Functor Cf_rbtree.Map

The tree type.

The empty tree.

Use empty m to test whether the tree m is empty.

Use size m to count the number of elements in the tree m.

Use min m to obtain the key-value pair with the ordinally minimum key in the tree m. Raises Not_found if the tree is empty.

Use max m to obtain the key-value pair with the ordinally maximum key in the tree m. Raises Not_found if the tree is empty.

Use search k m to obtain the value associated with the key k in the tree m. Raise Not_found if the tree does not contain the key.

Use member k m to test whether the tree m contains the key k.

Use insert p m to insert the key-value pair p into the tree m, producing a new tree with the inserted element and, if the key k is already present in m, the value replaced by the insertion.

Use replace p m to obtain a new tree produced by inserting the key-value pair p into the tree m, replacing any existing pair associated to the same key.

Use modify k f m to obtain a new tree produced by replacing the value in the tree m associated with the key k with the result of applying it to the continuation function f. Raises Not_found if the tree does not contain the key.

Use extract k m to obtain the value associated with the key k in the tree m and a new tree with the key deleted from the tree. Raises Not_found if the tree does not contain the key.

Use delete k m to obtain a new tree produced by deleting the key k from the tree m. If the tree does not contain the key, then the function simply returns its argument.

Use of_list s to compose a tree by iterating the list of key-value pairs s and inserting them in order into a new tree.

Use of_list_incr s to compose a tree with the key-value pairs in the ordered list s. Runs in linear time if the keys in the list s are known to be in increasing order. Otherwise, there is an additional linear cost beyond of_list s.

Use of_list_decr s to compose a tree with the key-value pairs in the ordered list s. Runs in linear time if the keys in the list s are known to be in decreasing order. Otherwise, there is an additional linear cost beyond of_list s.

Use of_seq z to compose a tree by evaluating the entire sequence of key-value pairs z and inserting them in order into a new tree.

Use of_seq_incr z to compose a tree with the key-value pairs in the ordered sequence z. Runs in linear time if the keys in the sequence z are known to be in increasing order. Otherwise, there is an additional linear cost beyond of_seq z.

Use of_seq_decr z to compose a tree with the key-value pairs in the ordered sequence z. Runs in linear time if the keys in the sequence z are known to be in decreasing order. Otherwise, there is an additional linear cost beyond of_seq z.

Use to_list_incr m to obtain a sequence of the key-value pairs in the tree m in order of increasing ordinality.

Use to_list_decr m to obtain a sequence of the key-value pairs in the tree m in order of descreasing ordinality.

Use to_seq_incr m to obtain a sequence of the key-value pairs in the tree m in order of increasing ordinality.

Use to_seq_decr m to obtain a sequence of the key-value pairs in the tree m in order of descreasing ordinality.

Use nearest_decr k m to obtain the key-value pair ordinally less than or equal to the key k in the map m. Raises Not_found if the map is empty or all the keys are ordinally greater.

Use nearest_incr k m to obtain the key-value pair ordinally greater than or equal to the key k in the map m. Raises Not_found if the map is empty or all the keys are ordinally less.

Use iterate f m to apply the function f to each key-value pair in the tree m in an arbitrary order (not increasing or decreasing).

Use predicate f m to test whether all the key-value pairs in the tree m satisfy the predicate function f. The nodes of the tree are visited in an arbitrary order (not increasing or decreasing).

Use fold f s m to fold the every key-value pair in the tree m into the state s with the folding function f, visiting the elements in an arbitrary order (not increasing or decreasing). Runs in O(log N) space, i.e. not tail-recursive.

Use filter f m to obtain a new tree comprised of all the key-value pairs in the tree m that satisfy the filtering function f. The elements in m are visited in arbitrary order (not increasing or decreasing). Runs in O(log N) space, i.e. not tail-recursive.

Use map f m to obtain a new tree produced by applying the mapping function f to the key and the value of each key-value pair in the tree m and associating the resulting value to the key in the new tree. Elements in the tree are visited in arbitrary order (not increasing or descreasing. Runs in O(log N) space, i.e. not tail-recursive.

Use optmap f m to obtain a new tree produced by applying the mapping function f to the key and the value of each key-value pair in the tree m and associating the resulting value to the key in the new tree. If the function f returns None then no value for that key will be present in the new tree. Elements in the tree are visited in arbitrary order (not increasing or descreasing. Runs in O(log N) space, i.e. not tail-recursive.

Use partition f m to obtain a pair of new trees produced by applying the partitioning function f to all the elements in the tree m in an arbitrary order (not increasing or descreasing). The first tree will contain all the elements for which f returns true, and the second tree will have all the elements for which f returns false. Runs in O(log N) space, i.e. not tail-recursive.