Patricia Tree API - `NodeWithId`

Here, nodes also contain a unique id, e.g. so that they can be used as keys of maps or hash-tables.

Parameters

module Key : sig ... end

module Value : HETEROGENEOUS_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

Unique number for each node.

This is not hash-consing. Equal nodes created separately will have different identifiers. On the flip side, nodes with equal identifiers will always be physically equal.

Patricia Tree API - NodeWithId