{-# LANGUAGE BangPatterns
, PatternSynonyms
, ViewPatterns
, UnboxedTuples
, UnboxedSums #-}
module Data.Zebra.Word.Internal
( Color (..)
, Zebra (Mono, ..)
, Data.Zebra.Word.Internal.lookup
, lookupL
, findL
, lookupR
, findR
, Range (..)
, monoL
, monoR
, monoRange
, unsafeMonoRange
, size
, sizeL
, sizeR
, sizeRange
, unsafeSize
, unsafeSizeL
, unsafeSizeR
, unsafeSizeRange
, fillL
, fillR
, fillRange
, unsafeFillL
, unsafeFillRange
, Data.Zebra.Word.Internal.foldl
, foldlL
, foldlR
, foldlRange
, unsafeFoldlRange
, Data.Zebra.Word.Internal.foldr
, foldrL
, foldrR
, foldrRange
, unsafeFoldrRange
, Data.Zebra.Word.Internal.foldl'
, foldlL'
, foldlR'
, foldlRange'
, unsafeFoldlRange'
, Data.Zebra.Word.Internal.foldr'
, foldrL'
, foldrR'
, foldrRange'
, unsafeFoldrRange'
, Data.Zebra.Word.Internal.complement
, union
, disjoint
, intersection
, difference
, symmetricDifference
, Data.Zebra.Word.Internal.compare
) where
import Radix.Common (PartialOrdering (..), order)
import Radix.Word.Common
import Radix.Word.Foundation
import Data.Bits
import Numeric.Natural
data Color = Black
| White
deriving (Int -> Color -> ShowS
[Color] -> ShowS
Color -> String
(Int -> Color -> ShowS)
-> (Color -> String) -> ([Color] -> ShowS) -> Show Color
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Color -> ShowS
showsPrec :: Int -> Color -> ShowS
$cshow :: Color -> String
show :: Color -> String
$cshowList :: [Color] -> ShowS
showList :: [Color] -> ShowS
Show, Color -> Color -> Bool
(Color -> Color -> Bool) -> (Color -> Color -> Bool) -> Eq Color
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Color -> Color -> Bool
== :: Color -> Color -> Bool
$c/= :: Color -> Color -> Bool
/= :: Color -> Color -> Bool
Eq)
invert :: Color -> (# Color #)
invert :: Color -> (# Color #)
invert Color
Black = (# Color
White #)
invert Color
White = (# Color
Black #)
data Zebra = Bin
{-# UNPACK #-} !Prefix
!Zebra
!Zebra
| Bla
{-# UNPACK #-} !Key
| Whi
{-# UNPACK #-} !Key
| Nil
{-# UNPACK #-} !Color
instance Show Zebra where
showsPrec :: Int -> Zebra -> ShowS
showsPrec Int
_ =
let f :: Range -> Color -> [(Key, Key)] -> [(Key, Key)]
f (UnsafeRange Key
kL Key
kR) Color
c [(Key, Key)]
z =
case Color
c of
Color
Black -> [(Key, Key)]
z
Color
White -> (Key
kL, Key
kR) (Key, Key) -> [(Key, Key)] -> [(Key, Key)]
forall a. a -> [a] -> [a]
: [(Key, Key)]
z
in [(Key, Key)] -> ShowS
forall a. Show a => [a] -> ShowS
showList ([(Key, Key)] -> ShowS)
-> (Zebra -> [(Key, Key)]) -> Zebra -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Range -> Color -> [(Key, Key)] -> [(Key, Key)])
-> [(Key, Key)] -> Zebra -> [(Key, Key)]
forall a. (Range -> Color -> a -> a) -> a -> Zebra -> a
Data.Zebra.Word.Internal.foldr Range -> Color -> [(Key, Key)] -> [(Key, Key)]
f []
instance Eq Zebra where
== :: Zebra -> Zebra -> Bool
(==) = Zebra -> Zebra -> Bool
go
where
go :: Zebra -> Zebra -> Bool
go Zebra
l Zebra
r =
case Zebra
l of
Bin Key
p Zebra
xl Zebra
xr ->
case Zebra
r of
Bin Key
q Zebra
yl Zebra
yr -> Key
p Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
q Bool -> Bool -> Bool
&& Zebra -> Zebra -> Bool
go Zebra
xl Zebra
yl Bool -> Bool -> Bool
&& Zebra -> Zebra -> Bool
go Zebra
xr Zebra
yr
Zebra
_ -> Bool
False
Bla Key
kA ->
case Zebra
r of
Bla Key
kB -> Key
kA Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
kB
Zebra
_ -> Bool
False
Whi Key
kA ->
case Zebra
r of
Whi Key
kB -> Key
kA Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
kB
Zebra
_ -> Bool
False
Nil Color
_ -> Bool
False
pattern Mono :: Color -> Zebra
pattern $mMono :: forall {r}. Zebra -> (Color -> r) -> ((# #) -> r) -> r
$bMono :: Color -> Zebra
Mono c <- ( ( \Zebra
z -> case Zebra
z of
Bla Key
0 -> Color -> Maybe Color
forall a. a -> Maybe a
Just Color
Black
Whi Key
0 -> Color -> Maybe Color
forall a. a -> Maybe a
Just Color
White
Zebra
_ -> Maybe Color
forall a. Maybe a
Nothing
)
-> Just c
)
where
Mono Color
Black = Key -> Zebra
Bla Key
0
Mono Color
White = Key -> Zebra
Whi Key
0
{-# INLINE join #-}
join :: Prefix -> Zebra -> Prefix -> Zebra -> Zebra
join :: Key -> Zebra -> Key -> Zebra -> Zebra
join Key
p0 Zebra
t0 Key
p1 Zebra
t1 =
let m :: Key
m = Key -> Key -> Key
branchingBit Key
p0 Key
p1
p :: Key
p = Key -> Key -> Key
mask Key
p0 Key
m Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
m
in if Key -> Key -> Bool
zeroBit Key
p0 Key
m
then Key -> Zebra -> Zebra -> Zebra
Bin Key
p Zebra
t0 Zebra
t1
else Key -> Zebra -> Zebra -> Zebra
Bin Key
p Zebra
t1 Zebra
t0
{-# INLINE rebin #-}
rebin :: Prefix -> Zebra -> Zebra -> Zebra
rebin :: Key -> Zebra -> Zebra -> Zebra
rebin Key
p Zebra
l Zebra
r =
case Zebra
l of
Nil Color
_ -> Zebra
r
Zebra
_ ->
case Zebra
r of
Nil Color
_ -> Zebra
l
Zebra
_ -> Key -> Zebra -> Zebra -> Zebra
Bin Key
p Zebra
l Zebra
r
{-# INLINE rebinL #-}
rebinL :: Prefix -> Zebra -> Zebra -> Zebra
rebinL :: Key -> Zebra -> Zebra -> Zebra
rebinL Key
p Zebra
l Zebra
r =
case Zebra
l of
Nil Color
_ -> Zebra
r
Zebra
_ -> Key -> Zebra -> Zebra -> Zebra
Bin Key
p Zebra
l Zebra
r
{-# INLINE rebinR #-}
rebinR :: Prefix -> Zebra -> Zebra -> Zebra
rebinR :: Key -> Zebra -> Zebra -> Zebra
rebinR Key
p Zebra
l Zebra
r =
case Zebra
r of
Nil Color
_ -> Zebra
l
Zebra
_ -> Key -> Zebra -> Zebra -> Zebra
Bin Key
p Zebra
l Zebra
r
{-# INLINE tip #-}
tip :: Key -> Color -> Zebra
tip :: Key -> Color -> Zebra
tip Key
k Color
Black = Key -> Zebra
Bla Key
k
tip Key
k Color
White = Key -> Zebra
Whi Key
k
monoL :: Word -> Zebra -> Maybe Color
monoL :: Key -> Zebra -> Maybe Color
monoL !Key
w = Zebra -> Maybe Color
go
where
go :: Zebra -> Maybe Color
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
_ ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p
then Zebra -> Maybe Color
go Zebra
l
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in Color -> Maybe Color
forall a. a -> Maybe a
Just Color
cL
else Maybe Color
forall a. Maybe a
Nothing
Bla Key
k -> Color -> Key -> Maybe Color
goTip Color
Black Key
k
Whi Key
k -> Color -> Key -> Maybe Color
goTip Color
White Key
k
Nil Color
_ -> Maybe Color
forall a. Maybe a
Nothing
goTip :: Color -> Key -> Maybe Color
goTip Color
c Key
k
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Color -> Maybe Color
forall a. a -> Maybe a
Just Color
c
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in Color -> Maybe Color
forall a. a -> Maybe a
Just Color
x
| Bool
otherwise = Maybe Color
forall a. Maybe a
Nothing
monoR :: Word -> Zebra -> Maybe Color
monoR :: Key -> Zebra -> Maybe Color
monoR !Key
w = Zebra -> Maybe Color
go
where
go :: Zebra -> Maybe Color
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
_ Zebra
r ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then Maybe Color
forall a. Maybe a
Nothing
else if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p
then Zebra -> Maybe Color
go Zebra
r
else let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in Color -> Maybe Color
forall a. a -> Maybe a
Just Color
cR
Bla Key
k -> Color -> Key -> Maybe Color
forall {a}. a -> Key -> Maybe a
goTip Color
Black Key
k
Whi Key
k -> Color -> Key -> Maybe Color
forall {a}. a -> Key -> Maybe a
goTip Color
White Key
k
Nil Color
_ -> Maybe Color
forall a. Maybe a
Nothing
goTip :: a -> Key -> Maybe a
goTip a
c Key
k
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = a -> Maybe a
forall a. a -> Maybe a
Just a
c
| Bool
otherwise = Maybe a
forall a. Maybe a
Nothing
monoRange :: Range -> Zebra -> Maybe Color
monoRange :: Range -> Zebra -> Maybe Color
monoRange (UnsafeRange Key
kL Key
kR)
| Key
kR Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
forall a. Bounded a => a
maxBound = Key -> Zebra -> Maybe Color
monoR Key
kL
| Bool
otherwise = Key -> Key -> Zebra -> Maybe Color
unsafeMonoRange Key
kL (Key
kR Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
1)
unsafeMonoRange
:: Word
-> Word
-> Zebra
-> Maybe Color
unsafeMonoRange :: Key -> Key -> Zebra -> Maybe Color
unsafeMonoRange !Key
wL !Key
wR = Zebra -> Maybe Color
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
go :: Zebra -> Maybe Color
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> let !mcL :: Maybe Color
mcL = Key -> Zebra -> Maybe Color
monoR Key
wL Zebra
l
!mcR :: Maybe Color
mcR = Key -> Zebra -> Maybe Color
monoL Key
wR Zebra
r
in if Maybe Color
mcL Maybe Color -> Maybe Color -> Bool
forall a. Eq a => a -> a -> Bool
== Maybe Color
mcR
then Maybe Color
mcL
else Maybe Color
forall a. Maybe a
Nothing
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> Zebra -> Maybe Color
go Zebra
r
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then Key -> Zebra -> Maybe Color
monoR Key
wL Zebra
r
else Maybe Color
forall a. Maybe a
Nothing
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in Color -> Maybe Color
forall a. a -> Maybe a
Just Color
cR
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key
p
then Key -> Zebra -> Maybe Color
monoL Key
wR Zebra
l
else Maybe Color
forall a. Maybe a
Nothing
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> Zebra -> Maybe Color
go Zebra
l
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in Color -> Maybe Color
forall a. a -> Maybe a
Just Color
cL
Bla Key
k -> Color -> Key -> Maybe Color
goTip Color
Black Key
k
Whi Key
k -> Color -> Key -> Maybe Color
goTip Color
White Key
k
Nil Color
_ -> Maybe Color
forall a. Maybe a
Nothing
goTip :: Color -> Key -> Maybe Color
goTip Color
c Key
k
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = Color -> Maybe Color
forall a. a -> Maybe a
Just Color
c
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key
k = let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in Color -> Maybe Color
forall a. a -> Maybe a
Just Color
x
| Bool
otherwise = Maybe Color
forall a. Maybe a
Nothing
size :: Color -> Zebra -> Natural
size :: Color -> Zebra -> Natural
size !Color
x Zebra
t =
case Zebra
t of
Bla Key
0 -> Color -> Natural
forall {a}. Num a => Color -> a
goZero Color
Black
Whi Key
0 -> Color -> Natural
forall {a}. Num a => Color -> a
goZero Color
White
Zebra
_ -> Key -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Key -> Natural) -> Key -> Natural
forall a b. (a -> b) -> a -> b
$ Color -> Zebra -> Key
unsafeSize Color
x Zebra
t
where
goZero :: Color -> a
goZero Color
c
| Color
x Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
c = Key -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Key
forall a. Bounded a => a
maxBound :: Word) a -> a -> a
forall a. Num a => a -> a -> a
+ a
1
| Bool
otherwise = a
0
unsafeSize :: Color -> Zebra -> Word
unsafeSize :: Color -> Zebra -> Key
unsafeSize !Color
x = Color -> Key -> Key -> Zebra -> Key
size_ Color
x Key
0 Key
0
size_ :: Color -> Word -> Word -> Zebra -> Word
size_ :: Color -> Key -> Key -> Zebra -> Key
size_ !Color
x = Key -> Key -> Zebra -> Key
go
where
go :: Key -> Key -> Zebra -> Key
go !Key
kL !Key
kR Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
let !nL :: Key
nL = Key -> Key -> Zebra -> Key
go Key
kL Key
p Zebra
l
!nR :: Key
nR = Key -> Key -> Zebra -> Key
go Key
p Key
kR Zebra
r
in Key
nL Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
nR
Bla Key
k -> Key -> Key -> Key -> Color -> Key
forall {a}. Num a => a -> a -> a -> Color -> a
goTip Key
kL Key
kR Key
k Color
Black
Whi Key
k -> Key -> Key -> Key -> Color -> Key
forall {a}. Num a => a -> a -> a -> Color -> a
goTip Key
kL Key
kR Key
k Color
White
Nil Color
_ -> Key
0
goTip :: a -> a -> a -> Color -> a
goTip !a
kL !a
kR a
k Color
c
| Color
x Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
c = a
kR a -> a -> a
forall a. Num a => a -> a -> a
- a
k
| Bool
otherwise = a
k a -> a -> a
forall a. Num a => a -> a -> a
- a
kL
sizeL :: Color -> Word -> Zebra -> Natural
sizeL :: Color -> Key -> Zebra -> Natural
sizeL Color
x Key
w
| Key
w Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
forall a. Bounded a => a
maxBound = Color -> Zebra -> Natural
size Color
x
| Bool
otherwise = Key -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Key -> Natural) -> (Zebra -> Key) -> Zebra -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Color -> Key -> Zebra -> Key
unsafeSizeL Color
x (Key
w Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
1)
unsafeSizeL :: Color -> Word -> Zebra -> Word
unsafeSizeL :: Color -> Key -> Zebra -> Key
unsafeSizeL Color
x Key
w = Color -> Key -> Key -> Zebra -> Key
sizeL_ Color
x Key
0 Key
w
sizeL_ :: Color -> Word -> Word -> Zebra -> Word
sizeL_ :: Color -> Key -> Key -> Zebra -> Key
sizeL_ !Color
x !Key
kL0 !Key
w = Key -> Zebra -> Key
go Key
kL0
where
go :: Key -> Zebra -> Key
go !Key
kL Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then Key -> Zebra -> Key
go Key
kL Zebra
l
else
let !nL :: Key
nL = Color -> Key -> Key -> Zebra -> Key
size_ Color
x Key
kL Key
p Zebra
l
!nR :: Key
nR = Key -> Zebra -> Key
go Key
p Zebra
r
in Key
nL Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
nR
Bla Key
k -> Key -> Key -> Color -> Key
goTip Key
kL Key
k Color
Black
Whi Key
k -> Key -> Key -> Color -> Key
goTip Key
kL Key
k Color
White
Nil Color
_ -> Key
0
goTip :: Key -> Key -> Color -> Key
goTip !Key
kL Key
k Color
c
| Color
x Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
c = if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
k
then Key
w Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
k
else Key
0
| Bool
otherwise = let i :: Key
i | Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
k = Key
k
| Bool
otherwise = Key
w
in Key
i Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
kL
sizeR :: Color -> Word -> Zebra -> Natural
sizeR :: Color -> Key -> Zebra -> Natural
sizeR Color
x Key
w
| Key
w Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Color -> Zebra -> Natural
size Color
x
| Bool
otherwise = Key -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Key -> Natural) -> (Zebra -> Key) -> Zebra -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Color -> Key -> Zebra -> Key
unsafeSizeR Color
x Key
w
unsafeSizeR :: Color -> Word -> Zebra -> Word
unsafeSizeR :: Color -> Key -> Zebra -> Key
unsafeSizeR Color
x Key
w = Color -> Key -> Key -> Zebra -> Key
sizeR_ Color
x Key
w Key
0
sizeR_ :: Color -> Word -> Word -> Zebra -> Word
sizeR_ :: Color -> Key -> Key -> Zebra -> Key
sizeR_ !Color
x !Key
w = Key -> Zebra -> Key
go
where
go :: Key -> Zebra -> Key
go !Key
kR Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !nL :: Key
nL = Key -> Zebra -> Key
go Key
p Zebra
l
!nR :: Key
nR = Color -> Key -> Key -> Zebra -> Key
size_ Color
x Key
p Key
kR Zebra
r
in Key
nL Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
nR
else Key -> Zebra -> Key
go Key
kR Zebra
r
Bla Key
k -> Key -> Key -> Color -> Key
goTip Key
kR Key
k Color
Black
Whi Key
k -> Key -> Key -> Color -> Key
goTip Key
kR Key
k Color
White
Nil Color
_ -> Key
0
goTip :: Key -> Key -> Color -> Key
goTip Key
kR Key
k Color
c
| Color
x Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
c = Key
kR Key -> Key -> Key
forall a. Num a => a -> a -> a
- if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
k
then Key
w
else Key
k
| Bool
otherwise = if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k
then Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
w
else Key
0
sizeRange :: Color -> Range -> Zebra -> Natural
sizeRange :: Color -> Range -> Zebra -> Natural
sizeRange Color
x (UnsafeRange Key
kL Key
kR)
| Key
kR Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
forall a. Bounded a => a
maxBound = Color -> Key -> Zebra -> Natural
sizeR Color
x Key
kL
| Bool
otherwise = Key -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Key -> Natural) -> (Zebra -> Key) -> Zebra -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Color -> Key -> Key -> Zebra -> Key
unsafeSizeRange Color
x Key
kL (Key
kR Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
1)
unsafeSizeRange
:: Color
-> Word
-> Word
-> Zebra
-> Word
unsafeSizeRange :: Color -> Key -> Key -> Zebra -> Key
unsafeSizeRange !Color
x !Key
wL !Key
wR = Zebra -> Key
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
go :: Zebra -> Key
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> let !n :: Key
n = Color -> Key -> Key -> Zebra -> Key
sizeR_ Color
x Key
wL Key
p Zebra
l
!m :: Key
m = Color -> Key -> Key -> Zebra -> Key
sizeL_ Color
x Key
p Key
wR Zebra
r
in Key
n Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
m
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> Zebra -> Key
go Zebra
r
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !n :: Key
n = Color -> Key -> Key -> Zebra -> Key
sizeR_ Color
x Key
wL Key
p Zebra
l
!m :: Key
m = Color -> Key -> Key -> Zebra -> Key
size_ Color
x Key
p Key
wR Zebra
r
in Key
n Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
m
else Color -> Key -> Key -> Zebra -> Key
sizeR_ Color
x Key
wL Key
wR Zebra
r
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key
wR Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
wL
else Key
0
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then let !n :: Key
n = Color -> Key -> Key -> Zebra -> Key
size_ Color
x Key
wL Key
p Zebra
l
!m :: Key
m = Color -> Key -> Key -> Zebra -> Key
sizeL_ Color
x Key
p Key
wR Zebra
r
in Key
n Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
m
else Color -> Key -> Key -> Zebra -> Key
sizeL_ Color
x Key
wL Key
wR Zebra
l
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> Zebra -> Key
go Zebra
l
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key
0
else Key
wR Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
wL
Bla Key
k -> Key -> Color -> Key
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> Key
goTip Key
k Color
White
Nil Color
_ -> Key
0
goTip :: Key -> Color -> Key
goTip Key
k Color
c
| Color
x Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
c = if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k
then Key
wR Key -> Key -> Key
forall a. Num a => a -> a -> a
- if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
k
then Key
wL
else Key
k
else Key
0
| Bool
otherwise = if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key
k
then let i :: Key
i | Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
> Key
k = Key
k
| Bool
otherwise = Key
wR
in Key
i Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
wL
else Key
0
foldl :: (a -> Range -> Color -> a) -> a -> Zebra -> a
foldl :: forall a. (a -> Range -> Color -> a) -> a -> Zebra -> a
foldl a -> Range -> Color -> a
f = \a
z Zebra
t ->
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl_L Key
0 a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl_R Key
forall a. Bounded a => a
maxBound a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> a -> Key -> Color -> a
tipM a
z Key
k Color
Black
Whi Key
k -> a -> Key -> Color -> a
tipM a
z Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: a -> Key -> Color -> a
tipM a
z Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = let !r :: Range
r = Key -> Key -> Range
UnsafeRange Key
0 Key
forall a. Bounded a => a
maxBound
in a -> Range -> Color -> a
f a
z Range
r Color
c
| Bool
otherwise = let z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
0 Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
forall a. Bounded a => a
maxBound) Color
c
foldl_L :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> (# Word, Color, a #)
foldl_L :: forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl_L !Key
wL a -> Range -> Color -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
l
in (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl_M a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c = (# Key
k, Color
c, if Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0
then a
z
else let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
#)
foldl_R :: Word -> (a -> Range -> Color -> a) -> Word -> Color -> a -> Zebra -> a
foldl_R :: forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl_R !Key
wR a -> Range -> Color -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl_M a -> Range -> Color -> a
f Key
w Color
x a
z Zebra
l
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c = let z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w Key
k') Color
x
!r' :: Range
r' = Key -> Key -> Range
UnsafeRange Key
k Key
wR
in a -> Range -> Color -> a
f a
z' Range
r' Color
c
foldl_M :: (a -> Range -> Color -> a) -> Word -> Color -> a -> Zebra -> (# Word, Color, a #)
foldl_M :: forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl_M a -> Range -> Color -> a
f = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go
where
go :: Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x a
z Zebra
l
in Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
forall {b}. Key -> b -> (# Key, b, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
forall {b}. Key -> b -> (# Key, b, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
w, Color
x, a
z #)
where
goTip :: Key -> b -> (# Key, b, a #)
goTip Key
k b
c = (# Key
k, b
c, let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w Key
k') Color
x
#)
foldlL :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL :: forall a. Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL = Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL_ Key
0
foldlL_ :: Word -> Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL_ :: forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL_ !Key
wL !Key
wR a -> Range -> Color -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then a -> Zebra -> a
go a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = let !r :: Range
r = Key -> Key -> Range
UnsafeRange Key
wL Key
wR
in a -> Range -> Color -> a
f a
z Range
r Color
c
| Bool
otherwise =
let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k
then a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x
else let z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldlL_R :: Word -> (a -> Range -> Color -> a) -> Word -> Color -> a -> Zebra -> a
foldlL_R :: forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL_R !Key
wR a -> Range -> Color -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then Key -> Color -> a -> Zebra -> a
go Key
w Color
x a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl_M a -> Range -> Color -> a
f Key
w Color
x a
z Zebra
l
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !r :: Range
r = Key -> Key -> Range
UnsafeRange Key
w Key
wR
in a -> Range -> Color -> a
f a
z Range
r Color
x
| Bool
otherwise = let z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldlR :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR :: forall a. Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR Key
wL = Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR_ Key
wL Key
forall a. Bounded a => a
maxBound
foldlR_ :: Word -> Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR_ :: forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR_ !Key
wL !Key
wR a -> Range -> Color -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else a -> Zebra -> a
go a
z Zebra
r
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
z' :: a
z' = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldlR_L :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> (# Word, Color, a #)
foldlR_L :: forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR_L !Key
wL a -> Range -> Color -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
l
in (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl_M a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
r
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = (# Key
wL, Color
c, a
z #)
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in (# Key
k, Color
c, a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x #)
foldlRange :: Range -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlRange :: forall a. Range -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlRange (UnsafeRange Key
wL Key
wR) a -> Range -> Color -> a
f a
z
| Key
wL Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
wR = \Zebra
t -> let !c :: Color
c = Key -> Zebra -> Color
Data.Zebra.Word.Internal.lookup Key
wL Zebra
t
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Bool
otherwise = Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
unsafeFoldlRange Key
wL Key
wR a -> Range -> Color -> a
f a
z
unsafeFoldlRange
:: Word
-> Word
-> (a -> Range -> Color -> a)
-> a
-> Zebra
-> a
unsafeFoldlRange :: forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
unsafeFoldlRange !Key
wL !Key
wR a -> Range -> Color -> a
f = a -> Zebra -> a
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> a -> Zebra -> a
go a
z Zebra
r
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR_ Key
wL Key
wR a -> Range -> Color -> a
f a
z Zebra
r
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cR
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL_ Key
wL Key
wR a -> Range -> Color -> a
f a
z Zebra
l
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> a -> Zebra -> a
go a
z Zebra
l
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cL
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Bool
otherwise =
let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k
then a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x
else let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
z' :: a
z' = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldr :: (Range -> Color -> a -> a) -> a -> Zebra -> a
foldr :: forall a. (Range -> Color -> a -> a) -> a -> Zebra -> a
foldr Range -> Color -> a -> a
f = \a
z Zebra
t ->
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr_R Key
forall a. Bounded a => a
maxBound Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr_L Key
0 Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> a -> Key -> Color -> a
goTip a
z Key
k Color
Black
Whi Key
k -> a -> Key -> Color -> a
goTip a
z Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: a -> Key -> Color -> a
goTip a
z Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
0 Key
forall a. Bounded a => a
maxBound) Color
c a
z
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
0 Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
forall a. Bounded a => a
maxBound) Color
c a
z
foldr_R :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> (# Word, Color, a #)
foldr_R :: forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr_R !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
r
in (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr_M Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in (# Key
k', Color
c, Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z #)
foldr_L :: Word -> (Range -> Color -> a -> a) -> Word -> Color -> a -> Zebra -> a
foldr_L :: forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr_L !Key
wL Range -> Color -> a -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr_M Range -> Color -> a -> a
f Key
w Color
x a
z Zebra
r
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
w) Color
c a
z
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
w) Color
c a
z
foldr_M
:: (Range -> Color -> a -> a) -> Word -> Color -> a -> Zebra -> (# Word, Color, a #)
foldr_M :: forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr_M Range -> Color -> a -> a
f = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go
where
go :: Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x a
z Zebra
r
in Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
w, Color
x, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in (# Key
k', Color
c, Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
w) Color
c a
z #)
foldrR :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR :: forall a. Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR Key
wL = Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR_ Key
wL Key
forall a. Bounded a => a
maxBound
foldrR_ :: Word -> Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR_ :: forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR_ !Key
wL !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
else a -> Zebra -> a
go a
z Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z
| Bool
otherwise = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
foldrR_L :: Word -> (Range -> Color -> a -> a) -> Word -> Color -> a -> Zebra -> a
foldrR_L :: forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR_L !Key
wL Range -> Color -> a -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr_M Range -> Color -> a -> a
f Key
w Color
x a
z Zebra
r
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
l
else Key -> Color -> a -> Zebra -> a
go Key
w Color
x a
z Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
w) Color
c a
z
| Bool
otherwise = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
w) Color
c a
z
foldrL :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL :: forall a. Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL = Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL_ Key
0
foldrL_ :: Word -> Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL_ :: forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL_ !Key
wL !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then a -> Zebra -> a
go a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z
| Bool
otherwise = let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x a
z
foldrL_R :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> (# Word, Color, a #)
foldrL_R :: forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL_R !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
r
in (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr_M Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in (# Key
k', Color
c, Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z #)
| Bool
otherwise = (# Key
wR, Color
c, a
z #)
foldrRange :: Range -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrRange :: forall a. Range -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrRange (UnsafeRange Key
wL Key
wR) Range -> Color -> a -> a
f a
z
| Key
wL Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
wR = \Zebra
t -> let !c :: Color
c = Key -> Zebra -> Color
Data.Zebra.Word.Internal.lookup Key
wL Zebra
t
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Bool
otherwise = Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
unsafeFoldrRange Key
wL Key
wR Range -> Color -> a -> a
f a
z
unsafeFoldrRange
:: Word
-> Word
-> (Range -> Color -> a -> a)
-> a
-> Zebra
-> a
unsafeFoldrRange :: forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
unsafeFoldrRange !Key
wL !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> a
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> a -> Zebra -> a
go a
z Zebra
r
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
else Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR_ Key
wL Key
wR Range -> Color -> a -> a
f a
z Zebra
r
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cR a
z
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
else Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL_ Key
wL Key
wR Range -> Color -> a -> a
f a
z Zebra
l
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> a -> Zebra -> a
go a
z Zebra
l
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cL a
z
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Bool
otherwise =
let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k
then Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x a
z
else let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z
foldl' :: (a -> Range -> Color -> a) -> a -> Zebra -> a
foldl' :: forall a. (a -> Range -> Color -> a) -> a -> Zebra -> a
foldl' a -> Range -> Color -> a
f = \ !a
z Zebra
t ->
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl'_L Key
0 a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl'_R Key
forall a. Bounded a => a
maxBound a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> a -> Key -> Color -> a
goTip a
z Key
k Color
Black
Whi Key
k -> a -> Key -> Color -> a
goTip a
z Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: a -> Key -> Color -> a
goTip a
z Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
0 Key
forall a. Bounded a => a
maxBound) Color
c
| Bool
otherwise = let !z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
0 Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
forall a. Bounded a => a
maxBound) Color
c
foldl'_L :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> (# Word, Color, a #)
foldl'_L :: forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl'_L !Key
wL a -> Range -> Color -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go !a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
l
in (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl'_M a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in (# Key
k, Color
c, if Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0
then a
z
else a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x #)
foldl'_R :: Word -> (a -> Range -> Color -> a) -> Word -> Color -> a -> Zebra -> a
foldl'_R :: forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl'_R !Key
wR a -> Range -> Color -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x !a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl'_M a -> Range -> Color -> a
f Key
w Color
x a
z Zebra
l
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c = let !z' :: a
z' = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w (Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1)) Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldl'_M
:: (a -> Range -> Color -> a) -> Word -> Color -> a -> Zebra -> (# Word, Color, a #)
foldl'_M :: forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl'_M a -> Range -> Color -> a
f = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go
where
go :: Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x !a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x a
z Zebra
l
in Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
forall {b}. Key -> b -> (# Key, b, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
forall {b}. Key -> b -> (# Key, b, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
w, Color
x, a
z #)
where
goTip :: Key -> b -> (# Key, b, a #)
goTip Key
k b
c = (# Key
k, b
c, a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w (Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1)) Color
x #)
foldlL' :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL' :: forall a. Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL' = Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL'_ Key
0
foldlL'_ :: Word -> Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL'_ :: forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL'_ !Key
wL !Key
wR a -> Range -> Color -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then a -> Zebra -> a
go a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl'_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL'_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x
| Bool
otherwise = let !z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldlL'_R :: Word -> (a -> Range -> Color -> a) -> Word -> Color -> a -> Zebra -> a
foldlL'_R :: forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL'_R !Key
wR a -> Range -> Color -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then Key -> Color -> a -> Zebra -> a
go Key
w Color
x a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl'_M a -> Range -> Color -> a
f Key
w Color
x a
z Zebra
l
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w Key
wR) Color
x
| Bool
otherwise = let z' :: a
z' = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
w (Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1)) Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldlR' :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR' :: forall a. Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR' Key
wL = Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR'_ Key
wL Key
forall a. Bounded a => a
maxBound
foldlR'_ :: Word -> Word -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR'_ :: forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR'_ !Key
wL !Key
wR a -> Range -> Color -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR'_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl'_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else a -> Zebra -> a
go a
z Zebra
r
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Bool
otherwise = let !z' :: a
z' = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldlR'_L :: Word -> (a -> Range -> Color -> a) -> a -> Zebra -> (# Word, Color, a #)
foldlR'_L :: forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR'_L !Key
wL a -> Range -> Color -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
l
in (a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(a -> Range -> Color -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldl'_M a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
r
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = (# Key
wL, Color
c, a
z #)
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in (# Key
k, Color
c, a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x #)
foldlRange' :: Range -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlRange' :: forall a. Range -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlRange' (UnsafeRange Key
wL Key
wR) a -> Range -> Color -> a
f a
z
| Key
wL Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
wR = \Zebra
t -> let !c :: Color
c = Key -> Zebra -> Color
Data.Zebra.Word.Internal.lookup Key
wL Zebra
t
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Bool
otherwise = Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
unsafeFoldlRange' Key
wL Key
wR a -> Range -> Color -> a
f a
z
unsafeFoldlRange'
:: Word
-> Word
-> (a -> Range -> Color -> a)
-> a
-> Zebra
-> a
unsafeFoldlRange' :: forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
unsafeFoldlRange' !Key
wL !Key
wR a -> Range -> Color -> a
f = a -> Zebra -> a
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
go :: a -> Zebra -> a
go a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR'_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL'_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> a -> Zebra -> a
go a
z Zebra
r
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldlR'_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldl'_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlR'_ Key
wL Key
wR a -> Range -> Color -> a
f a
z Zebra
r
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cR
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (a -> Range -> Color -> a) -> a -> Zebra -> (# Key, Color, a #)
foldl'_L Key
wL a -> Range -> Color -> a
f a
z Zebra
l
in Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (a -> Range -> Color -> a) -> Key -> Color -> a -> Zebra -> a
foldlL'_R Key
wR a -> Range -> Color -> a
f Key
w' Color
x' a
z' Zebra
r
else Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (a -> Range -> Color -> a) -> a -> Zebra -> a
foldlL'_ Key
wL Key
wR a -> Range -> Color -> a
f a
z Zebra
l
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> a -> Zebra -> a
go a
z Zebra
l
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cL
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c
| Bool
otherwise =
let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k
then a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x
else let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
z' :: a
z' = a -> Range -> Color -> a
f a
z (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x
in a -> Range -> Color -> a
f a
z' (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c
foldr' :: (Range -> Color -> a -> a) -> a -> Zebra -> a
foldr' :: forall a. (Range -> Color -> a -> a) -> a -> Zebra -> a
foldr' Range -> Color -> a -> a
f = \ !a
z Zebra
t ->
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr'_R Key
forall a. Bounded a => a
maxBound Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr'_L Key
0 Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> a -> Key -> Color -> a
goTip a
z Key
k Color
Black
Whi Key
k -> a -> Key -> Color -> a
goTip a
z Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: a -> Key -> Color -> a
goTip a
z Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
0 Key
forall a. Bounded a => a
maxBound) Color
c a
z
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
0 Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
forall a. Bounded a => a
maxBound) Color
c a
z
foldr'_R :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> (# Word, Color, a #)
foldr'_R :: forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr'_R !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go !a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
r
in (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr'_M Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in (# Key
k', Color
c, Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z #)
foldr'_L :: Word -> (Range -> Color -> a -> a) -> Word -> Color -> a -> Zebra -> a
foldr'_L :: forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr'_L !Key
wL Range -> Color -> a -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x !a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr'_M Range -> Color -> a -> a
f Key
w Color
x a
z Zebra
r
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
w) Color
c a
z
| Bool
otherwise = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
w) Color
c a
z
foldr'_M
:: (Range -> Color -> a -> a) -> Word -> Color -> a -> Zebra -> (# Word, Color, a #)
foldr'_M :: forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr'_M Range -> Color -> a -> a
f = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go
where
go :: Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x !a
z Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
r -> let !(# Key
w', Color
x', a
z' #) = Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w Color
x a
z Zebra
r
in Key -> Color -> a -> Zebra -> (# Key, Color, a #)
go Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
w, Color
x, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in (# Key
k', Color
c, Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
w) Color
c a
z #)
foldrR' :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR' :: forall a. Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR' Key
wL = Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR'_ Key
wL Key
forall a. Bounded a => a
maxBound
foldrR'_ :: Word -> Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR'_ :: forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR'_ !Key
wL !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr'_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR'_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
else a -> Zebra -> a
go a
z Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z
| Bool
otherwise = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
foldrR'_L :: Word -> (Range -> Color -> a -> a) -> Word -> Color -> a -> Zebra -> a
foldrR'_L :: forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR'_L !Key
wL Range -> Color -> a -> a
f = Key -> Color -> a -> Zebra -> a
go
where
go :: Key -> Color -> a -> Zebra -> a
go !Key
w !Color
x !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr'_M Range -> Color -> a -> a
f Key
w Color
x a
z Zebra
r
in Key -> Color -> a -> Zebra -> a
go Key
w' Color
x' a
z' Zebra
l
else Key -> Color -> a -> Zebra -> a
go Key
w Color
x a
z Zebra
r
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
w) Color
c a
z
| Bool
otherwise = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
w) Color
c a
z
foldrL' :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL' :: forall a. Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL' = Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL'_ Key
0
foldrL'_ :: Word -> Word -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL'_ :: forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL'_ !Key
wL !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> a
go
where
go :: a -> Zebra -> a
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then a -> Zebra -> a
go a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL'_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr'_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> a
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> a
goTip Key
k Color
White
Nil Color
_ -> a
z
where
goTip :: Key -> Color -> a
goTip Key
k Color
c
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
!(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z
| Bool
otherwise = let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x a
z
foldrL'_R :: Word -> (Range -> Color -> a -> a) -> a -> Zebra -> (# Word, Color, a #)
foldrL'_R :: forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL'_R !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> (# Key, Color, a #)
go
where
go :: a -> Zebra -> (# Key, Color, a #)
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
l
else let !(# Key
w', Color
x', a
z' #) = a -> Zebra -> (# Key, Color, a #)
go a
z Zebra
r
in (Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
forall a.
(Range -> Color -> a -> a)
-> Key -> Color -> a -> Zebra -> (# Key, Color, a #)
foldr'_M Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Bla Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
White
Nil Color
_ -> (# Key
0, Color
Black, a
z #)
where
goTip :: Key -> Color -> (# Key, Color, a #)
goTip Key
k Color
c
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in (# Key
k', Color
c, Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z #)
| Bool
otherwise = (# Key
wR, Color
c, a
z #)
foldrRange' :: Range -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrRange' :: forall a. Range -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrRange' (UnsafeRange Key
wL Key
wR) Range -> Color -> a -> a
f !a
z
| Key
wL Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
wR = \Zebra
t -> let !c :: Color
c = Key -> Zebra -> Color
Data.Zebra.Word.Internal.lookup Key
wL Zebra
t
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Bool
otherwise = Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
unsafeFoldrRange' Key
wL Key
wR Range -> Color -> a -> a
f a
z
unsafeFoldrRange'
:: Word
-> Word
-> (Range -> Color -> a -> a)
-> a
-> Zebra
-> a
unsafeFoldrRange' :: forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
unsafeFoldrRange' !Key
wL !Key
wR Range -> Color -> a -> a
f = a -> Zebra -> a
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
go :: a -> Zebra -> a
go !a
z Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL'_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR'_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> a -> Zebra -> a
go a
z Zebra
r
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldrL'_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldr'_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
else Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrR'_ Key
wL Key
wR Range -> Color -> a -> a
f a
z Zebra
r
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cR a
z
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then let !(# Key
w', Color
x', a
z' #) = Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
forall a.
Key
-> (Range -> Color -> a -> a) -> a -> Zebra -> (# Key, Color, a #)
foldr'_R Key
wR Range -> Color -> a -> a
f a
z Zebra
r
in Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
forall a.
Key
-> (Range -> Color -> a -> a) -> Key -> Color -> a -> Zebra -> a
foldrR'_L Key
wL Range -> Color -> a -> a
f Key
w' Color
x' a
z' Zebra
l
else Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
forall a.
Key -> Key -> (Range -> Color -> a -> a) -> a -> Zebra -> a
foldrL'_ Key
wL Key
wR Range -> Color -> a -> a
f a
z Zebra
l
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> a -> Zebra -> a
go a
z Zebra
l
| Bool
otherwise -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
cL a
z
Bla Key
k -> Key -> Color -> a
tipM Key
k Color
Black
Whi Key
k -> Key -> Color -> a
tipM Key
k Color
White
Nil Color
_ -> a
z
where
tipM :: Key -> Color -> a
tipM Key
k Color
c
| Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
c a
z
| Bool
otherwise =
let !(# Color
x #) = Color -> (# Color #)
invert Color
c
in if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k
then Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
wR) Color
x a
z
else let !k' :: Key
k' = Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
in Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
wL Key
k') Color
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! Range -> Color -> a -> a
f (Key -> Key -> Range
UnsafeRange Key
k Key
wR) Color
c a
z
lookup :: Word -> Zebra -> Color
lookup :: Key -> Zebra -> Color
lookup !Key
w = Zebra -> Color
go
where
go :: Zebra -> Color
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p
then Zebra -> Color
go Zebra
l
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
!(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in Color
cL
else if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p
then Zebra -> Color
go Zebra
r
else let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in Color
cR
Bla Key
k -> Key -> Color -> Color
goTip Key
k Color
Black
Whi Key
k -> Key -> Color -> Color
goTip Key
k Color
White
Nil Color
_ -> Color
Black
goTip :: Key -> Color -> Color
goTip Key
k Color
c
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = let !(# Color
cL #) = Color -> (# Color #)
invert Color
c
in Color
cL
| Bool
otherwise = Color
c
lookupL :: Color -> Word -> Zebra -> Maybe Word
lookupL :: Color -> Key -> Zebra -> Maybe Key
lookupL !Color
x !Key
w = Zebra -> Zebra -> Maybe Key
go (Color -> Zebra
Nil Color
Black)
where
go :: Zebra -> Zebra -> Maybe Key
go !Zebra
v Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p -> Zebra -> Zebra -> Maybe Key
go Zebra
v Zebra
l
| Bool
otherwise -> Zebra -> Zebra -> Maybe Key
go Zebra
l Zebra
r
Bla Key
k -> Color -> Key -> Zebra -> Maybe Key
goTip Color
Black Key
k Zebra
v
Whi Key
k -> Color -> Key -> Zebra -> Maybe Key
goTip Color
White Key
k Zebra
v
Nil Color
_ -> Maybe Key
forall a. Maybe a
Nothing
goTip :: Color -> Key -> Zebra -> Maybe Key
goTip Color
c Key
k Zebra
v =
case Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k of
Bool
True
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 -> if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Maybe Key
forall a. a -> Maybe a
Just Key
w
else Maybe Key
forall a. Maybe a
Nothing
| Bool
otherwise -> Key -> Maybe Key
forall a. a -> Maybe a
Just (Key -> Maybe Key) -> Key -> Maybe Key
forall a b. (a -> b) -> a -> b
$! if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key
w
else Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
Bool
False
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> case Zebra
v of
Nil Color
_ -> Maybe Key
forall a. Maybe a
Nothing
Zebra
_ -> let !(# Key
kL #) = Zebra -> (# Key #)
keyR Zebra
v
in Key -> Maybe Key
forall a. a -> Maybe a
Just (Key -> Maybe Key) -> Key -> Maybe Key
forall a b. (a -> b) -> a -> b
$! Key
kL Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
| Bool
otherwise -> Key -> Maybe Key
forall a. a -> Maybe a
Just Key
w
findL
:: Word
-> Color
-> Word
-> Zebra
-> Word
findL :: Key -> Color -> Key -> Zebra -> Key
findL Key
d !Color
x !Key
w = Zebra -> Zebra -> Key
go (Color -> Zebra
Nil Color
Black)
where
go :: Zebra -> Zebra -> Key
go !Zebra
v Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p -> Zebra -> Zebra -> Key
go Zebra
v Zebra
l
| Bool
otherwise -> Zebra -> Zebra -> Key
go Zebra
l Zebra
r
Bla Key
k -> Color -> Key -> Zebra -> Key
goTip Color
Black Key
k Zebra
v
Whi Key
k -> Color -> Key -> Zebra -> Key
goTip Color
White Key
k Zebra
v
Nil Color
_ -> Key
d
goTip :: Color -> Key -> Zebra -> Key
goTip Color
c Key
k Zebra
v =
case Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k of
Bool
True
| Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 -> if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key
w
else Key
d
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Key
w
| Bool
otherwise -> Key
k Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
Bool
False
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> case Zebra
v of
Nil Color
_ -> Key
d
Zebra
_ -> let !(# Key
kL #) = Zebra -> (# Key #)
keyR Zebra
v
in Key
kL Key -> Key -> Key
forall a. Num a => a -> a -> a
- Key
1
| Bool
otherwise -> Key
w
lookupR :: Color -> Word -> Zebra -> Maybe Word
lookupR :: Color -> Key -> Zebra -> Maybe Key
lookupR !Color
x !Key
w = Zebra -> Zebra -> Maybe Key
go (Color -> Zebra
Nil Color
Black)
where
go :: Zebra -> Zebra -> Maybe Key
go !Zebra
v Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p -> Zebra -> Zebra -> Maybe Key
go Zebra
r Zebra
l
| Bool
otherwise -> Zebra -> Zebra -> Maybe Key
go Zebra
v Zebra
r
Bla Key
k -> Color -> Key -> Zebra -> Maybe Key
goTip Color
Black Key
k Zebra
v
Whi Key
k -> Color -> Key -> Zebra -> Maybe Key
goTip Color
White Key
k Zebra
v
Nil Color
_ -> Maybe Key
forall a. Maybe a
Nothing
goTip :: Color -> Key -> Zebra -> Maybe Key
goTip Color
c Key
k Zebra
v =
case Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k of
Bool
True -> Key -> Maybe Key
forall a. a -> Maybe a
Just (Key -> Maybe Key) -> Key -> Maybe Key
forall a b. (a -> b) -> a -> b
$! if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key
k
else Key
w
Bool
False
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Key -> Maybe Key
forall a. a -> Maybe a
Just Key
w
| Bool
otherwise -> case Zebra
v of
Nil Color
_ -> Maybe Key
forall a. Maybe a
Nothing
Zebra
_ -> let !(# Key
kR #) = Zebra -> (# Key #)
keyL Zebra
v
in Key -> Maybe Key
forall a. a -> Maybe a
Just Key
kR
findR
:: Word
-> Color
-> Word
-> Zebra
-> Word
findR :: Key -> Color -> Key -> Zebra -> Key
findR Key
d !Color
x !Key
w = Zebra -> Zebra -> Key
go (Color -> Zebra
Nil Color
Black)
where
go :: Zebra -> Zebra -> Key
go !Zebra
v Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p -> Zebra -> Zebra -> Key
go Zebra
r Zebra
l
| Bool
otherwise -> Zebra -> Zebra -> Key
go Zebra
v Zebra
r
Bla Key
k -> Color -> Key -> Zebra -> Key
goTip Color
Black Key
k Zebra
v
Whi Key
k -> Color -> Key -> Zebra -> Key
goTip Color
White Key
k Zebra
v
Nil Color
_ -> Key
d
goTip :: Color -> Key -> Zebra -> Key
goTip Color
c Key
k Zebra
v =
case Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k of
Bool
True
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Key
k
| Bool
otherwise -> Key
w
Bool
False
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Key
w
| Bool
otherwise -> case Zebra
v of
Nil Color
_ -> Key
d
Zebra
_ -> let !(# Key
kR #) = Zebra -> (# Key #)
keyL Zebra
v
in Key
kR
fillL :: Word -> Color -> Zebra -> Zebra
fillL :: Key -> Color -> Zebra -> Zebra
fillL Key
w Color
x
| Key
w Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
forall a. Bounded a => a
maxBound = \Zebra
_ -> Color -> Zebra
Mono Color
x
| Bool
otherwise = Key -> Color -> Zebra -> Zebra
unsafeFillL (Key
w Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
1) Color
x
unsafeFillL :: Word -> Color -> Zebra -> Zebra
unsafeFillL :: Key -> Color -> Zebra -> Zebra
unsafeFillL Key
w Color
x = \Zebra
t ->
case Key -> Color -> Zebra -> Zebra
fillL_ Key
w Color
x Zebra
t of
Nil Color
_ -> Color -> Zebra
Mono Color
x
Zebra
t' -> Zebra
t'
fillL_ :: Word -> Color -> Zebra -> Zebra
fillL_ :: Key -> Color -> Zebra -> Zebra
fillL_ !Key
w !Color
x = Zebra -> Zebra
go
where
go :: Zebra -> Zebra
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p
then Key -> Zebra -> Zebra -> Zebra
rebinL Key
p (Zebra -> Zebra
go Zebra
l) Zebra
r
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then let !(# Color
cL #) = Color -> (# Color #)
invert Color
cR
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
w (Key -> Color -> Zebra
tip Key
w Color
cL) Key
p Zebra
t
else Zebra
t
else if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p
then Zebra -> Zebra
go Zebra
r
else let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Color -> Zebra
tip Key
w Color
cR
Bla Key
k -> Color -> Key -> Zebra -> Zebra
goTip Color
Black Key
k Zebra
t
Whi Key
k -> Color -> Key -> Zebra -> Zebra
goTip Color
White Key
k Zebra
t
Nil Color
_ -> Zebra
t
goTip :: Color -> Key -> Zebra -> Zebra
goTip Color
c Key
k Zebra
t
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
k = if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else if Key
w Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
k
then Zebra
t
else Key -> Color -> Zebra
tip Key
w Color
c
| Bool
otherwise = if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then let !(# Color
cL #) = Color -> (# Color #)
invert Color
x
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
w (Key -> Color -> Zebra
tip Key
w Color
cL) Key
k Zebra
t
else Zebra
t
fillR :: Word -> Color -> Zebra -> Zebra
fillR :: Key -> Color -> Zebra -> Zebra
fillR Key
w Color
x = \Zebra
t ->
case Key -> Color -> Zebra -> Zebra
fillR_ Key
w Color
x Zebra
t of
Nil Color
_ -> Color -> Zebra
Mono Color
x
Zebra
t' -> Zebra
t'
fillR_ :: Word -> Color -> Zebra -> Zebra
fillR_ :: Key -> Color -> Zebra -> Zebra
fillR_ !Key
w !Color
x = Zebra -> Zebra
go
where
go :: Zebra -> Zebra
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p
then Zebra -> Zebra
go Zebra
l
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Color -> Zebra
tip Key
w Color
x
else Color -> Zebra
Nil Color
Black
else if Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
p Zebra
l (Zebra -> Zebra
go Zebra
r)
else let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
t
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
w (Key -> Color -> Zebra
tip Key
w Color
x) Key
p Zebra
t
Bla Key
k -> Color -> Key -> Zebra -> Zebra
goTip Color
Black Key
k Zebra
t
Whi Key
k -> Color -> Key -> Zebra -> Zebra
goTip Color
White Key
k Zebra
t
Nil Color
_ -> Zebra
t
goTip :: Color -> Key -> Zebra -> Zebra
goTip Color
c Key
k Zebra
t
| Key
w Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key
k = if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then if Key
w Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
k
then Zebra
t
else Key -> Color -> Zebra
tip Key
w Color
c
else Color -> Zebra
Nil Color
Black
| Bool
otherwise = if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
t
else if Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0
then Key -> Color -> Zebra
tip Key
w Color
x
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
w (Key -> Color -> Zebra
tip Key
w Color
x) Key
k Zebra
t
fillRange :: Range -> Color -> Zebra -> Zebra
fillRange :: Range -> Color -> Zebra -> Zebra
fillRange (UnsafeRange Key
wL Key
wR) Color
x
| Key
wL Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0 = Key -> Color -> Zebra -> Zebra
fillL Key
wR Color
x
| Key
wR Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
forall a. Bounded a => a
maxBound = Key -> Color -> Zebra -> Zebra
fillR Key
wL Color
x
| Bool
otherwise = Key -> Key -> Color -> Zebra -> Zebra
unsafeFillRange Key
wL (Key
wR Key -> Key -> Key
forall a. Num a => a -> a -> a
+ Key
1) Color
x
unsafeFillRange
:: Word
-> Word
-> Color
-> Zebra
-> Zebra
unsafeFillRange :: Key -> Key -> Color -> Zebra -> Zebra
unsafeFillRange Key
wL Key
wR Color
x Zebra
t =
case Color -> Key -> Key -> Zebra -> Zebra
fillRange_ Color
x Key
wL Key
wR Zebra
t of
Nil Color
_ -> Color -> Zebra
Mono Color
x
Zebra
t' -> Zebra
t'
fillRange_ :: Color -> Word -> Word -> Zebra -> Zebra
fillRange_ :: Color -> Key -> Key -> Zebra -> Zebra
fillRange_ !Color
x !Key
wL !Key
wR = Zebra -> Zebra
go
where
!mM :: Key
mM = Key -> Key -> Key
branchingBit Key
wL Key
wR
!pM :: Key
pM = Key -> Key -> Key
mask Key
wL Key
mM Key -> Key -> Key
forall a. Bits a => a -> a -> a
.|. Key
mM
binM :: Zebra
binM = let !(# Color
c #) = Color -> (# Color #)
invert Color
x
in Key -> Zebra -> Zebra -> Zebra
Bin Key
pM (Key -> Color -> Zebra
tip Key
wL Color
x) (Key -> Color -> Zebra
tip Key
wR Color
c)
go :: Zebra -> Zebra
go Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r ->
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
p Key
pM of
Ordering
EQ -> Key -> Zebra -> Zebra -> Zebra
rebin Key
p (Key -> Color -> Zebra -> Zebra
fillR_ Key
wL Color
x Zebra
l) (Key -> Color -> Zebra -> Zebra
fillL_ Key
wR Color
x Zebra
r)
Ordering
LT | Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
p -> Key -> Zebra -> Zebra -> Zebra
rebinR Key
p Zebra
l (Zebra -> Zebra
go Zebra
r)
| Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pM -> let l' :: Zebra
l' = if Key
wL Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
p
then Key -> Color -> Zebra -> Zebra
fillR_ Key
wL Color
x Zebra
l
else Key -> Zebra -> Zebra -> Zebra
rebinR Key
p Zebra
l (Key -> Color -> Zebra -> Zebra
fillR_ Key
wL Color
x Zebra
r)
!(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
l'
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
p Zebra
l' Key
pM (Key -> Color -> Zebra
tip Key
wR Color
cR)
| Bool
otherwise ->
let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
r
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
t
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
p Zebra
t Key
pM Zebra
binM
Ordering
GT | Key
p Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pM -> let r' :: Zebra
r' = if Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key
p
then Key -> Color -> Zebra -> Zebra
fillL_ Key
wR Color
x Zebra
r
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
p (Key -> Color -> Zebra -> Zebra
fillL_ Key
wR Color
x Zebra
l) Zebra
r
!(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pM (Key -> Color -> Zebra
tip Key
wL Color
x) Key
p Zebra
r'
else Zebra
r'
| Key
pM Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
p -> Key -> Zebra -> Zebra -> Zebra
rebinL Key
p (Zebra -> Zebra
go Zebra
l) Zebra
r
| Bool
otherwise ->
let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
l
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
p Zebra
t Key
pM Zebra
binM
else Zebra
t
Bla Key
k -> Key -> Color -> Zebra -> Zebra
goTip Key
k Color
Black Zebra
t
Whi Key
k -> Key -> Color -> Zebra -> Zebra
goTip Key
k Color
White Zebra
t
Nil Color
_ -> Zebra
t
goTip :: Key -> Color -> Zebra -> Zebra
goTip Key
k Color
c Zebra
t
| Key
wR Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
k = if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
k Zebra
t Key
pM Zebra
binM
else Zebra
t
| Key
k Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
wL = if Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
t
else if Key
k Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
0
then Zebra
binM
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
k Zebra
t Key
pM Zebra
binM
| Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x = Key -> Color -> Zebra
tip Key
wL Color
c
| Bool
otherwise = Key -> Color -> Zebra
tip Key
wR Color
c
colorL :: Zebra -> (# Color #)
colorL :: Zebra -> (# Color #)
colorL Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
_ -> Zebra -> (# Color #)
colorL Zebra
l
Bla Key
_ -> (# Color
Black #)
Zebra
_ -> (# Color
White #)
colorR :: Zebra -> (# Color #)
colorR :: Zebra -> (# Color #)
colorR Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
_ Zebra
r -> Zebra -> (# Color #)
colorR Zebra
r
Bla Key
_ -> (# Color
Black #)
Zebra
_ -> (# Color
White #)
keyL :: Zebra -> (# Word #)
keyL :: Zebra -> (# Key #)
keyL Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
l Zebra
_ -> Zebra -> (# Key #)
keyL Zebra
l
Bla Key
k -> (# Key
k #)
Whi Key
k -> (# Key
k #)
Nil Color
_ -> (# Key
0 #)
keyR :: Zebra -> (# Word #)
keyR :: Zebra -> (# Key #)
keyR Zebra
t =
case Zebra
t of
Bin Key
_ Zebra
_ Zebra
r -> Zebra -> (# Key #)
keyR Zebra
r
Bla Key
k -> (# Key
k #)
Whi Key
k -> (# Key
k #)
Nil Color
_ -> (# Key
0 #)
complement :: Zebra -> Zebra
complement :: Zebra -> Zebra
complement Zebra
t =
case Zebra
t of
Bin Key
p Zebra
l Zebra
r -> Key -> Zebra -> Zebra -> Zebra
Bin Key
p (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
l)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
r)
Bla Key
k -> Key -> Zebra
Whi Key
k
Whi Key
k -> Key -> Zebra
Bla Key
k
Nil Color
_ -> Zebra
t
union :: Color -> Zebra -> Zebra -> Zebra
union :: Color -> Zebra -> Zebra -> Zebra
union Color
x Zebra
l Zebra
r =
case Zebra
l of
Mono Color
c | Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Zebra
l
| Bool
otherwise -> Zebra
r
Zebra
_ ->
case Zebra
r of
Mono Color
c | Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Zebra
r
| Bool
otherwise -> Zebra
l
Zebra
_ ->
case Zebra -> Zebra -> Zebra
anyAny Zebra
l Zebra
r of
Nil Color
_ -> Color -> Zebra
Mono Color
x
Zebra
t -> Zebra
t
where
anyAny :: Zebra -> Zebra -> Zebra
anyAny Zebra
tA Zebra
tB =
case Zebra
tA of
Bin Key
pA Zebra
lA Zebra
rA -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA Zebra
tB
Bla Key
kA -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key
kA, Color
Black #) Zebra
tA Zebra
tB
Whi Key
kA -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key
kA, Color
White #) Zebra
tA Zebra
tB
Nil Color
_ -> Zebra
tA
tipAny :: (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin (# Key, Color #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
White
Nil Color
_ -> Zebra
tB
where
goTip :: Key -> Color -> Zebra
goTip Key
kB Color
cB
| Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB = if (Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x) Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== (Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
kB)
then Zebra
tA
else Zebra
tB
| Bool
otherwise = if Key
kA Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
kB Bool -> Bool -> Bool
|| ((Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x) Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== (Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
kB))
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
tA Key
kB Zebra
tB
binAny :: (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> (# Key, Zebra, Zebra #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
binBin (# Key, Zebra, Zebra #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin (# Key
kB, Color
Black #) Zebra
tB (# Key, Zebra, Zebra #)
uA Zebra
tA
Whi Key
kB -> (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin (# Key
kB, Color
White #) Zebra
tB (# Key, Zebra, Zebra #)
uA Zebra
tA
Nil Color
_ -> Zebra
tB
tipBin :: (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
pB
then if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key, Color #)
uA Zebra
tA Zebra
lB
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB ((# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key, Color #)
uA Zebra
tA Zebra
lB) Zebra
rB
else let !(# Color
cB #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tA
else Zebra
tB
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
tA Key
pB Zebra
tB
else if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB Zebra
lB ((# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key, Color #)
uA Zebra
tA Zebra
rB)
else (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key, Color #)
uA Zebra
tA Zebra
rB
else let !(# Color
cB #) = Zebra -> (# Color #)
colorR Zebra
rB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tB
else Zebra
tA
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
tA Key
pB Zebra
tB
else Color -> Zebra
Nil Color
Black
binBin :: (# Key, Zebra, Zebra #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
binBin uA :: (# Key, Zebra, Zebra #)
uA@(# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA uB :: (# Key, Zebra, Zebra #)
uB@(# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
pA Key
pB of
Ordering
EQ -> Key -> Zebra -> Zebra -> Zebra
rebin Key
pA (Zebra -> Zebra -> Zebra
anyAny Zebra
lA Zebra
lB) (Zebra -> Zebra -> Zebra
anyAny Zebra
rA Zebra
rB)
Ordering
LT | Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pA -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
pA Zebra
lA ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA)
else (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA
| Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rA
in if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB) Zebra
rB
| Bool
otherwise ->
let !(# Color
cA #) = Zebra -> (# Color #)
colorR Zebra
rA
!(# Color
cB #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tA
else Zebra
tB
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pA Zebra
tA Key
pB Zebra
tB
Ordering
GT | Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lA
in if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB Zebra
lB ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB)
else (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB
| Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pA -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
in if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
pA ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA) Zebra
rA
| Bool
otherwise ->
let !(# Color
cB #) = Zebra -> (# Color #)
colorR Zebra
rB
!(# Color
cA #) = Zebra -> (# Color #)
colorL Zebra
lA
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tB
else Zebra
tA
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pA Zebra
tA Key
pB Zebra
tB
else Color -> Zebra
Nil Color
Black
intersection :: Color -> Zebra -> Zebra -> Zebra
intersection :: Color -> Zebra -> Zebra -> Zebra
intersection Color
x =
let !(# Color
c #) = Color -> (# Color #)
invert Color
x
in Color -> Zebra -> Zebra -> Zebra
union Color
c
disjoint :: Color -> Zebra -> Zebra -> Bool
disjoint :: Color -> Zebra -> Zebra -> Bool
disjoint Color
x Zebra
l Zebra
r =
case Zebra
l of
Mono Color
c -> Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
x
Zebra
_ ->
case Zebra
r of
Mono Color
c -> Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
x
Zebra
_ -> Zebra -> Zebra -> Bool
anyAny Zebra
l Zebra
r
where
anyAny :: Zebra -> Zebra -> Bool
anyAny Zebra
tA Zebra
tB =
case Zebra
tA of
Bin Key
pA Zebra
lA Zebra
rA -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Bool
binAny (# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA Zebra
tB
Bla Key
kA -> (# Key, Color #) -> Zebra -> Zebra -> Bool
forall {t}. (# Key, Color #) -> t -> Zebra -> Bool
tipAny (# Key
kA, Color
Black #) Zebra
tA Zebra
tB
Whi Key
kA -> (# Key, Color #) -> Zebra -> Zebra -> Bool
forall {t}. (# Key, Color #) -> t -> Zebra -> Bool
tipAny (# Key
kA, Color
White #) Zebra
tA Zebra
tB
Nil Color
_ -> Bool
False
tipAny :: (# Key, Color #) -> t -> Zebra -> Bool
tipAny uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) t
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> (# Key, Color #) -> t -> (# Key, Zebra, Zebra #) -> Bool
tipBin (# Key, Color #)
uA t
tA (# Key
pB, Zebra
lB, Zebra
rB #)
Bla Key
kB -> Key -> Color -> Bool
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> Bool
goTip Key
kB Color
White
Nil Color
_ -> Bool
False
where
goTip :: Key -> Color -> Bool
goTip Key
kB Color
cB
| Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB = Bool
False
| Bool
otherwise = Key
kA Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
kB Bool -> Bool -> Bool
|| ((Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x) Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== (Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
kB))
binAny :: (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Bool
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> (# Key, Zebra, Zebra #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Bool
binBin (# Key, Zebra, Zebra #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> (# Key, Color #) -> Zebra -> (# Key, Zebra, Zebra #) -> Bool
forall {t}.
(# Key, Color #) -> t -> (# Key, Zebra, Zebra #) -> Bool
tipBin (# Key
kB, Color
Black #) Zebra
tB (# Key, Zebra, Zebra #)
uA
Whi Key
kB -> (# Key, Color #) -> Zebra -> (# Key, Zebra, Zebra #) -> Bool
forall {t}.
(# Key, Color #) -> t -> (# Key, Zebra, Zebra #) -> Bool
tipBin (# Key
kB, Color
White #) Zebra
tB (# Key, Zebra, Zebra #)
uA
Nil Color
_ -> Bool
False
tipBin :: (# Key, Color #) -> t -> (# Key, Zebra, Zebra #) -> Bool
tipBin uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) t
tA (# Key
pB, Zebra
lB, Zebra
rB #) =
if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
pB
then if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB
then Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x Bool -> Bool -> Bool
&& (# Key, Color #) -> t -> Zebra -> Bool
tipAny (# Key, Color #)
uA t
tA Zebra
lB
else let !(# Color
cB #) = Zebra -> (# Color #)
colorL Zebra
lB
in Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
cB Bool -> Bool -> Bool
&& Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
else if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB
then Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
x Bool -> Bool -> Bool
&& (# Key, Color #) -> t -> Zebra -> Bool
tipAny (# Key, Color #)
uA t
tA Zebra
rB
else let !(# Color
cB #) = Zebra -> (# Color #)
colorR Zebra
rB
in Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
cB Bool -> Bool -> Bool
&& Color
cB Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
binBin :: (# Key, Zebra, Zebra #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Bool
binBin uA :: (# Key, Zebra, Zebra #)
uA@(# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA uB :: (# Key, Zebra, Zebra #)
uB@(# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
pA Key
pB of
Ordering
EQ -> Zebra -> Zebra -> Bool
anyAny Zebra
lA Zebra
lB Bool -> Bool -> Bool
&& Zebra -> Zebra -> Bool
anyAny Zebra
rA Zebra
rB
Ordering
LT | Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pA -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
x Bool -> Bool -> Bool
&& (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Bool
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA
| Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rA
in Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x Bool -> Bool -> Bool
&& (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Bool
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB
| Bool
otherwise ->
let !(# Color
cA #) = Zebra -> (# Color #)
colorR Zebra
rA
!(# Color
cB #) = Zebra -> (# Color #)
colorL Zebra
lB
in Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
cB Bool -> Bool -> Bool
&& Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
Ordering
GT | Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lA
in Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
x Bool -> Bool -> Bool
&& (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Bool
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB
| Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pA -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
in Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x Bool -> Bool -> Bool
&& (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Bool
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA
| Bool
otherwise ->
let !(# Color
cB #) = Zebra -> (# Color #)
colorR Zebra
rB
!(# Color
cA #) = Zebra -> (# Color #)
colorL Zebra
lA
in Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
/= Color
cB Bool -> Bool -> Bool
&& Color
cB Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
difference :: Color -> Zebra -> Zebra -> Zebra
difference :: Color -> Zebra -> Zebra -> Zebra
difference Color
x Zebra
l Zebra
r =
case Zebra
l of
Mono Color
c | Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
r
| Bool
otherwise -> Zebra
l
Zebra
_ ->
case Zebra
r of
Mono Color
c | Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> let !(# Color
x' #) = Color -> (# Color #)
invert Color
x
in Color -> Zebra
Mono Color
x'
| Bool
otherwise -> Zebra
l
Zebra
_ ->
case S -> Zebra -> Zebra -> Zebra
anyAny S
L Zebra
l Zebra
r of
Nil Color
_ -> let !(# Color
c #) = Color -> (# Color #)
invert Color
x
in Color -> Zebra
Mono Color
c
Zebra
t -> Zebra
t
where
anyAny :: S -> Zebra -> Zebra -> Zebra
anyAny S
s Zebra
tA Zebra
tB =
case Zebra
tA of
Bin Key
pA Zebra
lA Zebra
rA -> S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA Zebra
tB
Bla Key
kA -> S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key
kA, Color
Black #) Zebra
tA Zebra
tB
Whi Key
kA -> S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key
kA, Color
White #) Zebra
tA Zebra
tB
Nil Color
_ -> Zebra
tA
tipAny :: S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> S
-> (# Key, Color #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> Zebra
tipBin S
s (# Key, Color #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
White
Nil Color
_ -> Zebra
tB
where
goTip :: Key -> Color -> Zebra
goTip Key
kB Color
cB =
case S
s of
S
L -> Key -> Color -> Zebra -> Key -> Color -> Zebra
goTipL Key
kA Color
cA Zebra
tA Key
kB Color
cB
S
R -> Key -> Color -> Zebra -> Key -> Color -> Zebra
goTipL Key
kB Color
cB Zebra
tB Key
kA Color
cA
goTipL :: Key -> Color -> Zebra -> Key -> Color -> Zebra
goTipL Key
kL Color
cL Zebra
tL Key
kR Color
cR =
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
kL Key
kR of
Ordering
EQ -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then Color -> Zebra
Nil Color
Black
else Zebra
tL
Ordering
LT -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then let !(# Color
c #) = Color -> (# Color #)
invert Color
x
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kL Zebra
tL Key
kR (Key -> Color -> Zebra
tip Key
kR Color
c)
else Color -> Zebra
Nil Color
Black
else if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Color -> Zebra
tip Key
kR Color
x
else Zebra
tL
Ordering
GT -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kL Zebra
tL Key
kR (Key -> Color -> Zebra
tip Key
kR Color
x)
else if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tL
else Key -> Color -> Zebra
tip Key
kR Color
cL
binAny :: S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> S
-> (# Key, Zebra, Zebra #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> Zebra
binBin S
s (# Key, Zebra, Zebra #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
White
Nil Color
_ -> Zebra
tB
where
goTip :: Key -> Color -> Zebra
goTip Key
kB Color
cB =
let !(# S
s' #) = S -> (# S #)
other S
s
in S
-> (# Key, Color #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> Zebra
tipBin S
s' (# Key
kB, Color
cB #) Zebra
tB (# Key, Zebra, Zebra #)
uA Zebra
tA
tipBin :: S
-> (# Key, Color #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> Zebra
tipBin S
s uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
case S
s of
S
L -> if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
pB
then if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB (S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
lB
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
tA
Key
pB (Zebra -> Zebra) -> Zebra -> Zebra
forall a b. (a -> b) -> a -> b
$ Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else Color -> Zebra
Nil Color
Black
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else Zebra
tA
else if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
rB
else Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
rB)
else let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cL
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
tA
Key
pB (Zebra -> Zebra) -> Zebra -> Zebra
forall a b. (a -> b) -> a -> b
$ Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tA
else Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
S
R -> if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
pB
then if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
lB
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB (S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
lB) Zebra
rB
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA (Key -> Color -> Zebra
tip Key
kA Color
x) Key
pB Zebra
tB
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Color -> Zebra
tip Key
kA Color
cR
else Zebra
tB
else if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB Zebra
lB (S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
rB)
else S -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny S
s (# Key, Color #)
uA Zebra
tA Zebra
rB
else let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cL
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then let !(# Color
c #) = Color -> (# Color #)
invert Color
x
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA (Key -> Color -> Zebra
tip Key
kA Color
c) Key
pB Zebra
tB
else Color -> Zebra
Nil Color
Black
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tB
else Key -> Color -> Zebra
tip Key
kA Color
cL
binBin :: S
-> (# Key, Zebra, Zebra #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> Zebra
binBin S
s uA :: (# Key, Zebra, Zebra #)
uA@(# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA uB :: (# Key, Zebra, Zebra #)
uB@(# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
pA Key
pB of
Ordering
EQ -> Key -> Zebra -> Zebra -> Zebra
rebin Key
pB (S -> Zebra -> Zebra -> Zebra
anyAny S
s Zebra
lA Zebra
lB) (S -> Zebra -> Zebra -> Zebra
anyAny S
s Zebra
rA Zebra
rB)
Ordering
LT | Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pA -> let !(# S
s' #) = S -> (# S #)
other S
s
!(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in case S
s of
S
L -> if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
pA Zebra
lA (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA)
else S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA
S
R -> if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA
else Key -> Zebra -> Zebra -> Zebra
rebinR Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA)
| Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rA
in case S
s of
S
L -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB
S
R -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB) Zebra
rB
| Bool
otherwise ->
let !(# Color
cA #) = Zebra -> (# Color #)
colorR Zebra
rA
!(# Color
cB #) = Zebra -> (# Color #)
colorL Zebra
lB
in case S
s of
S
L -> if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pA Zebra
tA
Key
pB (Zebra -> Zebra) -> Zebra -> Zebra
forall a b. (a -> b) -> a -> b
$ Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else Color -> Zebra
Nil Color
Black
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else Zebra
tA
S
R -> if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pB Zebra
tB
Key
pA (Zebra -> Zebra) -> Zebra -> Zebra
forall a b. (a -> b) -> a -> b
$ Key -> Zebra -> Zebra -> Zebra
Bin Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
Bin Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
else Zebra
tB
Ordering
GT | Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lA
in case S
s of
S
L -> if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB
else Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB)
S
R -> if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB Zebra
lB (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB)
else S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB
| Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pA -> let !(# S
s' #) = S -> (# S #)
other S
s
!(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
in case S
s of
S
L -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA
else Key -> Zebra -> Zebra -> Zebra
rebinL Key
pA (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA) Zebra
rA
S
R -> if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Zebra -> Zebra
rebinL Key
pA (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
else S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA
| Bool
otherwise ->
let !(# Color
cB #) = Zebra -> (# Color #)
colorR Zebra
rB
!(# Color
cA #) = Zebra -> (# Color #)
colorL Zebra
lA
in case S
s of
S
L -> if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Color -> Zebra
Nil Color
Black
else Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pA Zebra
tA
Key
pB (Zebra -> Zebra) -> Zebra -> Zebra
forall a b. (a -> b) -> a -> b
$ Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tA
else Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
S
R -> if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pB Zebra
tB
Key
pA (Zebra -> Zebra) -> Zebra -> Zebra
forall a b. (a -> b) -> a -> b
$ Key -> Zebra -> Zebra -> Zebra
Bin Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
else Color -> Zebra
Nil Color
Black
else if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then Zebra
tB
else Key -> Zebra -> Zebra -> Zebra
Bin Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
symmetricDifference :: Color -> Zebra -> Zebra -> Zebra
symmetricDifference :: Color -> Zebra -> Zebra -> Zebra
symmetricDifference Color
xFG Zebra
l Zebra
r =
case Zebra
l of
Mono Color
c | Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG -> Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
r
| Bool
otherwise -> Zebra
r
Zebra
_ ->
case Zebra
r of
Mono Color
c | Color
c Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG -> Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
l
| Bool
otherwise -> Zebra
l
Zebra
_ ->
case Zebra -> Zebra -> Zebra
anyAny Zebra
l Zebra
r of
Nil Color
c -> Color -> Zebra
Mono Color
c
Zebra
t -> Zebra
t
where
anyAny :: Zebra -> Zebra -> Zebra
anyAny Zebra
tA Zebra
tB =
case Zebra
tA of
Bin Key
pA Zebra
lA Zebra
rA -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA Zebra
tB
Bla Key
kA -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key
kA, Color
Black #) Zebra
tA Zebra
tB
Whi Key
kA -> (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key
kA, Color
White #) Zebra
tA Zebra
tB
Nil Color
_ -> Zebra
tA
tipAny :: (# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin (# Key, Color #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> Zebra
goTip Key
kB Color
White
Nil Color
_ -> Zebra
tB
where
goTip :: Key -> Color -> Zebra
goTip Key
kB Color
cB
| Key
kA Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
kB = Color -> Zebra
Nil (Color -> Zebra) -> Color -> Zebra
forall a b. (a -> b) -> a -> b
$ if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB
then let !(# Color
xBG #) = Color -> (# Color #)
invert Color
xFG
in Color
xBG
else Color
xFG
| Bool
otherwise = let nA :: Zebra
nA | (Color
cB Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG) Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== (Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
kB) = Zebra
tA
| Bool
otherwise = let !(# Color
c #) = Color -> (# Color #)
invert Color
cA
in Key -> Color -> Zebra
tip Key
kA Color
c
nB :: Zebra
nB | (Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG) Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== (Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
kB) = let !(# Color
c #) = Color -> (# Color #)
invert Color
cB
in Key -> Color -> Zebra
tip Key
kB Color
c
| Bool
otherwise = Zebra
tB
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
nA Key
kB Zebra
nB
binAny :: (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> (# Key, Zebra, Zebra #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
binBin (# Key, Zebra, Zebra #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin (# Key
kB, Color
Black #) Zebra
tB (# Key, Zebra, Zebra #)
uA Zebra
tA
Whi Key
kB -> (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin (# Key
kB, Color
White #) Zebra
tB (# Key, Zebra, Zebra #)
uA Zebra
tA
Nil Color
_ -> Zebra
tB
tipBin :: (# Key, Color #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
tipBin uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
pB
then if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB
then let r' :: Zebra
r' | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB
| Bool
otherwise = Zebra
rB
in Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB ((# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key, Color #)
uA Zebra
tA Zebra
lB) Zebra
r'
else let !(# Color
cL #) = Zebra -> (# Color #)
colorL Zebra
lB
nA :: Zebra
nA | Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
tA
| Bool
otherwise = let !(# Color
c #) = Color -> (# Color #)
invert Color
cA
in Key -> Color -> Zebra
tip Key
kA Color
c
nB :: Zebra
nB | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
| Bool
otherwise = Zebra
tB
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
nA Key
pB Zebra
nB
else if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB
then let l' :: Zebra
l' | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
lB
| Bool
otherwise = Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB
in Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB Zebra
l' ((# Key, Color #) -> Zebra -> Zebra -> Zebra
tipAny (# Key, Color #)
uA Zebra
tA Zebra
rB)
else let !(# Color
cR #) = Zebra -> (# Color #)
colorR Zebra
rB
nA :: Zebra
nA | Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = let !(# Color
c #) = Color -> (# Color #)
invert Color
cA
in Key -> Color -> Zebra
tip Key
kA Color
c
| Bool
otherwise = Zebra
tA
nB :: Zebra
nB | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
tB
| Bool
otherwise = Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
kA Zebra
nA Key
pB Zebra
nB
binBin :: (# Key, Zebra, Zebra #)
-> Zebra -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra
binBin uA :: (# Key, Zebra, Zebra #)
uA@(# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA uB :: (# Key, Zebra, Zebra #)
uB@(# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
pA Key
pB of
Ordering
EQ -> Key -> Zebra -> Zebra -> Zebra
rebin Key
pA (Zebra -> Zebra -> Zebra
anyAny Zebra
lA Zebra
lB) (Zebra -> Zebra -> Zebra
anyAny Zebra
rA Zebra
rB)
Ordering
LT | Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pA -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
l' :: Zebra
l' | Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
lA
| Bool
otherwise = Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA
in Key -> Zebra -> Zebra -> Zebra
rebinR Key
pA Zebra
l' ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA)
| Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rA
r' :: Zebra
r' | Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB
| Bool
otherwise = Zebra
rB
in Key -> Zebra -> Zebra -> Zebra
rebinL Key
pB ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB) Zebra
r'
| Bool
otherwise ->
let !(# Color
cA #) = Zebra -> (# Color #)
colorR Zebra
rA
!(# Color
cB #) = Zebra -> (# Color #)
colorL Zebra
lB
nA :: Zebra
nA | Color
cB Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
tA
| Bool
otherwise = Key -> Zebra -> Zebra -> Zebra
Bin Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
nB :: Zebra
nB | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
| Bool
otherwise = Zebra
tB
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pA Zebra
nA Key
pB Zebra
nB
Ordering
GT | Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lA
l' :: Zebra
l' | Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
lB
| Bool
otherwise = Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB
in Key -> Zebra -> Zebra -> Zebra
rebinR Key
pB Zebra
l' ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB)
| Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pA -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
r' :: Zebra
r' | Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA
| Bool
otherwise = Zebra
rA
in Key -> Zebra -> Zebra -> Zebra
rebinL Key
pA ((# Key, Zebra, Zebra #) -> Zebra -> Zebra -> Zebra
binAny (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA) Zebra
r'
| Bool
otherwise ->
let !(# Color
cB #) = Zebra -> (# Color #)
colorR Zebra
rB
!(# Color
cA #) = Zebra -> (# Color #)
colorL Zebra
lA
nA :: Zebra
nA | Color
cB Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Key -> Zebra -> Zebra -> Zebra
Bin Key
pA (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lA)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rA)
| Bool
otherwise = Zebra
tA
nB :: Zebra
nB | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
xFG = Zebra
tB
| Bool
otherwise = Key -> Zebra -> Zebra -> Zebra
Bin Key
pB (Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
lB)
(Zebra -> Zebra
Data.Zebra.Word.Internal.complement Zebra
rB)
in Key -> Zebra -> Key -> Zebra -> Zebra
join Key
pA Zebra
nA Key
pB Zebra
nB
data S = L | R
deriving Int -> S -> ShowS
[S] -> ShowS
S -> String
(Int -> S -> ShowS) -> (S -> String) -> ([S] -> ShowS) -> Show S
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> S -> ShowS
showsPrec :: Int -> S -> ShowS
$cshow :: S -> String
show :: S -> String
$cshowList :: [S] -> ShowS
showList :: [S] -> ShowS
Show
other :: S -> (# S #)
other :: S -> (# S #)
other S
L = (# S
R #)
other S
R = (# S
L #)
compare :: Color -> Zebra -> Zebra -> PartialOrdering
compare :: Color -> Zebra -> Zebra -> PartialOrdering
compare Color
x Zebra
l Zebra
r =
case Zebra
l of
Mono Color
cA ->
case Zebra
r of
Mono Color
cB | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB -> PartialOrdering
Equal
| Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> PartialOrdering
Superset
| Bool
otherwise -> PartialOrdering
Subset
Zebra
_ | Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> PartialOrdering
Superset
| Bool
otherwise -> PartialOrdering
Subset
Zebra
_ ->
case Zebra
r of
Mono Color
cB | Color
cB Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x -> PartialOrdering
Subset
| Bool
otherwise -> PartialOrdering
Superset
Zebra
_ -> S -> Zebra -> Zebra -> PartialOrdering
anyAny S
L Zebra
l Zebra
r
where
anyAny :: S -> Zebra -> Zebra -> PartialOrdering
anyAny S
s Zebra
tA Zebra
tB =
case Zebra
tA of
Bin Key
pA Zebra
lA Zebra
rA -> S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> PartialOrdering
binAny S
s (# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA Zebra
tB
Bla Key
kA -> S -> (# Key, Color #) -> Zebra -> Zebra -> PartialOrdering
forall {t}. S -> (# Key, Color #) -> t -> Zebra -> PartialOrdering
tipAny S
s (# Key
kA, Color
Black #) Zebra
tA Zebra
tB
Whi Key
kA -> S -> (# Key, Color #) -> Zebra -> Zebra -> PartialOrdering
forall {t}. S -> (# Key, Color #) -> t -> Zebra -> PartialOrdering
tipAny S
s (# Key
kA, Color
White #) Zebra
tA Zebra
tB
Nil Color
_ -> PartialOrdering
Incomparable
tipAny :: S -> (# Key, Color #) -> t -> Zebra -> PartialOrdering
tipAny S
s uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) t
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> S
-> (# Key, Color #)
-> t
-> (# Key, Zebra, Zebra #)
-> PartialOrdering
tipBin S
s (# Key, Color #)
uA t
tA (# Key
pB, Zebra
lB, Zebra
rB #)
Bla Key
kB -> Key -> Color -> PartialOrdering
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> PartialOrdering
goTip Key
kB Color
White
Nil Color
_ -> PartialOrdering
Incomparable
where
goTip :: Key -> Color -> PartialOrdering
goTip Key
kB Color
cB
| Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cB = if Key
kA Key -> Key -> Bool
forall a. Eq a => a -> a -> Bool
== Key
kB
then PartialOrdering
Equal
else if (Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x) Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== (Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
kB)
then case S
s of
S
L -> PartialOrdering
Superset
S
R -> PartialOrdering
Subset
else case S
s of
S
L -> PartialOrdering
Subset
S
R -> PartialOrdering
Superset
| Bool
otherwise = PartialOrdering
Incomparable
binAny :: S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> PartialOrdering
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
tB =
case Zebra
tB of
Bin Key
pB Zebra
lB Zebra
rB -> S
-> (# Key, Zebra, Zebra #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> PartialOrdering
binBin S
s (# Key, Zebra, Zebra #)
uA Zebra
tA (# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB
Bla Key
kB -> Key -> Color -> PartialOrdering
goTip Key
kB Color
Black
Whi Key
kB -> Key -> Color -> PartialOrdering
goTip Key
kB Color
White
Nil Color
_ -> PartialOrdering
Incomparable
where
goTip :: Key -> Color -> PartialOrdering
goTip Key
kB Color
cB = let !(# S
s' #) = S -> (# S #)
other S
s
in S
-> (# Key, Color #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> PartialOrdering
forall {t}.
S
-> (# Key, Color #)
-> t
-> (# Key, Zebra, Zebra #)
-> PartialOrdering
tipBin S
s' (# Key
kB, Color
cB #) Zebra
tB (# Key, Zebra, Zebra #)
uA
tipBin :: S
-> (# Key, Color #)
-> t
-> (# Key, Zebra, Zebra #)
-> PartialOrdering
tipBin S
s uA :: (# Key, Color #)
uA@(# Key
kA, Color
cA #) t
tA (# Key
pB, Zebra
lB, Zebra
rB #) =
if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
< Key
pB
then if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB
then let !(# PartialOrdering
o #) = if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> (# PartialOrdering
Superset #)
S
R -> (# PartialOrdering
Subset #)
else case S
s of
S
L -> (# PartialOrdering
Subset #)
S
R -> (# PartialOrdering
Superset #)
in PartialOrdering -> PartialOrdering -> PartialOrdering
order PartialOrdering
o (S -> (# Key, Color #) -> t -> Zebra -> PartialOrdering
tipAny S
s (# Key, Color #)
uA t
tA Zebra
lB)
else let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> PartialOrdering
Superset
S
R -> PartialOrdering
Subset
else case S
s of
S
L -> PartialOrdering
Subset
S
R -> PartialOrdering
Superset
else PartialOrdering
Incomparable
else if Key
kA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB
then let !(# PartialOrdering
o #) = if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> (# PartialOrdering
Subset #)
S
R -> (# PartialOrdering
Superset #)
else case S
s of
S
L -> (# PartialOrdering
Superset #)
S
R -> (# PartialOrdering
Subset #)
in PartialOrdering -> PartialOrdering -> PartialOrdering
order PartialOrdering
o (S -> (# Key, Color #) -> t -> Zebra -> PartialOrdering
tipAny S
s (# Key, Color #)
uA t
tA Zebra
rB)
else let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
in if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cL
then if Color
cA Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> PartialOrdering
Subset
S
R -> PartialOrdering
Superset
else case S
s of
S
L -> PartialOrdering
Superset
S
R -> PartialOrdering
Subset
else PartialOrdering
Incomparable
binBin :: S
-> (# Key, Zebra, Zebra #)
-> Zebra
-> (# Key, Zebra, Zebra #)
-> Zebra
-> PartialOrdering
binBin S
s uA :: (# Key, Zebra, Zebra #)
uA@(# Key
pA, Zebra
lA, Zebra
rA #) Zebra
tA uB :: (# Key, Zebra, Zebra #)
uB@(# Key
pB, Zebra
lB, Zebra
rB #) Zebra
tB =
case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Key
pA Key
pB of
Ordering
EQ -> PartialOrdering -> PartialOrdering -> PartialOrdering
order (S -> Zebra -> Zebra -> PartialOrdering
anyAny S
s Zebra
lA Zebra
lB) (S -> Zebra -> Zebra -> PartialOrdering
anyAny S
s Zebra
rA Zebra
rB)
Ordering
LT | Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pA -> let !(# S
s' #) = S -> (# S #)
other S
s
!(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
!(# PartialOrdering
o #) = if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> (# PartialOrdering
Superset #)
S
R -> (# PartialOrdering
Subset #)
else case S
s of
S
L -> (# PartialOrdering
Subset #)
S
R -> (# PartialOrdering
Superset #)
in PartialOrdering -> PartialOrdering -> PartialOrdering
order PartialOrdering
o (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> PartialOrdering
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
rA)
| Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pB -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rA
!(# PartialOrdering
o #) = if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> (# PartialOrdering
Superset #)
S
R -> (# PartialOrdering
Subset #)
else case S
s of
S
L -> (# PartialOrdering
Subset #)
S
R -> (# PartialOrdering
Superset #)
in PartialOrdering -> PartialOrdering -> PartialOrdering
order PartialOrdering
o (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> PartialOrdering
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
lB)
| Bool
otherwise -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rA
!(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lB
in if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> PartialOrdering
Superset
S
R -> PartialOrdering
Subset
else case S
s of
S
L -> PartialOrdering
Subset
S
R -> PartialOrdering
Superset
else PartialOrdering
Incomparable
Ordering
GT | Key
pA Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
<= Key -> Key
upper Key
pB -> let !(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lA
!(# PartialOrdering
o #) = if Color
cR Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> (# PartialOrdering
Subset #)
S
R -> (# PartialOrdering
Superset #)
else case S
s of
S
L -> (# PartialOrdering
Superset #)
S
R -> (# PartialOrdering
Subset #)
in PartialOrdering -> PartialOrdering -> PartialOrdering
order PartialOrdering
o (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> PartialOrdering
binAny S
s (# Key, Zebra, Zebra #)
uA Zebra
tA Zebra
rB)
| Key
pB Key -> Key -> Bool
forall a. Ord a => a -> a -> Bool
>= Key -> Key
lower Key
pA -> let !(# S
s' #) = S -> (# S #)
other S
s
!(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
!(# PartialOrdering
o #) = if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> (# PartialOrdering
Subset #)
S
R -> (# PartialOrdering
Superset #)
else case S
s of
S
L -> (# PartialOrdering
Superset #)
S
R -> (# PartialOrdering
Subset #)
in PartialOrdering -> PartialOrdering -> PartialOrdering
order PartialOrdering
o (S -> (# Key, Zebra, Zebra #) -> Zebra -> Zebra -> PartialOrdering
binAny S
s' (# Key, Zebra, Zebra #)
uB Zebra
tB Zebra
lA)
| Bool
otherwise -> let !(# Color
cL #) = Zebra -> (# Color #)
colorR Zebra
rB
!(# Color
cR #) = Zebra -> (# Color #)
colorL Zebra
lA
in if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
cR
then if Color
cL Color -> Color -> Bool
forall a. Eq a => a -> a -> Bool
== Color
x
then case S
s of
S
L -> PartialOrdering
Subset
S
R -> PartialOrdering
Superset
else case S
s of
S
L -> PartialOrdering
Superset
S
R -> PartialOrdering
Subset
else PartialOrdering
Incomparable