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
[Skew a] -> ShowS
Skew a -> String
(Int -> Skew a -> ShowS)
-> (Skew a -> String) -> ([Skew a] -> ShowS) -> Show (Skew a)
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 :: Skew a
empty = Skew a
forall a. Skew a
Leaf
insert :: Frag a => a -> Skew a -> Skew a
insert :: a -> Skew a -> Skew a
insert a
x Skew a
t = Skew a -> Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a -> Skew a
merge (Skew a -> Seq a -> Skew a -> Skew a
forall a. Skew a -> Seq a -> Skew a -> Skew a
Node Skew a
forall a. Skew a
Leaf (a -> Seq a
forall a. a -> Seq a
Seq.singleton a
x) Skew a
forall a. Skew a
Leaf) Skew a
t
minimum :: Skew a -> Maybe (Seq a)
minimum :: Skew a -> Maybe (Seq a)
minimum Skew a
Leaf = Maybe (Seq a)
forall a. Maybe a
Nothing
minimum (Node Skew a
_ Seq a
f Skew a
_) = Seq a -> Maybe (Seq a)
forall a. a -> Maybe a
Just Seq a
f
deleteMin' :: Frag a => Skew a -> Skew a
deleteMin' :: Skew a -> Skew a
deleteMin' Skew a
Leaf = Skew a
forall a. Skew a
Leaf
deleteMin' (Node Skew a
l Seq a
_ Skew a
r) = Skew a -> Skew a -> Skew a
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 :: Skew a -> (Skew a, Maybe (Seq a))
deleteMin Skew a
h = (Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, Skew a -> Maybe (Seq a)
forall a. Skew a -> Maybe (Seq a)
minimum Skew a
h)
deleteMinIf :: Frag a => Int -> Skew a -> (Skew a, Maybe (Seq a))
deleteMinIf :: Int -> Skew a -> (Skew a, Maybe (Seq a))
deleteMinIf Int
off Skew a
h = case Skew a -> Maybe (Seq a)
forall a. Skew a -> Maybe (Seq a)
minimum Skew a
h of
jf :: Maybe (Seq a)
jf@(Just Seq a
f)
| Seq a -> Int
forall a. Frag a => a -> Int
currOff Seq a
f Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
off -> (Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, Maybe (Seq a)
jf)
| Seq a -> Int
forall a. Frag a => a -> Int
currOff Seq a
f Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
off Bool -> Bool -> Bool
&& Int
off Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Seq a -> Int
forall a. Frag a => a -> Int
nextOff Seq a
f -> (Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, Int -> Seq a -> Seq a
forall a. Frag a => Int -> a -> a
shrink Int
off (Seq a -> Seq a) -> Maybe (Seq a) -> Maybe (Seq a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (Seq a)
jf)
| Seq a -> Int
forall a. Frag a => a -> Int
nextOff Seq a
f Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
off -> (Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a
deleteMin' Skew a
h, Maybe (Seq a)
forall a. Maybe a
Nothing)
Maybe (Seq a)
_ -> (Skew a
h, Maybe (Seq a)
forall a. Maybe a
Nothing)
merge :: Frag a => Skew a -> Skew a -> Skew a
merge :: 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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
s2 = Skew a -> Seq a -> Skew a -> Skew a
forall a. Skew a -> Seq a -> Skew a -> Skew a
Node Skew a
r1 Seq a
f1 (Skew a -> Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
l1 Skew a
t2)
| Int
e2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
s1 = Skew a -> Seq a -> Skew a -> Skew a
forall a. Skew a -> Seq a -> Skew a -> Skew a
Node Skew a
r2 Seq a
f2 (Skew a -> Skew a -> Skew a
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
s2 = Seq a
f1 Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
>< Seq a
f2
| Int
s1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
e2 = Seq a
f2 Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
>< Seq a
f1
| Int
s1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
s2 Bool -> Bool -> Bool
&& Int
e2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
e1 = Seq a
f1
| Int
s2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
s1 Bool -> Bool -> Bool
&& Int
e1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
e2 = Seq a
f2
| Int
s1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
s2 = Seq a
f1 Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
>< Int -> Seq a -> Seq a
forall a. Frag a => Int -> a -> a
shrink Int
e1 Seq a
f2
| Bool
otherwise = Seq a
f2 Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
>< Int -> Seq a -> Seq a
forall a. Frag a => Int -> a -> a
shrink Int
e2 Seq a
f1
in Skew a -> Seq a -> Skew a -> Skew a
forall a. Skew a -> Seq a -> Skew a -> Skew a
Node (Skew a -> Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
l1 Skew a
l2) Seq a
f12 (Skew a -> Skew a -> Skew a
forall a. Frag a => Skew a -> Skew a -> Skew a
merge Skew a
r1 Skew a
r2)
where
s1 :: Int
s1 = Seq a -> Int
forall a. Frag a => a -> Int
currOff Seq a
f1
e1 :: Int
e1 = Seq a -> Int
forall a. Frag a => a -> Int
nextOff Seq a
f1
s2 :: Int
s2 = Seq a -> Int
forall a. Frag a => a -> Int
currOff Seq a
f2
e2 :: Int
e2 = Seq a -> Int
forall a. Frag a => a -> Int
nextOff Seq a
f2