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

Create a Patricia tree based set, analogous to the standard library's `Set.Make`

## Parameters

## Signature

`type elt = Key.t`

The type of elements of the set

`type key = elt`

Alias for the type of elements, for cross-compatibility with maps

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

Underlying basemap, for cross map/set operations

`type t = unit BaseMap.t`

The set type

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

`cardinal set`

is 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 (according to the unsigned order on `KEY.to_int`

) if non empty.

The maximal element (according to the unsigned order on `KEY.to_int`

) if non empty.

`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 `KEY.to_int`

.

`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 `KEY.to_int`

.

## Iterators

`iter f set`

calls `f`

on all elements of `set`

, in the unsigned order of `KEY.to_int`

.

`filter f set`

is the subset of `set`

that only contains the elements that satisfy `f`

. `f`

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

.

`for_all f set`

is `true`

if `f`

is `true`

on all elements of `set`

. Short-circuits on first `false`

. `f`

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

.

`fold f set acc`

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

, where `elt_1, ..., elt_n`

are the elements of `set`

, in increasing unsigned order of `KEY.to_int`

`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 `KEY.to_int`

.

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

Pretty prints the set, `pp_sep`

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

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

.

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