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