Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

`module PO : Pomap_intf.PARTIAL_ORDER`

`module Store : Store_intf.STORE`

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

`type key = PO.el`

Type of map keys

`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

`val empty : 'a pomap`

The empty partially ordered map.

`val is_empty : 'a pomap -> bool`

`is_empty pm`

tests whether partially ordered map `pm`

is empty.

`val cardinal : 'a pomap -> int`

`cardinal pm`

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

`remove_ix ix pm`

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

`take k pm`

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

`take_ix ix pm`

`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`

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

`find k pm`

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

`find_ix ix pm`

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

`choose pm`

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

`filter p pm`

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

`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`

.

`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 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.

`union pm1 pm2`

merges `pm1`

and `pm2`

, preserving the bindings of `pm1`

.

`inter pm1 pm2`

intersects `pm1`

and `pm2`

, preserving the bindings of `pm1`

.

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

`create_node k el sucs prds`

`val get_el : 'a node -> 'a`

`get_el n`

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

`get_sucs n`

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

`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.

`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.

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

`get_top pm`

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

`get_bot pm`

`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!

`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`

.

On This Page