{-# LANGUAGE LambdaCase #-}

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

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

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' =
      [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
as ([a]
bs' [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a] -> [a]
forall a. [a] -> [a]
reverse [a]
as' [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
bs)

instance Monoid (Deque a) where
    mempty :: Deque a
mempty = [a] -> [a] -> Deque a
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) =
      (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step ((b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> b -> b) -> b -> a -> b
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) =
      (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' ((b -> a -> b) -> a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
step) ((b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
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 = [a] -> [a] -> Deque a
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) = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
as (a
a a -> [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 -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
a, [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
head' [a]
tail)
    Deque [] [a]
tail ->
      case [a] -> [a]
forall a. [a] -> [a]
reverse [a]
tail of
        (a
a : [a]
head') -> (a, Deque a) -> Maybe (a, Deque a)
forall a. a -> Maybe a
Just (a
a, [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque [a]
head' [])
        []          -> Maybe (a, Deque a)
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) = [a] -> [a] -> Deque a
forall a. [a] -> [a] -> Deque a
Deque ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
f [a]
head) ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.filter a -> Bool
f [a]
tail)