← Back to branch summary

~tsep-dev/tsep/0.9-beta

« back to all changes in this revision

Viewing changes to branches/symfony/cake/libs/model/behaviors/tree.php

  • Committer: geoffreyfishing
  • Date: 2011-01-11 23:46:12 UTC
  • Revision ID: svn-v4:ae0de26e-ed09-4cbe-9a20-e40b4c60ac6c::125
Created a symfony branch for future migration to symfony

Show diffs side-by-side

added added

removed removed

Lines of Context:
branches/symfony/cake/libs/model/behaviors/tree.php
 
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 mixed $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 mixed $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
}