    {-|
    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

    {-|
    /O(n)/.
    Modify each element of the queue.
    -}
    map :: MonadState (Deque a) m => (a -> a) -> m ()
    map :: (a -> a) -> m ()
    map f :: 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)

    {-|
    /O(n)/.
    Add elements to the begginning.
    -}
    prepend :: MonadState (Deque a) m => Deque a -> m ()
    prepend :: Deque a -> m ()
    prepend deque :: 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
    <>)

    {-|
    /O(n)/.
    Add elements to the ending.
    -}
    append :: MonadState (Deque a) m => Deque a -> m ()
    append :: Deque a -> m ()
    append deque :: 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)

    {-|
    /O(1)/.
    Add element in the beginning.
    -}
    cons :: MonadState (Deque a) m => a -> m ()
    cons :: a -> m ()
    cons a :: 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)

    {-|
    /O(1)/.
    Add element in the ending.
    -}
    snoc :: MonadState (Deque a) m => a -> m ()
    snoc :: a -> m ()
    snoc a :: 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)

    {-|
    /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

    {-|
    /O(1)/, occasionally /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

    {-|
    /O(1)/, occasionally /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

    {-|
    /O(n)/.
    Leave only the elements satisfying the predicate.
    -}
    filter :: MonadState (Deque a) m => (a -> Bool) -> m ()
    filter :: (a -> Bool) -> m ()
    filter predicate :: 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)

    {-|
    /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

    {-|
    /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

    {-|
    /O(n)/.
    Leave only the first elements satisfying the predicate.
    -}
    takeWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()
    takeWhile :: (a -> Bool) -> m ()
    takeWhile predicate :: 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)

    {-|
    /O(n)/.
    Drop the first elements satisfying the predicate.
    -}
    dropWhile :: MonadState (Deque a) m => (a -> Bool) -> m ()
    dropWhile :: (a -> Bool) -> m ()
    dropWhile predicate :: 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)

    {-|
    /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 predicate :: 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)

    {-|
    /O(1)/, occasionally /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 :: Deque a
    deque -> case Deque a -> Maybe (a, Deque a)
    forall a. Deque a -> Maybe (a, Deque a)
    Deque.uncons Deque a
    deque of
      Nothing -> (Maybe a
    forall a. Maybe a
    Nothing, Deque a
    deque)
      Just (a :: a
    a, newDeque :: Deque a
    newDeque) -> (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    a, Deque a
    newDeque))

    {-|
    /O(1)/, occasionally /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 :: Deque a
    deque -> case Deque a -> Maybe (a, Deque a)
    forall a. Deque a -> Maybe (a, Deque a)
    Deque.unsnoc Deque a
    deque of
      Nothing -> (Maybe a
    forall a. Maybe a
    Nothing, Deque a
    deque)
      Just (a :: a
    a, newDeque :: Deque a
    newDeque) -> (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    a, Deque a
    newDeque))

    {-|
    /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

    {-|
    /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

    {-|
    /O(1)/, occasionally /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

    {-|
    /O(1)/, occasionally /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

    {-|
    /O(1)/, occasionally /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

    {-|
    /O(1)/, occasionally /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