`include module type of BatMap with module PMap := BatMap.PMap`
`module Pervasives := Stdlib`

Association tables over ordered types.

This module implements applicative association tables, also known as finite maps or dictionaries, given a total ordering function over the keys. All operations over maps are purely applicative (no side-effects). The implementation uses balanced binary trees, and therefore searching and insertion take time logarithmic in the size of the map.

Note OCaml, Batteries Included, provides two implementations of maps: polymorphic maps and functorized maps. Functorized maps (see `S` and `Make`) are slightly more complex to use but offer stronger type-safety. Polymorphic maps make it easier to shoot yourself in the foot. In case of doubt, you should use functorized maps.

##### Functorized maps

The important part is the `Make` module which builds association maps from a user-provided datatype and comparison function. In the `Make` module (or its output signature `S`) are documentated all functions available on maps.

Here is a typical example of use:

      module MyKeyType = struct
        type t = my_type
        let compare = my_compare_function
      end
      module MyMap = Map.Make(MyKeyType)

      let some_map = MyMap.add something MyMap.empty
            ...

To define maps with integer/string keys:

      module IntMap = Map.Make(Int)
      module StringMap = Map.Make(String)

- author Xavier Leroy (Base library)

- author Nicolas Cannasse

- author Markus Mottl

- author David Rajchenbach-Teller

- author Gabriel Scherer

`module type S = sig ... end`
`module Make (Ord : BatInterfaces.OrderedType) : S with type key = Ord.t with type 'a t = 'a Stdlib.Map.Make(Ord).t`

Functor building an implementation of the map structure given a totally ordered type.

## Common instantiations

*

`module Int : S with type key = int`
`module Int32 : S with type key = int32`
`module Int64 : S with type key = int64`
`module Nativeint : S with type key = nativeint`
`module Float : S with type key = float`
`module Char : S with type key = char`
`module String : S with type key = string`

##### Polymorphic maps

The functions below present the manipulation of polymorphic maps, as were provided by the Extlib PMap module.

They are similar in functionality to the functorized `Make` module, but only uses the `Pervasives.compare` function to compare elements. If you need to compare using a custom comparison function, it is recommended to use the functorized maps provided by `Make`.

`type (+'a, +'b) t`
`val empty : ('a, 'b) t`

The empty map, using `compare` as key comparison function.

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

Returns `true` if the map is empty.

`val singleton : 'a -> 'b -> ('a, 'b) t`

Creates a new map with a single binding.

`val cardinal : ('a, 'b) t -> int`

Return the number of bindings of a map.

`val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t`

`add x y m` returns a map containing the same bindings as `m`, plus a binding of `x` to `y`. If `x` was already bound in `m`, its previous binding disappears. If `x` was already bound to some `z` that is physically equal to `y`, then the returned map is physically equal to `m`.

- before 3.3.0

  or OCaml 4.03 physical equality was not ensured.

`val update : 'a -> 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t`

`update k1 k2 v2 m` replace the previous binding of `k1` in `m` by `k2` associated to `v2`. This is equivalent to `add k2 v2 (remove k1) m`, but more efficient in the case where `k1` and `k2` have the same key ordering. If `k1` and `k2` have the same key ordering and `v2` is physically equal to the value `k1` is bound to in `m` then the returned map will be physically equal to `m`

- raises `Not_found`

  if `k1` is not bound in `m`.

- since 2.4.0

- before 3.3.0

  physical equality was not ensured.

`val update_stdlib : 'a -> ('b option -> 'b option) -> ('a, 'b) t -> ('a, 'b) t`

`update_stdlib k f m` returns a map containing the same bindings as `m`, except `k` has a new binding as determined by `f`: First, calculate `y` as `f (find_opt k m)`. If `y = Some v` then `k` will be bound to `v` in the resulting map. Else `k` will not be bound in the resulting map.

If `v` is physically equal to the value of the previous binding of `k` in `m`, then the returned map will be physically equal to `m`.

This function does the same thing as `update` in the stdlib, but has a different name for backwards compatibility reasons.

- since 3.3.0

`val find_opt : 'a -> ('a, 'b) t -> 'b option`

`find_opt x m` returns Some b where b is the current binding * of `x` in `m`, or None if no such binding exists.

`val find_default : 'b -> 'a -> ('a, 'b) t -> 'b`

`find_default d x m` returns the current binding of `x` in `m`, or the default value `d` if no such binding exists.

`val find_first : ('a -> bool) -> ('a, 'b) t -> 'a * 'b`

`find_first f m` returns the first binding `(k, v)` for which `f k` is true or raises `Not_found` if there is no such binding. `f` must be monotonically increasing, i.e. if `k1 < k2 && f k1` is true then `f k2` must also be true.

- since 3.3.0

`val find_first_opt : ('a -> bool) -> ('a, 'b) t -> ('a * 'b) option`

`find_first_opt f m` returns `Some (k, v)` for the first binding `(k, v)` for which `f k` is true or returns `None` if there is no such binding. `f` must be monotonically increasing, i.e. if `k1 < k2 && f k1` is true then `f k2` must also be true.

- since 3.3.0

`val find_last : ('a -> bool) -> ('a, 'b) t -> 'a * 'b`

`find_last f m` returns the last binding `(k, v)` for which `f k` is true or raises `Not_found` if there is no such binding. `f` must be monotonically decreasing, i.e. if `k1 < k2 && f k2` is true then `f k1` must also be true.

- since 3.3.0

`val find_last_opt : ('a -> bool) -> ('a, 'b) t -> ('a * 'b) option`

`find_last_opt f m` returns `Some (k, v)` for the last binding `(k, v)` for which `f k` is true or returns `None` if there is no such binding. `f` must be monotonically decreasing, i.e. if `k1 < k2 && f k2` is true then `f k1` must also be true.

- since 3.3.0

`val remove : 'a -> ('a, 'b) t -> ('a, 'b) t`

`remove x m` returns a map containing the same bindings as `m`, except for `x` which is unbound in the returned map. The returned map is physically equal to the passed one if `x` was already unbound.

- before 3.3.0

  or OCaml 4.03 physical equality was not ensured.

`val remove_exn : 'a -> ('a, 'b) t -> ('a, 'b) t`

`remove_exn x m` behaves like `remove x m` except that it raises an exception if `x` is unbound in `m`.

- raises `Not_found`

  if `x` is unbound in `m`

- since 3.2.0

`val mem : 'a -> ('a, 'b) t -> bool`

`mem x m` returns `true` if `m` contains a binding for `x`, and `false` otherwise.

`val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit`

`iter f m` applies `f` to all bindings in map `m`. `f` receives the key as first argument, and the associated value as second argument. The order in which the bindings 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 map : ('b -> 'c) -> ('a, 'b) t -> ('a, 'c) t`

`map f m` returns a map with same domain as `m`, where the associated value `a` of all bindings of `m` has been replaced by the result of the application of `f` to `a`. The order in which the associated values are passed to `f` is unspecified.

`val mapi : ('a -> 'b -> 'c) -> ('a, 'b) t -> ('a, 'c) t`

Same as `map`, but the function receives as arguments both the key and the associated value for each binding of the map.

`val fold : ('b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c`

`fold f m a` computes `(f kN dN ... (f k1 d1 (f k0 d0 a))...)`, where `k0,k1..kN` are the keys of all bindings in `m`, and `d0,d1..dN` are the associated data. The order in which the bindings are presented to `f` is unspecified.

`val foldi : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c`

Same as `fold`, but the function receives as arguments both the key and the associated value for each binding of the map.

`val at_rank_exn : int -> ('key, 'a) t -> 'key * 'a`

`at_rank_exn i m` returns the `(key,value)` pair whose key is at rank `i` in `m`, that is the `i`-th element in increasing order of the keys (the `0`-th element being the smallest key in `m` with its associated value).

- raises `Not_found`

  if `m = empty`.

- raises `Invalid_argument`

  error_message if `i < 0 || i >= cardinal m`

- since 2.4

`val filterv : ('a -> bool) -> ('key, 'a) t -> ('key, 'a) t`

`filterv f m` returns a map where only the values `a` of `m` such that `f a = true` remain. The bindings are passed to `f` in increasing order with respect to the ordering over the type of the keys.

`val filter : ('key -> 'a -> bool) -> ('key, 'a) t -> ('key, 'a) t`

`filter f m` returns a map where only the `(key, value)` pairs of `m` such that `f key value = true` remain. The bindings are passed to `f` in increasing order with respect to the ordering over the type of the keys. If `f` returns `true` for all bindings of `m` the returned map is physically equal to `m`.

- before 3.3.0

  or OCaml 4.03 physical equality was not ensured.

`val filter_map : ('key -> 'a -> 'b option) -> ('key, 'a) t -> ('key, 'b) t`

`filter_map f m` combines the features of `filter` and `map`. It calls calls `f key0 a0`, `f key1 a1`, `f keyn an` where `a0..an` are the elements of `m` and `key0..keyn` the respective corresponding keys. It returns the map of `(keyi, bi)` pairs such as `f keyi ai = Some bi` (when `f` returns `None`, the corresponding element of `m` is discarded).

`val choose_opt : ('key, 'a) t -> ('key * 'a) option`

Return `Some (k, v)` for one binding `(k, v)` of the given map, if the map is not empty. Else, return None. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

- since 3.3.0

`val split : 'key -> ('key, 'a) t -> ('key, 'a) t * 'a option * ('key, 'a) t`

`split x m` returns a triple `(l, data, r)`, where `l` is the map with all the bindings of `m` whose key is strictly less than `x`; `r` is the map with all the bindings of `m` whose key is strictly greater than `x`; `data` is `None` if `m` contains no binding for `x`, or `Some v` if `m` binds `v` to `x`.

`val min_binding : ('key, 'a) t -> 'key * 'a`

Returns the binding with the smallest key. Raises Not_found if the map is empty.

`val min_binding_opt : ('key, 'a) t -> ('key * 'a) option`

Return `Some (key, value)` for the `key, value` pair with the smallest key, or `None` if the map is empty.

- since 3.3.0

`val pop_min_binding : ('key, 'a) t -> ('key * 'a) * ('key, 'a) t`

Returns the binding with the smallest key along with the rest of the map.

`val max_binding : ('key, 'a) t -> 'key * 'a`

Return the `(key, value)` pair with the largest key. Raises Not_found if the map is empty.

`val max_binding_opt : ('key, 'a) t -> ('key * 'a) option`

Return `Some (key, value)` for the `key, value` pair with the largest key, or `None` if the map is empty.

- since 3.3.0

`val pop_max_binding : ('key, 'a) t -> ('key * 'a) * ('key, 'a) t`

Returns the binding with the largest key along with the rest of the map.

`val enum : ('a, 'b) t -> ('a * 'b) BatEnum.t`

Creates an enumeration for this map, enumerating `(key, value)` pairs with the keys in increasing order.

`val backwards : ('a, 'b) t -> ('a * 'b) BatEnum.t`

Creates an enumeration for this map, enumerating `(key, value)` pairs with the keys in decreasing order.

`val keys : ('a, 'b) t -> 'a BatEnum.t`

Return an enumeration of all the keys of a map.

`val values : ('a, 'b) t -> 'b BatEnum.t`

Return an enumeration of all the values of a map.

`val of_enum : ('a * 'b) BatEnum.t -> ('a, 'b) t`

Creates a map from an enumeration.

`val for_all : ('a -> 'b -> bool) -> ('a, 'b) t -> bool`

Tests whether all `(key, value)` pairs satisfy a predicate function.

`val exists : ('a -> 'b -> bool) -> ('a, 'b) t -> bool`

Tests whether some `(key, value)` pair satisfies a predicate function.

`val partition : ('a -> 'b -> bool) -> ('a, 'b) t -> ('a, 'b) t * ('a, 'b) t`

`partition p m` returns a pair of maps `(m1, m2)`, where `m1` contains all the bindings of `s` that satisfy the predicate `p`, and `m2` is the map with all the bindings of `s` that do not satisfy `p`.

`val add_carry : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t * 'b option`

`add_carry k v m` adds the binding `(k, v)` to `m`, returning the new map and optionally the previous value bound to `k`.

`val modify : 'a -> ('b -> 'b) -> ('a, 'b) t -> ('a, 'b) t`

`modify k f m` replaces the previous binding for `k` with `f` applied to that value. If `k` is unbound in `m` or `Not_found` is raised during the search, `Not_found` is raised.

- since 1.2.0

- raises `Not_found`

  if `k` is unbound in `m` (or `f` raises `Not_found`)

`val modify_def : 'b -> 'a -> ('b -> 'b) -> ('a, 'b) t -> ('a, 'b) t`

`modify_def v0 k f m` replaces the previous binding for `k` with `f` applied to that value. If `k` is unbound in `m` or `Not_found` is raised during the search, `f v0` is inserted (as if the value found were `v0`).

- since 1.3.0

`val modify_opt : 'a -> ('b option -> 'b option) -> ('a, 'b) t -> ('a, 'b) t`

`modify_opt k f m` allow to modify the binding for `k` in `m` or absence thereof.

- since 2.1

`val extract : 'a -> ('a, 'b) t -> 'b * ('a, 'b) t`

`extract k m` removes the current binding of `k` from `m`, returning the value `k` was bound to and the updated `m`.

`val pop : ('a, 'b) t -> ('a * 'b) * ('a, 'b) t`

`pop m` returns a binding from `m` and `m` without that binding.

`val union : ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t`

`union m1 m2` merges two maps, using the comparison function of `m1`. In case of conflicted bindings, `m2`'s bindings override `m1`'s. Equivalent to `foldi add m2 m1`. The resulting map uses the comparison function of `m1`.

`val union_stdlib : ('key -> 'a -> 'a -> 'a option) -> ('key, 'a) t -> ('key, 'a) t -> ('key, 'a) t`

`union_stdlib f m1 m2` computes a map whose keys are a subset of the keys of `m1` and of `m2`. When the same binding is defined in both arguments, the function f is used to combine them. This function is similar to `merge`, except `f` is only called if a key is present in both `m1` and `m2`. If a key is present in either `m1` or `m2` but not in both, it (and the corresponding value) will be present in the resulting map.

This is the union method from the stdlib map, renamed for backwards compatibility.

- since 3.3.0

`val to_seq : ('key, 'a) t -> ('key * 'a) BatSeq.t`

Iterate on the whole map, in ascending order of keys.

- since 3.3.0

`val to_rev_seq : ('key, 'a) t -> ('key * 'a) BatSeq.t`

Iterate on the whole map, in descending order of keys.

- since 3.3.0

`val to_seq_from : 'key -> ('key, 'a) t -> ('key * 'a) BatSeq.t`

`to_seq_from k m` iterates on a subset of the bindings in `m`, namely those bindings greater or equal to `k`, in ascending order.

- since 3.3.0

`val add_seq : ('key * 'a) BatSeq.t -> ('key, 'a) t -> ('key, 'a) t`

add the given bindings to the map, in order.

- since 3.3.0

`val of_seq : ('key * 'a) BatSeq.t -> ('key, 'a) t`

build a map from the given bindings

- since 3.3.0

`val diff : ('a, 'b) t -> ('a, 'b) t -> ('a, 'b) t`

`diff m1 m2` removes all bindings of keys found in `m2` from `m1`, using the comparison function of `m1`. Equivalent to `foldi (fun k _v m -> remove k m) m2 m1`. The resulting map uses the comparison function of `m1`.

`val intersect : ('b -> 'c -> 'd) -> ('a, 'b) t -> ('a, 'c) t -> ('a, 'd) t`

`intersect merge_f m1 m2` returns a map with bindings only for keys bound in both `m1` and `m2`, and with `k` bound to `merge_f v1 v2`, where `v1` and `v2` are `k`'s bindings in `m1` and `m2`. The resulting map uses the comparison function of `m1`.

`val merge : ('key -> 'a option -> 'b option -> 'c option) -> ('key, 'a) t -> ('key, 'b) t -> ('key, 'c) t`

`merge f m1 m2` computes a map whose keys is a subset of keys of `m1` and of `m2`. The presence of each such binding, and the corresponding value, is determined with the function `f`. The resulting map uses the comparison function of `m1`.

`val compare : ('b -> 'b -> int) -> ('a, 'b) t -> ('a, 'b) t -> int`
`val equal : ('b -> 'b -> bool) -> ('a, 'b) t -> ('a, 'b) t -> bool`

Construct a comparison or equality function for maps based on a value comparison or equality function. Uses the key comparison function to compare keys

`module Exceptionless : sig ... end`

Exceptionless versions of functions

`module Infix : sig ... end`

Infix operators over a `BatPMap`

`val (-->) : ('a, 'b) t -> 'a -> 'b`

Map find and insert from Infix

`val (<--) : ('a, 'b) t -> ('a * 'b) -> ('a, 'b) t`
`val bindings : ('key, 'a) t -> ('key * 'a) list`

Return the list of all bindings of the given map. The returned list is sorted in increasing key order.

Added for compatibility with stdlib 3.12

## Boilerplate code

### Printing

`val print : ?first:string -> ?last:string -> ?sep:string -> ?kvsep:string -> ('a BatInnerIO.output -> 'b -> unit) -> ('a BatInnerIO.output -> 'c -> unit) -> 'a BatInnerIO.output -> ('b, 'c) t -> unit`
`include module type of struct include Exceptionless end`
`val find : 'a -> ('a, 'b) t -> 'b option`
`val choose : ('a, 'b) t -> ('a * 'b) option`
`val any : ('a, 'b) t -> ('a * 'b) option`
`module PMap : sig ... end`