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