<?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();