-- |
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
-- Functions for pushing elements into trees of known height.
module Data.Tree.AVL.Internals.HPush
        (pushHL,pushHR,pushHL_,pushHR_,
        ) where

import Data.Tree.AVL.Internals.Types(AVL(..))

import GHC.Base
#include "ghcdefs.h"

-- | A version of 'Data.Tree.AVL.pushL' for an AVL tree of known height.
-- Returns an AVL tree of known height.
-- It's OK if height is relative, with fixed offset. In this case the height of the result
-- will have the same fixed offset.
{-# INLINE pushHL #-}
pushHL :: e -> AVL e -> UINT -> UBT2(AVL e,UINT)
pushHL :: forall e. e -> AVL e -> Int# -> (# AVL e, Int# #)
pushHL e
e AVL e
t Int#
h = AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
forall e. AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
pushHL_ (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
forall e. AVL e
E e
e AVL e
forall e. AVL e
E) AVL e
t Int#
h

-- | A version of 'Data.Tree.AVL.pushR' for an AVL tree of known height.
-- Returns an AVL tree of known height.
-- It's OK if height is relative, with fixed offset. In this case the height of the result
-- will have the same fixed offset.
{-# INLINE pushHR #-}
pushHR :: AVL e -> UINT -> e -> UBT2(AVL e,UINT)
pushHR :: forall e. AVL e -> Int# -> e -> (# AVL e, Int# #)
pushHR AVL e
t Int#
h e
e = AVL e -> Int# -> AVL e -> (# AVL e, Int# #)
forall e. AVL e -> Int# -> AVL e -> (# AVL e, Int# #)
pushHR_ AVL e
t Int#
h (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
forall e. AVL e
E e
e AVL e
forall e. AVL e
E)

-- | Push a singleton tree (first arg) in the leftmost position of an AVL tree of known height,
-- returning an AVL tree of known height. It's OK if height is relative, with fixed offset.
-- In this case the height of the result will have the same fixed offset.
--
-- Complexity: O(log n)
pushHL_ :: AVL e -> AVL e -> UINT -> UBT2(AVL e,UINT)
pushHL_ :: forall e. AVL e -> AVL e -> Int# -> (# AVL e, Int# #)
pushHL_ AVL e
t0 AVL e
t Int#
h = case AVL e
t of
                 AVL e
E       -> UBT2(t0, INCINT1(h)) -- Relative Heights
                 N AVL e
l e
e AVL e
r -> let t_ :: AVL e
t_ = AVL e -> e -> AVL e -> AVL e
putNL AVL e
l e
e AVL e
r in AVL e
t_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(t_,h)
                 P AVL e
l e
e AVL e
r -> let t_ :: AVL e
t_ = AVL e -> e -> AVL e -> AVL e
putPL AVL e
l e
e AVL e
r in AVL e
t_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(t_,h)
                 Z AVL e
l e
e AVL e
r -> let t_ :: AVL e
t_ = AVL e -> e -> AVL e -> AVL e
putZL AVL e
l e
e AVL e
r
                            in case AVL e
t_ of
                               Z AVL e
_ e
_ AVL e
_ -> UBT2(t_,         h )
                               P AVL e
_ e
_ AVL e
_ -> UBT2(t_, INCINT1(h))
                               AVL e
_       -> [Char] -> (# AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHL_: Bug0" -- impossible
 where
 ----------------------------- LEVEL 2 ---------------------------------
 --                      putNL, putZL, putPL                          --
 -----------------------------------------------------------------------

 -- (putNL l e r): Put in L subtree of (N l e r), BF=-1 (Never requires rebalancing) , (never returns P)
 putNL :: AVL e -> e -> AVL e -> AVL e
putNL  AVL e
E           e
e AVL e
r = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
t0 e
e AVL e
r                    -- L subtree empty, H:0->1, parent BF:-1-> 0
 putNL (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putNL AVL e
ll e
le AVL e
lr     -- L subtree BF<>0, H:h->h, parent BF:-1->-1
                          in AVL e
l' 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
r
 putNL (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putPL AVL e
ll e
le AVL e
lr     -- L subtree BF<>0, H:h->h, parent BF:-1->-1
                          in AVL e
l' 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
r
 putNL (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putZL AVL e
ll e
le AVL e
lr     -- L subtree BF= 0, so need to look for changes
                          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         -- L subtree BF:0-> 0, H:h->h  , parent BF:-1->-1
                          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         -- L subtree BF:0->+1, H:h->h+1, parent BF:-1-> 0
                          AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHL_: Bug1" -- impossible

 -- (putZL l e r): Put in L subtree of (Z l e r), BF= 0  (Never requires rebalancing) , (never returns N)
 putZL :: AVL e -> e -> AVL e -> AVL e
putZL  AVL e
E           e
e AVL e
r = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
t0 e
e AVL e
r                    -- L subtree        H:0->1, parent BF: 0->+1
 putZL (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putNL AVL e
ll e
le AVL e
lr     -- L subtree BF<>0, H:h->h, parent BF: 0-> 0
                          in AVL e
l' 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
Z AVL e
l' e
e AVL e
r
 putZL (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putPL AVL e
ll e
le AVL e
lr     -- L subtree BF<>0, H:h->h, parent BF: 0-> 0
                          in AVL e
l' 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
Z AVL e
l' e
e AVL e
r
 putZL (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putZL AVL e
ll e
le AVL e
lr     -- L subtree BF= 0, so need to look for changes
                          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         -- L subtree BF: 0-> 0, H:h->h  , parent BF: 0-> 0
                          N AVL e
_ e
_ AVL e
_ -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHL_: Bug2" -- impossible
                          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         -- L subtree BF: 0->+1, H:h->h+1, parent BF: 0->+1

      -------- This case (PL) may need rebalancing if it goes to LEVEL 3 ---------

 -- (putPL l e r): Put in L subtree of (P l e r), BF=+1 , (never returns N)
 putPL :: AVL e -> e -> AVL e -> AVL e
putPL  AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHL_: Bug3"       -- impossible if BF=+1
 putPL (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putNL AVL e
ll e
le AVL e
lr     -- L subtree BF<>0, H:h->h, parent BF:+1->+1
                          in AVL e
l' 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
l' e
e AVL e
r
 putPL (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> AVL e
putPL AVL e
ll e
le AVL e
lr     -- L subtree BF<>0, H:h->h, parent BF:+1->+1
                          in AVL e
l' 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
l' e
e AVL e
r
 putPL (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
putPLL AVL e
ll e
le AVL e
lr e
e AVL e
r         -- LL (never returns N)

 ----------------------------- LEVEL 3 ---------------------------------
 --                            putPLL                                 --
 -----------------------------------------------------------------------

 -- (putPLL ll le lr e r): Put in LL subtree of (P (Z ll le lr) e r) , (never returns N)
 {-# INLINE putPLL #-}
 putPLL :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
putPLL  AVL e
E e
le AVL e
lr e
e AVL e
r              = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
t0 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)                  -- r and lr must also be E, special CASE LL!!
 putPLL (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 -> AVL e -> AVL e
putNL AVL e
lll e
lle AVL e
llr         -- LL subtree BF<>0, H:h->h, so no change
                                    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
 putPLL (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 -> AVL e -> AVL e
putPL AVL e
lll e
lle AVL e
llr         -- LL subtree BF<>0, H:h->h, so no change
                                    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
 putPLL (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 -> AVL e -> AVL e
putZL AVL e
lll e
lle AVL e
llr         -- LL subtree BF= 0, so need to look for changes
                                    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 -- LL subtree BF: 0-> 0, H:h->h, so no change
                                    N AVL e
_ e
_ AVL e
_ -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHL_: Bug4" -- impossible
                                    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) -- LL subtree BF: 0->+1, H:h->h+1, parent BF:-1->-2, CASE LL !!

-- | Push a singleton tree (third arg) in the rightmost position of an AVL tree of known height,
-- returning an AVL tree of known height. It's OK if height is relative, with fixed offset.
-- In this case the height of the result will have the same fixed offset.
--
-- Complexity: O(log n)
pushHR_ :: AVL e -> UINT -> AVL e -> UBT2(AVL e,UINT)
pushHR_ :: forall e. AVL e -> Int# -> AVL e -> (# AVL e, Int# #)
pushHR_ AVL e
t Int#
h AVL e
t0 = case AVL e
t of
                 AVL e
E         -> UBT2(t0, INCINT1(h)) -- Relative Heights
                 N AVL e
l e
e AVL e
r -> let t_ :: AVL e
t_ = AVL e -> e -> AVL e -> AVL e
putNR AVL e
l e
e AVL e
r in AVL e
t_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(t_,h)
                 P AVL e
l e
e AVL e
r -> let t_ :: AVL e
t_ = AVL e -> e -> AVL e -> AVL e
putPR AVL e
l e
e AVL e
r in AVL e
t_ AVL e -> (# AVL e, Int# #) -> (# AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT2(t_,h)
                 Z AVL e
l e
e AVL e
r -> let t_ :: AVL e
t_ = AVL e -> e -> AVL e -> AVL e
putZR AVL e
l e
e AVL e
r
                              in case AVL e
t_ of
                                 Z AVL e
_ e
_ AVL e
_ -> UBT2(t_,         h )
                                 N AVL e
_ e
_ AVL e
_ -> UBT2(t_, INCINT1(h))
                                 AVL e
_       -> [Char] -> (# AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHR_: Bug0" -- impossible
 where
 ----------------------------- LEVEL 2 ---------------------------------
 --                      putNR, putZR, putPR                          --
 -----------------------------------------------------------------------

 -- (putZR l e r): Put in R subtree of (Z l e r), BF= 0 (Never requires rebalancing) , (never returns P)
 putZR :: AVL e -> e -> AVL e -> AVL e
putZR AVL e
l e
e AVL e
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
t0                    -- R subtree        H:0->1, parent BF: 0->-1
 putZR AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putNR AVL e
rl e
re AVL e
rr     -- R subtree BF<>0, H:h->h, parent BF: 0-> 0
                          in AVL e
r' 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
Z AVL e
l e
e AVL e
r'
 putZR AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putPR AVL e
rl e
re AVL e
rr     -- R subtree BF<>0, H:h->h, parent BF: 0-> 0
                          in AVL e
r' 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
Z AVL e
l e
e AVL e
r'
 putZR AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putZR AVL e
rl e
re AVL e
rr     -- R subtree BF= 0, so need to look for changes
                          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'         -- R subtree BF: 0-> 0, H:h->h  , parent BF: 0-> 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'         -- R subtree BF: 0->-1, H:h->h+1, parent BF: 0->-1
                          AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHR_: Bug1" -- impossible

 -- (putPR l e r): Put in R subtree of (P l e r), BF=+1 (Never requires rebalancing) , (never returns N)
 putPR :: AVL e -> e -> AVL e -> AVL e
putPR AVL e
l e
e  AVL e
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
t0                    -- R subtree empty, H:0->1,     parent BF:+1-> 0
 putPR AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putNR AVL e
rl e
re AVL e
rr     -- R subtree BF<>0, H:h->h,     parent BF:+1->+1
                          in AVL e
r' 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
l e
e AVL e
r'
 putPR AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putPR AVL e
rl e
re AVL e
rr     -- R subtree BF<>0, H:h->h,     parent BF:+1->+1
                          in AVL e
r' 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
l e
e AVL e
r'
 putPR AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putZR AVL e
rl e
re AVL e
rr     -- R subtree BF= 0, so need to look for changes
                          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'         -- R subtree BF:0-> 0, H:h->h  , parent BF:+1->+1
                          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'         -- R subtree BF:0->-1, H:h->h+1, parent BF:+1-> 0
                          AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHR_: Bug2" -- impossible

      -------- This case (NR) may need rebalancing if it goes to LEVEL 3 ---------

 -- (putNR l e r): Put in R subtree of (N l e r), BF=-1 , (never returns P)
 putNR :: AVL e -> e -> AVL e -> AVL e
putNR AVL e
_ e
_ AVL e
E            = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHR_: Bug3"       -- impossible if BF=-1
 putNR AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putNR AVL e
rl e
re AVL e
rr     -- R subtree BF<>0, H:h->h, parent BF:-1->-1
                          in AVL e
r' 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
r'
 putNR AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> AVL e
putPR AVL e
rl e
re AVL e
rr     -- R subtree BF<>0, H:h->h, parent BF:-1->-1
                          in AVL e
r' 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
r'
 putNR AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
putNRR AVL e
l e
e AVL e
rl e
re AVL e
rr         -- RR (never returns P)

 ----------------------------- LEVEL 3 ---------------------------------
 --                            putNRR                                 --
 -----------------------------------------------------------------------

 -- (putNRR l e rl re rr): Put in RR subtree of (N l e (Z rl re rr)) , (never returns P)
 {-# INLINE putNRR #-}
 putNRR :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
putNRR AVL e
l e
e AVL e
rl e
re  AVL e
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
t0                  -- l and rl must also be E, special CASE RR!!
 putNRR 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 -> AVL e -> AVL e
putNR AVL e
rrl e
rre AVL e
rrr         -- RR subtree BF<>0, H:h->h, so no change
                                    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')
 putNRR 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 -> AVL e -> AVL e
putPR AVL e
rrl e
rre AVL e
rrr         -- RR subtree BF<>0, H:h->h, so no change
                                    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')
 putNRR 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 -> AVL e -> AVL e
putZR AVL e
rrl e
rre AVL e
rrr         -- RR subtree BF= 0, so need to look for changes
                                    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')      -- RR subtree BF: 0-> 0, H:h->h, so no change
                                    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'      -- RR subtree BF: 0->-1, H:h->h+1, parent BF:-1->-2, CASE RR !!
                                    AVL e
_       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"pushHR_: Bug4"    -- impossible