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