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)