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