Page
Library
Module
Module type
Parameter
Class
Class type
Source
Pomap_impl.Make
Sourcemodule PO : Pomap_intf.PARTIAL_ORDER
Store module used to store nodes of the partially ordered map.
Type of nodes in the partially ordered map
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
remove_ix ix pm
take_ix ix pm
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
.
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
.
mem el pm
find k pm
find_ix ix pm
choose pm
filter p pm
partition p pm
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
.
iteri f pm
same as iter
, but function f
also receives the index associated with the nodes.
mapi f pm
same as map
, but function f
also receives the index associated with the nodes.
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.
foldi f pm a
same as fold
, but function f
also receives the index associated with the nodes.
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
.
topo_foldi f pm a
same as topo_fold
, but function f
also receives the index associated with the nodes.
topo_fold_ix f pm a
same as topo_fold
, but function f
only receives the index associated with the nodes.
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
.
rev_topo_foldi f pm a
same as rev_topo_fold
, but function f
also receives the index associated with the nodes.
rev_topo_fold_ix f pm a
same as rev_topo_fold
, but function f
only receives the index associated with the nodes.
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.
chain_foldi f pm a
same as chain_fold
, but function f
receives chains including the index associated with the nodes.
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.
rev_chain_foldi f pm a
same as rev_chain_fold
, but function f
receives chains including the index associated with the nodes.
union pm1 pm2
merges pm1
and pm2
, preserving the bindings of pm1
.
inter pm1 pm2
intersects pm1
and pm2
, preserving the bindings of pm1
.
create_node k el sucs prds
get_sucs n
get_prds n
set_key n k
sets the key of node n
to k
and returns new node.
set_el n el
sets the data element of node n
to el
and returns new node.
set_sucs n sucs
set the successors of node n
to sucs
and returns new node.
set_prds n prds
set the predecessors of node n
to prds
and returns new node.
get_top pm
get_bot pm
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!
preorder_eq_classes eq pm
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_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!
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.
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
.
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
.