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

Create a Patricia tree based heterogeneous set, analogous to the standard library's Set.Make, but with an extra type parameter: a set stores elements of type 'a elt.

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.

Parameters

Signature

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

type any_elt =
  1. | Any : 'a elt -> any_elt

Existential wrapper for set elements.

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

val mem : 'a elt -> t -> bool

mem elt set is true if elt is contained in set, O(log(n)) complexity.

val add : 'a elt -> t -> t

add elt set adds element elt to the set. Preserves physical equality if elt was already present. O(log(n)) complexity.

val singleton : 'a elt -> t

singleton elt returns a set containing a single element: elt

val cardinal : t -> int

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

val is_singleton : t -> any_elt option

is_singleton set is Some (Any elt) if set is singleton elt and None otherwise.

val remove : 'a elt -> t -> t

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.

val unsigned_min_elt : t -> any_elt

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

  • raises Not_found
val unsigned_max_elt : t -> any_elt

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

  • raises Not_found
val pop_unsigned_minimum : t -> (any_elt * t) option

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.

val pop_unsigned_maximum : t -> (any_elt * t) option

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

val union : t -> t -> t

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.

val inter : t -> t -> t

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.

val disjoint : t -> t -> bool

disjoint a b is true if a and b have no elements in common.

val equal : t -> t -> bool

equal a b is true if a and b contain the same elements.

val subset : t -> t -> bool

subset a b is true if all elements of a are also in b.

val split : 'a elt -> t -> t * bool * t

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.

val diff : t -> t -> t

diff s1 s2 is the set of all elements of s1 that aren't in s2.

  • since 0.11.0

Iterators

type polyiter = {
  1. f : 'a. 'a elt -> unit;
}
val iter : polyiter -> t -> unit

iter f set calls f.f on all elements of set, in the unsigned order of KEY.to_int.

type polypredicate = {
  1. f : 'a. 'a elt -> bool;
}
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.

type 'acc polyfold = {
  1. f : 'a. 'a elt -> 'acc -> 'acc;
}
val fold : 'acc polyfold -> t -> 'acc -> 'acc

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

type polypretty = {
  1. f : 'a. Stdlib.Format.formatter -> 'a elt -> unit;
}
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

val to_seq : t -> any_elt Stdlib.Seq.t

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

val to_rev_seq : t -> any_elt Stdlib.Seq.t

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

val add_seq : any_elt Stdlib.Seq.t -> t -> t

add_seq s st adds all elements of the sequence s to st in order.

val of_seq : any_elt Stdlib.Seq.t -> t

of_seq s creates a new set from the elements of s.

val of_list : any_elt list -> t

of_list l creates a new set from the elements of l.

val to_list : t -> any_elt list

to_list s returns the elements of s as a list, in increasing unsigned order of KEY.to_int