-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A few multimap variants.
--
-- A library that provides a few multimap variants.
@package multi-containers
@version 0.2
module Data.Multimap.Internal
newtype Multimap k a
Multimap :: (Map k (NonEmpty a), Size) -> Multimap k a
type Size = Int
-- | O(1). The empty multimap.
--
--
-- size empty === 0
--
empty :: Multimap k a
-- | O(1). A multimap with a single element.
--
--
-- singleton 1 'a' === fromList [(1, 'a')]
-- size (singleton 1 'a') === 1
--
singleton :: k -> a -> Multimap k a
-- | O(1).
fromMap :: Map k (NonEmpty a) -> Multimap k a
-- | O(k). A key is retained only if it is associated with a
-- non-empty list of values.
--
--
-- fromMap' (Map.fromList [(1, "ab"), (2, ""), (3, "c")]) === fromList [(1, 'a'), (1, 'b'), (3, 'c')]
--
fromMap' :: Map k [a] -> Multimap k a
-- | O(n*log n) where n is the length of the input list.
-- Build a multimap from a list of key/value pairs.
--
--
-- fromList ([] :: [(Int, Char)]) === empty
--
fromList :: Ord k => [(k, a)] -> Multimap k a
-- | O(log k). If the key exists in the multimap, the new value will
-- be prepended to the list of values for the key.
--
--
-- insert 1 'a' empty === singleton 1 'a'
-- insert 1 'a' (fromList [(2, 'b'), (2, 'c')]) === fromList [(1, 'a'), (2, 'b'), (2, 'c')]
-- insert 1 'a' (fromList [(1, 'b'), (2, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
--
insert :: Ord k => k -> a -> Multimap k a -> Multimap k a
-- | O(log k). Delete a key and all its values from the map.
--
--
-- delete 1 (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === singleton 2 'c'
--
delete :: Ord k => k -> Multimap k a -> Multimap k a
-- | O(m*log k). Remove the first occurrence of the value associated
-- with the key, if exists.
--
--
-- deleteWithValue 1 'c' (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
-- deleteWithValue 1 'c' (fromList [(1, 'a'), (1, 'b'), (2, 'c'), (1, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
-- deleteWithValue 1 'c' (fromList [(2, 'c'), (1, 'c')]) === singleton 2 'c'
--
deleteWithValue :: (Ord k, Eq a) => k -> a -> Multimap k a -> Multimap k a
-- | O(log k). Remove the first value associated with the key. If
-- the key is associated with a single value, the key will be removed
-- from the multimap.
--
--
-- deleteOne 1 (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === fromList [(1, 'b'), (2, 'c')]
-- deleteOne 1 (fromList [(2, 'c'), (1, 'c')]) === singleton 2 'c'
--
deleteOne :: Ord k => k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function a -> a takes
-- O(1). Update values at a specific key, if exists.
--
--
-- adjust ("new " ++) 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(1,"new b"),(2,"c")]
--
adjust :: Ord k => (a -> a) -> k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function k -> a -> a
-- takes O(1). Update values at a specific key, if exists.
--
--
-- adjustWithKey (\k x -> show k ++ ":new " ++ x) 1 (fromList [(1,"a"),(1,"b"),(2,"c")])
-- === fromList [(1,"1:new a"),(1,"1:new b"),(2,"c")]
--
adjustWithKey :: Ord k => (k -> a -> a) -> k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function a -> Maybe
-- a takes O(1). The expression (update f k
-- map) updates the values at key k, if exists. If
-- f returns Nothing for a value, the value is deleted.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing in do
-- update f 1 (fromList [(1,"a"),(1, "b"),(2,"c")]) === fromList [(1,"new a"),(2, "c")]
-- update f 1 (fromList [(1,"b"),(1, "b"),(2,"c")]) === singleton 2 "c"
--
update :: Ord k => (a -> Maybe a) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function NonEmpty a ->
-- [a] takes O(1). The expression (update f k
-- map) updates the values at key k, if exists. If
-- f returns Nothing, the key is deleted.
--
--
-- update' NonEmpty.tail 1 (fromList [(1, "a"), (1, "b"), (2, "c")]) === fromList [(1, "b"), (2, "c")]
-- update' NonEmpty.tail 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
--
update' :: Ord k => (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function k -> a ->
-- Maybe a takes O(1). The expression
-- (updateWithKey f k map) updates the values at key
-- k, if exists. If f returns Nothing for a
-- value, the value is deleted.
--
--
-- let f k x = if x == "a" then Just (show k ++ ":new a") else Nothing in do
-- updateWithKey f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"1:new a"),(2,"c")]
-- updateWithKey f 1 (fromList [(1,"b"),(1,"b"),(2,"c")]) === singleton 2 "c"
--
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function k -> NonEmpty a
-- -> [a] takes O(1). The expression (update f
-- k map) updates the values at key k, if exists. If
-- f returns Nothing, the key is deleted.
--
--
-- let f k xs = if NonEmpty.length xs == 1 then (show k : NonEmpty.toList xs) else [] in do
-- updateWithKey' f 1 (fromList [(1, "a"), (1, "b"), (2, "c")]) === singleton 2 "c"
-- updateWithKey' f 1 (fromList [(1, "a"), (2, "b"), (2, "c")]) === fromList [(1, "1"), (1, "a"), (2, "b"), (2, "c")]
--
updateWithKey' :: Ord k => (k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function [a] -> [a] takes
-- O(1). The expression (alter f k map) alters the
-- values at k, if exists.
--
--
-- let (f, g) = (const [], ('c':)) in do
-- alter f 1 (fromList [(1, 'a'), (2, 'b')]) === singleton 2 'b'
-- alter f 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b')]
-- alter g 1 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'c'), (1, 'a'), (2, 'b')]
-- alter g 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b'), (3, 'c')]
--
alter :: Ord k => ([a] -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function k -> [a] -> [a]
-- takes O(1). The expression (alterWithKey f k
-- map) alters the values at k, if exists.
--
--
-- let (f, g) = (const (const []), (:) . show) in do
-- alterWithKey f 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
-- alterWithKey f 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b")]
-- alterWithKey g 1 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "1"), (1, "a"), (2, "b")]
-- alterWithKey g 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b"), (3, "3")]
--
alterWithKey :: Ord k => (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty list if the key is not in the map.
lookup :: Ord k => k -> Multimap k a -> [a]
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty list if the key is not in the map.
--
--
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 3 === "ac"
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 2 === []
--
(!) :: Ord k => Multimap k a -> k -> [a]
infixl 9 !
-- | O(log k). Is the key a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- member 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === True
-- member 1 (deleteOne 1 (fromList [(2, 'c'), (1, 'c')])) === False
--
member :: Ord k => k -> Multimap k a -> Bool
-- | O(log k). Is the key not a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- notMember 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === False
-- notMember 1 (deleteOne 1 (fromList [(2, 'c'), (1, 'c')])) === True
--
notMember :: Ord k => k -> Multimap k a -> Bool
-- | O(1). Is the multimap empty?
--
--
-- Data.Multimap.null empty === True
-- Data.Multimap.null (singleton 1 'a') === False
--
null :: Multimap k a -> Bool
-- | O(1). Is the multimap non-empty?
--
--
-- notNull empty === False
-- notNull (singleton 1 'a') === True
--
notNull :: Multimap k a -> Bool
-- | The total number of values for all keys.
--
-- size is evaluated lazily. Forcing the size for the first time
-- takes up to O(n) and subsequent forces take O(1).
--
--
-- size empty === 0
-- size (singleton 1 'a') === 1
-- size (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === 3
--
size :: Multimap k a -> Int
-- | Union two multimaps, concatenating values for duplicate keys.
--
--
-- union (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b')])
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c'),(2,'b')]
--
union :: Ord k => Multimap k a -> Multimap k a -> Multimap k a
-- | Union a number of multimaps, concatenating values for duplicate keys.
--
--
-- unions [fromList [(1,'a'),(2,'b'),(2,'c')], fromList [(1,'d'),(2,'b')]]
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c'),(2,'b')]
--
unions :: (Foldable f, Ord k) => f (Multimap k a) -> Multimap k a
-- | Difference of two multimaps.
--
-- If a key exists in the first multimap but not the second, it remains
-- unchanged in the result. If a key exists in both multimaps, a list
-- difference is performed on their values, i.e., the first occurrence of
-- each value in the second multimap is removed from the first multimap.
--
--
-- difference (fromList [(1,'a'),(2,'b'),(2,'c'),(2,'b')]) (fromList [(1,'d'),(2,'b'),(2,'a')])
-- === fromList [(1,'a'), (2,'c'), (2,'b')]
--
difference :: (Ord k, Eq a) => Multimap k a -> Multimap k a -> Multimap k a
-- | O(n), assuming the function a -> b takes
-- O(1). Map a function over all values in the map.
--
--
-- Data.Multimap.map (++ "x") (fromList [(1,"a"),(1,"a"),(2,"b")]) === fromList [(1,"ax"),(1,"ax"),(2,"bx")]
--
map :: (a -> b) -> Multimap k a -> Multimap k b
-- | O(n), assuming the function k -> a -> b takes
-- O(1). Map a function over all key/value pairs in the map.
--
--
-- mapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1,"a"),(1,"a"),(2,"b")]) === fromList [(1,"1:a"),(1,"1:a"),(2,"2:b")]
--
mapWithKey :: (k -> a -> b) -> Multimap k a -> Multimap k b
-- | Traverse key/value pairs and collect the results.
--
--
-- let f k a = if odd k then Just (succ a) else Nothing in do
-- traverseWithKey f (fromList [(1, 'a'), (1, 'b'), (3, 'b'), (3, 'c')]) === Just (fromList [(1, 'b'), (1, 'c'), (3, 'c'), (3, 'd')])
-- traverseWithKey f (fromList [(1, 'a'), (1, 'b'), (2, 'b')]) === Nothing
--
traverseWithKey :: Applicative t => (k -> a -> t b) -> Multimap k a -> t (Multimap k b)
-- | Traverse key/value pairs and collect the Just results.
traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> Multimap k a -> t (Multimap k b)
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator.
--
--
-- Data.Multimap.foldr ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr :: (a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator.
--
--
-- Data.Multimap.foldl (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl :: (a -> b -> a) -> a -> Multimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- right-associative binary operator.
--
--
-- foldrWithKey (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey :: (k -> a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). Fold the key/value pairs in the map using the given
-- left-associative binary operator.
--
--
-- foldlWithKey (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey :: (a -> k -> b -> a) -> a -> Multimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- monoid.
--
--
-- foldMapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1, "a"), (1, "a"), (2, "b")]) === "1:a1:a2:b"
--
foldMapWithKey :: Monoid m => (k -> a -> m) -> Multimap k a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.foldr' ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr' :: (a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.foldl' (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl' :: (a -> b -> a) -> a -> Multimap k b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldrWithKey' (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey' :: (k -> a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldlWithKey' (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey' :: (a -> k -> b -> a) -> a -> Multimap k b -> a
-- | O(n). Return all elements of the multimap in ascending order of
-- their keys.
--
--
-- elems (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === "bbac"
-- elems (empty :: Multimap Int Char) === []
--
elems :: Multimap k a -> [a]
-- | O(k). Return all keys of the multimap in ascending order.
--
--
-- keys (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === [1,2,3]
-- keys (empty :: Multimap Int Char) === []
--
keys :: Multimap k a -> [k]
-- | An alias for toAscList.
--
--
-- assocs (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
--
assocs :: Multimap k a -> [(k, a)]
-- | O(k). The set of all keys of the multimap.
--
--
-- keysSet (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === Set.fromList [1,2,3]
-- keysSet (empty :: Multimap Int Char) === Set.empty
--
keysSet :: Multimap k a -> Set k
-- | Convert the multimap into a list of key/value pairs.
--
--
-- toList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
--
toList :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in ascending order
-- of keys.
--
--
-- toAscList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
--
toAscList :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in descending
-- order of keys.
--
--
-- toDescList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(3,'c'),(2,'a'),(1,'b'),(1,'a')]
--
toDescList :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs, in a
-- breadth-first manner, in ascending order of keys.
--
--
-- toAscListBF (fromList [("Foo",1),("Foo",2),("Foo",3),("Bar",4),("Bar",5),("Baz",6)])
-- === [("Bar",4),("Baz",6),("Foo",1),("Bar",5),("Foo",2),("Foo",3)]
--
toAscListBF :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs, in a
-- breadth-first manner, in descending order of keys.
--
--
-- toDescListBF (fromList [("Foo",1),("Foo",2),("Foo",3),("Bar",4),("Bar",5),("Baz",6)])
-- === [("Foo",1),("Baz",6),("Bar",4),("Foo",2),("Bar",5),("Foo",3)]
--
toDescListBF :: Multimap k a -> [(k, a)]
-- | O(1). Convert the multimap into a regular map.
toMap :: Multimap k a -> Map k (NonEmpty a)
-- | O(n), assuming the predicate function takes O(1). Retain
-- all values that satisfy the predicate.
--
--
-- Data.Multimap.filter (> 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 1 'b'
-- Data.Multimap.filter (< 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === empty
--
filter :: (a -> Bool) -> Multimap k a -> Multimap k a
-- | O(n), assuming the predicate function takes O(1). Retain
-- all key/value pairs that satisfy the predicate.
--
--
-- filterWithKey (\k a -> even k && a > 'a') (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'b')]) === singleton 2 'b'
--
filterWithKey :: (k -> a -> Bool) -> Multimap k a -> Multimap k a
-- | O(k), assuming the predicate function takes O(1). Retain
-- all keys that satisfy the predicate.
--
--
-- filterKey even (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 2 'a'
--
filterKey :: (k -> Bool) -> Multimap k a -> Multimap k a
-- | Generalized filter.
--
--
-- let f a | a > 'b' = Just True
-- | a < 'b' = Just False
-- | a == 'b' = Nothing
-- in do
-- filterM f (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c')]) === Nothing
-- filterM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Just (fromList [(1,'c'),(2,'c')])
--
filterM :: (Ord k, Applicative t) => (a -> t Bool) -> Multimap k a -> t (Multimap k a)
-- | Generalized filterWithKey.
--
--
-- let f k a | even k && a > 'b' = Just True
-- | odd k && a < 'b' = Just False
-- | otherwise = Nothing
-- in do
-- filterWithKeyM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Nothing
-- filterWithKeyM f (fromList [(1,'a'),(1,'a'),(2,'c'),(2,'c')]) === Just (fromList [(2,'c'),(2,'c')])
--
filterWithKeyM :: (Ord k, Applicative t) => (k -> a -> t Bool) -> Multimap k a -> t (Multimap k a)
-- | O(n), assuming the function a -> Maybe b
-- takes O(1). Map values and collect the Just results.
--
--
-- mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === fromList [(1,"new a"),(2,"new a")]
--
mapMaybe :: (a -> Maybe b) -> Multimap k a -> Multimap k b
-- | O(n), assuming the function k -> a -> Maybe
-- b takes O(1). Map key/value pairs and collect the
-- Just results.
--
--
-- mapMaybeWithKey (\k a -> if k > 1 && a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === singleton 2 "new a"
--
mapMaybeWithKey :: (k -> a -> Maybe b) -> Multimap k a -> Multimap k b
-- | O(n), assuming the function a -> Either b c
-- takes O(1). Map values and separate the Left and
-- Right results.
--
--
-- mapEither (\a -> if a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(1,'a'),(2,'a')],fromList [(1,'c'),(2,'c')])
--
mapEither :: (a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
-- | O(n), assuming the function k -> a -> Either b
-- c takes O(1). Map key/value pairs and separate the
-- Left and Right results.
--
--
-- mapEitherWithKey (\k a -> if even k && a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(2,'a')],fromList [(1,'a'),(1,'c'),(2,'c')])
--
mapEitherWithKey :: (k -> a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
-- | O(log n). Return the smallest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMin (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (1, NonEmpty.fromList "ac")
-- lookupMin (empty :: Multimap Int Char) === Nothing
--
lookupMin :: Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the largest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMax (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (2, NonEmpty.fromList "c")
-- lookupMax (empty :: Multimap Int Char) === Nothing
--
lookupMax :: Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the largest key smaller than the given one,
-- and the associated values, if exist.
--
--
-- lookupLT 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLT 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupLT :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the smallest key larger than the given one,
-- and the associated values, if exist.
--
--
-- lookupGT 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGT 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupGT :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the largest key smaller than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupLE 0 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLE 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (1, NonEmpty.fromList "a")
-- lookupLE 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupLE :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the smallest key larger than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupGE 6 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGE 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (5, NonEmpty.fromList "c")
-- lookupGE 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupGE :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
instance (Data.Data.Data k, Data.Data.Data a, GHC.Classes.Ord k) => Data.Data.Data (Data.Multimap.Internal.Multimap k a)
instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Multimap.Internal.Multimap k a)
instance (GHC.Classes.Eq k, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Multimap.Internal.Multimap k a)
instance GHC.Classes.Eq k => Data.Functor.Classes.Eq1 (Data.Multimap.Internal.Multimap k)
instance Data.Functor.Classes.Eq2 Data.Multimap.Internal.Multimap
instance GHC.Classes.Ord k => Data.Functor.Classes.Ord1 (Data.Multimap.Internal.Multimap k)
instance Data.Functor.Classes.Ord2 Data.Multimap.Internal.Multimap
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.Multimap.Internal.Multimap k a)
instance GHC.Show.Show k => Data.Functor.Classes.Show1 (Data.Multimap.Internal.Multimap k)
instance Data.Functor.Classes.Show2 Data.Multimap.Internal.Multimap
instance (GHC.Classes.Ord k, GHC.Read.Read k, GHC.Read.Read e) => GHC.Read.Read (Data.Multimap.Internal.Multimap k e)
instance (GHC.Classes.Ord k, GHC.Read.Read k) => Data.Functor.Classes.Read1 (Data.Multimap.Internal.Multimap k)
instance GHC.Base.Functor (Data.Multimap.Internal.Multimap k)
instance Data.Foldable.Foldable (Data.Multimap.Internal.Multimap k)
instance Data.Traversable.Traversable (Data.Multimap.Internal.Multimap k)
instance GHC.Classes.Ord k => GHC.Base.Semigroup (Data.Multimap.Internal.Multimap k a)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.Multimap.Internal.Multimap k a)
module Data.Multimap.Set.Internal
newtype SetMultimap k a
SetMultimap :: (Map k (Set a), Size) -> SetMultimap k a
type Size = Int
-- | O(1). The empty multimap.
--
--
-- size empty === 0
--
empty :: SetMultimap k a
-- | O(1). A multimap with a single element.
--
--
-- singleton 1 'a' === fromList [(1, 'a')]
-- size (singleton 1 'a') === 1
--
singleton :: k -> a -> SetMultimap k a
-- | O(k). A key is retained only if it is associated with a
-- non-empty set of values.
fromMap :: Map k (Set a) -> SetMultimap k a
-- | O(n*log n) where n is the length of the input list.
-- Build a multimap from a list of key/value pairs.
--
--
-- fromList ([] :: [(Int, Char)]) === empty
-- fromList [(1, 'b'), (2, 'a'), (1, 'b')] === fromList [(1, 'b'), (2, 'a')]
--
fromList :: (Ord k, Ord a) => [(k, a)] -> SetMultimap k a
-- | O(log m * log k). If the key exists in the multimap, the new
-- value will be inserted into the set of values for the key. It is a
-- no-op if the value already exists in the set.
--
--
-- insert 1 'a' empty === singleton 1 'a'
-- insert 1 'a' (fromList [(1, 'b'), (2, 'a')]) === fromList [(1, 'a'), (1, 'b'), (2, 'a')]
-- insert 1 'a' (fromList [(1, 'a'), (2, 'c')]) === fromList [(1, 'a'), (2, 'c')]
--
insert :: (Ord k, Ord a) => k -> a -> SetMultimap k a -> SetMultimap k a
-- | O(log k). Delete a key and all its values from the map.
--
--
-- delete 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === singleton 2 'c'
--
delete :: Ord k => k -> SetMultimap k a -> SetMultimap k a
-- | O(log m * log k). Remove the first occurrence of the value
-- associated with the key, if exists.
--
--
-- deleteWithValue 1 'c' (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- deleteWithValue 1 'c' (fromList [(2,'c'),(1,'c')]) === singleton 2 'c'
--
deleteWithValue :: (Ord k, Ord a) => k -> a -> SetMultimap k a -> SetMultimap k a
-- | O(log m * log k). Remove the maximal value associated with the
-- key, if exists.
--
--
-- deleteMax 3 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- deleteMax 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(2,'c')]
--
deleteMax :: Ord k => k -> SetMultimap k a -> SetMultimap k a
-- | O(log m * log k). Remove the minimal value associated with the
-- key, if exists.
--
--
-- deleteMin 3 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- deleteMin 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'b'),(2,'c')]
--
deleteMin :: Ord k => k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function a -> a
-- takes O(1). Update values at a specific key, if exists.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- adjust ("new " ++) 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(1,"new b"),(2,"c")]
-- adjust (const "z") 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"z"),(2,"c")]
--
adjust :: (Ord k, Ord a) => (a -> a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function k -> a ->
-- a takes O(1). Update values at a specific key, if exists.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- adjustWithKey (\k x -> show k ++ ":new " ++ x) 1 (fromList [(1,"a"),(1,"b"),(2,"c")])
-- === fromList [(1,"1:new a"),(1,"1:new b"),(2,"c")]
--
adjustWithKey :: (Ord k, Ord a) => (k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function a ->
-- Maybe a takes O(1). The expression
-- (update f k map) updates the values at key k,
-- if exists. If f returns Nothing for a value, the value
-- is deleted.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing in do
-- update f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(2, "c")]
-- update f 1 (fromList [(1,"b"),(1,"c"),(2,"c")]) === singleton 2 "c"
--
update :: (Ord k, Ord a) => (a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function k -> a ->
-- Maybe a takes O(1). The expression
-- (updateWithKey f k map) updates the values at key
-- k, if exists. If f returns Nothing for a
-- value, the value is deleted.
--
--
-- let f k x = if x == "a" then Just (show k ++ ":new a") else Nothing in do
-- updateWithKey f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"1:new a"),(2,"c")]
-- updateWithKey f 1 (fromList [(1,"b"),(1,"c"),(2,"c")]) === singleton 2 "c"
--
updateWithKey :: (Ord k, Ord a) => (k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(log k), assuming the function Set a ->
-- Set a takes O(1). The expression (alter
-- f k map) alters the values at k, if exists.
--
--
-- let (f, g) = (const Set.empty, Set.insert 'c') in do
-- alter f 1 (fromList [(1, 'a'), (2, 'b')]) === singleton 2 'b'
-- alter f 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b')]
-- alter g 1 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'c'), (1, 'a'), (2, 'b')]
-- alter g 1 (fromList [(1, 'c'), (2, 'b')]) === fromList [(1, 'c'), (2, 'b')]
-- alter g 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b'), (3, 'c')]
--
alter :: Ord k => (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(log k), assuming the function k -> Set a ->
-- Set a takes O(1). The expression
-- (alterWithKey f k map) alters the values at k, if
-- exists.
--
--
-- let (f, g) = (const (const Set.empty), Set.insert . show) in do
-- alterWithKey f 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
-- alterWithKey f 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b")]
-- alterWithKey g 1 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "1"), (1, "a"), (2, "b")]
-- alterWithKey g 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b"), (3, "3")]
--
alterWithKey :: Ord k => (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty set if the key is not in the map.
lookup :: Ord k => k -> SetMultimap k a -> Set a
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty set if the key is not in the map.
--
--
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 3 === Set.fromList "ac"
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 2 === Set.empty
--
(!) :: Ord k => SetMultimap k a -> k -> Set a
infixl 9 !
-- | O(log k). Is the key a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- member 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === True
-- member 1 (deleteMax 1 (fromList [(2, 'c'), (1, 'c')])) === False
--
member :: Ord k => k -> SetMultimap k a -> Bool
-- | O(log k). Is the key not a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- notMember 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === False
-- notMember 1 (deleteMin 1 (fromList [(2, 'c'), (1, 'c')])) === True
--
notMember :: Ord k => k -> SetMultimap k a -> Bool
-- | O(1). Is the multimap empty?
--
--
-- Data.Multimap.Set.null empty === True
-- Data.Multimap.Set.null (singleton 1 'a') === False
--
null :: SetMultimap k a -> Bool
-- | O(1). Is the multimap non-empty?
--
--
-- notNull empty === False
-- notNull (singleton 1 'a') === True
--
notNull :: SetMultimap k a -> Bool
-- | The total number of values for all keys.
--
-- size is evaluated lazily. Forcing the size for the first time
-- takes up to O(k) and subsequent forces take O(1).
--
--
-- size empty === 0
-- size (singleton 1 'a') === 1
-- size (fromList [(1, 'a'), (2, 'b'), (2, 'c'), (2, 'b')]) === 3
--
size :: SetMultimap k a -> Int
-- | Union two multimaps, unioning values for duplicate keys.
--
--
-- union (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b')])
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c')]
--
union :: (Ord k, Ord a) => SetMultimap k a -> SetMultimap k a -> SetMultimap k a
-- | Union a number of multimaps, unioning values for duplicate keys.
--
--
-- unions [fromList [(1,'a'),(2,'b'),(2,'c')], fromList [(1,'d'),(2,'b')]]
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c')]
--
unions :: (Foldable f, Ord k, Ord a) => f (SetMultimap k a) -> SetMultimap k a
-- | Difference of two multimaps.
--
-- If a key exists in the first multimap but not the second, it remains
-- unchanged in the result. If a key exists in both multimaps, a set
-- difference is performed on their values.
--
--
-- difference (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b'),(2,'a')])
-- === fromList [(1,'a'),(2,'c')]
--
difference :: (Ord k, Ord a) => SetMultimap k a -> SetMultimap k a -> SetMultimap k a
-- | O(n * log m), assuming the function a -> b takes
-- O(1). Map a function over all values in the map.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- Data.Multimap.Set.map (++ "x") (fromList [(1,"a"),(2,"b")]) === fromList [(1,"ax"),(2,"bx")]
-- Data.Multimap.Set.map (const "c") (fromList [(1,"a"),(1,"b"),(2,"b")]) === fromList [(1,"c"),(2,"c")]
--
map :: Ord b => (a -> b) -> SetMultimap k a -> SetMultimap k b
-- | O(n * log m), assuming the function k -> a -> b
-- takes O(1). Map a function over all values in the map.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- mapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1,"a"),(2,"b")]) === fromList [(1,"1:a"),(2,"2:b")]
--
mapWithKey :: Ord b => (k -> a -> b) -> SetMultimap k a -> SetMultimap k b
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator.
--
--
-- Data.Multimap.Set.foldr ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr :: (a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator.
--
--
-- Data.Multimap.Set.foldl (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl :: (a -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- right-associative binary operator.
--
--
-- foldrWithKey (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). Fold the key/value pairs in the map using the given
-- left-associative binary operator.
--
--
-- foldlWithKey (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- monoid.
--
--
-- foldMapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1, "a"), (1, "c"), (2, "b")]) === "1:a1:c2:b"
--
foldMapWithKey :: Monoid m => (k -> a -> m) -> SetMultimap k a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Set.foldr' ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr' :: (a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Set.foldl' (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl' :: (a -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldrWithKey' (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey' :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldlWithKey' (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey' :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). Return all elements of the multimap in ascending order of
-- their keys. Elements of each key appear in ascending order.
--
--
-- elems (fromList [(2,'a'),(1,'b'),(3,'d'),(3,'c'),(1,'b')]) === "bacd"
-- elems (empty :: SetMultimap Int Char) === []
--
elems :: SetMultimap k a -> [a]
-- | O(k). Return all keys of the multimap in ascending order.
--
--
-- keys (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'b')]) === [1,2,3]
-- keys (empty :: SetMultimap Int Char) === []
--
keys :: SetMultimap k a -> [k]
-- | An alias for toAscList.
assocs :: SetMultimap k a -> [(k, a)]
-- | O(k). The set of all keys of the multimap.
--
--
-- keysSet (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'b')]) === Set.fromList [1,2,3]
-- keysSet (empty :: SetMultimap Int Char) === Set.empty
--
keysSet :: SetMultimap k a -> Set k
-- | Convert the multimap into a list of key/value pairs.
--
--
-- toList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'a'),(1,'b'),(2,'a'),(3,'c')]
--
toList :: SetMultimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in ascending order
-- of keys. Elements of each key appear in ascending order.
--
--
-- toAscList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'a'),(1,'b'),(2,'a'),(3,'c')]
--
toAscList :: SetMultimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in descending
-- order of keys. Elements of each key appear in descending order.
--
--
-- toDescList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(3,'c'),(2,'a'),(1,'b'),(1,'a')]
--
toDescList :: SetMultimap k a -> [(k, a)]
-- | O(1). Convert the multimap into a regular map.
toMap :: SetMultimap k a -> Map k (Set a)
-- | O(n), assuming the predicate function takes O(1). Retain
-- all values that satisfy the predicate. A key is removed if none of its
-- values satisfies the predicate.
--
--
-- Data.Multimap.Set.filter (> 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 1 'b'
-- Data.Multimap.Set.filter (< 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === empty
--
filter :: (a -> Bool) -> SetMultimap k a -> SetMultimap k a
-- | O(n), assuming the predicate function takes O(1). Retain
-- all key/value pairs that satisfy the predicate. A key is removed if
-- none of its values satisfies the predicate.
--
--
-- filterWithKey (\k a -> even k && a > 'a') (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'b')]) === singleton 2 'b'
--
filterWithKey :: (k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a
-- | O(k), assuming the predicate function takes O(1). Retain
-- all keys that satisfy the predicate.
filterKey :: (k -> Bool) -> SetMultimap k a -> SetMultimap k a
-- | Generalized filter.
--
--
-- let f a | a > 'b' = Just True
-- | a < 'b' = Just False
-- | a == 'b' = Nothing
-- in do
-- filterM f (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c')]) === Nothing
-- filterM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Just (fromList [(1,'c'),(2,'c')])
--
filterM :: (Ord k, Ord a, Applicative t) => (a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
-- | Generalized filterWithKey. | Generalized filterWithKey.
--
--
-- let f k a | even k && a > 'b' = Just True
-- | odd k && a < 'b' = Just False
-- | otherwise = Nothing
-- in do
-- filterWithKeyM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Nothing
-- filterWithKeyM f (fromList [(1,'a'),(3,'a'),(2,'c'),(4,'c')]) === Just (fromList [(2,'c'),(4,'c')])
--
filterWithKeyM :: (Ord k, Ord a, Applicative t) => (k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
-- | O(n * log m), assuming the function a -> Maybe
-- b takes O(1). Map values and collect the Just
-- results.
--
--
-- mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === fromList [(1,"new a"),(2,"new a")]
--
mapMaybe :: Ord b => (a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
-- | O(n * log m), assuming the function k -> a ->
-- Maybe b takes O(1). Map key/value pairs and collect
-- the Just results.
--
--
-- mapMaybeWithKey (\k a -> if k > 1 && a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === singleton 2 "new a"
--
mapMaybeWithKey :: Ord b => (k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
-- | O(n * log m), assuming the function a -> Either b
-- c takes O(1). Map values and separate the Left and
-- Right results.
--
--
-- mapEither (\a -> if a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(1,'a'),(2,'a')],fromList [(1,'c'),(2,'c')])
--
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
-- | O(n * log m), assuming the function k -> a ->
-- Either b c takes O(1). Map key/value pairs and
-- separate the Left and Right results.
--
--
-- mapEitherWithKey (\k a -> if even k && a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(2,'a')],fromList [(1,'a'),(1,'c'),(2,'c')])
--
mapEitherWithKey :: (Ord b, Ord c) => (k -> a -> Either b c) -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
-- | O(log n). Return the smallest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMin (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (1, Set.fromList "ac")
-- lookupMin (empty :: SetMultimap Int Char) === Nothing
--
lookupMin :: SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the largest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMax (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (2, Set.fromList "c")
-- lookupMax (empty :: SetMultimap Int Char) === Nothing
--
lookupMax :: SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the largest key smaller than the given one,
-- and the associated values, if exist.
--
--
-- lookupLT 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLT 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupLT :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the smallest key larger than the given one,
-- and the associated values, if exist.
--
--
-- lookupGT 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGT 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupGT :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the largest key smaller than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupLE 0 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLE 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (1, Set.fromList "a")
-- lookupLE 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupLE :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the smallest key larger than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupGE 6 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGE 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (5, Set.fromList "c")
-- lookupGE 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupGE :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
instance (Data.Data.Data k, Data.Data.Data a, GHC.Classes.Ord a, GHC.Classes.Ord k) => Data.Data.Data (Data.Multimap.Set.Internal.SetMultimap k a)
instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Multimap.Set.Internal.SetMultimap k a)
instance (GHC.Classes.Eq k, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Multimap.Set.Internal.SetMultimap k a)
instance GHC.Classes.Eq k => Data.Functor.Classes.Eq1 (Data.Multimap.Set.Internal.SetMultimap k)
instance Data.Functor.Classes.Eq2 Data.Multimap.Set.Internal.SetMultimap
instance GHC.Classes.Ord k => Data.Functor.Classes.Ord1 (Data.Multimap.Set.Internal.SetMultimap k)
instance Data.Functor.Classes.Ord2 Data.Multimap.Set.Internal.SetMultimap
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.Multimap.Set.Internal.SetMultimap k a)
instance GHC.Show.Show k => Data.Functor.Classes.Show1 (Data.Multimap.Set.Internal.SetMultimap k)
instance Data.Functor.Classes.Show2 Data.Multimap.Set.Internal.SetMultimap
instance (GHC.Classes.Ord k, GHC.Classes.Ord a, GHC.Read.Read k, GHC.Read.Read a) => GHC.Read.Read (Data.Multimap.Set.Internal.SetMultimap k a)
instance Data.Foldable.Foldable (Data.Multimap.Set.Internal.SetMultimap k)
instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Base.Semigroup (Data.Multimap.Set.Internal.SetMultimap k a)
instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Base.Monoid (Data.Multimap.Set.Internal.SetMultimap k a)
-- | Conversions between Multimap and SetMultimap.
module Data.Multimap.Conversions
-- | Convert a SetMultimap to a Multimap where the values of
-- each key are in ascending order.
--
--
-- toMultimapAsc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]
--
toMultimapAsc :: SetMultimap k a -> Multimap k a
-- | Convert a SetMultimap to a Multimap where the values of
-- each key are in descending order.
--
--
-- toMultimapDesc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'b'),(1,'a'),(2,'c')]
--
toMultimapDesc :: SetMultimap k a -> Multimap k a
-- | Convert a Multimap to a SetMultimap.
--
--
-- toSetMultimap (Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]
--
toSetMultimap :: Ord a => Multimap k a -> SetMultimap k a
-- | Multimaps, where values behave like (non empty) sets.
--
-- Multimaps whose values behave like lists are in Data.Multimap.
-- Multimaps whose values behave like maps (i.e., two-dimensional tables)
-- are in Data.Multimap.Table.
--
-- The implementation is backed by a Map k (Set
-- a). The differences between Multimap k a and
-- Map k (Set a) include:
--
--
-- - A key is only present in a SetMultimap if it is associated
-- with at least one values, i.e., a key is never associated with an
-- empty set of values.
-- - lookup (or !) returns a possibly empty set. Unlike
-- regular maps, the ! operator is total for multimaps.
-- - Functions like map, adjust, update, etc.,
-- take functions on individual values (e.g., a -> b) as
-- opposed to, e.g., Set a -> Set b.
-- - union and unions union the values when there are
-- duplicate keys, rather than being left- or right-biased.
-- - The difference function computes set differences for values
-- of keys that exist in both maps.
-- - The size function returns the total number of values for
-- all keys in the multimap, not the number of distinct keys. The latter
-- can be obtained by first getting the keysSet or first
-- converting the multimap to a regular map via toMap.
--
--
-- In the following Big-O notations, unless otherwise noted, n
-- denotes the size of the multimap, k denotes the number of
-- distinct keys, and m denotes the maximum number of values
-- associated with a single key.
module Data.Multimap.Set
data SetMultimap k a
-- | O(1). The empty multimap.
--
--
-- size empty === 0
--
empty :: SetMultimap k a
-- | O(1). A multimap with a single element.
--
--
-- singleton 1 'a' === fromList [(1, 'a')]
-- size (singleton 1 'a') === 1
--
singleton :: k -> a -> SetMultimap k a
-- | O(k). A key is retained only if it is associated with a
-- non-empty set of values.
fromMap :: Map k (Set a) -> SetMultimap k a
-- | O(n*log n) where n is the length of the input list.
-- Build a multimap from a list of key/value pairs.
--
--
-- fromList ([] :: [(Int, Char)]) === empty
-- fromList [(1, 'b'), (2, 'a'), (1, 'b')] === fromList [(1, 'b'), (2, 'a')]
--
fromList :: (Ord k, Ord a) => [(k, a)] -> SetMultimap k a
-- | O(log m * log k). If the key exists in the multimap, the new
-- value will be inserted into the set of values for the key. It is a
-- no-op if the value already exists in the set.
--
--
-- insert 1 'a' empty === singleton 1 'a'
-- insert 1 'a' (fromList [(1, 'b'), (2, 'a')]) === fromList [(1, 'a'), (1, 'b'), (2, 'a')]
-- insert 1 'a' (fromList [(1, 'a'), (2, 'c')]) === fromList [(1, 'a'), (2, 'c')]
--
insert :: (Ord k, Ord a) => k -> a -> SetMultimap k a -> SetMultimap k a
-- | O(log k). Delete a key and all its values from the map.
--
--
-- delete 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === singleton 2 'c'
--
delete :: Ord k => k -> SetMultimap k a -> SetMultimap k a
-- | O(log m * log k). Remove the first occurrence of the value
-- associated with the key, if exists.
--
--
-- deleteWithValue 1 'c' (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- deleteWithValue 1 'c' (fromList [(2,'c'),(1,'c')]) === singleton 2 'c'
--
deleteWithValue :: (Ord k, Ord a) => k -> a -> SetMultimap k a -> SetMultimap k a
-- | O(log m * log k). Remove the maximal value associated with the
-- key, if exists.
--
--
-- deleteMax 3 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- deleteMax 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(2,'c')]
--
deleteMax :: Ord k => k -> SetMultimap k a -> SetMultimap k a
-- | O(log m * log k). Remove the minimal value associated with the
-- key, if exists.
--
--
-- deleteMin 3 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'a'),(1,'b'),(2,'c')]
-- deleteMin 1 (fromList [(1,'a'),(1,'b'),(2,'c')]) === fromList [(1,'b'),(2,'c')]
--
deleteMin :: Ord k => k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function a -> a
-- takes O(1). Update values at a specific key, if exists.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- adjust ("new " ++) 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(1,"new b"),(2,"c")]
-- adjust (const "z") 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"z"),(2,"c")]
--
adjust :: (Ord k, Ord a) => (a -> a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function k -> a ->
-- a takes O(1). Update values at a specific key, if exists.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- adjustWithKey (\k x -> show k ++ ":new " ++ x) 1 (fromList [(1,"a"),(1,"b"),(2,"c")])
-- === fromList [(1,"1:new a"),(1,"1:new b"),(2,"c")]
--
adjustWithKey :: (Ord k, Ord a) => (k -> a -> a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function a ->
-- Maybe a takes O(1). The expression
-- (update f k map) updates the values at key k,
-- if exists. If f returns Nothing for a value, the value
-- is deleted.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing in do
-- update f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(2, "c")]
-- update f 1 (fromList [(1,"b"),(1,"c"),(2,"c")]) === singleton 2 "c"
--
update :: (Ord k, Ord a) => (a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(m * log m * log k), assuming the function k -> a ->
-- Maybe a takes O(1). The expression
-- (updateWithKey f k map) updates the values at key
-- k, if exists. If f returns Nothing for a
-- value, the value is deleted.
--
--
-- let f k x = if x == "a" then Just (show k ++ ":new a") else Nothing in do
-- updateWithKey f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"1:new a"),(2,"c")]
-- updateWithKey f 1 (fromList [(1,"b"),(1,"c"),(2,"c")]) === singleton 2 "c"
--
updateWithKey :: (Ord k, Ord a) => (k -> a -> Maybe a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(log k), assuming the function Set a ->
-- Set a takes O(1). The expression (alter
-- f k map) alters the values at k, if exists.
--
--
-- let (f, g) = (const Set.empty, Set.insert 'c') in do
-- alter f 1 (fromList [(1, 'a'), (2, 'b')]) === singleton 2 'b'
-- alter f 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b')]
-- alter g 1 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'c'), (1, 'a'), (2, 'b')]
-- alter g 1 (fromList [(1, 'c'), (2, 'b')]) === fromList [(1, 'c'), (2, 'b')]
-- alter g 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b'), (3, 'c')]
--
alter :: Ord k => (Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(log k), assuming the function k -> Set a ->
-- Set a takes O(1). The expression
-- (alterWithKey f k map) alters the values at k, if
-- exists.
--
--
-- let (f, g) = (const (const Set.empty), Set.insert . show) in do
-- alterWithKey f 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
-- alterWithKey f 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b")]
-- alterWithKey g 1 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "1"), (1, "a"), (2, "b")]
-- alterWithKey g 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b"), (3, "3")]
--
alterWithKey :: Ord k => (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k a
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty set if the key is not in the map.
lookup :: Ord k => k -> SetMultimap k a -> Set a
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty set if the key is not in the map.
--
--
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 3 === Set.fromList "ac"
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 2 === Set.empty
--
(!) :: Ord k => SetMultimap k a -> k -> Set a
infixl 9 !
-- | O(log k). Is the key a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- member 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === True
-- member 1 (deleteMax 1 (fromList [(2, 'c'), (1, 'c')])) === False
--
member :: Ord k => k -> SetMultimap k a -> Bool
-- | O(log k). Is the key not a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- notMember 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === False
-- notMember 1 (deleteMin 1 (fromList [(2, 'c'), (1, 'c')])) === True
--
notMember :: Ord k => k -> SetMultimap k a -> Bool
-- | O(1). Is the multimap empty?
--
--
-- Data.Multimap.Set.null empty === True
-- Data.Multimap.Set.null (singleton 1 'a') === False
--
null :: SetMultimap k a -> Bool
-- | O(1). Is the multimap non-empty?
--
--
-- notNull empty === False
-- notNull (singleton 1 'a') === True
--
notNull :: SetMultimap k a -> Bool
-- | The total number of values for all keys.
--
-- size is evaluated lazily. Forcing the size for the first time
-- takes up to O(k) and subsequent forces take O(1).
--
--
-- size empty === 0
-- size (singleton 1 'a') === 1
-- size (fromList [(1, 'a'), (2, 'b'), (2, 'c'), (2, 'b')]) === 3
--
size :: SetMultimap k a -> Int
-- | Union two multimaps, unioning values for duplicate keys.
--
--
-- union (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b')])
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c')]
--
union :: (Ord k, Ord a) => SetMultimap k a -> SetMultimap k a -> SetMultimap k a
-- | Union a number of multimaps, unioning values for duplicate keys.
--
--
-- unions [fromList [(1,'a'),(2,'b'),(2,'c')], fromList [(1,'d'),(2,'b')]]
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c')]
--
unions :: (Foldable f, Ord k, Ord a) => f (SetMultimap k a) -> SetMultimap k a
-- | Difference of two multimaps.
--
-- If a key exists in the first multimap but not the second, it remains
-- unchanged in the result. If a key exists in both multimaps, a set
-- difference is performed on their values.
--
--
-- difference (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b'),(2,'a')])
-- === fromList [(1,'a'),(2,'c')]
--
difference :: (Ord k, Ord a) => SetMultimap k a -> SetMultimap k a -> SetMultimap k a
-- | O(n * log m), assuming the function a -> b takes
-- O(1). Map a function over all values in the map.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- Data.Multimap.Set.map (++ "x") (fromList [(1,"a"),(2,"b")]) === fromList [(1,"ax"),(2,"bx")]
-- Data.Multimap.Set.map (const "c") (fromList [(1,"a"),(1,"b"),(2,"b")]) === fromList [(1,"c"),(2,"c")]
--
map :: Ord b => (a -> b) -> SetMultimap k a -> SetMultimap k b
-- | O(n * log m), assuming the function k -> a -> b
-- takes O(1). Map a function over all values in the map.
--
-- Since values are sets, the result may be smaller than the original
-- multimap.
--
--
-- mapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1,"a"),(2,"b")]) === fromList [(1,"1:a"),(2,"2:b")]
--
mapWithKey :: Ord b => (k -> a -> b) -> SetMultimap k a -> SetMultimap k b
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator.
--
--
-- Data.Multimap.Set.foldr ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr :: (a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator.
--
--
-- Data.Multimap.Set.foldl (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl :: (a -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- right-associative binary operator.
--
--
-- foldrWithKey (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). Fold the key/value pairs in the map using the given
-- left-associative binary operator.
--
--
-- foldlWithKey (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- monoid.
--
--
-- foldMapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1, "a"), (1, "c"), (2, "b")]) === "1:a1:c2:b"
--
foldMapWithKey :: Monoid m => (k -> a -> m) -> SetMultimap k a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Set.foldr' ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr' :: (a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Set.foldl' (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl' :: (a -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldrWithKey' (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey' :: (k -> a -> b -> b) -> b -> SetMultimap k a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldlWithKey' (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey' :: (a -> k -> b -> a) -> a -> SetMultimap k b -> a
-- | O(n). Return all elements of the multimap in ascending order of
-- their keys. Elements of each key appear in ascending order.
--
--
-- elems (fromList [(2,'a'),(1,'b'),(3,'d'),(3,'c'),(1,'b')]) === "bacd"
-- elems (empty :: SetMultimap Int Char) === []
--
elems :: SetMultimap k a -> [a]
-- | O(k). Return all keys of the multimap in ascending order.
--
--
-- keys (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'b')]) === [1,2,3]
-- keys (empty :: SetMultimap Int Char) === []
--
keys :: SetMultimap k a -> [k]
-- | An alias for toAscList.
assocs :: SetMultimap k a -> [(k, a)]
-- | O(k). The set of all keys of the multimap.
--
--
-- keysSet (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'b')]) === Set.fromList [1,2,3]
-- keysSet (empty :: SetMultimap Int Char) === Set.empty
--
keysSet :: SetMultimap k a -> Set k
-- | Convert the multimap into a list of key/value pairs.
--
--
-- toList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'a'),(1,'b'),(2,'a'),(3,'c')]
--
toList :: SetMultimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in ascending order
-- of keys. Elements of each key appear in ascending order.
--
--
-- toAscList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'a'),(1,'b'),(2,'a'),(3,'c')]
--
toAscList :: SetMultimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in descending
-- order of keys. Elements of each key appear in descending order.
--
--
-- toDescList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(3,'c'),(2,'a'),(1,'b'),(1,'a')]
--
toDescList :: SetMultimap k a -> [(k, a)]
-- | O(1). Convert the multimap into a regular map.
toMap :: SetMultimap k a -> Map k (Set a)
-- | Convert a Multimap to a SetMultimap.
--
--
-- fromMultimap (Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]
--
fromMultimap :: Ord a => Multimap k a -> SetMultimap k a
-- | Convert a SetMultimap to a Multimap where the values of
-- each key are in ascending order.
--
--
-- toMultimapAsc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]
--
toMultimapAsc :: SetMultimap k a -> Multimap k a
-- | Convert a SetMultimap to a Multimap where the values of
-- each key are in descending order.
--
--
-- toMultimapDesc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'b'),(1,'a'),(2,'c')]
--
toMultimapDesc :: SetMultimap k a -> Multimap k a
-- | O(n), assuming the predicate function takes O(1). Retain
-- all values that satisfy the predicate. A key is removed if none of its
-- values satisfies the predicate.
--
--
-- Data.Multimap.Set.filter (> 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 1 'b'
-- Data.Multimap.Set.filter (< 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === empty
--
filter :: (a -> Bool) -> SetMultimap k a -> SetMultimap k a
-- | O(n), assuming the predicate function takes O(1). Retain
-- all key/value pairs that satisfy the predicate. A key is removed if
-- none of its values satisfies the predicate.
--
--
-- filterWithKey (\k a -> even k && a > 'a') (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'b')]) === singleton 2 'b'
--
filterWithKey :: (k -> a -> Bool) -> SetMultimap k a -> SetMultimap k a
-- | O(k), assuming the predicate function takes O(1). Retain
-- all keys that satisfy the predicate.
filterKey :: (k -> Bool) -> SetMultimap k a -> SetMultimap k a
-- | Generalized filter.
--
--
-- let f a | a > 'b' = Just True
-- | a < 'b' = Just False
-- | a == 'b' = Nothing
-- in do
-- filterM f (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c')]) === Nothing
-- filterM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Just (fromList [(1,'c'),(2,'c')])
--
filterM :: (Ord k, Ord a, Applicative t) => (a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
-- | Generalized filterWithKey. | Generalized filterWithKey.
--
--
-- let f k a | even k && a > 'b' = Just True
-- | odd k && a < 'b' = Just False
-- | otherwise = Nothing
-- in do
-- filterWithKeyM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Nothing
-- filterWithKeyM f (fromList [(1,'a'),(3,'a'),(2,'c'),(4,'c')]) === Just (fromList [(2,'c'),(4,'c')])
--
filterWithKeyM :: (Ord k, Ord a, Applicative t) => (k -> a -> t Bool) -> SetMultimap k a -> t (SetMultimap k a)
-- | O(n * log m), assuming the function a -> Maybe
-- b takes O(1). Map values and collect the Just
-- results.
--
--
-- mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === fromList [(1,"new a"),(2,"new a")]
--
mapMaybe :: Ord b => (a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
-- | O(n * log m), assuming the function k -> a ->
-- Maybe b takes O(1). Map key/value pairs and collect
-- the Just results.
--
--
-- mapMaybeWithKey (\k a -> if k > 1 && a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === singleton 2 "new a"
--
mapMaybeWithKey :: Ord b => (k -> a -> Maybe b) -> SetMultimap k a -> SetMultimap k b
-- | O(n * log m), assuming the function a -> Either b
-- c takes O(1). Map values and separate the Left and
-- Right results.
--
--
-- mapEither (\a -> if a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(1,'a'),(2,'a')],fromList [(1,'c'),(2,'c')])
--
mapEither :: (Ord b, Ord c) => (a -> Either b c) -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
-- | O(n * log m), assuming the function k -> a ->
-- Either b c takes O(1). Map key/value pairs and
-- separate the Left and Right results.
--
--
-- mapEitherWithKey (\k a -> if even k && a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(2,'a')],fromList [(1,'a'),(1,'c'),(2,'c')])
--
mapEitherWithKey :: (Ord b, Ord c) => (k -> a -> Either b c) -> SetMultimap k a -> (SetMultimap k b, SetMultimap k c)
-- | O(log n). Return the smallest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMin (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (1, Set.fromList "ac")
-- lookupMin (empty :: SetMultimap Int Char) === Nothing
--
lookupMin :: SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the largest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMax (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (2, Set.fromList "c")
-- lookupMax (empty :: SetMultimap Int Char) === Nothing
--
lookupMax :: SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the largest key smaller than the given one,
-- and the associated values, if exist.
--
--
-- lookupLT 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLT 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupLT :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the smallest key larger than the given one,
-- and the associated values, if exist.
--
--
-- lookupGT 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGT 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupGT :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the largest key smaller than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupLE 0 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLE 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (1, Set.fromList "a")
-- lookupLE 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupLE :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | O(log n). Return the smallest key larger than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupGE 6 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGE 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (5, Set.fromList "c")
-- lookupGE 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, Set.fromList "bc")
--
lookupGE :: Ord k => k -> SetMultimap k a -> Maybe (k, Set a)
-- | Multimaps, where values behave like (non empty) lists.
--
-- Multimaps whose values behave like sets are in
-- Data.Multimap.Set. Multimaps whose values behave like maps
-- (i.e., two-dimensional tables) are in Data.Multimap.Table.
--
-- The implementation is backed by a Map k
-- (NonEmpty a). The differences between
-- Multimap k a and Map k (NonEmpty
-- a) include:
--
--
-- - lookup (or !) returns a possibly empty list. Unlike
-- regular maps, the ! operator is total for multimaps.
-- - Functions like map, adjust, traverse, etc.,
-- take functions on individual values (e.g., a -> b) as
-- opposed to, e.g., NonEmpty a -> NonEmpty
-- b.
-- - union and unions concatenate the values when there
-- are duplicate keys, rather than being left- or right-biased.
-- - The difference function computes list differences for
-- values of keys that exist in both maps.
-- - The size function returns the total number of values for
-- all keys in the multimap, not the number of distinct keys. The latter
-- can be obtained by first getting the keysSet or first
-- converting the multimap to a regular map via toMap.
--
--
-- In the following Big-O notations, unless otherwise noted, n
-- denotes the size of the multimap, k denotes the number of
-- distinct keys, and m denotes the maximum number of values
-- associated with a single key.
module Data.Multimap
data Multimap k a
-- | O(1). The empty multimap.
--
--
-- size empty === 0
--
empty :: Multimap k a
-- | O(1). A multimap with a single element.
--
--
-- singleton 1 'a' === fromList [(1, 'a')]
-- size (singleton 1 'a') === 1
--
singleton :: k -> a -> Multimap k a
-- | O(1).
fromMap :: Map k (NonEmpty a) -> Multimap k a
-- | O(k). A key is retained only if it is associated with a
-- non-empty list of values.
--
--
-- fromMap' (Map.fromList [(1, "ab"), (2, ""), (3, "c")]) === fromList [(1, 'a'), (1, 'b'), (3, 'c')]
--
fromMap' :: Map k [a] -> Multimap k a
-- | O(n*log n) where n is the length of the input list.
-- Build a multimap from a list of key/value pairs.
--
--
-- fromList ([] :: [(Int, Char)]) === empty
--
fromList :: Ord k => [(k, a)] -> Multimap k a
-- | O(log k). If the key exists in the multimap, the new value will
-- be prepended to the list of values for the key.
--
--
-- insert 1 'a' empty === singleton 1 'a'
-- insert 1 'a' (fromList [(2, 'b'), (2, 'c')]) === fromList [(1, 'a'), (2, 'b'), (2, 'c')]
-- insert 1 'a' (fromList [(1, 'b'), (2, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
--
insert :: Ord k => k -> a -> Multimap k a -> Multimap k a
-- | O(log k). Delete a key and all its values from the map.
--
--
-- delete 1 (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === singleton 2 'c'
--
delete :: Ord k => k -> Multimap k a -> Multimap k a
-- | O(m*log k). Remove the first occurrence of the value associated
-- with the key, if exists.
--
--
-- deleteWithValue 1 'c' (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
-- deleteWithValue 1 'c' (fromList [(1, 'a'), (1, 'b'), (2, 'c'), (1, 'c')]) === fromList [(1, 'a'), (1, 'b'), (2, 'c')]
-- deleteWithValue 1 'c' (fromList [(2, 'c'), (1, 'c')]) === singleton 2 'c'
--
deleteWithValue :: (Ord k, Eq a) => k -> a -> Multimap k a -> Multimap k a
-- | O(log k). Remove the first value associated with the key. If
-- the key is associated with a single value, the key will be removed
-- from the multimap.
--
--
-- deleteOne 1 (fromList [(1, 'a'), (1, 'b'), (2, 'c')]) === fromList [(1, 'b'), (2, 'c')]
-- deleteOne 1 (fromList [(2, 'c'), (1, 'c')]) === singleton 2 'c'
--
deleteOne :: Ord k => k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function a -> a takes
-- O(1). Update values at a specific key, if exists.
--
--
-- adjust ("new " ++) 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"new a"),(1,"new b"),(2,"c")]
--
adjust :: Ord k => (a -> a) -> k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function k -> a -> a
-- takes O(1). Update values at a specific key, if exists.
--
--
-- adjustWithKey (\k x -> show k ++ ":new " ++ x) 1 (fromList [(1,"a"),(1,"b"),(2,"c")])
-- === fromList [(1,"1:new a"),(1,"1:new b"),(2,"c")]
--
adjustWithKey :: Ord k => (k -> a -> a) -> k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function a -> Maybe
-- a takes O(1). The expression (update f k
-- map) updates the values at key k, if exists. If
-- f returns Nothing for a value, the value is deleted.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing in do
-- update f 1 (fromList [(1,"a"),(1, "b"),(2,"c")]) === fromList [(1,"new a"),(2, "c")]
-- update f 1 (fromList [(1,"b"),(1, "b"),(2,"c")]) === singleton 2 "c"
--
update :: Ord k => (a -> Maybe a) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function NonEmpty a ->
-- [a] takes O(1). The expression (update f k
-- map) updates the values at key k, if exists. If
-- f returns Nothing, the key is deleted.
--
--
-- update' NonEmpty.tail 1 (fromList [(1, "a"), (1, "b"), (2, "c")]) === fromList [(1, "b"), (2, "c")]
-- update' NonEmpty.tail 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
--
update' :: Ord k => (NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(m*log k), assuming the function k -> a ->
-- Maybe a takes O(1). The expression
-- (updateWithKey f k map) updates the values at key
-- k, if exists. If f returns Nothing for a
-- value, the value is deleted.
--
--
-- let f k x = if x == "a" then Just (show k ++ ":new a") else Nothing in do
-- updateWithKey f 1 (fromList [(1,"a"),(1,"b"),(2,"c")]) === fromList [(1,"1:new a"),(2,"c")]
-- updateWithKey f 1 (fromList [(1,"b"),(1,"b"),(2,"c")]) === singleton 2 "c"
--
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function k -> NonEmpty a
-- -> [a] takes O(1). The expression (update f
-- k map) updates the values at key k, if exists. If
-- f returns Nothing, the key is deleted.
--
--
-- let f k xs = if NonEmpty.length xs == 1 then (show k : NonEmpty.toList xs) else [] in do
-- updateWithKey' f 1 (fromList [(1, "a"), (1, "b"), (2, "c")]) === singleton 2 "c"
-- updateWithKey' f 1 (fromList [(1, "a"), (2, "b"), (2, "c")]) === fromList [(1, "1"), (1, "a"), (2, "b"), (2, "c")]
--
updateWithKey' :: Ord k => (k -> NonEmpty a -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function [a] -> [a] takes
-- O(1). The expression (alter f k map) alters the
-- values at k, if exists.
--
--
-- let (f, g) = (const [], ('c':)) in do
-- alter f 1 (fromList [(1, 'a'), (2, 'b')]) === singleton 2 'b'
-- alter f 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b')]
-- alter g 1 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'c'), (1, 'a'), (2, 'b')]
-- alter g 3 (fromList [(1, 'a'), (2, 'b')]) === fromList [(1, 'a'), (2, 'b'), (3, 'c')]
--
alter :: Ord k => ([a] -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(log k), assuming the function k -> [a] -> [a]
-- takes O(1). The expression (alterWithKey f k
-- map) alters the values at k, if exists.
--
--
-- let (f, g) = (const (const []), (:) . show) in do
-- alterWithKey f 1 (fromList [(1, "a"), (2, "b")]) === singleton 2 "b"
-- alterWithKey f 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b")]
-- alterWithKey g 1 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "1"), (1, "a"), (2, "b")]
-- alterWithKey g 3 (fromList [(1, "a"), (2, "b")]) === fromList [(1, "a"), (2, "b"), (3, "3")]
--
alterWithKey :: Ord k => (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k a
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty list if the key is not in the map.
lookup :: Ord k => k -> Multimap k a -> [a]
-- | O(log k). Lookup the values at a key in the map. It returns an
-- empty list if the key is not in the map.
--
--
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 3 === "ac"
-- fromList [(3, 'a'), (5, 'b'), (3, 'c')] ! 2 === []
--
(!) :: Ord k => Multimap k a -> k -> [a]
infixl 9 !
-- | O(log k). Is the key a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- member 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === True
-- member 1 (deleteOne 1 (fromList [(2, 'c'), (1, 'c')])) === False
--
member :: Ord k => k -> Multimap k a -> Bool
-- | O(log k). Is the key not a member of the map?
--
-- A key is a member of the map if and only if there is at least one
-- value associated with it.
--
--
-- notMember 1 (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === False
-- notMember 1 (deleteOne 1 (fromList [(2, 'c'), (1, 'c')])) === True
--
notMember :: Ord k => k -> Multimap k a -> Bool
-- | O(1). Is the multimap empty?
--
--
-- Data.Multimap.null empty === True
-- Data.Multimap.null (singleton 1 'a') === False
--
null :: Multimap k a -> Bool
-- | O(1). Is the multimap non-empty?
--
--
-- notNull empty === False
-- notNull (singleton 1 'a') === True
--
notNull :: Multimap k a -> Bool
-- | The total number of values for all keys.
--
-- size is evaluated lazily. Forcing the size for the first time
-- takes up to O(n) and subsequent forces take O(1).
--
--
-- size empty === 0
-- size (singleton 1 'a') === 1
-- size (fromList [(1, 'a'), (2, 'b'), (2, 'c')]) === 3
--
size :: Multimap k a -> Int
-- | Union two multimaps, concatenating values for duplicate keys.
--
--
-- union (fromList [(1,'a'),(2,'b'),(2,'c')]) (fromList [(1,'d'),(2,'b')])
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c'),(2,'b')]
--
union :: Ord k => Multimap k a -> Multimap k a -> Multimap k a
-- | Union a number of multimaps, concatenating values for duplicate keys.
--
--
-- unions [fromList [(1,'a'),(2,'b'),(2,'c')], fromList [(1,'d'),(2,'b')]]
-- === fromList [(1,'a'),(1,'d'),(2,'b'),(2,'c'),(2,'b')]
--
unions :: (Foldable f, Ord k) => f (Multimap k a) -> Multimap k a
-- | Difference of two multimaps.
--
-- If a key exists in the first multimap but not the second, it remains
-- unchanged in the result. If a key exists in both multimaps, a list
-- difference is performed on their values, i.e., the first occurrence of
-- each value in the second multimap is removed from the first multimap.
--
--
-- difference (fromList [(1,'a'),(2,'b'),(2,'c'),(2,'b')]) (fromList [(1,'d'),(2,'b'),(2,'a')])
-- === fromList [(1,'a'), (2,'c'), (2,'b')]
--
difference :: (Ord k, Eq a) => Multimap k a -> Multimap k a -> Multimap k a
-- | O(n), assuming the function a -> b takes
-- O(1). Map a function over all values in the map.
--
--
-- Data.Multimap.map (++ "x") (fromList [(1,"a"),(1,"a"),(2,"b")]) === fromList [(1,"ax"),(1,"ax"),(2,"bx")]
--
map :: (a -> b) -> Multimap k a -> Multimap k b
-- | O(n), assuming the function k -> a -> b takes
-- O(1). Map a function over all key/value pairs in the map.
--
--
-- mapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1,"a"),(1,"a"),(2,"b")]) === fromList [(1,"1:a"),(1,"1:a"),(2,"2:b")]
--
mapWithKey :: (k -> a -> b) -> Multimap k a -> Multimap k b
-- | Traverse key/value pairs and collect the results.
--
--
-- let f k a = if odd k then Just (succ a) else Nothing in do
-- traverseWithKey f (fromList [(1, 'a'), (1, 'b'), (3, 'b'), (3, 'c')]) === Just (fromList [(1, 'b'), (1, 'c'), (3, 'c'), (3, 'd')])
-- traverseWithKey f (fromList [(1, 'a'), (1, 'b'), (2, 'b')]) === Nothing
--
traverseWithKey :: Applicative t => (k -> a -> t b) -> Multimap k a -> t (Multimap k b)
-- | Traverse key/value pairs and collect the Just results.
traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> Multimap k a -> t (Multimap k b)
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator.
--
--
-- Data.Multimap.foldr ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr :: (a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator.
--
--
-- Data.Multimap.foldl (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl :: (a -> b -> a) -> a -> Multimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- right-associative binary operator.
--
--
-- foldrWithKey (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey :: (k -> a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). Fold the key/value pairs in the map using the given
-- left-associative binary operator.
--
--
-- foldlWithKey (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey :: (a -> k -> b -> a) -> a -> Multimap k b -> a
-- | O(n). Fold the key/value pairs in the map using the given
-- monoid.
--
--
-- foldMapWithKey (\k x -> show k ++ ":" ++ x) (fromList [(1, "a"), (1, "a"), (2, "b")]) === "1:a1:a2:b"
--
foldMapWithKey :: Monoid m => (k -> a -> m) -> Multimap k a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.foldr' ((+) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldr' :: (a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.foldl' (\len -> (+ len) . length) 0 (fromList [(1, "hello"), (1, "world"), (2, "!")]) === 11
--
foldl' :: (a -> b -> a) -> a -> Multimap k b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldrWithKey' (\k a len -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldrWithKey' :: (k -> a -> b -> b) -> b -> Multimap k a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
--
--
-- foldlWithKey' (\len k a -> length (show k) + length a + len) 0 (fromList [(1, "hello"), (1, "world"), (20, "!")]) === 15
--
foldlWithKey' :: (a -> k -> b -> a) -> a -> Multimap k b -> a
-- | O(n). Return all elements of the multimap in ascending order of
-- their keys.
--
--
-- elems (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === "bbac"
-- elems (empty :: Multimap Int Char) === []
--
elems :: Multimap k a -> [a]
-- | O(k). Return all keys of the multimap in ascending order.
--
--
-- keys (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === [1,2,3]
-- keys (empty :: Multimap Int Char) === []
--
keys :: Multimap k a -> [k]
-- | An alias for toAscList.
--
--
-- assocs (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
--
assocs :: Multimap k a -> [(k, a)]
-- | O(k). The set of all keys of the multimap.
--
--
-- keysSet (fromList [(2, 'a'), (1, 'b'), (3, 'c'), (1, 'b')]) === Set.fromList [1,2,3]
-- keysSet (empty :: Multimap Int Char) === Set.empty
--
keysSet :: Multimap k a -> Set k
-- | Convert the multimap into a list of key/value pairs.
--
--
-- toList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
--
toList :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in ascending order
-- of keys.
--
--
-- toAscList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(1,'b'),(1,'a'),(2,'a'),(3,'c')]
--
toAscList :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs in descending
-- order of keys.
--
--
-- toDescList (fromList [(2,'a'),(1,'b'),(3,'c'),(1,'a')]) === [(3,'c'),(2,'a'),(1,'b'),(1,'a')]
--
toDescList :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs, in a
-- breadth-first manner, in ascending order of keys.
--
--
-- toAscListBF (fromList [("Foo",1),("Foo",2),("Foo",3),("Bar",4),("Bar",5),("Baz",6)])
-- === [("Bar",4),("Baz",6),("Foo",1),("Bar",5),("Foo",2),("Foo",3)]
--
toAscListBF :: Multimap k a -> [(k, a)]
-- | Convert the multimap into a list of key/value pairs, in a
-- breadth-first manner, in descending order of keys.
--
--
-- toDescListBF (fromList [("Foo",1),("Foo",2),("Foo",3),("Bar",4),("Bar",5),("Baz",6)])
-- === [("Foo",1),("Baz",6),("Bar",4),("Foo",2),("Bar",5),("Foo",3)]
--
toDescListBF :: Multimap k a -> [(k, a)]
-- | O(1). Convert the multimap into a regular map.
toMap :: Multimap k a -> Map k (NonEmpty a)
-- | Convert a SetMultimap to a Multimap where the values of
-- each key are in ascending order.
--
--
-- fromSetMultimapAsc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]
--
fromSetMultimapAsc :: SetMultimap k a -> Multimap k a
-- | Convert a SetMultimap to a Multimap where the values of
-- each key are in descending order.
--
--
-- fromSetMultimapDesc (Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.fromList [(1,'b'),(1,'a'),(2,'c')]
--
fromSetMultimapDesc :: SetMultimap k a -> Multimap k a
-- | Convert a Multimap to a SetMultimap.
--
--
-- toSetMultimap (Data.Multimap.fromList [(1,'a'),(1,'b'),(2,'c')]) === Data.Multimap.Set.fromList [(1,'a'),(1,'b'),(2,'c')]
--
toSetMultimap :: Ord a => Multimap k a -> SetMultimap k a
-- | O(n), assuming the predicate function takes O(1). Retain
-- all values that satisfy the predicate.
--
--
-- Data.Multimap.filter (> 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 1 'b'
-- Data.Multimap.filter (< 'a') (fromList [(1,'a'),(1,'b'),(2,'a')]) === empty
--
filter :: (a -> Bool) -> Multimap k a -> Multimap k a
-- | O(n), assuming the predicate function takes O(1). Retain
-- all key/value pairs that satisfy the predicate.
--
--
-- filterWithKey (\k a -> even k && a > 'a') (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'b')]) === singleton 2 'b'
--
filterWithKey :: (k -> a -> Bool) -> Multimap k a -> Multimap k a
-- | O(k), assuming the predicate function takes O(1). Retain
-- all keys that satisfy the predicate.
--
--
-- filterKey even (fromList [(1,'a'),(1,'b'),(2,'a')]) === singleton 2 'a'
--
filterKey :: (k -> Bool) -> Multimap k a -> Multimap k a
-- | Generalized filter.
--
--
-- let f a | a > 'b' = Just True
-- | a < 'b' = Just False
-- | a == 'b' = Nothing
-- in do
-- filterM f (fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c')]) === Nothing
-- filterM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Just (fromList [(1,'c'),(2,'c')])
--
filterM :: (Ord k, Applicative t) => (a -> t Bool) -> Multimap k a -> t (Multimap k a)
-- | Generalized filterWithKey.
--
--
-- let f k a | even k && a > 'b' = Just True
-- | odd k && a < 'b' = Just False
-- | otherwise = Nothing
-- in do
-- filterWithKeyM f (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')]) === Nothing
-- filterWithKeyM f (fromList [(1,'a'),(1,'a'),(2,'c'),(2,'c')]) === Just (fromList [(2,'c'),(2,'c')])
--
filterWithKeyM :: (Ord k, Applicative t) => (k -> a -> t Bool) -> Multimap k a -> t (Multimap k a)
-- | O(n), assuming the function a -> Maybe b
-- takes O(1). Map values and collect the Just results.
--
--
-- mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === fromList [(1,"new a"),(2,"new a")]
--
mapMaybe :: (a -> Maybe b) -> Multimap k a -> Multimap k b
-- | O(n), assuming the function k -> a -> Maybe
-- b takes O(1). Map key/value pairs and collect the
-- Just results.
--
--
-- mapMaybeWithKey (\k a -> if k > 1 && a == "a" then Just "new a" else Nothing) (fromList [(1,"a"),(1,"b"),(2,"a"),(2,"c")])
-- === singleton 2 "new a"
--
mapMaybeWithKey :: (k -> a -> Maybe b) -> Multimap k a -> Multimap k b
-- | O(n), assuming the function a -> Either b c
-- takes O(1). Map values and separate the Left and
-- Right results.
--
--
-- mapEither (\a -> if a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(1,'a'),(2,'a')],fromList [(1,'c'),(2,'c')])
--
mapEither :: (a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
-- | O(n), assuming the function k -> a -> Either b
-- c takes O(1). Map key/value pairs and separate the
-- Left and Right results.
--
--
-- mapEitherWithKey (\k a -> if even k && a < 'b' then Left a else Right a) (fromList [(1,'a'),(1,'c'),(2,'a'),(2,'c')])
-- === (fromList [(2,'a')],fromList [(1,'a'),(1,'c'),(2,'c')])
--
mapEitherWithKey :: (k -> a -> Either b c) -> Multimap k a -> (Multimap k b, Multimap k c)
-- | O(log n). Return the smallest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMin (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (1, NonEmpty.fromList "ac")
-- lookupMin (empty :: Multimap Int Char) === Nothing
--
lookupMin :: Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the largest key and the associated values.
-- Returns Nothing if the map is empty.
--
--
-- lookupMax (fromList [(1,'a'),(1,'c'),(2,'c')]) === Just (2, NonEmpty.fromList "c")
-- lookupMax (empty :: Multimap Int Char) === Nothing
--
lookupMax :: Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the largest key smaller than the given one,
-- and the associated values, if exist.
--
--
-- lookupLT 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLT 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupLT :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the smallest key larger than the given one,
-- and the associated values, if exist.
--
--
-- lookupGT 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGT 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupGT :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the largest key smaller than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupLE 0 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupLE 1 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (1, NonEmpty.fromList "a")
-- lookupLE 4 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupLE :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
-- | O(log n). Return the smallest key larger than or equal to the
-- given one, and the associated values, if exist.
--
--
-- lookupGE 6 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Nothing
-- lookupGE 5 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (5, NonEmpty.fromList "c")
-- lookupGE 2 (fromList [(1,'a'),(3,'b'),(3,'c'),(5,'c')]) === Just (3, NonEmpty.fromList "bc")
--
lookupGE :: Ord k => k -> Multimap k a -> Maybe (k, NonEmpty a)
module Data.Multimap.Table.Internal
newtype Table r c a
Table :: (Map r (Map c a), Map c (Map r a), Size) -> Table r c a
type Size = Int
-- | O(1). The empty table.
--
--
-- size empty === 0
--
empty :: Table r c a
-- | O(1). A table with a single element.
--
--
-- singleton 1 'a' "a" === fromList [(1,'a',"a")]
-- size (singleton 1 'a' "a") === 1
--
singleton :: r -> c -> a -> Table r c a
-- | Build a table from a row map.
--
--
-- fromRowMap (Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]), (2, Map.fromList [('a',"d")])])
-- === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
fromRowMap :: (Ord r, Ord c) => Map r (Map c a) -> Table r c a
-- | Build a table from a column map.
--
--
-- fromColumnMap (Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]), (2, Map.fromList [('a',"d")])])
-- === fromList [('a',1,"b"),('a',2,"d"),('b',1,"c")]
--
fromColumnMap :: (Ord r, Ord c) => Map c (Map r a) -> Table r c a
-- | Flip the row and column keys.
--
--
-- transpose (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [('a',1,"b"),('a',2,"d"),('b',1,"c")]
--
transpose :: Table r c a -> Table c r a
-- | Build a table from a list of key/value pairs.
--
--
-- fromList ([] :: [(Int, Char, String)]) === empty
--
fromList :: (Ord r, Ord c) => [(r, c, a)] -> Table r c a
-- | O(log k). Associate with value with the row key and the column
-- key. If the table already contains a value for those keys, the value
-- is replaced.
--
--
-- insert 1 'a' "a" empty === singleton 1 'a' "a"
-- insert 1 'a' "a" (fromList [(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"d")]
-- insert 1 'a' "a" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"d")]
--
insert :: (Ord r, Ord c) => r -> c -> a -> Table r c a -> Table r c a
-- | O(log k). Remove the value associated with the given keys.
--
--
-- delete 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'b',"c"),(2,'a',"d")]
-- delete 1 'a' (fromList [(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'b',"c"),(2,'a',"d")]
--
delete :: (Ord r, Ord c) => r -> c -> Table r c a -> Table r c a
-- | Remove an entire row.
--
--
-- deleteRow 1 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
-- deleteRow 3 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
deleteRow :: Ord r => r -> Table r c a -> Table r c a
-- | Remove an entire column.
--
--
-- deleteColumn 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
-- deleteColumn 'z' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
deleteColumn :: Ord c => c -> Table r c a -> Table r c a
-- | O(log k), assuming the function a -> a takes
-- O(1). Update the value at a specific row key and column key, if
-- exists.
--
--
-- adjust ("new " ++) 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"new b"),(1,'b',"c"),(2,'a',"d")]
--
adjust :: (Ord r, Ord c) => (a -> a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function r -> c -> a ->
-- a takes O(1). Update the value at a specific row key and
-- column key, if exists.
--
--
-- adjustWithKeys (\r c x -> show r ++ ":" ++ show c ++ ":new " ++ x) 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
-- === fromList [(1,'a',"1:'a':new b"),(1,'b',"c"),(2,'a',"d")]
--
adjustWithKeys :: (Ord r, Ord c) => (r -> c -> a -> a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function a -> Maybe a
-- takes O(1). The expression (update f r c table)
-- updates the value at the given row and column keys, if exists. If
-- f returns Nothing, the value associated with those
-- keys, if exists is deleted.
--
--
-- let f x = if x == "b" then Just "new b" else Nothing in do
-- update f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"new b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- update f 1 'a' (fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
update :: (Ord r, Ord c) => (a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function r -> c -> a ->
-- Maybe a takes O(1). The expression
-- (updateWithKeys f r c table) updates the value at the
-- given row and column keys, if exists. If f returns
-- Nothing, the value associated with those keys, if exists is
-- deleted.
--
--
-- let f r c x = if x == "b" then Just (show r ++ ":" ++ show c ++ ":new b") else Nothing in do
-- updateWithKeys f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"1:'a':new b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- updateWithKeys f 1 'a' (fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
updateWithKeys :: (Ord r, Ord c) => (r -> c -> a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function Maybe a ->
-- Maybe a takes O(1). The expression
-- (alter f r c table) alters the value at the given row
-- and column keys, if exists. It can be used to insert, delete or update
-- a value.
--
--
-- let (f,g,h) = (const Nothing, const (Just "hello"), fmap ('z':)) in do
-- alter f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter f 4 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter f 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter g 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"hello"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter g 4 'e' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c"),(4,'e',"hello")]
-- alter h 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"zb"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter h 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
alter :: (Ord r, Ord c) => (Maybe a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function r -> c ->
-- Maybe a -> Maybe a takes O(1). The
-- expression (alterWithKeys f r c table) alters the
-- value at the given row and column keys, if exists. It can be used to
-- insert, delete or update a value.
--
--
-- let (f,g) = (\_ _ _ -> Nothing, \r c -> fmap ((show r ++ ":" ++ show c ++ ":") ++)) in do
-- alterWithKeys f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys f 4 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys f 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys g 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"1:'a':b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys g 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
alterWithKeys :: (Ord r, Ord c) => (r -> c -> Maybe a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k). Lookup the values at a row key and column key in the
-- map.
lookup :: (Ord r, Ord c) => r -> c -> Table r c a -> Maybe a
-- | O(log k). Lookup the values at a row key and column key in the
-- map.
--
--
-- fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] !? (1,'a') === Just "b"
-- fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] !? (1,'c') === Nothing
--
(!?) :: (Ord r, Ord c) => Table r c a -> (r, c) -> Maybe a
infixl 9 !?
-- | O(log k). Lookup the values at a row key and column key in the
-- map. Calls error if the value does not exist.
--
--
-- fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] ! (1,'a') === "b"
--
(!) :: (Ord r, Ord c) => Table r c a -> (r, c) -> a
infixl 9 !
-- | O(log k). Is there a value associated with the given row and
-- column keys?
--
--
-- hasCell (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (1,'a') === True
-- hasCell (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (1,'c') === False
--
hasCell :: (Ord r, Ord c) => Table r c a -> (r, c) -> Bool
-- | O(log r). Is there a row with the given row key that has at
-- least one value?
--
--
-- hasRow (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 1 === True
-- hasRow (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 3 === False
--
hasRow :: Ord r => Table r c a -> r -> Bool
-- | O(log c). Is there a column with the given column key that has
-- at least one value?
--
--
-- hasColumn (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 'a' === True
-- hasColumn (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 'c' === False
--
hasColumn :: Ord c => Table r c a -> c -> Bool
-- | O(1). Is the table empty?
--
--
-- Data.Multimap.Table.null empty === True
-- Data.Multimap.Table.null (singleton 1 'a' "a") === False
--
null :: Table r c a -> Bool
-- | O(1). Is the table non-empty?
--
--
-- notNull empty === False
-- notNull (singleton 1 'a' "a") === True
--
notNull :: Table r c a -> Bool
-- | The total number of values for all row and column keys.
--
-- size is evaluated lazily. Forcing the size for the first time
-- takes up to O(n) and subsequent forces take O(1).
--
--
-- size empty === 0
-- size (singleton 1 'a' "a") === 1
-- size (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === 3
--
size :: Table r c a -> Int
-- | Union two tables, preferring values from the first table upon
-- duplicate keys.
--
--
-- union (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
-- === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
union :: (Ord r, Ord c) => Table r c a -> Table r c a -> Table r c a
-- | Union two tables with a combining function for duplicate keys.
--
--
-- unionWith (++) (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
-- === fromList [(1,'a',"bc"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionWith :: (Ord r, Ord c) => (a -> a -> a) -> Table r c a -> Table r c a -> Table r c a
-- | Union two tables with a combining function for duplicate keys.
--
--
-- let f r c a a' = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ a' in do
-- unionWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
-- === fromList [(1,'a',"1:'a':b|c"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionWithKeys :: (Ord r, Ord c) => (r -> c -> a -> a -> a) -> Table r c a -> Table r c a -> Table r c a
-- | Union a number of tables, preferring values from the leftmost table
-- upon duplicate keys.
--
--
-- unions [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
-- === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unions :: (Foldable f, Ord r, Ord c) => f (Table r c a) -> Table r c a
-- | Union a number of tables with a combining function for duplicate keys.
--
--
-- unionsWith (++) [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
-- === fromList [(1,'a',"bc"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionsWith :: (Foldable f, Ord r, Ord c) => (a -> a -> a) -> f (Table r c a) -> Table r c a
-- | Union a number of tables with a combining function for duplicate keys.
--
--
-- let f r c a a' = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ a' in do
-- unionsWithKeys f [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
-- === fromList [(1,'a',"1:'a':b|c"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionsWithKeys :: (Foldable f, Ord r, Ord c) => (r -> c -> a -> a -> a) -> f (Table r c a) -> Table r c a
-- | Difference of two tables. Return values in the first table whose row
-- and column keys do not have an associated value in the second table.
--
--
-- difference (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(1,'b',"d"),(2,'b',"b")])
-- === singleton 2 'a' "b"
--
difference :: (Ord r, Ord c) => Table r c a -> Table r c a -> Table r c a
-- | O(n), assuming the function a -> b takes
-- O(1). Map a function over all values in the table.
--
--
-- Data.Multimap.Table.map (++ "x") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === fromList [(1,'a',"bx"),(1,'b',"cx"),(2,'a',"bx")]
--
map :: (a -> b) -> Table r c a -> Table r c b
-- | O(n), assuming the function r -> c -> a -> b
-- takes O(1). Map a function over all values in the table.
--
--
-- mapWithKeys (\r c x -> show r ++ ":" ++ show c ++ ":" ++ x) (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")])
-- === fromList [(1,'a',"1:'a':b"),(1,'b',"1:'b':c"),(2,'a',"2:'a':b")]
--
mapWithKeys :: (r -> c -> a -> b) -> Table r c a -> Table r c b
-- | Traverse the (row key, column key, value) triples and collect the
-- results.
--
--
-- let f r c a = if odd r && c > 'a' then Just (a ++ "x") else Nothing in do
-- traverseWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === Nothing
-- traverseWithKeys f (fromList [(1,'b',"b"),(1,'c',"c"),(3,'d',"b")]) === Just (fromList [(1,'b',"bx"),(1,'c',"cx"),(3,'d',"bx")])
--
traverseWithKeys :: (Applicative t, Ord r, Ord c) => (r -> c -> a -> t b) -> Table r c a -> t (Table r c b)
-- | Traverse the (row key, column key, value) triples and collect the
-- Just results.
traverseMaybeWithKeys :: (Applicative t, Ord r, Ord c) => (r -> c -> a -> t (Maybe b)) -> Table r c a -> t (Table r c b)
-- | O(n). Fold the values in the table row by row using the given
-- right-associative binary operator.
--
--
-- Data.Multimap.Table.foldr (:) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "bcd"
--
foldr :: (a -> b -> b) -> b -> Table r c a -> b
-- | O(n). Fold the values in the table row by row using the given
-- left-associative binary operator.
--
--
-- Data.Multimap.Table.foldl (flip (:)) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "dcb"
--
foldl :: (a -> b -> a) -> a -> Table r c b -> a
-- | O(n). Fold the (row key, column key value) triplets in the
-- table row by row using the given right-associative binary operator.
--
--
-- let f r c a b = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ b in do
-- foldrWithKeys f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"
--
foldrWithKeys :: (r -> c -> a -> b -> b) -> b -> Table r c a -> b
-- | O(n). Fold the (row key, column key, value) triplets in the
-- table row by row using the given left-associative binary operator.
--
--
-- let f a r c b = show r ++ ":" ++ show c ++ ":" ++ b ++ "|" ++ a in do
-- foldlWithKeys f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "2:'a':d|1:'b':c|1:'a':b|"
--
foldlWithKeys :: (a -> r -> c -> b -> a) -> a -> Table r c b -> a
-- | O(n). Fold the (row key, column key, value) triplets in the map
-- row by row using the given monoid.
--
--
-- let f r c a = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" in do
-- foldMapWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"
--
foldMapWithKeys :: Monoid m => (r -> c -> a -> m) -> Table r c a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Table.foldr' (:) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "bcd"
--
foldr' :: (a -> b -> b) -> b -> Table r c a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Table.foldl' (flip (:)) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "dcb"
--
foldl' :: (a -> b -> a) -> a -> Table r c b -> a
-- | O(n). A strict version of foldrWithKey. Each
-- application of the operator is evaluated before using the result in
-- the next application. This function is strict in the starting value.
--
--
-- let f r c a b = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ b in do
-- foldrWithKeys' f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"
--
foldrWithKeys' :: (r -> c -> a -> b -> b) -> b -> Table r c a -> b
-- | O(n). A strict version of foldlWithKey. Each
-- application of the operator is evaluated before using the result in
-- the next application. This function is strict in the starting value.
--
--
-- let f a r c b = show r ++ ":" ++ show c ++ ":" ++ b ++ "|" ++ a in do
-- foldlWithKeys' f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "2:'a':d|1:'b':c|1:'a':b|"
--
foldlWithKeys' :: (a -> r -> c -> b -> a) -> a -> Table r c b -> a
-- | O(r). Return a mapping from column keys to values for the given
-- row key.
--
--
-- row 1 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.fromList [('a',"b"),('b',"c")]
-- row 3 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.empty
--
row :: Ord r => r -> Table r c a -> Map c a
-- | O(c). Return a mapping from row keys to values for the given
-- column key.
--
--
-- column 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.fromList [(1,"b"),(2,"d")]
-- column 'c' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.empty
--
column :: Ord c => c -> Table r c a -> Map r a
-- | Return a mapping from row keys to maps from column keys to values.
--
--
-- rowMap (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
-- === Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]),(2, Map.fromList [('a',"d")])]
--
rowMap :: Table r c a -> Map r (Map c a)
-- | Return a mapping from column keys to maps from row keys to values.
--
--
-- columnMap (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
-- === Map.fromList [('a', Map.fromList [(1,"b"),(2,"d")]),('b', Map.fromList [(1,"c")])]
--
columnMap :: Table r c a -> Map c (Map r a)
-- | Return, in ascending order, the list of all row keys of that have at
-- least one value in the table.
--
--
-- rowKeys (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [1,2]
--
rowKeys :: Table r c a -> [r]
-- | Return, in ascending order, the list of all column keys of that have
-- at least one value in the table.
--
--
-- columnKeys (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === ['a','b']
--
columnKeys :: Table r c a -> [c]
-- | Return the set of all row keys of that have at least one value in the
-- table.
--
--
-- rowKeysSet (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Set.fromList [1,2]
--
rowKeysSet :: Table r c a -> Set r
-- | Return the set of all column keys of that have at least one value in
-- the table.
--
--
-- columnKeysSet (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Set.fromList ['a','b']
--
columnKeysSet :: Table r c a -> Set c
-- | Convert the table into a list of (row key, column key, value) triples.
--
--
-- toList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
toList :: Table r c a -> [(r, c, a)]
-- | Convert the table into a list of (row key, column key, value) triples
-- in ascending order of row keys, and ascending order of column keys
-- with a row.
--
--
-- toRowAscList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
toRowAscList :: Table r c a -> [(r, c, a)]
-- | Convert the table into a list of (column key, row key, value) triples
-- in ascending order of column keys, and ascending order of row keys
-- with a column.
--
--
-- toColumnAscList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [('a',1,"b"),('a',2,"d"),('b',1,"c")]
--
toColumnAscList :: Table r c a -> [(c, r, a)]
-- | Convert the table into a list of (row key, column key, value) triples
-- in descending order of row keys, and descending order of column keys
-- with a row.
--
--
-- toRowDescList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(2,'a',"d"),(1,'b',"c"),(1,'a',"b")]
--
toRowDescList :: Table r c a -> [(r, c, a)]
-- | Convert the table into a list of (column key, row key, value) triples
-- in descending order of column keys, and descending order of row keys
-- with a column.
--
--
-- toColumnDescList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [('b',1,"c"),('a',2,"d"),('a',1,"b")]
--
toColumnDescList :: Table r c a -> [(c, r, a)]
-- | O(n), assuming the predicate function takes O(1). Retain
-- all values that satisfy the predicate.
--
--
-- Data.Multimap.Table.filter (> "c") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
-- Data.Multimap.Table.filter (> "d") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === empty
--
filter :: (a -> Bool) -> Table r c a -> Table r c a
-- | O(r), assuming the predicate function takes O(1). Retain
-- all rows that satisfy the predicate.
--
--
-- filterRow even (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
--
filterRow :: (r -> Bool) -> Table r c a -> Table r c a
-- | O(c), assuming the predicate function takes O(1). Retain
-- all columns that satisfy the predicate.
--
--
-- filterColumn (> 'a') (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
--
filterColumn :: (c -> Bool) -> Table r c a -> Table r c a
-- | O(c), assuming the predicate function takes O(1). Retain
-- all (row key, column key, value) triples that satisfy the predicate.
--
--
-- filterWithKeys (\r c a -> odd r && c > 'a' && a > "b") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
--
filterWithKeys :: (r -> c -> a -> Bool) -> Table r c a -> Table r c a
-- | O(n), assuming the function a -> Maybe b
-- takes O(1). Map values and collect the Just results.
--
--
-- mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
-- === fromList [(1,'a',"new a"),(2,'b',"new a")]
--
mapMaybe :: (a -> Maybe b) -> Table r c a -> Table r c b
-- | O(n), assuming the function r -> c -> a ->
-- Maybe b takes O(1). Map (row key, column key,
-- value) triples and collect the Just results.
--
--
-- let f r c a = if r == 1 && a == "c" then Just "new c" else Nothing in do
-- mapMaybeWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "new c"
--
mapMaybeWithKeys :: (r -> c -> a -> Maybe b) -> Table r c a -> Table r c b
-- | O(n), assuming the function a -> Either a1
-- a2 takes O(1). Map values and separate the Left and
-- Right results.
--
--
-- mapEither (\a -> if a == "a" then Left a else Right a) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
-- === (fromList [(1,'a',"a"),(2,'b',"a")],fromList [(1,'b',"c")])
--
mapEither :: (a -> Either a1 a2) -> Table r c a -> (Table r c a1, Table r c a2)
-- | O(n), assuming the function r -> c -> a ->
-- Either a1 a2 takes O(1). Map (row key, column key,
-- value) triples and separate the Left and Right results.
--
--
-- mapEitherWithKeys (\r c a -> if r == 1 && c == 'a' then Left a else Right a) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
-- === (fromList [(1,'a',"a")],fromList [(1,'b',"c"),(2,'b',"a")])
--
mapEitherWithKeys :: (r -> c -> a -> Either a1 a2) -> Table r c a -> (Table r c a1, Table r c a2)
instance (Data.Data.Data r, Data.Data.Data c, Data.Data.Data a, GHC.Classes.Ord c, GHC.Classes.Ord r) => Data.Data.Data (Data.Multimap.Table.Internal.Table r c a)
instance (GHC.Classes.Ord r, GHC.Classes.Ord c, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Multimap.Table.Internal.Table r c a)
instance (GHC.Classes.Eq r, GHC.Classes.Eq c, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Multimap.Table.Internal.Table r c a)
instance (GHC.Show.Show r, GHC.Show.Show c, GHC.Show.Show a) => GHC.Show.Show (Data.Multimap.Table.Internal.Table r c a)
instance (GHC.Classes.Ord r, GHC.Classes.Ord c, GHC.Read.Read r, GHC.Read.Read c, GHC.Read.Read a) => GHC.Read.Read (Data.Multimap.Table.Internal.Table r c a)
instance GHC.Base.Functor (Data.Multimap.Table.Internal.Table r c)
instance Data.Foldable.Foldable (Data.Multimap.Table.Internal.Table r c)
instance (GHC.Classes.Ord r, GHC.Classes.Ord c) => Data.Traversable.Traversable (Data.Multimap.Table.Internal.Table r c)
instance (GHC.Classes.Ord r, GHC.Classes.Ord c) => GHC.Base.Semigroup (Data.Multimap.Table.Internal.Table r c a)
instance (GHC.Classes.Ord r, GHC.Classes.Ord c) => GHC.Base.Monoid (Data.Multimap.Table.Internal.Table r c a)
-- | The Table r c a type represents a finite
-- two-dimensional table that associates a pair of keys (a row key of
-- type r and a column key of type c) with a value of
-- type a.
--
-- The implementation is backed by two maps: a Map r
-- (Map c) a, and a Map c (Map r)
-- a, called "row map" and "column map", respectively.
--
-- It is worth noting that all functions that traverse a table, such as
-- foldl, foldr, foldMap and traverse, are
-- row-oriented, i.e., they traverse the table row by row. To traverse a
-- table column by column, transpose the table first.
--
-- In the following Big-O notations, unless otherwise noted, n
-- denotes the size of the table (i.e., the total number of values for
-- all row and column keys), r denotes the number of row keys that
-- has at least one value, c denotes the number of column keys
-- that has at least one value, and k = max r c.
module Data.Multimap.Table
data Table r c a
-- | O(1). The empty table.
--
--
-- size empty === 0
--
empty :: Table r c a
-- | O(1). A table with a single element.
--
--
-- singleton 1 'a' "a" === fromList [(1,'a',"a")]
-- size (singleton 1 'a' "a") === 1
--
singleton :: r -> c -> a -> Table r c a
-- | Build a table from a row map.
--
--
-- fromRowMap (Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]), (2, Map.fromList [('a',"d")])])
-- === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
fromRowMap :: (Ord r, Ord c) => Map r (Map c a) -> Table r c a
-- | Build a table from a column map.
--
--
-- fromColumnMap (Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]), (2, Map.fromList [('a',"d")])])
-- === fromList [('a',1,"b"),('a',2,"d"),('b',1,"c")]
--
fromColumnMap :: (Ord r, Ord c) => Map c (Map r a) -> Table r c a
-- | Flip the row and column keys.
--
--
-- transpose (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [('a',1,"b"),('a',2,"d"),('b',1,"c")]
--
transpose :: Table r c a -> Table c r a
-- | Build a table from a list of key/value pairs.
--
--
-- fromList ([] :: [(Int, Char, String)]) === empty
--
fromList :: (Ord r, Ord c) => [(r, c, a)] -> Table r c a
-- | O(log k). Associate with value with the row key and the column
-- key. If the table already contains a value for those keys, the value
-- is replaced.
--
--
-- insert 1 'a' "a" empty === singleton 1 'a' "a"
-- insert 1 'a' "a" (fromList [(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"d")]
-- insert 1 'a' "a" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"d")]
--
insert :: (Ord r, Ord c) => r -> c -> a -> Table r c a -> Table r c a
-- | O(log k). Remove the value associated with the given keys.
--
--
-- delete 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'b',"c"),(2,'a',"d")]
-- delete 1 'a' (fromList [(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'b',"c"),(2,'a',"d")]
--
delete :: (Ord r, Ord c) => r -> c -> Table r c a -> Table r c a
-- | Remove an entire row.
--
--
-- deleteRow 1 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
-- deleteRow 3 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
deleteRow :: Ord r => r -> Table r c a -> Table r c a
-- | Remove an entire column.
--
--
-- deleteColumn 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
-- deleteColumn 'z' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
deleteColumn :: Ord c => c -> Table r c a -> Table r c a
-- | O(log k), assuming the function a -> a takes
-- O(1). Update the value at a specific row key and column key, if
-- exists.
--
--
-- adjust ("new " ++) 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"new b"),(1,'b',"c"),(2,'a',"d")]
--
adjust :: (Ord r, Ord c) => (a -> a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function r -> c -> a ->
-- a takes O(1). Update the value at a specific row key and
-- column key, if exists.
--
--
-- adjustWithKeys (\r c x -> show r ++ ":" ++ show c ++ ":new " ++ x) 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
-- === fromList [(1,'a',"1:'a':new b"),(1,'b',"c"),(2,'a',"d")]
--
adjustWithKeys :: (Ord r, Ord c) => (r -> c -> a -> a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function a -> Maybe a
-- takes O(1). The expression (update f r c table)
-- updates the value at the given row and column keys, if exists. If
-- f returns Nothing, the value associated with those
-- keys, if exists is deleted.
--
--
-- let f x = if x == "b" then Just "new b" else Nothing in do
-- update f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"new b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- update f 1 'a' (fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
update :: (Ord r, Ord c) => (a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function r -> c -> a ->
-- Maybe a takes O(1). The expression
-- (updateWithKeys f r c table) updates the value at the
-- given row and column keys, if exists. If f returns
-- Nothing, the value associated with those keys, if exists is
-- deleted.
--
--
-- let f r c x = if x == "b" then Just (show r ++ ":" ++ show c ++ ":new b") else Nothing in do
-- updateWithKeys f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"1:'a':new b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- updateWithKeys f 1 'a' (fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
updateWithKeys :: (Ord r, Ord c) => (r -> c -> a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function Maybe a ->
-- Maybe a takes O(1). The expression
-- (alter f r c table) alters the value at the given row
-- and column keys, if exists. It can be used to insert, delete or update
-- a value.
--
--
-- let (f,g,h) = (const Nothing, const (Just "hello"), fmap ('z':)) in do
-- alter f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter f 4 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter f 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter g 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"hello"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter g 4 'e' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c"),(4,'e',"hello")]
-- alter h 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"zb"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alter h 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
alter :: (Ord r, Ord c) => (Maybe a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k), assuming the function r -> c ->
-- Maybe a -> Maybe a takes O(1). The
-- expression (alterWithKeys f r c table) alters the
-- value at the given row and column keys, if exists. It can be used to
-- insert, delete or update a value.
--
--
-- let (f,g) = (\_ _ _ -> Nothing, \r c -> fmap ((show r ++ ":" ++ show c ++ ":") ++)) in do
-- alterWithKeys f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys f 4 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys f 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys g 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"1:'a':b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
-- alterWithKeys g 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
--
alterWithKeys :: (Ord r, Ord c) => (r -> c -> Maybe a -> Maybe a) -> r -> c -> Table r c a -> Table r c a
-- | O(log k). Lookup the values at a row key and column key in the
-- map.
lookup :: (Ord r, Ord c) => r -> c -> Table r c a -> Maybe a
-- | O(log k). Lookup the values at a row key and column key in the
-- map.
--
--
-- fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] !? (1,'a') === Just "b"
-- fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] !? (1,'c') === Nothing
--
(!?) :: (Ord r, Ord c) => Table r c a -> (r, c) -> Maybe a
infixl 9 !?
-- | O(log k). Lookup the values at a row key and column key in the
-- map. Calls error if the value does not exist.
--
--
-- fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] ! (1,'a') === "b"
--
(!) :: (Ord r, Ord c) => Table r c a -> (r, c) -> a
infixl 9 !
-- | O(log k). Is there a value associated with the given row and
-- column keys?
--
--
-- hasCell (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (1,'a') === True
-- hasCell (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (1,'c') === False
--
hasCell :: (Ord r, Ord c) => Table r c a -> (r, c) -> Bool
-- | O(log r). Is there a row with the given row key that has at
-- least one value?
--
--
-- hasRow (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 1 === True
-- hasRow (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 3 === False
--
hasRow :: Ord r => Table r c a -> r -> Bool
-- | O(log c). Is there a column with the given column key that has
-- at least one value?
--
--
-- hasColumn (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 'a' === True
-- hasColumn (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 'c' === False
--
hasColumn :: Ord c => Table r c a -> c -> Bool
-- | O(1). Is the table empty?
--
--
-- Data.Multimap.Table.null empty === True
-- Data.Multimap.Table.null (singleton 1 'a' "a") === False
--
null :: Table r c a -> Bool
-- | O(1). Is the table non-empty?
--
--
-- notNull empty === False
-- notNull (singleton 1 'a' "a") === True
--
notNull :: Table r c a -> Bool
-- | The total number of values for all row and column keys.
--
-- size is evaluated lazily. Forcing the size for the first time
-- takes up to O(n) and subsequent forces take O(1).
--
--
-- size empty === 0
-- size (singleton 1 'a' "a") === 1
-- size (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === 3
--
size :: Table r c a -> Int
-- | Union two tables, preferring values from the first table upon
-- duplicate keys.
--
--
-- union (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
-- === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
union :: (Ord r, Ord c) => Table r c a -> Table r c a -> Table r c a
-- | Union two tables with a combining function for duplicate keys.
--
--
-- unionWith (++) (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
-- === fromList [(1,'a',"bc"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionWith :: (Ord r, Ord c) => (a -> a -> a) -> Table r c a -> Table r c a -> Table r c a
-- | Union two tables with a combining function for duplicate keys.
--
--
-- let f r c a a' = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ a' in do
-- unionWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
-- === fromList [(1,'a',"1:'a':b|c"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionWithKeys :: (Ord r, Ord c) => (r -> c -> a -> a -> a) -> Table r c a -> Table r c a -> Table r c a
-- | Union a number of tables, preferring values from the leftmost table
-- upon duplicate keys.
--
--
-- unions [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
-- === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unions :: (Foldable f, Ord r, Ord c) => f (Table r c a) -> Table r c a
-- | Union a number of tables with a combining function for duplicate keys.
--
--
-- unionsWith (++) [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
-- === fromList [(1,'a',"bc"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionsWith :: (Foldable f, Ord r, Ord c) => (a -> a -> a) -> f (Table r c a) -> Table r c a
-- | Union a number of tables with a combining function for duplicate keys.
--
--
-- let f r c a a' = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ a' in do
-- unionsWithKeys f [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
-- === fromList [(1,'a',"1:'a':b|c"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]
--
unionsWithKeys :: (Foldable f, Ord r, Ord c) => (r -> c -> a -> a -> a) -> f (Table r c a) -> Table r c a
-- | Difference of two tables. Return values in the first table whose row
-- and column keys do not have an associated value in the second table.
--
--
-- difference (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(1,'b',"d"),(2,'b',"b")])
-- === singleton 2 'a' "b"
--
difference :: (Ord r, Ord c) => Table r c a -> Table r c a -> Table r c a
-- | O(n), assuming the function a -> b takes
-- O(1). Map a function over all values in the table.
--
--
-- Data.Multimap.Table.map (++ "x") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === fromList [(1,'a',"bx"),(1,'b',"cx"),(2,'a',"bx")]
--
map :: (a -> b) -> Table r c a -> Table r c b
-- | O(n), assuming the function r -> c -> a -> b
-- takes O(1). Map a function over all values in the table.
--
--
-- mapWithKeys (\r c x -> show r ++ ":" ++ show c ++ ":" ++ x) (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")])
-- === fromList [(1,'a',"1:'a':b"),(1,'b',"1:'b':c"),(2,'a',"2:'a':b")]
--
mapWithKeys :: (r -> c -> a -> b) -> Table r c a -> Table r c b
-- | Traverse the (row key, column key, value) triples and collect the
-- results.
--
--
-- let f r c a = if odd r && c > 'a' then Just (a ++ "x") else Nothing in do
-- traverseWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === Nothing
-- traverseWithKeys f (fromList [(1,'b',"b"),(1,'c',"c"),(3,'d',"b")]) === Just (fromList [(1,'b',"bx"),(1,'c',"cx"),(3,'d',"bx")])
--
traverseWithKeys :: (Applicative t, Ord r, Ord c) => (r -> c -> a -> t b) -> Table r c a -> t (Table r c b)
-- | Traverse the (row key, column key, value) triples and collect the
-- Just results.
traverseMaybeWithKeys :: (Applicative t, Ord r, Ord c) => (r -> c -> a -> t (Maybe b)) -> Table r c a -> t (Table r c b)
-- | O(n). Fold the values in the table row by row using the given
-- right-associative binary operator.
--
--
-- Data.Multimap.Table.foldr (:) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "bcd"
--
foldr :: (a -> b -> b) -> b -> Table r c a -> b
-- | O(n). Fold the values in the table row by row using the given
-- left-associative binary operator.
--
--
-- Data.Multimap.Table.foldl (flip (:)) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "dcb"
--
foldl :: (a -> b -> a) -> a -> Table r c b -> a
-- | O(n). Fold the (row key, column key value) triplets in the
-- table row by row using the given right-associative binary operator.
--
--
-- let f r c a b = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ b in do
-- foldrWithKeys f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"
--
foldrWithKeys :: (r -> c -> a -> b -> b) -> b -> Table r c a -> b
-- | O(n). Fold the (row key, column key, value) triplets in the
-- table row by row using the given left-associative binary operator.
--
--
-- let f a r c b = show r ++ ":" ++ show c ++ ":" ++ b ++ "|" ++ a in do
-- foldlWithKeys f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "2:'a':d|1:'b':c|1:'a':b|"
--
foldlWithKeys :: (a -> r -> c -> b -> a) -> a -> Table r c b -> a
-- | O(n). Fold the (row key, column key, value) triplets in the map
-- row by row using the given monoid.
--
--
-- let f r c a = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" in do
-- foldMapWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"
--
foldMapWithKeys :: Monoid m => (r -> c -> a -> m) -> Table r c a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Table.foldr' (:) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "bcd"
--
foldr' :: (a -> b -> b) -> b -> Table r c a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
--
--
-- Data.Multimap.Table.foldl' (flip (:)) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "dcb"
--
foldl' :: (a -> b -> a) -> a -> Table r c b -> a
-- | O(n). A strict version of foldrWithKey. Each
-- application of the operator is evaluated before using the result in
-- the next application. This function is strict in the starting value.
--
--
-- let f r c a b = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ b in do
-- foldrWithKeys' f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"
--
foldrWithKeys' :: (r -> c -> a -> b -> b) -> b -> Table r c a -> b
-- | O(n). A strict version of foldlWithKey. Each
-- application of the operator is evaluated before using the result in
-- the next application. This function is strict in the starting value.
--
--
-- let f a r c b = show r ++ ":" ++ show c ++ ":" ++ b ++ "|" ++ a in do
-- foldlWithKeys' f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "2:'a':d|1:'b':c|1:'a':b|"
--
foldlWithKeys' :: (a -> r -> c -> b -> a) -> a -> Table r c b -> a
-- | O(r). Return a mapping from column keys to values for the given
-- row key.
--
--
-- row 1 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.fromList [('a',"b"),('b',"c")]
-- row 3 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.empty
--
row :: Ord r => r -> Table r c a -> Map c a
-- | O(c). Return a mapping from row keys to values for the given
-- column key.
--
--
-- column 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.fromList [(1,"b"),(2,"d")]
-- column 'c' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.empty
--
column :: Ord c => c -> Table r c a -> Map r a
-- | Return a mapping from row keys to maps from column keys to values.
--
--
-- rowMap (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
-- === Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]),(2, Map.fromList [('a',"d")])]
--
rowMap :: Table r c a -> Map r (Map c a)
-- | Return a mapping from column keys to maps from row keys to values.
--
--
-- columnMap (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
-- === Map.fromList [('a', Map.fromList [(1,"b"),(2,"d")]),('b', Map.fromList [(1,"c")])]
--
columnMap :: Table r c a -> Map c (Map r a)
-- | Return, in ascending order, the list of all row keys of that have at
-- least one value in the table.
--
--
-- rowKeys (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [1,2]
--
rowKeys :: Table r c a -> [r]
-- | Return, in ascending order, the list of all column keys of that have
-- at least one value in the table.
--
--
-- columnKeys (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === ['a','b']
--
columnKeys :: Table r c a -> [c]
-- | Return the set of all row keys of that have at least one value in the
-- table.
--
--
-- rowKeysSet (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Set.fromList [1,2]
--
rowKeysSet :: Table r c a -> Set r
-- | Return the set of all column keys of that have at least one value in
-- the table.
--
--
-- columnKeysSet (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Set.fromList ['a','b']
--
columnKeysSet :: Table r c a -> Set c
-- | Convert the table into a list of (row key, column key, value) triples.
--
--
-- toList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
toList :: Table r c a -> [(r, c, a)]
-- | Convert the table into a list of (row key, column key, value) triples
-- in ascending order of row keys, and ascending order of column keys
-- with a row.
--
--
-- toRowAscList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]
--
toRowAscList :: Table r c a -> [(r, c, a)]
-- | Convert the table into a list of (column key, row key, value) triples
-- in ascending order of column keys, and ascending order of row keys
-- with a column.
--
--
-- toColumnAscList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [('a',1,"b"),('a',2,"d"),('b',1,"c")]
--
toColumnAscList :: Table r c a -> [(c, r, a)]
-- | Convert the table into a list of (row key, column key, value) triples
-- in descending order of row keys, and descending order of column keys
-- with a row.
--
--
-- toRowDescList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(2,'a',"d"),(1,'b',"c"),(1,'a',"b")]
--
toRowDescList :: Table r c a -> [(r, c, a)]
-- | Convert the table into a list of (column key, row key, value) triples
-- in descending order of column keys, and descending order of row keys
-- with a column.
--
--
-- toColumnDescList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [('b',1,"c"),('a',2,"d"),('a',1,"b")]
--
toColumnDescList :: Table r c a -> [(c, r, a)]
-- | O(n), assuming the predicate function takes O(1). Retain
-- all values that satisfy the predicate.
--
--
-- Data.Multimap.Table.filter (> "c") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
-- Data.Multimap.Table.filter (> "d") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === empty
--
filter :: (a -> Bool) -> Table r c a -> Table r c a
-- | O(r), assuming the predicate function takes O(1). Retain
-- all rows that satisfy the predicate.
--
--
-- filterRow even (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
--
filterRow :: (r -> Bool) -> Table r c a -> Table r c a
-- | O(c), assuming the predicate function takes O(1). Retain
-- all columns that satisfy the predicate.
--
--
-- filterColumn (> 'a') (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
--
filterColumn :: (c -> Bool) -> Table r c a -> Table r c a
-- | O(c), assuming the predicate function takes O(1). Retain
-- all (row key, column key, value) triples that satisfy the predicate.
--
--
-- filterWithKeys (\r c a -> odd r && c > 'a' && a > "b") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
--
filterWithKeys :: (r -> c -> a -> Bool) -> Table r c a -> Table r c a
-- | O(n), assuming the function a -> Maybe b
-- takes O(1). Map values and collect the Just results.
--
--
-- mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
-- === fromList [(1,'a',"new a"),(2,'b',"new a")]
--
mapMaybe :: (a -> Maybe b) -> Table r c a -> Table r c b
-- | O(n), assuming the function r -> c -> a ->
-- Maybe b takes O(1). Map (row key, column key,
-- value) triples and collect the Just results.
--
--
-- let f r c a = if r == 1 && a == "c" then Just "new c" else Nothing in do
-- mapMaybeWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "new c"
--
mapMaybeWithKeys :: (r -> c -> a -> Maybe b) -> Table r c a -> Table r c b
-- | O(n), assuming the function a -> Either a1
-- a2 takes O(1). Map values and separate the Left and
-- Right results.
--
--
-- mapEither (\a -> if a == "a" then Left a else Right a) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
-- === (fromList [(1,'a',"a"),(2,'b',"a")],fromList [(1,'b',"c")])
--
mapEither :: (a -> Either a1 a2) -> Table r c a -> (Table r c a1, Table r c a2)
-- | O(n), assuming the function r -> c -> a ->
-- Either a1 a2 takes O(1). Map (row key, column key,
-- value) triples and separate the Left and Right results.
--
--
-- mapEitherWithKeys (\r c a -> if r == 1 && c == 'a' then Left a else Right a) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
-- === (fromList [(1,'a',"a")],fromList [(1,'b',"c"),(2,'b',"a")])
--
mapEitherWithKeys :: (r -> c -> a -> Either a1 a2) -> Table r c a -> (Table r c a1, Table r c a2)