module Data.Stack ( Stack
                  , empty
                  , size
                  , push, push'
                  , peek
                  , pop, pop_, _pop
                  , turn
                  , null
                  , fromList, toList
                  , over, under
                  ) where

import qualified Data.Sequence as S
import qualified Data.Foldable as F
import           Prelude                hiding (null)

data Stack a = Stack (S.Seq a) deriving (Eq, Read, Show)

-- | returns the empty stack
-- | O(1)
empty :: Stack a
empty = Stack S.empty

-- | returns the stack size
-- | O(1)
size :: Stack a -> Int
size (Stack items) = S.length items

-- | push an element on the stack
-- | O(1)
push :: Stack a -> a -> Stack a
push (Stack items) item = Stack (item S.<| items)

-- | push with its arguments flipped
-- | O(1)
push' :: a -> Stack a -> Stack a
push' = flip push

-- | returns the topmost element
-- | O(1)
peek :: Stack a -> Maybe a
peek (Stack items) = items S.!? 0

-- | returns the topmost element or nothing and the new stack
-- | O(1)
pop :: Stack a -> (Stack a, Maybe a)
pop (Stack items) = (Stack $ S.drop 1 items, items S.!? 0)

-- | return the stack without the topmost element
-- | O(1)
pop_ :: Stack a -> (Stack a)
pop_ stack = fst $ pop stack

-- | returns the topmost element or nothing
-- | O(1)
_pop :: Stack a -> Maybe a
_pop stack = snd $ pop stack

-- | turns the stack upside down
-- | O(n)
turn :: Stack a -> Stack a
turn (Stack items) = Stack (S.reverse items)

-- | returns true if it is the empty stack
-- | O(1)
null :: Stack a -> Bool
null (Stack items) = S.null items

-- | creates a stack from a list
-- | O(n)
fromList :: [a] -> Stack a
fromList list = Stack $ S.fromList list

-- | returns a list from the stack
-- | O(n)
toList :: Stack a -> [a]
toList (Stack items) = F.toList items

-- | puts the first stack onto the second stack
-- | O(log(min(a,b)))
over :: Stack a -> Stack a -> Stack a
(Stack a) `over` (Stack b) = Stack (a S.>< b)

-- | puts the first stack under the second stack
-- | O(log(min(a,b)))
under :: Stack a -> Stack a -> Stack a
(Stack a) `under` (Stack b) = Stack (b S.>< a)