{-# LANGUAGE CPP #-}

-- |
-- Definitions of strict Deque.
--
-- The typical `toList` and `fromList` conversions are provided by means of
-- the `Foldable` and `IsList` instances.
module Deque.Strict.Defs where

import Deque.Prelude hiding (dropWhile, filter, head, init, last, null, reverse, tail, take, takeWhile)
import qualified Deque.Prelude as Prelude
import qualified StrictList

-- |
-- Strict double-ended queue (aka Dequeue or Deque) based on head-tail linked list.
data Deque a = Deque !(StrictList.List a) !(StrictList.List a)

-- |
-- \(\mathcal{O}(n)\).
-- Construct from cons and snoc lists.
{-# INLINE fromConsAndSnocLists #-}
fromConsAndSnocLists :: [a] -> [a] -> Deque a
fromConsAndSnocLists :: forall a. [a] -> [a] -> Deque a
fromConsAndSnocLists [a]
consList [a]
snocList = forall a. List a -> List a -> Deque a
Deque (forall l. IsList l => [Item l] -> l
fromList [a]
consList) (forall l. IsList l => [Item l] -> l
fromList [a]
snocList)

-- |
-- \(\mathcal{O}(1)\).
-- Add element in the beginning.
{-# INLINE cons #-}
cons :: a -> Deque a -> Deque a
cons :: forall a. a -> Deque a -> Deque a
cons a
a (Deque List a
consList List a
snocList) = forall a. List a -> List a -> Deque a
Deque (forall a. a -> List a -> List a
StrictList.Cons a
a List a
consList) List a
snocList

-- |
-- \(\mathcal{O}(1)\).
-- Add element in the ending.
{-# INLINE snoc #-}
snoc :: a -> Deque a -> Deque a
snoc :: forall a. a -> Deque a -> Deque a
snoc a
a (Deque List a
consList List a
snocList) = forall a. List a -> List a -> Deque a
Deque List a
consList (forall a. a -> List a -> List a
StrictList.Cons a
a List a
snocList)

-- |
-- \(\mathcal{O}(1)\).
-- Reverse the deque.
{-# INLINE reverse #-}
reverse :: Deque a -> Deque a
reverse :: forall a. Deque a -> Deque a
reverse (Deque List a
consList List a
snocList) = forall a. List a -> List a -> Deque a
Deque List a
snocList List a
consList

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Move the first element to the end.
--
-- @
-- λ toList . shiftLeft $ fromList [1,2,3]
-- [2,3,1]
-- @
{-# INLINE shiftLeft #-}
shiftLeft :: Deque a -> Deque a
shiftLeft :: forall a. Deque a -> Deque a
shiftLeft Deque a
deque = forall b a. b -> (a -> b) -> Maybe a -> b
maybe Deque a
deque (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. a -> Deque a -> Deque a
snoc) (forall a. Deque a -> Maybe (a, Deque a)
uncons Deque a
deque)

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Move the last element to the beginning.
--
-- @
-- λ toList . shiftRight $ fromList [1,2,3]
-- [3,1,2]
-- @
{-# INLINE shiftRight #-}
shiftRight :: Deque a -> Deque a
shiftRight :: forall a. Deque a -> Deque a
shiftRight Deque a
deque = forall b a. b -> (a -> b) -> Maybe a -> b
maybe Deque a
deque (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a. a -> Deque a -> Deque a
cons) (forall a. Deque a -> Maybe (a, Deque a)
unsnoc Deque a
deque)

balanceLeft :: Deque a -> Deque a
balanceLeft :: forall a. Deque a -> Deque a
balanceLeft = forall a. HasCallStack => [Char] -> a
error [Char]
"TODO"

-- |
-- \(\mathcal{O}(n)\).
-- Leave only the elements satisfying the predicate.
{-# INLINE filter #-}
filter :: (a -> Bool) -> Deque a -> Deque a
filter :: forall a. (a -> Bool) -> Deque a -> Deque a
filter a -> Bool
predicate (Deque List a
consList List a
snocList) =
  let newConsList :: List a
newConsList =
        forall a. List a -> List a -> List a
StrictList.prependReversed
          (forall a. (a -> Bool) -> List a -> List a
StrictList.filterReversed a -> Bool
predicate List a
consList)
          (forall a. (a -> Bool) -> List a -> List a
StrictList.filterReversed a -> Bool
predicate List a
snocList)
   in forall a. List a -> List a -> Deque a
Deque List a
newConsList forall a. List a
StrictList.Nil

-- |
-- \(\mathcal{O}(n)\).
-- Leave only the specified amount of first elements.
take :: Int -> Deque a -> Deque a
take :: forall a. Int -> Deque a -> Deque a
take Int
amount (Deque List a
consList List a
snocList) =
  let newSnocList :: List a
newSnocList =
        let buildFromConsList :: Int -> List a -> List a -> List a
buildFromConsList Int
amount !List a
list =
              if Int
amount forall a. Ord a => a -> a -> Bool
> Int
0
                then \case
                  StrictList.Cons a
head List a
tail -> Int -> List a -> List a -> List a
buildFromConsList (forall a. Enum a => a -> a
pred Int
amount) (forall a. a -> List a -> List a
StrictList.Cons a
head List a
list) List a
tail
                  List a
_ -> forall {t} {a}.
(Ord t, Num t, Enum t) =>
t -> List a -> List a -> List a
buildFromSnocList Int
amount List a
list (forall a. List a -> List a
StrictList.reverse List a
snocList)
                else forall a b. a -> b -> a
const List a
list
            buildFromSnocList :: t -> List a -> List a -> List a
buildFromSnocList t
amount !List a
list =
              if t
amount forall a. Ord a => a -> a -> Bool
> t
0
                then \case
                  StrictList.Cons a
head List a
tail -> t -> List a -> List a -> List a
buildFromSnocList (forall a. Enum a => a -> a
pred t
amount) (forall a. a -> List a -> List a
StrictList.Cons a
head List a
list) List a
tail
                  List a
_ -> List a
list
                else forall a b. a -> b -> a
const List a
list
         in Int -> List a -> List a -> List a
buildFromConsList Int
amount forall a. List a
StrictList.Nil List a
consList
   in forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List a
newSnocList

-- |
-- \(\mathcal{O}(n)\).
-- Drop the specified amount of first elements.
drop :: Int -> Deque a -> Deque a
drop :: forall a. Int -> Deque a -> Deque a
drop Int
amount (Deque List a
consList List a
snocList) =
  let buildFromConsList :: Int -> List a -> Deque a
buildFromConsList Int
amount =
        if Int
amount forall a. Ord a => a -> a -> Bool
> Int
0
          then \case
            StrictList.Cons a
_ List a
tail -> Int -> List a -> Deque a
buildFromConsList (forall a. Enum a => a -> a
pred Int
amount) List a
tail
            List a
_ -> forall {t} {a}. (Ord t, Num t, Enum t) => t -> List a -> Deque a
buildFromSnocList Int
amount (forall a. List a -> List a
StrictList.reverse List a
snocList)
          else \List a
tail -> forall a. List a -> List a -> Deque a
Deque List a
tail List a
snocList
      buildFromSnocList :: t -> List a -> Deque a
buildFromSnocList t
amount =
        if t
amount forall a. Ord a => a -> a -> Bool
> t
0
          then \case
            StrictList.Cons a
_ List a
tail -> t -> List a -> Deque a
buildFromSnocList (forall a. Enum a => a -> a
pred t
amount) List a
tail
            List a
_ -> forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil forall a. List a
StrictList.Nil
          else \List a
tail -> forall a. List a -> List a -> Deque a
Deque List a
tail forall a. List a
StrictList.Nil
   in Int -> List a -> Deque a
buildFromConsList Int
amount List a
consList

-- |
-- \(\mathcal{O}(n)\).
-- Leave only the first elements satisfying the predicate.
{-# INLINE takeWhile #-}
takeWhile :: (a -> Bool) -> Deque a -> Deque a
takeWhile :: forall a. (a -> Bool) -> Deque a -> Deque a
takeWhile a -> Bool
predicate (Deque List a
consList List a
snocList) =
  let newConsList :: List a
newConsList =
        forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
          ( \a
a List a
nextState ->
              if a -> Bool
predicate a
a
                then forall a. a -> List a -> List a
StrictList.Cons a
a List a
nextState
                else forall a. List a
StrictList.Nil
          )
          (forall a. (a -> Bool) -> List a -> List a
StrictList.takeWhileFromEnding a -> Bool
predicate List a
snocList)
          List a
consList
   in forall a. List a -> List a -> Deque a
Deque List a
newConsList forall a. List a
StrictList.Nil

-- |
-- \(\mathcal{O}(n)\).
-- Drop the first elements satisfying the predicate.
{-# INLINE dropWhile #-}
dropWhile :: (a -> Bool) -> Deque a -> Deque a
dropWhile :: forall a. (a -> Bool) -> Deque a -> Deque a
dropWhile a -> Bool
predicate (Deque List a
consList List a
snocList) =
  let newConsList :: List a
newConsList = forall a. (a -> Bool) -> List a -> List a
StrictList.dropWhile a -> Bool
predicate List a
consList
   in case List a
newConsList of
        List a
StrictList.Nil -> forall a. List a -> List a -> Deque a
Deque (forall a. (a -> Bool) -> List a -> List a
StrictList.dropWhileFromEnding a -> Bool
predicate List a
snocList) forall a. List a
StrictList.Nil
        List a
_ -> forall a. List a -> List a -> Deque a
Deque List a
newConsList List a
snocList

-- |
-- \(\mathcal{O}(n)\).
-- Perform `takeWhile` and `dropWhile` in a single operation.
span :: (a -> Bool) -> Deque a -> (Deque a, Deque a)
span :: forall a. (a -> Bool) -> Deque a -> (Deque a, Deque a)
span a -> Bool
predicate (Deque List a
consList List a
snocList) = case forall a. (a -> Bool) -> List a -> (List a, List a)
StrictList.spanReversed a -> Bool
predicate List a
consList of
  (List a
consReversedPrefix, List a
consSuffix) ->
    if forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null List a
consSuffix
      then case forall a. (a -> Bool) -> List a -> (List a, List a)
StrictList.spanFromEnding a -> Bool
predicate List a
snocList of
        (List a
snocPrefix, List a
snocSuffix) ->
          let prefix :: Deque a
prefix = forall a. List a -> List a -> Deque a
Deque (forall a. List a -> List a -> List a
StrictList.prependReversed List a
consReversedPrefix List a
snocPrefix) forall a. List a
StrictList.Nil
              suffix :: Deque a
suffix = forall a. List a -> List a -> Deque a
Deque List a
snocSuffix forall a. List a
StrictList.Nil
           in (Deque a
prefix, Deque a
suffix)
      else
        let prefix :: Deque a
prefix = forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List a
consReversedPrefix
            suffix :: Deque a
suffix = forall a. List a -> List a -> Deque a
Deque List a
consSuffix List a
snocList
         in (Deque a
prefix, Deque a
suffix)

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the first element and deque without it if it's not empty.
{-# INLINE uncons #-}
uncons :: Deque a -> Maybe (a, Deque a)
uncons :: forall a. Deque a -> Maybe (a, Deque a)
uncons (Deque List a
consList List a
snocList) = case List a
consList of
  StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque List a
tail List a
snocList)
  List a
_ -> case forall a. List a -> List a
StrictList.reverse List a
snocList of
    StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque List a
tail forall a. List a
StrictList.Nil)
    List a
_ -> forall a. Maybe a
Nothing

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the last element and deque without it if it's not empty.
{-# INLINE unsnoc #-}
unsnoc :: Deque a -> Maybe (a, Deque a)
unsnoc :: forall a. Deque a -> Maybe (a, Deque a)
unsnoc (Deque List a
consList List a
snocList) = case List a
snocList of
  StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque List a
consList List a
tail)
  List a
_ -> case forall a. List a -> List a
StrictList.reverse List a
consList of
    StrictList.Cons a
head List a
tail -> forall a. a -> Maybe a
Just (a
head, forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List a
tail)
    List a
_ -> forall a. Maybe a
Nothing

-- |
-- \(\mathcal{O}(1)\).
-- Check whether deque is empty.
{-# INLINE null #-}
null :: Deque a -> Bool
null :: forall a. Deque a -> Bool
null = \case
  Deque List a
StrictList.Nil List a
StrictList.Nil -> Bool
True
  Deque a
_ -> Bool
False

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the first element if deque is not empty.
{-# INLINE head #-}
head :: Deque a -> Maybe a
head :: forall a. Deque a -> Maybe a
head (Deque List a
consList List a
snocList) = case List a
consList of
  StrictList.Cons a
head List a
_ -> forall a. a -> Maybe a
Just a
head
  List a
_ -> forall a. List a -> Maybe a
StrictList.last List a
snocList

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Get the last element if deque is not empty.
{-# INLINE last #-}
last :: Deque a -> Maybe a
last :: forall a. Deque a -> Maybe a
last (Deque List a
consList List a
snocList) = case List a
snocList of
  StrictList.Cons a
head List a
_ -> forall a. a -> Maybe a
Just a
head
  List a
_ -> forall a. List a -> Maybe a
StrictList.last List a
consList

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Keep all elements but the first one.
--
-- In case of empty deque returns an empty deque.
{-# INLINE tail #-}
tail :: Deque a -> Deque a
tail :: forall a. Deque a -> Deque a
tail (Deque List a
consList List a
snocList) = case List a
consList of
  StrictList.Cons a
_ List a
consListTail -> forall a. List a -> List a -> Deque a
Deque List a
consListTail List a
snocList
  List a
_ -> forall a. List a -> List a -> Deque a
Deque (forall a. List a -> List a
StrictList.initReversed List a
snocList) forall a. List a
StrictList.Nil

-- |
-- \(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
-- Keep all elements but the last one.
--
-- In case of empty deque returns an empty deque.
{-# INLINE init #-}
init :: Deque a -> Deque a
init :: forall a. Deque a -> Deque a
init (Deque List a
consList List a
snocList) = case List a
snocList of
  List a
StrictList.Nil -> forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil (forall a. List a -> List a
StrictList.initReversed List a
consList)
  List a
_ -> forall a. List a -> List a -> Deque a
Deque List a
consList (forall a. List a -> List a
StrictList.tail List a
snocList)

instance (Eq a) => Eq (Deque a) where
  == :: Deque a -> Deque a -> Bool
(==) Deque a
a Deque a
b = forall l. IsList l => l -> [Item l]
toList Deque a
a forall a. Eq a => a -> a -> Bool
== forall l. IsList l => l -> [Item l]
toList Deque a
b

instance (Show a) => Show (Deque a) where
  show :: Deque a -> [Char]
show = forall a. Show a => a -> [Char]
show forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. forall l. IsList l => l -> [Item l]
toList

instance IsList (Deque a) where
  type Item (Deque a) = a
  fromList :: [Item (Deque a)] -> Deque a
fromList [Item (Deque a)]
list = forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil (forall a. [a] -> List a
StrictList.fromListReversed [Item (Deque a)]
list)
  toList :: Deque a -> [Item (Deque a)]
toList (Deque List a
consList List a
snocList) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) (forall l. IsList l => l -> [Item l]
toList (forall a. List a -> List a
StrictList.reverse List a
snocList)) List a
consList

instance Semigroup (Deque a) where
  <> :: Deque a -> Deque a -> Deque a
(<>) (Deque List a
consList1 List a
snocList1) (Deque List a
consList2 List a
snocList2) =
    let consList :: List a
consList = List a
consList1
        snocList :: List a
snocList = List a
snocList2 forall a. Semigroup a => a -> a -> a
<> forall a. List a -> List a -> List a
StrictList.prependReversed List a
consList2 List a
snocList1
     in forall a. List a -> List a -> Deque a
Deque List a
consList List a
snocList

instance Monoid (Deque a) where
  mempty :: Deque a
mempty = forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil forall a. List a
StrictList.Nil
  mappend :: Deque a -> Deque a -> Deque a
mappend = forall a. Semigroup a => a -> a -> a
(<>)

deriving instance Functor Deque

instance Foldable Deque where
  foldr :: forall a b. (a -> b -> b) -> b -> Deque a -> b
foldr a -> b -> b
step b
init (Deque List a
consList List a
snocList) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step (forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
step b
init (forall a. List a -> List a
StrictList.reverse List a
snocList)) List a
consList
  foldl' :: forall b a. (b -> a -> b) -> b -> Deque a -> b
foldl' b -> a -> b
step b
init (Deque List a
consList List a
snocList) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
step b
init List a
consList) (forall a. List a -> List a
StrictList.reverse List a
snocList)

instance Traversable Deque where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Deque a -> f (Deque b)
traverse a -> f b
f (Deque List a
cs List a
ss) =
    (\List b
cs' List b
ss' -> forall a. List a -> List a -> Deque a
Deque List b
cs' (forall a. List a -> List a
StrictList.reverse List b
ss')) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f List a
cs forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f (forall a. List a -> List a
StrictList.reverse List a
ss)

instance Applicative Deque where
  pure :: forall a. a -> Deque a
pure a
a = forall a. List a -> List a -> Deque a
Deque (forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a) forall a. List a
StrictList.Nil
  <*> :: forall a b. Deque (a -> b) -> Deque a -> Deque b
(<*>) (Deque List (a -> b)
fnConsList List (a -> b)
fnSnocList) (Deque List a
argConsList List a
argSnocList) =
    let snocList :: List b
snocList =
          let fnStep :: List b -> (a -> b) -> List b
fnStep List b
resultSnocList a -> b
fn =
                let argStep :: List b -> a -> List b
argStep List b
resultSnocList a
arg = forall a. a -> List a -> List a
StrictList.Cons (a -> b
fn a
arg) List b
resultSnocList
                 in forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
argStep (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
argStep List b
resultSnocList List a
argConsList) (forall a. List a -> List a
StrictList.reverse List a
argSnocList)
           in forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> (a -> b) -> List b
fnStep (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> (a -> b) -> List b
fnStep forall a. List a
StrictList.Nil List (a -> b)
fnConsList) (forall a. List a -> List a
StrictList.reverse List (a -> b)
fnSnocList)
     in forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List b
snocList

instance Monad Deque where
  return :: forall a. a -> Deque a
return = forall (f :: * -> *) a. Applicative f => a -> f a
pure
  >>= :: forall a b. Deque a -> (a -> Deque b) -> Deque b
(>>=) (Deque List a
aConsList List a
aSnocList) a -> Deque b
k =
    let snocList :: List b
snocList =
          let aStep :: List b -> a -> List b
aStep List b
accBSnocList a
a = case a -> Deque b
k a
a of
                Deque List b
bConsList List b
bSnocList -> forall a. List a -> List a -> List a
StrictList.prependReversed List b
bConsList (List b
bSnocList forall a. Semigroup a => a -> a -> a
<> List b
accBSnocList)
           in forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
aStep (forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' List b -> a -> List b
aStep forall a. List a
StrictList.Nil List a
aConsList) (forall a. List a -> List a
StrictList.reverse List a
aSnocList)
     in forall a. List a -> List a -> Deque a
Deque forall a. List a
StrictList.Nil List b
snocList
#if !(MIN_VERSION_base(4,13,0))
  fail = const mempty
#endif

instance Alternative Deque where
  empty :: forall a. Deque a
empty = forall a. Monoid a => a
mempty
  <|> :: forall a. Deque a -> Deque a -> Deque a
(<|>) = forall a. Monoid a => a -> a -> a
mappend

instance MonadPlus Deque where
  mzero :: forall a. Deque a
mzero = forall (f :: * -> *) a. Alternative f => f a
empty
  mplus :: forall a. Deque a -> Deque a -> Deque a
mplus = forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)

instance MonadFail Deque where
  fail :: forall a. [Char] -> Deque a
fail = forall a b. a -> b -> a
const forall a. Monoid a => a
mempty

deriving instance Generic (Deque a)

deriving instance Generic1 Deque

instance (Hashable a) => Hashable (Deque a)

instance (NFData a) => NFData (Deque a)

instance NFData1 Deque