This is documentation for the development version of Patricia Tree, the latest released version is v0.11.0.
Click here to redirect to the latest version.

Patricia Tree API - `MAP_WITH_VALUE`

The signature for maps with a single type for keys and values, a 'a map binds key to 'a value. This is slightly more generic than MAP, which just binds to 'a. It is used for maps that need to restrict their value type, namely Hash-consed maps and sets.

since v0.10.0

type key

The type of keys.

type 'a t

A map from key to values of type 'a value.

type 'a value

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.

since v0.10.0

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.

val unsigned_min_binding : 'a t -> key * 'a value

Returns the (key,value) pair where Key.to_int key is minimal (in the unsigned representation of integers); O(log n) complexity.

raises Not_found
if the map is empty.

val unsigned_max_binding : 'a t -> key * 'a value

Returns the (key,value) pair where Key.to_int key is maximal (in the unsigned representation of integers); O(log n) complexity.

raises Not_found
if the map is empty.

val singleton : key -> 'a value -> 'a t

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.

val is_singleton : 'a t -> (key * 'a value) option

is_singleton m is Some (k,v) iff m is singleton k v.

val find : key -> 'a t -> 'a value

Return an element in the map, or raise Not_found, O(log(n)) complexity.

val find_opt : key -> 'a t -> 'a value option

Return an element in the map, or None, O(log(n)) complexity.

val mem : key -> 'a t -> bool

mem key map returns true if and only if key is bound in map. O(log(n)) complexity.

val remove : key -> 'a t -> 'a t

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

val pop_unsigned_minimum : 'a t -> (key * 'a value * 'a t) option

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.

val pop_unsigned_maximum : 'a t -> (key * 'a value * 'a t) option

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.

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

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.

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

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.

val add : key -> 'a value -> 'a t -> 'a t

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

val split : key -> 'a t -> 'a t * 'a value option * 'a t

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.

val iter : (key -> 'a value -> unit) -> 'a t -> unit

Iterate on each (key,value) pair of the map, in increasing unsigned order of KEY.to_int.

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

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.

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

Returns the submap containing only the key->value pairs satisfying the given predicate. f is called in increasing unsigned order of KEY.to_int.

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

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

val map : ('a value -> 'a value) -> 'a t -> 'a t

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.

val map_no_share : ('a value -> 'b value) -> 'a t -> 'b t

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.

val mapi : (key -> 'a value -> 'a value) -> 'a t -> 'a t

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.

val mapi_no_share : (key -> 'a value -> 'b value) -> 'a t -> 'b t

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.

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

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.

val filter_map_no_share : (key -> 'a value -> 'b value option) -> 'a t -> 'b t

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 an explaination of their main differences with the equivalent functions in Stdlib's Map.

Comparing two maps

Equality, inclusion and test for disjoint maps.

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

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.

val reflexive_equal : ('a value -> 'a value -> bool) -> 'a t -> 'a t -> bool

reflexive_equal f m1 m2 is true if both maps are equal, using f to compare values. f is assumed to be reflexive (i.e. f v v = true).

since v0.11.0

val reflexive_compare : ('a value -> 'a value -> int) -> 'a t -> 'a t -> int

reflexive_compare f m1 m2 is an order on both maps. m1 and m2 are equal (return 0) if they have the same domain and for all bindings (k,v) in m1, (k,v') in m2, we have f v v' = 0.

m1 is considered striclty smaller than m2 (return a negative integer) when the first difference (lowest key in the unsigned order of KEY.to_int) is either a shared binding (k,v) in m1, (k,v') in m2 with f v v' < 0, or a binding that only occurs in m2.

Assumes that f v v = 0.

since v0.11.0

val disjoint : 'a t -> 'a t -> bool

disjoint a b is true if and only if a and b have disjoint domains.

val min_binding_inter : 'a t -> 'b t -> (key * 'a value * 'b value) option

min_binding_inter m1 m2 is the minimal binding of the intersection. I.E. the (k,v1,v2) such that (k,v1) is in m1, (k,v2) is in m2, and k is minimal using the unsigned order on keys.

Returns None if and only if the intersection is empty.

It is rougthly equivalent to calling unsigned_min_binding on nonindempotent_inter_no_share f m1 m2, but can be faster.

since v0.11.0

val max_binding_inter : 'a t -> 'b t -> (key * 'a value * 'b value) option

max_binding_inter m1 m2 is the same as min_binding_inter, but returns the maximum key instead of the minimum.

since v0.11.0

Combining two maps

Union, intersection, difference... See the same section in BASE_MAP for a table showcasing the differences between them.

val idempotent_union : 
  (key -> 'a value -> 'a value -> 'a value) ->
  'a t ->
  'a t ->
  'a t

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.

val idempotent_inter : 
  (key -> 'a value -> 'a value -> 'a value) ->
  'a t ->
  'a t ->
  'a t

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.

val nonidempotent_inter_no_share : 
  (key -> 'a value -> 'b value -> 'c value) ->
  'a t ->
  'b t ->
  'c t

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.

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

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.

since v0.11.0

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

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.

since v0.11.0

module WithForeign (Map2 : NODE_WITH_FIND 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

val to_seq : 'a t -> (key * 'a value) Stdlib.Seq.t

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

val to_rev_seq : 'a t -> (key * 'a value) Stdlib.Seq.t

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

val add_seq : (key * 'a value) Stdlib.Seq.t -> 'a t -> 'a t

add_seq s m adds all bindings of the sequence s to m in order.

val of_seq : (key * 'a value) Stdlib.Seq.t -> 'a t

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

val of_list : (key * 'a value) list -> 'a t

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

val to_list : 'a t -> (key * 'a value) list

to_list m returns the bindings of m as a list, in increasing unsigned order of KEY.to_int

Patricia Tree API - MAP_WITH_VALUE