-- |
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
-- This module defines utility functions for deleting elements from AVL trees.
module Data.Tree.AVL.Internals.DelUtils
        (-- * Deleting utilities.
         delRN,delRZ,delRP,delLN,delLZ,delLP,

         -- * Popping utilities.
         popRN,popRZ,popRP,popLN,popLZ,popLP,
         popHL,popHLN,popHLZ,popHLP,

         -- * Balancing utilities.
         chkLN,chkLZ,chkLP,chkRN,chkRZ,chkRP,
         chkLN',chkLZ',chkLP',chkRN',chkRZ',chkRP',

         -- * Node substitution utilities.
         subN,subZR,subZL,subP,

         -- * BinPath related.
         deletePath,
        ) where

import Data.Tree.AVL.Internals.Types(AVL(..))
import Data.Tree.AVL.BinPath(sel,goL,goR)

import GHC.Base
#include "ghcdefs.h"

{------------------------------------------------------------------------------------------------------------------------------
 -------------------------------------- Notes about Deletion and Rebalancing -------------------------------------------------
 ------------------------------------------------------------------------------------------------------------------------------
If you go through a similar analysis to that indicated in the Push.hs module (which I haven't illustrated
here with ASCII art) it can be seen that (as with insertion) the height change in a tree which occurs
as a result of deletion of a node can be infered from the change in BF, (whether or not a re-balancing
rotation was required). The rules are:
      BF +/-1 ->    0, height decreased by 1
      BF    0 -> +/-1, height unchanged.
      BF unchanged   , height unchanged.
      BF +/-1 -> -/+1, height unchanged.

Unlike insertion, rebalancing on deletion requires pattern matching on nodes which aren't on the
current path, hence the existance of separate rebalancing functions (rebalN and rebalP).
-}

-------------------------- delL LEVEL 1 -------------------------------
--                      delLN, delLZ, delLP                          --
-----------------------------------------------------------------------
-- | Delete leftmost from (N l e r)
delLN :: AVL e -> e -> AVL e -> AVL e
delLN :: forall e. AVL e -> e -> AVL e -> AVL e
delLN  AVL e
E           e
_ AVL e
r = AVL e
r                          -- Terminal case, r must be of form (Z E re E)
delLN (N AVL e
ll 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
chkLN (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delLN AVL e
ll e
le AVL e
lr) e
e AVL e
r
delLN (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLNZ AVL e
ll e
le AVL e
lr e
e AVL e
r
delLN (P AVL e
ll 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
chkLN (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delLP AVL e
ll e
le AVL e
lr) e
e AVL e
r

-- | Delete leftmost from (Z l e r)
delLZ :: AVL e -> e -> AVL e -> AVL e
delLZ :: forall e. AVL e -> e -> AVL e -> AVL e
delLZ  AVL e
E           e
_ AVL e
_ = AVL e
forall e. AVL e
E                          -- Terminal case, r must be E
delLZ (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN AVL e
ll e
le AVL e
lr e
e AVL e
r
delLZ (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ AVL e
ll e
le AVL e
lr e
e AVL e
r
delLZ (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP AVL e
ll e
le AVL e
lr e
e AVL e
r

-- | Delete leftmost from (P l e r)
delLP :: AVL e -> e -> AVL e -> AVL e
delLP :: forall e. AVL e -> e -> AVL e -> AVL e
delLP  AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"delLP: Bug0"       -- Impossible if BF=+1
delLP (N AVL e
ll 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
chkLP (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delLN AVL e
ll e
le AVL e
lr) e
e AVL e
r
delLP (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLPZ AVL e
ll e
le AVL e
lr e
e AVL e
r
delLP (P AVL e
ll 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
chkLP (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delLP AVL e
ll e
le AVL e
lr) e
e AVL e
r

-------------------------- delL LEVEL 2 -------------------------------
--                     delLNZ, delLZZ, delLPZ                        --
--                        delLZN, delLZP                             --
-----------------------------------------------------------------------

-- Delete leftmost from (N (Z ll le lr) e r), height of left sub-tree can't change in this case
{-# INLINE delLNZ #-}
delLNZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLNZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLNZ  AVL e
E              e
_  AVL e
_  e
e AVL e
r = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalN AVL e
forall e. AVL e
E e
e AVL e
r                     -- Terminal case, Needs rebalancing
delLNZ (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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
delLNZ (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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
delLNZ (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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

-- Delete leftmost from (Z (Z ll le lr) e r), height of left sub-tree can't change in this case
-- Don't inline
delLZZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ  AVL e
E              e
_  AVL e
_  e
e AVL e
r = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
forall e. AVL e
E e
e AVL e
r                           -- Terminal case
delLZZ (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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
delLZZ (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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
delLZZ (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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

-- Delete leftmost from (P (Z ll le lr) e r), height of left sub-tree can't change in this case
{-# INLINE delLPZ #-}
delLPZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLPZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLPZ  AVL e
E              e
_  AVL e
_  e
e AVL e
_ = 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                           -- Terminal case
delLPZ (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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
delLPZ (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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
delLPZ (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = let l' :: AVL e
l' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP AVL e
lll e
lle AVL e
llr e
le AVL e
lr 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

-- Delete leftmost from (Z (N ll le lr) e r)
{-# INLINE delLZN #-}
delLZN :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN AVL e
ll 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
chkLZ (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delLN AVL e
ll e
le AVL e
lr) e
e AVL e
r

-- Delete leftmost from (Z (P ll le lr) e r)
{-# INLINE delLZP #-}
delLZP :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP AVL e
ll 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
chkLZ (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delLP AVL e
ll e
le AVL e
lr) e
e AVL e
r

-------------------------- delR LEVEL 1 -------------------------------
--                      delRN, delRZ, delRP                          --
-----------------------------------------------------------------------
-- | Delete rightmost from (N l e r)
delRN :: AVL e -> e -> AVL e -> AVL e
delRN :: forall e. AVL e -> e -> AVL e -> AVL e
delRN AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"delRN: Bug0"           -- Impossible if BF=-1
delRN AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delRN AVL e
rl e
re AVL e
rr)
delRN AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRNZ AVL e
l e
e AVL e
rl e
re AVL e
rr
delRN AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delRP AVL e
rl e
re AVL e
rr)

-- | Delete rightmost from (Z l e r)
delRZ :: AVL e -> e -> AVL e -> AVL e
delRZ :: forall e. AVL e -> e -> AVL e -> AVL e
delRZ AVL e
_ e
_  AVL e
E           = AVL e
forall e. AVL e
E                          -- Terminal case, l must be E
delRZ AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZN AVL e
l e
e AVL e
rl e
re AVL e
rr
delRZ AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ AVL e
l e
e AVL e
rl e
re AVL e
rr
delRZ AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZP AVL e
l e
e AVL e
rl e
re AVL e
rr

-- | Delete rightmost from (P l e r)
delRP :: AVL e -> e -> AVL e -> AVL e
delRP :: forall e. AVL e -> e -> AVL e -> AVL e
delRP AVL e
l e
_  AVL e
E           = AVL e
l                          -- Terminal case, l must be of form (Z E le E)
delRP AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delRN AVL e
rl e
re AVL e
rr)
delRP AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRPZ AVL e
l e
e AVL e
rl e
re AVL e
rr
delRP AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delRP AVL e
rl e
re AVL e
rr)

-------------------------- delR LEVEL 2 -------------------------------
--                     delRNZ, delRZZ, delRPZ                        --
--                        delRZN, delRZP                             --
-----------------------------------------------------------------------

-- Delete rightmost from (N l e (Z rl re rr)), height of right sub-tree can't change in this case
delRNZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
{-# INLINE delRNZ #-}
delRNZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRNZ AVL e
_ e
e AVL e
_  e
_   AVL e
E              = 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                           -- Terminal case
delRNZ AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZN AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'
delRNZ AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'
delRNZ AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZP AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'

-- Delete rightmost from (Z l e (Z rl re rr)), height of right sub-tree can't change in this case
delRZZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ AVL e
l e
e AVL e
_  e
_   AVL e
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
forall e. AVL e
E                           -- Terminal case
delRZZ AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZN AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'
delRZZ AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'
delRZZ AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZP AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'

-- Delete rightmost from (P l e (Z rl re rr)), height of right sub-tree can't change in this case
delRPZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
{-# INLINE delRPZ #-}
delRPZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRPZ AVL e
l e
e AVL e
_  e
_   AVL e
E              = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalP AVL e
l e
e AVL e
forall e. AVL e
E                     -- Terminal case, Needs rebalancing
delRPZ AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZN AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'
delRPZ AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'
delRPZ AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZP AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr 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'

-- Delete rightmost from (Z l e (N rl re rr))
delRZN :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
{-# INLINE delRZN #-}
delRZN :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZN AVL e
l e
e AVL e
rl e
re AVL e
rr = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delRN AVL e
rl e
re AVL e
rr)

-- Delete rightmost from (Z l e (P rl re rr))
delRZP :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
{-# INLINE delRZP #-}
delRZP :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZP AVL e
l e
e AVL e
rl e
re AVL e
rr = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ AVL e
l e
e (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
delRP AVL e
rl e
re AVL e
rr)

-------------------------- popL LEVEL 1 -------------------------------
--                      popLN, popLZ, popLP                          --
-----------------------------------------------------------------------
-- | Delete leftmost from (N l e r)
popLN :: AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLN :: forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN  AVL e
E           e
e AVL e
r = UBT2(AVL e
e,r)                  -- Terminal case, r must be of form (Z E re E)
popLN (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
ll e
le AVL e
lr of
                         UBT2(AVL e
v,l) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(AVL e
v,t)
popLN (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLNZ AVL e
ll e
le AVL e
lr e
e AVL e
r
popLN (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
ll e
le AVL e
lr of
                         UBT2(AVL e
v,l) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(AVL e
v,t)

-- | Delete leftmost from (Z l e r)
popLZ :: AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZ :: forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLZ  AVL e
E           e
e AVL e
_ = UBT2(AVL e
forall e. AVL e
e,E)                  -- Terminal case, r must be E
popLZ (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZN AVL e
ll e
le AVL e
lr e
e AVL e
r
popLZ (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZZ AVL e
ll e
le AVL e
lr e
e AVL e
r
popLZ (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZP AVL e
ll e
le AVL e
lr e
e AVL e
r

-- | Delete leftmost from (P l e r)
popLP :: AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLP :: forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP  AVL e
E           e
_ AVL e
_ = [Char] -> (# e, AVL e #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popLP: Bug!"        -- Impossible if BF=+1
popLP (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
ll e
le AVL e
lr of
                         UBT2(AVL e
v,l) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(AVL e
v,t)
popLP (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLPZ AVL e
ll e
le AVL e
lr e
e AVL e
r
popLP (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
ll e
le AVL e
lr of
                         UBT2(AVL e
v,l) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(AVL e
v,t)

-------------------------- popL LEVEL 2 -------------------------------
--                     popLNZ, popLZZ, popLPZ                        --
--                        popLZN, popLZP                             --
-----------------------------------------------------------------------

-- Delete leftmost from (N (Z ll le lr) e r), height of left sub-tree can't change in this case
popLNZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
{-# INLINE popLNZ #-}
popLNZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLNZ  AVL e
E              e
le AVL e
_  e
e AVL e
r = let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalN AVL e
forall e. AVL e
E e
e AVL e
r              -- Terminal case, Needs rebalancing
                                   in  AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(le,t)
popLNZ (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZN AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
N e
l AVL e
e r)
popLNZ (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZZ AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
N e
l AVL e
e r)
popLNZ (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZP AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
N e
l AVL e
e r)

-- Delete leftmost from (Z (Z ll le lr) e r), height of left sub-tree can't change in this case
-- Don't INLINE this!
popLZZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZZ  AVL e
E              e
le AVL e
_  e
e AVL e
r = UBT2(leAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
forall e. AVL e
N e
E AVL e
e r)                     -- Terminal case
popLZZ (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZN AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
Z e
l AVL e
e r)
popLZZ (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZZ AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
Z e
l AVL e
e r)
popLZZ (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZP AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
Z e
l AVL e
e r)

-- Delete leftmost from (P (Z ll le lr) e r), height of left sub-tree can't change in this case
popLPZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
{-# INLINE popLPZ #-}
popLPZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLPZ  AVL e
E              e
le AVL e
_  e
e AVL e
_ = UBT2(leAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
forall e. AVL e
Z e
E AVL e
forall e. AVL e
e E)                     -- Terminal case
popLPZ (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZN AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
P e
l AVL e
e r)
popLPZ (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZZ AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
P e
l AVL e
e r)
popLPZ (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZP AVL e
lll e
lle AVL e
llr e
le AVL e
lr of
                                   UBT2(AVL e
v,l) -> UBT2(vAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
P e
l AVL e
e r)

-- Delete leftmost from (Z (N ll le lr) e r)
-- Don't INLINE this!
popLZN :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZN :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZN AVL e
ll e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
ll e
le AVL e
lr of
                      UBT2(AVL e
v,l) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(AVL e
v,t)
-- Delete leftmost from (Z (P ll le lr) e r)
-- Don't INLINE this!
popLZP :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZP :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e #)
popLZP AVL e
ll e
le AVL e
lr e
e AVL e
r = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
ll e
le AVL e
lr of
                      UBT2(AVL e
v,l) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# e, AVL e #) -> (# e, AVL e #)
forall a b. a -> b -> b
`seq` UBT2(AVL e
v,t)

-------------------------- popR LEVEL 1 -------------------------------
--                      popRN, popRZ, popRP                          --
-----------------------------------------------------------------------
-- | Delete rightmost from (N l e r)
popRN :: AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRN :: forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
_ e
_  AVL e
E           = [Char] -> (# AVL e, e #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popRN: Bug!"        -- Impossible if BF=-1
popRN AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
rl e
re AVL e
rr of
                         UBT2(e
r,v) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(e
t,v)
popRN AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRNZ AVL e
l e
e AVL e
rl e
re AVL e
rr
popRN AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
rl e
re AVL e
rr of
                         UBT2(e
r,v) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(e
t,v)

-- | Delete rightmost from (Z l e r)
popRZ :: AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZ :: forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRZ AVL e
_ e
e  AVL e
E           = UBT2(e
E,e)                  -- Terminal case, l must be E
popRZ AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZN AVL e
l e
e AVL e
rl e
re AVL e
rr
popRZ AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZZ AVL e
l e
e AVL e
rl e
re AVL e
rr
popRZ AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZP AVL e
l e
e AVL e
rl e
re AVL e
rr

-- | Delete rightmost from (P l e r)
popRP :: AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRP :: forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
l e
e  AVL e
E           = UBT2(e
l,e)                  -- Terminal case, l must be of form (Z E le E)
popRP AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
rl e
re AVL e
rr of
                         UBT2(e
r,v) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(e
t,v)
popRP AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRPZ AVL e
l e
e AVL e
rl e
re AVL e
rr
popRP AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
rl e
re AVL e
rr of
                         UBT2(e
r,v) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(e
t,v)

-------------------------- popR LEVEL 2 -------------------------------
--                     popRNZ, popRZZ, popRPZ                        --
--                        popRZN, popRZP                             --
-----------------------------------------------------------------------

-- Delete rightmost from (N l e (Z rl re rr)), height of right sub-tree can't change in this case
popRNZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
{-# INLINE popRNZ #-}
popRNZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRNZ AVL e
_ e
e AVL e
_  e
re  AVL e
E              = UBT2(Z E e E, re)                 -- Terminal case
popRNZ AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZN AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(N l e re
, v)
popRNZ AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZZ AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(N l e re
, v)
popRNZ AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZP AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(N l e re
, v)

-- Delete rightmost from (Z l e (Z rl re rr)), height of right sub-tree can't change in this case
-- Don't INLINE this!
popRZZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZZ AVL e
l e
e AVL e
_  e
re  AVL e
E              = UBT2(P l e E, re)                 -- Terminal case
popRZZ AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZN AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(Z l e re
, v)
popRZZ AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZZ AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(Z l e re
, v)
popRZZ AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZP AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(Z l e re
, v)

-- Delete rightmost from (P l e (Z rl re rr)), height of right sub-tree can't change in this case
popRPZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
{-# INLINE popRPZ #-}
popRPZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRPZ AVL e
l e
e AVL e
_  e
re  AVL e
E              = let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalP AVL e
l e
e AVL e
forall e. AVL e
E             -- Terminal case, Needs rebalancing
                                   in  AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(t,re)
popRPZ AVL e
l e
e AVL e
rl e
re (N AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZN AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(P l e re
, v)
popRPZ AVL e
l e
e AVL e
rl e
re (Z AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZZ AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(P l e re
, v)
popRPZ AVL e
l e
e AVL e
rl e
re (P AVL e
rrl e
rre AVL e
rrr) = case AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZP AVL e
rl e
re AVL e
rrl e
rre AVL e
rrr of
                                   UBT2(e
r,v) -> UBT2(P l e re
, v)

-- Delete rightmost from (Z l e (N rl re rr))
-- Don't INLINE this!
popRZN :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZN :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZN AVL e
l e
e AVL e
rl e
re AVL e
rr = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
rl e
re AVL e
rr of
                      UBT2(e
r,v) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(e
t,v)

-- Delete rightmost from (Z l e (P rl re rr))
-- Don't INLINE this!
popRZP :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZP :: forall e. AVL e -> e -> AVL e -> e -> AVL e -> (# AVL e, e #)
popRZP AVL e
l e
e AVL e
rl e
re AVL e
rr = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
rl e
re AVL e
rr of
                      UBT2(e
r,v) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# AVL e, e #) -> (# AVL e, e #)
forall a b. a -> b -> b
`seq` UBT2(e
t,v)

-- | Deletes a tree element. Assumes the path bits were extracted
-- from a 'Data.Tree.AVL.FullBP' constructor.
--
-- Complexity: O(log n)
deletePath :: UINT -> AVL e -> AVL e
deletePath :: forall e. Int# -> AVL e -> AVL e
deletePath Int#
_ AVL e
E         = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"deletePath: Element not found."
deletePath Int#
p (N AVL e
l e
e AVL e
r) = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delN Int#
p AVL e
l e
e AVL e
r
deletePath Int#
p (Z AVL e
l e
e AVL e
r) = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZ Int#
p AVL e
l e
e AVL e
r
deletePath Int#
p (P AVL e
l e
e AVL e
r) = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delP Int#
p AVL e
l e
e AVL e
r

----------------------------- LEVEL 1 ---------------------------------
--                       delN, delZ, delP                            --
-----------------------------------------------------------------------

-- Delete from (N l e r)
delN :: UINT -> AVL e -> e -> AVL e -> AVL e
delN :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delN Int#
p AVL e
l e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
               Ordering
LT -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
l e
e AVL e
r
               Ordering
EQ -> AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN AVL e
l AVL e
r
               Ordering
GT -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
l e
e AVL e
r

-- Delete from (Z l e r)
delZ :: UINT -> AVL e -> e -> AVL e -> AVL e
delZ :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZ Int#
p AVL e
l e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
               Ordering
LT -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
l e
e AVL e
r
               Ordering
EQ -> AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZR AVL e
l AVL e
r
               Ordering
GT -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
l e
e AVL e
r

-- Delete from (P l e r)
delP :: UINT -> AVL e -> e -> AVL e -> AVL e
delP :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delP Int#
p AVL e
l e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
               Ordering
LT -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
l e
e AVL e
r
               Ordering
EQ -> AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP AVL e
l AVL e
r
               Ordering
GT -> Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
l e
e AVL e
r

----------------------------- LEVEL 2 ---------------------------------
--                      delNL, delZL, delPL                          --
--                      delNR, delZR, delPR                          --
-----------------------------------------------------------------------

-- Delete from the left subtree of (N l e r)
delNL :: UINT -> AVL e -> e -> AVL e -> AVL e
delNL :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
t = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dNL (Int# -> Int#
goL Int#
p) AVL e
t
{-# INLINE dNL #-}
dNL :: UINT -> AVL e -> e -> AVL e -> AVL e
dNL :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dNL Int#
_  AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"deletePath: Element not found."              -- Left sub-tree is empty
dNL Int#
p (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN  AVL e
ll    AVL e
lr) e
e AVL e
r
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
dNL Int#
p (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> let l' :: AVL e
l' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
ll e
le AVL e
lr 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  -- height can't change
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN' (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZR AVL e
ll    AVL e
lr) e
e AVL e
r                    -- << But it can here
                         Ordering
GT -> let l' :: AVL e
l' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
ll e
le AVL e
lr 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  -- height can't change
dNL Int#
p (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP  AVL e
ll    AVL e
lr) e
e AVL e
r
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r

-- Delete from the right subtree of (N l e r)
delNR :: UINT -> AVL e -> e -> AVL e -> AVL e
delNR :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
t = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dNR (Int# -> Int#
goR Int#
p) AVL e
t
{-# INLINE dNR #-}
dNR :: UINT -> AVL e -> e -> AVL e -> AVL e
dNR :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dNR Int#
_ AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"delNR: Bug0"             -- Impossible
dNR Int#
p AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
rl e
re AVL e
rr)
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN  AVL e
rl    AVL e
rr)
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
rl e
re AVL e
rr)
dNR Int#
p AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> let r' :: AVL e
r' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
rl e
re AVL e
rr 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'   -- height can't change
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN' AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZL AVL e
rl    AVL e
rr)                    -- << But it can here
                         Ordering
GT -> let r' :: AVL e
r' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
rl e
re AVL e
rr 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'   -- height can't change
dNR Int#
p AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
rl e
re AVL e
rr)
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP  AVL e
rl    AVL e
rr)
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
rl e
re AVL e
rr)

-- Delete from the left subtree of (Z l e r)
delZL :: UINT -> AVL e -> e -> AVL e -> AVL e
delZL :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
t = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dZL (Int# -> Int#
goL Int#
p) AVL e
t
{-# INLINE dZL #-}
dZL :: UINT -> AVL e -> e -> AVL e -> AVL e
dZL :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dZL Int#
_  AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"deletePath: Element not found."               -- Left sub-tree is empty
dZL Int#
p (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN  AVL e
ll    AVL e
lr) e
e AVL e
r
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
dZL Int#
p (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> let l' :: AVL e
l' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
ll e
le AVL e
lr 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  -- height can't change
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ'  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZR AVL e
ll    AVL e
lr) e
e AVL e
r                  -- << But it can here
                         Ordering
GT -> let l' :: AVL e
l' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
ll e
le AVL e
lr 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  -- height can't change
dZL Int#
p (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP  AVL e
ll    AVL e
lr) e
e AVL e
r
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r

-- Delete from the right subtree of (Z l e r)
delZR :: UINT -> AVL e -> e -> AVL e -> AVL e
delZR :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
t = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dZR (Int# -> Int#
goR Int#
p) AVL e
t
{-# INLINE dZR #-}
dZR :: UINT -> AVL e -> e -> AVL e -> AVL e
dZR :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dZR Int#
_ AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"deletePath: Element not found."              -- Right sub-tree is empty
dZR Int#
p AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
rl e
re AVL e
rr)
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN  AVL e
rl    AVL e
rr)
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
rl e
re AVL e
rr)
dZR Int#
p AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> let r' :: AVL e
r' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
rl e
re AVL e
rr 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'  -- height can't change
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ' AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZL AVL e
rl AVL e
rr)                      -- << But it can here
                         Ordering
GT -> let r' :: AVL e
r' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
rl e
re AVL e
rr 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'  -- height can't change
dZR Int#
p AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
rl e
re AVL e
rr)
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP    AVL e
rl    AVL e
rr)
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
rl e
re AVL e
rr)

-- Delete from the left subtree of (P l e r)
delPL :: UINT -> AVL e -> e -> AVL e -> AVL e
delPL :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
t = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dPL (Int# -> Int#
goL Int#
p) AVL e
t
{-# INLINE dPL #-}
dPL :: UINT -> AVL e -> e -> AVL e -> AVL e
dPL :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dPL Int#
_  AVL e
E           e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"delPL: Bug0"             -- Impossible
dPL Int#
p (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN    AVL e
ll    AVL e
lr) e
e AVL e
r
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
dPL Int#
p (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> let l' :: AVL e
l' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
ll e
le AVL e
lr 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  -- height can't change
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP' (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZR AVL e
ll AVL e
lr) e
e AVL e
r                        -- << But it can here
                         Ordering
GT -> let l' :: AVL e
l' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
ll e
le AVL e
lr 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  -- height can't change
dPL Int#
p (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP    AVL e
ll    AVL e
lr) e
e AVL e
r
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
ll e
le AVL e
lr) e
e AVL e
r

-- Delete from the right subtree of (P l e r)
delPR :: UINT -> AVL e -> e -> AVL e -> AVL e
delPR :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
t = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dPR (Int# -> Int#
goR Int#
p) AVL e
t
{-# INLINE dPR #-}
dPR :: UINT -> AVL e -> e -> AVL e -> AVL e
dPR :: forall e. Int# -> AVL e -> e -> AVL e -> AVL e
dPR Int#
_ AVL e
_ e
_  AVL e
E           = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"deletePath: Element not found."               -- Right sub-tree is empty
dPR Int#
p AVL e
l e
e (N AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNL Int#
p AVL e
rl e
re AVL e
rr)
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP  AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subN    AVL e
rl    AVL e
rr)
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delNR Int#
p AVL e
rl e
re AVL e
rr)
dPR Int#
p AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> let r' :: AVL e
r' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZL Int#
p AVL e
rl e
re AVL e
rr 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'  -- height can't change
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP' AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subZL AVL e
rl AVL e
rr)                        -- << But it can here
                         Ordering
GT -> let r' :: AVL e
r' = Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delZR Int#
p AVL e
rl e
re AVL e
rr 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'  -- height can't change
dPR Int#
p AVL e
l e
e (P AVL e
rl e
re AVL e
rr) = case Int# -> Ordering
sel Int#
p of
                         Ordering
LT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPL Int#
p AVL e
rl e
re AVL e
rr)
                         Ordering
EQ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP  AVL e
l e
e (AVL e -> AVL e -> AVL e
forall e. AVL e -> AVL e -> AVL e
subP    AVL e
rl    AVL e
rr)
                         Ordering
GT -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRP  AVL e
l e
e (Int# -> AVL e -> e -> AVL e -> AVL e
forall e. Int# -> AVL e -> e -> AVL e -> AVL e
delPR Int#
p AVL e
rl e
re AVL e
rr)

-- | This is a modified version of popL which returns the (popped) tree height as well.
popHL :: AVL e -> UBT3(e,AVL e,UINT)
popHL :: forall e. AVL e -> (# e, AVL e, Int# #)
popHL  AVL e
E        = [Char] -> (# e, AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popHL: Empty tree."
popHL (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN AVL e
l e
e AVL e
r
popHL (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZ AVL e
l e
e AVL e
r
popHL (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP AVL e
l e
e AVL e
r

popHLN :: AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLN :: forall e. AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN AVL e
l e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN_ L(2AVL e
) e
l AVL e
e r of
               UBT3(e_,Int#
t,h) -> case AVL e
t of
                  AVL e
E        -> [Char] -> (# e, AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popHLN: Bug0"           -- impossible
                  Z AVL e
_ e
_ AVL e
_  -> UBT3(e_,t,DECINT1(h))          -- dH = -1
                  AVL e
_        -> UBT3(e_,t,        h )          -- dH =  0

popHLZ :: AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZ :: forall e. AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZ AVL e
l e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZ_ L(1AVL e
) e
l AVL e
e r of
               UBT3(e_,Int#
t,h) -> case AVL e
t of
                  AVL e
E        -> UBT3(AVL e
forall e. AVL e
e,E,L(0))                 -- Resulting tree is empty
                  P AVL e
_ e
_ AVL e
_  -> [Char] -> (# e, AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popHLZ: Bug0"           -- impossible
                  AVL e
_        -> UBT3(e_,t,        h )          -- dH =  0

popHLP :: AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLP :: forall e. AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP AVL e
l e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP_ L(1AVL e
) e
l AVL e
e r of
               UBT3(e_,Int#
t,h) -> case AVL e
t of
                  Z AVL e
_ e
_ AVL e
_  -> UBT3(e_,t,DECINT1(h))          -- dH = -1
                  P AVL e
_ e
_ AVL e
_  -> UBT3(e_,t,        h )          -- dH =  0
                  AVL e
_        -> [Char] -> (# e, AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popHLP: Bug0"           -- impossible

-------------------------- popHL LEVEL 1 ------------------------------
--                      popHLN_, popHLZ_, popHLP_                    --
-----------------------------------------------------------------------
-- Delete leftmost from (N l e r)
popHLN_ :: UINT -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLN_ :: forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN_ Int#
h  AVL e
E           e
e AVL e
r = UBT3(AVL e
e,Int#
r,h)                        -- Terminal case, r must be of form (Z E re E)
popHLN_ Int#
h (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN_ INCINT2(h) ll le lr of
                             UBT3(e_,l,hl) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(e_,t,hl)
popHLN_ Int#
h (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLNZ INCINT1(h) ll le lr e r
popHLN_ Int#
h (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP_ INCINT1(h) ll le lr of
                             UBT3(e_,l,hl) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLN AVL e
l e
e AVL e
r in AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(e_,t,hl)

-- Delete leftmost from (Z l e r)
{-# INLINE popHLZ_ #-}
popHLZ_ :: UINT -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZ_ :: forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZ_ Int#
h  AVL e
E           e
e AVL e
_ = UBT3(AVL e
forall e. AVL e
e,Int#
E,h)                       -- Terminal case, r must be E
popHLZ_ Int#
h (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZN INCINT2(h) ll le lr e r
popHLZ_ Int#
h (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZZ INCINT1(h) ll le lr e r
popHLZ_ Int#
h (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZP INCINT1(h) ll le lr e r

-- Delete leftmost from (P l e r)
popHLP_ :: UINT -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLP_ :: forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP_ Int#
_  AVL e
E           e
_ AVL e
_ = [Char] -> (# e, AVL e, Int# #)
forall a. HasCallStack => [Char] -> a
error [Char]
"popHLP_: Bug0"             -- Impossible if BF=+1
popHLP_ Int#
h (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN_ INCINT2(h) ll le lr of
                             UBT3(e_,l,hl) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(e_,t,hl)
popHLP_ Int#
h (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLPZ INCINT1(h) ll le lr e r
popHLP_ Int#
h (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP_ INCINT1(h) ll le lr of
                             UBT3(e_,l,hl) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(e_,t,hl)

-------------------------- popHL LEVEL 2 ------------------------------
--                     popHLNZ, popHLZZ, popHLPZ                     --
--                        popHLZN, popHLZP                           --
-----------------------------------------------------------------------

-- Delete leftmost from (N (Z ll le lr) e r), height of left sub-tree can't change in this case
{-# INLINE popHLNZ #-}
popHLNZ :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLNZ :: forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLNZ Int#
h  AVL e
E              e
le AVL e
_  e
e AVL e
r = let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalN AVL e
forall e. AVL e
E e
e AVL e
r         -- Terminal case, Needs rebalancing
                                      in  AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(le,Int#
t,h)
popHLNZ Int#
h (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZN INCINT2(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
N e
l AVL e
e r, hl)
popHLNZ Int#
h (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZZ INCINT1(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
N e
l AVL e
e r, hl)
popHLNZ Int#
h (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZP INCINT1(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
N e
l AVL e
e r, hl)

-- Delete leftmost from (Z (Z ll le lr) e r), height of left sub-tree can't change in this case
-- Don't INLINE this!
popHLZZ :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZZ :: forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZZ Int#
h  AVL e
E              e
le AVL e
_  e
e AVL e
r = UBT3(leAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
forall e. AVL e
N e
E AVL e
e rInt#
, h)            -- Terminal case
popHLZZ Int#
h (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZN INCINT2(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
Z e
l AVL e
e r, hl)
popHLZZ Int#
h (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZZ INCINT1(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
Z e
l AVL e
e r, hl)
popHLZZ Int#
h (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZP INCINT1(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
Z e
l AVL e
e r, hl)

-- Delete leftmost from (P (Z ll le lr) e r), height of left sub-tree can't change in this case
{-# INLINE popHLPZ #-}
popHLPZ :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLPZ :: forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLPZ Int#
h  AVL e
E              e
le AVL e
_  e
e AVL e
_ = UBT3(leAVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
forall e. AVL e
Z e
E AVL e
forall e. AVL e
e EInt#
, h)            -- Terminal case
popHLPZ Int#
h (N AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZN INCINT2(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
P e
l AVL e
e r, hl)
popHLPZ Int#
h (Z AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZZ INCINT1(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
P e
l AVL e
e r, hl)
popHLPZ Int#
h (P AVL e
lll e
lle AVL e
llr) e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZP INCINT1(h) lll lle llr le lr of
                                      UBT3(e_,l,hl) -> UBT3(e_AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
, AVL e
P e
l AVL e
e r, hl)

-- Delete leftmost from (Z (N ll le lr) e r)
-- Don't INLINE this!
popHLZN :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZN :: forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZN Int#
h AVL e
ll e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLN_ Int#
h AVL e
ll e
le AVL e
lr of
                         UBT3(e_,l,hl) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(e_,t,hl)
-- Delete leftmost from (Z (P ll le lr) e r)
-- Don't INLINE this!
popHLZP :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZP :: forall e.
Int# -> AVL e -> e -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLZP Int#
h AVL e
ll e
le AVL e
lr e
e AVL e
r = case Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
forall e. Int# -> AVL e -> e -> AVL e -> (# e, AVL e, Int# #)
popHLP_ Int#
h AVL e
ll e
le AVL e
lr of
                         UBT3(e_,l,hl) -> let t :: AVL e
t = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ AVL e
l e
e AVL e
r in  AVL e
t AVL e -> (# e, AVL e, Int# #) -> (# e, AVL e, Int# #)
forall a b. a -> b -> b
`seq` UBT3(e_,t,hl)

{-************************** Balancing Utilities Below Here ************************************-}

-- Rebalance a tree of form (N l e r) which has become unbalanced as
-- a result of the height of the left sub-tree (l) decreasing by 1.
-- N.B Result is never of form (N _ _ _) (or E!)
rebalN :: AVL e -> e -> AVL e -> AVL e
rebalN :: forall e. AVL e -> e -> AVL e -> AVL e
rebalN AVL e
_ e
_  AVL e
E                        = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"rebalN: Bug0"             -- impossible case
rebalN AVL e
l e
e (N AVL e
rl              e
re AVL e
rr) = 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               -- N->Z, dH=-1
rebalN AVL e
l e
e (Z AVL e
rl              e
re AVL e
rr) = 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
N AVL e
l e
e AVL e
rl) e
re AVL e
rr               -- N->P, dH= 0
rebalN AVL e
_ e
_ (P  AVL e
E               e
_  AVL e
_) = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"rebalN: Bug1"             -- impossible case
rebalN AVL e
l e
e (P (N AVL e
rll e
rle AVL e
rlr) e
re AVL e
rr) = 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
P AVL e
l e
e AVL e
rll) e
rle (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
rlr e
re AVL e
rr)  -- N->Z, dH=-1
rebalN AVL e
l e
e (P (Z AVL e
rll e
rle AVL e
rlr) e
re AVL e
rr) = 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
rll) e
rle (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
rlr e
re AVL e
rr)  -- N->Z, dH=-1
rebalN AVL e
l e
e (P (P AVL e
rll e
rle AVL e
rlr) e
re AVL e
rr) = 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
rll) e
rle (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
rlr e
re AVL e
rr)  -- N->Z, dH=-1

-- Rebalance a tree of form (P l e r) which has become unbalanced as
-- a result of the height of the right sub-tree (r) decreasing by 1.
-- N.B Result is never of form (P _ _ _) (or E!)
rebalP :: AVL e -> e -> AVL e -> AVL e
rebalP :: forall e. AVL e -> e -> AVL e -> AVL e
rebalP  AVL e
E                        e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"rebalP: Bug0"             -- impossible case
rebalP (P AVL e
ll 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
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)               -- P->Z, dH=-1
rebalP (Z AVL e
ll 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
N AVL e
ll e
le (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
lr e
e AVL e
r)               -- P->N, dH= 0
rebalP (N  AVL e
_  e
_  AVL e
E             ) e
_ AVL e
_ = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"rebalP: Bug1"             -- impossible case
rebalP (N AVL e
ll e
le (P AVL e
lrl e
lre AVL e
lrr)) e
e AVL e
r = 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
ll e
le AVL e
lrl) e
lre (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
lrr e
e AVL e
r)  -- P->Z, dH=-1
rebalP (N AVL e
ll e
le (Z AVL e
lrl e
lre AVL e
lrr)) e
e AVL e
r = 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
ll e
le AVL e
lrl) e
lre (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
lrr e
e AVL e
r)  -- P->Z, dH=-1
rebalP (N AVL e
ll e
le (N AVL e
lrl e
lre AVL e
lrr)) e
e AVL e
r = 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
P AVL e
ll e
le AVL e
lrl) e
lre (AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
lrr e
e AVL e
r)  -- P->Z, dH=-1

-- | Check for height changes in left subtree of (N l e r),
-- where l was (N ll le lr) or (P ll le lr)
chkLN :: AVL e -> e -> AVL e -> AVL e
chkLN :: forall e. AVL e -> e -> AVL e -> AVL e
chkLN AVL e
l e
e AVL e
r = case AVL e
l of
              AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"chkLN: Bug0"   -- impossible if BF<>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               -- BF +/-1 -> -1, so dH= 0
              Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalN AVL e
l e
e AVL e
r          -- BF +/-1 ->  0, so dH=-1
              P 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               -- BF +/-1 -> +1, so dH= 0
-- | Check for height changes in left subtree of (Z l e r),
-- where l was (N ll le lr) or (P ll le lr)
chkLZ :: AVL e -> e -> AVL e -> AVL e
chkLZ :: forall e. AVL e -> e -> AVL e -> AVL e
chkLZ AVL e
l e
e AVL e
r = case AVL e
l of
              AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"chkLZ: Bug0"   -- impossible if BF<>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               -- BF +/-1 -> -1, so dH= 0
              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               -- BF +/-1 ->  0, so dH=-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               -- BF +/-1 -> +1, so dH= 0
-- | Check for height changes in left subtree of (P l e r),
-- where l was (N ll le lr) or (P ll le lr)
chkLP :: AVL e -> e -> AVL e -> AVL e
chkLP :: forall e. AVL e -> e -> AVL e -> AVL e
chkLP AVL e
l e
e AVL e
r = case AVL e
l of
              AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"chkLP: Bug0"   -- impossible if BF<>0
              N 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               -- BF +/-1 -> -1, so dH= 0
              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               -- BF +/-1 ->  0, so dH=-1
              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               -- BF +/-1 -> +1, so dH= 0
-- | Check for height changes in right subtree of (N l e r),
-- where r was (N rl re rr) or (P rl re rr)
chkRN :: AVL e -> e -> AVL e -> AVL e
chkRN :: forall e. AVL e -> e -> AVL e -> AVL e
chkRN AVL e
l e
e AVL e
r = case AVL e
r of
              AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"chkRN: Bug0"   -- impossible if BF<>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               -- BF +/-1 -> -1, so dH= 0
              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               -- BF +/-1 ->  0, so dH=-1
              P 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               -- BF +/-1 -> +1, so dH= 0
-- | Check for height changes in right subtree of (Z l e r),
-- where r was (N rl re rr) or (P rl re rr)
chkRZ :: AVL e -> e -> AVL e -> AVL e
chkRZ :: forall e. AVL e -> e -> AVL e -> AVL e
chkRZ AVL e
l e
e AVL e
r = case AVL e
r of
              AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"chkRZ: Bug0"   -- impossible if BF<>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               -- BF +/-1 -> -1, so dH= 0
              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               -- BF +/-1 ->  0, so dH=-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               -- BF +/-1 -> +1, so dH= 0
-- | Check for height changes in right subtree of (P l e r),
-- where l was (N rl re rr) or (P rl re rr)
chkRP :: AVL e -> e -> AVL e -> AVL e
chkRP :: forall e. AVL e -> e -> AVL e -> AVL e
chkRP AVL e
l e
e AVL e
r = case AVL e
r of
              AVL e
E       -> [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"chkRP: Bug0"   -- impossible if BF<>0
              N 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               -- BF +/-1 -> -1, so dH= 0
              Z AVL e
_ e
_ AVL e
_ -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalP AVL e
l e
e AVL e
r          -- BF +/-1 ->  0, so dH=-1
              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               -- BF +/-1 -> +1, so dH= 0

-- | Substitute deleted element from (N l _ r)
subN :: AVL e -> AVL e -> AVL e
subN :: forall e. AVL e -> AVL e -> AVL e
subN AVL e
_  AVL e
E            = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"subN: Bug0"      -- Impossible
subN 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_) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e AVL e
r_
subN 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_) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN' AVL e
l e
e AVL e
r_
subN 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_) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRN  AVL e
l e
e AVL e
r_

-- | Substitute deleted element from (Z l _ r)
-- Pops the replacement from the right sub-tree, so result may be (P _ _ _)
subZR :: AVL e -> AVL e -> AVL e
subZR :: forall e. AVL e -> AVL e -> AVL e
subZR AVL e
_  AVL e
E            = AVL e
forall e. AVL e
E   -- Both left and right subtrees must have been empty
subZR 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_) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e AVL e
r_
subZR 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_) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ' AVL e
l e
e AVL e
r_
subZR 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_) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkRZ  AVL e
l e
e AVL e
r_

-- | Local utility to substitute deleted element from (Z l _ r)
-- Pops the replacement from the left sub-tree, so result may be (N _ _ _)
subZL :: AVL e -> AVL e -> AVL e
subZL :: forall e. AVL e -> AVL e -> AVL e
subZL  AVL e
E           AVL e
_  = AVL e
forall e. AVL e
E   -- Both left and right subtrees must have been empty
subZL (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) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  AVL e
l_ e
e AVL e
r
subZL (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) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ' AVL e
l_ e
e AVL e
r
subZL (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) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLZ  AVL e
l_ e
e AVL e
r

-- | Substitute deleted element from (P l _ r)
subP :: AVL e -> AVL e -> AVL e
subP :: forall e. AVL e -> AVL e -> AVL e
subP  AVL e
E           AVL e
_  = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"subP: Bug0"      -- Impossible
subP (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) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  AVL e
l_ e
e AVL e
r
subP (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) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP' AVL e
l_ e
e AVL e
r
subP (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) -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
chkLP  AVL e
l_ e
e AVL e
r

-- | Check for height changes in left subtree of (N l e r),
-- where l was (Z ll le lr)
chkLN' :: AVL e -> e -> AVL e -> AVL e
chkLN' :: forall e. AVL e -> e -> AVL e -> AVL e
chkLN' AVL e
l e
e AVL e
r = case AVL e
l of
               AVL e
E       -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalN AVL e
l e
e AVL e
r  -- BF 0 -> E, so dH=-1
               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       -- Otherwise dH=0
-- | Check for height changes in left subtree of (Z l e r),
-- where l was (Z ll le lr)
chkLZ' :: AVL e -> e -> AVL e -> AVL e
chkLZ' :: forall e. AVL e -> e -> AVL e -> AVL e
chkLZ' AVL e
l e
e AVL e
r = case AVL e
l of
               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
r      -- BF 0 -> E, so dH=-1
               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      -- Otherwise dH=0
-- | Check for height changes in left subtree of (P l e r),
-- where l was (Z ll le lr)
chkLP' :: AVL e -> e -> AVL e -> AVL e
chkLP' :: forall e. AVL e -> e -> AVL e -> AVL e
chkLP' AVL e
l e
e AVL e
r = case AVL e
l of
               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
r      -- BF 0 -> E, so dH=-1
               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      -- Otherwise dH=0
-- | Check for height changes in right subtree of (N l e r),
-- where r was (Z rl re rr)
chkRN' :: AVL e -> e -> AVL e -> AVL e
chkRN' :: forall e. AVL e -> e -> AVL e -> AVL e
chkRN' AVL e
l e
e AVL e
r = case AVL e
r of
               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
r      -- BF 0 -> E, so dH=-1
               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      -- Otherwise dH=0
-- | Check for height changes in right subtree of (Z l e r),
-- where r was (Z rl re rr)
chkRZ' :: AVL e -> e -> AVL e -> AVL e
chkRZ' :: forall e. AVL e -> e -> AVL e -> AVL e
chkRZ' AVL e
l e
e AVL e
r = case AVL e
r of
               AVL e
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      -- BF 0 -> E, so dH=-1
               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      -- Otherwise dH=0
-- | Check for height changes in right subtree of (P l e r),
-- where l was (Z rl re rr)
chkRP' :: AVL e -> e -> AVL e -> AVL e
chkRP' :: forall e. AVL e -> e -> AVL e -> AVL e
chkRP' AVL e
l e
e AVL e
r = case AVL e
r of
               AVL e
E       -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
rebalP AVL e
l e
e AVL e
r -- BF 0 -> E, so dH=-1
               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      -- Otherwise dH=0