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

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.15.0.tbz
sha256=e0fe66ab7da5b2ad240b64430d605f4064bc704bf487acc6314fd868e98ec279
sha512=72d267a727bdda2b3254a8459f6ab3b78ac539456dca8d026520a3a1537369d553d4008c17956d465ea40aa0fdca5a4df1d658fd28af68f73754904a0350d421

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

Module PatriciaTree.MakeHashconsedSetWithMutexSource

Thread-safe variant of MakeHashconsedSet, using a MUTEX to synchronize access.

  • since v0.12.0

Parameters

module Key : KEY
module Mutex : MUTEX

Signature

include SET with type elt = Key.t
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. O(1) complexity.

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

Iterators on pairs of sets

Sourceval for_all2 : left_only:(elt -> bool) forall2_pred -> common:(elt -> bool) forall2_pred -> right_only:(elt -> bool) forall2_pred -> t -> t -> bool

for_all2 ~reflexive ~left_only ~common ~right_only s1 s2 evaluates predicates on the elements of s1 and s2.

  • left_only k v1 is called for elements of s1 that don't appear in s2;
  • right_only k v2 is called for eleemnts of s2 that don't appear in s1;
  • common k v1 v2 is called for shared elements.

All three of these parameters can be either True, False, or a user supplied function (using F). The True and False constructors are faster, as knowing these values in advance avoids having to explore the relevant branches.

for_all2 explores elements in the unsigned order of KEY.to_int. It also has early-return: any false evaluation will stop exploration.

  • since v0.15.0
Sourceval exists2 : left_only:(elt -> bool) forall2_pred -> common:(elt -> bool) forall2_pred -> right_only:(elt -> bool) forall2_pred -> t -> t -> bool

Negation of for_all2. While for_all2 early returns at the first encountered false value. This early returns at the first encountered true.

  • since v0.15.0
Sourceval fold2 : left_only:(elt -> 'r -> 'r) option -> common:(elt -> 'r -> 'r) option -> right_only:(elt -> 'r -> 'r) option -> t -> t -> 'r -> 'r

fold2 ~reflexive ~left_only ~common ~right_only s1 s2 r iterates two sets s1 and s2 simultaneously, updating the accumulator r at each binding:

  • left_only x r is called on elements x present in s1 but not s2;
  • right_only k v2 r is called on elements present in s2 but not s1
  • common k v1 v2 r is called on shared elements.

Each of these can be None instead of a function, in which case the corresponding bindings are ignored. This can dramatically speed up the fold, as it then skips exploration of unneeded subtrees.

fold2 explores bindings in the unsigned order of KEY.to_int.

  • since v0.15.0
Sourceval iter2 : left_only:(elt -> unit) option -> common:(elt -> unit) option -> right_only:(elt -> unit) option -> t -> t -> unit

Calls the argument function on all bindings, just like fold2. Unlike fold2, each function returns unit so no accumulator is threaded.

  • since v0.15.0

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

Hash-consing specific operations

Sourceval to_int : t -> int

Returns the hash-consed id of the map. Unlike NODE_WITH_ID.to_int, hash-consing ensures that maps which contain the same keys (compared by KEY.to_int) and values (compared by HASHED_VALUE.polyeq) will always be physically equal and have the same identifier.

Note that when using physical equality as HASHED_VALUE.polyeq, some maps of different types a t and b t may be given the same identifier. See the end of the documentation of HASHED_VALUE.polyeq for details.

Sourceval equal : t -> t -> bool

Constant time equality using the hash-consed nodes identifiers. This is equivalent to physical equality. Two nodes are equal if their trees contain the same bindings, where keys are compared by KEY.to_int and values are compared by HASHED_VALUE.polyeq.

Sourceval compare : t -> t -> int

Constant time comparison using the hash-consed node identifiers. This order is fully arbitrary, but it is total and can be used to sort nodes. It is based on node ids which depend on the order in which the nodes where created (older nodes having smaller ids).

One useful property of this order is that child nodes will always have a smaller identifier than their parents.