<?php
/**
	PHP4 Simple Binary Search Tree Class ("stupid tree")
	@Author Greg Feigenson
	Why the hell doesn't this already exist...?

	TREENESS!
*/

class Tree 
{
	var $root = null; //root node

	function getRoot()
	{
		if ($this->isEmpty())
			return null;

		return $this->root; //r00t r00t
	}

	function addNode($node)
	{
		if ($this->isEmpty())
		
		$this->root = $node; //construct before adding please
		else
			$this->root->appendNode($node);
	}

	function deleteNode($node)
	{
		if ($this->isEmpty())
			return true;

		return $this->root->removeNode($node);
	}

	function inTree($node)
	{
		if ($this->isEmpty())
			return false;

		return ($this->root->findNode($node) != null);
	}

	function getNode($node)
	{
		if ($this->isEmpty())
			return null;

		return $this->root->findNode($node);
	}

	function isEmpty()
	{
		if ($this->root == null)
			return true;
	}
}

class BTreeNode 
{
	var $data = null;
	var $left = null;
	var $right = null;

	//CTOR
	function BTreeNode($value)
	{
		$this->data = $value;
	}

	//ToString look-a-like
	function value()
	{
		return $this->data;
	}

	function nodeCompare($node)
	{
		//are we greater than node?
		if ($this->data < $node->data)
			return 1;
		
		//equal to?
		elseif ($this->data == $node->data)
			return 0;
		
		//less than node?
		elseif ($this->data > $node->data)
			return -1;
	}

	function appendNode($node)
	{
		//smaller things go to the left
		if ($this->nodeCompare($node) < 0)
		{
			if ($this->left == null)
				$this->left = $node;
			else
				$this->left->appendNode($node);
		}

		//larger the right
		elseif ($this->nodeCompare($node) > 0)
		{
			if ($this->right == null)
				$this->right = $node;
			else
				$this->right->appendNode($node);
		}
	}

	//This will drop all sub-nodes
	function removeNode($node)
	{
		//if it's us...
		if ($this->nodeCompare($node) == 0)
		{
			//destroy children
			if ($this->left != null)
				$this->left->destroyNode();
			
			if ($this->right != null)
				$this->right->destroyNode();
			
			//self-destruct
			$this = null;
		}

		//otherwise keep going
		else
		{
			if ($this->left != null)
				$this->left->removeNode($node);
			if ($this->right != null)
				$this->right->removeNode($node);
		}
	}

	function findNode($node)
	{
		$comparison = $this->nodeCompare($node);
		
		//it's us!
		if ($comparison == 0)
			return $this;

		//look to the left
		if ($comparison < 0 && $this->left != null)
			return $this->left->findNode($node);
		
		//look to the right
		if ($comparison > 0 && $this->right != null)
			return $this->right->findNode($node);
	 
	}


	/**
		These should be private
	*/
	
	function destroyNode()
	{
		//recurse
		$this->left->destroyNode();
		$this->right->destroyNode();
		
		//References to null
		$this->left = null;
		$this->right = null;
		$this = null;
	}

	function isNull()
	{
		if ($data == null || $data == "")
			return true;

		return false;
	}
}
?>