patricia-tree 0.9.0 · OCaml Package

A set containing different keys, very similar to SET, but with simple type elt being replaced by type constructor 'a elt.

Parameters

module Key : HETEROGENEOUS_KEY

Signature

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.

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 =

| Any : 'a elt -> any_elt
(*
Existential wrapper for keys
*)

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 min_elt : t -> any_elt

The minimal element if non empty.

raises Not_found

val max_elt : t -> any_elt

The maximal element if non empty.

raises Not_found

val pop_minimum : t -> (any_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.

val pop_maximum : t -> (any_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.

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.

Iterators

type polyiter = {

f : 'a. 'a elt -> unit;

}

val iter : polyiter -> t -> unit

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

type polypredicate = {

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 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 order of Key.to_int.

type 'acc polyfold = {

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 order of Key.to_int

type polypretty = {

f : 'a. Format.formatter -> 'a elt -> unit;

}

val pretty : 
  ?pp_sep:(Format.formatter -> unit -> unit) ->
  polypretty ->
  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 Seq.t

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

val to_rev_seq : t -> any_elt Seq.t

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

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

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

val of_seq : any_elt 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 order of Key.to_int