-- | This module provides sequence-specific multimap functionality.
module Data.Multimap.Seq (
  SeqMultimap,
  popFirst, popLast
) where

import Data.Functor.Compose (Compose(..))
import Data.Sequence (Seq)
import qualified Data.Sequence as Seq

import Data.Multimap.Generic (Multimap, modifyManyF)

-- | A multimap with 'Seq' values.
--
-- See "Data.Multimap.Seq" for operations specific to this type.
type SeqMultimap = Multimap Seq

-- | /O(log m)/ Pops the first value associated with a key, if present.
popFirst :: Ord k => k -> SeqMultimap k v -> Maybe (v, SeqMultimap k v)
popFirst :: k -> SeqMultimap k v -> Maybe (v, SeqMultimap k v)
popFirst k
k = Compose Maybe ((,) v) (SeqMultimap k v)
-> Maybe (v, SeqMultimap k v)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose (Compose Maybe ((,) v) (SeqMultimap k v)
 -> Maybe (v, SeqMultimap k v))
-> (SeqMultimap k v -> Compose Maybe ((,) v) (SeqMultimap k v))
-> SeqMultimap k v
-> Maybe (v, SeqMultimap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Seq v -> Compose Maybe ((,) v) (Seq v))
-> k -> SeqMultimap k v -> Compose Maybe ((,) v) (SeqMultimap 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, Seq v) -> Compose Maybe ((,) v) (Seq v)
forall k k1 (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose (Maybe (v, Seq v) -> Compose Maybe ((,) v) (Seq v))
-> (Seq v -> Maybe (v, Seq v))
-> Seq v
-> Compose Maybe ((,) v) (Seq v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ViewL v -> Maybe (v, Seq v)
forall a. ViewL a -> Maybe (a, Seq a)
go (ViewL v -> Maybe (v, Seq v))
-> (Seq v -> ViewL v) -> Seq v -> Maybe (v, Seq v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq v -> ViewL v
forall a. Seq a -> ViewL a
Seq.viewl) k
k where
  go :: ViewL a -> Maybe (a, Seq a)
go ViewL a
Seq.EmptyL = Maybe (a, Seq a)
forall a. Maybe a
Nothing
  go (a
v Seq.:< Seq a
c) = (a, Seq a) -> Maybe (a, Seq a)
forall a. a -> Maybe a
Just (a
v, Seq a
c)

-- | /O(log m)/ Pops the last value associated with a key, if present.
popLast :: Ord k => k -> SeqMultimap k v -> Maybe (v, SeqMultimap k v)
popLast :: k -> SeqMultimap k v -> Maybe (v, SeqMultimap k v)
popLast k
k = Compose Maybe ((,) v) (SeqMultimap k v)
-> Maybe (v, SeqMultimap k v)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose (Compose Maybe ((,) v) (SeqMultimap k v)
 -> Maybe (v, SeqMultimap k v))
-> (SeqMultimap k v -> Compose Maybe ((,) v) (SeqMultimap k v))
-> SeqMultimap k v
-> Maybe (v, SeqMultimap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Seq v -> Compose Maybe ((,) v) (Seq v))
-> k -> SeqMultimap k v -> Compose Maybe ((,) v) (SeqMultimap 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, Seq v) -> Compose Maybe ((,) v) (Seq v)
forall k k1 (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose (Maybe (v, Seq v) -> Compose Maybe ((,) v) (Seq v))
-> (Seq v -> Maybe (v, Seq v))
-> Seq v
-> Compose Maybe ((,) v) (Seq v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ViewR v -> Maybe (v, Seq v)
forall a. ViewR a -> Maybe (a, Seq a)
go (ViewR v -> Maybe (v, Seq v))
-> (Seq v -> ViewR v) -> Seq v -> Maybe (v, Seq v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq v -> ViewR v
forall a. Seq a -> ViewR a
Seq.viewr) k
k where
  go :: ViewR a -> Maybe (a, Seq a)
go ViewR a
Seq.EmptyR = Maybe (a, Seq a)
forall a. Maybe a
Nothing
  go (Seq a
c Seq.:> a
v) = (a, Seq a) -> Maybe (a, Seq a)
forall a. a -> Maybe a
Just (a
v, Seq a
c)