-- | This module provides list-specific multimap functionality.
module Data.Multimap.List (
  ListMultimap,
  cons, uncons
) where

import Data.Functor.Compose (Compose(..))
import qualified Data.List as List

import Data.Multimap.Generic (Multimap(..), modifyMany, modifyManyF)

-- | A multimap with list values. Note that lists do not support efficient appends or sizing, so
-- several multimap operations will have higher complexity than for other collections. If
-- performance is a concern, consider using a 'Data.Multimap.SeqMultimap' instead.
--
-- See "Data.Multimap.List" for operations specific to this type.
type ListMultimap = Multimap []

-- | /O(log m)/ Prepends a value to a given key.
cons :: (Ord k) => k -> v -> ListMultimap k v -> ListMultimap k v
cons :: k -> v -> ListMultimap k v -> ListMultimap k v
cons k
k v
v = ([v] -> [v]) -> k -> ListMultimap k v -> ListMultimap k v
forall (c :: * -> *) v k.
(Collection c, Monoid (c v), Ord k) =>
(c v -> c v) -> k -> Multimap c k v -> Multimap c k v
modifyMany (v
vv -> [v] -> [v]
forall a. a -> [a] -> [a]
:) k
k

-- | /O(log m)/ Extracts the first value associated with a given key, if possible.
uncons :: (Ord k, Ord v) => k -> ListMultimap k v -> Maybe (v, ListMultimap k v)
uncons :: k -> ListMultimap k v -> Maybe (v, ListMultimap k v)
uncons k
k = Compose Maybe ((,) v) (ListMultimap k v)
-> Maybe (v, ListMultimap k v)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose (Compose Maybe ((,) v) (ListMultimap k v)
 -> Maybe (v, ListMultimap k v))
-> (ListMultimap k v -> Compose Maybe ((,) v) (ListMultimap k v))
-> ListMultimap k v
-> Maybe (v, ListMultimap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([v] -> Compose Maybe ((,) v) [v])
-> k
-> ListMultimap k v
-> Compose Maybe ((,) v) (ListMultimap k v)
forall (c :: * -> *) v k (f :: * -> *).
(Collection c, Monoid (c v), Ord k, Functor f) =>
(c v -> f (c v)) -> k -> Multimap c k v -> f (Multimap c k v)
modifyManyF (Maybe (v, [v]) -> Compose Maybe ((,) v) [v]
forall k k1 (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose (Maybe (v, [v]) -> Compose Maybe ((,) v) [v])
-> ([v] -> Maybe (v, [v])) -> [v] -> Compose Maybe ((,) v) [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [v] -> Maybe (v, [v])
forall a. [a] -> Maybe (a, [a])
List.uncons) k
k