- data IntBag
- (\\) :: IntBag -> IntBag -> IntBag
- isEmpty :: IntBag -> Bool
- size :: IntBag -> Int
- distinctSize :: IntBag -> Int
- member :: Int -> IntBag -> Bool
- occur :: Int -> IntBag -> Int
- subset :: IntBag -> IntBag -> Bool
- properSubset :: IntBag -> IntBag -> Bool
- empty :: IntBag
- single :: Int -> IntBag
- insert :: Int -> IntBag -> IntBag
- insertMany :: Int -> Int -> IntBag -> IntBag
- delete :: Int -> IntBag -> IntBag
- deleteAll :: Int -> IntBag -> IntBag
- union :: IntBag -> IntBag -> IntBag
- difference :: IntBag -> IntBag -> IntBag
- intersection :: IntBag -> IntBag -> IntBag
- unions :: [IntBag] -> IntBag
- filter :: (Int -> Bool) -> IntBag -> IntBag
- partition :: (Int -> Bool) -> IntBag -> (IntBag, IntBag)
- fold :: (Int -> b -> b) -> b -> IntBag -> b
- foldOccur :: (Int -> Int -> b -> b) -> b -> IntBag -> b
- elems :: IntBag -> [Int]
- toList :: IntBag -> [Int]
- fromList :: [Int] -> IntBag
- toAscList :: IntBag -> [Int]
- fromAscList :: [Int] -> IntBag
- fromDistinctAscList :: [Int] -> IntBag
- toOccurList :: IntBag -> [(Int, Int)]
- toAscOccurList :: IntBag -> [(Int, Int)]
- fromOccurList :: [(Int, Int)] -> IntBag
- fromAscOccurList :: [(Int, Int)] -> IntBag
- toMap :: IntBag -> IntMap Int
- fromMap :: IntMap Int -> IntBag
- fromOccurMap :: IntMap Int -> IntBag
- showTree :: IntBag -> String
- showTreeWith :: Bool -> Bool -> IntBag -> String
Bag type
Operators
Query
distinctSize :: IntBag -> IntSource
O(n). Returns the number of distinct elements in the bag, ie. (distinctSize bag == length (nub (toList bag))
).
properSubset :: IntBag -> IntBag -> BoolSource
O(n+m). Is this a proper subset? (ie. a subset and not equal)
Construction
insertMany :: Int -> Int -> IntBag -> IntBagSource
O(min(n,W)). The expression (insertMany x count bag
)
inserts count
instances of x
in the bag bag
.
Combine
union :: IntBag -> IntBag -> IntBagSource
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 -> IntBagSource
O(n+m). Difference between two bags.
IntBag\> difference (fromList [1,1,2]) (fromList [1,2,2,3]) {1}
intersection :: IntBag -> IntBag -> IntBagSource
O(n+m). Intersection of two bags.
IntBag\> intersection (fromList [1,1,2]) (fromList [1,2,2,3]) {1,2}
Filter
filter :: (Int -> Bool) -> IntBag -> IntBagSource
O(n). Filter all elements that satisfy some predicate.
partition :: (Int -> Bool) -> IntBag -> (IntBag, IntBag)Source
O(n). Partition the bag according to some predicate.
Fold
foldOccur :: (Int -> Int -> b -> b) -> b -> IntBag -> bSource
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
List
Ordered list
fromAscList :: [Int] -> IntBagSource
O(n*min(n,W)). Create a bag from an ascending list.
fromDistinctAscList :: [Int] -> IntBagSource
O(n*min(n,W)). Create a bag from an ascending list of distinct elements.
Occurrence lists
toOccurList :: IntBag -> [(Int, Int)]Source
O(n). Create a list of element/occurrence pairs.
toAscOccurList :: IntBag -> [(Int, Int)]Source
O(n). Create an ascending list of element/occurrence pairs.
fromOccurList :: [(Int, Int)] -> IntBagSource
O(n*min(n,W)). Create a bag from a list of element/occurrence pairs.
fromAscOccurList :: [(Int, Int)] -> IntBagSource
O(n*min(n,W)). Create a bag from an ascending list of element/occurrence pairs.
IntMap
toMap :: IntBag -> IntMap IntSource
O(1). Convert to an IntMap.IntMap
from elements to number of occurrences.
fromMap :: IntMap Int -> IntBagSource
O(n). Convert a IntMap.IntMap
from elements to occurrences into a bag.
fromOccurMap :: IntMap Int -> IntBagSource
O(1). Convert a IntMap.IntMap
from elements to occurrences into a bag.
Assumes that the IntMap.IntMap
contains only elements that occur at least once.