#!/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";
}
|
Download
