Data.SetMap

A SetMap allows the association of multiple values with a single key, but there are no duplicates per key.

SetMap type

data SetMap k v

A SetMap with keys k and values v.

Instances

(Data k, Data v, Ord k, Ord v) => Data (SetMap k v)

Typeable (* -> * -> *) SetMap

Query

null :: SetMap k a -> Bool

O(1). Check whether the multimap is empty or not.

size :: SetMap k a -> Int

O(1). The number of elements in the multimap.

numKeys :: SetMap k a -> Word32

O(1). The number of keys in the multimap.

As this is a multimap, the number of keys is not necessarily equal to the number of values.

numValues :: SetMap k a -> Word32

O(1). The number of values in the multimap.

As this is a multimap, the number of keys is not necessarily equal to the number of values.

member :: Ord k => SetMap k a -> k -> Bool

O(log n). Is the key a member of the multimap?

notMember :: Ord k => SetMap k a -> k -> Bool

O(log n). Is the key not a member of the multimap?

lookup :: Ord k => k -> SetMap k a -> Set a

O(log n). Lookup the value at a key in the map.

The function will return the corrsponding values as a List, or the empty list if no values are associated witht the given key.

Operators

(!) :: Ord k => SetMap k a -> k -> Set a

As flip lookup

Construction

empty :: SetMap k a

O(1). The empty multimap.

Insertion

insert :: (Ord k, Ord a) => k -> a -> SetMap k a -> SetMap k a

Insert a new key and value in the map.

Deletion

delete :: Ord k => k -> SetMap k a -> SetMap k a

Delete a key and all its values from the map.

Traversal

map :: (Ord a, Ord b) => (a -> b) -> SetMap k a -> SetMap k b

Map a function over all values in the map.

Conversion

elems :: SetMap k a -> [[a]]

Return all elements of the multimap in the ascending order of their keys.

A list of lists is returned since a key can have multiple values. Use concat to flatten.

keys :: SetMap k a -> [k]

O(n). Return all keys of the multimap in ascending order.

toMap :: SetMap k a -> Map k (Set a)

O(1). Return the map of sets.