| ||||||||

| ||||||||

| ||||||||

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?
| ||||||||

notMember :: Int -> IntSet -> Bool | ||||||||

O(log n). Is the element not in 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 |