Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Test.Utils
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Contents
Correctness checking.
Test data generation.
Exhaustive tests.
Tree parameter utilities.
Testing BinPath module.
Description
AVL tree related test and verification utilities. The functions defined here are not exported by the main Data.Tree.AVL module. You need to import this module explicitly if you want to use any of them.
Synopsis
isBalanced :: AVL e -> Bool
checkHeight :: AVL e -> Maybe Int
isSorted :: (e -> e -> Ordering) -> AVL e -> Bool
isSortedOK :: (e -> e -> Ordering) -> AVL e -> Bool
type TestTrees = [(Int, [(AVL Int, Int)])]
allAVL :: TestTrees
allNonEmptyAVL :: TestTrees
numTrees :: Int -> Integer
flatAVL :: Int -> AVL Int
exhaustiveTest :: (Int -> Int -> AVL Int -> Bool) -> TestTrees -> IO ()
minElements :: Int -> Integer
maxElements :: Int -> Integer
pathTree :: AVL Int
Correctness checking.
isBalanced :: AVL e -> Bool

Verify that a tree is height balanced and that the BF of each node is correct.

Complexity: O(n)

checkHeight :: AVL e -> Maybe Int

Verify that a tree is balanced and the BF of each node is correct. Returns (Just height) if so, otherwise Nothing.

Complexity: O(n)

isSorted :: (e -> e -> Ordering) -> AVL e -> Bool

Verify that a tree is sorted.

Complexity: O(n)

isSortedOK :: (e -> e -> Ordering) -> AVL e -> Bool

Verify that a tree is sorted, height balanced and the BF of each node is correct.

Complexity: O(n)

Test data generation.
type TestTrees = [(Int, [(AVL Int, Int)])]
AVL Tree test data. Each element of a the list is a pair consisting of a height, and list of all possible sorted trees of the same height, paired with their sizes. The elements of each tree of size s are 0..s-1.
allAVL :: TestTrees
All possible sorted AVL trees.
allNonEmptyAVL :: TestTrees
Same as allAVL, but excluding the empty tree (of height 0).
numTrees :: Int -> Integer

Returns the number of possible AVL trees of a given height.

Behaves as if defined..

 numTrees h = (\(_,xs) -> length xs) (allAVL !! h)

and satisfies this recurrence relation..

 numTrees 0 = 1
 numTrees 1 = 1
 numTrees h = (2*(numTrees (h-2)) + (numTrees (h-1))) * (numTrees (h-1)) 
 
flatAVL :: Int -> AVL Int
Generates a flat AVL tree of n elements [0..n-1].
Exhaustive tests.
exhaustiveTest :: (Int -> Int -> AVL Int -> Bool) -> TestTrees -> IO ()
Apply the test function to each AVL tree in the TestTrees argument, and report progress as test proceeds. The first two arguments of the test function are tree height and size respectively.
Tree parameter utilities.
minElements :: Int -> Integer

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
 
maxElements :: Int -> Integer

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
 
Testing BinPath module.
pathTree :: AVL Int
Infinite test tree. Used for test purposes for BinPath module. Value at each node is the path to that node.
Produced by Haddock version 0.7