module Data.Tree.AVL.Height
(
height,addHeight,compareHeight,
) where
import Data.Tree.AVL.Types(AVL(..))
#ifdef __GLASGOW_HASKELL__
import GHC.Base
#include "ghcdefs.h"
#else
#include "h98defs.h"
#endif
height :: AVL e -> UINT
height t = addHeight L(0) t
addHeight :: UINT -> AVL e -> UINT
addHeight h E = h
addHeight h (N l _ _) = addHeight INCINT2(h) l
addHeight h (Z l _ _) = addHeight INCINT1(h) l
addHeight h (P _ _ r) = addHeight INCINT2(h) r
compareHeight :: AVL a -> AVL b -> Ordering
compareHeight = ch L(0) where
ch :: UINT -> AVL a -> AVL b -> Ordering
ch d E E = COMPAREUINT d L(0)
ch d E (N l1 _ _ ) = chA DECINT2(d) l1
ch d E (Z l1 _ _ ) = chA DECINT1(d) l1
ch d E (P _ _ r1) = chA DECINT2(d) r1
ch d (N l0 _ _ ) E = chB INCINT2(d) l0
ch d (N l0 _ _ ) (N l1 _ _ ) = ch d l0 l1
ch d (N l0 _ _ ) (Z l1 _ _ ) = ch INCINT1(d) l0 l1
ch d (N l0 _ _ ) (P _ _ r1) = ch d l0 r1
ch d (Z l0 _ _ ) E = chB INCINT1(d) l0
ch d (Z l0 _ _ ) (N l1 _ _ ) = ch DECINT1(d) l0 l1
ch d (Z l0 _ _ ) (Z l1 _ _ ) = ch d l0 l1
ch d (Z l0 _ _ ) (P _ _ r1) = ch DECINT1(d) l0 r1
ch d (P _ _ r0) E = chB INCINT2(d) r0
ch d (P _ _ r0) (N l1 _ _ ) = ch d r0 l1
ch d (P _ _ r0) (Z l1 _ _ ) = ch INCINT1(d) r0 l1
ch d (P _ _ r0) (P _ _ r1) = ch d r0 r1
chA d tB = case COMPAREUINT d L(0) of
LT -> LT
EQ -> case tB of
E -> EQ
_ -> LT
GT -> case tB of
E -> GT
N l _ _ -> chA DECINT2(d) l
Z l _ _ -> chA DECINT1(d) l
P _ _ r -> chA DECINT2(d) r
chB d tA = case COMPAREUINT d L(0) of
GT -> GT
EQ -> case tA of
E -> EQ
_ -> GT
LT -> case tA of
E -> LT
N l _ _ -> chB INCINT2(d) l
Z l _ _ -> chB INCINT1(d) l
P _ _ r -> chB INCINT2(d) r