This is documentation for version v0.10.0 of patricia-tree, but the latest version is v0.11.0.
Click here to redirect to the latest version.

Patricia Tree API - `HashconsedNode`

Gives a unique number to each node like NodeWithId, but also performs hash-consing. So two maps with the same bindings will always be physically equal. See Hash-consed maps and sets for more details on this.

This is a generative functor, as calling it creates a new hash-table to store the created nodes, and a reference to store the next unallocated identifier. Maps/sets from different hash-consing functors (even if these functors have the same arguments) will have different (incompatible) numbering systems and be stored in different hash-tables (thus they will never be physically equal).

Using a single HashconsedNode in multiple MakeCustomMap functors will result in all those maps being hash-consed together (stored in the same hash-table, same numbering system).

since v0.10.0

Parameters

module Key : HETEROGENEOUS_KEY

module Value : HETEROGENEOUS_HASHED_VALUE

Signature

include NODE
  with type 'a key = 'a Key.t
  with type ('key, 'map) value = ('key, 'map) Value.t

Types

type 'a key = 'a Key.t

The type of keys.

type ('key, 'map) value = ('key, 'map) Value.t

The type of value, which depends on the type of the key and the type of the map.

type 'map t

The type of the map, which is parameterized by a type.

Constructors: build values

val empty : 'map t

The empty map

val leaf : 'key key -> ('key, 'map) value -> 'map t

A singleton leaf, similar to BASE_MAP.singleton

val branch : 
  prefix:intkey ->
  branching_bit:mask ->
  tree0:'map t ->
  tree1:'map t ->
  'map t

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 nor tree1 should be empty.
branching_bit should have a single bit set
prefix should be normalized (bits below branching_bit set to zero)
All elements of tree0 should have their to_int start by prefix followed by 0 at position branching_bit).
All elements of tree1 should have their to_int start by prefix followed by 0 at position branching_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 : {
1. prefix : intkey;
2. branching_bit : mask;
3. tree0 : 'map t;
4. tree1 : 'map t;
} -> '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 the branching_bit are set to zero (i.e. prefix & (branching_bit - 1) = 0).
- All elements of tree0 should have their to_int start by prefix followed by 0 at position branching_bit).
- All elements of tree1 should have their to_int start by prefix followed by 0 at position branching_bit).
*)
| Leaf : {
1. key : 'key key;
2. value : ('key, 'map) value;
} -> '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 copy-and-pasted for every node type.

val is_empty : 'map t -> bool

Check if the map is empty. Should be constant time.

val view : 'a t -> 'a view

Convert the map to a view. Should be constant time.

val to_int : 'a t -> int

Returns a unique number for each map, the hash-consed identifier of the map. Unlike NODE_WITH_ID.to_int, hash-consing 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.

Maps with the same identifier are also physically equal: to_int m1 = to_int m2 implies m1 == m2.

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.

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

Constant time equality using the hash-consed 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.

val compare : 'a t -> 'a t -> int

Constant time comparison using the hash-consed 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.

Patricia Tree API - HashconsedNode