pomap 3.0.7 · OCaml Package

Interface to partially ordered maps

Modules and types

module Store : Store_intf.STORE

Store module used to store nodes of the partially ordered map.

type key

Type of map keys

type +'a node

Type of nodes in the partially ordered map

type +'a pomap

Type of partially ordered maps

type +'a add_find_result =

| Found of Store.Ix.t * 'a node
| Added of Store.Ix.t * 'a node * 'a pomap

Type of result originating from an add_find operation

Map-constructors

val empty : 'a pomap

The empty partially ordered map.

val singleton : key -> 'a -> 'a pomap

singleton k el

returns
a partially ordered map containing as only binding the one from k to el.

Information on maps

val is_empty : 'a pomap -> bool

is_empty pm tests whether partially ordered map pm is empty.

val cardinal : 'a pomap -> int

cardinal pm

returns
the number of elements in pm.

Adding and removing

val add : key -> 'a -> 'a pomap -> 'a pomap

add k el pm

returns
a partially ordered map containing the same bindings as pm, plus a binding of k to el. If k was already bound in pm, its previous binding disappears.

val add_node : 'a node -> 'a pomap -> 'a pomap

add_node node pm

returns
a partially ordered map containing the same bindings as pm plus a binding as represented by node. If the associated key already existed in pm, its previous binding disappears.

val remove : key -> 'a pomap -> 'a pomap

remove k pm

returns
a map containing the same bindings as pm except for the node with key k.

val remove_node : 'a node -> 'a pomap -> 'a pomap

remove_node node pm

returns
a map containing the same bindings as pm except for the one with the key of node.

val remove_ix : Store.Ix.t -> 'a pomap -> 'a pomap

remove_ix ix pm

returns
a map containing the same bindings as pm except for the node indexed by ix.

raises Not_found
if ix does not index any node.

val take : key -> 'a pomap -> Store.Ix.t * 'a node * 'a pomap

take k pm

returns
a tuple (ix, node, map), where ix is the index of the node associated with key k in pm, and map is pm without this element.

raises Not_found
if there is no binding for key.

val take_ix : Store.Ix.t -> 'a pomap -> 'a node * 'a pomap

take_ix ix pm

returns
a tuple (n, m), where n is the node associated with index ix, and m is a map without this element.

raises Not_found
if ix does not index any node.

val add_find : key -> 'a -> 'a pomap -> 'a add_find_result

add_find k el pm similar to add, but if the binding did already exist, then Found (ix, node) will be returned to indicate the index and node under which key k is bound. Otherwise Added (new_ix, new_pm) will be returned to indicate that k was bound under new index new_ix in the partially ordered map new_pm.

val add_fun : key -> 'a -> ('a -> 'a) -> 'a pomap -> 'a pomap

add_fun k el f pm similar to add, but if the binding already existed, then function f will be applied to the previously bound data. Otherwise the binding will be added as in add.

Scanning and searching

val mem : key -> 'a pomap -> bool

mem k pm

returns
true if pm contains a binding for key k and false otherwise.

val mem_ix : Store.Ix.t -> 'a pomap -> bool

mem el pm

returns
true if pm contains a binding for data element el and false otherwise.

val find : key -> 'a pomap -> Store.Ix.t * 'a node

find k pm

returns
a tuple (ix, node), where ix is the index of key k and node its associated node in map pm.

raises Not_found
if no such binding exists.

val find_ix : Store.Ix.t -> 'a pomap -> 'a node

find_ix ix pm

returns
the node associated with index ix in map pm.

raises Not_found
if such a node does not exist.

val choose : 'a pomap -> Store.Ix.t * 'a node

choose pm

returns
a tuple (ix, node), where ix is the index of the node of some unspecified element in pm.

raises Not_found
if pm is empty.

val filter : (Store.Ix.t -> 'a node -> bool) -> 'a pomap -> 'a pomap

filter p pm

returns
the map of all elements in pm that satisfy p.

val partition : 
  (Store.Ix.t -> 'a node -> bool) ->
  'a pomap ->
  'a pomap * 'a pomap

partition p pm

returns
a pair of maps (pm1, pm2), where pm1 is the map of all the elements of pm that satisfy the predicate p, and pm2 is the map of all the elements of pm that do not satisfy p.

Iterators

val iter : ('a node -> unit) -> 'a pomap -> unit

iter f pm applies f to all bound nodes in map pm. The order in which the nodes are passed to f is unspecified. Only current bindings are presented to f: bindings hidden by more recent bindings are not passed to f.

val iteri : (Store.Ix.t -> 'a node -> unit) -> 'a pomap -> unit

iteri f pm same as iter, but function f also receives the index associated with the nodes.

val map : ('a node -> 'b) -> 'a pomap -> 'b pomap

map f pm

returns
a map with all nodes in pm mapped from their original value to identical nodes whose data element is in the codomain of f. The order in which nodes are passed to f is unspecified.

val mapi : (Store.Ix.t -> 'a node -> 'b) -> 'a pomap -> 'b pomap

mapi f pm same as map, but function f also receives the index associated with the nodes.

val fold : ('a node -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

fold f pm a computes (f nN ... (f n1 a) ...), where n1 ... nN are the nodes in map pm. The order in which the nodes are presented to f is unspecified.

val foldi : (Store.Ix.t -> 'a node -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

foldi f pm a same as fold, but function f also receives the index associated with the nodes.

val topo_fold : ('a node -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

topo_fold f pm a computes (f nN ... (f n1 a) ...), where n1 ... nN are the nodes in map pm sorted in ascending topological order. Slower than fold.

val topo_foldi : (Store.Ix.t -> 'a node -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

topo_foldi f pm a same as topo_fold, but function f also receives the index associated with the nodes.

val topo_fold_ix : (Store.Ix.t -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

topo_fold_ix f pm a same as topo_fold, but function f only receives the index associated with the nodes.

val rev_topo_fold : ('a node -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

rev_topo_fold f pm a computes (f nN ... (f n1 a) ...), where n1 ... nN are the nodes in map pm sorted in descending topological order. Slower than fold.

val rev_topo_foldi : 
  (Store.Ix.t -> 'a node -> 'b -> 'b) ->
  'a pomap ->
  'b ->
  'b

rev_topo_foldi f pm a same as rev_topo_fold, but function f also receives the index associated with the nodes.

val rev_topo_fold_ix : (Store.Ix.t -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

rev_topo_fold_ix f pm a same as rev_topo_fold, but function f only receives the index associated with the nodes.

val chain_fold : ('a node list -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

chain_fold f pm a computes (f cN ... (f c1 a) ...), where c1 ... cN are the ascending chaines of nodes in map pm. Only useful for small maps, because of potentially exponential complexity.

val chain_foldi : 
  ((Store.Ix.t * 'a node) list -> 'b -> 'b) ->
  'a pomap ->
  'b ->
  'b

chain_foldi f pm a same as chain_fold, but function f receives chains including the index associated with the nodes.

val rev_chain_fold : ('a node list -> 'b -> 'b) -> 'a pomap -> 'b -> 'b

rev_chain_fold f pm a computes (f cN ... (f c1 a) ...), where c1 ... cN are the descending chaines of nodes in map pm. Only useful for small maps, because of potentially exponential complexity.

val rev_chain_foldi : 
  ((Store.Ix.t * 'a node) list -> 'b -> 'b) ->
  'a pomap ->
  'b ->
  'b

rev_chain_foldi f pm a same as rev_chain_fold, but function f receives chains including the index associated with the nodes.

Set-like map-operations

val union : 'a pomap -> 'a pomap -> 'a pomap

union pm1 pm2 merges pm1 and pm2, preserving the bindings of pm1.

val inter : 'a pomap -> 'a pomap -> 'a pomap

inter pm1 pm2 intersects pm1 and pm2, preserving the bindings of pm1.

val diff : 'a pomap -> 'a pomap -> 'a pomap

diff pm1 pm2 removes all elements of pm2 from pm1.

Node-creators and accessors

val create_node : key -> 'a -> Store.Ix.Set.t -> Store.Ix.Set.t -> 'a node

create_node k el sucs prds

returns
a node with key k, data element el, successors sucs and predecessors prds.

val get_key : 'a node -> key

get_key n

returns
the key associated with node n.

val get_el : 'a node -> 'a

get_el n

returns
the data element associated with node n.

val get_sucs : 'a node -> Store.Ix.Set.t

get_sucs n

returns
the successors associated with node n.

val get_prds : 'a node -> Store.Ix.Set.t

get_prds n

returns
the predecessors associated with node n.

val set_key : 'a node -> key -> 'a node

set_key n k sets the key of node n to k and returns new node.

val set_el : 'a node -> 'a -> 'a node

set_el n el sets the data element of node n to el and returns new node.

val set_sucs : 'a node -> Store.Ix.Set.t -> 'a node

set_sucs n sucs set the successors of node n to sucs and returns new node.

val set_prds : 'a node -> Store.Ix.Set.t -> 'a node

set_prds n prds set the predecessors of node n to prds and returns new node.

Map-accessors

val get_nodes : 'a pomap -> 'a node Store.t

get_nodes pm

returns
the store of nodes associated with partially ordered map pm. This store represents the Hasse-graph of the nodes partially ordered by their keys.

val get_top : 'a pomap -> Store.Ix.Set.t

get_top pm

returns
the set of node indices of nodes that are greater than any other node in pm but themselves.

val get_bot : 'a pomap -> Store.Ix.Set.t

get_bot pm

returns
the set of node indices of nodes that are lower than any other node in pm but themselves.

Operations over equivalences of data elements

val remove_eq_prds : ('a -> 'a -> bool) -> 'a pomap -> 'a pomap

remove_eq_prds eq pm

returns
a map containing the same bindings as pm except for nodes whose non-empty predecessors all have the same data element as identified by eq.

val fold_eq_classes : 
  ('a -> 'a -> bool) ->
  ('a -> 'a pomap -> 'b -> 'b) ->
  'a pomap ->
  'b ->
  'b

fold_eq_classes eq f pm a factorizes pm into maximal equivalence classes of partial orders: all bindings in each class have equivalent data elements as identified by eq and are connected in the original Hasse-diagram. This function then computes (f ec_elN ecN ... (f ec_el1 ec1 a)), where ec1 ... ecN are the mentioned equivalence classes in unspecified order, and ec_el1 ... ec_elN are their respective common data elements.

val fold_split_eq_classes : 
  ('a -> 'a -> bool) ->
  ('a -> 'a pomap -> 'b -> 'b) ->
  'a pomap ->
  'b ->
  'b

fold_split_eq_classes eq f pm a same as fold_eq_classes, but the equivalence classes are split further so that no element of other classes would fit between its bottom and top elements. It is unspecified how non-conflicting elements are assigned to upper or lower classes!

val preorder_eq_classes : ('a -> 'a -> bool) -> 'a pomap -> 'a pomap list

preorder_eq_classes eq pm

returns
a preordered list of equivalence classes, the latter being defined as in fold_split_eq_classes.

val topo_fold_reduced : 
  ('a -> 'a -> bool) ->
  ('a node -> 'b -> 'b) ->
  'a pomap ->
  'b ->
  'b

topo_fold_reduced eq f pm a computes (f nN ... (f n1 a) ...), where n1 ... nN are those nodes in map pm sorted in ascending topological order, whose data element is equivalent as defined by eq to the one of lower elements if there are no intermediate elements that violate this equivalence.

Unsafe operations - USE WITH CAUTION!

val unsafe_update : 'a pomap -> Store.Ix.t -> 'a node -> 'a pomap

unsafe_update pm ix node updates the node associated with node index ix in map pm with node. The Hasse-diagram associated with the partially ordered map pm may become inconsistent if the new node violates the partial order structure. This can lead to unpredictable results with other functions!

val unsafe_set_nodes : 'a pomap -> 'a node Store.t -> 'a pomap

unsafe_set_nodes pm s updates the node store associated with map pm with s. This assumes that s stores a consistent Hasse-diagram of nodes.

val unsafe_set_top : 'a pomap -> Store.Ix.Set.t -> 'a pomap

unsafe_set_top pm set updates the index of top nodes in map pm with set. This assumes that the nodes referenced by the node indices in set do not violate the properties of the Hasse-diagram of pm.

val unsafe_set_bot : 'a pomap -> Store.Ix.Set.t -> 'a pomap

unsafe_set_bot pm set updates the index of bottom nodes in map pm with set. This assumes that the nodes referenced by the node indices in set do not violate the properties of the Hasse-diagram of pm.

package pomap