Blame | Letzte Änderung | Log anzeigen | RSS feed
<?php/* SVN FILE: $Id: tree.php 8004 2009-01-16 20:15:21Z gwoo $ *//*** Tree behavior class.** Enables a model object to act as a node-based tree.** PHP versions 4 and 5** CakePHP : Rapid Development Framework (http://www.cakephp.org)* Copyright 2006-2008, Cake Software Foundation, Inc.** Licensed under The MIT License* Redistributions of files must retain the above copyright notice.** @filesource* @copyright Copyright 2006-2008, Cake Software Foundation, Inc.* @link http://www.cakefoundation.org/projects/info/cakephp CakePHP Project* @package cake* @subpackage cake.cake.libs.model.behaviors* @since CakePHP v 1.2.0.4487* @version $Revision: 8004 $* @modifiedby $LastChangedBy: gwoo $* @lastmodified $Date: 2009-01-16 12:15:21 -0800 (Fri, 16 Jan 2009) $* @license http://www.opensource.org/licenses/mit-license.php The MIT License*//*** Short description for file** Long description for file** @package cake* @subpackage cake.cake.libs.model.behaviors*/class TreeBehavior extends ModelBehavior {/*** Errors** @var array*/var $errors = array();/*** Defaults** @var array* @access protected*/var $_defaults = array('parent' => 'parent_id', 'left' => 'lft', 'right' => 'rght','scope' => '1 = 1', 'type' => 'nested', '__parentChange' => false, 'recursive' => -1);/*** Initiate Tree behavior** @param object $Model* @param array $config* @return void* @access public*/function setup(&$Model, $config = array()) {if (!is_array($config)) {$config = array('type' => $config);}$settings = array_merge($this->_defaults, $config);if (in_array($settings['scope'], $Model->getAssociated('belongsTo'))) {$data = $Model->getAssociated($settings['scope']);$parent =& $Model->{$settings['scope']};$settings['scope'] = $Model->alias . '.' . $data['foreignKey'] . ' = ' . $parent->alias . '.' . $parent->primaryKey;$settings['recursive'] = 0;}$this->settings[$Model->alias] = $settings;}/*** After save method. Called after all saves** Overriden to transparently manage setting the lft and rght fields if and only if the parent field is included in the* parameters to be saved.** @param AppModel $Model* @param boolean $created indicates whether the node just saved was created or updated* @return boolean true on success, false on failure* @access public*/function afterSave(&$Model, $created) {extract($this->settings[$Model->alias]);if ($created) {if ((isset($Model->data[$Model->alias][$parent])) && $Model->data[$Model->alias][$parent]) {return $this->_setParent($Model, $Model->data[$Model->alias][$parent], $created);}} elseif ($__parentChange) {$this->settings[$Model->alias]['__parentChange'] = false;return $this->_setParent($Model, $Model->data[$Model->alias][$parent]);}}/*** Before delete method. Called before all deletes** Will delete the current node and all children using the deleteAll method and sync the table** @param AppModel $Model* @return boolean true to continue, false to abort the delete* @access public*/function beforeDelete(&$Model) {extract($this->settings[$Model->alias]);list($name, $data) = array($Model->alias, $Model->read());$data = $data[$name];if (!$data[$right] || !$data[$left]) {return true;}$diff = $data[$right] - $data[$left] + 1;if ($diff > 2) {if (is_string($scope)) {$scope = array($scope);}$scope[]["{$Model->alias}.{$left} BETWEEN ? AND ?"] = array($data[$left] + 1, $data[$right] - 1);$Model->deleteAll($scope);}$this->__sync($Model, $diff, '-', '> ' . $data[$right]);return true;}/*** Before save method. Called before all saves** Overriden to transparently manage setting the lft and rght fields if and only if the parent field is included in the* parameters to be saved. For newly created nodes with NO parent the left and right field values are set directly by* this method bypassing the setParent logic.** @since 1.2* @param AppModel $Model* @return boolean true to continue, false to abort the save* @access public*/function beforeSave(&$Model) {extract($this->settings[$Model->alias]);if (isset($Model->data[$Model->alias][$Model->primaryKey])) {if ($Model->data[$Model->alias][$Model->primaryKey]) {if (!$Model->id) {$Model->id = $Model->data[$Model->alias][$Model->primaryKey];}}unset($Model->data[$Model->alias][$Model->primaryKey]);}$this->_addToWhitelist($Model, array($left, $right));if (!$Model->id) {if (array_key_exists($parent, $Model->data[$Model->alias]) && $Model->data[$Model->alias][$parent]) {$parentNode = $Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $Model->data[$Model->alias][$parent]),'fields' => array($Model->primaryKey, $right), 'recursive' => $recursive));if (!$parentNode) {return false;}list($parentNode) = array_values($parentNode);$Model->data[$Model->alias][$left] = 0; //$parentNode[$right];$Model->data[$Model->alias][$right] = 0; //$parentNode[$right] + 1;} else {$edge = $this->__getMax($Model, $scope, $right, $recursive);$Model->data[$Model->alias][$left] = $edge + 1;$Model->data[$Model->alias][$right] = $edge + 2;}} elseif (array_key_exists($parent, $Model->data[$Model->alias])) {if ($Model->data[$Model->alias][$parent] != $Model->field($parent)) {$this->settings[$Model->alias]['__parentChange'] = true;}if (!$Model->data[$Model->alias][$parent]) {$Model->data[$Model->alias][$parent] = null;$this->_addToWhitelist($Model, $parent);} else {list($node) = array_values($Model->find('first', array('conditions' => array($scope,$Model->escapeField() => $Model->id),'fields' => array($Model->primaryKey, $parent, $left, $right ), 'recursive' => $recursive)));$parentNode = $Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $Model->data[$Model->alias][$parent]),'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive));if (!$parentNode) {return false;}list($parentNode) = array_values($parentNode);if (($node[$left] < $parentNode[$left]) && ($parentNode[$right] < $node[$right])) {return false;} elseif ($node[$Model->primaryKey] == $parentNode[$Model->primaryKey]) {return false;}}}return true;}/*** Get the number of child nodes** If the direct parameter is set to true, only the direct children are counted (based upon the parent_id field)* If false is passed for the id parameter, all top level nodes are counted, or all nodes are counted.** @param AppModel $Model* @param mixed $id The ID of the record to read or false to read all top level nodes* @param boolean $direct whether to count direct, or all, children* @return integer number of child nodes* @access public*/function childcount(&$Model, $id = null, $direct = false) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}if ($id === null && $Model->id) {$id = $Model->id;} elseif (!$id) {$id = null;}extract($this->settings[$Model->alias]);if ($direct) {return $Model->find('count', array('conditions' => array($scope, $Model->escapeField($parent) => $id)));}if ($id === null) {return $Model->find('count', array('conditions' => $scope));} elseif (isset($Model->data[$Model->alias][$left]) && isset($Model->data[$Model->alias][$right])) {$data = $Model->data[$Model->alias];} else {$data = $Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $id), 'recursive' => $recursive));if (!$data) {return 0;}$data = $data[$Model->alias];}return ($data[$right] - $data[$left] - 1) / 2;}/*** Get the child nodes of the current model** If the direct parameter is set to true, only the direct children are returned (based upon the parent_id field)* If false is passed for the id parameter, top level, or all (depending on direct parameter appropriate) are counted.** @param AppModel $Model* @param mixed $id The ID of the record to read* @param boolean $direct whether to return only the direct, or all, children* @param mixed $fields Either a single string of a field name, or an array of field names* @param string $order SQL ORDER BY conditions (e.g. "price DESC" or "name ASC") defaults to the tree order* @param integer $limit SQL LIMIT clause, for calculating items per page.* @param integer $page Page number, for accessing paged data* @param integer $recursive The number of levels deep to fetch associated records* @return array Array of child nodes* @access public*/function children(&$Model, $id = null, $direct = false, $fields = null, $order = null, $limit = null, $page = 1, $recursive = null) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}$overrideRecursive = $recursive;if ($id === null && $Model->id) {$id = $Model->id;} elseif (!$id) {$id = null;}$name = $Model->alias;extract($this->settings[$Model->alias]);if (!is_null($overrideRecursive)) {$recursive = $overrideRecursive;}if (!$order) {$order = $Model->alias . '.' . $left . ' asc';}if ($direct) {$conditions = array($scope, $Model->escapeField($parent) => $id);return $Model->find('all', compact('conditions', 'fields', 'order', 'limit', 'page', 'recursive'));}if (!$id) {$conditions = $scope;} else {$result = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $id),'fields' => array($left, $right),'recursive' => $recursive)));if (empty($result) || !isset($result[0])) {return array();}$conditions = array($scope,$Model->escapeField($right) . ' <' => $result[0][$right],$Model->escapeField($left) . ' >' => $result[0][$left]);}return $Model->find('all', compact('conditions', 'fields', 'order', 'limit', 'page', 'recursive'));}/*** A convenience method for returning a hierarchical array used for HTML select boxes** @param AppModel $Model* @param mixed $conditions SQL conditions as a string or as an array('field' =>'value',...)* @param string $keyPath A string path to the key, i.e. "{n}.Post.id"* @param string $valuePath A string path to the value, i.e. "{n}.Post.title"* @param string $spacer The character or characters which will be repeated* @param integer $recursive The number of levels deep to fetch associated records* @return array An associative array of records, where the id is the key, and the display field is the value* @access public*/function generatetreelist(&$Model, $conditions = null, $keyPath = null, $valuePath = null, $spacer = '_', $recursive = null) {$overrideRecursive = $recursive;extract($this->settings[$Model->alias]);if (!is_null($overrideRecursive)) {$recursive = $overrideRecursive;}if ($keyPath == null && $valuePath == null && $Model->hasField($Model->displayField)) {$fields = array($Model->primaryKey, $Model->displayField, $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);} elseif (is_string($valuePath)) {$valuePath = array('{0}{1}', '{n}.tree_prefix', $valuePath);} else {$valuePath[0] = '{' . (count($valuePath) - 1) . '}' . $valuePath[0];$valuePath[] = '{n}.tree_prefix';}$order = $Model->alias . '.' . $left . ' asc';$results = $Model->find('all', compact('conditions', 'fields', 'order', 'recursive'));$stack = array();foreach ($results as $i => $result) {while ($stack && ($stack[count($stack) - 1] < $result[$Model->alias][$right])) {array_pop($stack);}$results[$i]['tree_prefix'] = str_repeat($spacer,count($stack));$stack[] = $result[$Model->alias][$right];}if (empty($results)) {return array();}return Set::combine($results, $keyPath, $valuePath);}/*** Get the parent node** reads the parent id and returns this node** @param AppModel $Model* @param mixed $id The ID of the record to read* @param integer $recursive The number of levels deep to fetch associated records* @return array Array of data for the parent node* @access public*/function getparentnode(&$Model, $id = null, $fields = null, $recursive = null) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}$overrideRecursive = $recursive;if (empty ($id)) {$id = $Model->id;}extract($this->settings[$Model->alias]);if (!is_null($overrideRecursive)) {$recursive = $overrideRecursive;}$parentId = $Model->read($parent, $id);if ($parentId) {$parentId = $parentId[$Model->alias][$parent];$parent = $Model->find('first', array('conditions' => array($Model->escapeField() => $parentId), 'fields' => $fields, 'recursive' => $recursive));return $parent;}return false;}/*** Get the path to the given node** @param AppModel $Model* @param mixed $id The ID of the record to read* @param mixed $fields Either a single string of a field name, or an array of field names* @param integer $recursive The number of levels deep to fetch associated records* @return array Array of nodes from top most parent to current node* @access public*/function getpath(&$Model, $id = null, $fields = null, $recursive = null) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}$overrideRecursive = $recursive;if (empty ($id)) {$id = $Model->id;}extract($this->settings[$Model->alias]);if (!is_null($overrideRecursive)) {$recursive = $overrideRecursive;}$result = $Model->find('first', array('conditions' => array($Model->escapeField() => $id), 'fields' => array($left, $right), 'recursive' => $recursive));if ($result) {$result = array_values($result);} else {return null;}$item = $result[0];$results = $Model->find('all', array('conditions' => array($scope, $Model->escapeField($left) . ' <=' => $item[$left], $Model->escapeField($right) . ' >=' => $item[$right]),'fields' => $fields, 'order' => array($Model->escapeField($left) => 'asc'), 'recursive' => $recursive));return $results;}/*** Reorder the node without changing the parent.** If the node is the last child, or is a top level node with no subsequent node this method will return false** @param AppModel $Model* @param mixed $id The ID of the record to move* @param mixed $number how many places to move the node or true to move to last position* @return boolean true on success, false on failure* @access public*/function movedown(&$Model, $id = null, $number = 1) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}if (!$number) {return false;}if (empty ($id)) {$id = $Model->id;}extract($this->settings[$Model->alias]);list($node) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $id),'fields' => array($Model->primaryKey, $left, $right, $parent), 'recursive' => $recursive)));if ($node[$parent]) {list($parentNode) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $node[$parent]),'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive)));if (($node[$right] + 1) == $parentNode[$right]) {return false;}}$nextNode = $Model->find('first', array('conditions' => array($scope, $Model->escapeField($left) => ($node[$right] + 1)),'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive));if ($nextNode) {list($nextNode)= array_values($nextNode);} else {return false;}$edge = $this->__getMax($Model, $scope, $right, $recursive);$this->__sync($Model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right]);$this->__sync($Model, $nextNode[$left] - $node[$left], '-', 'BETWEEN ' . $nextNode[$left] . ' AND ' . $nextNode[$right]);$this->__sync($Model, $edge - $node[$left] - ($nextNode[$right] - $nextNode[$left]), '-', '> ' . $edge);if (is_int($number)) {$number--;}if ($number) {$this->moveDown($Model, $id, $number);}return true;}/*** Reorder the node without changing the parent.** If the node is the first child, or is a top level node with no previous node this method will return false** @param AppModel $Model* @param mixed $id The ID of the record to move* @param mixed $number how many places to move the node, or true to move to first position* @return boolean true on success, false on failure* @access public*/function moveup(&$Model, $id = null, $number = 1) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}if (!$number) {return false;}if (empty ($id)) {$id = $Model->id;}extract($this->settings[$Model->alias]);list($node) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $id),'fields' => array($Model->primaryKey, $left, $right, $parent ), 'recursive' => $recursive)));if ($node[$parent]) {list($parentNode) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $node[$parent]),'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive)));if (($node[$left] - 1) == $parentNode[$left]) {return false;}}$previousNode = $Model->find('first', array('conditions' => array($scope, $Model->escapeField($right) => ($node[$left] - 1)),'fields' => array($Model->primaryKey, $left, $right),'recursive' => $recursive));if ($previousNode) {list($previousNode) = array_values($previousNode);} else {return false;}$edge = $this->__getMax($Model, $scope, $right, $recursive);$this->__sync($Model, $edge - $previousNode[$left] +1, '+', 'BETWEEN ' . $previousNode[$left] . ' AND ' . $previousNode[$right]);$this->__sync($Model, $node[$left] - $previousNode[$left], '-', 'BETWEEN ' .$node[$left] . ' AND ' . $node[$right]);$this->__sync($Model, $edge - $previousNode[$left] - ($node[$right] - $node[$left]), '-', '> ' . $edge);if (is_int($number)) {$number--;}if ($number) {$this->moveUp($Model, $id, $number);}return true;}/*** Recover a corrupted tree** The mode parameter is used to specify the source of info that is valid/correct. The opposite source of data* will be populated based upon that source of info. E.g. if the MPTT fields are corrupt or empty, with the $mode* 'parent' the values of the parent_id field will be used to populate the left and right fields. The missingParentAction* parameter only applies to "parent" mode and determines what to do if the parent field contains an id that is not present.** @todo Could be written to be faster, *maybe*. Ideally using a subquery and putting all the logic burden on the DB.* @param AppModel $Model* @param string $mode parent or tree* @param mixed $missingParentAction 'return' to do nothing and return, 'delete' to* delete, or the id of the parent to set as the parent_id* @return boolean true on success, false on failure* @access public*/function recover(&$Model, $mode = 'parent', $missingParentAction = null) {if (is_array($mode)) {extract (array_merge(array('mode' => 'parent'), $mode));}extract($this->settings[$Model->alias]);$Model->recursive = $recursive;if ($mode == 'parent') {$Model->bindModel(array('belongsTo' => array('VerifyParent' => array('className' => $Model->alias,'foreignKey' => $parent,'fields' => array($Model->primaryKey, $left, $right, $parent),))));$missingParents = $Model->find('list', array('recursive' => 0,'conditions' => array($scope, array('NOT' => array($Model->escapeField($parent) => null), $Model->VerifyParent->escapeField() => null))));$Model->unbindModel(array('belongsTo' => array('VerifyParent')));if ($missingParents) {if ($missingParentAction == 'return') {foreach ($missingParents as $id => $display) {$this->errors[] = 'cannot find the parent for ' . $Model->alias . ' with id ' . $id . '(' . $display . ')';}return false;} elseif ($missingParentAction == 'delete') {$Model->deleteAll(array($Model->primaryKey => array_flip($missingParents)));} else {$Model->updateAll(array($parent => $missingParentAction), array($Model->escapeField($Model->primaryKey) => array_flip($missingParents)));}}$count = 1;foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey), 'order' => $left)) as $array) {$Model->id = $array[$Model->alias][$Model->primaryKey];$lft = $count++;$rght = $count++;$Model->save(array($left => $lft, $right => $rght), array('callbacks' => false));}foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey, $parent), 'order' => $left)) as $array) {$Model->create();$Model->id = $array[$Model->alias][$Model->primaryKey];$this->_setParent($Model, $array[$Model->alias][$parent]);}} else {$db =& ConnectionManager::getDataSource($Model->useDbConfig);foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey, $parent), 'order' => $left)) as $array) {$path = $this->getpath($Model, $array[$Model->alias][$Model->primaryKey]);if ($path == null || count($path) < 2) {$parentId = null;} else {$parentId = $path[count($path) - 2][$Model->alias][$Model->primaryKey];}$Model->updateAll(array($parent => $db->value($parentId, $parent)), array($Model->escapeField() => $array[$Model->alias][$Model->primaryKey]));}}return true;}/*** Reorder method.** Reorders the nodes (and child nodes) of the tree according to the field and direction specified in the parameters.* This method does not change the parent of any node.** Requires a valid tree, by default it verifies the tree before beginning.** @param AppModel $Model* @param array $options* @return boolean true on success, false on failure*/function reorder(&$Model, $options = array()) {$options = array_merge(array('id' => null, 'field' => $Model->displayField, 'order' => 'ASC', 'verify' => true), $options);extract($options);if ($verify && !$this->verify($Model)) {return false;}$verify = false;extract($this->settings[$Model->alias]);$fields = array($Model->primaryKey, $field, $left, $right);$sort = $field . ' ' . $order;$nodes = $this->children($Model, $id, true, $fields, $sort, null, null, $recursive);if ($nodes) {foreach ($nodes as $node) {$id = $node[$Model->alias][$Model->primaryKey];$this->moveDown($Model, $id, true);if ($node[$Model->alias][$left] != $node[$Model->alias][$right] - 1) {$this->reorder($Model, compact('id', 'field', 'order', 'verify'));}}}return true;}/*** Remove the current node from the tree, and reparent all children up one level.** If the parameter delete is false, the node will become a new top level node. Otherwise the node will be deleted* after the children are reparented.** @param AppModel $Model* @param mixed $id The ID of the record to remove* @param boolean $delete whether to delete the node after reparenting children (if any)* @return boolean true on success, false on failure* @access public*/function removefromtree(&$Model, $id = null, $delete = false) {if (is_array($id)) {extract (array_merge(array('id' => null), $id));}extract($this->settings[$Model->alias]);list($node) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $id),'fields' => array($Model->primaryKey, $left, $right, $parent),'recursive' => $recursive)));if ($node[$right] == $node[$left] + 1) {if ($delete) {return $Model->delete($id);} else {$Model->id = $id;return $Model->saveField($parent, null);}} elseif ($node[$parent]) {list($parentNode) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $node[$parent]),'fields' => array($Model->primaryKey, $left, $right),'recursive' => $recursive)));} else {$parentNode[$right] = $node[$right] + 1;}$db =& ConnectionManager::getDataSource($Model->useDbConfig);$Model->updateAll(array($parent => $db->value($node[$parent], $parent)), array($parent => $node[$Model->primaryKey]));$this->__sync($Model, 1, '-', 'BETWEEN ' . ($node[$left] + 1) . ' AND ' . ($node[$right] - 1));$this->__sync($Model, 2, '-', '> ' . ($node[$right]));$Model->id = $id;if ($delete) {$Model->updateAll(array($Model->escapeField($left) => 0,$Model->escapeField($right) => 0,$Model->escapeField($parent) => null),array($Model->escapeField() => $id));return $Model->delete($id);} else {$edge = $this->__getMax($Model, $scope, $right, $recursive);if ($node[$right] == $edge) {$edge = $edge - 2;}$Model->id = $id;return $Model->save(array($left => $edge + 1, $right => $edge + 2, $parent => null),array('callbacks' => false));}}/*** Check if the current tree is valid.** Returns true if the tree is valid otherwise an array of (type, incorrect left/right index, message)** @param AppModel $Model* @return mixed true if the tree is valid or empty, otherwise an array of (error type [index, node],* [incorrect left/right index,node id], message)* @access public*/function verify(&$Model) {extract($this->settings[$Model->alias]);if (!$Model->find('count', array('conditions' => $scope))) {return true;}$min = $this->__getMin($Model, $scope, $left, $recursive);$edge = $this->__getMax($Model, $scope, $right, $recursive);$errors = array();for ($i = $min; $i <= $edge; $i++) {$count = $Model->find('count', array('conditions' => array($scope, 'OR' => array($Model->escapeField($left) => $i, $Model->escapeField($right) => $i))));if ($count != 1) {if ($count == 0) {$errors[] = array('index', $i, 'missing');} else {$errors[] = array('index', $i, 'duplicate');}}}$node = $Model->find('first', array('conditions' => array($scope, $Model->escapeField($right) . '< ' . $Model->escapeField($left)), 'recursive' => 0));if ($node) {$errors[] = array('node', $node[$Model->alias][$Model->primaryKey], 'left greater than right.');}$Model->bindModel(array('belongsTo' => array('VerifyParent' => array('className' => $Model->alias,'foreignKey' => $parent,'fields' => array($Model->primaryKey, $left, $right, $parent)))));foreach ($Model->find('all', array('conditions' => $scope, 'recursive' => 0)) as $instance) {if (is_null($instance[$Model->alias][$left]) || is_null($instance[$Model->alias][$right])) {$errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],'has invalid left or right values');} elseif ($instance[$Model->alias][$left] == $instance[$Model->alias][$right]) {$errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],'left and right values identical');} elseif ($instance[$Model->alias][$parent]) {if (!$instance['VerifyParent'][$Model->primaryKey]) {$errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],'The parent node ' . $instance[$Model->alias][$parent] . ' doesn\'t exist');} elseif ($instance[$Model->alias][$left] < $instance['VerifyParent'][$left]) {$errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],'left less than parent (node ' . $instance['VerifyParent'][$Model->primaryKey] . ').');} elseif ($instance[$Model->alias][$right] > $instance['VerifyParent'][$right]) {$errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],'right greater than parent (node ' . $instance['VerifyParent'][$Model->primaryKey] . ').');}} elseif ($Model->find('count', array('conditions' => array($scope, $Model->escapeField($left) . ' <' => $instance[$Model->alias][$left], $Model->escapeField($right) . ' >' => $instance[$Model->alias][$right]), 'recursive' => 0))) {$errors[] = array('node', $instance[$Model->alias][$Model->primaryKey], 'The parent field is blank, but has a parent');}}if ($errors) {return $errors;}return true;}/*** Sets the parent of the given node** The force parameter is used to override the "don't change the parent to the current parent" logic in the event* of recovering a corrupted table, or creating new nodes. Otherwise it should always be false. In reality this* method could be private, since calling save with parent_id set also calls setParent** @param AppModel $Model* @param mixed $parentId* @return boolean true on success, false on failure* @access protected*/function _setParent(&$Model, $parentId = null, $created = false) {extract($this->settings[$Model->alias]);list($node) = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $Model->id),'fields' => array($Model->primaryKey, $parent, $left, $right),'recursive' => $recursive)));$edge = $this->__getMax($Model, $scope, $right, $recursive, $created);if (empty ($parentId)) {$this->__sync($Model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);$this->__sync($Model, $node[$right] - $node[$left] + 1, '-', '> ' . $node[$left], $created);} else {$parentNode = array_values($Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $parentId),'fields' => array($Model->primaryKey, $left, $right),'recursive' => $recursive)));if (empty($parentNode) || empty($parentNode[0])) {return false;}$parentNode = $parentNode[0];if (($Model->id == $parentId)) {return false;} elseif (($node[$left] < $parentNode[$left]) && ($parentNode[$right] < $node[$right])) {return false;}if (empty ($node[$left]) && empty ($node[$right])) {$this->__sync($Model, 2, '+', '>= ' . $parentNode[$right], $created);$result = $Model->save(array($left => $parentNode[$right], $right => $parentNode[$right] + 1, $parent => $parentId),array('validate' => false, 'callbacks' => false));$Model->data = $result;} else {$this->__sync($Model, $edge - $node[$left] +1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);$diff = $node[$right] - $node[$left] + 1;if ($node[$left] > $parentNode[$left]) {if ($node[$right] < $parentNode[$right]) {$this->__sync($Model, $diff, '-', 'BETWEEN ' . $node[$right] . ' AND ' . ($parentNode[$right] - 1), $created);$this->__sync($Model, $edge - $parentNode[$right] + $diff + 1, '-', '> ' . $edge, $created);} else {$this->__sync($Model, $diff, '+', 'BETWEEN ' . $parentNode[$right] . ' AND ' . $node[$right], $created);$this->__sync($Model, $edge - $parentNode[$right] + 1, '-', '> ' . $edge, $created);}} else {$this->__sync($Model, $diff, '-', 'BETWEEN ' . $node[$right] . ' AND ' . ($parentNode[$right] - 1), $created);$this->__sync($Model, $edge - $parentNode[$right] + $diff + 1, '-', '> ' . $edge, $created);}}}return true;}/*** get the maximum index value in the table.** @param AppModel $Model* @param string $scope* @param string $right* @return int* @access private*/function __getMax($Model, $scope, $right, $recursive = -1, $created = false) {$db =& ConnectionManager::getDataSource($Model->useDbConfig);if ($created) {if (is_string($scope)) {$scope .= " AND {$Model->alias}.{$Model->primaryKey} <> ";$scope .= $db->value($Model->id, $Model->getColumnType($Model->primaryKey));} else {$scope['NOT'][$Model->alias . '.' . $Model->primaryKey] = $Model->id;}}list($edge) = array_values($Model->find('first', array('conditions' => $scope,'fields' => $db->calculate($Model, 'max', array($right)),'recursive' => $recursive)));return (empty($edge[$right])) ? 0 : $edge[$right];}/*** get the minimum index value in the table.** @param AppModel $Model* @param string $scope* @param string $right* @return int* @access private*/function __getMin($Model, $scope, $left, $recursive = -1) {$db =& ConnectionManager::getDataSource($Model->useDbConfig);list($edge) = array_values($Model->find('first', array('conditions' => $scope,'fields' => $db->calculate($Model, 'min', array($left)),'recursive' => $recursive)));return (empty($edge[$left])) ? 0 : $edge[$left];}/*** Table sync method.** Handles table sync operations, Taking account of the behavior scope.** @param AppModel $Model* @param integer $shift* @param string $direction* @param array $conditions* @param string $field* @access private*/function __sync(&$Model, $shift, $dir = '+', $conditions = array(), $created = false, $field = 'both') {$ModelRecursive = $Model->recursive;extract($this->settings[$Model->alias]);$Model->recursive = $recursive;if ($field == 'both') {$this->__sync($Model, $shift, $dir, $conditions, $created, $left);$field = $right;}if (is_string($conditions)) {$conditions = array("{$Model->alias}.{$field} {$conditions}");}if (($scope != '1 = 1' && $scope !== true) && $scope) {$conditions[] = $scope;}if ($created) {$conditions['NOT'][$Model->alias . '.' . $Model->primaryKey] = $Model->id;}$Model->updateAll(array($Model->alias . '.' . $field => $Model->escapeField($field) . ' ' . $dir . ' ' . $shift), $conditions);$Model->recursive = $ModelRecursive;}}?>