package patricia-tree

  1. Overview
  2. Docs

Module type PatriciaTree.SETSource

Signature for sets implemented using Patricia trees. Most of this interface should be shared with Stdlib.Set.S.

Sourcetype elt

The type of elements of the set

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

Underlying basemap, for cross map/set operations

Basic functions

Sourcetype key = elt

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

Sourcetype t = unit BaseMap.t

The set type

Sourceval empty : t

The empty set

Sourceval is_empty : t -> bool

is_empty st is true if st contains no elements, false otherwise

Sourceval mem : elt -> t -> bool

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

Sourceval add : elt -> t -> t

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

Sourceval singleton : elt -> t

singleton elt returns a set containing a single element: elt

Sourceval cardinal : t -> int

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

Sourceval is_singleton : t -> elt option

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

Sourceval remove : 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.

Sourceval min_elt : t -> elt

The minimal element if non empty.

Sourceval max_elt : t -> elt

The maximal element if non empty.

Sourceval pop_minimum : t -> (elt * t) option

pop_minimum s is Some (elt, s') where elt = min_elt s and s' = remove elt s if s is non empty.

Sourceval pop_maximum : t -> (elt * t) option

pop_maximum s is Some (elt, s') where elt = max_elt s and s' = remove elt s if s is non empty.

Iterators

Sourceval iter : (elt -> unit) -> t -> unit

iter f set calls f on all elements of set, in order of Key.to_int.

Sourceval filter : (elt -> bool) -> t -> t

filter f set is the subset of set that only contains the elements that satisfy f. f is called in order of Key.to_int.

Sourceval for_all : (elt -> bool) -> t -> bool

for_all f set is true if f is true on all elements of set. Short-circuits on first false. f is called in order of Key.to_int.

Sourceval fold : (elt -> 'acc -> 'acc) -> t -> 'acc -> 'acc

fold f set acc returns f elt_n (... (f elt_1 acc) ...), where elt_1, ..., elt_n are the elements of set, in increasing order of Key.to_int

Sourceval split : 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.

Sourceval pretty : ?pp_sep:(Format.formatter -> unit -> unit) -> (Format.formatter -> elt -> unit) -> 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

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

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

Sourceval disjoint : t -> t -> bool

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

Sourceval equal : t -> t -> bool

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

Sourceval subset : t -> t -> bool

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

Conversion functions

Sourceval to_seq : t -> elt Seq.t

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

Sourceval to_rev_seq : t -> elt Seq.t

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

Sourceval add_seq : elt Seq.t -> t -> t

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

Sourceval of_seq : elt Seq.t -> t

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

Sourceval of_list : elt list -> t

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

Sourceval to_list : t -> elt list

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