This is documentation for the development version of Patricia Tree,
the latest released version is
v0.10.0.
Click here
to redirect to the latest version.
Patricia Tree API - MakeHashconsedSet
Hash-consed version of SET
. See Hash-consed maps and sets for the differences between hash-consed and non hash-consed sets.
This is a generative functor, as calling it creates a new hash-table to store the created nodes, and a reference to store the next unallocated identifier. Maps/sets from different hash-consing functors (even if these functors have the same arguments) will have different (incompatible) numbering systems and be stored in different hash-tables (thus they will never be physically equal).
Parameters
Signature
include SET with type elt = Key.t
type elt = Key.t
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
add elt set
adds element elt
to the set
. Preserves physical equality if elt
was already present. O(log(n)) complexity.
val cardinal : t -> int
cardinal set
is the size of the set (number of elements), O(n) complexity.
is_singleton set
is Some (Any elt)
if set
is singleton elt
and None
otherwise.
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.
The minimal element (according to the unsigned order on KEY.to_int
) if non empty.
The maximal element (according to the unsigned order on KEY.to_int
) if non empty.
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
.
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
iter f set
calls f
on all elements of set
, in the unsigned order of KEY.to_int
.
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
.
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
.
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
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:(Stdlib.Format.formatter -> unit -> unit) ->
(Stdlib.Format.formatter -> elt -> unit) ->
Stdlib.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
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
.
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
.
Conversion functions
to_seq st
iterates the whole set, in increasing unsigned order of KEY.to_int
to_rev_seq st
iterates the whole set, in decreasing unsigned order of KEY.to_int
add_seq s st
adds all elements of the sequence s
to st
in order.
to_list s
returns the elements of s
as a list, in increasing unsigned order of KEY.to_int
Hash-consing specific operations
val 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.
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
.
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.