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: 6 years ago
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";
}