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
add k el pm
pm
, plus a binding of k
to el
. If k
was already
bound in pm
, its previous binding disappears.add_node node pm
pm
plus a binding as represented by
node
. If the associated key already existed in pm
, its previous
binding disappears.remove_node node pm
pm
except for the one with the key of node
.val remove_ix : Store.Ix.t ‑> 'a pomap ‑> 'a pomap
remove_ix ix pm
pm
except for the node indexed by ix
.ix
does not index any node.val take : key ‑> 'a pomap ‑> Store.Ix.t * 'a node * 'a pomap
take k pm
(ix, node, map)
, where ix
is
the index of the node
associated with key k
in pm
, and map
is pm
without this element.key
.val take_ix : Store.Ix.t ‑> 'a pomap ‑> 'a node * 'a pomap
take_ix ix pm
(n, m)
, where n
is the node
associated with index ix
, and m
is a map without this element.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
.
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
.
val mem_ix : Store.Ix.t ‑> 'a pomap ‑> bool
mem el pm
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
(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
ix
in map pm
.val choose : 'a pomap ‑> Store.Ix.t * 'a node
choose pm
(ix, node)
, where ix
is the
index of the node
of some unspecified element in pm
.pm
is empty.val filter : (Store.Ix.t ‑> 'a node ‑> bool) ‑> 'a pomap ‑> 'a pomap
filter p pm
pm
that
satisfy p
.val partition : (Store.Ix.t ‑> 'a node ‑> bool) ‑> 'a pomap ‑> 'a pomap * 'a pomap
partition p pm
(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
.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.
map f pm
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.
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.
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.
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.
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.
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.
val create_node : key ‑> 'a ‑> Store.Ix.Set.t ‑> Store.Ix.Set.t ‑> 'a node
create_node k el sucs prds
k
, data
element el
, successors sucs
and predecessors prds
.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.
get_nodes pm
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
pm
but themselves.val get_bot : 'a pomap ‑> Store.Ix.Set.t
get_bot pm
pm
but themselves.remove_eq_prds eq pm
pm
except for nodes whose non-empty predecessors
all have the same data element as identified by eq
.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
fold_split_eq_classes
.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.
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!
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
.