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 - HASH_CONSED_OPERATIONS

Operations added/changed in hash-consed maps and sets.

type 'a t

Hash-consing specific operations

val to_int : 'a t -> int

Returns the hash-consed id 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.

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.