# Module Core_set_intf.Map

    module Map: Core_map

    module Tree: sig .. end

    type ('key, +'value, 'cmp) t

    val invariants : ('a, 'b, 'c) t -> bool

Test if invariants of internal AVL search tree hold.

    val comparator : ('a, 'b, 'cmp) t -> ('a, 'cmp) Comparator.t

    val empty : comparator:('a, 'cmp) Comparator.t -> ('a, 'b, 'cmp) t

the empty map

    val singleton : comparator:('a, 'cmp) Comparator.t -> 'a -> 'b -> ('a, 'b, 'cmp) t

map with one key, data pair

    val of_alist : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) list -> [ `Duplicate_key of 'a | `Ok of ('a, 'b, 'cmp) t ]

creates map from association list with unique keys

    val of_alist_or_error : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) list -> ('a, 'b, 'cmp) t Or_error.t

creates map from association list with unique keys. Returns an error if duplicate 'a keys are found.

    val of_alist_exn : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) list -> ('a, 'b, 'cmp) t

creates map from association list with unique keys. Raises an exception if duplicate 'a keys are found.

    val of_alist_multi : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) list -> ('a, 'b list, 'cmp) t

creates map from association list with possibly repeated keys.

    val of_alist_fold : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) list -> init:'c -> f:('c -> 'b -> 'c) -> ('a, 'c, 'cmp) t

combines an association list into a map, folding together bound values with common keys

    val of_alist_reduce : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) list -> f:('b -> 'b -> 'b) -> ('a, 'b, 'cmp) t

combines an association list into a map, reducing together bound values with common keys

    val to_tree : ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) Tree.t

    val of_tree : comparator:('k, 'cmp) Comparator.t ->
           ('k, 'v, 'cmp) Tree.t -> ('k, 'v, 'cmp) t

Creates a `t` from a `Tree.t` and a `Comparator.t`. This is an O(n) operation as it must discover the length of the `Tree.t`.

    val of_sorted_array : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) array -> ('a, 'b, 'cmp) t Or_error.t

creates map from sorted array of key-data pairs. The input array must be sorted, as given by the relevant comparator (either in ascending or descending order), and must not contain any duplicate keys. If either of these conditions do not hold, an error is returned.

    val of_sorted_array_unchecked : comparator:('a, 'cmp) Comparator.t ->
           ('a * 'b) array -> ('a, 'b, 'cmp) t

Like `of_sorted_array` except behavior is undefined when an `Error` would have been returned.

    val is_empty : ('a, 'b, 'c) t -> bool

Test whether a map is empty or not.

    val length : ('a, 'b, 'c) t -> int

`length map`
Returns number of elements in `map`. O(1), but `Tree.length` is O(n).

    val add : ('k, 'v, 'cmp) t -> key:'k -> data:'v -> ('k, 'v, 'cmp) t

returns a new map with the specified new binding; if the key was already bound, its previous binding disappears.

    val add_multi : ('k, 'v list, 'cmp) t ->
           key:'k -> data:'v -> ('k, 'v list, 'cmp) t

if key is not present then add a singleton list, otherwise, cons data on the head of the existing list.

    val change : ('k, 'v, 'cmp) t ->
           'k -> ('v option -> 'v option) -> ('k, 'v, 'cmp) t

`change map key f` updates the given map by changing the value stored under `key` according to `f`. Thus, for example, one might write:

    change m k (function None -> Some 0 | Some x -> Some (x + 1))

to produce a new map where the integer stored under key `k` is incremented by one (treating an unknown key as zero).

    val find : ('k, 'v, 'cmp) t -> 'k -> 'v option

returns the value bound to the given key, raising `Not_found` if none such exists

    val find_exn : ('k, 'v, 'cmp) t -> 'k -> 'v

    val remove : ('k, 'v, 'cmp) t -> 'k -> ('k, 'v, 'cmp) t

returns a new map with any binding for the key in question removed

    val mem : ('k, 'a, 'cmp) t -> 'k -> bool

`mem map key` tests whether `map` contains a binding for `key`

    val iter : ('k, 'v, 'a) t -> f:(key:'k -> data:'v -> unit) -> unit

iterator for map

    val iter2 : ('k, 'v1, 'cmp) t ->
           ('k, 'v2, 'cmp) t ->
           f:(key:'k ->
              data:[ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> unit) ->
           unit

Iterate two maps side by side. Complexity of this function is O(M+N). If two inputs are `(0, a); (1, a)` and `(1, b); (2, b)`, `f` will be called with `(0, `Left a); (1, `Both (a, b)); (2, `Right b)`

    val map : ('k, 'v1, 'cmp) t -> f:('v1 -> 'v2) -> ('k, 'v2, 'cmp) t

returns new map with bound values replaced by f applied to the bound values

    val mapi : ('k, 'v1, 'cmp) t ->
           f:(key:'k -> data:'v1 -> 'v2) -> ('k, 'v2, 'cmp) t

like `map`, but function takes both key and data as arguments

    val fold : ('k, 'v, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a

folds over keys and data in map in increasing order of key.

    val fold_right : ('k, 'v, 'b) t -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a

folds over keys and data in map in decreasing order of key.

    val filter : ('k, 'v, 'cmp) t ->
           f:(key:'k -> data:'v -> bool) -> ('k, 'v, 'cmp) t

`filter`, `filter_map`, and `filter_mapi` run in O(n * lg n) time; they simply accumulate each key & data retained by `f` into a new map using `add`.

    val filter_map : ('k, 'v1, 'cmp) t ->
           f:('v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t

returns new map with bound values filtered by f applied to the bound values

    val filter_mapi : ('k, 'v1, 'cmp) t ->
           f:(key:'k -> data:'v1 -> 'v2 option) -> ('k, 'v2, 'cmp) t

like `filter_map`, but function takes both key and data as arguments

    val compare_direct : ('v -> 'v -> int) ->
           ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> int

Total ordering between maps. The first argument is a total ordering used to compare data associated with equal keys in the two maps.

    val equal : ('v -> 'v -> bool) ->
           ('k, 'v, 'cmp) t -> ('k, 'v, 'cmp) t -> bool

`equal cmp m1 m2` tests whether the maps `m1` and `m2` are equal, that is, contain equal keys and associate them with equal data. `cmp` is the equality predicate used to compare the data associated with the keys.

    val keys : ('k, 'a, 'b) t -> 'k list

returns list of keys in map

    val data : ('a, 'v, 'b) t -> 'v list

returns list of data in map

    val to_alist : ('k, 'v, 'a) t -> ('k * 'v) list

creates association list from map. No guarantee about order.

    val validate : name:('k -> string) ->
           'v Validate.check -> ('k, 'v, 'a) t Validate.check

###### Additional operations on maps

    val merge : ('k, 'v1, 'cmp) t ->
           ('k, 'v2, 'cmp) t ->
           f:(key:'k ->
              [ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> 'v3 option) ->
           ('k, 'v3, 'cmp) t

merges two maps

    val symmetric_diff : ('k, 'v, 'cmp) t ->
           ('k, 'v, 'cmp) t ->
           data_equal:('v -> 'v -> bool) ->
           ('k * [ `Left of 'v | `Right of 'v | `Unequal of 'v * 'v ]) Sequence.t

`symmetric_diff t1 t2 ~data_equal` returns a list of changes between `t1` and `t2`. It is intended to be efficient in the case where `t1` and `t2` share a large amount of structure.

    val min_elt : ('k, 'v, 'a) t -> ('k * 'v) option

`min_elt map`
Returns Some `(key, data)` pair corresponding to the minimum key in `map`, None if empty.

    val min_elt_exn : ('k, 'v, 'a) t -> 'k * 'v

    val max_elt : ('k, 'v, 'a) t -> ('k * 'v) option

`max_elt map`
Returns Some `(key, data)` pair corresponding to the maximum key in `map`, and None if `map` is empty.

    val max_elt_exn : ('k, 'v, 'a) t -> 'k * 'v

    val for_all : ('k, 'v, 'a) t -> f:('v -> bool) -> bool

same semantics as similar functions in List

    val exists : ('k, 'v, 'a) t -> f:('v -> bool) -> bool

    val split : ('k, 'v, 'cmp) t ->
           'k ->
           ('k, 'v, 'cmp) t * ('k * 'v) option * ('k, 'v, 'cmp) t

`split t key` returns a map of keys strictly less than `key`, the mapping of `key` if any, and a map of keys strictly greater than `key`. *

    val fold_range_inclusive : ('k, 'v, 'cmp) t ->
           min:'k -> max:'k -> init:'a -> f:(key:'k -> data:'v -> 'a -> 'a) -> 'a

`fold_range_inclusive t ~min ~max ~init ~f` folds f (with initial value ~init) over all keys (and their associated values) that are in the range `min, max` (inclusive).

    val range_to_alist : ('k, 'v, 'cmp) t -> min:'k -> max:'k -> ('k * 'v) list

`range_to_alist t ~min ~max` returns an associative list of the elements whose keys lie in `min, max` (inclusive), with the smallest key being at the head of the list.

    val closest_key : ('k, 'v, 'cmp) t ->
           [ `Greater_or_equal_to | `Greater_than | `Less_or_equal_to | `Less_than ] ->
           'k -> ('k * 'v) option

`closest_key t dir k` returns the `(key, value)` pair in `t` with `key` closest to `k`, which satisfies the given inequality bound.

For example, `closest_key t `Less_than k` would be the pair with the closest key to `k` where `key < k`.

`to_sequence` can be used to get the same results as `closest_key`. It is less efficient for individual lookups but more efficient for finding many elements starting at some value.

    val nth : ('k, 'v, 'a) t -> int -> ('k * 'v) option

`nth t n` finds the (key, value) pair of rank n (i.e. such that there are exactly n keys strictly less than the found key), if one exists. O(log(length t) + n) time.

    val rank : ('k, 'v, 'cmp) t -> 'k -> int option

`rank t k` if k is in t, returns the number of keys strictly less than k in t, otherwise None

    val to_sequence : ?order:[ `Decreasing_key | `Increasing_key ] ->
           ?keys_greater_or_equal_to:'k ->
           ?keys_less_or_equal_to:'k ->
           ('k, 'v, 'cmp) t -> ('k * 'v) Sequence.t

`to_sequence ?order ?keys_greater_or_equal_to ?keys_less_or_equal_to t` gives a sequence of key-value pairs between `keys_less_or_equal_to` and `keys_greater_or_equal_to` inclusive, presented in `order`. If `keys_greater_or_equal_to > keys_less_or_equal_to`, the sequence is empty. Cost is O(log n) up front and amortized O(1) to produce each element.

    module Poly: sig .. end
      with type ('a, 'b, 'c) map = ('a, 'b, 'c) t

    module type Key = Core_map_intf.Key

    module type Key_binable = Core_map_intf.Key_binable

    module type S = S
      with type ('a, 'b, 'c) map  := ('a, 'b, 'c) t
      with type ('a, 'b, 'c) tree := ('a, 'b, 'c) Tree.t

    module type S_binable = S_binable
      with type ('a, 'b, 'c) map  := ('a, 'b, 'c) t
      with type ('a, 'b, 'c) tree := ('a, 'b, 'c) Tree.t

    module Make: functor (Key : Key) -> S  with type Key.t = Key.t

    module Make_using_comparator: functor (Key : sig
    type t

    include Comparator.S

    val t_of_sexp : Sexplib.Sexp.t -> t
    val sexp_of_t : t -> Sexplib.Sexp.tend) -> S
        with type Key.t                  = Key.t
        with type Key.comparator_witness = Key.comparator_witness

    module Make_binable: functor (Key : Key_binable) -> S_binable  with type Key.t = Key.t

    module Make_binable_using_comparator: functor (Key : sig
    type t

    include Comparator.S

    val t_of_sexp : Sexplib.Sexp.t -> t
    val sexp_of_t : t -> Sexplib.Sexp.t
    val bin_t : t Bin_prot.Type_class.t
    val bin_read_t : t Bin_prot.Read.reader
    val __bin_read_t__ : (int -> t) Bin_prot.Read.reader
    val bin_reader_t : t Bin_prot.Type_class.reader
    val bin_size_t : t Bin_prot.Size.sizer
    val bin_write_t : t Bin_prot.Write.writer
    val bin_writer_t : t Bin_prot.Type_class.writerend) -> S_binable
        with type Key.t                  = Key.t
        with type Key.comparator_witness = Key.comparator_witness