module Network.QUIC.Stream.Skew (
Skew (..),
empty,
insert,
deleteMin,
deleteMinIf,
) 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
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
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
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)
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