package patricia-tree

  1. Overview
  2. Docs
Patricia Tree data structure in OCaml for maps and sets. Supports generic key-value pairs

Install 

dune-project
 Dependency

codex.top Readme Changelog Edit opam file Versions (3)

Authors

  1. M
    Matthieu Lemerre <matthieu.lemerre@cea.fr>
  2. D
    Dorian Lesbre <dorian.lesbre@cea.fr>

Maintainers

  1. D
    Dorian Lesbre <dorian.lesbre@cea.fr>

Sources

patricia-tree-0.11.0.tbz
sha256=18fcde5d35d65c9bb2f9ec4ff732ecdd8969ba6fc2cf51d29ecb3be66e2fe664
sha512=da038d5096deb4bf3c02efd694e962ecf9b2571d140fa1fef17cce474f628ec070b93a44fd742748b9d3ba0e51041f864623d83e9cb0c72214abb0fb4a043625

doc/patricia-tree/PatriciaTree/MakeSet/index.html

Module PatriciaTree.MakeSetSource

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

Parameters

module Key : KEY

Signature

Sourcetype elt = Key.t

The type of elements of the set

Sourcetype key = elt

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

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

Underlying basemap, for cross map/set operations

Sourcetype t = unit BaseMap.t

The set type

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

cardinal set is 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 unsigned_min_elt : t -> elt

The minimal element (according to the unsigned order on KEY.to_int) if non empty.

Sourceval unsigned_max_elt : t -> elt

The maximal element (according to the unsigned order on KEY.to_int) if non empty.

Sourceval pop_unsigned_minimum : t -> (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 KEY.to_int.

Sourceval pop_unsigned_maximum : t -> (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 KEY.to_int.

Iterators

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

iter f set calls f on all elements of set, in the unsigned 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 the unsigned 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 the unsigned 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 unsigned 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. Uses the unsigned order on KEY.to_int.

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

Conversion functions

Sourceval to_seq : t -> elt Seq.t

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

Sourceval to_rev_seq : t -> elt Seq.t

to_rev_seq st iterates the whole set, in decreasing unsigned 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 unsigned order of KEY.to_int