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

A set containing different keys, very similar to `SET`

, but with simple type `elt`

being replaced by type constructor `'a elt`

.

The main changes from `SET`

are:

- The type of
`elt`

is replaced by a type constructor`'k elt`

. Because of that, most higher-order arguments require higher-ranking polymorphism, and we provide records that allows to pass them as arguments (e.g.`polyfold`

,`polypretty`

, etc.) - The type of some return values, must be concealed existentially, hence the
`Any`

constructor.

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