module Ptset:sig..end
Sets of integers implemented as Patricia trees.
This implementation follows Chris Okasaki and Andrew Gill's paper Fast Mergeable Integer Maps.
Patricia trees provide faster operations than standard library's
module Set, and especially very fast union, subset, inter
and diff operations.
The idea behind Patricia trees is to build a trie on the
binary digits of the elements, and to compact the representation
by branching only one the relevant bits (i.e. the ones for which
there is at least on element in each subtree). We implement here
little-endian Patricia trees: bits are processed from
least-significant to most-significant. The trie is implemented by
the following type t. Empty stands for the empty trie, and
Leaf k for the singleton k. (Note that k is the actual
element.) Branch (m,p,l,r) represents a branching, where p is
the prefix (from the root of the trie) and m is the branching
bit (a power of 2). l and r contain the subsets for which the
branching bit is respectively 0 and 1. Invariant: the trees l
and r are not empty.
The docuemntation is given for function that differs from Set.S.
with type elt = int
module type S =sig..end
include Ptset.S
Big-endian Patricia trees
module Big:S
Big-endian Patricia trees with non-negative elements. Changes:
add and singleton raise Invalid_arg if a negative element is givenmem is slightly faster (the Patricia tree is now a search tree)min_elt and max_elt are now O(log(N))elements returns a list with elements in ascending ordermodule BigPos:S