7.hs

data Deque a = Deque [a] [a] deriving (Show)

-- Íà÷àëî ïåðâîãî ñïèñêà - ëåâûé êîíåö î÷åðåäè.
-- Êîíåö ïåðâîãî ñïèñêà ~ ñåðåäèíà î÷åðåäè ñëåâà.
-- Íà÷àëî âòîðîãî ñïèñêà - ïðàâûé êîíåö î÷åðåäè.
-- Êîíåö âòîðîãî ñïèñêà ~ ñåðåäèíà î÷åðåäè ñïðàâà.

-- Òàêèì îáðàçîì append è appendLeft âñåãäà O(1), ò.ê. (:) - O(1).
-- pop è popLeft ïî÷òè âñåãäà O(1) ïî òåì æå ïðè÷èíàì, êðîìå ñëó÷àÿ,
-- êîãäà îäèí èç ñïèñêîâ îïóñòååò, à â äðóãîì áóäåò áîëüøå îäíîãî ýëåìåíòà.

append :: Deque a -> a -> Deque a
append (Deque in_ out) v = Deque in_ (v:out)


appendLeft :: Deque a -> a -> Deque a
appendLeft (Deque in_ out) v = Deque (v:in_) out


halve :: [a] -> ([a], [a])
halve lst = splitAt (length lst `div` 2) lst

equalize :: Deque a -> Deque a
equalize (Deque in_ []) = Deque (fst half) (reverse $ snd half) where
  half = halve in_
equalize (Deque [] out) = Deque (reverse $ snd half) (fst half) where
  half = halve out


pop :: Deque a -> (Deque a, a)
pop (Deque [] []) = error "Deque is empty"
pop (Deque in_ (h:t)) = (Deque in_ t, h)
-- Ñëó÷àè, êîãäà ïðàâûé ñïèñîê îïóñòååò
pop (Deque (h:[]) []) = (Deque [] [], h)
pop deque@(Deque in_ []) = pop $ equalize deque

popLeft :: Deque a -> (Deque a, a)
popLeft (Deque [] []) = error "Deque is empty"
popLeft (Deque (h:t) out) = (Deque t out, h)
-- Ñëó÷àè, êîãäà ëåâûé ñïèñîê îïóñòååò
popLeft (Deque [] (h:[])) = (Deque [] [], h)
popLeft deque@(Deque [] out) = popLeft $ equalize deque

-- Ìåòîä áàíêèðà:
--   Çàðàáàòûâàåì 1$ çà êàæäîå äîáàâëåíèå.
--   Ïðè óäàëåíèè èç äåêè ìîæåò âîçíèêíóòü ñëó÷àé, êîãäà íóæíûé ñïèñîê îïóñòåë.
--   Òîãäà íóæíî ïðîèçâîäèòü "ïåðåêèäûâàíèå".
--   Ïåðåêèäûâàåì â ýòîì ñëó÷àå N/2, ãäå N ìû óæå çàðàáîòàëè íà äîáàâëåíèÿõ.
--   Ñîîòâåòñòâåííî, àìîðòèçèðîâàííàÿ ñëîæíîñòü âñåõ îïåðàöèé íàä äåêîé - êîíñòàíòà.
--
-- Ìåòîä ôèçèêà:
--   Ïîòåíöèàë - ñóììà äëèí ñïèñêîâ.
--   Äîáàâëåíèå óâåëè÷èâàåò ïîòåíöèàë íà 1.
--   Óäàëåíèå áåç "ïåðåêèäûâàíèÿ" íå ìåíÿåò ïîòåíöèàë.
--   Óäàëåíèå ñ "ïåðåêèäûâàíèåì" óìåíüøàåò ïîòåíöèàë íà N è çàíèìàåò O(N),
--   íî ñëó÷àåòñÿ íå ÷àùå ÷åì êàæäóþ N/2 îïåðàöèþ.