package patricia-tree

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Basic functions
Iterators
Functions on pairs of sets
Conversion functions

patricia-tree
- PatriciaTree
  - BASE_MAP
  - HASHED_VALUE
  - HASH_CONSED_NODE
  - HETEROGENEOUS_HASHED_VALUE
  - HETEROGENEOUS_KEY
  - HETEROGENEOUS_MAP
    
    WithForeign
    
    Map2
  - HETEROGENEOUS_SET
    
    BaseMap
    
    WithForeign
    
    Map2
  - HETEROGENEOUS_VALUE
  - HashconsedNode
    
    Key
    
    Value
  - HashconsedSetNode
    
    Key
  - HashedValue
  - HeterogeneousHashedValue
  - HomogeneousValue
  - KEY
  - MAP
    
    BaseMap
    
    WithForeign
    
    Map2
    
    WithForeign
    
    Map2
  - MAP_WITH_VALUE
    
    BaseMap
    
    WithForeign
    
    Map2
    
    WithForeign
    
    Map2
  - MakeCustomHeterogeneousMap
    
    Key
    
    Node
    
    Value
    
    WithForeign
    
    Map2
  - MakeCustomHeterogeneousSet
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
    
    NODE
  - MakeCustomMap
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
    
    Node
    
    Value
    
    WithForeign
    
    Map2
  - MakeCustomSet
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
    
    Node
  - MakeHashconsedHeterogeneousMap
    
    Key
    
    Value
    
    WithForeign
    
    Map2
  - MakeHashconsedHeterogeneousSet
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
  - MakeHashconsedMap
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
    
    Value
    
    WithForeign
    
    Map2
  - MakeHashconsedSet
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
  - MakeHeterogeneousMap
    
    Key
    
    Value
    
    WithForeign
    
    Map2
  - MakeHeterogeneousSet
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
  - MakeMap
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
    
    WithForeign
    
    Map2
  - MakeSet
    
    BaseMap
    
    WithForeign
    
    Map2
    
    Key
  - NODE
  - NODE_WITH_ID
  - NodeWithId
    
    Key
    
    Value
  - SET
    
    BaseMap
    
    WithForeign
    
    Map2
  - SetNode
    
    Key
  - SimpleNode
    
    Key
    
    Value
  - VALUE
  - Value
  - WeakNode
    
    Key
    
    Value
  - WeakSetNode
    
    Key
  - WrappedHomogeneousValue

Legend:
Library
Module
Module type
Parameter
Class
Class type

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

type elt

The type of elements of the set

type key = elt

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

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

Underlying basemap, for cross map/set operations

type t = unit BaseMap.t

The set type

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

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

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

val singleton : elt -> t

singleton elt returns a set containing a single element: elt

val cardinal : t -> int

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

val is_singleton : t -> elt option

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

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

val unsigned_min_elt : t -> elt

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

raises Not_found

val unsigned_max_elt : t -> elt

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

raises Not_found

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

val 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

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

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

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

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

val 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

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

val 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

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.

Conversion functions

val to_seq : t -> elt Seq.t

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

val to_rev_seq : t -> elt Seq.t

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

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

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

val of_seq : elt Seq.t -> t

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

val of_list : elt list -> t

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

val to_list : t -> elt list

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