more-containers-0.2.2.2: A few more collections

Data.Multimap

Description

This modules provides a strict multimap implementation. To avoid collision with Prelude functions, it is recommended to import this module qualified:

import qualified Data.Multiset as Mmap

All complexities below use m for the number of distinct keys and n for the total number of entries in the multimap.

Synopsis

# Types

## Generic

data Multimap c k v Source #

A map where the same key can be present multiple times.

#### Instances

Instances details

type Group k cv = (k, cv) Source #

A group of values.

## Specific

type ListMultimap = Multimap [] Source #

A multimap with list values. Note that lists do not support efficient appends or sizing, so several multimap operations will have higher complexity than for other collections. If performance is a concern, consider using a SeqMultimap instead.

See Data.Multimap.List for operations specific to this type.

A multimap with Seq values.

See Data.Multimap.Seq for operations specific to this type.

A multimap with Set values. This multimap implementation will automatically deduplicate values per key. For example:

let mm = fromList [('a', 1), ('a', 1)] :: SetMultimap Char Int
size mm == 1 -- True

See Data.Multimap.Set for operations specific to this type.

# Construction

empty :: Multimap c k v Source #

O(1) Creates an empty multimap.

singleton :: Collection c => k -> v -> Multimap c k v Source #

O(1) Creates a multimap with a single entry.

fromList :: (Collection c, IsList (c v), Item (c v) ~ v, Ord k) => [(k, v)] -> Multimap c k v Source #

O(n * log n) Builds a multimap from a list of key, value tuples. The values are in the same order as in the original list.

fromListWith :: Ord k => ([v] -> c v) -> [(k, v)] -> Multimap c k v Source #

O(n * log n) Transforms a list of entries into a multimap, combining the values for each key into the chosen collection. The values are in the same order as in the original list.

fromGroupList :: (Collection c, Monoid (c v), Ord k) => [Group k (c v)] -> Multimap c k v Source #

O(m) Builds a multimap from already grouped collections.

fromMap :: Collection c => Map k (c v) -> Multimap c k v Source #

O(m * C) Transforms a map of collections into a multimap.

# Tests and accessors

null :: Multimap c k v -> Bool Source #

O(1) Checks whether the multimap is empty.

size :: Collection c => Multimap c k v -> Int Source #

O(m * C) Returns the size of the multimap.

distinctSize :: Multimap c k v -> Int Source #

O(1) Returns the number of distinct keys in the multimap.

member :: Ord k => k -> Multimap c k v -> Bool Source #

O(log m) Checks whether a key is present at least once in a multimap.

notMember :: Ord k => k -> Multimap c k v -> Bool Source #

O(log m) Checks whether a key is absent from a multimap.

find :: (Monoid (c v), Ord k) => k -> Multimap c k v -> c v Source #

O(log m) Returns the collection of values associated with a key.

(!) :: (Monoid (c v), Ord k) => Multimap c k v -> k -> c v Source #

O(log m) Infix version of find.

# Modification

prepend :: (Collection c, Monoid (c v), Ord k) => k -> v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Prepends a value to a key's collection.

prependMany :: (Collection c, Monoid (c v), Ord k) => k -> c v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Prepends a collection of values to a key's collection.

append :: (Collection c, Monoid (c v), Ord k) => k -> v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Appends a value to a key's collection.

appendMany :: (Collection c, Monoid (c v), Ord k) => k -> c v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Appends a collection of values to a key's collection.

deleteMany :: Ord k => k -> Multimap c k v -> Multimap c k v Source #

O(log m) Removes all entries for the given key.

modifyMany :: (Collection c, Monoid (c v), Ord k) => (c v -> c v) -> k -> Multimap c k v -> Multimap c k v Source #

Modifies a key's collection using an arbitrary function. More specifically, this function lifts an operation over a collection of values into a multimap operation.

Sample use to filter even values from a SetMultimap:

   let ms = fromList [('a', 1), ('a', 2)] :: SetMultimap Char Int
modifyMany (Set.filter even) 'a' ms == fromList [('a', 1)]


modifyManyF :: (Collection c, Monoid (c v), Ord k, Functor f) => (c v -> f (c v)) -> k -> Multimap c k v -> f (Multimap c k v) Source #

Modifies a key's collection using an arbitrary function. This is the applicative version of modifyMany.

# Maps and filters

mapGroups :: (Collection c2, Monoid (c2 v2), Ord k2) => (Group k1 (c1 v1) -> Group k2 (c2 v2)) -> Multimap c1 k1 v1 -> Multimap c2 k2 v2 Source #

Maps over the multimap's groups. This method can be used to convert between specific multimaps, for example:

let m1 = fromList [('a', 1), ('a', 1)] :: ListMultimap Char Int
let m2 = mapGroups (fmap Set.fromList) m1 :: SetMultimap Char Int

filter :: (Collection c, Monoid (c v), Ord k) => (v -> Bool) -> Multimap c k v -> Multimap c k v Source #

O(n) Filters multimap entries by value.

filterGroups :: (Collection c, Monoid (c v), Ord k) => (Group k (c v) -> Bool) -> Multimap c k v -> Multimap c k v Source #

O(m) Filters multimap groups. This enables filtering by key and collection.

# Conversion

toList :: Collection c => Multimap c k v -> [(k, v)] Source #

O(n) Converts a multimap into its list of entries. Note that this is different from toList which returns the multimap's values (similar to Data.Map).

toGroupList :: Multimap c k v -> [Group k (c v)] Source #

O(m) Converts a multimap into its list of collections.

toMap :: Multimap c k v -> Map k (c v) Source #

O(1) Converts a multimap into a map of collections.

# Other

keys :: Collection c => Multimap c k v -> [k] Source #

O(m) Returns a list of the multimap's keys. Each key will be repeated as many times as it is present in the multimap.

keysSet :: Multimap c k v -> Set k Source #

O(m) Returns a set of the multimap's (distinct) keys.

keysMultiset :: (Collection c, Ord k) => Multimap c k v -> Multiset k Source #

O(m * C) Returns a multiset of the map's keys with matching multiplicities.

inverse :: (Collection c, IsList (c k), Item (c k) ~ k, Ord k, Ord v) => Multimap c k v -> Multimap c v k Source #

O(n) Inverts keys and values inside a multimap.

inverseWith :: (Collection c1, Ord k, Ord v) => ([k] -> c2 k) -> Multimap c1 k v -> Multimap c2 v k Source #

O(n) Inverts keys and values inside a multimap, potentially changing the collection type.

maxViewWith :: (Collection c, Ord k) => (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v) Source #

Returns the multimap's maximum key and value. The input function is guaranteed to be called with a non-empty collection.

Since: 0.2.1.2

minViewWith :: (Collection c, Ord k) => (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v) Source #

Returns the multimap's minimum key and value. The input function is guaranteed to be called with a non-empty collection.

Since: 0.2.1.2