Login   Register  
PHP Classes
elePHPant
Icontem

File: testLLRBTree.php

Recommend this page to a friend!
Stumble It! Stumble It! Bookmark in del.icio.us Bookmark in del.icio.us
  Classes of Jay Wheeler  >  LLRB Tree  >  testLLRBTree.php  >  Download  
File: testLLRBTree.php
Role: Example script
Content type: text/plain
Description: A test application to prove the correct operation of the LLRB tree
Class: LLRB Tree
Manage a balanced tree of text word nodes
Author: By
Last change: Changed to test application
Date: 2009-07-16 10:48
Size: 2,766 bytes
 

Contents

Class file image Download
#!/usr/bin/php
<?php

/*
 *         testLLRBTree is copyright � 2009. EarthWalk Software.
 *         Licensed under the Academic Free License version 3.0
 *      Refer to the file named Copyright provided with the source.
 */
/**
 * 
 * testLLRBTree.
 * 
 * Sample application to test the LLRBTree classes.
 * @author Jay Wheeler.
 * @version 1.0
 * @copyright � 2009. EarthWalk Software.
 * @license refer to Copyright file provided with the source.
 * @package LLRBTree.
 * @subpackage testLLRBTree.
 */
require 'iComparable.php';

require 'bTree.php';
require 'bNode.php';

require 'LLRBTree.php';
require 'LLRBNode.php';

$words = array('cat',      'animal',  'donkey', 
               'bear',     'bat',     'dog', 
               'elephant', 'gazelle', 'llama',
               'zebra',    'horse',   'ferret', 
               'wombat');

$orderedWords = array('animal',   'bat',    'bear',
                         'cat',      'dog',    'donkey',
                      'elephant', 'ferret', 'gazelle',
                         'horse',    'llama',  'wombat',
                        'zebra');

$deleteWords =array('elephant', 'gazelle', 'animal',
                    'horse',    'wombat',  'cat',
                    'zebra',    'ferret',  'donkey',
                    'bat',      'llama',   'dog',
                    'bear');

$tree = new LLRBTree();
$wordnumber = 0;
foreach($words as $word)
{
    $tree->insert($word, ++$wordnumber);
    printLine(sprintf("inserted: %s, root = %s", $word, $tree->root()->key()));
    printTree($tree);
}

$minNode = $tree->treeTop();
printLine("**************************");
printLine(sprintf('minimum = %s', $minNode->key()));
printLine("**************************");

foreach($deleteWords as $word)
{
    $tree->delete($word);
    printLine(sprintf("deleted: %s, root = %s", $word, (($tree->root() != null) ? $tree->root()->key() : 'null')));
    printTree($tree);
}

$wordnumber = 0;
foreach($orderedWords as $word)
{
    $tree->insert($word, ++$wordnumber);
    printLine(sprintf("inserted: %s, root = %s", $word, $tree->root()->key()));
    printTree($tree);
}

exit(0);

function printTree($tree)
{
    $nodenumber = 0;
    foreach($tree as $key => $data)
    {
        $node = $tree->currentNode();
        $nodenumber++;
        printLine(sprintf("\t% 2u - %s = %s, left = %s, right = %s, flag = %s", 
                          $nodenumber,
                          $key,
                          $data,
                          (($node->left() === null) ? 'null' : $node->left()->key()),
                          (($node->right() === null) ? 'null' : $node->right()->key()),
                          ($node->flag() ? 'RED' : 'BLACK')));
    }

    printLine("**************************");
}

function printLine($buffer)
{
    print $buffer . "\n";
}