`Belt_Map`

A *immutable* sorted map module which allows customize *compare* behavior.

The implementation uses balanced binary trees, and therefore searching and insertion take time logarithmic in the size of the map.

For more info on this module's usage of identity, `make` and others, please see the top level documentation of Belt, **A special encoding for collection safety**.

Example usage:

```
module PairComparator = Belt.Id.MakeComparable(struct
type t = int * int
let cmp (a0, a1) (b0, b1) =
match Pervasives.compare a0 b0 with
| 0 -> Pervasives.compare a1 b1
| c -> c
end)
let myMap = Belt.Map.make ~id:(module PairComparator)
let myMap2 = Belt.Map.set myMap (1, 2) "myValue"
```

The API documentation below will assume a predeclared comparator module for integers, IntCmp

`module Int = Belt_MapInt;`

Specalized when key type is `int`

, more efficient than the generic type, its compare behavior is fixed using the built-in comparison

`module String = Belt_MapString;`

specalized when key type is `string`

, more efficient than the generic type, its compare behavior is fixed using the built-in comparison

`module Dict = Belt_MapDict;`

This module seprate identity from data, it is a bit more verboe but slightly more efficient due to the fact that there is no need to pack identity and data back after each operation

`('key, 'identity) t`

`'key`

is the field type

`'value`

is the element type

`'identity`

the identity of the collection

`type id('key, 'id) = Belt_Id.comparable('key, 'id);`

The identity needed for making an empty map

`make ~id`

creates a new map by taking in the comparator

`let m = Belt.Map.make ~id:(module IntCmp)`

`let isEmpty: t(_, _, _) => bool;`

`isEmpty m`

checks whether a map m is empty

`isEmpty (fromArray [|1,"1"|] ~id:(module IntCmp)) = false`

`let has: t('k, 'v, 'id) => 'k => bool;`

`has m k`

checks whether m has the key k

`has (fromArray [|1,"1"|] ~id:(module IntCmp)) 1 = true`

```
let cmpU:
t('k, 'v, 'id) =>
t('k, 'v, 'id) =>
Js.Fn.arity2(('v => 'v => int)) =>
int;
```

`cmp m0 m1 vcmp`

Total ordering of map given total ordering of value function.

It will compare size first and each element following the order one by one.

```
let eqU:
t('k, 'v, 'id) =>
t('k, 'v, 'id) =>
Js.Fn.arity2(('v => 'v => bool)) =>
bool;
```

`eq m1 m2 veq`

tests whether the maps `m1`

and `m2`

are equal, that is, contain equal keys and associate them with equal data. `veq`

is the equality predicate used to compare the data associated with the keys.

```
let findFirstByU:
t('k, 'v, 'id) =>
Js.Fn.arity2(('k => 'v => bool)) =>
option(('k, 'v));
```

`let findFirstBy: t('k, 'v, 'id) => ('k => 'v => bool) => option(('k, 'v));`

`findFirstBy m p`

uses funcion `f`

to find the first key value pair to match predicate `p`

.

```
let s0 = fromArray ~id:(module IntCmp) [|4,"4";1,"1";2,"2,"3""|];;
findFirstBy s0 (fun k v -> k = 4 ) = option (4, "4");;
```

`let forEachU: t('k, 'v, 'id) => Js.Fn.arity2(('k => 'v => unit)) => unit;`

`let forEach: t('k, 'v, 'id) => ('k => 'v => unit) => unit;`

`forEach m f`

applies `f`

to all bindings in map `m`

. `f`

receives the 'k as first argument, and the associated value as second argument. The bindings are passed to `f`

in increasing order with respect to the ordering over the type of the keys.

```
let s0 = fromArray ~id:(module IntCmp) [|4,"4";1,"1";2,"2,"3""|];;
let acc = ref [] ;;
forEach s0 (fun k v -> acc := (k,v) :: !acc);;
!acc = [4,"4"; 3,"3"; 2,"2"; 1,"1"]
```

```
let reduceU:
t('k, 'v, 'id) =>
'acc =>
Js.Fn.arity3(('acc => 'k => 'v => 'acc)) =>
'acc;
```

`let reduce: t('k, 'v, 'id) => 'acc => ('acc => 'k => 'v => 'acc) => 'acc;`

`reduce m a f`

computes `(f kN dN ... (f k1 d1 a)...)`

, where `k1 ... kN`

are the keys of all bindings in `m`

(in increasing order), and `d1 ... dN`

are the associated data.

```
let s0 = fromArray ~id:(module IntCmp) [|4,"4";1,"1";2,"2,"3""|];;
reduce s0 [] (fun acc k v -> (k,v) acc ) = [4,"4";3,"3";2,"2";1,"1"];;
```

`let everyU: t('k, 'v, 'id) => Js.Fn.arity2(('k => 'v => bool)) => bool;`

`let every: t('k, 'v, 'id) => ('k => 'v => bool) => bool;`

`every m p`

checks if all the bindings of the map satisfy the predicate `p`

. Order unspecified

`let someU: t('k, 'v, 'id) => Js.Fn.arity2(('k => 'v => bool)) => bool;`

`let some: t('k, 'v, 'id) => ('k => 'v => bool) => bool;`

`some m p`

checks if at least one binding of the map satisfy the predicate `p`

. Order unspecified

`let size: t('k, 'v, 'id) => int;`

`size s`

`size (fromArray [2,"2"; 2,"1"; 3,"3"] ~id:(module IntCmp)) = 2 ;;`

`let toArray: t('k, 'v, 'id) => array(('k, 'v));`

`toArray s`

`toArray (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp)) = [1,"1";2,"2";3,"3"]`

`fromArray kvs ~id`

`toArray (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp)) = [1,"1";2,"2";3,"3"]`

`let keysToArray: t('k, 'v, 'id) => array('k);`

`keysToArray s`

```
keysToArray (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp)) =
[|1;2;3|];;
```

`let valuesToArray: t('k, 'v, 'id) => array('v);`

`valuesToArray s`

```
valuesToArray (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp)) =
[|"1";"2";"3"|];;
```

`let minKey: t('k, _, _) => option('k);`

`minKey s`

`let minKeyUndefined: t('k, _, _) => Js.undefined('k);`

**See** `minKey`

`let maxKey: t('k, _, _) => option('k);`

`maxKey s`

`let maxKeyUndefined: t('k, _, _) => Js.undefined('k);`

**See** `maxKey`

`let minimum: t('k, 'v, _) => option(('k, 'v));`

`minimum s`

`let minUndefined: t('k, 'v, _) => Js.undefined(('k, 'v));`

**See** `minimum`

`let maximum: t('k, 'v, _) => option(('k, 'v));`

`maximum s`

`let maxUndefined: t('k, 'v, _) => Js.undefined(('k, 'v));`

**See** `maximum`

`let get: t('k, 'v, 'id) => 'k => option('v);`

`get s k`

```
get (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp)) 2 =
Some "2";;
get (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp)) 2 =
None;;
```

`let getUndefined: t('k, 'v, 'id) => 'k => Js.undefined('v);`

**See** `get`

`remove m x`

when `x`

is not in `m`

, `m`

is returned reference unchanged.

```
let s0 = (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp));;
let s1 = remove s0 1;;
let s2 = remove s1 1;;
s1 == s2 ;;
keysToArray s1 = [|2;3|];;
```

`removeMany s xs`

Removing each of `xs`

to `s`

, note unlike `remove`

, the reference of return value might be changed even if none in `xs`

exists `s`

`set m x y `

returns a map containing the same bindings as `m`

, with a new binding of `x`

to `y`

. If `x`

was already bound in `m`

, its previous binding disappears.

```
let s0 = (fromArray [2,"2"; 1,"1"; 3,"3"] ~id:(module IntCmp));;
let s1 = set s0 2 "3";;
valuesToArray s1 = ["1";"3";"3"];;
```

```
let updateU:
t('k, 'v, 'id) =>
'k =>
Js.Fn.arity1((option('v) => option('v))) =>
t('k, 'v, 'id);
```

`update m x f`

returns a map containing the same bindings as `m`

, except for the binding of `x`

. Depending on the value of `y`

where `y`

is `f (get x m)`

, the binding of `x`

is added, removed or updated. If `y`

is `None`

, the binding is removed if it exists; otherwise, if `y`

is `Some z`

then `x`

is associated to `z`

in the resulting map.

`mergeMany s xs`

Adding each of `xs`

to `s`

, note unlike `add`

, the reference of return value might be changed even if all values in `xs`

exist `s`

```
let mergeU:
t('k, 'v, 'id) =>
t('k, 'v2, 'id) =>
Js.Fn.arity3(('k => option('v) => option('v2) => option('v3))) =>
t('k, 'v3, 'id);
```

```
let merge:
t('k, 'v, 'id) =>
t('k, 'v2, 'id) =>
('k => option('v) => option('v2) => option('v3)) =>
t('k, 'v3, 'id);
```

`merge m1 m2 f`

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`

.

```
let keepU:
t('k, 'v, 'id) =>
Js.Fn.arity2(('k => 'v => bool)) =>
t('k, 'v, 'id);
```

`keep m p`

returns the map with all the bindings in `m`

that satisfy predicate `p`

.

```
let partitionU:
t('k, 'v, 'id) =>
Js.Fn.arity2(('k => 'v => bool)) =>
(t('k, 'v, 'id), t('k, 'v, 'id));
```

`partition m p`

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`

.

`split x m`

returns a tuple `(l r), data`

, where `l`

is the map with all the bindings of `m`

whose 'k is strictly less than `x`

; `r`

is the map with all the bindings of `m`

whose 'k is strictly greater than `x`

; `data`

is `None`

if `m`

contains no binding for `x`

, or `Some v`

if `m`

binds `v`

to `x`

.

`let mapU: t('k, 'v, 'id) => Js.Fn.arity1(('v => 'v2)) => t('k, 'v2, 'id);`

`map m f`

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 bindings are passed to `f`

in increasing order with respect to the ordering over the type of the keys.

```
let mapWithKeyU:
t('k, 'v, 'id) =>
Js.Fn.arity2(('k => 'v => 'v2)) =>
t('k, 'v2, 'id);
```

`mapWithKey m f`

The same as `map`

except that `f`

is supplied with one more argument: the key

`let getData: t('k, 'v, 'id) => Belt_MapDict.t('k, 'v, 'id);`

`getData s0`

**Advanced usage only**

```
let packIdData:
id:id('k, 'id) =>
data:Belt_MapDict.t('k, 'v, 'id) =>
t('k, 'v, 'id);
```

`packIdData ~id ~data`

**Advanced usage only**