-- |
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
--
-- 'AVL' tree related test and verification utilities.
module Data.Tree.AVL.Test.Utils
        (-- * Correctness checking.
         isBalanced,isSorted,isSortedOK,
         -- * Tree parameter utilities.
         minElements,maxElements,
        ) where

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

import GHC.Base
#include "ghcdefs.h"

-- | Verify that a tree is height balanced and that the BF of each node is correct.
--
-- Complexity: O(n)
isBalanced :: AVL e -> Bool
isBalanced :: forall e. AVL e -> Bool
isBalanced AVL e
t = Bool -> Bool
not (Int# -> Bool
isTrue# (AVL e -> Int#
forall e. AVL e -> Int#
cH AVL e
t Int# -> Int# -> Int#
EQL L(-1)))

-- Local utility, returns height if balanced, -1 if not
cH :: AVL e -> UINT
cH :: forall e. AVL e -> Int#
cH  AVL e
E        = L(0)
cH (N AVL e
l e
_ AVL e
r) = Int# -> AVL e -> AVL e -> Int#
forall e. Int# -> AVL e -> AVL e -> Int#
cH_ L(1AVL e
) AVL e
l r -- (hr-hl) = 1
cH (Z AVL e
l e
_ AVL e
r) = Int# -> AVL e -> AVL e -> Int#
forall e. Int# -> AVL e -> AVL e -> Int#
cH_ L(0AVL e
) AVL e
l r -- (hr-hl) = 0
cH (P AVL e
l e
_ AVL e
r) = Int# -> AVL e -> AVL e -> Int#
forall e. Int# -> AVL e -> AVL e -> Int#
cH_ L(1AVL e
) AVL e
r l -- (hl-hr) = 1
cH_ :: UINT -> AVL e -> AVL e -> UINT
cH_ :: forall e. Int# -> AVL e -> AVL e -> Int#
cH_ Int#
delta AVL e
l AVL e
r = let hl :: Int#
hl = AVL e -> Int#
forall e. AVL e -> Int#
cH AVL e
l
                in if Int# -> Bool
isTrue# (Int#
hl Int# -> Int# -> Int#
EQL L(-1)) then hl
                                   else let hr :: Int#
hr = AVL e -> Int#
forall e. AVL e -> Int#
cH AVL e
r
                                        in if Int# -> Bool
isTrue# (Int#
hr Int# -> Int# -> Int#
EQL L(-1)) then hr
                                                           else if Int# -> Bool
isTrue# (SUBINT(hr,hl) EQL delta) then INCINT1(hr)
                                                                                           else L(-1)

-- | Verify that a tree is sorted.
--
-- Complexity: O(n)
isSorted :: (e -> e -> Ordering) -> AVL e -> Bool
isSorted :: forall e. (e -> e -> Ordering) -> AVL e -> Bool
isSorted  e -> e -> Ordering
c = AVL e -> Bool
isSorted' where
 isSorted' :: AVL e -> Bool
isSorted'  AVL e
E        = Bool
True
 isSorted' (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Bool
isSorted'' AVL e
l e
e AVL e
r
 isSorted' (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Bool
isSorted'' AVL e
l e
e AVL e
r
 isSorted' (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Bool
isSorted'' AVL e
l e
e AVL e
r
 isSorted'' :: AVL e -> e -> AVL e -> Bool
isSorted''   AVL e
l e
e AVL e
r  = (AVL e -> e -> Bool
isSortedU AVL e
l e
e) Bool -> Bool -> Bool
&& (e -> AVL e -> Bool
isSortedL e
e AVL e
r)
 -- Verify tree is sorted and rightmost element is less than an upper limit (ul)
 isSortedU :: AVL e -> e -> Bool
isSortedU  AVL e
E        e
_  = Bool
True
 isSortedU (N AVL e
l e
e AVL e
r) e
ul = AVL e -> e -> AVL e -> e -> Bool
isSortedU' AVL e
l e
e AVL e
r e
ul
 isSortedU (Z AVL e
l e
e AVL e
r) e
ul = AVL e -> e -> AVL e -> e -> Bool
isSortedU' AVL e
l e
e AVL e
r e
ul
 isSortedU (P AVL e
l e
e AVL e
r) e
ul = AVL e -> e -> AVL e -> e -> Bool
isSortedU' AVL e
l e
e AVL e
r e
ul
 isSortedU' :: AVL e -> e -> AVL e -> e -> Bool
isSortedU'   AVL e
l e
e AVL e
r  e
ul = case e -> e -> Ordering
c e
e e
ul of
                          Ordering
LT -> (AVL e -> e -> Bool
isSortedU AVL e
l e
e) Bool -> Bool -> Bool
&& (e -> AVL e -> e -> Bool
isSortedLU e
e AVL e
r e
ul)
                          Ordering
_  -> Bool
False
 -- Verify tree is sorted and leftmost element is greater than a lower limit (ll)
 isSortedL :: e -> AVL e -> Bool
isSortedL  e
_   AVL e
E        = Bool
True
 isSortedL  e
ll (N AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> Bool
isSortedL' e
ll AVL e
l e
e AVL e
r
 isSortedL  e
ll (Z AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> Bool
isSortedL' e
ll AVL e
l e
e AVL e
r
 isSortedL  e
ll (P AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> Bool
isSortedL' e
ll AVL e
l e
e AVL e
r
 isSortedL' :: e -> AVL e -> e -> AVL e -> Bool
isSortedL' e
ll    AVL e
l e
e AVL e
r  = case e -> e -> Ordering
c e
e e
ll of
                           Ordering
GT -> (e -> AVL e -> e -> Bool
isSortedLU e
ll AVL e
l e
e) Bool -> Bool -> Bool
&& (e -> AVL e -> Bool
isSortedL e
e AVL e
r)
                           Ordering
_  -> Bool
False
 -- Verify tree is sorted and leftmost element is greater than a lower limit (ll)
 -- and rightmost element is less than an upper limit (ul)
 isSortedLU :: e -> AVL e -> e -> Bool
isSortedLU  e
_   AVL e
E        e
_  = Bool
True
 isSortedLU  e
ll (N AVL e
l e
e AVL e
r) e
ul = e -> AVL e -> e -> AVL e -> e -> Bool
isSortedLU' e
ll AVL e
l e
e AVL e
r e
ul
 isSortedLU  e
ll (Z AVL e
l e
e AVL e
r) e
ul = e -> AVL e -> e -> AVL e -> e -> Bool
isSortedLU' e
ll AVL e
l e
e AVL e
r e
ul
 isSortedLU  e
ll (P AVL e
l e
e AVL e
r) e
ul = e -> AVL e -> e -> AVL e -> e -> Bool
isSortedLU' e
ll AVL e
l e
e AVL e
r e
ul
 isSortedLU' :: e -> AVL e -> e -> AVL e -> e -> Bool
isSortedLU' e
ll    AVL e
l e
e AVL e
r  e
ul = case e -> e -> Ordering
c e
e e
ll of
                               Ordering
GT -> case e -> e -> Ordering
c e
e e
ul of
                                     Ordering
LT -> (e -> AVL e -> e -> Bool
isSortedLU e
ll AVL e
l e
e) Bool -> Bool -> Bool
&& (e -> AVL e -> e -> Bool
isSortedLU e
e AVL e
r e
ul)
                                     Ordering
_  -> Bool
False
                               Ordering
_  -> Bool
False
-- isSorted ends --
-------------------

-- | Verify that a tree is sorted, height balanced and the BF of each node is correct.
--
-- Complexity: O(n)
isSortedOK :: (e -> e -> Ordering) -> AVL e -> Bool
isSortedOK :: forall e. (e -> e -> Ordering) -> AVL e -> Bool
isSortedOK e -> e -> Ordering
c AVL e
t = (AVL e -> Bool
forall e. AVL e -> Bool
isBalanced AVL e
t) Bool -> Bool -> Bool
&& ((e -> e -> Ordering) -> AVL e -> Bool
forall e. (e -> e -> Ordering) -> AVL e -> Bool
isSorted e -> e -> Ordering
c AVL e
t)

-- | Detetermine the minimum number of elements in an AVL tree of given height.
-- This function satisfies this recurrence relation..
--
-- @
-- minElements 0 = 0
-- minElements 1 = 1
-- minElements h = 1 + minElements (h-1) + minElements (h-2)
--            -- = Some weird expression involving the golden ratio
-- @
minElements :: Int -> Integer
minElements :: Int -> Integer
minElements Int
0 = Integer
0
minElements Int
1 = Integer
1
minElements Int
h = Integer -> Integer -> Int -> Integer
forall {t} {t}. (Eq t, Num t, Num t) => t -> t -> t -> t
minElements' Integer
0 Integer
1 Int
h where
 minElements' :: t -> t -> t -> t
minElements' t
n1 t
n2 t
2 = t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
n1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
n2
 minElements' t
n1 t
n2 t
m = t -> t -> t -> t
minElements' t
n2 (t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
n1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
n2) (t
mt -> t -> t
forall a. Num a => a -> a -> a
-t
1)

-- | Detetermine the maximum number of elements in an AVL tree of given height.
-- This function satisfies this recurrence relation..
--
-- @
-- maxElements 0 = 0
-- maxElements h = 1 + 2 * maxElements (h-1) -- = 2^h-1
-- @
maxElements :: Int -> Integer
maxElements :: Int -> Integer
maxElements Int
0 = Integer
0
maxElements Int
h = Integer -> Int -> Integer
forall {t} {t}. (Eq t, Num t, Num t) => t -> t -> t
maxElements' Integer
0 Int
h where
 maxElements' :: t -> t -> t
maxElements' t
n1 t
1 = t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
2t -> t -> t
forall a. Num a => a -> a -> a
*t
n1
 maxElements' t
n1 t
m = t -> t -> t
maxElements' (t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
2t -> t -> t
forall a. Num a => a -> a -> a
*t
n1) (t
mt -> t -> t
forall a. Num a => a -> a -> a
-t
1)