The contents of this module may change in any way whatsoever
and without any warning between minor versions of this package.
Authors importing this module are expected to track development
closely.
Finite Int Sets (internals)
The IntSet type represents a set of elements of type Int. An IntSet
is strict in its elements.
Implementation
The implementation is based on big-endian patricia trees. This data
structure performs especially well on binary operations like union
and intersection. Additionally, benchmarks show that it is also
(much) faster on insertions and deletions when compared to a generic
size-balanced set implementation (see Data.Set).
D.R. Morrison,
"PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric",
Journal of the ACM, 15(4), October 1968, pages 514-534,
https://doi.org/10.1145/321479.321481.
Additionally, this implementation places bitmaps in the leaves of the tree.
Their size is the natural size of a machine word (32 or 64 bits) and greatly
reduces the memory footprint and execution times for dense sets, e.g. sets
where it is likely that many values lie close to each other. The asymptotics
are not affected by this optimization.
O(\min(n,W)). Take while a predicate on the elements holds.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
See note at spanAntitone.
O(\min(n,W)). Drop while a predicate on the elements holds.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
See note at spanAntitone.
O(\min(n,W)). Divide a set at the point where a predicate on the elements stops holding.
The user is responsible for ensuring that for all Ints, j < k ==> p j >= p k.
O(\min(n,W)). The expression (split x set) is a pair (set1,set2)
where set1 comprises the elements of set less than x and set2
comprises the elements of set greater than x.
O(1). Decompose a set into pieces based on the structure of the underlying
tree. This function is useful for consuming a set in parallel.
No guarantee is made as to the sizes of the pieces; an internal, but
deterministic process determines this. However, it is guaranteed that the
pieces returned will be in ascending order (all elements in the first submap
less than all elements in the second, and so on).
Note that the current implementation does not return more than two subsets,
but you should not depend on this behaviour because it can change in the
future without notice. Also, the current version does not continue
splitting all the way to individual singleton sets -- it stops at some
point.
mapMonotonic f s == map f s, but works only when f is strictly increasing.
Semi-formally, we have:
and [x < y ==> f x < f y | x <- ls, y <- ls]
==> mapMonotonic f s == map f s
where ls = toList s
Warning: This function should be used only if f is monotonically
strictly increasing. This precondition is not checked. Use map if the
precondition may not hold.
O(n). A strict version of foldr. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
O(n). A strict version of foldl. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
O(n). Build a set from an ascending list of elements.
Warning: This function should be used only if the elements are in
non-decreasing order. This precondition is not checked. Use fromList if the
precondition may not hold.
O(n). Build a set from an ascending list of distinct elements.
Warning: This function should be used only if the elements are in
strictly increasing order. This precondition is not checked. Use fromList
if the precondition may not hold.
O(n \min(n,W)). The expression (showTreeWith hang wide map) shows
the tree that implements the set. If hang is
True, a hanging tree is shown otherwise a rotated tree is shown. If
wide is True, an extra wide version is shown.