UU.DData.IntBag

Bag type

data IntBag

A bag of integers.

Instances

Eq IntBag

Show IntBag

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.IntMap from elements to number of occurrences.

fromMap :: IntMap Int -> IntBag

O(n). Convert a IntMap.IntMap from elements to occurrences into a bag.

fromOccurMap :: IntMap Int -> IntBag

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.

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.