Showing a colleague some things with tree's

FunWithTrees.php

<?php
/**
* 	Category Class Object ... because i dont got any definitions here
*/
class Category
{
	private $uid;
	private $parentUid;

	function __construct($uid, $parentUid)
	{
		$this->setUid($uid);
		$this->setParentUid($parentUid);
	}
	function setUid($uid) {
		$this->uid = $uid;
	}
	public function setParentUid($parentUid='')
	{
		$this->parentUid = $parentUid;
	}
	public function getUid()
	{
		return $this->uid;
	}
	public function getParentUid()
	{
		return $this->parentUid;
	}
}
/*	A Tree which holds a RootNode
*/
class Tree
{
    protected $root; // the root node of our tree
 
    public function __construct() {
        $this->root = null;
    }
 
    public function isEmpty() {
        return $this->root === null;
    }
    public function addRootNode($nodeItem) {
    	$this->root = $nodeItem;
    }
    public function toString() {
    	return $this->root->toString();
    }
}
/*	A node which holds a value and childs
*/
class Node
{
    public $value;    // contains the node item
    public $childs;
 
    public function __construct($item) {
        $this->value = $item;
        // new nodes are leaf nodes
        $this->childs = array();
    }
    public function addChild($childItem) {
    	array_push($this->childs, $childItem);
    }
    public function hasChilds() {
    	return (count($this->childs)>0) ? true : false;
    }
    public function toString() {
    	$return = "<style>.nodeValue{border: 1px solid grey;} .nodeChilds{border:1px solid grey;}</style>";
    	$return .= "<table><tr><td class='nodeValue'>";
    	if(is_string($this->value)) {	// is root
    		$return .= "CATEGORY #".$this->value."->";
    	} else {	// is normal node
    		$return .= "CATEGORY #".$this->value->getUid()."->";
    	}
    	$return .= "</td><td class='nodeChilds'>";

    	
    	foreach ($this->childs as $key => $val) {
    		$return.=$val->toString();
    	}
    	$return .= "</td></tr></table>";
    	return $return;
    }
}
/*
*	@param 	$tree = array with Category Objects
*	@return array[level][parentid][uid] = CategoryObject    (incase of level = 0 -> parentid is irrelevant and so array[0][uid] )
*/
function sortTreeArrayIntoLevels($tree) {
	$return = array();
	# sort array with parentid parameter asc (NULL<0<10<x)
	usort($tree, "cmpCategories");

	/*	Outputs the sorted tree array
	foreach ($tree as $key => $value) {
		echo $value->getUid()."->".$value->getParentUid()."<br>";
	}
	*/

	// adding level 0 nodes to array
	foreach ($tree as $key => $value) {
		$parentID = $value->getParentUid();
		if (!isset($parentID)) {
			$return[0][$value->getUid()] = $value;
			unset($tree[$key]);
		} 
	}
	// adding level 1-oo to array ... effectivly walks though all nodes and try adding them the the $return Value
	foreach ($tree as $treeKey => $treeVal) {
		if(tryFindAPlaceForChildInArray($treeVal, $return)) {
			unset($tree[$treeKey]);
		}
	}

	return $return;
}
/* tries to find the correct level for a childVal in the array (which os sorted by tree levels in first place)
*	@param $childVal: Category object to add to array
*	@param $array: (pass by reference) array to hold a tree, based on levels
*	@return bool true if adding childVal was successfull
*/
function tryFindAPlaceForChildInArray($childVal, &$array) {
	if (is_array($array)) {
		foreach ($array as $key => $value) {	// for each level
			if (is_array($value)) {
				foreach ($value as $key2 => $value2) { // for each parentitem		
					if (is_object($value2)) {
						if ($value2->getUid() == $childVal->getParentUid()) {
							$array[$key+1][$childVal->getParentUid()][$childVal->getUid()] = $childVal;
							return true;
						}
					} elseif (is_array($value2)) {
						foreach ($value2 as $key3 => $value3) {
							if ($value3->getUid() == $childVal->getParentUid()) {
								$array[$key+1][$childVal->getParentUid()][$childVal->getUid()] = $childVal;
								return true;
							}
						}
					}	
				}
			} else { return false; }
		}
	} else { return false; }
}

/*
* compares two category objects by there parentuid property and in second instance by uid
* @param $a CategoryObject
* @param $b CategoryObject
* @return a>b->1 && a<b->-1 && a=b=0
*/
function cmpCategories($a, $b) 
{
    $aa = $a->getParentUid();
    $bb = $b->getParentUid();
    $ua = $a->getUid();
    $ub = $b->getUid();
	if (!isset($aa)) {
		$aa=-1;
	}
	if (!isset($bb)) {
		$bb=-1;
	}

    if ($aa == $bb) {
    	if($ua == $ub) {
    		return 0;
    	}
    	return ($ua < $ub) ? -1 : 1;
    }
    return ($aa < $bb) ? -1 : 1;
}
/*
* Debugfunction
*/
function varToHtml($var='', $key='') {
    $type = gettype($var);
    $result = '';
	//add styling
      $result.= "<style>table.debug-table {
				  padding: 0;
				  margin: 0;
				  font-family: arial,tahoma,helvetica,sans-serif;
				  font-size: 11px;
				}

				td.debug-key-cell {
				  vertical-align: top;
				  padding: 3px;
				  border: 1px solid #AAAAAA;
				}

				td.debug-value-cell {
				  vertical-align: top;
				  padding: 3px;
				  border: 1px solid #AAAAAA;
				}

				div.debug-item {
				  border-bottom: 1px dotted #AAAAAA;
				}

				span.debug-label {
				  font-weight: bold;
				}</style>";
      if (in_array($type, array('object','array'))) {
        $result .= '
          <table class="debug-table">
            <tr>
              <td class="debug-key-cell"><b>'.$key.'</b><br/>Type: '.$type.'<br/>Length: '.count($var).'</td>
              <td class="debug-value-cell">';

        foreach ($var as $akey => $val) {
          $result .= varToHtml($val, $akey);
        }
        $result .= '</td></tr></table>';
      } else {
        $result .= '<div class="debug-item"><span class="debug-label">'.$key.' ('.$type.'): </span><span class="debug-value">'.$var.'</span></div>';
      }


      return $result;
    }

/*	converts level sorted array into a tree object
*	@param $array array holding a tree, sorted by levels in the first place
*	@return Tree Object
*/
function levelSortedArrayToTreeObject($array) {
	$tree = new Tree();
	$rootNode = new Node("rootNode");
	$tree->addRootNode($rootNode);

	foreach ($array[0] as $key => $value) {
		$child = new Node($value);
		addChildtoNodeRecursivly($rootNode, $child, $array, 1);
	}
	return $tree;
}
/*	Adds a $child to a $node and recursivly all childs of $child which are in tree
*	$level is only a parameter needed for recursion through the levels of $tree
*/
function addChildtoNodeRecursivly($node,$child,$tree,$level) {
	if(array_key_exists($level, $tree)) {
		if(array_key_exists($child->value->getUid(), $tree[$level])) {
			//if (is_array($tree[$level][$child->value->getUid()])) {
				if ($tree[$level][$child->value->getUid()]>0) {
					foreach ($tree[$level][$child->value->getUid()] as $key => $value) {
						addChildtoNodeRecursivly($child, new Node($value), $tree, $level+1);
					}
				}
			//}
		}
	}
	$node->addChild($child);
}

$testValues = array(
	'0' => new Category(0, NULL),
	'1' => new Category(1, NULL),
	'2' => new Category(2, NULL),
	'3' => new Category(3, 0),
	'4' => new Category(4, 0),
	'5' => new Category(5, 1),
	'6' => new Category(6, 2),
	'7' => new Category(7, 6),
	'8' => new Category(8, 1),
	'9' => new Category(9, NULL),
	'10' => new Category(10, 7),
	'11' => new Category(11, 8),
	'12' => new Category(12, 2),
	'13' => new Category(13, 11),
	'14' => new Category(14, 2),
	'15' => new Category(15, 8),
	'16' => new Category(16, 8),
	'17' => new Category(17, 13),
	'18' => new Category(18, 13)

);

$result = array();
// Sort the $test Data into the $result based on the level of a item in the tree (represented impicitly by the category objects)
$result = sortTreeArrayIntoLevels($testValues);
// Sorts the level sorted array into a sleek object
// also after sorting it will be outputed for debugging purpose (and showing how to handle such recursion) 
echo levelSortedArrayToTreeObject($result)->toString();
// only for debugging, echo the Array sorted by levels
echo varToHtml($result);