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