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  MakeHashconsedHeterogeneousMap
Hashconsed version of HETEROGENEOUS_MAP
. See Hashconsed maps and sets for the differences between hashconsed and non hashconsed maps.
This is a generative functor, as calling it creates a new hashtable to store the created nodes, and a reference to store the next unallocated identifier. Maps/sets from different hashconsing functors (even if these functors have the same arguments) will have different (incompatible) numbering systems and be stored in different hashtables (thus they will never be physically equal).
Parameters
module Key : HETEROGENEOUS_KEY
module Value : HETEROGENEOUS_HASHED_VALUE
Signature
include HETEROGENEOUS_MAP
with type 'a key = 'a Key.t
and type ('k, 'm) value = ('k, 'm) Value.t
include BASE_MAP
with type 'a key = 'a Key.t
with type ('k, 'm) value = ('k, 'm) Value.t
include NODE
with type 'a key = 'a Key.t
with type ('k, 'm) value = ('k, 'm) Value.t
Types
type 'a key = 'a Key.t
The type of keys.
type ('k, 'm) value = ('k, 'm) Value.t
The type of value, which depends on the type of the key and the type of the map.
Constructors: build values
val empty : 'map t
The empty map
A singleton leaf, similar to BASE_MAP.singleton
A branch node. This shouldn't be called externally unless you know what you're doing! Doing so could easily break the data structure's invariants.
When called, it assumes that:
 Neither
tree0
nortree1
should be empty. branching_bit
should have a single bit setprefix
should be normalized (bits belowbranching_bit
set to zero) All elements of
tree0
should have theirto_int
start byprefix
followed by 0 at positionbranching_bit
).  All elements of
tree1
should have theirto_int
start byprefix
followed by 0 at positionbranching_bit
).
Destructors: access the value
type 'map view = private
 Empty : 'map view
(*Can happen only at the toplevel: there is no empty interior node.
*) Branch : {
} > 'map view
(*Same constraints as
branch
:branching_bit
contains only one bit set; the corresponding mask is (branching_bit  1).prefix
is normalized: the bits below thebranching_bit
are set to zero (i.e.prefix & (branching_bit  1) = 0
). All elements of
tree0
should have theirto_int
start byprefix
followed by 0 at positionbranching_bit
).  All elements of
tree1
should have theirto_int
start byprefix
followed by 0 at positionbranching_bit
).
 Leaf : {
} > 'map view
(*A key > value mapping.
*)
This makes the map nodes accessible to the pattern matching algorithm; this corresponds 1:1 to the SimpleNode
implementation. This just needs to be copyandpasted for every node type.
val is_empty : 'map t > bool
Check if the map is empty. Should be constant time.
Existential wrapper for the 'a
parameter in a 'a key
, ('a,'map) value
pair
Basic functions
val unsigned_min_binding : 'a t > 'a key_value_pair
unsigned_min_binding m
is minimal binding KeyValue(k,v)
of the map, using the unsigned order on KEY.to_int
.
val unsigned_max_binding : 'a t > 'a key_value_pair
unsigned_max_binding m
is maximal binding KeyValue(k,v)
of the map, using the unsigned order on KEY.to_int
.
val cardinal : 'a t > int
The size of the map, O(n) complexity
val is_singleton : 'a t > 'a key_value_pair option
is_singleton m
returns Some(KeyValue(k,v))
if and only if m
contains a unique binding k>v
.
find key map
returns the value associated with key
in map
if present.
Same as find
, but returns None
for Not_found
mem key map
returns true
iff 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.
val pop_unsigned_minimum : 'map t > ('map key_value_pair * 'map 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
. Uses the unsigned order on KEY.to_int
. O(log(n)) complexity.
val pop_unsigned_maximum : 'map t > ('map key_value_pair * 'map 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
. Uses the unsigned order on KEY.to_int
. O(log(n)) complexity.
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 thankey
 value associated to
key
(if present)  submap of
map
whose keys are bigger thankey
Where the order is given by the unsigned order on KEY.to_int
.
iter f m
calls f.f
on all bindings of m
, in the unsigned order on KEY.to_int
fold f m acc
returns f.f key_n value_n (... (f.f key_1 value_1 acc))
where (key_1, value_1) ... (key_n, value_n)
are the bindings of m
, in the unsigned order on KEY.to_int
.
fold_on_nonequal_inter f m1 m2 acc
returns f.f key_n value1_n value2n (... (f.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.f
are performed in the unsigned order of KEY.to_int
.
val fold_on_nonequal_union :
('acc, 'map) polyfold2_union >
'map t >
'map t >
'acc >
'acc
fold_on_nonequal_union f m1 m2 acc
returns f.f key_n value1_n value2n (... (f.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 : 'map polypredicate > 'map t > 'map t
filter f m
returns the submap of m
containing the bindings k>v
such that f.f k v = true
. f.f
is called in the unsigned order of KEY.to_int
val for_all : 'map polypredicate > 'map t > bool
for_all f m
checks that f
holds on all bindings of m
. Shortcircuiting.
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
and map_no_share f m
replace all bindings (k,v)
by (k, f.f v)
. Bindings are examined in the unsigned order of KEY.to_int
.
mapi f m
and mapi_no_share f m
replace all bindings (k,v)
by (k, f.f k v)
. Bindings are examined in the unsigned order of KEY.to_int
.
val filter_map : ('map, 'map) polyfilter_map > 'map t > 'map t
filter_map m f
and filter_map_no_share m f
remove the bindings (k,v)
for which f.f k v
is None
, and replaces the bindings (k,v)
for which f.f k v
is Some v'
by (k,v')
. Bindings are examined in the unsigned order of KEY.to_int
.
val pretty :
?pp_sep:(Stdlib.Format.formatter > unit > unit) >
'map polypretty >
Stdlib.Format.formatter >
'map t >
unit
Prettyprints a map using the given formatter. pp_sep
is called once between each binding, it defaults to Format.pp_print_cut
. Bindings are printed in the unsigned order of KEY.to_int
Functions on pairs of maps
This section regroups functions that act on pairs of maps.
Due to restrictions with higherorder polymorphism, we need to wrap the function f
in a record, which has a single field f
. These is what the polyXXX
types are for.
These functions are where Patricia trees offer substantial speedup compared to Stdlib's Maps:
 We can often avoid exploring physically equal subtrees (for equality tests, inclusion tests, union, intersection, difference). This yields important performance gains when combining maps that derive from a common ancestor or when using Hashconsed maps and sets maps which have a lot of elements in common.
 We can also avoid visiting a subtree when merging with
Empty
(for union, intersection and difference).
To do so safely, we have specialized versions of these functions that assume properties of the function parameter (reflexive relation, idempotent operation, etc.)
When we cannot enjoy these properties, our functions explicitly say so (with a nonreflexive or nonidempotent prefix). The names are a bit long, but having these names avoids using an ineffective code by default, by forcing to know and choose between the fast and slow version.
In general, the fast versions of these function will be on O(log n + d)
where n
is the size of the maps being joined and d
the size of their difference (number of keys bound in both maps to nonphysically equal values). The slow version is O(n)
.
Comparing two maps
Functions for equality, inclusion, and test for disjointness.
val reflexive_same_domain_for_all2 :
('map, 'map) polysame_domain_for_all2 >
'map t >
'map t >
bool
reflexive_same_domain_for_all2 f m1 m2
is true if and only if
m1
andm2
have the same domain (set of keys) for all bindings
(k, v1)
inm1
and(k, v2)
inm2
,f.f k v1 v2
holds
Assumes f.f
is reflexive, i.e. f.f k v v = true
to skip calls to equal subtrees. Calls f.f
in ascending unsigned order of KEY.to_int
. Exits early if the domains mismatch or if f.f
returns false.
It is useful to implement equality on maps:
# let equal m1 m2 = MyMap.reflexive_same_domain_for_all2
{ f = fun _ v1 v2 > MyValue.equal v1 v2}
m1 m2;;
val equal : 'a MyMap.t > 'a MyMap.t > bool = <fun>
val nonreflexive_same_domain_for_all2 :
('map1, 'map2) polysame_domain_for_all2 >
'map1 t >
'map2 t >
bool
nonreflexive_same_domain_for_all2 f m1 m2
is the same as reflexive_same_domain_for_all2
, but doesn't assume f.f
is reflexive. It thus calls f.f
on every binding, in ascending unsigned order of KEY.to_int
. Exits early if the domains mismatch or if f.f
returns false.
val reflexive_subset_domain_for_all2 :
('map, 'map) polysame_domain_for_all2 >
'map t >
'map t >
bool
reflexive_subset_domain_for_all2 f m1 m2
is true if and only if
m1
's domain is a subset ofm2
's. (all keys defined inm1
are also defined inm2
) for all bindings
(k, v1)
inm1
and(k, v2)
inm2
,f.f k v1 v2
holds
Assumes f.f
is reflexive, i.e. f.f k v v = true
to skip calls to equal subtrees. Calls f.f
in ascending unsigned order of KEY.to_int
. Exits early if the domains mismatch.
Combining two maps
We provide many functions that operate on pairs of maps for computing intersection, union, difference... Here is a short summary of what each of one returns when applied to two maps m1
and m2
. Here y
is physically the same value in m1
and m2
.
Keys 








 



 



 






 

 

 


 



[1]: Here f
returns an optional value, returning None
removes the binding.
[2]: Here the function f
actually takes option
as arguments, omitted for brevity. _
is None
.
idempotent_union f map1 map2
returns a map whose keys is the union of the keys of map1
and map2
. f.f
is used to combine the values of keys mapped in both maps.
Assumes f.f
idempotent (i.e. f key value value == value
) f.f
is called in the unsigned order of KEY.to_int
. f.f
is never called on physically equal values. Preserves physical equality as much as possible. Complexity is O(log(n)*Delta) where Delta is the number of different keys between map1
and map2
.
idempotent_inter f map1 map2
returns a map whose keys is the intersection of the keys of map1
and map2
. f.f
is used to combine the values a key is mapped in both maps.
Assumes f.f
idempotent (i.e. f.f key value value == value
) f.f
is called in the unsigned order of KEY.to_int
. f.f
is never called on physically equal values. Preserves physical equality as much as possible. Complexity is O(log(n)*Delta) where Delta is the number of different keys between map1
and map2
.
nonidempotent_inter_no_share f map1 map2
is the same as idempotent_inter
but doesn't preverse physical equality, doesn't assume f.f
is idempotent, and can change the type of values. f.f
is called on every shared binding. f.f
is called in increasing unsigned order of KEY.to_int
. O(n) complexity
val idempotent_inter_filter :
('a, 'a, 'a) polyinterfilter >
'a t >
'a t >
'a t
idempotent_inter_filter f map1 map2
is the same as idempotent_inter
but f.f
can return None
to remove a binding from the resutling map.
This is the same as Stdlib.Map.S.merge
type ('a, 'b) polydifference = ('a, 'b, 'a) polyinterfilter
val symmetric_difference : ('a, 'a) polydifference > '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 nonphysically equal values are passed to f.f
. If f.f
returns Some v
then v
is used as the new value, otherwise the binding is dropped.
Assumes f.f
is none on equal values (i.e. f.f key value value == None
) f.f
is called in increasing unsigned order of KEY.to_int
. f.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.
val difference : ('a, 'a) polydifference > 'a t > 'a t > 'a t
difference f map1 map2
returns the map containing the bindings of map1
that aren't in map2
. For keys present in both maps but with different values, f.f
is called. If it returns Some v
, then binding k,v
is kept, else k
is dropped.
Assumes f.f
is None
on the diagonal: f.f k v v = None
. f.f
is called in the unsigned order of KEY.to_int
. f.f
is never called on physically equal values.
Conversion functions
val to_seq : 'a t > 'a key_value_pair Stdlib.Seq.t
to_seq m
iterates the whole map, in increasing unsigned order of KEY.to_int
val to_rev_seq : 'a t > 'a key_value_pair Stdlib.Seq.t
to_rev_seq m
iterates the whole map, in decreasing unsigned order of KEY.to_int
val add_seq : 'a key_value_pair 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 : 'a key_value_pair 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 : 'a key_value_pair 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 > 'a key_value_pair list
to_list m
returns the bindings of m
as a list, in increasing unsigned order of KEY.to_int
module WithForeign (Map2 : BASE_MAP with type 'a key = 'a key) : sig ... end
Operation with maps/set of different types. Map2
must use the same KEY.to_int
function.
Hashconsing specific operations
val to_int : 'a t > int
Returns the hashconsed id of the map. Unlike NODE_WITH_ID.to_int
, hashconsing ensures that maps which contain the same keys (compared by KEY.to_int
) and values (compared by HASHED_VALUE.polyeq
) will always be physically equal and have the same identifier.
Note that when using physical equality as HASHED_VALUE.polyeq
, some maps of different types a t
and b t
may be given the same identifier. See the end of the documentation of HASHED_VALUE.polyeq
for details.
Constant time equality using the hashconsed nodes identifiers. This is equivalent to physical equality. Two nodes are equal if their trees contain the same bindings, where keys are compared by KEY.to_int
and values are compared by HASHED_VALUE.polyeq
.
Constant time comparison using the hashconsed node identifiers. This order is fully arbitrary, but it is total and can be used to sort nodes. It is based on node ids which depend on the order in which the nodes where created (older nodes having smaller ids).
One useful property of this order is that child nodes will always have a smaller identifier than their parents.