Patricia Tree API - HETEROGENEOUS_KEY

The signature of heterogeneous keys.

type 'key t

The type of generic/heterogeneous keys.

It is recommended to use immutable keys. If keys are mutable, any mutations to keys must preserve to_int. Failing to do so will break the patricia trees' invariants.

val to_int : 'key t -> int

A unique identifier for values of the type. Usually, we use a fresh counter that is increased to give a unique id to each object. Correctness of the operations requires that different values in a tree correspond to different integers.

Must be injective, and ideally fast. hash-consing keys is a good way to generate such unique identifiers.

Note that since Patricia Trees use unsigned order, negative keys are seen as bigger than positive keys. Be wary of this when using negative keys combined with functions like unsigned_max_binding and pop_unsigned_maximum.

val polyeq : 'a t -> 'b t -> ('a, 'b) cmp

Polymorphic equality function used to compare our keys. It should satisfy (to_int a) = (to_int b) ==> polyeq a b = Eq, and be fast.