package patricia-tree

  1. Overview
  2. Docs
package patricia-tree
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module PatriciaTree.MakeHeterogeneousSetSource

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

Sourcetype 'a elt = 'a Key.t

Elements of the set

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

Underlying basemap, for cross map/set operations

Sourcetype t = unit BaseMap.t

The type of our set

Sourcetype 'a key = 'a elt

Alias for elements, for compatibility with other PatriciaTrees

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

Existential wrapper for set elements.

Basic functions

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 : 'a elt -> t -> bool

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

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

Sourceval singleton : 'a 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 -> any_elt option

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

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

Sourceval unsigned_min_elt : t -> any_elt

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

Sourceval unsigned_max_elt : t -> any_elt

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

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

Sourceval 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

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 compare : t -> t -> int

compare s1 s2 is an order on setss. s1 and s2 are equal if they contain the same bindings (compare by KEY.to_int). s1 is strictly smaller than s2 if the first difference (in the order of KEY.to_int) is an element that appears in s2 but not in s1.

  • since v0.11.0
Sourceval subset : t -> t -> bool

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

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

Sourceval diff : t -> t -> t

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

  • since v0.11.0
Sourceval min_elt_inter : t -> t -> any_elt option

min_elt_inter s1 s2 is unsigned_min_elt of inter s1 s2, but faster as it does not require computing the whole intersection. Returns None when the intersection is empty.

  • since v0.11.0
Sourceval max_elt_inter : t -> t -> any_elt option

max_elt_inter s1 s2 is unsigned_max_elt of inter s1 s2, but faster as it does not require computing the whole intersection. Returns None when the intersection is empty.

  • since v0.11.0

Iterators

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

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

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

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

Sourcetype 'acc polyfold = {
  1. f : 'a. 'a elt -> 'acc -> 'acc;
}
Sourceval 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

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

Sourceval to_seq : t -> any_elt Seq.t

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

Sourceval to_rev_seq : t -> any_elt Seq.t

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

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

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

Sourceval of_seq : any_elt Seq.t -> t

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

Sourceval of_list : any_elt list -> t

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

Sourceval 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

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct