|
| IntBag | | Portability | portable | | Stability | provisional | | Maintainer | daan@cs.uu.nl |
|
|
|
|
| Contents |
- Bag type
- Operators
- Query
- Construction
- Combine
- Filter
- Fold
- Conversion
- List
- Ordered list
- Occurrence lists
- IntMap
- Debugging
|
|
| Description |
An efficient implementation of bags of integers on top of the IntMap module. Many operations have a worst-case complexity of O(min(n,W)). This means that the
operation can become linear in the number of elements with a maximum of W
-- the number of bits in an Int (32 or 64). For more information, see
the references in the IntMap module.
|
|
| 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.4 |
