# Module type Cf_map.T

    module type T = sig .. end

    type +'a t

The tree type.

    module Key: sig .. end

A module defining the type of the key.

    val nil : 'a t

The empty tree.

    val empty : 'a t -> bool

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

    val size : 'a t -> int

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

    val min : 'a t -> Key.t * 'a

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.

    val max : 'a t -> Key.t * 'a

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.

    val search : Key.t -> 'a t -> 'a

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.

    val member : Key.t -> 'a t -> bool

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

    val insert : Key.t * 'a -> 'a t -> 'a t * 'a option

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.

    val replace : Key.t * 'a -> 'a t -> 'a t

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.

    val modify : Key.t -> ('a -> 'a) -> 'a t -> 'a t

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.

    val extract : Key.t -> 'a t -> 'a * 'a t

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.

    val delete : Key.t -> 'a t -> 'a t

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.

    val of_list : (Key.t * 'a) list -> 'a t

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.

    val of_list_incr : (Key.t * 'a) list -> 'a t

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

    val of_list_decr : (Key.t * 'a) list -> 'a t

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

    val of_seq : (Key.t * 'a) Cf_seq.t -> 'a t

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.

    val of_seq_incr : (Key.t * 'a) Cf_seq.t -> 'a t

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

    val of_seq_decr : (Key.t * 'a) Cf_seq.t -> 'a t

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

    val to_list_incr : 'a t -> (Key.t * 'a) list

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

    val to_list_decr : 'a t -> (Key.t * 'a) list

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

    val to_seq_incr : 'a t -> (Key.t * 'a) Cf_seq.t

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

    val to_seq_decr : 'a t -> (Key.t * 'a) Cf_seq.t

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

    val nearest_decr : Key.t -> 'a t -> (Key.t * 'a) Cf_seq.t

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.

    val nearest_incr : Key.t -> 'a t -> (Key.t * 'a) Cf_seq.t

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.

    val iterate : (Key.t * 'a -> unit) -> 'a t -> unit

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

    val predicate : (Key.t * 'a -> bool) -> 'a t -> bool

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

    val fold : ('b -> Key.t * 'a -> 'b) -> 'b -> 'a t -> 'b

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.

    val filter : (Key.t * 'a -> bool) -> 'a t -> 'a t

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.

    val map : (Key.t * 'a -> 'b) -> 'a t -> 'b t

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.

    val optmap : (Key.t * 'a -> 'b option) -> 'a t -> 'b t

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.

    val partition : (Key.t * 'a -> bool) ->
           'a t -> 'a t * 'a t

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.