<?php
/*
* LLRBTree is copyright � 2009. EarthWalk Software.
* Licensed under the Academic Free License version 3.0
* Refer to the file named Copyright provided with the source.
*/
/**
*
* LLRBTree (Left Leaning Red Black Tree).
*
* LLRBTree implements the bTree abstract class to create a LLRB tree container (object).
* @author Jay Wheeler.
* @version 1.0
* @copyright � 2009. EarthWalk Software.
* @license refer to Copyright file provided with the source.
* @package LLRBTree.
* @subpackage LLRBTree.
*/
class LLRBTree extends bTree
{
private $keyNode;
protected $traversal;
/**
* __construct.
*
* Class constructor.
* @return tree object
*/
public function __construct()
{
parent::__construct();
$this->keyNode = null;
$this->traversal = array();
}
/**
* __destruct.
*
* Class destructor.
* @return null
*/
public function __destruct()
{
parent::__destruct();
unset($this->keyNode);
}
/**
* search.
*
* lookup a key in the tree.
* @param $key is the key to lookup in the tree.
* @param $data is the value to store in the key-ed node.
* @param $okayToAdd = true to add unfound node, false to return null if not found.
* @return $node = pointer to the node, null if not found.
*/
public function search($key, $data=null, $okayToAdd=false)
{
$this->allocateKeynode($key, $data);
$node = $this->root;
while ($node != null)
{
switch($node->compare($this->keyNode))
{
case 0:
return $node;
case -1:
$node = $node->left();
break;
case 1:
$node = $node->right();
break;
}
}
if (! $okayToAdd)
{
return null;
}
return $this->insert($key, $data);
}
/**
* insert.
*
* insert a key node in the tree.
* @param $key is the key to add to the tree.
* @param $data is the (optional) data to add to the key node.
* @return $node = pointer to the inserted key node.
*/
public function insert($key, $data=null)
{
$this->allocateKeynode($key, $data);
$this->root = $this->insertNode($this->root, $this->keyNode);
if ($this->root != null)
{
$this->root->flag(LLRBNode::BLACK);
}
}
/**
* root.
*
* Return the current tree root.
* @return $root = current tree root.
*/
public function root()
{
return $this->root;
}
/**
* nodes.
*
* Return the number of unique nodes in the tree.
* @return $nodes = count of the unique nodes.
*/
public function nodes()
{
return $this->nodes;
}
/**
* firstNode.
*
* Return the first item in the tree (in key order).
* @return $node = the first node in the tree, null if the tree is empty.
*/
public function firstNode()
{
$this->traversal = array();
$this->current = $this->traverseBranch($this->root);
return $this->current;
}
/**
* nextNode.
*
* Return the next item in the tree (in key order).
* @return $node = the next node in the tree, null if at the tree end.
*/
public function nextNode()
{
$this->current = null;
if (count($this->traversal) > 0)
{
$this->current = array_pop($this->traversal);
if ($this->current != null)
{
if ($this->current->right() != null)
{
$this->current = $this->traverseBranch($this->current->right());
return $this->current;
}
}
if (count($this->traversal) > 0)
{
$this->current = array_pop($this->traversal);
array_push($this->traversal, $this->current);
}
else
{
$this->current = null;
}
}
return $this->current;
}
/**
* currentNode.
*
* Returns the current tree node.
* @return $current = current tree node.
*/
public function currentNode()
{
return $this->current;
}
/**
* valid.
*
* Returns the validity of the current node pointer
* @return boolean true = the current node pointer is valid.
*/
public function valid()
{
return ! is_null($this->current);
}
/**
* key.
*
* Returns the current tree node key value.
* @return $key = current tree node value.
*/
public function key()
{
return $this->current->key();
}
/**
* current.
*
* Returns the current tree node data.
* @return $current = current tree node data.
*/
public function current()
{
return $this->current->data();
}
/**
* next.
*
* Moves current to the next node in the tree in In-Order Traversal.
* @return null.
*/
public function next()
{
return $this->nextNode();
}
/**
* rewind.
*
* Moves the current node pointer to the first item in the tree.
* @return null.
*/
public function rewind()
{
$this->firstNode();
}
/**
* traverseBranch.
*
* Traverse the supplied branch to the left leaf, storing the nodes met along the way.
* Returns the first node with no left child (a left leaf).
* @param $node = root of the branch to be traversed.
* @return $node = the pointer to the left leaf found, null if none found.
*/
protected function traverseBranch($node)
{
while(($node != null) && ($node->left() != null))
{
array_push($this->traversal, $node);
$node = $node->left();
}
if ($node != null)
{
array_push($this->traversal, $node);
}
return $node;
}
/**
* insertNode.
*
* Insert the node into the tree at the proper place, then balance the tree.
* @param $node is the tree root node.
* @param $key is the key to insert.
* @param $data is the (optional) data to store in the key.
* @return $node = the inserted node
*/
protected function insertNode($node, $keyNode)
{
if ($node == null)
{
$this->nodes++;
return new LLRBNode($keyNode->key(), $keyNode->data());
}
switch($node->compare($keyNode))
{
case 0:
$node->data($data);
break;
case -1:
$node->left($this->insertNode($node->left(), $keyNode));
break;
case 1:
$node->right($this->insertNode($node->right(), $keyNode));
break;
}
return $this->fixUp($node);
}
/**
* fixUp.
*
* Balance the tree and fix up the colors on the way up the tree.
* @param $node is the tree root node.
* @param $deleting = true if deleting a node, false if inserting
* @return $node = the root node following all fixUps.
*/
protected function fixUp($node, $deleting=false)
{
if ($this->isRed($node->right()))
{
if ($deleting ||
((! $deleting) && (! $this->isRed($node->left()))))
{
$node = $this->rotateLeft($node);
}
}
if (($this->isRed($node->left())) &&
($this->isRed($node->left()->left())))
{
$node = $this->rotateRight($node);
}
if (($this->isRed($node->left())) &&
($this->isRed($node->right())))
{
$this->flipColors($node);
}
return $node;
}
/**
* isRed.
*
* Return true if the node is valid and colored red.
* @param $node = the node to check
* @return boolean result of validation (true = red).
*/
protected function isRed($node)
{
if (($node != null) && ($node->flag() == LLRBNode::RED))
{
return true;
}
return false;
}
/**
* rotateLeft.
*
* Perform a rotate left operation around the node
* @param $node = node to rotate to root.
* @return $root is the new root node
*/
protected function rotateLeft($node)
{
$root = $node->right();
$node->right($root->left());
$root->left($node);
$root->flag($node->flag());
$node->flag(LLRBNode::RED);
return $root;
}
/**
* rotateRight.
*
* Perform a rotate right operation around the node
* @param $node = node to rotate to root.
* @return $root is the new root node
*/
protected function rotateRight($node)
{
$root = $node->left();
$node->left($root->right());
$root->right($node);
$root->flag($node->flag());
$node->flag(LLRBNode::RED);
return $root;
}
/**
* flipColors.
*
* Flip the colors of the current node and its (2) children.
* @param $node = node to rotate to root.
* @return $root is the new root node
*/
protected function flipColors($node)
{
$node->flag(! $node->flag());
$child = $node->left();
$child->flag(! $child->flag());
$child = $node->right();
$child->flag(! $child->flag());
}
/**
* treeTop.
*
* Return the minimum item in the tree (the top).
* @return $node = node containing the smallest item.
*/
public function treeTop()
{
return $this->leaf($this->root);
}
/**
* leaf.
*
* Return the left leaf in the supplied branch.
* @param $node = branch to get the left leaf from
* @return $node = node containing the smallest item.
*/
public function leaf($node)
{
if ($node != null)
{
while($node->left() !== null)
{
$node = $node->left();
}
}
return $node;
}
/**
* deleteMin.
*
* Delete the smallest item in the tree.
* @return null
*/
public function deleteMin()
{
$this->root = $this->deleteMinNode($this->root);
if ($this->root != null)
{
$this->root->flag(LLRBNode::BLACK);
}
}
/**
* delete.
*
* Delete a node in the tree.
* @param $key = name of the key to delete
* @return null
*/
public function delete($key)
{
$this->allocateKeynode($key);
$this->root = $this->deleteNode($this->root, $this->keyNode);
if ($this->root != null)
{
$this->root->flag(LLRBNode::BLACK);
}
}
/**
* deleteMinNode.
*
* Delete the minimum node in the branch.
* @param $node = branch to delete minimum node in.
* @return $node = new root after deletion.
*/
protected function deleteMinNode($node)
{
if ($node->left() == null)
{
return null;
}
if ((! $this->isRed($node->left())) && (! $this->isRed($node->left()->left())))
{
$node = $this->moveRedLeft($node);
}
$node->left($this->deleteMinNode($node->left()));
if ($this->nodes > 0)
{
$this->nodes--;
}
return $this->fixUp($node, true);
}
/**
* moveRedLeft.
*
* Move the left red node.
* @param $node = node to be moved.
* @return $node is the new root.
*/
protected function moveRedLeft($node)
{
$this->flipColors($node);
if (($node->right() != null) &&
($this->isRed($node->right()->left())))
{
$node->right($this->rotateRight($node->right()));
$node = $this->rotateLeft($node);
$this->flipColors($node);
}
return $node;
}
/**
* moveRedRight.
*
* Move the right red node.
* @param $node = node to be moved.
* @return $node is the new root.
*/
protected function moveRedRight($node)
{
$this->flipColors($node);
if (($node->left() != null) && ($this->isRed($node->left()->left())))
{
$node = $this->rotateRight($node);
$this->flipColors($node);
}
return $node;
}
/**
* deleteNode.
*
* Delete a node in the tree.
* @param $node = node to delete.
* @param $keyNode = node containing the name of the key to delete
* @return null
*/
protected function deleteNode($node, $keyNode)
{
if ($node->compare($keyNode) < 0)
{
if ((! $this->isRed($node->left())) &&
(! $this->isRed($node->left()->left())))
{
$node = $this->moveRedLeft($node);
}
$node->left($this->deleteNode($node->left(), $keyNode));
}
else
{
if ($this->isRed($node->left()))
{
$node = $this->rotateRight($node);
}
if (($node->compare($keyNode) == 0) && ($node->right() == null))
{
return null;
}
if ((! $this->isRed($node->right())) &&
(($node->right() != null) && (! $this->isRed($node->right()->left()))))
{
$node = $this->moveRedRight($node);
}
if ($node->compare($keyNode) == 0)
{
$leafNode = $this->leaf($node->right());
$node->data($leafNode->data());
$node->key($leafNode->key());
$node->right($this->deleteMinNode($node->right()));
}
else
{
$node->right($this->deleteNode($node->right(), $keyNode));
}
}
if ($this->nodes > 0)
{
$this->nodes--;
}
return $this->fixUp($node, true);
}
/**
* allocateKeynode.
*
* Create a new class keynode if none exists. Add key and data to the keynode.
* @param $key
* @param $data
* @return none
*/
protected function allocateKeynode($key, $data=null)
{
if ($this->keyNode == null)
{
$this->keyNode = new LLRBNode($key, $data);
}
else
{
$this->keyNode->key($key);
$this->keyNode->data($data);
}
}
}