34 lines
837 B
Haskell
34 lines
837 B
Haskell
module Queue2 where
|
|
|
|
import Prelude hiding (length)
|
|
|
|
-- Invariant: |R| <= |L|
|
|
-- Invariant is preserved via the makeQ function
|
|
|
|
data Queue a = Q { left :: [a]
|
|
, leftLen :: !Int
|
|
, right :: [a]
|
|
, rightLen :: !Int
|
|
} deriving (Show, Eq)
|
|
|
|
empty :: Queue a
|
|
empty = Q [] 0 [] 0
|
|
|
|
length :: Queue a -> Int
|
|
length (Q _ ll _ rl) = ll + rl
|
|
|
|
insert :: a -> Queue a -> Queue a
|
|
insert e (Q l ll r rl) = makeQ (Q l ll (e : r) (rl + 1))
|
|
|
|
remove :: Queue a -> (a, Queue a)
|
|
remove (Q l ll r rl) = (head l, makeQ (Q (tail l) (ll - 1) r rl))
|
|
|
|
makeQ :: Queue a -> Queue a
|
|
makeQ q@(Q l ll r rl)
|
|
| rl <= ll = q
|
|
| otherwise = Q (rot l r []) (ll + rl) [] 0
|
|
|
|
rot :: [a] -> [a] -> [a] -> [a]
|
|
rot [] r a = head r : a
|
|
rot l r a = head l : rot (tail l) (tail r) (head r : a)
|