module Data.Tree.AVL.Internals.DelUtils
(
delRN,delRZ,delRP,delLN,delLZ,delLP,
popRN,popRZ,popRP,popLN,popLZ,popLP,
popHL,popHLN,popHLZ,popHLP,
chkLN,chkLZ,chkLP,chkRN,chkRZ,chkRP,
chkLN',chkLZ',chkLP',chkRN',chkRZ',chkRP',
subN,subZR,subZL,subP,
deletePath,
) where
import Data.Tree.AVL.Types(AVL(..))
import Data.Tree.AVL.BinPath(sel,goL,goR)
#ifdef __GLASGOW_HASKELL__
import GHC.Base
#include "ghcdefs.h"
#else
#include "h98defs.h"
#endif
delLN :: AVL e -> e -> AVL e -> AVL e
delLN E _ r = r
delLN (N ll le lr) e r = chkLN (delLN ll le lr) e r
delLN (Z ll le lr) e r = delLNZ ll le lr e r
delLN (P ll le lr) e r = chkLN (delLP ll le lr) e r
delLZ :: AVL e -> e -> AVL e -> AVL e
delLZ E _ _ = E
delLZ (N ll le lr) e r = delLZN ll le lr e r
delLZ (Z ll le lr) e r = delLZZ ll le lr e r
delLZ (P ll le lr) e r = delLZP ll le lr e r
delLP :: AVL e -> e -> AVL e -> AVL e
delLP E _ _ = error "delLP: Bug0"
delLP (N ll le lr) e r = chkLP (delLN ll le lr) e r
delLP (Z ll le lr) e r = delLPZ ll le lr e r
delLP (P ll le lr) e r = chkLP (delLP ll le lr) e r
delLNZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLNZ E _ _ e r = rebalN E e r
delLNZ (N lll lle llr) le lr e r = let l' = delLZN lll lle llr le lr in l' `seq` N l' e r
delLNZ (Z lll lle llr) le lr e r = let l' = delLZZ lll lle llr le lr in l' `seq` N l' e r
delLNZ (P lll lle llr) le lr e r = let l' = delLZP lll lle llr le lr in l' `seq` N l' e r
delLZZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZZ E _ _ e r = N E e r
delLZZ (N lll lle llr) le lr e r = let l' = delLZN lll lle llr le lr in l' `seq` Z l' e r
delLZZ (Z lll lle llr) le lr e r = let l' = delLZZ lll lle llr le lr in l' `seq` Z l' e r
delLZZ (P lll lle llr) le lr e r = let l' = delLZP lll lle llr le lr in l' `seq` Z l' e r
delLPZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLPZ E _ _ e _ = Z E e E
delLPZ (N lll lle llr) le lr e r = let l' = delLZN lll lle llr le lr in l' `seq` P l' e r
delLPZ (Z lll lle llr) le lr e r = let l' = delLZZ lll lle llr le lr in l' `seq` P l' e r
delLPZ (P lll lle llr) le lr e r = let l' = delLZP lll lle llr le lr in l' `seq` P l' e r
delLZN :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZN ll le lr e r = chkLZ (delLN ll le lr) e r
delLZP :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delLZP ll le lr e r = chkLZ (delLP ll le lr) e r
delRN :: AVL e -> e -> AVL e -> AVL e
delRN _ _ E = error "delRN: Bug0"
delRN l e (N rl re rr) = chkRN l e (delRN rl re rr)
delRN l e (Z rl re rr) = delRNZ l e rl re rr
delRN l e (P rl re rr) = chkRN l e (delRP rl re rr)
delRZ :: AVL e -> e -> AVL e -> AVL e
delRZ _ _ E = E
delRZ l e (N rl re rr) = delRZN l e rl re rr
delRZ l e (Z rl re rr) = delRZZ l e rl re rr
delRZ l e (P rl re rr) = delRZP l e rl re rr
delRP :: AVL e -> e -> AVL e -> AVL e
delRP l _ E = l
delRP l e (N rl re rr) = chkRP l e (delRN rl re rr)
delRP l e (Z rl re rr) = delRPZ l e rl re rr
delRP l e (P rl re rr) = chkRP l e (delRP rl re rr)
delRNZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRNZ _ e _ _ E = Z E e E
delRNZ l e rl re (N rrl rre rrr) = let r' = delRZN rl re rrl rre rrr in r' `seq` N l e r'
delRNZ l e rl re (Z rrl rre rrr) = let r' = delRZZ rl re rrl rre rrr in r' `seq` N l e r'
delRNZ l e rl re (P rrl rre rrr) = let r' = delRZP rl re rrl rre rrr in r' `seq` N l e r'
delRZZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZZ l e _ _ E = P l e E
delRZZ l e rl re (N rrl rre rrr) = let r' = delRZN rl re rrl rre rrr in r' `seq` Z l e r'
delRZZ l e rl re (Z rrl rre rrr) = let r' = delRZZ rl re rrl rre rrr in r' `seq` Z l e r'
delRZZ l e rl re (P rrl rre rrr) = let r' = delRZP rl re rrl rre rrr in r' `seq` Z l e r'
delRPZ :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRPZ l e _ _ E = rebalP l e E
delRPZ l e rl re (N rrl rre rrr) = let r' = delRZN rl re rrl rre rrr in r' `seq` P l e r'
delRPZ l e rl re (Z rrl rre rrr) = let r' = delRZZ rl re rrl rre rrr in r' `seq` P l e r'
delRPZ l e rl re (P rrl rre rrr) = let r' = delRZP rl re rrl rre rrr in r' `seq` P l e r'
delRZN :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZN l e rl re rr = chkRZ l e (delRN rl re rr)
delRZP :: AVL e -> e -> AVL e -> e -> AVL e -> AVL e
delRZP l e rl re rr = chkRZ l e (delRP rl re rr)
popLN :: AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLN E e r = UBT2(e,r)
popLN (N ll le lr) e r = case popLN ll le lr of
UBT2(v,l) -> let t = chkLN l e r in t `seq` UBT2(v,t)
popLN (Z ll le lr) e r = popLNZ ll le lr e r
popLN (P ll le lr) e r = case popLP ll le lr of
UBT2(v,l) -> let t = chkLN l e r in t `seq` UBT2(v,t)
popLZ :: AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZ E e _ = UBT2(e,E)
popLZ (N ll le lr) e r = popLZN ll le lr e r
popLZ (Z ll le lr) e r = popLZZ ll le lr e r
popLZ (P ll le lr) e r = popLZP ll le lr e r
popLP :: AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLP E _ _ = error "popLP: Bug!"
popLP (N ll le lr) e r = case popLN ll le lr of
UBT2(v,l) -> let t = chkLP l e r in t `seq` UBT2(v,t)
popLP (Z ll le lr) e r = popLPZ ll le lr e r
popLP (P ll le lr) e r = case popLP ll le lr of
UBT2(v,l) -> let t = chkLP l e r in t `seq` UBT2(v,t)
popLNZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLNZ E le _ e r = let t = rebalN E e r
in t `seq` UBT2(le,t)
popLNZ (N lll lle llr) le lr e r = case popLZN lll lle llr le lr of
UBT2(v,l) -> UBT2(v, N l e r)
popLNZ (Z lll lle llr) le lr e r = case popLZZ lll lle llr le lr of
UBT2(v,l) -> UBT2(v, N l e r)
popLNZ (P lll lle llr) le lr e r = case popLZP lll lle llr le lr of
UBT2(v,l) -> UBT2(v, N l e r)
popLZZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZZ E le _ e r = UBT2(le, N E e r)
popLZZ (N lll lle llr) le lr e r = case popLZN lll lle llr le lr of
UBT2(v,l) -> UBT2(v, Z l e r)
popLZZ (Z lll lle llr) le lr e r = case popLZZ lll lle llr le lr of
UBT2(v,l) -> UBT2(v, Z l e r)
popLZZ (P lll lle llr) le lr e r = case popLZP lll lle llr le lr of
UBT2(v,l) -> UBT2(v, Z l e r)
popLPZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLPZ E le _ e _ = UBT2(le, Z E e E)
popLPZ (N lll lle llr) le lr e r = case popLZN lll lle llr le lr of
UBT2(v,l) -> UBT2(v, P l e r)
popLPZ (Z lll lle llr) le lr e r = case popLZZ lll lle llr le lr of
UBT2(v,l) -> UBT2(v, P l e r)
popLPZ (P lll lle llr) le lr e r = case popLZP lll lle llr le lr of
UBT2(v,l) -> UBT2(v, P l e r)
popLZN :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZN ll le lr e r = case popLN ll le lr of
UBT2(v,l) -> let t = chkLZ l e r in t `seq` UBT2(v,t)
popLZP :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(e,AVL e)
popLZP ll le lr e r = case popLP ll le lr of
UBT2(v,l) -> let t = chkLZ l e r in t `seq` UBT2(v,t)
popRN :: AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRN _ _ E = error "popRN: Bug!"
popRN l e (N rl re rr) = case popRN rl re rr of
UBT2(r,v) -> let t = chkRN l e r in t `seq` UBT2(t,v)
popRN l e (Z rl re rr) = popRNZ l e rl re rr
popRN l e (P rl re rr) = case popRP rl re rr of
UBT2(r,v) -> let t = chkRN l e r in t `seq` UBT2(t,v)
popRZ :: AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZ _ e E = UBT2(E,e)
popRZ l e (N rl re rr) = popRZN l e rl re rr
popRZ l e (Z rl re rr) = popRZZ l e rl re rr
popRZ l e (P rl re rr) = popRZP l e rl re rr
popRP :: AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRP l e E = UBT2(l,e)
popRP l e (N rl re rr) = case popRN rl re rr of
UBT2(r,v) -> let t = chkRP l e r in t `seq` UBT2(t,v)
popRP l e (Z rl re rr) = popRPZ l e rl re rr
popRP l e (P rl re rr) = case popRP rl re rr of
UBT2(r,v) -> let t = chkRP l e r in t `seq` UBT2(t,v)
popRNZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRNZ _ e _ re E = UBT2(Z E e E, re)
popRNZ l e rl re (N rrl rre rrr) = case popRZN rl re rrl rre rrr of
UBT2(r,v) -> UBT2(N l e r, v)
popRNZ l e rl re (Z rrl rre rrr) = case popRZZ rl re rrl rre rrr of
UBT2(r,v) -> UBT2(N l e r, v)
popRNZ l e rl re (P rrl rre rrr) = case popRZP rl re rrl rre rrr of
UBT2(r,v) -> UBT2(N l e r, v)
popRZZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZZ l e _ re E = UBT2(P l e E, re)
popRZZ l e rl re (N rrl rre rrr) = case popRZN rl re rrl rre rrr of
UBT2(r,v) -> UBT2(Z l e r, v)
popRZZ l e rl re (Z rrl rre rrr) = case popRZZ rl re rrl rre rrr of
UBT2(r,v) -> UBT2(Z l e r, v)
popRZZ l e rl re (P rrl rre rrr) = case popRZP rl re rrl rre rrr of
UBT2(r,v) -> UBT2(Z l e r, v)
popRPZ :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRPZ l e _ re E = let t = rebalP l e E
in t `seq` UBT2(t,re)
popRPZ l e rl re (N rrl rre rrr) = case popRZN rl re rrl rre rrr of
UBT2(r,v) -> UBT2(P l e r, v)
popRPZ l e rl re (Z rrl rre rrr) = case popRZZ rl re rrl rre rrr of
UBT2(r,v) -> UBT2(P l e r, v)
popRPZ l e rl re (P rrl rre rrr) = case popRZP rl re rrl rre rrr of
UBT2(r,v) -> UBT2(P l e r, v)
popRZN :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZN l e rl re rr = case popRN rl re rr of
UBT2(r,v) -> let t = chkRZ l e r in t `seq` UBT2(t,v)
popRZP :: AVL e -> e -> AVL e -> e -> AVL e -> UBT2(AVL e,e)
popRZP l e rl re rr = case popRP rl re rr of
UBT2(r,v) -> let t = chkRZ l e r in t `seq` UBT2(t,v)
deletePath :: UINT -> AVL e -> AVL e
deletePath _ E = error "deletePath: Element not found."
deletePath p (N l e r) = delN p l e r
deletePath p (Z l e r) = delZ p l e r
deletePath p (P l e r) = delP p l e r
delN :: UINT -> AVL e -> e -> AVL e -> AVL e
delN p l e r = case sel p of
LT -> delNL p l e r
EQ -> subN l r
GT -> delNR p l e r
delZ :: UINT -> AVL e -> e -> AVL e -> AVL e
delZ p l e r = case sel p of
LT -> delZL p l e r
EQ -> subZR l r
GT -> delZR p l e r
delP :: UINT -> AVL e -> e -> AVL e -> AVL e
delP p l e r = case sel p of
LT -> delPL p l e r
EQ -> subP l r
GT -> delPR p l e r
delNL :: UINT -> AVL e -> e -> AVL e -> AVL e
delNL p t = dNL (goL p) t
dNL :: UINT -> AVL e -> e -> AVL e -> AVL e
dNL _ E _ _ = error "deletePath: Element not found."
dNL p (N ll le lr) e r = case sel p of
LT -> chkLN (delNL p ll le lr) e r
EQ -> chkLN (subN ll lr) e r
GT -> chkLN (delNR p ll le lr) e r
dNL p (Z ll le lr) e r = case sel p of
LT -> let l' = delZL p ll le lr in l' `seq` N l' e r
EQ -> chkLN' (subZR ll lr) e r
GT -> let l' = delZR p ll le lr in l' `seq` N l' e r
dNL p (P ll le lr) e r = case sel p of
LT -> chkLN (delPL p ll le lr) e r
EQ -> chkLN (subP ll lr) e r
GT -> chkLN (delPR p ll le lr) e r
delNR :: UINT -> AVL e -> e -> AVL e -> AVL e
delNR p t = dNR (goR p) t
dNR :: UINT -> AVL e -> e -> AVL e -> AVL e
dNR _ _ _ E = error "delNR: Bug0"
dNR p l e (N rl re rr) = case sel p of
LT -> chkRN l e (delNL p rl re rr)
EQ -> chkRN l e (subN rl rr)
GT -> chkRN l e (delNR p rl re rr)
dNR p l e (Z rl re rr) = case sel p of
LT -> let r' = delZL p rl re rr in r' `seq` N l e r'
EQ -> chkRN' l e (subZL rl rr)
GT -> let r' = delZR p rl re rr in r' `seq` N l e r'
dNR p l e (P rl re rr) = case sel p of
LT -> chkRN l e (delPL p rl re rr)
EQ -> chkRN l e (subP rl rr)
GT -> chkRN l e (delPR p rl re rr)
delZL :: UINT -> AVL e -> e -> AVL e -> AVL e
delZL p t = dZL (goL p) t
dZL :: UINT -> AVL e -> e -> AVL e -> AVL e
dZL _ E _ _ = error "deletePath: Element not found."
dZL p (N ll le lr) e r = case sel p of
LT -> chkLZ (delNL p ll le lr) e r
EQ -> chkLZ (subN ll lr) e r
GT -> chkLZ (delNR p ll le lr) e r
dZL p (Z ll le lr) e r = case sel p of
LT -> let l' = delZL p ll le lr in l' `seq` Z l' e r
EQ -> chkLZ' (subZR ll lr) e r
GT -> let l' = delZR p ll le lr in l' `seq` Z l' e r
dZL p (P ll le lr) e r = case sel p of
LT -> chkLZ (delPL p ll le lr) e r
EQ -> chkLZ (subP ll lr) e r
GT -> chkLZ (delPR p ll le lr) e r
delZR :: UINT -> AVL e -> e -> AVL e -> AVL e
delZR p t = dZR (goR p) t
dZR :: UINT -> AVL e -> e -> AVL e -> AVL e
dZR _ _ _ E = error "deletePath: Element not found."
dZR p l e (N rl re rr) = case sel p of
LT -> chkRZ l e (delNL p rl re rr)
EQ -> chkRZ l e (subN rl rr)
GT -> chkRZ l e (delNR p rl re rr)
dZR p l e (Z rl re rr) = case sel p of
LT -> let r' = delZL p rl re rr in r' `seq` Z l e r'
EQ -> chkRZ' l e (subZL rl rr)
GT -> let r' = delZR p rl re rr in r' `seq` Z l e r'
dZR p l e (P rl re rr) = case sel p of
LT -> chkRZ l e (delPL p rl re rr)
EQ -> chkRZ l e (subP rl rr)
GT -> chkRZ l e (delPR p rl re rr)
delPL :: UINT -> AVL e -> e -> AVL e -> AVL e
delPL p t = dPL (goL p) t
dPL :: UINT -> AVL e -> e -> AVL e -> AVL e
dPL _ E _ _ = error "delPL: Bug0"
dPL p (N ll le lr) e r = case sel p of
LT -> chkLP (delNL p ll le lr) e r
EQ -> chkLP (subN ll lr) e r
GT -> chkLP (delNR p ll le lr) e r
dPL p (Z ll le lr) e r = case sel p of
LT -> let l' = delZL p ll le lr in l' `seq` P l' e r
EQ -> chkLP' (subZR ll lr) e r
GT -> let l' = delZR p ll le lr in l' `seq` P l' e r
dPL p (P ll le lr) e r = case sel p of
LT -> chkLP (delPL p ll le lr) e r
EQ -> chkLP (subP ll lr) e r
GT -> chkLP (delPR p ll le lr) e r
delPR :: UINT -> AVL e -> e -> AVL e -> AVL e
delPR p t = dPR (goR p) t
dPR :: UINT -> AVL e -> e -> AVL e -> AVL e
dPR _ _ _ E = error "deletePath: Element not found."
dPR p l e (N rl re rr) = case sel p of
LT -> chkRP l e (delNL p rl re rr)
EQ -> chkRP l e (subN rl rr)
GT -> chkRP l e (delNR p rl re rr)
dPR p l e (Z rl re rr) = case sel p of
LT -> let r' = delZL p rl re rr in r' `seq` P l e r'
EQ -> chkRP' l e (subZL rl rr)
GT -> let r' = delZR p rl re rr in r' `seq` P l e r'
dPR p l e (P rl re rr) = case sel p of
LT -> chkRP l e (delPL p rl re rr)
EQ -> chkRP l e (subP rl rr)
GT -> chkRP l e (delPR p rl re rr)
popHL :: AVL e -> UBT3(e,AVL e,UINT)
popHL E = error "popHL: Empty tree."
popHL (N l e r) = popHLN l e r
popHL (Z l e r) = popHLZ l e r
popHL (P l e r) = popHLP l e r
popHLN :: AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLN l e r = case popHLN_ L(2) l e r of
UBT3(e_,t,h) -> case t of
E -> error "popHLN: Bug0"
Z _ _ _ -> UBT3(e_,t,DECINT1(h))
_ -> UBT3(e_,t, h )
popHLZ :: AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZ l e r = case popHLZ_ L(1) l e r of
UBT3(e_,t,h) -> case t of
E -> UBT3(e,E,L(0))
P _ _ _ -> error "popHLZ: Bug0"
_ -> UBT3(e_,t, h )
popHLP :: AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLP l e r = case popHLP_ L(1) l e r of
UBT3(e_,t,h) -> case t of
Z _ _ _ -> UBT3(e_,t,DECINT1(h))
P _ _ _ -> UBT3(e_,t, h )
_ -> error "popHLP: Bug0"
popHLN_ :: UINT -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLN_ h E e r = UBT3(e,r,h)
popHLN_ h (N ll le lr) e r = case popHLN_ INCINT2(h) ll le lr of
UBT3(e_,l,hl) -> let t = chkLN l e r in t `seq` UBT3(e_,t,hl)
popHLN_ h (Z ll le lr) e r = popHLNZ INCINT1(h) ll le lr e r
popHLN_ h (P ll le lr) e r = case popHLP_ INCINT1(h) ll le lr of
UBT3(e_,l,hl) -> let t = chkLN l e r in t `seq` UBT3(e_,t,hl)
popHLZ_ :: UINT -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZ_ h E e _ = UBT3(e,E,h)
popHLZ_ h (N ll le lr) e r = popHLZN INCINT2(h) ll le lr e r
popHLZ_ h (Z ll le lr) e r = popHLZZ INCINT1(h) ll le lr e r
popHLZ_ h (P ll le lr) e r = popHLZP INCINT1(h) ll le lr e r
popHLP_ :: UINT -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLP_ _ E _ _ = error "popHLP_: Bug0"
popHLP_ h (N ll le lr) e r = case popHLN_ INCINT2(h) ll le lr of
UBT3(e_,l,hl) -> let t = chkLP l e r in t `seq` UBT3(e_,t,hl)
popHLP_ h (Z ll le lr) e r = popHLPZ INCINT1(h) ll le lr e r
popHLP_ h (P ll le lr) e r = case popHLP_ INCINT1(h) ll le lr of
UBT3(e_,l,hl) -> let t = chkLP l e r in t `seq` UBT3(e_,t,hl)
popHLNZ :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLNZ h E le _ e r = let t = rebalN E e r
in t `seq` UBT3(le,t,h)
popHLNZ h (N lll lle llr) le lr e r = case popHLZN INCINT2(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, N l e r, hl)
popHLNZ h (Z lll lle llr) le lr e r = case popHLZZ INCINT1(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, N l e r, hl)
popHLNZ h (P lll lle llr) le lr e r = case popHLZP INCINT1(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, N l e r, hl)
popHLZZ :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZZ h E le _ e r = UBT3(le, N E e r, h)
popHLZZ h (N lll lle llr) le lr e r = case popHLZN INCINT2(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, Z l e r, hl)
popHLZZ h (Z lll lle llr) le lr e r = case popHLZZ INCINT1(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, Z l e r, hl)
popHLZZ h (P lll lle llr) le lr e r = case popHLZP INCINT1(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, Z l e r, hl)
popHLPZ :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLPZ h E le _ e _ = UBT3(le, Z E e E, h)
popHLPZ h (N lll lle llr) le lr e r = case popHLZN INCINT2(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, P l e r, hl)
popHLPZ h (Z lll lle llr) le lr e r = case popHLZZ INCINT1(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, P l e r, hl)
popHLPZ h (P lll lle llr) le lr e r = case popHLZP INCINT1(h) lll lle llr le lr of
UBT3(e_,l,hl) -> UBT3(e_, P l e r, hl)
popHLZN :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZN h ll le lr e r = case popHLN_ h ll le lr of
UBT3(e_,l,hl) -> let t = chkLZ l e r in t `seq` UBT3(e_,t,hl)
popHLZP :: UINT -> AVL e -> e -> AVL e -> e -> AVL e -> UBT3(e,AVL e,UINT)
popHLZP h ll le lr e r = case popHLP_ h ll le lr of
UBT3(e_,l,hl) -> let t = chkLZ l e r in t `seq` UBT3(e_,t,hl)
rebalN :: AVL e -> e -> AVL e -> AVL e
rebalN _ _ E = error "rebalN: Bug0"
rebalN l e (N rl re rr) = Z (Z l e rl) re rr
rebalN l e (Z rl re rr) = P (N l e rl) re rr
rebalN _ _ (P E _ _) = error "rebalN: Bug1"
rebalN l e (P (N rll rle rlr) re rr) = Z (P l e rll) rle (Z rlr re rr)
rebalN l e (P (Z rll rle rlr) re rr) = Z (Z l e rll) rle (Z rlr re rr)
rebalN l e (P (P rll rle rlr) re rr) = Z (Z l e rll) rle (N rlr re rr)
rebalP :: AVL e -> e -> AVL e -> AVL e
rebalP E _ _ = error "rebalP: Bug0"
rebalP (P ll le lr ) e r = Z ll le (Z lr e r)
rebalP (Z ll le lr ) e r = N ll le (P lr e r)
rebalP (N _ _ E ) _ _ = error "rebalP: Bug1"
rebalP (N ll le (P lrl lre lrr)) e r = Z (Z ll le lrl) lre (N lrr e r)
rebalP (N ll le (Z lrl lre lrr)) e r = Z (Z ll le lrl) lre (Z lrr e r)
rebalP (N ll le (N lrl lre lrr)) e r = Z (P ll le lrl) lre (Z lrr e r)
chkLN :: AVL e -> e -> AVL e -> AVL e
chkLN l e r = case l of
E -> error "chkLN: Bug0"
N _ _ _ -> N l e r
Z _ _ _ -> rebalN l e r
P _ _ _ -> N l e r
chkLZ :: AVL e -> e -> AVL e -> AVL e
chkLZ l e r = case l of
E -> error "chkLZ: Bug0"
N _ _ _ -> Z l e r
Z _ _ _ -> N l e r
P _ _ _ -> Z l e r
chkLP :: AVL e -> e -> AVL e -> AVL e
chkLP l e r = case l of
E -> error "chkLP: Bug0"
N _ _ _ -> P l e r
Z _ _ _ -> Z l e r
P _ _ _ -> P l e r
chkRN :: AVL e -> e -> AVL e -> AVL e
chkRN l e r = case r of
E -> error "chkRN: Bug0"
N _ _ _ -> N l e r
Z _ _ _ -> Z l e r
P _ _ _ -> N l e r
chkRZ :: AVL e -> e -> AVL e -> AVL e
chkRZ l e r = case r of
E -> error "chkRZ: Bug0"
N _ _ _ -> Z l e r
Z _ _ _ -> P l e r
P _ _ _ -> Z l e r
chkRP :: AVL e -> e -> AVL e -> AVL e
chkRP l e r = case r of
E -> error "chkRP: Bug0"
N _ _ _ -> P l e r
Z _ _ _ -> rebalP l e r
P _ _ _ -> P l e r
subN :: AVL e -> AVL e -> AVL e
subN _ E = error "subN: Bug0"
subN l (N rl re rr) = case popLN rl re rr of UBT2(e,r_) -> chkRN l e r_
subN l (Z rl re rr) = case popLZ rl re rr of UBT2(e,r_) -> chkRN' l e r_
subN l (P rl re rr) = case popLP rl re rr of UBT2(e,r_) -> chkRN l e r_
subZR :: AVL e -> AVL e -> AVL e
subZR _ E = E
subZR l (N rl re rr) = case popLN rl re rr of UBT2(e,r_) -> chkRZ l e r_
subZR l (Z rl re rr) = case popLZ rl re rr of UBT2(e,r_) -> chkRZ' l e r_
subZR l (P rl re rr) = case popLP rl re rr of UBT2(e,r_) -> chkRZ l e r_
subZL :: AVL e -> AVL e -> AVL e
subZL E _ = E
subZL (N ll le lr) r = case popRN ll le lr of UBT2(l_,e) -> chkLZ l_ e r
subZL (Z ll le lr) r = case popRZ ll le lr of UBT2(l_,e) -> chkLZ' l_ e r
subZL (P ll le lr) r = case popRP ll le lr of UBT2(l_,e) -> chkLZ l_ e r
subP :: AVL e -> AVL e -> AVL e
subP E _ = error "subP: Bug0"
subP (N ll le lr) r = case popRN ll le lr of UBT2(l_,e) -> chkLP l_ e r
subP (Z ll le lr) r = case popRZ ll le lr of UBT2(l_,e) -> chkLP' l_ e r
subP (P ll le lr) r = case popRP ll le lr of UBT2(l_,e) -> chkLP l_ e r
chkLN' :: AVL e -> e -> AVL e -> AVL e
chkLN' l e r = case l of
E -> rebalN l e r
_ -> N l e r
chkLZ' :: AVL e -> e -> AVL e -> AVL e
chkLZ' l e r = case l of
E -> N l e r
_ -> Z l e r
chkLP' :: AVL e -> e -> AVL e -> AVL e
chkLP' l e r = case l of
E -> Z l e r
_ -> P l e r
chkRN' :: AVL e -> e -> AVL e -> AVL e
chkRN' l e r = case r of
E -> Z l e r
_ -> N l e r
chkRZ' :: AVL e -> e -> AVL e -> AVL e
chkRZ' l e r = case r of
E -> P l e r
_ -> Z l e r
chkRP' :: AVL e -> e -> AVL e -> AVL e
chkRP' l e r = case r of
E -> rebalP l e r
_ -> P l e r