-- |
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
-- Functions for joining AVL trees of known height.
module Data.Tree.AVL.Internals.HJoin
        ( spliceH,joinH,joinH',
        ) where

import Data.Tree.AVL.Internals.Types(AVL(..))
import Data.Tree.AVL.Push(pushL,pushR)
import Data.Tree.AVL.Internals.HPush(pushHL_,pushHR_)
import Data.Tree.AVL.Internals.DelUtils(popRN,popRZ,popRP,popLN,popLZ,popLP)

import GHC.Base
#include "ghcdefs.h"

-- | Join two trees of known height, returning an AVL tree.
-- It's OK if heights are relative (I.E. if they share same fixed offset).
--
-- Complexity: O(d), where d is the absolute difference in tree heights.
joinH'
       :: AVL e -> UINT -> AVL e -> UINT -> AVL e
joinH' :: forall e. AVL e -> Int# -> AVL e -> Int# -> AVL e
joinH' AVL e
l Int#
hl AVL e
r Int#
hr
                 = if Int# -> Bool
isTrue# (Int#
hl Int# -> Int# -> Int#
LEQ Int#
hr) then let d :: Int#
d = SUBINT(hr,hl) in joinHL d l r
                                else let d :: Int#
d = SUBINT(hl,hr) in joinHR d l r

-- hr >= hl, join l to left subtree of r.
-- Int argument is absolute difference in tree height, hr-hl (>=0)
{-# INLINE joinHL #-}
joinHL :: UINT -> AVL e -> AVL e -> AVL e
joinHL :: forall e. Int# -> AVL e -> AVL e -> AVL e
joinHL Int#
_  AVL e
E           AVL e
r = AVL e
r                                                  -- l was empty
joinHL Int#
d (N AVL e
ll e
le AVL e
lr) AVL e
r = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
ll e
le AVL e
lr of
                          UBT2(l_,e) -> case AVL e
l_ of
                                        AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"joinHL: Bug0"       -- impossible if BF=-1
                                        Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceL AVL e
l_ e
e INCINT1(d) r  -- hl2=hl-1
                                        AVL e
_       -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceL AVL e
l_ e
e         Int#
d  AVL e
r  -- hl2=hl
joinHL Int#
d (Z AVL e
ll e
le AVL e
lr) AVL e
r = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRZ AVL e
ll e
le AVL e
lr of
                          UBT2(l_,e) -> case AVL e
l_ of
                                        AVL e
E       -> e
e e -> AVL e -> AVL e
forall e. e -> AVL e -> AVL e
`pushL` AVL e
r               -- l had only one element
                                        AVL e
_       -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceL AVL e
l_ e
e Int#
d  AVL e
r         -- hl2=hl
joinHL Int#
d (P AVL e
ll e
le AVL e
lr) AVL e
r = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
ll e
le AVL e
lr of
                          UBT2(l_,e) -> case AVL e
l_ of
                                        AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"joinHL: Bug1"      -- impossible if BF=+1
                                        Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceL AVL e
l_ e
e INCINT1(d) r -- hl2=hl-1
                                        AVL e
_       -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceL AVL e
l_ e
e         Int#
d  AVL e
r -- hl2=hl


-- hl >= hr, join r to right subtree of l.
-- Int argument is absolute difference in tree height, hl-hr (>=0)
{-# INLINE joinHR #-}
joinHR :: UINT -> AVL e -> AVL e -> AVL e
joinHR :: forall e. Int# -> AVL e -> AVL e -> AVL e
joinHR Int#
_ AVL e
l  AVL e
E           = AVL e
l                                    -- r was empty
joinHR Int#
d AVL e
l (N AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
rl e
re AVL e
rr of
                          UBT2(e,r_) -> case AVL e
r_ of
                                        AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"joinHR: Bug0"      -- impossible if BF=-1
                                        Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceR AVL e
r_ e
e INCINT1(d) l -- hr2=hr-1
                                        AVL e
_       -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceR AVL e
r_ e
e         Int#
d  AVL e
l -- hr2=hr
joinHR Int#
d AVL e
l (Z AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLZ AVL e
rl e
re AVL e
rr of
                          UBT2(e,r_) -> case AVL e
r_ of
                                        AVL e
E       -> AVL e
l AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e
`pushR` e
e            -- r had only one element
                                        AVL e
_       -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceR AVL e
r_ e
e Int#
d AVL e
l       -- hr2=hr
joinHR Int#
d AVL e
l (P AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
rl e
re AVL e
rr of
                          UBT2(e,r_) -> case AVL e
r_ of
                                        AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"joinHL: Bug1"      -- impossible if BF=+1
                                        Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceR AVL e
r_ e
e INCINT1(d) l -- hr2=hr-1
                                        AVL e
_       -> AVL e -> e -> Int# -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceR AVL e
r_ e
e         Int#
d  AVL e
l -- hr2=hr

-- | Join two AVL trees of known height, returning an AVL tree of known height.
-- It's OK if heights are relative (I.E. if they share same fixed offset).
--
-- Complexity: O(d), where d is the absolute difference in tree heights.
joinH :: AVL e -> UINT -> AVL e -> UINT -> UBT2(AVL e,UINT)
joinH :: forall e. AVL e -> Int# -> AVL e -> Int# -> (# AVL e, Int# #)
joinH AVL e
l Int#
hl AVL e
r Int#
hr =
 case Int# -> Int# -> Ordering
COMPAREUINT Int#
hl Int#
hr of
 -- hr > hl
 Ordering
LT -> case AVL e
l of
       AVL e
E          -> UBT2(r,hr)
       N AVL e
ll e
le AVL e
lr -> case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
ll e
le AVL e
lr of
                     UBT2(l_,e) -> case AVL e
l_ of
                                   Z AVL e
_ e
_ AVL e
_ -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_ DECINT1(hl) e r hr -- dH=-1
                                   AVL e
_       -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_         Int#
hl  e
e AVL e
r Int#
hr -- dH= 0
       Z AVL e
ll e
le AVL e
lr -> case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRZ AVL e
ll e
le AVL e
lr of
                     UBT2(l_,e) -> case AVL e
l_ of
                                   AVL e
E       -> AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
pushHL_ AVL e
l AVL e
r Int#
hr                  -- l had only 1 element
                                   AVL e
_       -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_         Int#
hl  e
e AVL e
r Int#
hr -- dH=0
       P AVL e
ll e
le AVL e
lr -> case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
ll e
le AVL e
lr of
                     UBT2(l_,e) -> case AVL e
l_ of
                                   Z AVL e
_ e
_ AVL e
_ -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_ DECINT1(hl) e r hr -- dH=-1
                                   AVL e
_       -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_         Int#
hl  e
e AVL e
r Int#
hr -- dH= 0
 -- hr = hl
 Ordering
EQ -> case AVL e
l of
       AVL e
E          -> UBT2(l,hl)              -- r must be empty too, don't use emptyAVL!
       N AVL e
ll e
le AVL e
lr -> case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
ll e
le AVL e
lr of
                     UBT2(l_,e) -> case AVL e
l_ of
                                   Z AVL e
_ e
_ AVL e
_ -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_ DECINT1(hl) e r hr -- dH=-1
                                   AVL e
_       -> UBT2(Z l_ e r, INCINT1(hr))    -- dH= 0
       Z AVL e
ll e
le AVL e
lr -> case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRZ AVL e
ll e
le AVL e
lr of
                     UBT2(l_,e) -> case AVL e
l_ of
                                   AVL e
E       -> AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
pushHL_ AVL e
l AVL e
r Int#
hr                 -- l had only 1 element
                                   AVL e
_       -> UBT2(Z l_ e r, INCINT1(hr))    -- dH= 0
       P AVL e
ll e
le AVL e
lr -> case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
ll e
le AVL e
lr of
                     UBT2(l_,e) -> case AVL e
l_ of
                                   Z AVL e
_ e
_ AVL e
_ -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l_ DECINT1(hl) e r hr -- dH=-1
                                   AVL e
_       -> UBT2(Z l_ e r, INCINT1(hr))    -- dH= 0
 -- hl > hr
 Ordering
GT -> case AVL e
r of
       AVL e
E          -> UBT2(l,hl)
       N AVL e
rl e
re AVL e
rr -> case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
rl e
re AVL e
rr of
                     UBT2(e,r_) -> case AVL e
r_ of
                                   Z AVL e
_ e
_ AVL e
_ -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
e AVL e
r_ DECINT1(hr) -- dH=-1
                                   AVL e
_       -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
e AVL e
r_         Int#
hr  -- dH= 0
       Z AVL e
rl e
re AVL e
rr -> case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLZ AVL e
rl e
re AVL e
rr of
                     UBT2(e,r_) -> case AVL e
r_ of
                                   AVL e
E       -> AVL e -> Int# -> AVL e -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> AVL e -> (# AVL e, Int# #)
pushHR_ AVL e
l Int#
hl AVL e
r                 -- r had only 1 element
                                   AVL e
_       -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
e AVL e
r_ Int#
hr          -- dH=0
       P AVL e
rl e
re AVL e
rr -> case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
rl e
re AVL e
rr of
                     UBT2(e,r_) -> case AVL e
r_ of
                                   Z AVL e
_ e
_ AVL e
_ -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
e AVL e
r_ DECINT1(hr) -- dH=-1
                                   AVL e
_       -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
e AVL e
r_         Int#
hr  -- dH= 0


-- | Splice two AVL trees of known height using the supplied bridging element.
-- That is, the bridging element appears \"in the middle\" of the resulting AVL tree.
-- The elements of the first tree argument are to the left of the bridging element and
-- the elements of the second tree are to the right of the bridging element.
--
-- This function does not require that the AVL heights are absolutely correct, only that
-- the difference in supplied heights is equal to the difference in actual heights. So it's
-- OK if the input heights both have the same unknown constant offset. (The output height
-- will also have the same constant offset in this case.)
--
-- Complexity: O(d), where d is the absolute difference in tree heights.
spliceH :: AVL e -> UINT -> e -> AVL e -> UINT -> UBT2(AVL e,UINT)
-- You'd think inlining this function would make a significant difference to many functions
-- (such as set operations), but it doesn't. It makes them marginally slower!!
spliceH :: forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceH AVL e
l Int#
hl e
b AVL e
r Int#
hr =
 case Int# -> Int# -> Ordering
COMPAREUINT Int#
hl Int#
hr of
 Ordering
LT -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l Int#
hl e
b AVL e
r Int#
hr
 Ordering
EQ -> UBT2(Z l b r, INCINT1(hl))
 Ordering
GT -> AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
b AVL e
r Int#
hr

-- Splice two trees of known relative height where hr>hl, using the supplied bridging element,
-- returning another tree of known relative height.
spliceHL :: AVL e -> UINT -> e -> AVL e -> UINT -> UBT2(AVL e,UINT)
spliceHL :: forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHL AVL e
l Int#
hl e
b AVL e
r Int#
hr = let d :: Int#
d = SUBINT(hr,hl)
                       in if Int# -> Bool
isTrue# (Int#
d Int# -> Int# -> Int#
EQL L(1)) then UBT2(N l b r, INCINT1(hr))
                                        else Int# -> Int# -> AVL e -> e -> AVL e -> (# AVL e, Int# #)
forall e. Int# -> Int# -> AVL e -> e -> AVL e -> (# AVL e, Int# #)
spliceHL_ Int#
hr Int#
d AVL e
l e
b AVL e
r

-- Splice two trees of known relative height where hl>hr, using the supplied bridging element,
-- returning another tree of known relative height.
spliceHR :: AVL e -> UINT -> e -> AVL e -> UINT -> UBT2(AVL e,UINT)
spliceHR :: forall e. AVL e -> Int# -> e -> AVL e -> Int# -> (# AVL e, Int# #)
spliceHR AVL e
l Int#
hl e
b AVL e
r Int#
hr = let d :: Int#
d = SUBINT(hl,hr)
                       in if Int# -> Bool
isTrue# (Int#
d Int# -> Int# -> Int#
EQL L(1)) then UBT2(P l b r, INCINT1(hl))
                                        else Int# -> Int# -> AVL e -> e -> AVL e -> (# AVL e, Int# #)
forall e. Int# -> Int# -> AVL e -> e -> AVL e -> (# AVL e, Int# #)
spliceHR_ Int#
hl Int#
d AVL e
l e
b AVL e
r

-- Splice two trees of known relative height where hr>hl+1, using the supplied bridging element,
-- returning another tree of known relative height. d >= 2
{-# INLINE spliceHL_ #-}
spliceHL_ :: UINT -> UINT -> AVL e -> e -> AVL e -> UBT2(AVL e,UINT)
spliceHL_ :: forall e. Int# -> Int# -> AVL e -> e -> AVL e -> (# AVL e, Int# #)
spliceHL_ Int#
_  Int#
_ AVL e
_ e
_  AVL e
E           = [Char] -> (# AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceHL_: Bug0"          -- impossible if hr>hl
spliceHL_ Int#
hr Int#
d AVL e
l e
b (N AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
l e
b DECINT2(d) rl re rr
                                  in  AVL e
r_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(r_,hr)
spliceHL_ Int#
hr Int#
d AVL e
l e
b (Z AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLZ AVL e
l e
b DECINT1(d) rl re rr
                                  in case AVL e
r_ of
                                     AVL e
E       -> [Char] -> (# AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceHL_: Bug1"
                                     Z AVL e
_ e
_ AVL e
_ -> UBT2(r_,        hr )
                                     AVL e
_       -> UBT2(r_,INCINT1(hr))
spliceHL_ Int#
hr Int#
d AVL e
l e
b (P AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
l e
b DECINT1(d) rl re rr
                                  in  AVL e
r_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(r_,hr)

-- Splice two trees of known relative height where hl>hr+1, using the supplied bridging element,
-- returning another tree of known relative height. d >= 2 !!
{-# INLINE spliceHR_ #-}
spliceHR_ :: UINT -> UINT -> AVL e -> e -> AVL e -> UBT2(AVL e,UINT)
spliceHR_ :: forall e. Int# -> Int# -> AVL e -> e -> AVL e -> (# AVL e, Int# #)
spliceHR_ Int#
_  Int#
_  AVL e
E           e
_ AVL e
_ = [Char] -> (# AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceHR_: Bug0"          -- impossible if hl>hr
spliceHR_ Int#
hl Int#
d (N AVL e
ll e
le AVL e
lr) e
b AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
r e
b DECINT1(d) ll le lr
                                  in  AVL e
l_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(l_,hl)
spliceHR_ Int#
hl Int#
d (Z AVL e
ll e
le AVL e
lr) e
b AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRZ AVL e
r e
b DECINT1(d) ll le lr
                                  in case AVL e
l_ of
                                     AVL e
E       -> [Char] -> (# AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceHR_: Bug1"
                                     Z AVL e
_ e
_ AVL e
_ -> UBT2(l_,        hl )
                                     AVL e
_       -> UBT2(l_,INCINT1(hl))
spliceHR_ Int#
hl Int#
d (P AVL e
ll e
le AVL e
lr) e
b AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
r e
b DECINT2(d) ll le lr
                                  in  AVL e
l_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(l_,hl)

-- hr >= hl, splice s to left subtree of r, using b as the bridge
-- The Int argument is the absolute difference in tree height, hr-hl (>=0)
spliceL :: AVL e -> e -> UINT -> AVL e -> AVL e
spliceL :: forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceL AVL e
s e
b L(0AVL e
) r           = Z s b r
spliceL AVL e
s e
b L(1AVL e
) r           = N s b r
spliceL AVL e
s e
b Int#
d   (N AVL e
rl e
re AVL e
rr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
s e
b DECINT2(d) rl re rr   -- height diff of rl is two less
spliceL AVL e
s e
b Int#
d   (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLZ AVL e
s e
b DECINT1(d) rl re rr   -- height diff of rl is one less
spliceL AVL e
s e
b Int#
d   (P AVL e
rl e
re AVL e
rr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
s e
b DECINT1(d) rl re rr   -- height diff of rl is one less
spliceL AVL e
_ e
_ Int#
_    AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceL: Bug0"              -- r can't be empty

-- Splice into left subtree of (N l e r), height cannot change as a result of this
spliceLN :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> AVL e
spliceLN :: forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
s e
b L(0AVL e
) l           AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
Z e
s AVL e
b le
) AVL e
e r                                             -- dH=0
spliceLN AVL e
s e
b L(1AVL e
) l           AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
N e
s AVL e
b le
) AVL e
e r                                             -- dH=0
spliceLN AVL e
s e
b Int#
d   (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
s e
b DECINT2(d) ll le lr in l_ `seq` N l_ e r
spliceLN AVL e
s e
b Int#
d   (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLZ AVL e
s e
b DECINT1(d) ll le lr
                                    in case AVL e
l_ of
                                       Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l_ e
e AVL e
r                                      -- dH=0
                                       P AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l_ e
e AVL e
r                                      -- dH=0
                                       AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLN: Bug0"                        -- impossible
spliceLN AVL e
s e
b Int#
d   (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
s e
b DECINT1(d) ll le lr in l_ `seq` N l_ e r
spliceLN AVL e
_ e
_ Int#
_    AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLN: Bug1"                                      -- impossible

-- Splice into left subtree of (Z l e r), Z->P if dH=1, Z->Z if dH=0
spliceLZ :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> AVL e
spliceLZ :: forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLZ AVL e
s e
b L(1AVL e
) l           AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= P (AVL e
N e
s AVL e
b le
) AVL e
e r                                                -- Z->P, dH=1
spliceLZ AVL e
s e
b Int#
d   (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
s e
b DECINT2(d) ll le lr in l_ `seq` Z l_ e r -- Z->Z, dH=0
spliceLZ AVL e
s e
b Int#
d   (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLZ AVL e
s e
b DECINT1(d) ll le lr
                                    in case AVL e
l_ of
                                       Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l_ e
e AVL e
r                                      -- Z->Z, dH=0
                                       P AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l_ e
e AVL e
r                                      -- Z->P, dH=1
                                       AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLZ: Bug0"                        -- impossible
spliceLZ AVL e
s e
b Int#
d   (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
s e
b DECINT1(d) ll le lr in l_ `seq` Z l_ e r -- Z->Z, dH=0
spliceLZ AVL e
_ e
_ Int#
_    AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLZ: Bug1"                                      -- impossible

-- Splice into left subtree of (P l e r), height cannot change as a result of this
spliceLP :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> AVL e
spliceLP :: forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
s e
b L(1) (N ll le lre
) AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
P e
s b ll) le (Z lr e r)                                     -- dH=0
spliceLP AVL e
s e
b L(1) (Z ll le lre
) AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
Z e
s b ll) le (Z lr e r)                                     -- dH=0
spliceLP AVL e
s e
b L(1) (P ll le lre
) AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
Z e
s b ll) le (N lr e r)                                     -- dH=0
spliceLP AVL e
s e
b Int#
d    (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
s e
b DECINT2(d) ll le lr in l_ `seq` P l_ e r -- dH=0
spliceLP AVL e
s e
b Int#
d    (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e.
AVL e -> e -> Int# -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
spliceLPZ AVL e
s e
b DECINT1(d) ll le lr e r                          -- dH=0
spliceLP AVL e
s e
b Int#
d    (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l_ :: AVL e
l_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
s e
b DECINT1(d) ll le lr in l_ `seq` P l_ e r -- dH=0
spliceLP AVL e
_ e
_ Int#
_     AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLP: Bug0"

-- Splice into left subtree of (P (Z ll le lr) e r)
{-# INLINE spliceLPZ #-}
spliceLPZ :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
spliceLPZ :: forall e.
AVL e -> e -> Int# -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
spliceLPZ AVL e
s e
b L(1) ll             le lr AVL e
e r AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
N e
s b ll) le (Z lr e r)                        -- dH=0
spliceLPZ AVL e
s e
b Int#
d   (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let ll_ :: AVL e
ll_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLN AVL e
s e
b DECINT2(d) lll lle llr     -- dH=0
                                              in  AVL e
ll_ AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
ll_ e
le AVL e
lr) e
e AVL e
r
spliceLPZ AVL e
s e
b Int#
d   (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let ll_ :: AVL e
ll_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLZ AVL e
s e
b DECINT1(d) lll lle llr     -- dH=0
                                              in case AVL e
ll_ of
                                                 Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
ll_ e
le AVL e
lr) e
e AVL e
r                 -- dH=0
                                                 P AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
ll_ e
le (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
lr e
e AVL e
r)                 -- dH=0
                                                 AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLPZ: Bug0"             -- impossible
spliceLPZ AVL e
s e
b Int#
d   (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let ll_ :: AVL e
ll_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceLP AVL e
s e
b DECINT1(d) lll lle llr     -- dH=0
                                              in  AVL e
ll_ AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
ll_ e
le AVL e
lr) e
e AVL e
r
spliceLPZ AVL e
_ e
_ Int#
_    AVL e
E              e
_  AVL e
_  e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceLPZ: Bug1"

-- hl >= hr, splice s to right subtree of l, using b as the bridge
-- The Int argument is the absolute difference in tree height, hl-hr (>=0)
spliceR :: AVL e -> e -> UINT -> AVL e -> AVL e
spliceR :: forall e. AVL e -> e -> Int# -> AVL e -> AVL e
spliceR AVL e
s e
b L(0AVL e
) l           = Z l b s
spliceR AVL e
s e
b L(1AVL e
) l           = P l b s
spliceR AVL e
s e
b Int#
d   (N AVL e
ll e
le AVL e
lr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
s e
b DECINT1(d) ll le lr   -- height diff of lr is one less
spliceR AVL e
s e
b Int#
d   (Z AVL e
ll e
le AVL e
lr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRZ AVL e
s e
b DECINT1(d) ll le lr   -- height diff of lr is one less
spliceR AVL e
s e
b Int#
d   (P AVL e
ll e
le AVL e
lr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
s e
b DECINT2(d) ll le lr   -- height diff of lr is two less
spliceR AVL e
_ e
_ Int#
_    AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceR: Bug0"              -- l can't be empty

-- Splice into right subtree of (P l e r), height cannot change as a result of this
spliceRP :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> AVL e
spliceRP :: forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
s e
b L(0AVL e
) e
l e  r           = Z l e (Z r b s)                                             -- dH=0
spliceRP AVL e
s e
b L(1AVL e
) e
l e  r           = Z l e (P r b s)                                             -- dH=0
spliceRP AVL e
s e
b Int#
d    AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
s e
b DECINT1(d) rl re rr in r_ `seq` P l e r_
spliceRP AVL e
s e
b Int#
d    AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRZ AVL e
s e
b DECINT1(d) rl re rr
                                     in case AVL e
r_ of
                                        Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l e
e AVL e
r_                                      -- dH=0
                                        N AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e AVL e
r_                                      -- dH=0
                                        AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRP: Bug0"                        -- impossible
spliceRP AVL e
s e
b Int#
d    AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
s e
b DECINT2(d) rl re rr in r_ `seq` P l e r_
spliceRP AVL e
_ e
_ Int#
_    AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRP: Bug1"                                      -- impossible

-- Splice into right subtree of (Z l e r), Z->N if dH=1, Z->Z if dH=0
spliceRZ :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> AVL e
spliceRZ :: forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRZ AVL e
s e
b L(1AVL e
) e
l e  r           = N l e (P r b s)                                                -- Z->N, dH=1
spliceRZ AVL e
s e
b Int#
d    AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
s e
b DECINT1(d) rl re rr in r_ `seq` Z l e r_ -- Z->Z, dH=0
spliceRZ AVL e
s e
b Int#
d    AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRZ AVL e
s e
b DECINT1(d) rl re rr
                                     in case AVL e
r_ of
                                        Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e AVL e
r_                                         -- Z->Z, dH=0
                                        N AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l e
e AVL e
r_                                         -- Z->N, dH=1
                                        AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRZ: Bug0"                           -- impossible
spliceRZ AVL e
s e
b Int#
d    AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
s e
b DECINT2(d) rl re rr in r_ `seq` Z l e r_ -- Z->Z, dH=0
spliceRZ AVL e
_ e
_ Int#
_    AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRZ: Bug1"                                         -- impossible

-- Splice into right subtree of (N l e r), height cannot change as a result of this
spliceRN :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> AVL e
spliceRN :: forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
s e
b L(1AVL e
) e
l e (N rl re rr) AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
P e
l e rl) re (Z rr b s)                                     -- dH=0
spliceRN AVL e
s e
b L(1AVL e
) e
l e (Z rl re rr) AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
Z e
l e rl) re (Z rr b s)                                     -- dH=0
spliceRN AVL e
s e
b L(1AVL e
) e
l e (P rl re rr) AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
= Z (AVL e
Z e
l e rl) re (N rr b s)                                     -- dH=0
spliceRN AVL e
s e
b Int#
d    AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
s e
b DECINT1(d) rl re rr in r_ `seq` N l e r_ -- dH=0
spliceRN AVL e
s e
b Int#
d    AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e.
AVL e -> e -> Int# -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
spliceRNZ AVL e
s e
b DECINT1(d) l e rl re rr                          -- dH=0
spliceRN AVL e
s e
b Int#
d    AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = let r_ :: AVL e
r_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
s e
b DECINT2(d) rl re rr in r_ `seq` N l e r_ -- dH=0
spliceRN AVL e
_ e
_ Int#
_    AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRN: Bug0"

-- Splice into right subtree of (N l e (Z rl re rr))
{-# INLINE spliceRNZ #-}
spliceRNZ :: AVL e -> e -> UINT -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
spliceRNZ :: forall e.
AVL e -> e -> Int# -> AVL e -> e -> AVL e -> e -> AVL e -> AVL e
spliceRNZ AVL e
s e
b L(1AVL e
) e
l e rl re rr              = Z (Z l e rl) re (P rr b s)                        -- dH=0
spliceRNZ AVL e
s e
b Int#
d    AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = let rr_ :: AVL e
rr_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRN AVL e
s e
b DECINT1(d) rrl rre rrr
                                               in  AVL e
rr_ AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
rl e
re AVL e
rr_)                 -- dH=0
spliceRNZ AVL e
s e
b Int#
d    AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = let rr_ :: AVL e
rr_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRZ AVL e
s e
b DECINT1(d) rrl rre rrr     -- dH=0
                                               in case AVL e
rr_ of
                                                  Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
rl e
re AVL e
rr_)                 -- dH=0
                                                  N AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e AVL e
rl) e
re AVL e
rr_                 -- dH=0
                                                  AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRNZ: Bug0"             -- impossible
spliceRNZ AVL e
s e
b Int#
d    AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = let rr_ :: AVL e
rr_ = AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> Int# -> AVL e -> e -> AVL e -> AVL e
spliceRP AVL e
s e
b DECINT2(d) rrl rre rrr     -- dH=0
                                               in AVL e
rr_ AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
rl e
re AVL e
rr_)
spliceRNZ AVL e
_ e
_ Int#
_    AVL e
_ e
_ AVL e
_  e
_   AVL e
E              = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"spliceRNZ: Bug1"