-- fronty

-- invariant -- bqFront == [] => bqBack == []
data BQ a = BQ {bqFront::[a], bqBack::[a]} deriving (Show)

bqNew::[a]->[a]->BQ a
bqNew [] back = BQ {bqFront = reverse back, bqBack = []}
bqNew front back = BQ {bqFront = front, bqBack = back}

bqEmpty::BQ a
bqEmpty = BQ {bqFront = [], bqBack = []}

bqHead::BQ a -> a
bqHead q = head (bqFront q)

bqTail::BQ a -> BQ a
bqTail q = bqNew (tail $ bqFront q) (bqBack q)

bqSnoc::BQ a -> a -> BQ a
bqSnoc q e = bqNew (bqFront q) (e : bqBack q)

-- amortizovane O(1) pri pristupech pouze k nejnovejsi verzi
-- selze pro pristupy ke starsim verzim
-- bqHead (bqTail q) muze mit linearni casovou slozitost, a muzeme
-- ho libovolnekrat opakovat

-- nutno drive obracet frontu; invariant -- |F| >= |B|

data ABQ a = ABQ {abqFront::[a], abqFLen::Int, abqBack::[a], abqBLen::Int} deriving (Show)

abqEmpty::ABQ a
abqEmpty = ABQ {abqFront = [], abqFLen = 0, abqBack = [], abqBLen = 0}

abqSnoc::ABQ a -> a -> ABQ a
abqSnoc q e = abqBalance q{abqBack = e : abqBack q, abqBLen = abqBLen q + 1}

abqHead::ABQ a -> a
abqHead q = head (abqFront q)

abqTail::ABQ a -> ABQ a
abqTail q = abqBalance q{abqFront = tail (abqFront q), abqFLen = abqFLen q - 1} 

abqBalance::ABQ a -> ABQ a
abqBalance q
  | abqFLen q >= abqBLen q = q
  | otherwise = ABQ {abqFront = abqFront q ++ reverse (abqBack q),
                     abqFLen = abqFLen q + abqBLen q,
		     abqBack = [], abqBLen = 0}

-- jina varianta, pro analyzu pres potencialy
-- invarianty -- |F|>=|B|, W == [] => F == []
-- W obsahuje pocatecni usek F, az pred operaci otoceni

data FQ a = FQ {fqW::[a], fqF::[a], fqFL::Int, fqB::[a], fqBL::Int} deriving (Show)

fqEmpty::FQ a
fqEmpty = FQ {fqW=[], fqF=[], fqFL=0, fqB=[], fqBL=0}

fqSnoc::FQ a->a->FQ a
fqSnoc q e = fqBalance q{fqB=e:fqB q, fqBL = fqBL q + 1}

fqHead::FQ a->a
fqHead q = head (fqW q)

fqTail::FQ a->FQ a
fqTail q = fqBalance q{fqW = tail (fqW q), fqF = tail (fqF q), fqFL = fqFL q - 1}

fqBalance::FQ a->FQ a
fqBalance q = fqBalanceW $ fqBalanceB q

fqBalanceB::FQ a->FQ a
fqBalanceB q
  | fqFL q >= fqBL q = q
  | otherwise = let w = fqF q in FQ {fqW = w, fqF = w ++ reverse (fqB q),
                                     fqFL = fqFL q + fqBL q,
                                     fqB=[], fqBL=0}

fqBalanceW::FQ a->FQ a
fqBalanceW q
  | null (fqW q) = q{fqW = fqF q}
  | otherwise = q

-- worst-case omezeni casove slozitosti
-- prvni krok -- nahradit reverse + append operaci, ktera se da vykonavat postupne

-- rotate f b a = f ++ reverse b ++ a
-- pouzivame jen v situaci, kdyz |f| = |b| - 1
-- f ++ reverse b == rotate f b []
rotate [] [y] a = y : a
rotate (x:xs) (y:ys) a = x : rotate xs ys (y : a)

-- invariant: |S| = |F| - |B| (implikuje |F| >= |B|)
-- S je rozvrh pro vyhodnocovani prvku F (obsahuje jeste nevyhodnoceny sufix F)
data RT a = RT {rtF::[a], rtB::[a], rtS::[a]} deriving (Show)

rtEmpty::RT a
rtEmpty = RT {rtF = [], rtB = [], rtS = []}

rtSnoc::RT a -> a -> RT a
rtSnoc q e = rtBalance q{rtB = e : rtB q}

rtHead::RT a -> a
rtHead q = head (rtF q)

rtTail::RT a -> RT a
rtTail q = rtBalance q{rtF = tail (rtF q)} 

-- v tomto okamziku |S| = |F| - |B| + 1
rtBalance::RT a -> RT a
rtBalance q
  -- testovani S == [] vynuti vyhodnoceni prvniho konstruktoru v S
  -- pokud S = [], pak |F| = |B| - 1 a muzeme prerotovat prvky
  | null (rtS q) = let s = rotate (rtF q) (rtB q) []
                    in RT{rtF = s, rtB = [], rtS = s}
  | otherwise = q{rtS = tail (rtS q)}

-- podobne lze implementovat oboustranne fronty -- invarianty
-- |F| <= 2|B| + 1, |B| <= 2|F| + 1