{-# LANGUAGE LambdaCase #-}

-- | A minimal implementation of a strict deque.
--
module Data.Deque.Strict where

import           Prelude hiding (head, init, tail)
import           Data.Foldable (foldl', foldr')
import qualified Data.List as List

data Deque a = Deque ![a] ![a]

instance Semigroup (Deque a) where
    Deque [a]
as [a]
bs <> :: Deque a -> Deque a -> Deque a
<> Deque [a]
as' [a]
bs' =
      forall a. [a] -> [a] -> Deque a
Deque [a]
as ([a]
bs' forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [a]
reverse [a]
as' forall a. [a] -> [a] -> [a]
++ [a]
bs)

instance Monoid (Deque a) where
    mempty :: Deque a
mempty = forall a. [a] -> [a] -> Deque a
Deque [] []

instance Foldable Deque where
    foldr :: forall a b. (a -> b -> b) -> b -> Deque a -> b
foldr a -> b -> b
step b
init (Deque [a]
head [a]
tail) =
      forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
step) b
init [a]
tail) [a]
head
    foldl' :: forall b a. (b -> a -> b) -> b -> Deque a -> b
foldl' b -> a -> b
step b
init (Deque [a]
head [a]
tail) =
      forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' (forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
step) (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step b
init [a]
head) [a]
tail

fromList :: [a] -> Deque a
fromList :: forall a. [a] -> Deque a
fromList [a]
as = forall a. [a] -> [a] -> Deque a
Deque [a]
as []

snoc :: a -> Deque a -> Deque a
snoc :: forall a. a -> Deque a -> Deque a
snoc a
a (Deque [a]
as [a]
bs) = forall a. [a] -> [a] -> Deque a
Deque [a]
as (a
a forall a. a -> [a] -> [a]
: [a]
bs)

uncons :: Deque a -> Maybe (a, Deque a)
uncons :: forall a. Deque a -> Maybe (a, Deque a)
uncons = \case
    Deque (a
a : [a]
head') [a]
tail -> forall a. a -> Maybe a
Just (a
a, forall a. [a] -> [a] -> Deque a
Deque [a]
head' [a]
tail)
    Deque [] [a]
tail ->
      case forall a. [a] -> [a]
reverse [a]
tail of
        (a
a : [a]
head') -> forall a. a -> Maybe a
Just (a
a, forall a. [a] -> [a] -> Deque a
Deque [a]
head' [])
        []          -> forall a. Maybe a
Nothing

filter :: (a -> Bool) -> Deque a -> Deque a
filter :: forall a. (a -> Bool) -> Deque a -> Deque a
filter a -> Bool
f (Deque [a]
head [a]
tail) = forall a. [a] -> [a] -> Deque a
Deque (forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
f [a]
head) (forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
f [a]
tail)