This is documentation for the **development version** of Patricia Tree,
the latest released version is
**v0.10.0**.

Click here
to redirect to the latest version.

#
Patricia Tree API - `MakeCustomMap`

Create a homogeneous map with a custom `NODE`

. Also allows customizing the map values

## Parameters

## Signature

`type key = Key.t`

The type of keys.

`type 'm t = 'm Node.t`

A map from `key`

to values of type `'a value`

.

`type 'm value = 'm Value.t`

Type for values, this is a divergence from Stdlib's `Map`

, but becomes equivalent to it when using `MAP`

, which is just `MAP_WITH_VALUE with type 'a value = 'a`

. On the other hand, it allows defining maps with fixed values, which is useful for hash-consing.

```
module BaseMap :
HETEROGENEOUS_MAP
with type 'a t = 'a t
and type _ key = key
and type ('a, 'b) value = ('a, 'b value) snd
```

Underlying basemap, for cross map/set operations

## Basic functions

`val empty : 'a t`

The empty map.

`val is_empty : 'a t -> bool`

Test if a map is empty; O(1) complexity.

Returns the `(key,value)`

pair where `Key.to_int key`

is minimal (in the unsigned representation of integers); O(log n) complexity.

Returns the `(key,value)`

pair where `Key.to_int key`

is maximal (in the unsigned representation of integers); O(log n) complexity.

`singleton key value`

creates a map with a single binding, O(1) complexity.

`val cardinal : 'a t -> int`

The size of the map. O(n) complexity.

`is_singleton m`

is `Some (k,v)`

iff `m`

is `singleton k v`

.

Return an element in the map, or raise `Not_found`

, O(log(n)) complexity.

Return an element in the map, or `None`

, O(log(n)) complexity.

`mem key map`

returns `true`

if and only if `key`

is bound in `map`

. O(log(n)) complexity.

Returns a map with the element removed, O(log(n)) complexity. Returns a physically equal map if the element is absent.

`pop_unsigned_minimum m`

returns `None`

if `is_empty m`

, or `Some(key,value,m')`

where `(key,value) = unsigned_min_binding m`

and `m' = remove m key`

. O(log(n)) complexity. Uses the unsigned order on `KEY.to_int`

.

`pop_unsigned_maximum m`

returns `None`

if `is_empty m`

, or `Some(key,value,m')`

where `(key,value) = unsigned_max_binding m`

and `m' = remove m key`

. O(log(n)) complexity. Uses the unsigned order on `KEY.to_int`

.

`insert key f map`

modifies or insert an element of the map; `f`

takes `None`

if the value was not previously bound, and `Some old`

where `old`

is the previously bound value otherwise. The function preserves physical equality when possible. O(log(n)) complexity. Preserves physical equality if the new value is physically equal to the old.

`update key f map`

modifies, insert, or remove an element from the map; `f`

takes `None`

if the value was not previously bound, and `Some old`

where `old`

is the previously bound value otherwise. The function preserves physical equality when possible. It returns None if the element should be removed O(log(n)) complexity. Preserves physical equality if the new value is physically equal to the old.

Unconditionally adds a value in the map (independently from whether the old value existed). O(log(n)) complexity. Preserves physical equality if the new value is physically equal to the old.

## Iterators

`split key map`

splits the map into:

- submap of
`map`

whose keys are smaller than`key`

- value associated to
`key`

(if present) - submap of
`map`

whose keys are bigger than`key`

Uses the unsigned order on `KEY.to_int`

.

Iterate on each `(key,value)`

pair of the map, in increasing unsigned order of `KEY.to_int`

.

Fold on each `(key,value)`

pair of the map, in increasing unsigned order of `KEY.to_int`

.

```
val fold_on_nonequal_inter :
(key -> 'a value -> 'a value -> 'acc -> 'acc) ->
'a t ->
'a t ->
'acc ->
'acc
```

`fold_on_nonequal_inter f m1 m2 acc`

returns `f key_n value1_n value2n (... (f key_1 value1_1 value2_1 acc))`

where `(key_1, value1_1, value2_1) ... (key_n, value1_n, value2_n)`

are the bindings that exist in both maps (`m1 âˆ© m2`

) whose values are physically different. Calls to `f`

are performed in the unsigned order of `KEY.to_int`

.

```
val fold_on_nonequal_union :
(key -> 'a value option -> 'a value option -> 'acc -> 'acc) ->
'a t ->
'a t ->
'acc ->
'acc
```

`fold_on_nonequal_union f m1 m2 acc`

returns `f key_n value1_n value2n (... (f key_1 value1_1 value2_1 acc))`

where `(key_1, value1_1, value2_1) ... (key_n, value1_n, value2_n)`

are the bindings that exists in either map (`m1 âˆª m2`

) whose values are physically different. Calls to `f.f`

are performed in the unsigned order of `KEY.to_int`

.

Returns the submap containing only the key->value pairs satisfying the given predicate. `f`

is called in increasing unsigned order of `KEY.to_int`

.

Returns true if the predicate holds on all map bindings. Short-circuiting. `f`

is called in increasing unsigned order of `KEY.to_int`

.

In the following, the *no_share function allows taking arguments of different types (but cannot share subtrees of the map), while the default functions attempt to preserve and benefit from sharing the subtrees (using physical equality to detect sharing).

`map f m`

returns a map where the `value`

bound to each `key`

is replaced by `f value`

. The subtrees for which the returned value is physically the same (i.e. `f key value == value`

for all the keys in the subtree) are guaranteed to be physically equal to the original subtree. O(n) complexity. `f`

is called in increasing unsigned order of `KEY.to_int`

.

`map_no_share f m`

returns a map where the `value`

bound to each `key`

is replaced by `f value`

. O(n) complexity. `f`

is called in increasing unsigned order of `KEY.to_int`

.

`mapi f m`

returns a map where the `value`

bound to each `key`

is replaced by `f key value`

. The subtrees for which the returned value is physically the same (i.e. `f key value == value`

for all the keys in the subtree) are guaranteed to be physically equal to the original subtree. O(n) complexity. `f`

is called in increasing unsigned order of `KEY.to_int`

.

`mapi_no_share f m`

returns a map where the `value`

bound to each `key`

is replaced by `f key value`

. O(n) complexity. `f`

is called in increasing unsigned order of `KEY.to_int`

.

`filter_map m f`

returns a map where the `value`

bound to each `key`

is removed (if `f key value`

returns `None`

), or is replaced by `v`

((if `f key value`

returns `Some v`

). The subtrees for which the returned value is physically the same (i.e. `f key value = Some v`

with `value == v`

for all the keys in the subtree) are guaranteed to be physically equal to the original subtree. O(n) complexity. `f`

is called in increasing unsigned order of `KEY.to_int`

.

`filter_map m f`

returns a map where the `value`

bound to each `key`

is removed (if `f key value`

returns `None`

), or is replaced by `v`

((if `f key value`

returns `Some v`

). O(n) complexity. `f`

is called in increasing unsigned order of `KEY.to_int`

.

## Operations on pairs of maps

See the same section for `BASE_MAP`

for an overview of what these functions do, and a quick overview of the differences between them.

### Comparing two maps

Equality, inclusion and test for disjoint maps.

`reflexive_same_domain_for_all2 f map1 map2`

returns `true`

if `map1`

and `map2`

have the same keys, and `f key value1 value2`

returns true for each mapping pair of keys. We assume that `f`

is reflexive (i.e. `f key value value`

returns `true`

) to avoid visiting physically equal subtrees of `map1`

and `map2`

. The complexity is O(log(n)+Delta) where Delta is the number of different keys between `map1`

and `map2`

.

```
val nonreflexive_same_domain_for_all2 :
(key -> 'a value -> 'b value -> bool) ->
'a t ->
'b t ->
bool
```

`nonreflexive_same_domain_for_all2 f map1 map2`

returns true if map1 and map2 have the same keys, and `f key value1 value2`

returns true for each mapping pair of keys. The complexity is O(min(|map1|,|map2|)).

```
val reflexive_subset_domain_for_all2 :
(key -> 'a value -> 'a value -> bool) ->
'a t ->
'a t ->
bool
```

`reflexive_subset_domain_for_all2 f map1 map2`

returns true if all the keys of `map1`

also are in `map2`

, and `f key (find map1 key) (find map2 key)`

returns `true`

when both keys are present in the map. We assume that `f`

is reflexive (i.e. `f key value value`

returns true) to avoid visiting physically equal subtrees of `map1`

and `map2`

. The complexity is O(log(n)*Delta) where Delta is the number of different keys between `map1`

and `map2`

.

`disjoint a b`

is `true`

if and only if `a`

and `b`

have disjoint domains.

### Combining two maps

Union, intersection, difference... See the same section in `BASE_MAP`

for a table showcasing the differences between them.

`idempotent_union f map1 map2`

returns a map whose keys is the union of the keys of `map1`

and `map2`

. `f`

is used to combine the values a key is mapped in both maps. We assume that `f`

is idempotent (i.e. `f key value value == value`

) to avoid visiting physically equal subtrees of `map1`

and `map2`

, and also to preserve physical equality of the subtreess in that case. The complexity is O(log(n)*Delta) where Delta is the number of different keys between `map1`

and `map2`

. `f`

is called in increasing unsigned order of `KEY.to_int`

. `f`

is never called on physically equal values.

`idempotent_inter f map1 map2`

returns a map whose keys is the intersection of the keys of `map1`

and `map2`

. `f`

is used to combine the values a key is mapped in both maps. We assume that `f`

is idempotent (i.e. `f key value value == value`

) to avoid visiting physically equal subtrees of `map1`

and `map2`

, and also to preserve physical equality of the subtrees in that case. The complexity is O(log(n)*Delta) where Delta is the number of different keys between `map1`

and `map2`

. `f`

is called in increasing unsigned order of `KEY.to_int`

!. `f`

is never called on physically equal values.

`nonidempotent_inter_no_share f map1 map2`

returns a map whose keys is the intersection of the keys of `map1`

and `map2`

. `f`

is used to combine the values a key is mapped in both maps. `f`

does not need to be idempotent, which imply that we have to visit physically equal subtrees of `map1`

and `map2`

. The complexity is O(log(n)*min(|map1|,|map2|)). `f`

is called in increasing unsigned order of `KEY.to_int`

. `f`

is called on every shared binding.

```
val idempotent_inter_filter :
(key -> 'a value -> 'a value -> 'a value option) ->
'a t ->
'a t ->
'a t
```

`idempotent_inter_filter f m1 m2`

is like `idempotent_inter`

(assuming idempotence, using and preserving physically equal subtrees), but it also removes the key->value bindings for which `f`

returns `None`

.

```
val slow_merge :
(key -> 'a value option -> 'b value option -> 'c value option) ->
'a t ->
'b t ->
'c t
```

`slow_merge f m1 m2`

returns a map whose keys are a subset of the keys of `m1`

and `m2`

. The `f`

function is used to combine keys, similarly to the `Map.merge`

function. This funcion has to traverse all the bindings in `m1`

and `m2`

; its complexity is O(|m1|+|m2|). Use one of faster functions above if you can.

`symmetric_difference f map1 map2`

returns a map comprising of the bindings of `map1`

that aren't in `map2`

, and the bindings of `map2`

that aren't in `map1`

.

Bindings that are both in `map1`

and `map2`

, but with non-physically equal values are passed to `f`

. If `f`

returns `Some v`

then `v`

is used as the new value, otherwise the binding is dropped.

**Assumes** `f`

is none on equal values (i.e. `f key value value == None`

) `f`

is called in increasing unsigned order of `KEY.to_int`

. `f`

is never called on physically equal values.

Complexity is `O(log n + d)`

where `n`

is the size of the maps, and `d`

the size of the difference.

`difference f map1 map2`

returns a map comprising of the bindings of `map1`

which aren't in `map2`

. For keys present in both maps but with different values, `f`

is called. If it returns `Some v`

, then binding `k,v`

is kept, else `k`

is dropped.

**Assumes** `f`

is none on equal values (i.e. `f key value value == None`

) `f`

is called in the unsigned order of `KEY.to_int`

.

`module WithForeign (Map2 : BASE_MAP with type _ key = key) : sig ... end`

Combination with other kinds of maps. `Map2`

must use the same `KEY.to_int`

function.

```
val pretty :
?pp_sep:(Stdlib.Format.formatter -> unit -> unit) ->
(Stdlib.Format.formatter -> key -> 'a value -> unit) ->
Stdlib.Format.formatter ->
'a t ->
unit
```

Pretty prints all bindings of the map. `pp_sep`

is called once between each binding pair and defaults to `Format.pp_print_cut`

.

## Conversion functions

`to_seq m`

iterates the whole map, in increasing unsigned order of `KEY.to_int`

`to_rev_seq m`

iterates the whole map, in decreasing unsigned order of `KEY.to_int`

`add_seq s m`

adds all bindings of the sequence `s`

to `m`

in order.

`of_seq s`

creates a new map from the bindings of `s`

. If a key is bound multiple times in `s`

, the latest binding is kept

`of_list l`

creates a new map from the bindings of `l`

. If a key is bound multiple times in `l`

, the latest binding is kept

`to_list m`

returns the bindings of `m`

as a list, in increasing unsigned order of `KEY.to_int`