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