Source file store_intf.ml

(* POMAP - Library for manipulating partially ordered maps

   Copyright (C) 2001-2002 Markus Mottl (OEFAI) email: markus.mottl@gmail.com
   WWW: http://www.ocaml.info

   This library is free software; you can redistribute it and/or modify it under
   the terms of the GNU Lesser General Public License as published by the Free
   Software Foundation; either version 2.1 of the License, or (at your option)
   any later version.

   This library is distributed in the hope that it will be useful, but WITHOUT
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
   FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
   details.

   You should have received a copy of the GNU Lesser General Public License
   along with this library; if not, write to the Free Software Foundation, Inc.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *)

(** Specification of indices used to index elements in stores *)
module type INDEX = sig
  type t = int
  (** Type of indices *)

  type gen
  (** Type of index generators *)

  module Set : module type of Ptset
  (** Efficient sets of indices *)

  module Map : Map.S with type key = t
  (** Efficient maps of indices *)

  val start : gen
  (** The start state of the index generator *)

  val next_ix : gen -> t
  (** [next_ix gen]

      @return the next index that generator [gen] will produce. *)

  val next : gen -> t * gen
  (** [next gen]

      @return
        the tuple of [(new_ix, new_gen)], where [new_ix] is the next index and
        [new_gen] the next state of the index generator. *)

  val remove_ix : gen -> t -> gen
  (** [remove_ix gen ix]

      @return
        an updated index generator which is guaranteed to never return index
        [ix] or any other previously returned index. *)

  val int_of_ix : t -> int
  (** [int_of_ix ix] converts index [ix] to an integer.
      @raise Failure if index out of range for machine integers. *)
end

(** Interface to stores *)
module type STORE = sig
  module Ix : INDEX
  (** Index module used to index elements in the store *)

  type +'a t
  (** Type of stores *)

  val empty : 'a t
  (** The empty store *)

  val is_empty : 'a t -> bool
  (** [is_empty s]

      @return [true] if [s] is empty, [false] otherwise. *)

  val cardinal : 'a t -> int
  (** [cardinal s]

      @return the number of elements in [s]. *)

  val next_ix : 'a t -> Ix.t
  (** [next_ix s]

      @return the next index the store [s] will use to index a new element. *)

  val singleton : 'a -> Ix.t * 'a t
  (** [singleton el]

      @return
        the tuple [(ix, store)], where [ix] is the index under which the only
        element [el] was stored, and [store] is the store containing [el]. *)

  val add : 'a -> 'a t -> Ix.t * 'a t
  (** [add el s]

      @return
        the tuple [(new_ix, new_store)], where [new_ix] is the index under which
        the new element [el] was stored, and [new_store] is the new store
        containing [el]. *)

  val find : Ix.t -> 'a t -> 'a
  (** [find ix s]

      @return the element stored under index [ix].
      @raise Not_found if index [ix] not bound. *)

  val update : Ix.t -> 'a -> 'a t -> 'a t
  (** [update ix el s] rebinds index [ix] in store [s] to point to [el], and
      returns the resulting store. The previous binding disappears. New indices
      resulting from further adds are guaranteed to have higher indices.
      @raise Not_found if index [ix] not bound. *)

  val remove : Ix.t -> 'a t -> 'a t
  (** [remove ix s] removes the binding of index [ix] of store [s], and returns
      the resulting store. *)

  val iter : ('a -> unit) -> 'a t -> unit
  (** [iter f s] applies [f] to all stored elements in store [s]. The order in
      which elements are passed to [f] is unspecified. *)

  val iteri : (Ix.t -> 'a -> unit) -> 'a t -> unit
  (** [iter f s] applies [f] to all indexes and their related elements in store
      [s]. The order in which elements are passed to [f] is unspecified. *)

  val map : ('a -> 'b) -> 'a t -> 'b t
  (** [map f s]

      @return
        a store with all elements in [s] mapped from their original value to the
        codomain of [f]. Only the elements are passed to [f]. The order in which
        elements are passed to [f] is unspecified. *)

  val mapi : (Ix.t -> 'a -> 'b) -> 'a t -> 'b t
  (** [mapi f s] same as [map], but function [f] also receives the index
      associated with the elements. *)

  val fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  (** [fold f s a] computes [(f eN ... (f e1 a) ...)], where [e1 ... eN] are the
      elements of all bindings in store [s]. The order in which the bindings are
      presented to [f] is unspecified. *)

  val foldi : (Ix.t -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  (** [foldi f s a] same as [fold], but function [f] also receives the index
      associated with the elements. *)

  val to_list : 'a t -> (Ix.t * 'a) list
  (** [to_list s] converts [s] to an association list of indices and elements. *)

  val choose : 'a t -> Ix.t * 'a
  (** [choose s]

      @return
        a tuple [(ix, x)], where [ix] is the index of some unspecified value [x]
        in store [s].
      @raise Not_found if [s] is empty. *)

  val filter : (Ix.t -> 'a -> bool) -> 'a t -> 'a t
  (** [filter p s]

      @return the store of all elements in [s] that satisfy [p]. *)

  val partition : (Ix.t -> 'a -> bool) -> 'a t -> 'a t * 'a t
  (** [partition p s]

      @return
        a pair of stores [(s1, s2)], where [s1] is the store of all the elements
        of [s] that satisfy the predicate [p], and [s2] is the store of all the
        elements of [s] that do not satisfy [p]. *)

  val eq_classes : ('a -> 'a -> bool) -> 'a t -> ('a * 'a t) list
  (** [eq_classes eq s]

      @return
        a list of tuples [(el, ec)], where [el] is the only kind of element as
        identified by the equivalence relation [eq] stored in the equivalence
        class (store) [ec] under each index. Every such equivalence class is
        unique and maximal with respect to [s], and the original indices of the
        elements are preserved in each class. *)

  val get_ix_map : 'a t -> 'a Ix.Map.t
  (** [get_ix_map s]

      @return
        a map of all indices mapped to their respective elements in store [s]. *)
end