Module type Pomap_intf.POMAP

module type POMAP = sig .. end
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
Raises Not_found if ix does not index any node.
Returns a map containing the same bindings as pm except for the node indexed by ix.
val take : key ->
'a pomap ->
Store.Ix.t * 'a node * 'a pomap
take k pm
Raises Not_found if there is no binding for key.
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.
val take_ix : Store.Ix.t ->
'a pomap ->
'a node * 'a pomap
take_ix ix pm
Raises Not_found if ix does not index any node.
Returns a tuple (n, m), where n is the node associated with index ix, and m is a map without this element.
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
Raises Not_found if no such binding exists.
Returns a tuple (ix, node), where ix is the index of key k and node its associated node in map pm.
val find_ix : Store.Ix.t -> 'a pomap -> 'a node
find_ix ix pm
Raises Not_found if such a node does not exist.
Returns the node associated with index ix in map pm.
val choose : 'a pomap -> Store.Ix.t * 'a node
choose pm
Raises Not_found if pm is empty.
Returns a tuple (ix, node), where ix is the index of the node of some unspecified element in pm.
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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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 Pomap_intf.POMAP.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.