-- | This module implements a customized stack for the Piet programming
-- language.
--
-- In addition to the common 'push', 'pop' and 'top' operations, the
-- a 'RollStack' provides a 'roll' (see below) command, which is the
-- reason for using a 'Seq'uence and not a list as underlying data
-- structure.
--
-- Whenever the /O/-notation is used, /n/ describes the number of elements
-- within the stack.
module Data.RollStack
	(
	-- * Stack type
	  RollStack
	
	-- * Query
	, isEmpty
	, top
	
	-- * Construction
	, Data.RollStack.empty
	, Data.RollStack.singleton
	
	-- * Insert delete and roll operations
	, push
	, pop
	, roll

	-- * List conversion
	, Data.RollStack.fromList
	, Data.RollStack.toList
	) where

import Data.Foldable as Foldable
import Data.Maybe
import Data.Sequence  as Seq
import Prelude hiding (foldl, foldr)

-- | The 'RollStack' type.
newtype RollStack a
	= Stack (Seq a)

instance (Show a) => Show (RollStack a) where
	show (Stack xs) = show xs

instance (Eq a) => Eq (RollStack a) where
	(Stack xs) == (Stack ys) = xs == ys

instance (Ord a) => Ord (RollStack a) where
	compare (Stack xs) (Stack ys) = compare xs ys

instance Functor RollStack where
	fmap f (Stack xs) = Stack $ fmap f xs

instance Foldable RollStack where
	fold      (Stack xs) = fold      xs
	foldMap f (Stack xs) = foldMap f xs
	foldr f z (Stack xs) = foldr f z xs
	foldl f z (Stack xs) = foldl f z xs

-- | /O(1)/. Tests, if a 'RollStack' is empty.
isEmpty :: RollStack a -> Bool
isEmpty = isNothing . top

-- | /O(1)/. Looks at the top element of the 'RollStack'. Returns
-- 'Nothing' if the stack is empty.
top :: RollStack a -> Maybe a
top stack = fst `fmap` pop stack

-- | /O(1)/. Construct an empty 'Stack'.
empty :: RollStack a
empty = Stack Seq.empty

-- | /O(1)/. Construct a 'RollStack' containing a single element.
singleton :: a -> RollStack a
singleton = Stack . Seq.singleton

-- | /O(1)/. Push an element on the 'RollStack'.
push :: a -> RollStack a -> RollStack a
push x (Stack xs) = Stack (x <| xs)

-- | /O(1)/. Pop the top element from the 'RollStack' if it is not empty.
pop :: RollStack a -> Maybe (a, RollStack a)
pop (Stack xs) = case viewl xs of
	EmptyL   -> fail "empty RollStack"
	y :< ys -> return (y, Stack ys)

-- | /O(log(n))/. A single roll to depth /n/ is defined as burying the top
-- value on the stack /n/ deep and bringing all values above it up by 1
-- place. A negative number of rolls rolls in the opposite direction. A
-- negative depth results in an 'error'.
roll :: Int		-- ^ Number of rolls
	-> Int		-- ^ Depth
	-> RollStack a	-- ^ Original 'RollStack'
	-> RollStack a	-- ^ Rotated 'RollStack'
roll rolls depth unmodified@(Stack xs)
	| depth < 0                = error $ "negative depth in Data.RollStack.roll: " ++ show depth
	| rolls == 0 || depth == 0 = unmodified
	| otherwise                = let
		(xs1, xs2)   = Seq.splitAt depth xs
		(xs1a, xs1b) = Seq.splitAt (rolls `mod` depth) xs1
		in
		Stack (xs1b >< xs1a >< xs2)

-- | /O(n)/. Convert a list into a 'Stack'. The list's head will be
-- the first element of the 'Stack'
fromList :: [a] -> RollStack a
fromList = Stack . Seq.fromList

-- | /O(n)/. Convert a 'RollStack' to a list. The 'top' of the 'RollStack'
-- will be the list's head.
toList :: RollStack a -> [a]
toList (Stack xs) = Foldable.toList xs