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