Closure tree implementation

TreeNode.php

<?php


/**
 * Class for smart browsing of recursive structures
 *
 * example:
 * {var $node = $rootNode}
 * <ul>
 * {block #groups}
 * 	<li n:foreach="$node->getChildren() as $node">
 * 		<div>{$node->name}</div>
 *		<ul n:if="$node->hasChildren()">
 *			{include #groups, node => $node}
 *		</ul>
 * 	</li>
 * {/block}
 * </ul>
 *
 * @author Pavel Zbytovský <[email protected]>
 * @copyright (c) 2013 under CC-BY-SA
 */
class TreeNode extends \Nette\Object
{
	private $nodesByParent;
	private $data;
	public $level;

	/**
	 * Constructor
	 *
	 * @param ArrayAccess $data     current node-data
	 * @param array $nodesByParent	needs sub-items indexed by parent-id
	 * @throws \Nette\InvalidStateException
	 */
	public function __construct($data, array $nodesByParent)
	{
		if(!isset($data['id'])){
			throw new \Nette\InvalidStateException("TreeNode data need 'id' item!");
		}

		$this->data = (array)$data;
		$this->nodesByParent = $nodesByParent;
	}

	/**
	 * Returns node-data item
	 *
	 * @param string $name
	 * @return mixed
	 */
	public function &__get($name)
	{
		if(isset($this->data[$name])) {
			return $this->data[$name];
		}
		return parent::__get($name);
	}

	/**
	 * Checks if current node has children
	 *
	 * @return bool
	 */
	public function hasChildren()
	{
		return isset($this->nodesByParent[$this->id]);
	}


	/**
	 * Returns children of current node
	 *
	 * @return \Projectisimo\Models\TreeNode
	 */
	public function getChildren()
	{
		$results = array();
		if ($this->hasChildren()) {
			foreach($this->nodesByParent[$this->id] as $row) {
				$results[] = new TreeNode($row, $this->nodesByParent);
			}
		}
		return $results;
	}


	/**
	 * Returns all descendants with correct level set (DFS algorithm)
	 *
	 * @param int $maxDepth
	 * @return array of TreeNodes
	 */
	public function getDescendantsFlat($maxDepth = 100)
	{
		$this->level = 0;
		$flatResult = array();
		$stack = array($this); //process own children

		while( ($parent = array_pop($stack)) ){ //recursion using stack
			if($parent != $this)
				$flatResult[] = $parent;

			if($parent->level >= $maxDepth) break;

			$children = $parent->getChildren();
			foreach(array_reverse($children) as $child){
				$child->level = $parent->level + 1;
				$stack[] = $child;
			}
		}

		return $flatResult;
	}

	/**
	 * Returns pairs useful for selectboxes
	 *
	 * @param int $maxDepth
	 * @return array of id=>name
	 */
	public function getDescendantsFlatPairs($maxDepth = 100){
		$flat = $this->getDescendantsFlat($maxDepth);
		$result = array();
		foreach($flat as $n){
			$result[$n->id] = $n->padding . $n->name;
		}
		return $result;
	}

	/**
	 * Gets level padding
	 */
	public function getPadding($separator = "&nbsp;&nbsp;&nbsp;")
	{
		return ($separator ? str_repeat($separator, $this->level - 1) : '');
	}

}

Usage.php

<?php

class Model
{

	/**
	 * Returns virtual root as TreeNode for easy ul-li displaying
	 *
	 * @return \TreeNode
	 */
	public function getRootNode($user = NULL)
	{
		$query = $this->db->query("
			SELECT *, COUNT(DISTINCT u2u.ancestor) AS count
			FROM data d
			LEFT JOIN user2user u2u
				ON d.id = u2u.group
				%if",$user," AND u2u.descendant = %i",$user," AND u2u.descendant != u2u.ancestor %end
			GROUP BY d.id
			ORDER BY name");
		$nodesByParent = $query->fetchAssoc('parent[]');
		$virtualRoot = array(
			'id' => 0,
			'parent' => -1,
			'name' => 'virtual root'
		);
		return new TreeNode($virtualRoot, $nodesByParent); //virtual super root
	}
}