comparison cake/libs/model/behaviors/tree.php @ 0:261e66bd5a0c

hg init
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Sun, 24 Jul 2011 21:08:31 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:261e66bd5a0c
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 2006-2010, 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 2006-2010, 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/view/1339/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/view/1347/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 (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/view/1346/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/view/1348/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/view/1349/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/view/1350/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/view/1352/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/view/1353/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/view/1628/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->alias,
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 }
594 return false;
595 } elseif ($missingParentAction == 'delete') {
596 $Model->deleteAll(array($Model->primaryKey => array_flip($missingParents)));
597 } else {
598 $Model->updateAll(array($parent => $missingParentAction), array($Model->escapeField($Model->primaryKey) => array_flip($missingParents)));
599 }
600 }
601 $count = 1;
602 foreach ($Model->find('all', array('conditions' => $scope, 'fields' => array($Model->primaryKey), 'order' => $left)) as $array) {
603 $Model->id = $array[$Model->alias][$Model->primaryKey];
604 $lft = $count++;
605 $rght = $count++;
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();
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/view/1355/reorder
647 * @link http://book.cakephp.org/view/1629/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/view/1354/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/view/1630/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->alias,
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 * @return boolean true on success, false on failure
831 * @access protected
832 */
833 function _setParent(&$Model, $parentId = null, $created = false) {
834 extract($this->settings[$Model->alias]);
835 list($node) = array_values($Model->find('first', array(
836 'conditions' => array($scope, $Model->escapeField() => $Model->id),
837 'fields' => array($Model->primaryKey, $parent, $left, $right),
838 'recursive' => $recursive
839 )));
840 $edge = $this->__getMax($Model, $scope, $right, $recursive, $created);
841
842 if (empty ($parentId)) {
843 $this->__sync($Model, $edge - $node[$left] + 1, '+', 'BETWEEN ' . $node[$left] . ' AND ' . $node[$right], $created);
844 $this->__sync($Model, $node[$right] - $node[$left] + 1, '-', '> ' . $node[$left], $created);
845 } else {
846 $values = $Model->find('first', array(
847 'conditions' => array($scope, $Model->escapeField() => $parentId),
848 'fields' => array($Model->primaryKey, $left, $right),
849 'recursive' => $recursive
850 ));
851
852 if ($values === false) {
853 return false;
854 }
855 $parentNode = array_values($values);
856
857 if (empty($parentNode) || empty($parentNode[0])) {
858 return false;
859 }
860 $parentNode = $parentNode[0];
861
862 if (($Model->id == $parentId)) {
863 return false;
864
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 * @return int
903 * @access private
904 */
905 function __getMax($Model, $scope, $right, $recursive = -1, $created = false) {
906 $db =& ConnectionManager::getDataSource($Model->useDbConfig);
907 if ($created) {
908 if (is_string($scope)) {
909 $scope .= " AND {$Model->alias}.{$Model->primaryKey} <> ";
910 $scope .= $db->value($Model->id, $Model->getColumnType($Model->primaryKey));
911 } else {
912 $scope['NOT'][$Model->alias . '.' . $Model->primaryKey] = $Model->id;
913 }
914 }
915 $name = $Model->alias . '.' . $right;
916 list($edge) = array_values($Model->find('first', array(
917 'conditions' => $scope,
918 'fields' => $db->calculate($Model, 'max', array($name, $right)),
919 'recursive' => $recursive
920 )));
921 return (empty($edge[$right])) ? 0 : $edge[$right];
922 }
923
924 /**
925 * get the minimum index value in the table.
926 *
927 * @param AppModel $Model
928 * @param string $scope
929 * @param string $right
930 * @return int
931 * @access private
932 */
933 function __getMin($Model, $scope, $left, $recursive = -1) {
934 $db =& ConnectionManager::getDataSource($Model->useDbConfig);
935 $name = $Model->alias . '.' . $left;
936 list($edge) = array_values($Model->find('first', array(
937 'conditions' => $scope,
938 'fields' => $db->calculate($Model, 'min', array($name, $left)),
939 'recursive' => $recursive
940 )));
941 return (empty($edge[$left])) ? 0 : $edge[$left];
942 }
943
944 /**
945 * Table sync method.
946 *
947 * Handles table sync operations, Taking account of the behavior scope.
948 *
949 * @param AppModel $Model
950 * @param integer $shift
951 * @param string $direction
952 * @param array $conditions
953 * @param string $field
954 * @access private
955 */
956 function __sync(&$Model, $shift, $dir = '+', $conditions = array(), $created = false, $field = 'both') {
957 $ModelRecursive = $Model->recursive;
958 extract($this->settings[$Model->alias]);
959 $Model->recursive = $recursive;
960
961 if ($field == 'both') {
962 $this->__sync($Model, $shift, $dir, $conditions, $created, $left);
963 $field = $right;
964 }
965 if (is_string($conditions)) {
966 $conditions = array("{$Model->alias}.{$field} {$conditions}");
967 }
968 if (($scope != '1 = 1' && $scope !== true) && $scope) {
969 $conditions[] = $scope;
970 }
971 if ($created) {
972 $conditions['NOT'][$Model->alias . '.' . $Model->primaryKey] = $Model->id;
973 }
974 $Model->updateAll(array($Model->alias . '.' . $field => $Model->escapeField($field) . ' ' . $dir . ' ' . $shift), $conditions);
975 $Model->recursive = $ModelRecursive;
976 }
977 }