1: <?php
   2: /**
   3:  * Tree behavior class.
   4:  *
   5:  * Enables a model object to act as a node-based tree.
   6:  *
   7:  * PHP 5
   8:  *
   9:  * CakePHP :  Rapid Development Framework (http://cakephp.org)
  10:  * Copyright (c) Cake Software Foundation, Inc. (http://cakefoundation.org)
  11:  *
  12:  * Licensed under The MIT License
  13:  * For full copyright and license information, please see the LICENSE.txt
  14:  * Redistributions of files must retain the above copyright notice.
  15:  *
  16:  * @copyright     Copyright (c) Cake Software Foundation, Inc. (http://cakefoundation.org)
  17:  * @link          http://cakephp.org CakePHP Project
  18:  * @package       Cake.Model.Behavior
  19:  * @since         CakePHP v 1.2.0.4487
  20:  * @license       http://www.opensource.org/licenses/mit-license.php MIT License
  21:  */
  22: 
  23: App::uses('ModelBehavior', 'Model');
  24: 
  25: /**
  26:  * Tree Behavior.
  27:  *
  28:  * Enables a model object to act as a node-based tree. Using Modified Preorder Tree Traversal
  29:  *
  30:  * @see http://en.wikipedia.org/wiki/Tree_traversal
  31:  * @package       Cake.Model.Behavior
  32:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html
  33:  */
  34: class TreeBehavior extends ModelBehavior {
  35: 
  36: /**
  37:  * Errors
  38:  *
  39:  * @var array
  40:  */
  41:     public $errors = array();
  42: 
  43: /**
  44:  * Defaults
  45:  *
  46:  * @var array
  47:  */
  48:     protected $_defaults = array(
  49:         'parent' => 'parent_id', 'left' => 'lft', 'right' => 'rght',
  50:         'scope' => '1 = 1', 'type' => 'nested', '__parentChange' => false, 'recursive' => -1
  51:     );
  52: 
  53: /**
  54:  * Used to preserve state between delete callbacks.
  55:  *
  56:  * @var array
  57:  */
  58:     protected $_deletedRow = array();
  59: 
  60: /**
  61:  * Initiate Tree behavior
  62:  *
  63:  * @param Model $Model instance of model
  64:  * @param array $config array of configuration settings.
  65:  * @return void
  66:  */
  67:     public function setup(Model $Model, $config = array()) {
  68:         if (isset($config[0])) {
  69:             $config['type'] = $config[0];
  70:             unset($config[0]);
  71:         }
  72:         $settings = array_merge($this->_defaults, $config);
  73: 
  74:         if (in_array($settings['scope'], $Model->getAssociated('belongsTo'))) {
  75:             $data = $Model->getAssociated($settings['scope']);
  76:             $Parent = $Model->{$settings['scope']};
  77:             $settings['scope'] = $Model->escapeField($data['foreignKey']) . ' = ' . $Parent->escapeField();
  78:             $settings['recursive'] = 0;
  79:         }
  80:         $this->settings[$Model->alias] = $settings;
  81:     }
  82: 
  83: /**
  84:  * After save method. Called after all saves
  85:  *
  86:  * Overridden to transparently manage setting the lft and rght fields if and only if the parent field is included in the
  87:  * parameters to be saved.
  88:  *
  89:  * @param Model $Model Model instance.
  90:  * @param boolean $created indicates whether the node just saved was created or updated
  91:  * @return boolean true on success, false on failure
  92:  */
  93:     public function afterSave(Model $Model, $created) {
  94:         extract($this->settings[$Model->alias]);
  95:         if ($created) {
  96:             if ((isset($Model->data[$Model->alias][$parent])) && $Model->data[$Model->alias][$parent]) {
  97:                 return $this->_setParent($Model, $Model->data[$Model->alias][$parent], $created);
  98:             }
  99:         } elseif ($this->settings[$Model->alias]['__parentChange']) {
 100:             $this->settings[$Model->alias]['__parentChange'] = false;
 101:             return $this->_setParent($Model, $Model->data[$Model->alias][$parent]);
 102:         }
 103:     }
 104: 
 105: /**
 106:  * Runs before a find() operation
 107:  *
 108:  * @param Model $Model Model using the behavior
 109:  * @param array $query Query parameters as set by cake
 110:  * @return array
 111:  */
 112:     public function beforeFind(Model $Model, $query) {
 113:         if ($Model->findQueryType === 'threaded' && !isset($query['parent'])) {
 114:             $query['parent'] = $this->settings[$Model->alias]['parent'];
 115:         }
 116:         return $query;
 117:     }
 118: 
 119: /**
 120:  * Stores the record about to be deleted.
 121:  *
 122:  * This is used to delete child nodes in the afterDelete.
 123:  *
 124:  * @param Model $Model Model instance
 125:  * @param boolean $cascade
 126:  * @return boolean
 127:  */
 128:     public function beforeDelete(Model $Model, $cascade = true) {
 129:         extract($this->settings[$Model->alias]);
 130:         $data = $Model->find('first', array(
 131:             'conditions' => array($Model->escapeField($Model->primaryKey) => $Model->id),
 132:             'fields' => array($Model->escapeField($left), $Model->escapeField($right)),
 133:             'recursive' => -1));
 134:         if ($data) {
 135:             $this->_deletedRow[$Model->alias] = current($data);
 136:         }
 137:         return true;
 138:     }
 139: 
 140: /**
 141:  * After delete method.
 142:  *
 143:  * Will delete the current node and all children using the deleteAll method and sync the table
 144:  *
 145:  * @param Model $Model Model instance
 146:  * @return boolean true to continue, false to abort the delete
 147:  */
 148:     public function afterDelete(Model $Model) {
 149:         extract($this->settings[$Model->alias]);
 150:         $data = $this->_deletedRow[$Model->alias];
 151:         $this->_deletedRow[$Model->alias] = null;
 152: 
 153:         if (!$data[$right] || !$data[$left]) {
 154:             return true;
 155:         }
 156:         $diff = $data[$right] - $data[$left] + 1;
 157: 
 158:         if ($diff > 2) {
 159:             if (is_string($scope)) {
 160:                 $scope = array($scope);
 161:             }
 162:             $scope[][$Model->escapeField($left) . " BETWEEN ? AND ?"] = array($data[$left] + 1, $data[$right] - 1);
 163:             $Model->deleteAll($scope);
 164:         }
 165:         $this->_sync($Model, $diff, '-', '> ' . $data[$right]);
 166:         return true;
 167:     }
 168: 
 169: /**
 170:  * Before save method. Called before all saves
 171:  *
 172:  * Overridden to transparently manage setting the lft and rght fields if and only if the parent field is included in the
 173:  * parameters to be saved. For newly created nodes with NO parent the left and right field values are set directly by
 174:  * this method bypassing the setParent logic.
 175:  *
 176:  * @since         1.2
 177:  * @param Model $Model Model instance
 178:  * @return boolean true to continue, false to abort the save
 179:  */
 180:     public function beforeSave(Model $Model) {
 181:         extract($this->settings[$Model->alias]);
 182: 
 183:         $this->_addToWhitelist($Model, array($left, $right));
 184:         if (!$Model->id || !$Model->exists()) {
 185:             if (array_key_exists($parent, $Model->data[$Model->alias]) && $Model->data[$Model->alias][$parent]) {
 186:                 $parentNode = $Model->find('first', array(
 187:                     'conditions' => array($scope, $Model->escapeField() => $Model->data[$Model->alias][$parent]),
 188:                     'fields' => array($Model->primaryKey, $right), 'recursive' => $recursive
 189:                 ));
 190:                 if (!$parentNode) {
 191:                     return false;
 192:                 }
 193:                 list($parentNode) = array_values($parentNode);
 194:                 $Model->data[$Model->alias][$left] = 0;
 195:                 $Model->data[$Model->alias][$right] = 0;
 196:             } else {
 197:                 $edge = $this->_getMax($Model, $scope, $right, $recursive);
 198:                 $Model->data[$Model->alias][$left] = $edge + 1;
 199:                 $Model->data[$Model->alias][$right] = $edge + 2;
 200:             }
 201:         } elseif (array_key_exists($parent, $Model->data[$Model->alias])) {
 202:             if ($Model->data[$Model->alias][$parent] != $Model->field($parent)) {
 203:                 $this->settings[$Model->alias]['__parentChange'] = true;
 204:             }
 205:             if (!$Model->data[$Model->alias][$parent]) {
 206:                 $Model->data[$Model->alias][$parent] = null;
 207:                 $this->_addToWhitelist($Model, $parent);
 208:             } else {
 209:                 $values = $Model->find('first', array(
 210:                     'conditions' => array($scope, $Model->escapeField() => $Model->id),
 211:                     'fields' => array($Model->primaryKey, $parent, $left, $right), 'recursive' => $recursive)
 212:                 );
 213: 
 214:                 if ($values === false) {
 215:                     return false;
 216:                 }
 217:                 list($node) = array_values($values);
 218: 
 219:                 $parentNode = $Model->find('first', array(
 220:                     'conditions' => array($scope, $Model->escapeField() => $Model->data[$Model->alias][$parent]),
 221:                     'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive
 222:                 ));
 223:                 if (!$parentNode) {
 224:                     return false;
 225:                 }
 226:                 list($parentNode) = array_values($parentNode);
 227: 
 228:                 if (($node[$left] < $parentNode[$left]) && ($parentNode[$right] < $node[$right])) {
 229:                     return false;
 230:                 } elseif ($node[$Model->primaryKey] == $parentNode[$Model->primaryKey]) {
 231:                     return false;
 232:                 }
 233:             }
 234:         }
 235:         return true;
 236:     }
 237: 
 238: /**
 239:  * Get the number of child nodes
 240:  *
 241:  * If the direct parameter is set to true, only the direct children are counted (based upon the parent_id field)
 242:  * If false is passed for the id parameter, all top level nodes are counted, or all nodes are counted.
 243:  *
 244:  * @param Model $Model Model instance
 245:  * @param integer|string|boolean $id The ID of the record to read or false to read all top level nodes
 246:  * @param boolean $direct whether to count direct, or all, children
 247:  * @return integer number of child nodes
 248:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::childCount
 249:  */
 250:     public function childCount(Model $Model, $id = null, $direct = false) {
 251:         if (is_array($id)) {
 252:             extract(array_merge(array('id' => null), $id));
 253:         }
 254:         if ($id === null && $Model->id) {
 255:             $id = $Model->id;
 256:         } elseif (!$id) {
 257:             $id = null;
 258:         }
 259:         extract($this->settings[$Model->alias]);
 260: 
 261:         if ($direct) {
 262:             return $Model->find('count', array('conditions' => array($scope, $Model->escapeField($parent) => $id)));
 263:         }
 264: 
 265:         if ($id === null) {
 266:             return $Model->find('count', array('conditions' => $scope));
 267:         } elseif ($Model->id === $id && isset($Model->data[$Model->alias][$left]) && isset($Model->data[$Model->alias][$right])) {
 268:             $data = $Model->data[$Model->alias];
 269:         } else {
 270:             $data = $Model->find('first', array('conditions' => array($scope, $Model->escapeField() => $id), 'recursive' => $recursive));
 271:             if (!$data) {
 272:                 return 0;
 273:             }
 274:             $data = $data[$Model->alias];
 275:         }
 276:         return ($data[$right] - $data[$left] - 1) / 2;
 277:     }
 278: 
 279: /**
 280:  * Get the child nodes of the current model
 281:  *
 282:  * If the direct parameter is set to true, only the direct children are returned (based upon the parent_id field)
 283:  * If false is passed for the id parameter, top level, or all (depending on direct parameter appropriate) are counted.
 284:  *
 285:  * @param Model $Model Model instance
 286:  * @param integer|string $id The ID of the record to read
 287:  * @param boolean $direct whether to return only the direct, or all, children
 288:  * @param string|array $fields Either a single string of a field name, or an array of field names
 289:  * @param string $order SQL ORDER BY conditions (e.g. "price DESC" or "name ASC") defaults to the tree order
 290:  * @param integer $limit SQL LIMIT clause, for calculating items per page.
 291:  * @param integer $page Page number, for accessing paged data
 292:  * @param integer $recursive The number of levels deep to fetch associated records
 293:  * @return array Array of child nodes
 294:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::children
 295:  */
 296:     public function children(Model $Model, $id = null, $direct = false, $fields = null, $order = null, $limit = null, $page = 1, $recursive = null) {
 297:         if (is_array($id)) {
 298:             extract(array_merge(array('id' => null), $id));
 299:         }
 300:         $overrideRecursive = $recursive;
 301: 
 302:         if ($id === null && $Model->id) {
 303:             $id = $Model->id;
 304:         } elseif (!$id) {
 305:             $id = null;
 306:         }
 307: 
 308:         extract($this->settings[$Model->alias]);
 309: 
 310:         if ($overrideRecursive !== null) {
 311:             $recursive = $overrideRecursive;
 312:         }
 313:         if (!$order) {
 314:             $order = $Model->escapeField($left) . " asc";
 315:         }
 316:         if ($direct) {
 317:             $conditions = array($scope, $Model->escapeField($parent) => $id);
 318:             return $Model->find('all', compact('conditions', 'fields', 'order', 'limit', 'page', 'recursive'));
 319:         }
 320: 
 321:         if (!$id) {
 322:             $conditions = $scope;
 323:         } else {
 324:             $result = array_values((array)$Model->find('first', array(
 325:                 'conditions' => array($scope, $Model->escapeField() => $id),
 326:                 'fields' => array($left, $right),
 327:                 'recursive' => $recursive
 328:             )));
 329: 
 330:             if (empty($result) || !isset($result[0])) {
 331:                 return array();
 332:             }
 333:             $conditions = array($scope,
 334:                 $Model->escapeField($right) . ' <' => $result[0][$right],
 335:                 $Model->escapeField($left) . ' >' => $result[0][$left]
 336:             );
 337:         }
 338:         return $Model->find('all', compact('conditions', 'fields', 'order', 'limit', 'page', 'recursive'));
 339:     }
 340: 
 341: /**
 342:  * A convenience method for returning a hierarchical array used for HTML select boxes
 343:  *
 344:  * @param Model $Model Model instance
 345:  * @param string|array $conditions SQL conditions as a string or as an array('field' =>'value',...)
 346:  * @param string $keyPath A string path to the key, i.e. "{n}.Post.id"
 347:  * @param string $valuePath A string path to the value, i.e. "{n}.Post.title"
 348:  * @param string $spacer The character or characters which will be repeated
 349:  * @param integer $recursive The number of levels deep to fetch associated records
 350:  * @return array An associative array of records, where the id is the key, and the display field is the value
 351:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::generateTreeList
 352:  */
 353:     public function generateTreeList(Model $Model, $conditions = null, $keyPath = null, $valuePath = null, $spacer = '_', $recursive = null) {
 354:         $overrideRecursive = $recursive;
 355:         extract($this->settings[$Model->alias]);
 356:         if ($overrideRecursive !== null) {
 357:             $recursive = $overrideRecursive;
 358:         }
 359: 
 360:         $fields = null;
 361:         if (!$keyPath && !$valuePath && $Model->hasField($Model->displayField)) {
 362:             $fields = array($Model->primaryKey, $Model->displayField, $left, $right);
 363:         }
 364: 
 365:         if (!$keyPath) {
 366:             $keyPath = '{n}.' . $Model->alias . '.' . $Model->primaryKey;
 367:         }
 368: 
 369:         if (!$valuePath) {
 370:             $valuePath = array('%s%s', '{n}.tree_prefix', '{n}.' . $Model->alias . '.' . $Model->displayField);
 371: 
 372:         } elseif (is_string($valuePath)) {
 373:             $valuePath = array('%s%s', '{n}.tree_prefix', $valuePath);
 374: 
 375:         } else {
 376:             array_unshift($valuePath, '%s' . $valuePath[0], '{n}.tree_prefix');
 377:         }
 378:         $order = $Model->escapeField($left) . " asc";
 379:         $results = $Model->find('all', compact('conditions', 'fields', 'order', 'recursive'));
 380:         $stack = array();
 381: 
 382:         foreach ($results as $i => $result) {
 383:             $count = count($stack);
 384:             while ($stack && ($stack[$count - 1] < $result[$Model->alias][$right])) {
 385:                 array_pop($stack);
 386:                 $count--;
 387:             }
 388:             $results[$i]['tree_prefix'] = str_repeat($spacer, $count);
 389:             $stack[] = $result[$Model->alias][$right];
 390:         }
 391:         if (empty($results)) {
 392:             return array();
 393:         }
 394:         return Hash::combine($results, $keyPath, $valuePath);
 395:     }
 396: 
 397: /**
 398:  * Get the parent node
 399:  *
 400:  * reads the parent id and returns this node
 401:  *
 402:  * @param Model $Model Model instance
 403:  * @param integer|string $id The ID of the record to read
 404:  * @param string|array $fields
 405:  * @param integer $recursive The number of levels deep to fetch associated records
 406:  * @return array|boolean Array of data for the parent node
 407:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::getParentNode
 408:  */
 409:     public function getParentNode(Model $Model, $id = null, $fields = null, $recursive = null) {
 410:         if (is_array($id)) {
 411:             extract(array_merge(array('id' => null), $id));
 412:         }
 413:         $overrideRecursive = $recursive;
 414:         if (empty($id)) {
 415:             $id = $Model->id;
 416:         }
 417:         extract($this->settings[$Model->alias]);
 418:         if ($overrideRecursive !== null) {
 419:             $recursive = $overrideRecursive;
 420:         }
 421:         $parentId = $Model->find('first', array('conditions' => array($Model->primaryKey => $id), 'fields' => array($parent), 'recursive' => -1));
 422: 
 423:         if ($parentId) {
 424:             $parentId = $parentId[$Model->alias][$parent];
 425:             $parent = $Model->find('first', array('conditions' => array($Model->escapeField() => $parentId), 'fields' => $fields, 'recursive' => $recursive));
 426: 
 427:             return $parent;
 428:         }
 429:         return false;
 430:     }
 431: 
 432: /**
 433:  * Get the path to the given node
 434:  *
 435:  * @param Model $Model Model instance
 436:  * @param integer|string $id The ID of the record to read
 437:  * @param string|array $fields Either a single string of a field name, or an array of field names
 438:  * @param integer $recursive The number of levels deep to fetch associated records
 439:  * @return array Array of nodes from top most parent to current node
 440:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::getPath
 441:  */
 442:     public function getPath(Model $Model, $id = null, $fields = null, $recursive = null) {
 443:         if (is_array($id)) {
 444:             extract(array_merge(array('id' => null), $id));
 445:         }
 446:         $overrideRecursive = $recursive;
 447:         if (empty($id)) {
 448:             $id = $Model->id;
 449:         }
 450:         extract($this->settings[$Model->alias]);
 451:         if ($overrideRecursive !== null) {
 452:             $recursive = $overrideRecursive;
 453:         }
 454:         $result = $Model->find('first', array('conditions' => array($Model->escapeField() => $id), 'fields' => array($left, $right), 'recursive' => $recursive));
 455:         if ($result) {
 456:             $result = array_values($result);
 457:         } else {
 458:             return null;
 459:         }
 460:         $item = $result[0];
 461:         $results = $Model->find('all', array(
 462:             'conditions' => array($scope, $Model->escapeField($left) . ' <=' => $item[$left], $Model->escapeField($right) . ' >=' => $item[$right]),
 463:             'fields' => $fields, 'order' => array($Model->escapeField($left) => 'asc'), 'recursive' => $recursive
 464:         ));
 465:         return $results;
 466:     }
 467: 
 468: /**
 469:  * Reorder the node without changing the parent.
 470:  *
 471:  * If the node is the last child, or is a top level node with no subsequent node this method will return false
 472:  *
 473:  * @param Model $Model Model instance
 474:  * @param integer|string $id The ID of the record to move
 475:  * @param integer|boolean $number how many places to move the node or true to move to last position
 476:  * @return boolean true on success, false on failure
 477:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::moveDown
 478:  */
 479:     public function moveDown(Model $Model, $id = null, $number = 1) {
 480:         if (is_array($id)) {
 481:             extract(array_merge(array('id' => null), $id));
 482:         }
 483:         if (!$number) {
 484:             return false;
 485:         }
 486:         if (empty($id)) {
 487:             $id = $Model->id;
 488:         }
 489:         extract($this->settings[$Model->alias]);
 490:         list($node) = array_values($Model->find('first', array(
 491:             'conditions' => array($scope, $Model->escapeField() => $id),
 492:             'fields' => array($Model->primaryKey, $left, $right, $parent), 'recursive' => $recursive
 493:         )));
 494:         if ($node[$parent]) {
 495:             list($parentNode) = array_values($Model->find('first', array(
 496:                 'conditions' => array($scope, $Model->escapeField() => $node[$parent]),
 497:                 'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive
 498:             )));
 499:             if (($node[$right] + 1) == $parentNode[$right]) {
 500:                 return false;
 501:             }
 502:         }
 503:         $nextNode = $Model->find('first', array(
 504:             'conditions' => array($scope, $Model->escapeField($left) => ($node[$right] + 1)),
 505:             'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive)
 506:         );
 507:         if ($nextNode) {
 508:             list($nextNode) = array_values($nextNode);
 509:         } else {
 510:             return false;
 511:         }
 512:         $edge = $this->_getMax($Model, $scope, $right, $recursive);
 513:         $this->_sync($Model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right]);
 514:         $this->_sync($Model, $nextNode[$left] - $node[$left], '-', 'BETWEEN ' . $nextNode[$left] . ' AND ' . $nextNode[$right]);
 515:         $this->_sync($Model, $edge - $node[$left] - ($nextNode[$right] - $nextNode[$left]), '-', '> ' . $edge);
 516: 
 517:         if (is_int($number)) {
 518:             $number--;
 519:         }
 520:         if ($number) {
 521:             $this->moveDown($Model, $id, $number);
 522:         }
 523:         return true;
 524:     }
 525: 
 526: /**
 527:  * Reorder the node without changing the parent.
 528:  *
 529:  * If the node is the first child, or is a top level node with no previous node this method will return false
 530:  *
 531:  * @param Model $Model Model instance
 532:  * @param integer|string $id The ID of the record to move
 533:  * @param integer|boolean $number how many places to move the node, or true to move to first position
 534:  * @return boolean true on success, false on failure
 535:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::moveUp
 536:  */
 537:     public function moveUp(Model $Model, $id = null, $number = 1) {
 538:         if (is_array($id)) {
 539:             extract(array_merge(array('id' => null), $id));
 540:         }
 541:         if (!$number) {
 542:             return false;
 543:         }
 544:         if (empty($id)) {
 545:             $id = $Model->id;
 546:         }
 547:         extract($this->settings[$Model->alias]);
 548:         list($node) = array_values($Model->find('first', array(
 549:             'conditions' => array($scope, $Model->escapeField() => $id),
 550:             'fields' => array($Model->primaryKey, $left, $right, $parent), 'recursive' => $recursive
 551:         )));
 552:         if ($node[$parent]) {
 553:             list($parentNode) = array_values($Model->find('first', array(
 554:                 'conditions' => array($scope, $Model->escapeField() => $node[$parent]),
 555:                 'fields' => array($Model->primaryKey, $left, $right), 'recursive' => $recursive
 556:             )));
 557:             if (($node[$left] - 1) == $parentNode[$left]) {
 558:                 return false;
 559:             }
 560:         }
 561:         $previousNode = $Model->find('first', array(
 562:             'conditions' => array($scope, $Model->escapeField($right) => ($node[$left] - 1)),
 563:             'fields' => array($Model->primaryKey, $left, $right),
 564:             'recursive' => $recursive
 565:         ));
 566: 
 567:         if ($previousNode) {
 568:             list($previousNode) = array_values($previousNode);
 569:         } else {
 570:             return false;
 571:         }
 572:         $edge = $this->_getMax($Model, $scope, $right, $recursive);
 573:         $this->_sync($Model, $edge - $previousNode[$left] + 1, '+', 'BETWEEN ' . $previousNode[$left] . ' AND ' . $previousNode[$right]);
 574:         $this->_sync($Model, $node[$left] - $previousNode[$left], '-', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right]);
 575:         $this->_sync($Model, $edge - $previousNode[$left] - ($node[$right] - $node[$left]), '-', '> ' . $edge);
 576:         if (is_int($number)) {
 577:             $number--;
 578:         }
 579:         if ($number) {
 580:             $this->moveUp($Model, $id, $number);
 581:         }
 582:         return true;
 583:     }
 584: 
 585: /**
 586:  * Recover a corrupted tree
 587:  *
 588:  * The mode parameter is used to specify the source of info that is valid/correct. The opposite source of data
 589:  * will be populated based upon that source of info. E.g. if the MPTT fields are corrupt or empty, with the $mode
 590:  * 'parent' the values of the parent_id field will be used to populate the left and right fields. The missingParentAction
 591:  * parameter only applies to "parent" mode and determines what to do if the parent field contains an id that is not present.
 592:  *
 593:  * @param Model $Model Model instance
 594:  * @param string $mode parent or tree
 595:  * @param string|integer $missingParentAction 'return' to do nothing and return, 'delete' to
 596:  * delete, or the id of the parent to set as the parent_id
 597:  * @return boolean true on success, false on failure
 598:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::recover
 599:  */
 600:     public function recover(Model $Model, $mode = 'parent', $missingParentAction = null) {
 601:         if (is_array($mode)) {
 602:             extract(array_merge(array('mode' => 'parent'), $mode));
 603:         }
 604:         extract($this->settings[$Model->alias]);
 605:         $Model->recursive = $recursive;
 606:         if ($mode === 'parent') {
 607:             $Model->bindModel(array('belongsTo' => array('VerifyParent' => array(
 608:                 'className' => $Model->name,
 609:                 'foreignKey' => $parent,
 610:                 'fields' => array($Model->primaryKey, $left, $right, $parent),
 611:             ))));
 612:             $missingParents = $Model->find('list', array(
 613:                 'recursive' => 0,
 614:                 'conditions' => array($scope, array(
 615:                     'NOT' => array($Model->escapeField($parent) => null), $Model->VerifyParent->escapeField() => null
 616:                 ))
 617:             ));
 618:             $Model->unbindModel(array('belongsTo' => array('VerifyParent')));
 619:             if ($missingParents) {
 620:                 if ($missingParentAction === 'return') {
 621:                     foreach ($missingParents as $id => $display) {
 622:                         $this->errors[] = 'cannot find the parent for ' . $Model->alias . ' with id ' . $id . '(' . $display . ')';
 623:                     }
 624:                     return false;
 625:                 } elseif ($missingParentAction === 'delete') {
 626:                     $Model->deleteAll(array($Model->escapeField($Model->primaryKey) => array_flip($missingParents)), false);
 627:                 } else {
 628:                     $Model->updateAll(array($Model->escapeField($parent) => $missingParentAction), array($Model->escapeField($Model->primaryKey) => array_flip($missingParents)));
 629:                 }
 630:             }
 631:             $count = 1;
 632:             foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey), 'order' => $left)) as $array) {
 633:                 $lft = $count++;
 634:                 $rght = $count++;
 635:                 $Model->create(false);
 636:                 $Model->id = $array[$Model->alias][$Model->primaryKey];
 637:                 $Model->save(array($left => $lft, $right => $rght), array('callbacks' => false, 'validate' => false));
 638:             }
 639:             foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey, $parent), 'order' => $left)) as $array) {
 640:                 $Model->create(false);
 641:                 $Model->id = $array[$Model->alias][$Model->primaryKey];
 642:                 $this->_setParent($Model, $array[$Model->alias][$parent]);
 643:             }
 644:         } else {
 645:             $db = ConnectionManager::getDataSource($Model->useDbConfig);
 646:             foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey, $parent), 'order' => $left)) as $array) {
 647:                 $path = $this->getPath($Model, $array[$Model->alias][$Model->primaryKey]);
 648:                 $parentId = null;
 649:                 if (count($path) > 1) {
 650:                     $parentId = $path[count($path) - 2][$Model->alias][$Model->primaryKey];
 651:                 }
 652:                 $Model->updateAll(array($parent => $db->value($parentId, $parent)), array($Model->escapeField() => $array[$Model->alias][$Model->primaryKey]));
 653:             }
 654:         }
 655:         return true;
 656:     }
 657: 
 658: /**
 659:  * Reorder method.
 660:  *
 661:  * Reorders the nodes (and child nodes) of the tree according to the field and direction specified in the parameters.
 662:  * This method does not change the parent of any node.
 663:  *
 664:  * Requires a valid tree, by default it verifies the tree before beginning.
 665:  *
 666:  * Options:
 667:  *
 668:  * - 'id' id of record to use as top node for reordering
 669:  * - 'field' Which field to use in reordering defaults to displayField
 670:  * - 'order' Direction to order either DESC or ASC (defaults to ASC)
 671:  * - 'verify' Whether or not to verify the tree before reorder. defaults to true.
 672:  *
 673:  * @param Model $Model Model instance
 674:  * @param array $options array of options to use in reordering.
 675:  * @return boolean true on success, false on failure
 676:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::reorder
 677:  */
 678:     public function reorder(Model $Model, $options = array()) {
 679:         $options = array_merge(array('id' => null, 'field' => $Model->displayField, 'order' => 'ASC', 'verify' => true), $options);
 680:         extract($options);
 681:         if ($verify && !$this->verify($Model)) {
 682:             return false;
 683:         }
 684:         $verify = false;
 685:         extract($this->settings[$Model->alias]);
 686:         $fields = array($Model->primaryKey, $field, $left, $right);
 687:         $sort = $field . ' ' . $order;
 688:         $nodes = $this->children($Model, $id, true, $fields, $sort, null, null, $recursive);
 689: 
 690:         $cacheQueries = $Model->cacheQueries;
 691:         $Model->cacheQueries = false;
 692:         if ($nodes) {
 693:             foreach ($nodes as $node) {
 694:                 $id = $node[$Model->alias][$Model->primaryKey];
 695:                 $this->moveDown($Model, $id, true);
 696:                 if ($node[$Model->alias][$left] != $node[$Model->alias][$right] - 1) {
 697:                     $this->reorder($Model, compact('id', 'field', 'order', 'verify'));
 698:                 }
 699:             }
 700:         }
 701:         $Model->cacheQueries = $cacheQueries;
 702:         return true;
 703:     }
 704: 
 705: /**
 706:  * Remove the current node from the tree, and reparent all children up one level.
 707:  *
 708:  * If the parameter delete is false, the node will become a new top level node. Otherwise the node will be deleted
 709:  * after the children are reparented.
 710:  *
 711:  * @param Model $Model Model instance
 712:  * @param integer|string $id The ID of the record to remove
 713:  * @param boolean $delete whether to delete the node after reparenting children (if any)
 714:  * @return boolean true on success, false on failure
 715:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::removeFromTree
 716:  */
 717:     public function removeFromTree(Model $Model, $id = null, $delete = false) {
 718:         if (is_array($id)) {
 719:             extract(array_merge(array('id' => null), $id));
 720:         }
 721:         extract($this->settings[$Model->alias]);
 722: 
 723:         list($node) = array_values($Model->find('first', array(
 724:             'conditions' => array($scope, $Model->escapeField() => $id),
 725:             'fields' => array($Model->primaryKey, $left, $right, $parent),
 726:             'recursive' => $recursive
 727:         )));
 728: 
 729:         if ($node[$right] == $node[$left] + 1) {
 730:             if ($delete) {
 731:                 return $Model->delete($id);
 732:             } else {
 733:                 $Model->id = $id;
 734:                 return $Model->saveField($parent, null);
 735:             }
 736:         } elseif ($node[$parent]) {
 737:             list($parentNode) = array_values($Model->find('first', array(
 738:                 'conditions' => array($scope, $Model->escapeField() => $node[$parent]),
 739:                 'fields' => array($Model->primaryKey, $left, $right),
 740:                 'recursive' => $recursive
 741:             )));
 742:         } else {
 743:             $parentNode[$right] = $node[$right] + 1;
 744:         }
 745: 
 746:         $db = ConnectionManager::getDataSource($Model->useDbConfig);
 747:         $Model->updateAll(
 748:             array($parent => $db->value($node[$parent], $parent)),
 749:             array($Model->escapeField($parent) => $node[$Model->primaryKey])
 750:         );
 751:         $this->_sync($Model, 1, '-', 'BETWEEN ' . ($node[$left] + 1) . ' AND ' . ($node[$right] - 1));
 752:         $this->_sync($Model, 2, '-', '> ' . ($node[$right]));
 753:         $Model->id = $id;
 754: 
 755:         if ($delete) {
 756:             $Model->updateAll(
 757:                 array(
 758:                     $Model->escapeField($left) => 0,
 759:                     $Model->escapeField($right) => 0,
 760:                     $Model->escapeField($parent) => null
 761:                 ),
 762:                 array($Model->escapeField() => $id)
 763:             );
 764:             return $Model->delete($id);
 765:         }
 766:         $edge = $this->_getMax($Model, $scope, $right, $recursive);
 767:         if ($node[$right] == $edge) {
 768:             $edge = $edge - 2;
 769:         }
 770:         $Model->id = $id;
 771:         return $Model->save(
 772:             array($left => $edge + 1, $right => $edge + 2, $parent => null),
 773:             array('callbacks' => false, 'validate' => false)
 774:         );
 775:     }
 776: 
 777: /**
 778:  * Check if the current tree is valid.
 779:  *
 780:  * Returns true if the tree is valid otherwise an array of (type, incorrect left/right index, message)
 781:  *
 782:  * @param Model $Model Model instance
 783:  * @return mixed true if the tree is valid or empty, otherwise an array of (error type [index, node],
 784:  *  [incorrect left/right index,node id], message)
 785:  * @link http://book.cakephp.org/2.0/en/core-libraries/behaviors/tree.html#TreeBehavior::verify
 786:  */
 787:     public function verify(Model $Model) {
 788:         extract($this->settings[$Model->alias]);
 789:         if (!$Model->find('count', array('conditions' => $scope))) {
 790:             return true;
 791:         }
 792:         $min = $this->_getMin($Model, $scope, $left, $recursive);
 793:         $edge = $this->_getMax($Model, $scope, $right, $recursive);
 794:         $errors = array();
 795: 
 796:         for ($i = $min; $i <= $edge; $i++) {
 797:             $count = $Model->find('count', array('conditions' => array(
 798:                 $scope, 'OR' => array($Model->escapeField($left) => $i, $Model->escapeField($right) => $i)
 799:             )));
 800:             if ($count != 1) {
 801:                 if (!$count) {
 802:                     $errors[] = array('index', $i, 'missing');
 803:                 } else {
 804:                     $errors[] = array('index', $i, 'duplicate');
 805:                 }
 806:             }
 807:         }
 808:         $node = $Model->find('first', array('conditions' => array($scope, $Model->escapeField($right) . '< ' . $Model->escapeField($left)), 'recursive' => 0));
 809:         if ($node) {
 810:             $errors[] = array('node', $node[$Model->alias][$Model->primaryKey], 'left greater than right.');
 811:         }
 812: 
 813:         $Model->bindModel(array('belongsTo' => array('VerifyParent' => array(
 814:             'className' => $Model->name,
 815:             'foreignKey' => $parent,
 816:             'fields' => array($Model->primaryKey, $left, $right, $parent)
 817:         ))));
 818: 
 819:         foreach ($Model->find('all', array('conditions' => $scope, 'recursive' => 0)) as $instance) {
 820:             if ($instance[$Model->alias][$left] === null || $instance[$Model->alias][$right] === null) {
 821:                 $errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],
 822:                     'has invalid left or right values');
 823:             } elseif ($instance[$Model->alias][$left] == $instance[$Model->alias][$right]) {
 824:                 $errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],
 825:                     'left and right values identical');
 826:             } elseif ($instance[$Model->alias][$parent]) {
 827:                 if (!$instance['VerifyParent'][$Model->primaryKey]) {
 828:                     $errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],
 829:                         'The parent node ' . $instance[$Model->alias][$parent] . ' doesn\'t exist');
 830:                 } elseif ($instance[$Model->alias][$left] < $instance['VerifyParent'][$left]) {
 831:                     $errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],
 832:                         'left less than parent (node ' . $instance['VerifyParent'][$Model->primaryKey] . ').');
 833:                 } elseif ($instance[$Model->alias][$right] > $instance['VerifyParent'][$right]) {
 834:                     $errors[] = array('node', $instance[$Model->alias][$Model->primaryKey],
 835:                         'right greater than parent (node ' . $instance['VerifyParent'][$Model->primaryKey] . ').');
 836:                 }
 837:             } elseif ($Model->find('count', array('conditions' => array($scope, $Model->escapeField($left) . ' <' => $instance[$Model->alias][$left], $Model->escapeField($right) . ' >' => $instance[$Model->alias][$right]), 'recursive' => 0))) {
 838:                 $errors[] = array('node', $instance[$Model->alias][$Model->primaryKey], 'The parent field is blank, but has a parent');
 839:             }
 840:         }
 841:         if ($errors) {
 842:             return $errors;
 843:         }
 844:         return true;
 845:     }
 846: 
 847: /**
 848:  * Sets the parent of the given node
 849:  *
 850:  * The force parameter is used to override the "don't change the parent to the current parent" logic in the event
 851:  * of recovering a corrupted table, or creating new nodes. Otherwise it should always be false. In reality this
 852:  * method could be private, since calling save with parent_id set also calls setParent
 853:  *
 854:  * @param Model $Model Model instance
 855:  * @param integer|string $parentId
 856:  * @param boolean $created
 857:  * @return boolean true on success, false on failure
 858:  */
 859:     protected function _setParent(Model $Model, $parentId = null, $created = false) {
 860:         extract($this->settings[$Model->alias]);
 861:         list($node) = array_values($Model->find('first', array(
 862:             'conditions' => array($scope, $Model->escapeField() => $Model->id),
 863:             'fields' => array($Model->primaryKey, $parent, $left, $right),
 864:             'recursive' => $recursive
 865:         )));
 866:         $edge = $this->_getMax($Model, $scope, $right, $recursive, $created);
 867: 
 868:         if (empty($parentId)) {
 869:             $this->_sync($Model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);
 870:             $this->_sync($Model, $node[$right] - $node[$left] + 1, '-', '> ' . $node[$left], $created);
 871:         } else {
 872:             $values = $Model->find('first', array(
 873:                 'conditions' => array($scope, $Model->escapeField() => $parentId),
 874:                 'fields' => array($Model->primaryKey, $left, $right),
 875:                 'recursive' => $recursive
 876:             ));
 877: 
 878:             if ($values === false) {
 879:                 return false;
 880:             }
 881:             $parentNode = array_values($values);
 882: 
 883:             if (empty($parentNode) || empty($parentNode[0])) {
 884:                 return false;
 885:             }
 886:             $parentNode = $parentNode[0];
 887: 
 888:             if (($Model->id == $parentId)) {
 889:                 return false;
 890:             } elseif (($node[$left] < $parentNode[$left]) && ($parentNode[$right] < $node[$right])) {
 891:                 return false;
 892:             }
 893:             if (empty($node[$left]) && empty($node[$right])) {
 894:                 $this->_sync($Model, 2, '+', '>= ' . $parentNode[$right], $created);
 895:                 $result = $Model->save(
 896:                     array($left => $parentNode[$right], $right => $parentNode[$right] + 1, $parent => $parentId),
 897:                     array('validate' => false, 'callbacks' => false)
 898:                 );
 899:                 $Model->data = $result;
 900:             } else {
 901:                 $this->_sync($Model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);
 902:                 $diff = $node[$right] - $node[$left] + 1;
 903: 
 904:                 if ($node[$left] > $parentNode[$left]) {
 905:                     if ($node[$right] < $parentNode[$right]) {
 906:                         $this->_sync($Model, $diff, '-', 'BETWEEN ' . $node[$right] . ' AND ' . ($parentNode[$right] - 1), $created);
 907:                         $this->_sync($Model, $edge - $parentNode[$right] + $diff + 1, '-', '> ' . $edge, $created);
 908:                     } else {
 909:                         $this->_sync($Model, $diff, '+', 'BETWEEN ' . $parentNode[$right] . ' AND ' . $node[$right], $created);
 910:                         $this->_sync($Model, $edge - $parentNode[$right] + 1, '-', '> ' . $edge, $created);
 911:                     }
 912:                 } else {
 913:                     $this->_sync($Model, $diff, '-', 'BETWEEN ' . $node[$right] . ' AND ' . ($parentNode[$right] - 1), $created);
 914:                     $this->_sync($Model, $edge - $parentNode[$right] + $diff + 1, '-', '> ' . $edge, $created);
 915:                 }
 916:             }
 917:         }
 918:         return true;
 919:     }
 920: 
 921: /**
 922:  * get the maximum index value in the table.
 923:  *
 924:  * @param Model $Model
 925:  * @param string $scope
 926:  * @param string $right
 927:  * @param integer $recursive
 928:  * @param boolean $created
 929:  * @return integer
 930:  */
 931:     protected function _getMax(Model $Model, $scope, $right, $recursive = -1, $created = false) {
 932:         $db = ConnectionManager::getDataSource($Model->useDbConfig);
 933:         if ($created) {
 934:             if (is_string($scope)) {
 935:                 $scope .= " AND " . $Model->escapeField() . " <> ";
 936:                 $scope .= $db->value($Model->id, $Model->getColumnType($Model->primaryKey));
 937:             } else {
 938:                 $scope['NOT'][$Model->alias . '.' . $Model->primaryKey] = $Model->id;
 939:             }
 940:         }
 941:         $name = $Model->escapeField($right);
 942:         list($edge) = array_values($Model->find('first', array(
 943:             'conditions' => $scope,
 944:             'fields' => $db->calculate($Model, 'max', array($name, $right)),
 945:             'recursive' => $recursive,
 946:             'callbacks' => false
 947:         )));
 948:         return (empty($edge[$right])) ? 0 : $edge[$right];
 949:     }
 950: 
 951: /**
 952:  * get the minimum index value in the table.
 953:  *
 954:  * @param Model $Model
 955:  * @param string $scope
 956:  * @param string $left
 957:  * @param integer $recursive
 958:  * @return integer
 959:  */
 960:     protected function _getMin(Model $Model, $scope, $left, $recursive = -1) {
 961:         $db = ConnectionManager::getDataSource($Model->useDbConfig);
 962:         $name = $Model->escapeField($left);
 963:         list($edge) = array_values($Model->find('first', array(
 964:             'conditions' => $scope,
 965:             'fields' => $db->calculate($Model, 'min', array($name, $left)),
 966:             'recursive' => $recursive,
 967:             'callbacks' => false
 968:         )));
 969:         return (empty($edge[$left])) ? 0 : $edge[$left];
 970:     }
 971: 
 972: /**
 973:  * Table sync method.
 974:  *
 975:  * Handles table sync operations, Taking account of the behavior scope.
 976:  *
 977:  * @param Model $Model
 978:  * @param integer $shift
 979:  * @param string $dir
 980:  * @param array $conditions
 981:  * @param boolean $created
 982:  * @param string $field
 983:  * @return void
 984:  */
 985:     protected function _sync(Model $Model, $shift, $dir = '+', $conditions = array(), $created = false, $field = 'both') {
 986:         $ModelRecursive = $Model->recursive;
 987:         extract($this->settings[$Model->alias]);
 988:         $Model->recursive = $recursive;
 989: 
 990:         if ($field === 'both') {
 991:             $this->_sync($Model, $shift, $dir, $conditions, $created, $left);
 992:             $field = $right;
 993:         }
 994:         if (is_string($conditions)) {
 995:             $conditions = array($Model->escapeField($field) . " {$conditions}");
 996:         }
 997:         if (($scope !== '1 = 1' && $scope !== true) && $scope) {
 998:             $conditions[] = $scope;
 999:         }
1000:         if ($created) {
1001:             $conditions['NOT'][$Model->escapeField()] = $Model->id;
1002:         }
1003:         $Model->updateAll(array($Model->escapeField($field) => $Model->escapeField($field) . ' ' . $dir . ' ' . $shift), $conditions);
1004:         $Model->recursive = $ModelRecursive;
1005:     }
1006: 
1007: }
1008: