|
|
|
|
|
Description |
|
|
Synopsis |
|
|
|
|
Bag type
|
|
data IntBag |
A bag of integers.
| Instances | |
|
|
Operators
|
|
(\\) :: IntBag -> IntBag -> IntBag |
O(n+m). See difference.
|
|
Query
|
|
isEmpty :: IntBag -> Bool |
O(1). Is the bag empty?
|
|
size :: IntBag -> Int |
O(n). The number of elements in the bag.
|
|
distinctSize :: IntBag -> Int |
O(n). Returns the number of distinct elements in the bag, ie. (distinctSize bag == length (nub (toList bag))).
|
|
member :: Int -> IntBag -> Bool |
O(min(n,W)). Is the element in the bag?
|
|
occur :: Int -> IntBag -> Int |
O(min(n,W)). The number of occurrences of an element in the bag.
|
|
subset :: IntBag -> IntBag -> Bool |
O(n+m). Is this a subset of the bag?
|
|
properSubset :: IntBag -> IntBag -> Bool |
O(n+m). Is this a proper subset? (ie. a subset and not equal)
|
|
Construction
|
|
empty :: IntBag |
O(1). Create an empty bag.
|
|
single :: Int -> IntBag |
O(1). Create a singleton bag.
|
|
insert :: Int -> IntBag -> IntBag |
O(min(n,W)). Insert an element in the bag.
|
|
insertMany :: Int -> Int -> IntBag -> IntBag |
O(min(n,W)). The expression (insertMany x count bag)
inserts count instances of x in the bag bag.
|
|
delete :: Int -> IntBag -> IntBag |
O(min(n,W)). Delete a single element.
|
|
deleteAll :: Int -> IntBag -> IntBag |
O(min(n,W)). Delete all occurrences of an element.
|
|
Combine
|
|
union :: IntBag -> IntBag -> IntBag |
O(n+m). Union of two bags. The union adds the elements together.
IntBag\> union (fromList [1,1,2]) (fromList [1,2,2,3])
{1,1,1,2,2,2,3}
|
|
difference :: IntBag -> IntBag -> IntBag |
O(n+m). Difference between two bags.
IntBag\> difference (fromList [1,1,2]) (fromList [1,2,2,3])
{1}
|
|
intersection :: IntBag -> IntBag -> IntBag |
O(n+m). Intersection of two bags.
IntBag\> intersection (fromList [1,1,2]) (fromList [1,2,2,3])
{1,2}
|
|
unions :: [IntBag] -> IntBag |
The union of a list of bags.
|
|
Filter
|
|
filter :: (Int -> Bool) -> IntBag -> IntBag |
O(n). Filter all elements that satisfy some predicate.
|
|
partition :: (Int -> Bool) -> IntBag -> (IntBag, IntBag) |
O(n). Partition the bag according to some predicate.
|
|
Fold
|
|
fold :: (Int -> b -> b) -> b -> IntBag -> b |
O(n). Fold over each element in the bag.
|
|
foldOccur :: (Int -> Int -> b -> b) -> b -> IntBag -> b |
O(n). Fold over all occurrences of an element at once.
In a call (foldOccur f z bag), the function f takes
the element first and than the occur count.
|
|
Conversion
|
|
elems :: IntBag -> [Int] |
O(n). The list of elements.
|
|
List
|
|
toList :: IntBag -> [Int] |
O(n). Create a list with all elements.
|
|
fromList :: [Int] -> IntBag |
O(n*min(n,W)). Create a bag from a list of elements.
|
|
Ordered list
|
|
toAscList :: IntBag -> [Int] |
O(n). Create an ascending list of all elements.
|
|
fromAscList :: [Int] -> IntBag |
O(n*min(n,W)). Create a bag from an ascending list.
|
|
fromDistinctAscList :: [Int] -> IntBag |
O(n*min(n,W)). Create a bag from an ascending list of distinct elements.
|
|
Occurrence lists
|
|
toOccurList :: IntBag -> [(Int, Int)] |
O(n). Create a list of element/occurrence pairs.
|
|
toAscOccurList :: IntBag -> [(Int, Int)] |
O(n). Create an ascending list of element/occurrence pairs.
|
|
fromOccurList :: [(Int, Int)] -> IntBag |
O(n*min(n,W)). Create a bag from a list of element/occurrence pairs.
|
|
fromAscOccurList :: [(Int, Int)] -> IntBag |
O(n*min(n,W)). Create a bag from an ascending list of element/occurrence pairs.
|
|
IntMap
|
|
toMap :: IntBag -> IntMap Int |
O(1). Convert to an IntMap from elements to number of occurrences.
|
|
fromMap :: IntMap Int -> IntBag |
O(n). Convert a IntMap from elements to occurrences into a bag.
|
|
fromOccurMap :: IntMap Int -> IntBag |
O(1). Convert a IntMap from elements to occurrences into a bag.
Assumes that the IntMap contains only elements that occur at least once.
|
|
Debugging
|
|
showTree :: IntBag -> String |
O(n). Show the tree structure that implements the IntBag. The tree
is shown as a compressed and hanging.
|
|
showTreeWith :: Bool -> Bool -> IntBag -> String |
O(n). The expression (showTreeWith hang wide map) shows
the tree that implements the bag. The tree is shown hanging when hang is True
and otherwise as a rotated tree. When wide is True an extra wide version
is shown.
|
|
Produced by Haddock version 0.8 |