uulib-0.9.10: Haskell Utrecht Tools LibrarySource codeContentsIndex
UU.DData.IntSet
Contents
Set type
Operators
Query
Construction
Combine
Filter
Fold
Conversion
List
Ordered list
Debugging
Description
Synopsis
data IntSet
(\\) :: IntSet -> IntSet -> IntSet
isEmpty :: IntSet -> Bool
size :: IntSet -> Int
member :: Int -> IntSet -> Bool
subset :: IntSet -> IntSet -> Bool
properSubset :: IntSet -> IntSet -> Bool
empty :: IntSet
single :: Int -> IntSet
insert :: Int -> IntSet -> IntSet
delete :: Int -> IntSet -> IntSet
union :: IntSet -> IntSet -> IntSet
unions :: [IntSet] -> IntSet
difference :: IntSet -> IntSet -> IntSet
intersection :: IntSet -> IntSet -> IntSet
filter :: (Int -> Bool) -> IntSet -> IntSet
partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)
split :: Int -> IntSet -> (IntSet, IntSet)
splitMember :: Int -> IntSet -> (Bool, IntSet, IntSet)
fold :: (Int -> b -> b) -> b -> IntSet -> b
elems :: IntSet -> [Int]
toList :: IntSet -> [Int]
fromList :: [Int] -> IntSet
toAscList :: IntSet -> [Int]
fromAscList :: [Int] -> IntSet
fromDistinctAscList :: [Int] -> IntSet
showTree :: IntSet -> String
showTreeWith :: Bool -> Bool -> IntSet -> String
Set type
data IntSet Source
A set of integers.
show/hide Instances
Operators
(\\) :: IntSet -> IntSet -> IntSetSource
O(n+m). See difference.
Query
isEmpty :: IntSet -> BoolSource
O(1). Is the set empty?
size :: IntSet -> IntSource
O(n). Cardinality of the set.
member :: Int -> IntSet -> BoolSource
O(min(n,W)). Is the value a member of the set?
subset :: IntSet -> IntSet -> BoolSource
O(n+m). Is this a subset?
properSubset :: IntSet -> IntSet -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Construction
empty :: IntSetSource
O(1). The empty set.
single :: Int -> IntSetSource
O(1). A set of one element.
insert :: Int -> IntSet -> IntSetSource
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 -> IntSetSource
O(min(n,W)). Delete a value in the set. Returns the original set when the value was not present.
Combine
union :: IntSet -> IntSet -> IntSetSource
O(n+m). The union of two sets.
unions :: [IntSet] -> IntSetSource
The union of a list of sets.
difference :: IntSet -> IntSet -> IntSetSource
O(n+m). Difference between two sets.
intersection :: IntSet -> IntSet -> IntSetSource
O(n+m). The intersection of two sets.
Filter
filter :: (Int -> Bool) -> IntSet -> IntSetSource
O(n). Filter all elements that satisfy some predicate.
partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)Source
O(n). partition the set according to some predicate.
split :: Int -> IntSet -> (IntSet, IntSet)Source
O(log n). The expression (split x set) is a pair (set1,set2) where all elements in set1 are lower than x and all elements in set2 larger than x.
splitMember :: Int -> IntSet -> (Bool, IntSet, IntSet)Source
O(log n). Performs a split but also returns whether the pivot element was found in the original set.
Fold
fold :: (Int -> b -> b) -> b -> IntSet -> bSource

O(n). Fold over the elements of a set in an unspecified order.

 sum set   = fold (+) 0 set
 elems set = fold (:) [] set
Conversion
List
elems :: IntSet -> [Int]Source
O(n). The elements of a set.
toList :: IntSet -> [Int]Source
O(n). Convert the set to a list of elements.
fromList :: [Int] -> IntSetSource
O(n*min(n,W)). Create a set from a list of integers.
Ordered list
toAscList :: IntSet -> [Int]Source
O(n). Convert the set to an ascending list of elements.
fromAscList :: [Int] -> IntSetSource
O(n*min(n,W)). Build a set from an ascending list of elements.
fromDistinctAscList :: [Int] -> IntSetSource
O(n*min(n,W)). Build a set from an ascending list of distinct elements.
Debugging
showTree :: IntSet -> StringSource
O(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format.
showTreeWith :: Bool -> Bool -> IntSet -> StringSource
O(n). 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.
Produced by Haddock version 2.4.2