MultiTree Behavior

by cyberthom
MultiTree is a drop-in behaviour to CakePHP's Core Tree Behavior allowing for more advanced operations and better performance on large data sets
This article assumes you have read and understood http://book.cakephp.org/view/228/Basic-Usage

Public Repository

http://github.com/cyberthom/MultiTree-Behavior (fork away!)

Advantages

  • Support for root_id (This will vastly increase speed for write operations on large data sets - this is because not the whole tree has to be rewritten when updating a node but only those rows with the same root id)
  • Support for level caching
  • Easier moving of nodes (MultiTree supports full move() to any id as opposed to Core Tree's moveUp and moveDown)
  • More getter functions (easily retrieve siblings, children, parents etc.)

Caution

Use InnoDB (or a different engine that supports transactions, otherwise you have to LOCK tables manually during operations to prevent corrupted data in multi user environments)

Configuration

Example 1

The following config is meant for large trees that are often updated as well a retrieved. It keeps track of a tree that has root_id's and level caching enabled. It is ideal for e.g. Comment Trees

Model Class:

<?php class Comment extends AppModel {
    var 
$name 'Comment';
    var 
$actsAs = array(
        
'MultiTree' => array(
            
'root' =>'root_id',
            
'level' =>'level'
            
)
        );
}
?>
Schema
CREATE TABLE `comments` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `title` varchar(128) NOT NULL default '',
  `body` text NOT NULL,
  `created` datetime default NULL,
  `modified` datetime default NULL,
  `parent_id` int(10) unsigned default NULL,
  `root_id` int(10) unsigned default NULL,
  `lft` mediumint(8) unsigned default NULL,
  `rght` mediumint(8) unsigned default NULL,
  `level` mediumint(8) unsigned default NULL,
  PRIMARY KEY  (`id`),
  KEY `rght` USING BTREE (`root_id`,`rght`,`lft`),
  KEY `lft` USING BTREE (`root_id`,`lft`,`rght`),
  KEY `parent_id` USING BTREE (`parent_id`,`sticky`,`created`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

Example 2

This following config is meant for small trees that are mainly retrieved and not often updated. It keeps track of a tree without root_id's and level caching disabled. It is ideal for e.g. Category Trees
Note: This would also be the config for drop in's from the core Tree Behaviour

Model Class:

<?php class Category extends AppModel {
    var 
$name 'Comment';
    var 
$actsAs = array(
        
'MultiTree' => array(
            
'root' => false,
            
'level' => false
            
)
        );
}
?>
Schema
CREATE TABLE `categories` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `name` varchar(128) NOT NULL default '',
  `parent_id` int(10) unsigned default NULL,
  `lft` mediumint(6) unsigned default NULL,
  `rght` mediumint(6) unsigned default NULL,
  PRIMARY KEY  (`id`),
  KEY `lft` USING BTREE (`lft`),
  KEY `parent_id` USING BTREE (`parent_id`),
  KEY `rght` USING BTREE (`rght`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8


Config defaults

parent: parent_id
left: lft
right: rght
root: root_id
level: level


Traversing the tree

Get parent

Get parent based on Parent
debug($this->Category->getParent(32));
Get parent based on Left/Right values
debug($this->Category->getParentFromTree(32));

Get path

debug($this->Category->getPath(32));

Get level

debug($this->Category->getLevel(32));

Get children

debug($this->Category->getChildren(32));
Get direct children only:
debug($this->Category->getChildren(32, true));

Get child count

debug($this->Category->getChildCount(32));

Get siblings

debug($this->Category->getSiblings(32));
Get siblings including the node itself
debug($this->Category->getSiblings(32, true));

Get previous siblings

debug($this->Category->getPrevSiblings(32));
Get previous siblings including the node itself
debug($this->Category->getPrevSiblings(32, true));

Get next siblings

debug($this->Category->getNextSiblings(32));
Get next siblings including the node itself
debug($this->Category->getNextSiblings(32, true));

Get previous sibling

debug($this->Category->getPrevSibling(32));

Get next sibling

debug($this->Category->getNextSibling(32));

Insert

Insert new node as the last child of node 1
$format = array(
    'name' => 'Cat',
    'parent_id' => 1
    );
$this->Category->save($format);

Insert new node as the next sibling of node 4
$format = array(
    'name' => 'Lion',
    'parent_id' => array('destination' => 4, 'position' => 'nextSibling')
    );
$this->Category->save($format);

Not setting a parent_id or nulling it out will insert the node as a top level (root) node
$format = array(
    'name' => 'Animal',
    'parent_id' => null
    );
$this->Category->save($format);


Move

$this->Category->move(6, 12, 'firstChild'); // Move node 6 to be the first child of node 12
$this->Category->move(6, 12, 'lastChild'); // Move node 6 to be the last child of node 12
$this->Category->move(6, 12, 'prevSibling'); // You get the idea..
$this->Category->move(6, 12, 'nextSibling');

Move node 9 up by 2 (if possible, otherwise move as high up as possible)
$this->Category->moveUp(9, 2);
Move node 9 down by 3 (if possible, otherwise move as low down as possible)
$this->Category->moveDown(9, 3);
Will make node 6 a new top level (root) node
$this->Category->move(6, null);

Delete

$this->Category->delete(25); // Same as removeFromTree(25)
This will delete node 25 and all its children
$this->Category->removeFromTree(25);
This will delete node 25 itself but if it has any children shift them one level up
$this->Category->removeFromTree(25, false);

Repair

left and right values are broken but we have valid parent_id's
$this->Category->repair('tree');
parent_id's are broken but we have valid left and right values
$this->Category->repair('parent');

Behavior Class:

<?php 
/**
 * Multi Tree Behaviour Class
 * 
 * MultiTree is a semi-drop-in behaviour to CakePHP's Core Tree Behavior allowing 
 * for more advanced operations and better performance on large data sets
 * 
 * NOTE: Use InnoDB (or a different engine that supports transactions, otherwise you have to LOCK tables manually during operations to prevent corrupted data in multi user environments)
 * 
 * @author Thomas Heymann
 * @link http://bakery.cakephp.org/articles/view/multitree-behavior
 * @link http://book.cakephp.org/view/228/Basic-Usage
 * @version    0.1
 * @license    http://www.opensource.org/licenses/mit-license.php The MIT License
 * @package app
 * @subpackage app.models.behaviors
 **/
class MultiTreeBehavior extends ModelBehavior {
    
    
/**
     * undocumented class variable
     *
     * @access protected
     * @var array
     **/
    
var $_defaults = array(
        
// Field names
        
'parent' => 'parent_id',
        
'left' => 'lft',
        
'right' => 'rght',
        
'root' => 'root_id'// optional, allow multiple trees per table
        
'level' => 'level'// optional, cache levels
        
        // Other
        
'recursive' => -1,
        
        
// Private
        
'__treeFields' => array(),
        
'__move' => false,
        
'__delete' => false
    
);
    
    
/**
     * undocumented function
     *
     * @access public
     * @return void
     **/
    
function setup(&$Model$config = array()) {
        
// Merge config with defaults
        
if ( !is_array($config) ) {
            
$config = array();
        }
        
$this->settings[$Model->alias] = array_merge($this->_defaults$config);
        
// __treeFields
        
if ( empty($this->settings[$Model->alias]['__treeFields']) ) {
            
$this->settings[$Model->alias]['__treeFields'] = array(
                
$this->settings[$Model->alias]['parent'],
                
$this->settings[$Model->alias]['left'],
                
$this->settings[$Model->alias]['right']
                );
            if ( !empty(
$this->settings[$Model->alias]['root']) ) {
                
// if ( !$Model->hasField($this->settings[$Model->alias]['root']) )
                
$this->settings[$Model->alias]['__treeFields'][] = $this->settings[$Model->alias]['root'];
            }
            if ( !empty(
$this->settings[$Model->alias]['level']) ) {
                
// if ( !$Model->hasField($this->settings[$Model->alias]['level']) )
                
$this->settings[$Model->alias]['__treeFields'][] = $this->settings[$Model->alias]['level'];
            }
        }
    }

    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function beforeSave(&$Model) {
        
extract($this->settings[$Model->alias]);
        
        
// Are we about to create or edit?
        
$creating = empty($Model->id);
        
        
// Check if we need to perform changes to the tree
        
if ( isset($Model->data[$Model->alias][$parent]) ) {
            
// Get node
            
if ( !$creating && ($node $this->_node(&$Model$Model->id)) === false ) {
                return 
false;
            }
            
// Accept array with position information
            
$position 'lastChild';
            if ( 
is_array($Model->data[$Model->alias][$parent]) ) {
                if ( 
array_key_exists('destination'$Model->data[$Model->alias][$parent]) && array_key_exists('position'$Model->data[$Model->alias][$parent]) ) {
                    
$position $Model->data[$Model->alias][$parent]['position'];
                    
$Model->data[$Model->alias][$parent] = $Model->data[$Model->alias][$parent]['destination'];
                } else {
                    
$Model->data[$Model->alias][$parent] = reset($Model->data[$Model->alias][$parent]);
                }
            }
            
// Any parent changes?
            
if ( $creating || $Model->data[$Model->alias][$parent] != $node[$parent] ) {
                
// Check if parent axists
                
if ( !empty($Model->data[$Model->alias][$parent]) && ($destNode $this->_node(&$Model$Model->data[$Model->alias][$parent])) === false ) {
                    
$Model->invalidate($parent'Parent does not exist');
                    return 
false;
                }
                
// Mark for moving
                
$this->settings[$Model->alias]['__move'] = array('parent' => $Model->data[$Model->alias][$parent], 'position' => $position);
            }
        } else if ( !empty(
$root) && isset($Model->data[$Model->alias][$root]) ) {
            
// Get node
            
if ( !$creating && ($node $this->_node(&$Model$Model->id)) === false ) {
                return 
false;
            }
            
// Any root changes?
            
if ( $creating || $Model->data[$Model->alias][$root] != $node[$root] ) {
                
// Mark for moving
                
$this->settings[$Model->alias]['__move'] = array('root' => $Model->data[$Model->alias][$root]);
            }
        } else if ( 
$creating ) {
            
$this->settings[$Model->alias]['__move'] = null;
        }
        
        
// Don't allow manually changing left, right etc.
        
$Model->data[$Model->alias] = array_diff_key($Model->data[$Model->alias], array_flip($__treeFields));
        
        return 
true;
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function afterSave(&$Model$created) {
        if ( 
$this->settings[$Model->alias]['__move'] !== false ) {
            
$this->move($Model$Model->id$this->settings[$Model->alias]['__move']);
            
$this->settings[$Model->alias]['__move'] = false;
        }
    }
    
    
/**
     * undocumented function
     *
     * @return void
     **/
    
function beforeDelete(&$Model$cascade) {
        
$this->settings[$Model->alias]['__delete'] = $this->_node($Model$Model->id);
        return 
true;
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function afterDelete(&$Model) {
        if ( 
$this->settings[$Model->alias]['__delete'] !== false ) {
            
$this->removeFromTree($Model$this->settings[$Model->alias]['__delete']);
            
$this->settings[$Model->alias]['__delete'] = false;
        }
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function move(&$Model$id$dest null$position 'lastChild') {
        
extract($this->settings[$Model->alias]);
        if ( !
is_array($dest) ) {
            
$dest = array('parent' => $dest);
        } else if ( 
array_key_exists('position'$dest) ) {
            
$position $dest['position'];
        }
        
        
// Get node
        
if ( ($node $this->_node(&$Model$id)) === false ) {
            return 
false;
        }
        
$oldNode $node;
        
$invalid = (empty($oldNode[$left]) || empty($oldNode[$right]));
        
        
// Start transaction
        
$Model->getDataSource()->begin($Model);
        
        
// Fake loop allowing us to jump to the end on failure
        
while ( $commit true ) {
        
            
// Get node size
            
if ( $invalid ) {
                
$node[$left] = 1;
                
$node[$right] = 2;
                
// $node[$parent] = null;
                // if ( !empty($root) )
                //     $node[$root] = null;
            
}
            
$treeSize $node[$right]-$node[$left]+1;
            
            
// Are we moving to another node?
            
if ( !empty($dest['parent']) ) {
                
// Get destination node
                
if ( ($destNode $this->_node(&$Model$dest['parent'])) === false ) {
                    
// return false;
                    
$Model->invalidate($parent'Parent does not exist');
                    
$commit false;
                    break;
                }
                
// Do not allow to move a node to or inside itself
                
if ( !$invalid && (empty($root) || $node[$root] == $destNode[$root]) && ($destNode[$left] >= $node[$left] && $destNode[$right] <= $node[$right]) ) {
                    
// return false;
                    
$Model->invalidate($parent'Destination node is within source tree');
                    
$commit false;
                    break;
                }
                
// Set beginning of shift range
                
switch ( $position ) {
                    case 
'prevSibling':
                        
$node[$parent] = $destNode[$parent];
                        if ( !empty(
$level) )
                            
$node[$level] = $destNode[$level];
                        
$start $destNode[$left];
                        break;
                    case 
'nextSibling':
                        
$node[$parent] = $destNode[$parent];
                        if ( !empty(
$level) )
                            
$node[$level] = $destNode[$level];
                        
$start $destNode[$right]+1;
                        break;
                    case 
'firstChild':
                        
$node[$parent] = $destNode[$Model->primaryKey]; // Same as $dest['parent']
                        
if ( !empty($level) )
                            
$node[$level] = $destNode[$level]+1;
                        
$start $destNode[$left]+1;
                        break;
                    case 
'lastChild':
                    default:
                        
$node[$parent] = $destNode[$Model->primaryKey]; // Same as $dest['parent']
                        
if ( !empty($level) )
                            
$node[$level] = $destNode[$level]+1;
                        
$start $destNode[$right];
                }
                if ( !empty(
$root) )
                    
$node[$root] = $destNode[$root];
                
                
// Create gap for node in target tree
                
if ( ($commit $this->_shift($Model$start$treeSize, @$destNode[$root])) === false )
                    break;
                
                
// Refresh node record (might have been affected by previous shift)
                // $node = $this->_node(&$Model, $id); // We can save us this query with the following:
                
if ( ($affectedLeft = (!$invalid && (empty($root) || $node[$root] == $destNode[$root]) && $node[$left] >= $start)) !== false )
                    
$node[$left] += $treeSize;
                if ( (
$affectedRight = (!$invalid && (empty($root) || $node[$root] == $destNode[$root]) && $node[$right] >= $start)) !== false )
                    
$node[$right] += $treeSize;
            } else if ( empty(
$root) ) {
                
// Move to the end of new tree
                
$node[$parent] = null;
                if ( !empty(
$level) )
                    
$node[$level] = 0;
                
$start $this->_max($Model$right)+1;
            } else if ( !empty(
$dest['root']) ) {
                
// Move to the end of tree
                
$node[$root] = $dest['root'];
                
$node[$parent] = null;
                if ( !empty(
$level) )
                    
$node[$level] = 0;
                
$start $this->_max($Model$right, array($Model->escapeField($root) => $dest['root']))+1;
            } else if ( isset(
$dest['root']) && !empty($node[$root]) ) {
                
// Move to the end of tree
                // $node[$root] = $node[$root]; // I know..
                
$node[$parent] = null;
                if ( !empty(
$level) )
                    
$node[$level] = 0;
                
$start $this->_max($Model$right, array($Model->escapeField($root) => $node[$root]))+1;
            } else {
                
// Move to the end of new tree
                
$node[$root] = $this->_max($Model$root)+1;
                
$node[$parent] = null;
                if ( !empty(
$level) )
                    
$node[$level] = 0;
                
$start 1;
            }
            
            if ( !
$invalid && $treeSize ) {
                
// Move node into that gap (Save new left, right, root and level)
                
$diff $start-$node[$left];
                
$levelDiff = !empty($level) ? $node[$level]-$oldNode[$level] : 0;
                if ( (
$commit $this->_shiftRange($Model$node[$left], $node[$right], $diff, @$oldNode[$root], @$node[$root], @$levelDiff)) === false )
                    break;
                
// Save new parent
                
if ( ($commit = ($Model->save($node, array('callbacks' => false'validate' => false'fieldList' => array($parent))) !== false)) === false )
                    break;
            } else {
                
// Move node into that gap (Save new left, right, root, parent and level)
                
$diff $start-$node[$left];
                
$data $node// Create new array, otherwise we affect range of shift() below
                
$data[$left] += $diff;
                
$data[$right] += $diff;
                if ( (
$commit = ($Model->save($data, array('callbacks' => false'validate' => false'fieldList' => $__treeFields)) !== false)) === false )
                    break;
            }
            
            
// Remove gap created while removing node from source tree
            
if ( !$invalid ) {
                if ( (
$commit $this->_shift($Model$node[$left], -$treeSize, @$oldNode[$root])) === false )
                    break;
            }
            
            
// We don't want this to actually loop
            
break;
        }
        
        
// Commit
        
if ( $commit ) {
            
$Model->getDataSource()->commit($Model);
        } else {
            
$Model->getDataSource()->rollback($Model);
        }
        return 
$commit;
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function moveUp(&$Model$id$number 1) {
        
$prevSiblings array_reverse($this->getPrevSiblings($Model$idfalse));
        if ( empty(
$prevSiblings) )
            return 
false;
        if ( 
count($prevSiblings) < $number )
            
$number count($prevSiblings);
        return 
$this->move($Model$id$prevSiblings[$number-1][$Model->alias][$Model->primaryKey], 'prevSibling');
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function moveDown(&$Model$id$number 1) {
        
$nextSiblings $this->getNextSiblings($Model$idfalse);
        if ( empty(
$nextSiblings) )
            return 
false;
        if ( 
count($nextSiblings) < $number )
            
$number count($nextSiblings);
        return 
$this->move($Model$id$nextSiblings[$number-1][$Model->alias][$Model->primaryKey], 'nextSibling');
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function removeFromTree(&$Model$id$deleteChildren true) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node (or use id as data)
        
if ( is_array($id) ) {
            
$node $id;
            
$id $node[$Model->primaryKey];
        } else {
            if ( (
$node $this->_node(&$Model$id)) === false ) {
                return 
false;
            }
        }
        
$invalid = (empty($node[$left]) || empty($node[$right]));
        if ( 
$invalid ) {
            
// Delete invalid nodes just like that
            
return $this->__delete($Model$id);
        }
        
        
// Get node size
        
$treeSize $node[$right]-$node[$left]+1;
        
        
// Start transaction
        
$Model->getDataSource()->begin($Model);
        
        
// Fake loop allowing us to jump to the end on failure
        
while ( $commit true ) {
            
// Either delete node and all its children - or - delete node and shift its children one level up
            
if ( $deleteChildren ) {
                if ( 
$treeSize ) {
                    
// Delete node and all its children from tree
                    
if ( ($commit $this->__deleteRange($Model$node[$left], $node[$right], @$node[$root])) === false )
                        break;
                } else {
                    
// Delete node
                    
if ( ($commit $this->__delete($Model$id)) === false )
                        break;
                }
                
// Remove gap created while removing node from tree
                
if ( ($commit $this->_shift($Model$node[$left], -$treeSize, @$node[$root])) === false )
                    break;
            } else {
                
// Delete node
                
if ( ($commit $this->__delete($Model$id)) === false )
                    break;
                if ( 
$treeSize ) {
                    
// Set new parent of direct children
                    
$conditions = array($Model->escapeField($parent) => $id);
                    if ( !empty(
$root) )
                        
$conditions[$Model->escapeField($root)] = $node[$root];
                    if ( (
$commit $Model->updateAll(array($Model->escapeField($parent) => $node[$parent]), $conditions)) === false )
                        break;
                    
// Shift all children up
                    
if ( ($commit $this->_shiftRange($Model$node[$left], $node[$right], -1, @$node[$root], @$node[$root], -1)) === false )
                        break;
                }
                
// Shift siblings
                
if ( ($commit $this->_shift($Model$node[$right], -2, @$node[$root])) === false )
                    break;
            }
            
            
// We don't want this to actually loop
            
break;
        }
            
// $Model->getDataSource()->rollback($Model);
            // return true;
        
        // Commit
        
if ( $commit ) {
            
$Model->getDataSource()->commit($Model);
        } else {
            
$Model->getDataSource()->rollback($Model);
        }
        return 
$commit;
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getChildren(&$Model$id$direct false$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        if ( 
$direct ) {
            
// Get node's direct children
            
return $Model->find('all', array(
                
'fields' => $fields,
                
'conditions' => array($Model->escapeField($parent) => $id),
                
'order' => array($Model->escapeField($left) => 'asc'),
                
'recursive' => $recursive,
                ));
        }
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Conditions
        
$conditions = array(
            
// $Model->escapeField($root) => $node[$root],
            
$Model->escapeField($left).' >' => $node[$left],
            
$Model->escapeField($right).' <' => $node[$right]
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $node[$root];
        
// Get node's children
        
return $Model->find('all', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'order' => array($Model->escapeField($left) => 'asc'),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getChildCount(&$Model$id$direct false) {
        
extract($this->settings[$Model->alias]);
        
        if ( 
$direct ) {
            return 
$Model->find('count', array('conditions' => array($Model->escapeField($parent) => $id)));
        } else {
            
// Use cached node if possible
            
if ( isset($Model->data[$Model->alias][$left]) && isset($Model->data[$Model->alias][$right]) ) {
                
$node $Model->data[$Model->alias];
            } else {
                
// Get node
                
if ( ($node $this->_node($Model$id)) === false ) {
                    return 
0;
                }
            }
            return (
$node[$right]-$node[$left]-1)/2;
        }
    }

    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getSiblings(&$Model$id$includeNode false$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Get node's siblings
        
$conditions = array($Model->escapeField($parent) => $node[$parent]);
        if ( !
$includeNode ) {
            
$conditions[$Model->escapeField().' <>'] = $id;
        }
        return 
$Model->find('all', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'order' => array($Model->escapeField($left) => 'asc'),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getNextSiblings(&$Model$id$includeNode false$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Get node's siblings
        
$conditions = array($Model->escapeField($parent) => $node[$parent]);
        if ( 
$includeNode ) {
            
$conditions[$Model->escapeField($left).' >='] = $node[$left];
        } else {
            
$conditions[$Model->escapeField($left).' >'] = $node[$left];
        }
        return 
$Model->find('all', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'order' => array($Model->escapeField($left) => 'asc'),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getPrevSiblings(&$Model$id$includeNode false$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Get node's siblings
        
$conditions = array($Model->escapeField($parent) => $node[$parent]);
        if ( 
$includeNode ) {
            
$conditions[$Model->escapeField($left).' <='] = $node[$left];
        } else {
            
$conditions[$Model->escapeField($left).' <'] = $node[$left];
        }
        return 
$Model->find('all', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'order' => array($Model->escapeField($left) => 'asc'),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getNextSibling(&$Model$id$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Conditions
        
$conditions = array(
            
// $Model->escapeField($root) => $node[$root],
            
$Model->escapeField($left) => $node[$right]+1
            
);
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $node[$root];
        
// Get node's parent
        
return $Model->find('first', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getPrevSibling(&$Model$id$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Conditions
        
$conditions = array(
            
// $Model->escapeField($root) => $node[$root],
            
$Model->escapeField($right) => $node[$left]-1
            
);
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $node[$root];
        
// Get node's parent
        
return $Model->find('first', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getParent(&$Model$id$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Get node's parent
        
return $Model->find('first', array(
            
'fields' => $fields,
            
'conditions' => array($Model->escapeField() => $node[$parent]),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getParentFromTree(&$Model$id$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Conditions
        
$conditions = array(
            
$Model->escapeField($left).' <' => $node[$left],
            
$Model->escapeField($right).' >' => $node[$right],
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $node[$root];
        
// Get path to node
        
return $Model->find('first', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'order' => array($Model->escapeField($left) => 'desc'),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getPath(&$Model$id$fields null$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// Conditions
        
$conditions = array(
            
// $Model->escapeField($root) => $node[$root],
            
$Model->escapeField($left).' <=' => $node[$left],
            
$Model->escapeField($right).' >=' => $node[$right],
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $node[$root];
        
// Get path to node
        
return $Model->find('all', array(
            
'fields' => $fields,
            
'conditions' => $conditions,
            
'order' => array($Model->escapeField($left) => 'asc'),
            
'recursive' => $recursive,
            ));
    }
    
    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function getLevel(&$Model$id) {
        
extract($this->settings[$Model->alias]);

        
// Get node
        
if ( ($node $this->_node($Model$id)) === false ) {
            return array();
        }
        
// if ( !empty($level) )
        //     return $node[$level];
        // Conditions
        
$conditions = array(
            
$Model->escapeField($left).' <' => $node[$left],
            
$Model->escapeField($right).' >' => $node[$right],
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $node[$root];        
        return 
$Model->find('count', array('conditions' => $conditions));
    }

    
/**
     * undocumented function
     *
     * @access public
     * @return boolean
     **/
    
function generateTreeList(&$Model$conditions null$keyPath null$valuePath null$spacer '_'$recursive null) {
        
extract($this->settings[$Model->alias]);
        
        if ( 
is_numeric($conditions) ) {
            
$results $this->getChildren($Model$conditions);
        } else {
            
$results $Model->find('all', array(
                
'conditions' => $conditions,
                
'order' => array($Model->escapeField($left) => 'asc'),
                
'recursive' => $recursive,
                ));
        }
        if ( empty(
$results) ) {
            return array();
        }
        
        if (
$keyPath == null && $valuePath == null && $Model->hasField($Model->displayField)) {
            
$fields = array($Model->primaryKey$Model->displayField$root$left$right);
        } else {
            
$fields null;
        }
        if (
$keyPath == null) {
            
$keyPath '{n}.'.$Model->alias.'.'.$Model->primaryKey;
        }
        if (
$valuePath == null) {
            
$valuePath = array('{0}{1}''{n}.tree_prefix''{n}.'.$Model->alias.'.'.$Model->displayField);
        } else if (
is_string($valuePath)) {
            
$valuePath = array('{0}{1}''{n}.tree_prefix'$valuePath);
        } else {
            
$valuePath[0] = '{'.(count($valuePath)-1).'}'.$valuePath[0];
            
$valuePath[] = '{n}.tree_prefix';
        }
        
        if ( !empty(
$level) ) {
            foreach ( 
$results as $i => $result ) {
                
$results[$i]['tree_prefix'] = str_repeat($spacer$result[$Model->alias][$level]);
            }
        } else {
            foreach (
$results as $i => $result) {
                
$stack_key = @$result[$Model->alias][$root];
                if ( !@
array_key_exists($stack_key$stack) )
                    
$stack[$stack_key] = array();
                while (
$stack[$stack_key] && ($stack[$stack_key][count($stack[$stack_key])-1] < $result[$Model->alias][$right])) {
                    
array_pop($stack[$stack_key]);
                }
                
$results[$i]['tree_prefix'] = str_repeat($spacer,count($stack[$stack_key]));
                
$stack[$stack_key][] = $result[$Model->alias][$right];
            }
        }
        return 
Set::combine($results$keyPath$valuePath);
        
    }
    
    
/**
     * undocumented function
     *
     * @return void
     **/
    
function repair(&$Model$broken 'tree') {
        
extract($this->settings[$Model->alias]);
        
$Model->recursive $recursive;
        
        switch ( 
$broken ) {
            case 
'parent':
                
// Find and set parent of each node using tree structure
                
$nodes $Model->find('all', array(
                    
'fields' => array_merge(array($Model->primaryKey), $__treeFields),
                    ));
                foreach ( 
$nodes as $node ) {
                    
$id $node[$Model->alias][$Model->primaryKey];
                    if ( (
$parentNode $this->getParentFromTree($Model$id)) !== false ) {
                        
$node[$Model->alias][$parent] = $parentNode[$Model->alias][$Model->primaryKey];
                    } else {
                        
$node[$Model->alias][$parent] = null;
                    }
                    
$Model->save($node, array('callbacks' => false'validate' => false'fieldList' => array($parent)));
                }
                break;
            
            case 
'tree':
                
// Null out all tree values except for parent
                
$data array_fill_keys(array_diff($__treeFields, array($parent)), null); // PHP5.2
                
$Model->updateAll($data);
                
// Move nodes back into tree structure, one after the other
                
$nodes $Model->find('all', array(
                    
'fields' => array_merge(array($Model->primaryKey), $__treeFields),
                    
'order' => array(
                        
"$Model->alias.$parent=> 'asc',
                        
"$Model->alias.$Model->primaryKey=> 'asc',
                        )
                    ));
                foreach ( 
$nodes as $node ) {
                    
$node reset($node);
                    
$this->move($Model$node[$Model->primaryKey], $node[$parent], 'lastChild');
                }
                break;
        }
    }
    
    
/**
     * undocumented function
     *
     * @access protected
     * @return void
     **/
    
function _node(&$Model$id) {
        
extract($this->settings[$Model->alias]);
        if ( (
$node $Model->find('first', array(
            
'fields' => array_merge(array($Model->primaryKey), $__treeFields),
            
'conditions' => array($Model->escapeField() => $id),
            
'recursive' => $recursive
            
))) === false ) {
            return 
false;
        }
        return 
reset($node);
    }
    
    
/**
     * undocumented function
     *
     * @access protected
     * @return void
     **/
    
function _max(&$Model$field$conditions null) {
        
$max $Model->find('all', array(
            
'fields' => $Model->getDataSource()->calculate($Model'max', array($Model->escapeField($field), $field)),
            
'conditions' => $conditions,
            
'recursive' => -1
        
));
        return (int)(
reset(reset(reset($max))));
    }
    
    
/**
     * undocumented function
     *
     * @access protected
     * @return void
     **/
     
function _shift(&$Model$first$delta$rootId 1) {
        
extract($this->settings[$Model->alias]);
        
        
$sign = ($delta >= 0) ? ' + ' ' - ';
        
$delta abs($delta);
        
        
// Shift (left)
        
$data = array($Model->escapeField($left) => $Model->escapeField($left).$sign.$delta);
        
$conditions = array(
            
// $Model->escapeField($root) => $rootId,
            
$Model->escapeField($left).' >=' => $first,
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $rootId;
        if ( 
$Model->updateAll($data$conditions) === false )
            return 
false;
        
        
// Shift (right)
        
$data = array($Model->escapeField($right) => $Model->escapeField($right).$sign.$delta);
        
$conditions = array(
            
// $Model->escapeField($root) => $rootId,
            
$Model->escapeField($right).' >=' => $first,
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $rootId;
        if ( 
$Model->updateAll($data$conditions) === false )
            return 
false;
        
        return 
true;
    }
    
    
/**
     * undocumented function
     *
     * @access protected
     * @return void
     **/
     
function _shiftRange(&$Model$first$last 0$delta$rootId 1$destRootId 1$levelDelta 0) {
        
extract($this->settings[$Model->alias]);
        
        
$sign = ($delta >= 0) ? ' + ' ' - ';
        
$delta abs($delta);
        
$levelSign = ($levelDelta >= 0) ? ' + ' ' - ';
        
$levelDelta abs($levelDelta);
        
        
// Data
        
$data = array(
            
// $Model->escapeField($root) => $destRootId,
            
$Model->escapeField($left) => $Model->escapeField($left).$sign.$delta,
            
$Model->escapeField($right) => $Model->escapeField($right).$sign.$delta
            
);
        if ( !empty(
$root) )
            
$data[$Model->escapeField($root)] = $destRootId;
        if ( !empty(
$level) )
            
$data[$Model->escapeField($level)] = $Model->escapeField($level).$levelSign.$levelDelta;
        
        
// Conditions
        
$conditions = array(
            
// $Model->escapeField($root) => $rootId,
            
$Model->escapeField($left).' >=' => $first,
            
$Model->escapeField($right).' <=' => $last,
            );
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $rootId;
        return 
$Model->updateAll($data$conditions);
    }
    
    
/**
     * undocumented function
     *
     * @access private
     * @return void
     **/
    
function __delete(&$Model$id) {
        return 
$Model->deleteAll(array(
            
$Model->escapeField() => $id
            
), truefalse);
    }
    
    
/**
     * undocumented function
     *
     * @access private
     * @return void
     **/
    
function __deleteRange(&$Model$first$last$rootId 1) {
        
extract($this->settings[$Model->alias]);
        
        
$conditions = array(
            
// $Model->escapeField($root) => $rootId,
            
$Model->escapeField($left).' >=' => $first,
            
$Model->escapeField($right).' <=' => $last
            
);
        if ( !empty(
$root) )
            
$conditions[$Model->escapeField($root)] = $rootId;
        return 
$Model->deleteAll($conditionstruefalse);
    }


    
/**
     * @see getChildren
     * @deprecated use getChildren
     * @access public
     */
    
function children() {
        
trigger_error('Deprecated method, use MultiTree::getChildren instead'E_USER_WARNING);
        return 
$this->getChildren();
    }

    
/**
     * @see repair
     * @deprecated use repair
     * @access public
     */
    
function recover(&$Model$correct 'parent'$missingParentAction null) {
        
trigger_error('Deprecated method, use MultiTree::repair instead'E_USER_WARNING);
        return 
$this->repair($Model, ($correct == 'parent' 'tree' 'parent'));
    }
}
?>

1 | 2

Report

More on Behaviors

Advertising

Comments

  • alexparker posted on 04/15/11 09:14:54 PM
    I dropped it in, and updated an existing root task to be a child of another root task, so
    Task A was id:1, lft:1, rght:2, level:0, root:1
    Task B was id:2, lft:1, rght:2, level:0, root:2

    i ran $Task->id = 2; $Task->save(array('parent_id'=>1)); And then i was left with:
    Task A was id:1, lft:1, rght:4, level:0, root:1
    Task B was id:2, lft:2, rght:5, level:1, root:1

    It almost got it. Then if you continue to set/modify the parent_id value to other roots, it causes all sorts of left/right messes. I'm really new to the whole left/right thing and I've never jumped into making my own behaviors yet, so I'm not sure how to diagnose or fix it. Just wanted to bring it to attention, and hopefully someone knows how to fix it.
  • -Ste- posted on 11/30/10 11:25:14 AM
    oh,my, my..
    it was my mistake. I was updating old code with wrong assumptions.
    Sorry.


    As cyberthom pointed out on Github, my previous "patch" had an obvious problem - $Model->alias[$this->settings[$Model->alias]['root']] was wrong, $Model->alias is a string, I actually meant $Model->data[$Model->alias][$this->settings[$Model->alias]['root']]

    but the real issue was elsewhere.

    I actually had records gruoped by another field, and every group could have many trees. So, what I needed was an additional filter by Model::gruop_id, not a filter by root_id (I assumed they were the same, it wasn't)

    So i refactored a little, adding a new parameter in $_defaults (handled in setup(), and used in repair() to filter the records to update)

    I'll not add a pull requst on github, because it's probably an edge case.
    Here is what I've added, it could be useful for someone with the same setup.

    Add a new parameter:

    var $_defaults = array(
            // Field names
            [..]
            'filter' => null, // i.e. group_id, for gruoped trees and repair only selected gorup
            [..]
        );

    handle it in setup()

    if ( !empty($this->settings[$Model->alias]['fiter']) ) {
                    // if ( !$Model->hasField($this->settings[$Model->alias]['root']) )
                    $this->settings[$Model->alias]['__treeFields'][] = $this->settings[$Model->alias]['filter'];
                }

    In repair() replace:

    $data = array_fill_keys(array_diff($__treeFields, array($parent, $root)), null); // PHP5.2
    $Model->updateAll($data);

    with:

    $data = array_fill_keys(array_diff($__treeFields, array($parent,$root)), null); // PHP5.2
        
                    if(!is_null($Model->data[0][$Model->alias][$this->settings[$Model->alias]['filter']])) 
                        $filter = $Model->data[0][$Model->alias][$this->settings[$Model->alias]['filter']];
                    
                    else if (!is_null($Model->data[$Model->alias][$this->settings[$Model->alias]['filter']])) 
                        $filter = $Model->data[$Model->alias][$this->settings[$Model->alias]['filter']];
                    
                    if(!isset($filter)) 
                        $Model->updateAll($data);
                    else 
                        $Model->updateAll($data, array($this->settings[$Model->alias]['filter'] =>  $filter));



    Of course, update your model properly

    var $actsAs = array(                
                    'MultiTree' => array(
                                        'root' =>'root_id',
                        'level' =>'level_deep',
                        'filter' => 'group_id'
                    )
                    );

    It's not properly tested, take it as a suggestion if you need grouped trees
  • -Ste- posted on 11/30/10 06:49:50 AM
    I'm Sorry, I replied to the wrong thread. I'll repost here as a new comments thread.

    About repair('tree') sets most of other trees records to null:

    Hello, I had the same problem.
    I don't know if this is the best solution, but here is a patch that works for me. (Or, so it seems until next disaster)

    Problem: when you call repair('tree') the current tree is correctly repaired, but other trees are broken ($__treeFields set to null)

    The problem probably lies -in the MultiTreeBehaviour::repair() method- in the $Model->updateAll($data) call, without conditions (-> update EVERY record, setting left, right, and root id to null..)

    telling the method to update ONLY the records of the current tree should be enough:

    change line 1048
    (see https://github.com/cyberthom/MultiTree-Behavior/blob/master/models/behaviors/multi_tree.php version 0.3)

    to

    $Model->updateAll($data, array($this->settings[$Model->alias]['root'] => $Model->alias[$this->settings[$Model->alias]['root']]));

    (should i fork the code on github? It's just one line.. and I still have to check for side effects)

    HTH,
    Stefano
    [end quote]
  • ctoa posted on 05/23/10 04:51:48 PM
    I'm not sure if this project is still active, but it looks very interesting. In a current project I am in need of tracking multiple trees in a single table. I have tried to use this behavior without success. I have created 2 root nodes using the behavior. Later, when I try to add children a node is created but the parent, root, lft, adn rght fields are all null. Am I doing something wrong here.

    var $actsAs = array( 
        'MultiTree' => array(
            'root' => 'root_id',
            'parent' => 'parent_id',
            'level' => 'level',
        ),
        'Revision', 
        'Logable',        
    );

    function CreateChild( $parentID )
    {
        $newID = false;
            
        $numChildren = $this->getChildCount( $parentID );
        $parent = $this->GetBaseInfo( $parentID );
        
            $this->id = false;
            
        $data = array(
            'root_id' => $parent['TaskTemplate']['root_id'],
            'parent_id' => $parentID,
            'title' => 'New Task-' . $parentID . '-' . ($numChildren + 1),
            'description' => 'Please enter a description or this task.',
            'priority' => $parent['TaskTemplate']['priority'],
            'required' => $parent['TaskTemplate']['required'],
            'deleted' => 0,
        );
        
        if ( $this->save( $data ) )
        {
            #debug( $data );
            $newID = $this->id;
        }
        
        return $newID;
    }


    I noticed in the behavior you remove the parent and root fields. Why is this? I appreciate any help you can offer.
    • aldo posted on 05/25/10 04:57:48 AM
      Similar problem with the NULL values here. When using repair everything is reset to 0.
  • LDSign posted on 05/08/10 11:40:17 AM
    Hi

    Reordering the parents (parent_id=NULL) with moveUp and moveDown does not work. Both functions return false. Reordering of any >1 level childs work as normal. Do you have any hints on this issue?

    Thanks,
    Frank
    • Mr5o1 posted on 01/04/11 07:16:49 PM
      This is a great behaviour, its been really helpful.

      As LDSign mentioned 05/08/10.. there's something wrong with the move functions when called on parents.
      For example, say you want to move the following node:

      id: 100
      root_id: 20
      parent: null
      lft: 1
      rght: 2
      The following will occur:

      $this->Model->moveDown(100);
      //returns true, DELETES NODE ?!, not sure of lft & rght of other nodes is updated
      $this->Model->move(100, null, 'lastChild'); //or some such
      //returns true, creates a NEW TREE for the node (with root_id 101) ?!
      In fairness... move() is "undocumented"... having looked at it briefly the third $dest param can be an array in which you can specify a root_id, to avoid having a new tree created:

      $dest = array(
      'parent' => null,
      'root' => 20
      //can specify 'position' here also? unconfirmed
      );
      $this->Model->move(100, $dest, 'lastChild');
      //moves the node to the lastChild of the root = 20 tree. As expected.

      Hope this saves someone else a bit of time.. took me a while to track down.
      Not sure if its a 'bug' per se, maybe moveDn & moveUp just need to be updated to pass $dest as an array containing 'root' & 'parent'.
    • -Ste- posted on 11/30/10 05:14:36 AM
      [quote] Hi

      Reordering the parents (parent_id=NULL) with moveUp and moveDown does not work. Both functions return false. Reordering of any >1 level childs work as normal. Do you have any hints on this issue?

      Thanks,
      Frank
      [end quote]
      Hello, I had the same problem.
      I don't know if this is the best solution, but here is a patch that works for me. (Or, so it seems until next disaster)

      Problem: when you call repair('tree') the current tree is correctly repaired, but other trees are broken ($__treeFields set to null)

      The problem probably lies -in the MultiTreeBehaviour::repair() method- in the $Model->updateAll($data) call, without conditions (-> update EVERY record, setting left, right, and root id to null..)

      telling the method to update ONLY the records of the current tree should be enough:

      change line 1048
      (see https://github.com/cyberthom/MultiTree-Behavior/blob/master/models/behaviors/multi_tree.php version 0.3)

      to

      $Model->updateAll($data, array($this->settings[$Model->alias]['root'] => $Model->alias[$this->settings[$Model->alias]['root']]));

      (should i fork the code on github? It's just one line.. and I still have to check for side effects)

      HTH,
      Stefano
  • aldo posted on 04/16/10 07:43:45 AM
    Hello,

    When we run the repair function all the values for lft, rght, root_id and level of most tree entries are reset to 0.

    Any idea whre to start looking for the error?

    Thanks!
    Aldo
  • aldo posted on 03/31/10 02:11:11 AM
    Nobody?

    Do I still need http://bakery.cakephp.org/articles/view/scopedtreebehavior additionally to handle different trees in one table?

    Thanks!
  • aldo posted on 03/25/10 09:05:14 AM
    Hello,

    Can this plugin handle different trees in one table?
  • Dieter_be posted on 02/01/10 08:53:16 AM
    > Easier moving of nodes (MultiTree supports full move() to any id as
    > opposed to Core Tree's moveUp and moveDown)

    note that you can very easily do this with cake's treebehavior also.
    See http://book.cakephp.org/view/521/Modifying-data
    • cyberthom posted on 02/01/10 09:01:24 AM
      > Easier moving of nodes (MultiTree supports full move() to any id as
      > opposed to Core Tree's moveUp and moveDown)

      note that you can very easily do this with cake's treebehavior also.
      See http://book.cakephp.org/view/521/Modifying-data

      good point - however MultiTree allows you to specify the _exact_ position:

      $format = array(
      'name' => 'Lion',
      'parent_id' => array('destination' => 4, 'position' => 'nextSibling')
      );
      $this->Category->save($format);
  • cyberthom posted on 01/27/10 08:17:49 AM
    You're welcome guys - Hope it helps!

    I've added a public repository in case someone finds any bugs and wants to fix them or add any features: http://github.com/cyberthom/MultiTree-Behavior (fork away!)
  • toyosawa posted on 01/27/10 07:07:10 AM
    Thanks for your help.
  • zoghal posted on 01/26/10 12:51:44 PM
    very very very tnx
login to post a comment.