module Network.QUIC.Stream.Skew (
    Skew (..),
    empty,
    insert,
    deleteMin,
    deleteMinIf,
    --  , deleteMin'
    --  , showSkew
) where

import Data.Maybe
import Data.Sequence (Seq, (><))
import qualified Data.Sequence as Seq
import Prelude hiding (minimum)

import Network.QUIC.Stream.Frag

----------------------------------------------------------------

data Skew a = Leaf | Node (Skew a) (Seq a) (Skew a) deriving (Int -> Skew a -> ShowS
forall a. Show a => Int -> Skew a -> ShowS
forall a. Show a => [Skew a] -> ShowS
forall a. Show a => Skew a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Skew a] -> ShowS
$cshowList :: forall a. Show a => [Skew a] -> ShowS
show :: Skew a -> String
$cshow :: forall a. Show a => Skew a -> String
showsPrec :: Int -> Skew a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Skew a -> ShowS
Show)

empty :: Skew a
empty :: forall a. Skew a
empty = forall a. Skew a
Leaf

----------------------------------------------------------------

-- | Insertion. Worst-case: O(N), amortized: O(log N).
insert :: Frag a => a -> Skew a -> Skew a
insert :: forall a. Frag a => a -> Skew a -> Skew a
insert a
x Skew a
t = forall a. Frag a => Skew a -> Skew a -> Skew a
merge (forall a. Skew a -> Seq a -> Skew a -> Skew a
Node forall a. Skew a
Leaf (forall a. a -> Seq a
Seq.singleton a
x) forall a. Skew a
Leaf) Skew a
t

----------------------------------------------------------------

-- | Finding the minimum element. Worst-case: O(1).
minimum :: Skew a -> Maybe (Seq a)
minimum :: forall a. Skew a -> Maybe (Seq a)
minimum Skew a
Leaf = forall a. Maybe a
Nothing
minimum (Node Skew a
_ Seq a
f Skew a
_) = forall a. a -> Maybe a
Just Seq a
f

----------------------------------------------------------------

-- | Deleting the minimum element. Worst-case: O(N), amortized: O(log N).
deleteMin' :: Frag a => Skew a -> Skew a
deleteMin' :: forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
Leaf = forall a. Skew a
Leaf
deleteMin' (Node Skew a
l Seq a
_ Skew a
r) = forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
l Skew a
r

deleteMin :: Frag a => Skew a -> (Skew a, Maybe (Seq a))
deleteMin :: forall a. Frag a => Skew a -> (Skew a, Maybe (Seq a))
deleteMin Skew a
h = (forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, forall a. Skew a -> Maybe (Seq a)
minimum Skew a
h)

deleteMinIf :: Frag a => Int -> Skew a -> (Skew a, Maybe (Seq a))
deleteMinIf :: forall a. Frag a => Int -> Skew a -> (Skew a, Maybe (Seq a))
deleteMinIf Int
off Skew a
h = case forall a. Skew a -> Maybe (Seq a)
minimum Skew a
h of
    jf :: Maybe (Seq a)
jf@(Just Seq a
f)
        | forall a. Frag a => a -> Int
currOff Seq a
f forall a. Eq a => a -> a -> Bool
== Int
off -> (forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, Maybe (Seq a)
jf)
        | forall a. Frag a => a -> Int
currOff Seq a
f forall a. Ord a => a -> a -> Bool
< Int
off Bool -> Bool -> Bool
&& Int
off forall a. Ord a => a -> a -> Bool
< forall a. Frag a => a -> Int
nextOff Seq a
f -> (forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, forall a. Frag a => Int -> a -> a
shrink Int
off forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (Seq a)
jf)
        | forall a. Frag a => a -> Int
nextOff Seq a
f forall a. Ord a => a -> a -> Bool
<= Int
off -> (forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, forall a. Maybe a
Nothing)
    Maybe (Seq a)
_ -> (Skew a
h, forall a. Maybe a
Nothing)

----------------------------------------------------------------

-- | Merging two heaps. Worst-case: O(N), amortized: O(log N).
merge :: Frag a => Skew a -> Skew a -> Skew a
merge :: forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
t1 Skew a
Leaf = Skew a
t1
merge Skew a
Leaf Skew a
t2 = Skew a
t2
merge t1 :: Skew a
t1@(Node Skew a
l1 Seq a
f1 Skew a
r1) t2 :: Skew a
t2@(Node Skew a
l2 Seq a
f2 Skew a
r2)
    | Int
e1 forall a. Ord a => a -> a -> Bool
< Int
s2 = forall a. Skew a -> Seq a -> Skew a -> Skew a
Node Skew a
r1 Seq a
f1 (forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
l1 Skew a
t2)
    | Int
e2 forall a. Ord a => a -> a -> Bool
< Int
s1 = forall a. Skew a -> Seq a -> Skew a -> Skew a
Node Skew a
r2 Seq a
f2 (forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
l2 Skew a
t1)
    | Bool
otherwise =
        let f12 :: Seq a
f12
                | Int
e1 forall a. Eq a => a -> a -> Bool
== Int
s2 = Seq a
f1 forall a. Seq a -> Seq a -> Seq a
>< Seq a
f2
                | Int
s1 forall a. Eq a => a -> a -> Bool
== Int
e2 = Seq a
f2 forall a. Seq a -> Seq a -> Seq a
>< Seq a
f1
                | Int
s1 forall a. Ord a => a -> a -> Bool
<= Int
s2 Bool -> Bool -> Bool
&& Int
e2 forall a. Ord a => a -> a -> Bool
<= Int
e1 = Seq a
f1
                | Int
s2 forall a. Ord a => a -> a -> Bool
<= Int
s1 Bool -> Bool -> Bool
&& Int
e1 forall a. Ord a => a -> a -> Bool
<= Int
e2 = Seq a
f2
                | Int
s1 forall a. Ord a => a -> a -> Bool
<= Int
s2 = Seq a
f1 forall a. Seq a -> Seq a -> Seq a
>< forall a. Frag a => Int -> a -> a
shrink Int
e1 Seq a
f2
                | Bool
otherwise = Seq a
f2 forall a. Seq a -> Seq a -> Seq a
>< forall a. Frag a => Int -> a -> a
shrink Int
e2 Seq a
f1
         in forall a. Skew a -> Seq a -> Skew a -> Skew a
Node (forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
l1 Skew a
l2) Seq a
f12 (forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
r1 Skew a
r2)
  where
    s1 :: Int
s1 = forall a. Frag a => a -> Int
currOff Seq a
f1
    e1 :: Int
e1 = forall a. Frag a => a -> Int
nextOff Seq a
f1
    s2 :: Int
s2 = forall a. Frag a => a -> Int
currOff Seq a
f2
    e2 :: Int
e2 = forall a. Frag a => a -> Int
nextOff Seq a
f2

{-
showSkew :: Show a => Skew a -> String
showSkew = showSkew' ""

showSkew' :: Show a => String -> Skew a -> String
showSkew' _    Leaf = "\n"
showSkew' pref (Node l x r) = show x ++ "\n"
                           ++ pref ++ "+ " ++ showSkew' pref' l
                           ++ pref ++ "+ " ++ showSkew' pref' r
  where
    pref' = "  " ++ pref
-}