| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Description | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

An efficient implementation of integer sets. This module is intended to be imported import Data.IntSet as Set The implementation is based on - Chris Okasaki and Andy Gill, "
*Fast Mergeable Integer Maps*", Workshop on ML, September 1998, pages 77-86, http://www.cse.ogi.edu/~andy/pub/finite.htm - D.R. Morrison, "
*PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric*", Journal of the ACM, 15(4), October 1968, pages 514-534.
Many operations have a worst-case complexity of | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Set type | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

data IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Operators | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

(\\) :: IntSet -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n+m). See difference.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Query | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

null :: IntSet -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(1). Is the set empty?
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

size :: IntSet -> Int | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). Cardinality of the set.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

member :: Int -> IntSet -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(min(n,W)). Is the value a member of the set?
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

isSubsetOf :: IntSet -> IntSet -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n+m). Is this a subset?
(s1 tells whether isSubsetOf s2)s1 is a subset of s2.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

isProperSubsetOf :: IntSet -> IntSet -> Bool | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n+m). Is this a proper subset? (ie. a subset but not equal).
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Construction | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

empty :: IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(1). The empty set.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

singleton :: Int -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(1). A set of one element.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

insert :: Int -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(min(n,W)). Add a value to the set. When the value is already
an element of the set, it is replaced by the new one, ie. insert
is left-biased.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

delete :: Int -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(min(n,W)). Delete a value in the set. Returns the
original set when the value was not present.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Combine | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

union :: IntSet -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n+m). The union of two sets.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

unions :: [IntSet] -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The union of a list of sets. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

difference :: IntSet -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n+m). Difference between two sets.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

intersection :: IntSet -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n+m). The intersection of two sets.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Filter | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

filter :: (Int -> Bool) -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). Filter all elements that satisfy some predicate.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). partition the set according to some predicate.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

split :: Int -> IntSet -> (IntSet, IntSet) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

(set1,set2)
where all elements in set1 are lower than x and all elements in
set2 larger than x.
split 3 (fromList [1..5]) == (fromList [1,2], fromList [3,4]) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

splitMember :: Int -> IntSet -> (IntSet, Bool, IntSet) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(log n). Performs a split but also returns whether the pivot
element was found in the original set.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Map | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

map :: (Int -> Int) -> IntSet -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

f to each element of s.
It's worth noting that the size of the result may be smaller if,
for some | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Fold | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

fold :: (Int -> b -> b) -> b -> IntSet -> b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

sum set == fold (+) 0 set elems set == fold (:) [] set | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Conversion | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

List | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

elems :: IntSet -> [Int] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). The elements of a set. (For sets, this is equivalent to toList)
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

toList :: IntSet -> [Int] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). Convert the set to a list of elements.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

fromList :: [Int] -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*min(n,W)). Create a set from a list of integers.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Ordered list | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

toAscList :: IntSet -> [Int] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). Convert the set to an ascending list of elements.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

fromAscList :: [Int] -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*min(n,W)). Build a set from an ascending list of elements.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

fromDistinctAscList :: [Int] -> IntSet | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n*min(n,W)). Build a set from an ascending list of distinct elements.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Debugging | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

showTree :: IntSet -> String | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

showTreeWith :: Bool -> Bool -> IntSet -> String | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

O(n). The expression () shows
the tree that implements the set. If showTreeWith hang wide maphang is
True, a hanging tree is shown otherwise a rotated tree is shown. If
wide is True, an extra wide version is shown.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 0.7 |