package ptset
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Module Ptset
Source
Sets of integers implemented as Patricia trees.
Following Chris Okasaki and Andrew Gill's paper "Fast Mergeable Integer Maps".
This is a purely applicative data structure implementing a large fragment of Set.S with type elt = int
, with identical specifications and similar performances.
One advantage of Patricia trees is unicity of representation. Thus OCaml's structural comparison can be used on sets.
sets implemented with little-endian Patricia trees
Notes:
- Functions
min_elt
,max_elt
, andelements
are purposely not provided, as there is no efficient way to implement them. If needed, you can implementmin_elt s
withfold min s (choose s)
, and similarly formax_elt
, but this has linear complexity.
- Functions
map
andsplit
are merely implemented usingfold
andadd
.
Additional functions not appearing in the signature Set.S
from ocaml standard library.
intersect u v
determines whether sets u
and v
have a non-empty intersection.
Big-endian Patricia trees
Big-endian Patricia trees with nonnegative elements only.
Changes:
add
andsingleton
raiseInvalid_arg
if a negative element is givenmem
is slightly faster (the Patricia tree is now a search tree)min_elt
andmax_elt
are provided (and efficient)elements
returns a list with elements in ascending order