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 - `MakeHashconsedHeterogeneousSet`

Hash-consed version of `HETEROGENEOUS_SET`

. See Hash-consed maps and sets for the differences between hash-consed and non hash-consed sets.

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).

## Parameters

`module Key : HETEROGENEOUS_KEY`

## Signature

`include HETEROGENEOUS_SET with type 'a elt = 'a Key.t`

`type 'a elt = 'a Key.t`

Elements of the set

```
module BaseMap :
HETEROGENEOUS_MAP with type 'a key = 'a elt and type (_, _) value = unit
```

Underlying basemap, for cross map/set operations

`type t = unit BaseMap.t`

The type of our set

`type 'a key = 'a elt`

Alias for elements, for compatibility with other PatriciaTrees

## Basic functions

`val empty : t`

The empty set

`val is_empty : t -> bool`

`is_empty st`

is `true`

if `st`

contains no elements, `false`

otherwise

`add elt set`

adds element `elt`

to the `set`

. Preserves physical equality if `elt`

was already present. O(log(n)) complexity.

`val cardinal : t -> int`

the size of the set (number of elements), O(n) complexity.

`is_singleton set`

is `Some (Any elt)`

if `set`

is `singleton elt`

and `None`

otherwise.

`remove elt set`

returns a set containing all elements of `set`

except `elt`

. Returns a value physically equal to `set`

if `elt`

is not present.

The minimal element if non empty, according to the unsigned order on elements.

The maximal element if non empty, according to the unsigned order on elements.

`pop_unsigned_minimum s`

is `Some (elt, s')`

where `elt = unsigned_min_elt s`

and `s' = remove elt s`

if `s`

is non empty. Uses the unsigned order on elements.

`pop_unsigned_maximum s`

is `Some (elt, s')`

where `elt = unsigned_max_elt s`

and `s' = remove elt s`

if `s`

is non empty. Uses the unsigned order on elements.

## Functions on pairs of sets

`union a b`

is the set union of `a`

and `b`

, i.e. the set containing all elements that are either in `a`

or `b`

.

`inter a b`

is the set intersection of `a`

and `b`

, i.e. the set containing all elements that are in both `a`

or `b`

.

`split elt set`

returns `s_lt, present, s_gt`

where `s_lt`

contains all elements of `set`

smaller than `elt`

, `s_gt`

all those greater than `elt`

, and `present`

is `true`

if `elt`

is in `set`

. Uses the unsigned order on elements.

## Iterators

`iter f set`

calls `f.f`

on all elements of `set`

, in the unsigned order of `KEY.to_int`

.

`val filter : polypredicate -> t -> t`

`filter f set`

is the subset of `set`

that only contains the elements that satisfy `f.f`

. `f.f`

is called in the unsigned order of `KEY.to_int`

.

`val for_all : polypredicate -> t -> bool`

`for_all f set`

is `true`

if `f.f`

is `true`

on all elements of `set`

. Short-circuits on first `false`

. `f.f`

is called in the unsigned order of `KEY.to_int`

.

`fold f set acc`

returns `f.f elt_n (... (f.f elt_1 acc) ...)`

, where `elt_1, ..., elt_n`

are the elements of `set`

, in increasing unsigned order of `KEY.to_int`

```
val pretty :
?pp_sep:(Stdlib.Format.formatter -> unit -> unit) ->
polypretty ->
Stdlib.Format.formatter ->
t ->
unit
```

Pretty prints the set, `pp_sep`

is called once between each element, it defaults to `Format.pp_print_cut`

## Conversion functions

`to_seq st`

iterates the whole set, in increasing unsigned order of `KEY.to_int`

`to_rev_seq st`

iterates the whole set, in decreasing unsigned order of `KEY.to_int`

`add_seq s st`

adds all elements of the sequence `s`

to `st`

in order.

`to_list s`

returns the elements of `s`

as a list, in increasing unsigned order of `KEY.to_int`

### Hash-consing specific operations

`val to_int : 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.

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`

.

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.