MultiTree Behavior
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
Note: This would also be the config for drop in's from the core Tree Behaviour
left: lft
right: rght
root: root_id
level: level
Get parent based on Left/Right values
Get direct children only:
Get siblings including the node itself
Get previous siblings including the node itself
Get next siblings including the node itself
Insert new node as the next sibling of node 4
Not setting a parent_id or nulling it out will insert the node as a top level (root) node
Move node 9 up by 2 (if possible, otherwise move as high up as possible)
Move node 9 down by 3 (if possible, otherwise move as low down as possible)
Will make node 6 a new top level (root) node
This will delete node 25 and all its children
This will delete node 25 itself but if it has any children shift them one level up
parent_id's are broken but we have valid left and right values
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 TreesModel 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 TreesNote: 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_idleft: 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 > 2 ) {
// 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, $id, false));
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, $id, false);
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 > 2 ) {
// 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 > 2 ) {
// 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
), true, false);
}
/**
* 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($conditions, true, false);
}
/**
* @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'));
}
}
?>








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.
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
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]
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.
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
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:
The following will occur:id: 100
root_id: 20
parent: null
lft: 1
rght: 2
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:$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) ?!
$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'.
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
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
Do I still need http://bakery.cakephp.org/articles/view/scopedtreebehavior additionally to handle different trees in one table?
Thanks!
No, the whole point of this behavior is to store multiple trees in one table - they are separated by a root_id
Can this plugin handle different trees in one table?
> 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);
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!)
Comments are closed for articles over a year old