Module Pomap.Pomap_impl.Make

The empty partially ordered map.

singleton k el

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

is_empty pm tests whether partially ordered map pm is empty.

cardinal pm

• Returns the number of elements in pm.

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.

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.

remove k pm

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

remove_node node pm

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

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.

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.

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.

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 k pm

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

mem el pm

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

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.

find_ix ix pm

• Returns the node associated with index ix in map pm.
• Raises Not_found: if such a node does not exist.

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.

filter p pm

• Returns the map of all elements in pm that satisfy p.

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.

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.

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.

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.

diff pm1 pm2 removes all elements of pm2 from pm1.

create_node k el sucs prds

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

get_key n

• Returns the key associated with node n.

get_el n

• Returns the data element associated with node n.

get_sucs n

• Returns the successors associated with node n.

get_prds n

• Returns the predecessors associated with node 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_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.

get_top pm

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

get_bot pm

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

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.

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.

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

• Returns a preordered list of equivalence classes, the latter being defined as in 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.

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.