MySQL "Closure Table" for Kohana based on Bill Karwin design.

hierarchy.php

<?php defined('SYSPATH') or die('No direct script access.');
/**
 * MySQL "Closure Table" for Kohana based on Bill Karwin design.
 * 
 * @link  http://www.slideshare.net/billkarwin/models-for-hierarchical-data 
 * @TODO  improve
 * 
 * sql schema:
 * CREATE TABLE `closures` (
 *   `id` int(11) NOT NULL AUTO_INCREMENT,
 *   `ancestor` int(11) NOT NULL,
 *   `descendant` int(11) NOT NULL,
 *   `lvl` int(11) NOT NULL,
 *   PRIMARY KEY (`id`)
 * );
 * 
 */
class Hierarchy {

	public $table;

	public $closure_table = 'closures';

	public function __construct($table_name, $closure_table = NULL)
	{
		$this->table = $table_name;

		if ($closure_table !== NULL)
		{
			$this->closure_table = $closure_table;
		}
	}

	/**
	 * Add a node (as last child).
	 * 
	 * @param	array	data to be inserted
	 * @param	mixed	target id
	 * @return	mixed	last insert id if succeed
	 */
	public function add(array $data, $target_id = NULL)
	{
		$target_id = DB::select('id')
			->from($this->table)
			->where('id','=',$target_id)
			->execute()
			->get('id', 0);

		$last_insert_id = DB::insert($this->table, array_keys($data))
			->values($data)
			->execute();

		if ($last_insert_id AND count($last_insert_id)>0)
		{
			$last_insert_id = Arr::get($last_insert_id, 0);

			$query = DB::select(DB::expr('ancestor, '.$last_insert_id.', lvl+1'))
				->from($this->closure_table)
				->where('descendant', '=', $target_id);

			$query = 'SELECT '.$last_insert_id.','.$last_insert_id.',0 UNION ALL '.$query;
			
			$query = 'INSERT INTO '.$this->closure_table.' (ancestor, descendant,lvl) '.$query;

			$query = DB::query(Database::INSERT, $query)->execute();
			
			if ($query AND count($query)>0)
			{
				return Arr::get($query, 0);
			}
		}

		return FALSE;
	}

	/**
	 * Check if current node has children.
	 * 
	 * @param	int		node id
	 * @return	boolean
	 */
	public function has_children($node_id)
	{
		$descendants = DB::select('descendant')
			->from($this->closure_table)
			->where('ancestor','=', $node_id);

		return (bool)  DB::select(array('COUNT("*")', 'total'))
			->from($this->closure_table)
			->where('ancestor', 'IN', DB::expr('('.$descendants.')'))
			->where('descendant', '<>', $node_id)
			->execute()
			->get('total');
	}

	/**
	 * Get parent(s) of current node.
	 * 
	 * @param	int		current node id
	 * @param	mixed	level up (e.g direct parent = 1)
	 * @return	mixed	array if succeed
	 */
	public function get_parent($node_id, $level = NULL)
	{
		$query = DB::select()
			->from(array($this->table, 't'))
			->join(array($this->closure_table, 'c'))
				->on('t.id', '=', 'c.ancestor')
			->where('c.descendant', '=', $node_id)
			->where('c.ancestor', '<>', $node_id);

		if ($level)
		{
			$query->where('c.lvl' ,'<=', $level);
		}

		$query = $query->order_by('t.id')->execute();

		return $query->count() ? $query->as_array() : FALSE;
	}

	/**
	 * Fetch children(s).
	 * 
	 * Example to generate nested tree:
	 * 
	 *   $h = new Hierarchy('same table');
	 *   $data = $h->get_children(1, TRUE);
	 *   $data = $h->nestify($data);
	 *   print_r($data);
	 * 
	 * If level/depth specified then self will be ignore.
	 * 
	 * @param	mixed		node id
	 * @param	boolean		include self
	 * @param	mixed		node level/depth (e.g direct children = 1) 
	 * @return	mixed		array if query true
	 */
	public function get_children($node_id = NULL, $self = FALSE, $level = NULL)
	{
		$query = DB::select('t.*', array('c2.ancestor', 'parent'), array('c1.lvl', 'level'))
			->from(array($this->closure_table, 'c1'))
			->join(array($this->table, 't'))
				->on('t.id', '=','c1.descendant')
			->join(array($this->closure_table, 'c2'), 'LEFT')
				->on('c2.lvl', '=', DB::expr('1 AND c2.descendant = c1.descendant '))
			->where('c1.ancestor', '=', $node_id ? $node_id : 1);

		if ( ! $self)
		{
			$query->where('c1.descendant', '<>', $node_id);
		}

		if ($level)
		{
			$query->where('c1.lvl','=', $level);
		}

		$query = $query->execute();

		return $query->count() ? $query->as_array() : FALSE;
	}

	/**
	 * TODO: optional recursion
	 * 
	 * Delete node.
	 * 
	 * @param	int		node id
	 * @return	void
	 */
	public function delete($node_id)
	{
		$operand = DB::select('descendant')
			->from($this->closure_table)
			->where('ancestor', '=', $node_id);

		$query = DB::select('id','descendant')
			->from($this->closure_table)
			->where('descendant','IN', DB::expr('('.$operand.')'))
			->execute();

		if ($query->count())
		{
			$descendants = Arr::pluck($query, 'descendant');

			DB::delete($this->table)
				->where('id','IN', DB::expr('('.implode(',',$descendants).')'))
				->execute();

			$descendants = Arr::pluck($query, 'id');

			DB::delete($this->closure_table)
				->where('id','IN', DB::expr('('.implode(',',$descendants).')'))
				->execute();
		}
	}

	/**
	 * Move node with its children to another node.
	 * 
	 * @link	http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/
	 * 
	 * @param	int		node to be moved
	 * @param	int		target node
	 * @return	void
	 */
	public function move($node_id, $target_id)
	{
		// MySQL’s multi-table DELETE
		$query1 = 'DELETE a FROM '.$this->closure_table.' AS a ';
		$query1 .= 'JOIN '.$this->closure_table.' AS d ON a.descendant = d.descendant ';
		$query1 .= 'LEFT JOIN '.$this->closure_table.' AS x ';
		$query1 .= 'ON x.ancestor = d.ancestor AND x.descendant = a.ancestor ';
		$query1 .= 'WHERE d.ancestor = '.$node_id.'  AND x.ancestor IS NULL';

		DB::query(Database::DELETE, $query1)->execute();

		$query2 = 'INSERT INTO '.$this->closure_table.' (ancestor, descendant, lvl) ';
		$query2 .= 'SELECT a.ancestor, b.descendant, a.lvl+b.lvl+1 ';
		$query2 .= 'FROM '.$this->closure_table.' AS a JOIN '.$this->closure_table.' AS b ';
		$query2 .= 'WHERE b.ancestor = '.$node_id.' AND a.descendant = '.$target_id;

		DB::query(Database::INSERT, $query2)->execute();
	}

	/**
	 * Helper to nestify array.
	 *
	 * @link	http://stackoverflow.com/questions/841014/nested-sets-php-array-and-transformation/886931#886931
	 * 
	 * @param	array
	 * @param	string
	 * @return	mixed	array if succeed
	 */
	public function nestify(array $nodes, $key = 'parent')
	{
		if (count($nodes)<1)
		{
			return FALSE;
		}

		$trees = array();

		$stack = array();
		$counter = 0;

		foreach ($nodes as $node)
		{
			// Number of stack items
			$counter = count($stack);

			// Check if we're dealing with different levels
			while ($counter > 0 AND $stack[$counter - 1][$key] >= $node[$key])
			{
				array_pop($stack);
				$counter--;
			}

			// Stack not empty (we are inspecting the children)
			if ($counter > 0)
			{
				$idx = $counter - 1;

				if ( ! isset($stack[$idx]['children']))
				{
					$stack[$idx]['children'] = array();
				}

				$i = count($stack[$idx]['children']);

				$stack[$idx]['children'][$i] = $node;

				$stack[] = &$stack[$idx]['children'][$i];
			}
			else
			{
				$i = count($trees);

				$trees[$i] = $node;

				$stack[] = &$trees[$i];
			}
		}

		return $trees;
	}

}