{-# 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



-- | Space partition colors.
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 #)



-- | Fully-strict one-dimensional space partitioning tree.
data Zebra = Bin
               {-# UNPACK #-} !Prefix
               !Zebra                 -- ^ Masked bit is @0@.
               !Zebra                 -- ^ Masked bit is not @0@.

           | Bla
               -- | Invariant: can only be @0@ as the root of the tree.
               {-# UNPACK #-} !Key

           | Whi
               -- | Invariant: can only be @0@ as the root of the tree.
               {-# UNPACK #-} !Key

           | Nil                     -- ^ Invariant: unreachable state.
               {-# UNPACK #-} !Color

-- | Tree is represented as a list of closed intervals of all 'White' keys.
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



-- | \(\mathcal{O}(1)\).
--   All keys are the same color.
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 #-}
-- | Knowing that the prefices of two non-'Nil' trees disagree, construct a 'Bin'.
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 #-}
-- | Reconstruct a 'Bin' knowing that either of the sides may now be a 'Nil'.
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 #-}
-- | Reconstruct a 'Bin' knowing that the left side may now be a 'Nil'.
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 #-}
-- | Reconstruct a 'Bin' knowing that the right side may now be a 'Nil'.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Check whether all keys smaller than or equal to the given key are of the same color.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Check whether all keys greater than or equal to the given key are of the same color.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Check whether all keys in the range are of the same color.
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)

-- | \(\mathcal{O}(\min(n,W))\).
--   Check whether all keys in the range are of the same color.
--
--    \(k_R\) __must__ be greater than \(k_L\).
unsafeMonoRange
  :: Word  -- ^ \(k_L\)
  -> Word  -- ^ \(k_R\)
  -> 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



-- | \(\mathcal{O}(n)\).
--   Calculate the number of keys of the given color.
--   The returned number is guaranteed to be in the \([0, 2^W]\) interval.
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

-- | \(\mathcal{O}(n)\).
--   Calculate the number of keys of the given color.
--
--   The tree __must not__ be 'Mono'.
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



-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Calculate the number of keys of the given color that are smaller than
--   or equal to the given key.
--   The returned number is guaranteed to be in the \([0, 2^W]\) interval.
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)

-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Calculate the number of keys of the given color that are smaller than the given key.
--
--   The given key __must not__ be equal to @'Data.Bits.maxBound'@.
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



-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Calculate the number of keys of the given color that are greater than
--   or equal to the given key.
--   The returned number is guaranteed to be in the \([0, 2^W]\) interval.
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

-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Calculate the number of keys of the given color that are greater than
--   or equal to the given key.
--
--   The given key __must not__ be @0@.
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



-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Calculate the number of keys of the given color in the range.
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)

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Calculate the number of keys of the given color in the \([k_L, k_R)\) interval.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeSizeRange
  :: Color
  -> Word  -- ^ \(k_L\)
  -> Word  -- ^ \(k_R\)
  -> 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



-- | \(\mathcal{O}(n_R)\).
--   Fold left-to-right over the ranges.
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
                     #)



-- | \(\mathcal{O}(n_R)\).
--   Fold left-to-right over the ranges of all the keys smaller than
--   or equal to the given one.
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



-- | \(\mathcal{O}(n_R)\).
--   Fold left-to-right over the ranges of all the keys greater than
--   or equal to the given one.
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 #)



-- | \(\mathcal{O}(\min(n,W) + n_{I_R})\).
--   Fold left-to-right over the ranges of all the keys in the given range.
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

-- | \(\mathcal{O}(n)\).
--   Fold left-to-right over the ranges of all the keys
--   in the \([k_L, k_R)\) interval.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeFoldlRange
  :: Word                       -- ^ \(k_L\)
  -> Word                       -- ^ \(k_R\)
  -> (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



-- | \(\mathcal{O}(n_L)\).
--   Fold right-to-left over the ranges.
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 #)



-- | \(\mathcal{O}(n_L)\).
--   Fold right-to-left over the ranges of all the keys greater than
--   or equal to the given one.
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



-- | \(\mathcal{O}(n_L)\).
--   Fold right-to-left over the ranges of all the keys smaller than
--   or equal to the given one.
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 #)



-- | \(\mathcal{O}(\min(n,W) + n_{I_L})\).
--   Fold right-to-left over the ranges of all the keys in the given range.
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

-- | \(\mathcal{O}(\min(n,W) + n_{I_L})\).
--   Fold right-to-left over the ranges of all the keys
--   in the \([k_L, k_R)\) interval.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeFoldrRange
  :: Word                       -- ^ \(k_L\)
  -> Word                       -- ^ \(k_R\)
  -> (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



-- | \(\mathcal{O}(n)\).
--   Fold left-to-right over the ranges with a strict accumulator.
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 #)



-- | \(\mathcal{O}(n)\).
--   Fold left-to-right over the ranges of all the keys smaller than
--   or equal to the given one.
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



-- | \(\mathcal{O}(n)\).
--   Fold left-to-right over the ranges of all the keys greater than
--   or equal to the given one.
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 #)



-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Fold left-to-right over the ranges of all the keys in the given range.
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

-- | \(\mathcal{O}(n)\).
--   Fold left-to-right over the ranges of all the keys
--   in the \([k_L, k_R)\) interval.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeFoldlRange'
  :: Word                       -- ^ \(k_L\)
  -> Word                       -- ^ \(k_R\)
  -> (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



-- | \(\mathcal{O}(n)\).
--   Fold right-to-left over the ranges.
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 #)



-- | \(\mathcal{O}(n)\).
--   Fold right-to-left over the ranges of all the keys greater than
--   or equal to the given one.
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



-- | \(\mathcal{O}(n)\).
--   Fold right-to-left over the ranges of all the keys smaller than
--   or equal to the given one.
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 #)



-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Fold right-to-left with a strict accumulator over the ranges of all the keys
--   in the given range.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Fold right-to-left with a strict accumulator over the ranges of all the keys
--   in the \([k_L, k_R)\) interval.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeFoldrRange'
  :: Word                       -- ^ \(k_L\)
  -> Word                       -- ^ \(k_R\)
  -> (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




-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the color of the key.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the key of the given color that is smaller than or equal to the given key.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the key of the given color that is smaller than or equal to the given key,
--   falling back to the default value if no such key exists.
findL
  :: Word -- ^ Default value
  -> Color
  -> Word -- ^ Key
  -> 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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the key of the given color that is greater than or equal to the given key.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the key of the given color that is greater than or equal to the given key,
--   falling back to the default value if no such key exists.
findR
  :: Word  -- ^ Default value
  -> Color
  -> Word  -- ^ Key
  -> 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




-- | \(\mathcal{O}(\min(n,W))\).
--   Set every key smaller than or equal to the given one to the given color.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Set every key smaller than the given one to the given color.
--
--   The given key __must not__ be @0@.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Set every key greater than or equal to the given one to the given color.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Set every key in the range to the given color.
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

-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Set every key in the \([k_L, k_R)\) interval to the given color.
--
--   \(k_L\) __must not__ be @0@. \(k_R\) __must__ be greater than \(k_L\).
unsafeFillRange
  :: Word  -- ^ \(k_L\)
  -> Word  -- ^ \(k_R\)
  -> 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 #)



-- | \(\mathcal{O}(n)\).
--   Invert the colors of all keys.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Union of two trees over the given color.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Intersection of two trees over the given color.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Determine whether two trees are disjoint over the given color.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Difference of two trees over the given color.
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)



-- | \(\mathcal{O}(n_A + n_B)\).
--   Symmetric difference of two trees over the given color.
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 #)

-- | \(\mathcal{O}(n_A + n_B)\).
--    Compare two trees with respect to set inclusion over the given color.
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