{-|
Strict Deque API lifted to a State monad, \"mtl\"-style.
-}
module Deque.Strict.State
where

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


{-|
\(\mathcal{O}(n)\).
Modify each element of the queue.
-}
map :: MonadState (Deque a) m => (a -> a) -> m ()
map :: (a -> a) -> m ()
map a -> a
f = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((a -> a) -> Deque a -> Deque a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
f)

{-|
\(\mathcal{O}(n)\).
Add elements to the begginning.
-}
prepend :: MonadState (Deque a) m => Deque a -> m ()
prepend :: Deque a -> m ()
prepend Deque a
deque = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify (Deque a
deque Deque a -> Deque a -> Deque a
forall a. Semigroup a => a -> a -> a
<>)

{-|
\(\mathcal{O}(n)\).
Add elements to the ending.
-}
append :: MonadState (Deque a) m => Deque a -> m ()
append :: Deque a -> m ()
append Deque a
deque = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify (Deque a -> Deque a -> Deque a
forall a. Semigroup a => a -> a -> a
<> Deque a
deque)

{-|
\(\mathcal{O}(1)\).
Add element in the beginning.
-}
cons :: MonadState (Deque a) m => a -> m ()
cons :: a -> m ()
cons a
a = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify (a -> Deque a -> Deque a
forall a. a -> Deque a -> Deque a
Deque.cons a
a)

{-|
\(\mathcal{O}(1)\).
Add element in the ending.
-}
snoc :: MonadState (Deque a) m => a -> m ()
snoc :: a -> m ()
snoc a
a = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify (a -> Deque a -> Deque a
forall a. a -> Deque a -> Deque a
Deque.snoc a
a)

{-|
\(\mathcal{O}(1)\).
Reverse the deque.
-}
reverse :: MonadState (Deque a) m => m ()
reverse :: m ()
reverse = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify Deque a -> Deque a
forall a. Deque a -> Deque a
Deque.reverse

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Move the first element to the end.
-}
shiftLeft :: MonadState (Deque a) m => m ()
shiftLeft :: m ()
shiftLeft = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify Deque a -> Deque a
forall a. Deque a -> Deque a
Deque.shiftLeft

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Move the last element to the beginning.
-}
shiftRight :: MonadState (Deque a) m => m ()
shiftRight :: m ()
shiftRight = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify Deque a -> Deque a
forall a. Deque a -> Deque a
Deque.shiftRight

{-|
\(\mathcal{O}(n)\).
Leave only the elements satisfying the predicate.
-}
filter :: MonadState (Deque a) m => (a -> Bool) -> m ()
filter :: (a -> Bool) -> m ()
filter a -> Bool
predicate = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((a -> Bool) -> Deque a -> Deque a
forall a. (a -> Bool) -> Deque a -> Deque a
Deque.filter a -> Bool
predicate)

{-|
\(\mathcal{O}(n)\).
Leave only the specified amount of first elements.
-}
take :: MonadState (Deque a) m => Int -> m ()
take :: Int -> m ()
take = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Deque a -> Deque a) -> m ())
-> (Int -> Deque a -> Deque a) -> Int -> m ()
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Int -> Deque a -> Deque a
forall a. Int -> Deque a -> Deque a
Deque.take

{-|
\(\mathcal{O}(n)\).
Drop the specified amount of first elements.
-}
drop :: MonadState (Deque a) m => Int -> m ()
drop :: Int -> m ()
drop = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((Deque a -> Deque a) -> m ())
-> (Int -> Deque a -> Deque a) -> Int -> m ()
forall k (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Int -> Deque a -> Deque a
forall a. Int -> Deque a -> Deque a
Deque.drop

{-|
\(\mathcal{O}(n)\).
Leave only the first elements satisfying the predicate.
-}
takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()
takeWhile :: (a -> Bool) -> m ()
takeWhile a -> Bool
predicate = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((a -> Bool) -> Deque a -> Deque a
forall a. (a -> Bool) -> Deque a -> Deque a
Deque.takeWhile a -> Bool
predicate)

{-|
\(\mathcal{O}(n)\).
Drop the first elements satisfying the predicate.
-}
dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()
dropWhile :: (a -> Bool) -> m ()
dropWhile a -> Bool
predicate = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify ((a -> Bool) -> Deque a -> Deque a
forall a. (a -> Bool) -> Deque a -> Deque a
Deque.dropWhile a -> Bool
predicate)

{-|
\(\mathcal{O}(n)\).
Return the first elements satisfying the predicate, removing them from the state.
-}
span :: MonadState (Deque a) m => (a -> Bool) -> m (Deque a)
span :: (a -> Bool) -> m (Deque a)
span a -> Bool
predicate = (Deque a -> (Deque a, Deque a)) -> m (Deque a)
forall s (m :: * -> *) a. MonadState s m => (s -> (a, s)) -> m a
state ((a -> Bool) -> Deque a -> (Deque a, Deque a)
forall a. (a -> Bool) -> Deque a -> (Deque a, Deque a)
Deque.span a -> Bool
predicate)

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Get the first element if deque is not empty,
removing the element.
-}
uncons :: MonadState (Deque a) m => m (Maybe a)
uncons :: m (Maybe a)
uncons = (Deque a -> (Maybe a, Deque a)) -> m (Maybe a)
forall s (m :: * -> *) a. MonadState s m => (s -> (a, s)) -> m a
state (\ Deque a
deque -> case Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
Deque.uncons Deque a
deque of
  Maybe (a, Deque a)
Nothing -> (Maybe a
forall a. Maybe a
Nothing, Deque a
deque)
  Just (a
a, Deque a
newDeque) -> (a -> Maybe a
forall a. a -> Maybe a
Just a
a, Deque a
newDeque))

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Get the last element if deque is not empty,
removing the element.
-}
unsnoc :: MonadState (Deque a) m => m (Maybe a)
unsnoc :: m (Maybe a)
unsnoc = (Deque a -> (Maybe a, Deque a)) -> m (Maybe a)
forall s (m :: * -> *) a. MonadState s m => (s -> (a, s)) -> m a
state (\ Deque a
deque -> case Deque a -> Maybe (a, Deque a)
forall a. Deque a -> Maybe (a, Deque a)
Deque.unsnoc Deque a
deque of
  Maybe (a, Deque a)
Nothing -> (Maybe a
forall a. Maybe a
Nothing, Deque a
deque)
  Just (a
a, Deque a
newDeque) -> (a -> Maybe a
forall a. a -> Maybe a
Just a
a, Deque a
newDeque))

{-|
\(\mathcal{O}(1)\). 
Check whether deque is empty.
-}
null :: MonadState (Deque a) m => m Bool
null :: m Bool
null = (Deque a -> Bool) -> m Bool
forall s (m :: * -> *) a. MonadState s m => (s -> a) -> m a
gets Deque a -> Bool
forall a. Deque a -> Bool
Deque.null

{-|
\(\mathcal{O}(1)\). 
Check whether deque is empty.
-}
length :: MonadState (Deque a) m => m Int
length :: m Int
length = (Deque a -> Int) -> m Int
forall s (m :: * -> *) a. MonadState s m => (s -> a) -> m a
gets Deque a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
Prelude.length

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Get the first element if deque is not empty.
-}
head :: MonadState (Deque a) m => m (Maybe a)
head :: m (Maybe a)
head = (Deque a -> Maybe a) -> m (Maybe a)
forall s (m :: * -> *) a. MonadState s m => (s -> a) -> m a
gets Deque a -> Maybe a
forall a. Deque a -> Maybe a
Deque.head

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Get the last element if deque is not empty.
-}
last :: MonadState (Deque a) m => m (Maybe a)
last :: m (Maybe a)
last = (Deque a -> Maybe a) -> m (Maybe a)
forall s (m :: * -> *) a. MonadState s m => (s -> a) -> m a
gets Deque a -> Maybe a
forall a. Deque a -> Maybe a
Deque.last

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Keep all elements but the first one.
-}
tail :: MonadState (Deque a) m => m ()
tail :: m ()
tail = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify Deque a -> Deque a
forall a. Deque a -> Deque a
Deque.tail

{-|
\(\mathcal{O}(1)\), occasionally \(\mathcal{O}(n)\).
Keep all elements but the last one.
-}
init :: MonadState (Deque a) m => m ()
init :: m ()
init = (Deque a -> Deque a) -> m ()
forall s (m :: * -> *). MonadState s m => (s -> s) -> m ()
modify Deque a -> Deque a
forall a. Deque a -> Deque a
Deque.init