Util.IntBag

Map type

data IntBag

O(n+m). See difference. (\) :: IntBag -> IntBag -> IntBag m1 \ m2 = difference m1 m2

A map of integers to values a.

Instances

Eq IntBag

Ord IntBag

Show IntBag

Monoid IntBag

type Key = Int

Operators

(!) :: IntBag -> Key -> Int

O(min(n,W)). Find the value at a key. Calls error when the element can not be found.

Query

null :: IntBag -> Bool

O(1). Is the map empty?

size :: IntBag -> Int

O(n). Number of elements in the map.

Construction

empty :: IntBag

O(min(n,W)). The expression (findWithDefault def k map) returns the value at key k or returns def when the key is not an element of the map. findWithDefault :: Int -> Key -> IntBag -> Int findWithDefault def k m = case lookup k m of Nothing -> def Just x -> x

O(1). The empty map.

singleton :: Key -> IntBag

O(1). A map of one element.

msingleton :: Key -> Int -> IntBag

Insertion

insert :: Key -> Int -> IntBag -> IntBag

O(min(n,W)). Insert a new key/value pair in the map. If the key is already present in the map, the associated value is added to the supplied value, i.e. insert is equivalent to insertWith const.

Delete/Update

delete :: Key -> Int -> IntBag -> IntBag

O(min(n,W)). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.

Combine

Union

union :: IntBag -> IntBag -> IntBag

The union of a list of maps, with a combining operation unionsWith :: (Int->Int->Int) -> [IntBag] -> IntBag unionsWith f ts = foldlStrict (unionWith f) empty ts

O(n+m). The (left-biased) union of two maps. It prefers the first map when duplicate keys are encountered, i.e. (union == unionWith const).

Difference

Traversal

Map

Fold

fold :: (Int -> b -> b) -> b -> IntBag -> b

O(n+m). The union with a combining function. unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a unionWith f m1 m2 = unionWithKey (k x y -> f x y) m1 m2

O(n+m). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)). isProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool isProperSubmapOf m1 m2 = isProperSubmapOfBy (==) m1 m2

O(n+m). Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy f m1 m2) returns True when m1 and m2 are not equal, all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True:

 isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
 isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])

But the following are all False:

 isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
 isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
 isProperSubmapOfBy (<)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])

O(n+m). The expression (isSubmapOfBy f m1 m2) returns True if all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True:

 isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
 isSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
 isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])

But the following are all False:

 isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)])
 isSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
 isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])

O(n). Fold the values in the map, such that fold f z == foldr f z . elems. For example,

 elems map = fold (:) [] map

foldWithKey :: (Key -> Int -> b -> b) -> b -> IntBag -> b

O(n). Fold the keys and values in the map, such that foldWithKey f z == foldr (uncurry f) z . toAscList. For example,

 keys map = foldWithKey (\k x ks -> k:ks) [] map

Conversion

assocs :: IntBag -> [(Key, Int)]

O(n). Return all elements of the map in the ascending order of their keys. elems :: IntMap a -> [a] elems m = foldWithKey (k x xs -> x:xs) [] m

O(n). Return all key/value pairs in the map in ascending key order.

Lists

toList :: IntBag -> [(Key, Int)]

O(n). Convert the map to a list of key/value pairs.

fromList :: [(Key, Int)] -> IntBag

O(n*min(n,W)). Create a map from a list of key/value pairs.

Ordered lists

toAscList :: IntBag -> [(Key, Int)]

O(n). Convert the map to a list of key/value pairs where the keys are in ascending order.

Filter

Submap

Debugging