queuelike-1.0.1: Data/Queue/Stack.hs

{-# LANGUAGE NamedFieldPuns, GeneralizedNewtypeDeriving, TypeFamilies #-}

-- | A basic implementation of a stack implementing the 'Queue' abstraction.
module Data.Queue.Stack (Stack) where

import Data.Queue.Class
import Data.Maybe

data Stack e = S {elts :: {-# UNPACK #-} !Int, stk :: [e]}

instance IQueue (Stack e) where
	type QueueKey (Stack e) = e
	empty = S 0 []
	insert x (S n stk) = S (n+1) (x:stk)

	S n1 s1 `merge` S n2 s2 = S (n1 + n2) (reverse s2 ++ s1)

	extract (S (n+1) (x:xs)) = Just (x, S n xs)
	extract _ = Nothing
	size = elts
	toList = stk