<?php

/**
 * Work with a mptt tree. Based on the insert/delete procedures found at: 
 * http://www.developer.com/db/article.php/10920_3517366_2
 * @author Peter Goodman
 * @copyright Copyright 2007 Peter Goodman, all rights reserved.
 */
class NestedSet {
	
	/**
	 * Database link resource.
	 * @internal
	 */
	private $conn;
	
	/**
	 * Databse table configurations.
	 * @internal
	 */
	private $db_table,
			$db_left_id,
			$db_right_id,
			$db_primary_id;
	
	/**
	 * Constructor, bring in the database connection.
	 */
	public function __construct($conn_id) {
		if(!$conn_id || !is_resource($conn_id)) {
			throw new Exception("NestedSet::__construct expects first parameter passed to be a database resource.");
		}
		
		$this->conn = $conn_id;
	}
	
	/**
	 * Configure the NestedSet class.
	 */
	public function configure($table, $left, $right, $id) {
		$this->db_table = $table;
		$this->db_left_id = $left;
		$this->db_right_id = $right;
		$this->db_primary_id = $id;
		
		// debug
		$this->db_query("TRUNCATE TABLE {$this->db_table}");
	}
	
	/**
	 * Query the database.
	 * @internal
	 */
	private function db_query($sql, $multi_rows = FALSE) {
		$res = mysql_query($sql, $this->conn);
		
		if(!$res || !is_resource($res)) {
			return FALSE;
		}
		
		if(($num_rows = mysql_num_rows($res)) > 0) {
			if($num_rows == 1 || !$multi_rows) {
				$rows = mysql_fetch_array($res, MYSQL_NUM);
			} else {
				$rows = array();
				while($row = mysql_fetch_array($res, MYSQL_NUM)) {
					$rows[] = $row;
				}
			}
			
			mysql_free_result($res);
			
			return $rows;
		}
		
		return FALSE;
	}
	
	/**
	 * Get the last insert ID from the database.
	 * @internal
	 */
	private function db_insert_id() {
		return mysql_insert_id($this->conn);
	}
	
	/**
	 * Insert a node onto the NestedSet tree given the primary key of
	 * its parent. If zero is supplied, this will be a top-level node.
	 * @param int $parent_id The node to add this node to or 0 to make this a top-level node.
	 * @return mixed It will return the database insert ID on success or FALSE on failure.
	 */
	public function insert($parent_id = 0) {
		
		$parent_level;
		
		// are we adding a top-level node?
		if((int)$parent_id === 0) {
			
			// default top-level parent_level, assume that this is the first
			// node going into the tree
			$parent_level = 1;
			
			// top level element, needs the + 1
			if(FALSE !== ($row = $this->db_query("SELECT {$this->db_right_id} FROM {$this->db_table} ORDER BY {$this->db_right_id} DESC LIMIT 1"))) {
				$parent_level = (int)$row[0] + 1;
			}
		
		// sub-level node
		} else {
			
			// sub-level element
			if(FALSE !== ($row = $this->db_query("SELECT {$this->db_right_id} FROM {$this->db_table} WHERE {$this->db_primary_id}={$parent_id}"))) {
				$parent_level = (int)$row[0];
			
			// error!
			} else {
				return FALSE;
			}
		}
		
		// allocate enough space for this node to fit in
		$this->allocate_space(2, $parent_level);
		
		// insert the new node
		$sql = "INSERT INTO {$this->db_table} ({$this->db_left_id},{$this->db_right_id})";
		$sql .= "VALUES({$parent_level}, ({$parent_level} + 1));";
		$this->db_query($sql);
		
		// return the insert ID
		if(FALSE !== ($id = $this->db_insert_id())) {
			return $id;
		}
		
		// whoops, problem.
		return FALSE;		
	}
	
	/**
	 * Allocate space for node(s).
	 * @internal
	 */
	private function allocate_space($num_nodes_time_two, $parent_level) {
		
		// update the left ids to allocate space
		$sql = "UPDATE {$this->db_table} ";
		$sql .= "SET {$this->db_left_id} = CASE WHEN {$this->db_left_id} > {$parent_level} THEN ";
		$sql .= "		{$this->db_left_id} + {$num_nodes_time_two} ";
		$sql .= "	ELSE ";
		$sql .= "		{$this->db_left_id} ";
		$sql .= "	END ";
		$sql .= "WHERE {$this->db_right_id} >= {$parent_level};";
		$this->db_query($sql);
		
		// update the right ids to allocate space
		$sql = "UPDATE {$this->db_table} ";
		$sql .= "SET {$this->db_right_id} = CASE WHEN {$this->db_right_id} >= {$parent_level} THEN";
		$sql .= "		{$this->db_right_id} + {$num_nodes_time_two} ";
		$sql .= "	ELSE";
		$sql .= "		{$this->db_right_id} ";
		$sql .= "	END ";
		$sql .= "WHERE {$this->db_right_id} >= {$parent_level};";
		$this->db_query($sql);
	}
	
	/**
	 * Delete a node on the NestedSet tree by the value of its primary key.
	 * @param int $id The value of the primary key of the node to delete.
	 * @param bool $delete_children Boolean of whether to remove all of the nodes children as well.
	 * @return bool
	 */
	public function delete($id = 0, $delete_children = TRUE) {
			
		// get the node
		$sql = "SELECT {$this->db_left_id}, {$this->db_right_id} FROM {$this->db_table} WHERE {$this->db_primary_id}={$id};";
		
		@list($deleted_left, $deleted_right) = $this->db_query($sql);
		
		// whoops, this isn't good! Must be nothing to delete
		if(empty($deleted_left) || empty($deleted_right)) {
			return FALSE;
		}
		
		// delete the node and all nodes under it
		if($delete_children) {
			$sql = "DELETE FROM {$this->db_table} WHERE {$this->db_left_id} BETWEEN {$deleted_left} AND {$deleted_right};";
			$this->db_query($sql);		
		
			// update the left ids
			$sql = "UPDATE {$this->db_table} SET ";
			$sql .= "{$this->db_left_id} = CASE ";
			$sql .= "	WHEN {$this->db_left_id} > {$deleted_left} THEN ";
			$sql .= "		{$this->db_left_id} - ({$deleted_right} - {$deleted_left} + 1) ";
			$sql .= "	ELSE ";
			$sql .= "		{$this->db_left_id} ";
			$sql .= "END ";
			$sql .= "WHERE {$this->db_left_id} > {$deleted_left} OR {$this->db_right_id} > {$deleted_right};";
			$this->db_query($sql);
		
			// update the right ids
			$sql = "UPDATE {$this->db_table} SET ";
			$sql .= "{$this->db_right_id} = CASE ";
			$sql .= "	WHEN {$this->db_right_id} > {$deleted_right} THEN ";
			$sql .= "		{$this->db_right_id} - ({$deleted_right} - {$deleted_left} + 1) ";
			$sql .= "	ELSE ";
			$sql .= "		{$this->db_right_id} ";
			$sql .= "END ";
			$sql .= "WHERE {$this->db_left_id} > {$deleted_left} OR {$this->db_right_id} > {$deleted_right};";
			$this->db_query($sql);
		
		// delete the node and move all nodes from under it up to take its place
		} else {
						
			$sql = "DELETE FROM {$this->db_table} WHERE {$this->db_left_id} = {$deleted_left} AND {$this->db_right_id} = {$deleted_right};";
			$this->db_query($sql);
			
			// update the left ids
			$sql = "UPDATE {$this->db_table} SET ";
			$sql .= "{$this->db_left_id} = CASE ";
			$sql .= "	WHEN {$this->db_left_id} > {$deleted_left} AND {$this->db_right_id} < {$deleted_right} THEN ";
			$sql .= "		{$this->db_left_id} - 1 ";
			$sql .= "	WHEN {$this->db_left_id} > {$deleted_right} THEN ";
			$sql .= "		{$this->db_left_id} - 2 ";
			$sql .= "	ELSE ";
			$sql .= "		{$this->db_left_id} ";
			$sql .= "END ";
			$sql .= "WHERE {$this->db_left_id} > {$deleted_left} OR {$this->db_right_id} > {$deleted_right};";
			$this->db_query($sql);
				
			// update the right ids
			$sql = "UPDATE {$this->db_table} SET ";
			$sql .= "{$this->db_right_id} = CASE ";
			$sql .= "	WHEN {$this->db_right_id} < {$deleted_right} AND {$this->db_left_id} >= {$deleted_left} THEN ";
			$sql .= "		{$this->db_right_id} - 1 ";
			$sql .= "	WHEN {$this->db_right_id} > {$deleted_right} THEN ";
			$sql .= "		{$this->db_right_id} - 2 ";
			$sql .= "	ELSE ";
			$sql .= "		{$this->db_right_id} ";
			$sql .= "END ";
			$sql .= "WHERE 1=1;";
			$this->db_query($sql);
		}
		
		return TRUE;
	}
	
	/**
	 * Export the nodes on the tree to a readable format. Debug function.
	 * @internal
	 */
	public function export() {
		$sql = "SELECT a.{$this->db_primary_id}, a.{$this->db_left_id}, a.{$this->db_right_id}, COUNT(b.{$this->db_primary_id}) ";
		$sql .= "FROM {$this->db_table} a LEFT JOIN {$this->db_table} b ON (b.{$this->db_left_id} < a.{$this->db_left_id} AND b.{$this->db_right_id} > a.{$this->db_right_id}) ";
		$sql .= "GROUP BY a.{$this->db_left_id} ORDER BY a.{$this->db_left_id} ASC";
		
		$rows = $this->db_query($sql, TRUE);
		
		// export the tree
		echo '<table>';
		echo '<th>Export of Tree Structure for Table ['. $this->db_table .']</th>';
		if($rows) {
			foreach($rows as $row) {
				echo '<tr>';
				echo '<td>'. str_repeat('&nbsp;|&nbsp;-&nbsp;-&nbsp;-&nbsp;', $row[3]) . $row[0] .' ('. $row[1] .', '. $row[2] .')</td>';
				echo '</tr>';
			}
		}
		
		echo '</table>';
	}
}

/*
CREATE TABLE `mptt` (
  `id` int(11) NOT NULL auto_increment,
  `left_id` int(11) NOT NULL,
  `right_id` int(11) NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;
*/

// connect to the db
$conn = mysql_connect('localhost', 'test', 'test', TRUE);
mysql_select_db('test', $conn);

// instanciate
$mptt = new MPTT($conn);
$mptt->configure('mptt', 'left_id', 'right_id', 'id');


$mptt->insert(); // 1
	$mptt->insert(1); // 2
		$mptt->insert(2); // 3
$mptt->insert(); // 4
	$mptt->insert(4); // 5

$mptt->move(2, 4);

$mptt->export();