This week the Binary Search Tree has been altered to find more than one object and also to allow the Binary Search Tree to be iterated through as if it was an array (so now it can be used in a foreach loop). This uses the built in PHP ArrayIterator, if you would like your own iterator that is included at the very bottom of the page and is named MyIterator.php
Today were goin to start with a little concrete class myBST that extends the binarySearchTree class and defines what is equal and what is, then a PHP_UNIT testing class to test the Binary Search Tree and finally the revised Binary Search Tree code. I have not altered the Binary Search Tree Node class, so I have not included it's code today.
myBST
<?php
/**
* Description
*
* PHP Version 5
*
* @package PHPEssentials
* @subpackage tree
*/
/**
* A concrete BST to test with
*/
class myBST extends binarySearchTree
{
protected function equalTo($prop1, $prop2)
{
return $prop1->me == $prop2->me;
}
protected function greaterThan($prop1, $prop2)
{
return $prop1->me > $prop2->me;
}
}
Binary Search Tree Test w/ PHP_UNIT
<?php
require_once "binarySearchTreeNode.php";
require_once "binarySearchTree.php";
require_once "myBST.php";
/**
* Class to Unit Test the myBST class (extends the binarySearchTree class)
*
* @package PHPEssentials
* @subpackage UnitTests
*/
class bstTEST extends PHPUnit_Framework_TestCase {
/**
* Created a data set to be tested
*
* @return myBST
*/
public function testInsertionSuccess()
{
$bst = new myBST();
//expect the newly created object to be empty
$this->assertEquals(0, $bst->length());
//add item
$item = new stdclass;
$item->me = 5;
$bst->insert($item);
$this->assertEquals(1, $bst->length());
//add greater item
$item = new stdclass;
$item->me = 6;
$bst->insert($item);
$this->assertEquals(2, $bst->length());
//add equal item
$item = new stdclass;
$item->me = 6;
$bst->insert($item);
$this->assertEquals(3, $bst->length());
//add lesser & equal
$item = new stdclass;
$item->me = 5;
$bst->insert($item);
$this->assertEquals(4, $bst->length());
//add lesser
$item = new stdclass;
$item->me = 1;
$bst->insert($item);
$this->assertEquals(5, $bst->length());
return $bst;
}
/**
* Will attempt to find one or more objects
*
* @param myBST $tree the tree to be searched
*
* @depends testInsertionSuccess
*/
public function testFindObjectSuccess($tree)
{
$item = new stdclass;
$item->me = 6;
$results = $tree->find($item);
$this->assertEquals(2, count($results));
}
/**
* Will attempt to find an object that has been added
*
* @param myBST $tree the tree to be searched
*
* @depends testInsertionSuccess
*/
public function testFindOneObjectByPropertySuccess($tree)
{
$this->assertInstanceOf("stdclass", $tree->findOneByProperty("me", 1));
}
/**
* Will attempt to find an object that has not been added
*
* @param myBST $tree
*
* @depends testInsertionSuccess
*/
public function testFindOneObjectByPropertyFail($tree)
{
$this->assertFalse($tree->findOneByProperty("me", 7));
}
}
Altered Binary Search Tree class
<?php
/**
* @package PHPEssentials
* @subpackage tree
*/
/**
* A binary search tree.
*
* A binary search tree that saves <= to the left and > to the right. The class
* is abstract because it requires the usage of a greater than function that
* will depend on the object
*
* @package PHPEssentials
* @subpackage tree
* @uses binarySearchTreeNode
*/
abstract class binarySearchTree implements IteratorAggregate
{
/**
* functions that return by reference report to the error log
* if a value is passed that is not a variable, this avoids that
*/
private $nullGuard = false;
/**
* The starting binarySearchTreeNode
*/
private $head = null;
public function __construct()
{
$this->head = null;
$this->parent = null;
$this->child = null;
}
/**
* A function created by the user, used to decide if a node has equal data
*/
abstract protected function equalTo($prop1, $prop2);
/**
* A function created by the user, used to decide if a node goes right
*/
abstract protected function greaterThan($prop1, $prop2);
/**
* inserts the given node
*
* @param binarySearchTreeNode $node
*
* @return bool
*/
public function insert(&$item)
{
//make sure there is something to save
if ( isset($item) ) {
$node = new binarySearchTreeNode($item);
//if the list is empty then add as head
if (!isset($this->head)) {
$this->head = $node;
return true;
}
//call recursive function to add the node
return $this->add($node, $this->head);
}
return false;
}
/**
* recursive function to add new nodes
*
* @param binarySearchTreeNode $newNode The node to be added
* @param binarySearchTreeNode $checkNode The current node being navigated
*
* @return bool
*/
protected function add(&$newNode, &$checkNode)
{
//check that there are values to work with
if (isset($newNode) && isset($checkNode)) {
//if the new item is greater than, add it to the right
if ( $this->greaterThan($newNode->getItem(), $checkNode->getItem()) ) {
//if the right is empty, add on
if ($checkNode->getRight() == NULL) {
$checkNode->setRight($newNode);
return true;
}
//if the right was not empty add to the right
return $this->add($newNode, $checkNode->getRight());
}
//if the new item is <=, add it to the left
//if the left is empty, add on
if ($checkNode->getLeft() == NULL) {
$checkNode->setLeft($newNode);
return true;
}
//if the left was not empty add to the left
return $this->add($newNode, $checkNode->getLeft());
}
//the program made it to far
return false;
}
/**
* Searches the BST for matching items
*
* @param mixed $item The needle
*
* @uses findAux()
* @return array
*/
public function &find($item)
{
//if there is a needle and a haystack
if ( isset($item) && isset($this->head) ) {
$result = array();
$this->findAux($item, $this->head, $result);
return $result;
}
//if there is no needle, or no haystack
return $this->nullGuard;
}
protected function &findAux($item, &$current, &$results)
{
if (isset($item) && isset($current)) {
$this->findAux($item, $current->getLeft(), $results);
//if the item is in the current node
if ( $this->equalTo($current->getItem(), $item) ) {
$results[] = &$current->getItem();
}
$this->findAux($item, $current->getRight(), $results);
}
//could not find a match
return $this->nullGuard;
}
/**
* Searches the BST for a matching item
*
* @param mixed $item The needle
*
* @uses findOneAux()
* @return mixed
*/
public function &findOne($item)
{
//if there is a needle and a haystack
if ( isset($item) && isset($this->head) ) {
return $this->findOneAux($item, $this->head);
}
//if there is no needle, or no haystack
return $this->nullGuard;
}
/**
* Recursive Aux function that actually performs searches
*
* @param mixed $item The needle
* @param binarySearchTreeNode The current, but ever changing haystack
*
* @param binarySearchTreeNode
*/
protected function &findOneAux(&$item, &$current)
{
if (isset($item) && isset($current)) {
//if the item is in the current node
if ( $this->equalTo($current->getItem(), $item) ) {
return $current->getItem();
}
//see if the path is to the right
if ( $this->greaterThan($item, $current->getItem()) ) {
return $this->findOneAux($item, $current->getRight());
}
return $this->findOneAux($item, $current->getLeft());
}
//could not find a match
return $this->nullGuard;
}
/**
* Search for a object by property
*
* @param string $property The object resource to search
* @param string $needle The object resource to search for
*
* @return binarySearchTreeNode
*/
public function &findOneByProperty($property, $needle)
{
//make surethere is a property, a needle, and a haystack
if (isset($property) && isset($needle) && isset($this->head)) {
return $this->findOneByPropertyAux($property, $needle, $this->head);
}
//if there is nothing to search through or for
return $this->nullGuard;
}
/**
* Recursive Aux function that actually performs searches by property
*
* @param string $property The property of the object to be searched for
* @param mixed $needle The needle
* @param binarySearchTreeNode The current, but ever changing haystack
*
* @param mixed
*/
protected function &findOneByPropertyAux($property, $needle, &$current)
{
/* check that there is a object property to seach, a needle to search
for and a haystack */
if (isset($property) && isset($needle) && isset($current)) {
//check that the object has the property and then checks with needle
if (
$current->getItem()->$property == $needle
) {
//if this is the item being searched for
return $current->getItem();
}
//if the needle would have been added to the right, follow
if (
$needle > $current->getItem()->$property
) {
return $this->findOneByPropertyAux(
$property,
$needle,
$current->getRight()
);
}
//if the needle would have been added to the left, follow
if (
$needle <= $current->getItem()->$property
) {
return $this->findOneByPropertyAux(
$property,
$needle,
$current->getLeft()
);
}
//if it makes it here (it shouldn't) then it has failed
return $this->nullGuard;
}
//if there is nothing to search through or possibly for
return $this->nullGuard;
}
/**
* Will return the number of items in the tree
*/
public function length()
{
$i = 0;
$this->lengthAux($this->head, $i);
return $i;
}
private function lengthAux(&$node, &$count)
{
if (isset($node) && isset($count)) {
//count left
$this->lengthAux($node->getLeft(), $count);
//count item
$count++;
//count right
$this->lengthAux($node->getRight(), $count);
return true;
}
return false;
}
/**
* Prints items left to right
*/
public function toArray()
{
$results = array();
$this->toArrayAux($this->head, $results);
return $results;
}
/**
* Finds and returns results to print
*/
private function toArrayAux(&$node, &$results)
{
if (isset($node) && isset($results)) {
//add left
$this->toArrayAux($node->getLeft(), $results);
//add item
$results[] = $node->getItem();
//add right
$this->toArrayAux($node->getRight(), $results);
return true;
}
return false;
}
// Required definition of interface IteratorAggregate
public function getIterator() {
return new ArrayIterator($this->toArray());
}
}
The custom iterator (replace "return new ArrayIterator" with "return new MyIterator" in the Binary Search Tree class
<?php
class MyIterator implements Iterator
{
private $var = array();
public function __construct($array)
{
if (is_array($array)) {
$this->var = $array;
}
}
public function rewind()
{
reset($this->var);
}
public function current()
{
$var = current($this->var);
return $var;
}
public function key()
{
$var = key($this->var);
return $var;
}
public function next()
{
$var = next($this->var);
return $var;
}
public function valid()
{
$key = key($this->var);
$var = ($key !== NULL && $key !== FALSE);
return $var;
}
}
