1: <?php
   2: /**
   3:  * CakePHP(tm) : Rapid Development Framework (https://cakephp.org)
   4:  * Copyright (c) Cake Software Foundation, Inc. (https://cakefoundation.org)
   5:  *
   6:  * Licensed under The MIT License
   7:  * For full copyright and license information, please see the LICENSE.txt
   8:  * Redistributions of files must retain the above copyright notice.
   9:  *
  10:  * @copyright     Copyright (c) Cake Software Foundation, Inc. (https://cakefoundation.org)
  11:  * @link          https://cakephp.org CakePHP(tm) Project
  12:  * @since         3.0.0
  13:  * @license       https://opensource.org/licenses/mit-license.php MIT License
  14:  */
  15: namespace Cake\ORM\Behavior;
  16: 
  17: use Cake\Database\Expression\IdentifierExpression;
  18: use Cake\Datasource\EntityInterface;
  19: use Cake\Datasource\Exception\RecordNotFoundException;
  20: use Cake\Event\Event;
  21: use Cake\ORM\Behavior;
  22: use Cake\ORM\Query;
  23: use InvalidArgumentException;
  24: use RuntimeException;
  25: 
  26: /**
  27:  * Makes the table to which this is attached to behave like a nested set and
  28:  * provides methods for managing and retrieving information out of the derived
  29:  * hierarchical structure.
  30:  *
  31:  * Tables attaching this behavior are required to have a column referencing the
  32:  * parent row, and two other numeric columns (lft and rght) where the implicit
  33:  * order will be cached.
  34:  *
  35:  * For more information on what is a nested set and a how it works refer to
  36:  * https://www.sitepoint.com/hierarchical-data-database-2/
  37:  */
  38: class TreeBehavior extends Behavior
  39: {
  40:     /**
  41:      * Cached copy of the first column in a table's primary key.
  42:      *
  43:      * @var string
  44:      */
  45:     protected $_primaryKey;
  46: 
  47:     /**
  48:      * Default config
  49:      *
  50:      * These are merged with user-provided configuration when the behavior is used.
  51:      *
  52:      * @var array
  53:      */
  54:     protected $_defaultConfig = [
  55:         'implementedFinders' => [
  56:             'path' => 'findPath',
  57:             'children' => 'findChildren',
  58:             'treeList' => 'findTreeList',
  59:         ],
  60:         'implementedMethods' => [
  61:             'childCount' => 'childCount',
  62:             'moveUp' => 'moveUp',
  63:             'moveDown' => 'moveDown',
  64:             'recover' => 'recover',
  65:             'removeFromTree' => 'removeFromTree',
  66:             'getLevel' => 'getLevel',
  67:             'formatTreeList' => 'formatTreeList',
  68:         ],
  69:         'parent' => 'parent_id',
  70:         'left' => 'lft',
  71:         'right' => 'rght',
  72:         'scope' => null,
  73:         'level' => null,
  74:         'recoverOrder' => null,
  75:     ];
  76: 
  77:     /**
  78:      * {@inheritDoc}
  79:      */
  80:     public function initialize(array $config)
  81:     {
  82:         $this->_config['leftField'] = new IdentifierExpression($this->_config['left']);
  83:         $this->_config['rightField'] = new IdentifierExpression($this->_config['right']);
  84:     }
  85: 
  86:     /**
  87:      * Before save listener.
  88:      * Transparently manages setting the lft and rght fields if the parent field is
  89:      * included in the parameters to be saved.
  90:      *
  91:      * @param \Cake\Event\Event $event The beforeSave event that was fired
  92:      * @param \Cake\Datasource\EntityInterface $entity the entity that is going to be saved
  93:      * @return void
  94:      * @throws \RuntimeException if the parent to set for the node is invalid
  95:      */
  96:     public function beforeSave(Event $event, EntityInterface $entity)
  97:     {
  98:         $isNew = $entity->isNew();
  99:         $config = $this->getConfig();
 100:         $parent = $entity->get($config['parent']);
 101:         $primaryKey = $this->_getPrimaryKey();
 102:         $dirty = $entity->isDirty($config['parent']);
 103:         $level = $config['level'];
 104: 
 105:         if ($parent && $entity->get($primaryKey) == $parent) {
 106:             throw new RuntimeException("Cannot set a node's parent as itself");
 107:         }
 108: 
 109:         if ($isNew && $parent) {
 110:             $parentNode = $this->_getNode($parent);
 111:             $edge = $parentNode->get($config['right']);
 112:             $entity->set($config['left'], $edge);
 113:             $entity->set($config['right'], $edge + 1);
 114:             $this->_sync(2, '+', ">= {$edge}");
 115: 
 116:             if ($level) {
 117:                 $entity->set($level, $parentNode[$level] + 1);
 118:             }
 119: 
 120:             return;
 121:         }
 122: 
 123:         if ($isNew && !$parent) {
 124:             $edge = $this->_getMax();
 125:             $entity->set($config['left'], $edge + 1);
 126:             $entity->set($config['right'], $edge + 2);
 127: 
 128:             if ($level) {
 129:                 $entity->set($level, 0);
 130:             }
 131: 
 132:             return;
 133:         }
 134: 
 135:         if (!$isNew && $dirty && $parent) {
 136:             $this->_setParent($entity, $parent);
 137: 
 138:             if ($level) {
 139:                 $parentNode = $this->_getNode($parent);
 140:                 $entity->set($level, $parentNode[$level] + 1);
 141:             }
 142: 
 143:             return;
 144:         }
 145: 
 146:         if (!$isNew && $dirty && !$parent) {
 147:             $this->_setAsRoot($entity);
 148: 
 149:             if ($level) {
 150:                 $entity->set($level, 0);
 151:             }
 152:         }
 153:     }
 154: 
 155:     /**
 156:      * After save listener.
 157:      *
 158:      * Manages updating level of descendants of currently saved entity.
 159:      *
 160:      * @param \Cake\Event\Event $event The afterSave event that was fired
 161:      * @param \Cake\Datasource\EntityInterface $entity the entity that is going to be saved
 162:      * @return void
 163:      */
 164:     public function afterSave(Event $event, EntityInterface $entity)
 165:     {
 166:         if (!$this->_config['level'] || $entity->isNew()) {
 167:             return;
 168:         }
 169: 
 170:         $this->_setChildrenLevel($entity);
 171:     }
 172: 
 173:     /**
 174:      * Set level for descendants.
 175:      *
 176:      * @param \Cake\Datasource\EntityInterface $entity The entity whose descendants need to be updated.
 177:      * @return void
 178:      */
 179:     protected function _setChildrenLevel($entity)
 180:     {
 181:         $config = $this->getConfig();
 182: 
 183:         if ($entity->get($config['left']) + 1 === $entity->get($config['right'])) {
 184:             return;
 185:         }
 186: 
 187:         $primaryKey = $this->_getPrimaryKey();
 188:         $primaryKeyValue = $entity->get($primaryKey);
 189:         $depths = [$primaryKeyValue => $entity->get($config['level'])];
 190: 
 191:         $children = $this->_table->find('children', [
 192:             'for' => $primaryKeyValue,
 193:             'fields' => [$this->_getPrimaryKey(), $config['parent'], $config['level']],
 194:             'order' => $config['left'],
 195:         ]);
 196: 
 197:         /* @var \Cake\Datasource\EntityInterface $node */
 198:         foreach ($children as $node) {
 199:             $parentIdValue = $node->get($config['parent']);
 200:             $depth = $depths[$parentIdValue] + 1;
 201:             $depths[$node->get($primaryKey)] = $depth;
 202: 
 203:             $this->_table->updateAll(
 204:                 [$config['level'] => $depth],
 205:                 [$primaryKey => $node->get($primaryKey)]
 206:             );
 207:         }
 208:     }
 209: 
 210:     /**
 211:      * Also deletes the nodes in the subtree of the entity to be delete
 212:      *
 213:      * @param \Cake\Event\Event $event The beforeDelete event that was fired
 214:      * @param \Cake\Datasource\EntityInterface $entity The entity that is going to be saved
 215:      * @return void
 216:      */
 217:     public function beforeDelete(Event $event, EntityInterface $entity)
 218:     {
 219:         $config = $this->getConfig();
 220:         $this->_ensureFields($entity);
 221:         $left = $entity->get($config['left']);
 222:         $right = $entity->get($config['right']);
 223:         $diff = $right - $left + 1;
 224: 
 225:         if ($diff > 2) {
 226:             $query = $this->_scope($this->_table->query())
 227:                 ->delete()
 228:                 ->where(function ($exp) use ($config, $left, $right) {
 229:                     /* @var \Cake\Database\Expression\QueryExpression $exp */
 230:                     return $exp
 231:                         ->gte($config['leftField'], $left + 1)
 232:                         ->lte($config['leftField'], $right - 1);
 233:                 });
 234:             $statement = $query->execute();
 235:             $statement->closeCursor();
 236:         }
 237: 
 238:         $this->_sync($diff, '-', "> {$right}");
 239:     }
 240: 
 241:     /**
 242:      * Sets the correct left and right values for the passed entity so it can be
 243:      * updated to a new parent. It also makes the hole in the tree so the node
 244:      * move can be done without corrupting the structure.
 245:      *
 246:      * @param \Cake\Datasource\EntityInterface $entity The entity to re-parent
 247:      * @param mixed $parent the id of the parent to set
 248:      * @return void
 249:      * @throws \RuntimeException if the parent to set to the entity is not valid
 250:      */
 251:     protected function _setParent($entity, $parent)
 252:     {
 253:         $config = $this->getConfig();
 254:         $parentNode = $this->_getNode($parent);
 255:         $this->_ensureFields($entity);
 256:         $parentLeft = $parentNode->get($config['left']);
 257:         $parentRight = $parentNode->get($config['right']);
 258:         $right = $entity->get($config['right']);
 259:         $left = $entity->get($config['left']);
 260: 
 261:         if ($parentLeft > $left && $parentLeft < $right) {
 262:             throw new RuntimeException(sprintf(
 263:                 'Cannot use node "%s" as parent for entity "%s"',
 264:                 $parent,
 265:                 $entity->get($this->_getPrimaryKey())
 266:             ));
 267:         }
 268: 
 269:         // Values for moving to the left
 270:         $diff = $right - $left + 1;
 271:         $targetLeft = $parentRight;
 272:         $targetRight = $diff + $parentRight - 1;
 273:         $min = $parentRight;
 274:         $max = $left - 1;
 275: 
 276:         if ($left < $targetLeft) {
 277:             // Moving to the right
 278:             $targetLeft = $parentRight - $diff;
 279:             $targetRight = $parentRight - 1;
 280:             $min = $right + 1;
 281:             $max = $parentRight - 1;
 282:             $diff *= -1;
 283:         }
 284: 
 285:         if ($right - $left > 1) {
 286:             // Correcting internal subtree
 287:             $internalLeft = $left + 1;
 288:             $internalRight = $right - 1;
 289:             $this->_sync($targetLeft - $left, '+', "BETWEEN {$internalLeft} AND {$internalRight}", true);
 290:         }
 291: 
 292:         $this->_sync($diff, '+', "BETWEEN {$min} AND {$max}");
 293: 
 294:         if ($right - $left > 1) {
 295:             $this->_unmarkInternalTree();
 296:         }
 297: 
 298:         // Allocating new position
 299:         $entity->set($config['left'], $targetLeft);
 300:         $entity->set($config['right'], $targetRight);
 301:     }
 302: 
 303:     /**
 304:      * Updates the left and right column for the passed entity so it can be set as
 305:      * a new root in the tree. It also modifies the ordering in the rest of the tree
 306:      * so the structure remains valid
 307:      *
 308:      * @param \Cake\Datasource\EntityInterface $entity The entity to set as a new root
 309:      * @return void
 310:      */
 311:     protected function _setAsRoot($entity)
 312:     {
 313:         $config = $this->getConfig();
 314:         $edge = $this->_getMax();
 315:         $this->_ensureFields($entity);
 316:         $right = $entity->get($config['right']);
 317:         $left = $entity->get($config['left']);
 318:         $diff = $right - $left;
 319: 
 320:         if ($right - $left > 1) {
 321:             //Correcting internal subtree
 322:             $internalLeft = $left + 1;
 323:             $internalRight = $right - 1;
 324:             $this->_sync($edge - $diff - $left, '+', "BETWEEN {$internalLeft} AND {$internalRight}", true);
 325:         }
 326: 
 327:         $this->_sync($diff + 1, '-', "BETWEEN {$right} AND {$edge}");
 328: 
 329:         if ($right - $left > 1) {
 330:             $this->_unmarkInternalTree();
 331:         }
 332: 
 333:         $entity->set($config['left'], $edge - $diff);
 334:         $entity->set($config['right'], $edge);
 335:     }
 336: 
 337:     /**
 338:      * Helper method used to invert the sign of the left and right columns that are
 339:      * less than 0. They were set to negative values before so their absolute value
 340:      * wouldn't change while performing other tree transformations.
 341:      *
 342:      * @return void
 343:      */
 344:     protected function _unmarkInternalTree()
 345:     {
 346:         $config = $this->getConfig();
 347:         $this->_table->updateAll(
 348:             function ($exp) use ($config) {
 349:                 /* @var \Cake\Database\Expression\QueryExpression $exp */
 350:                 $leftInverse = clone $exp;
 351:                 $leftInverse->setConjunction('*')->add('-1');
 352:                 $rightInverse = clone $leftInverse;
 353: 
 354:                 return $exp
 355:                     ->eq($config['leftField'], $leftInverse->add($config['leftField']))
 356:                     ->eq($config['rightField'], $rightInverse->add($config['rightField']));
 357:             },
 358:             function ($exp) use ($config) {
 359:                 /* @var \Cake\Database\Expression\QueryExpression $exp */
 360:                 return $exp->lt($config['leftField'], 0);
 361:             }
 362:         );
 363:     }
 364: 
 365:     /**
 366:      * Custom finder method which can be used to return the list of nodes from the root
 367:      * to a specific node in the tree. This custom finder requires that the key 'for'
 368:      * is passed in the options containing the id of the node to get its path for.
 369:      *
 370:      * @param \Cake\ORM\Query $query The constructed query to modify
 371:      * @param array $options the list of options for the query
 372:      * @return \Cake\ORM\Query
 373:      * @throws \InvalidArgumentException If the 'for' key is missing in options
 374:      */
 375:     public function findPath(Query $query, array $options)
 376:     {
 377:         if (empty($options['for'])) {
 378:             throw new InvalidArgumentException("The 'for' key is required for find('path')");
 379:         }
 380: 
 381:         $config = $this->getConfig();
 382:         list($left, $right) = array_map(
 383:             function ($field) {
 384:                 return $this->_table->aliasField($field);
 385:             },
 386:             [$config['left'], $config['right']]
 387:         );
 388: 
 389:         $node = $this->_table->get($options['for'], ['fields' => [$left, $right]]);
 390: 
 391:         return $this->_scope($query)
 392:             ->where([
 393:                 "$left <=" => $node->get($config['left']),
 394:                 "$right >=" => $node->get($config['right']),
 395:             ])
 396:             ->order([$left => 'ASC']);
 397:     }
 398: 
 399:     /**
 400:      * Get the number of children nodes.
 401:      *
 402:      * @param \Cake\Datasource\EntityInterface $node The entity to count children for
 403:      * @param bool $direct whether to count all nodes in the subtree or just
 404:      * direct children
 405:      * @return int Number of children nodes.
 406:      */
 407:     public function childCount(EntityInterface $node, $direct = false)
 408:     {
 409:         $config = $this->getConfig();
 410:         $parent = $this->_table->aliasField($config['parent']);
 411: 
 412:         if ($direct) {
 413:             return $this->_scope($this->_table->find())
 414:                 ->where([$parent => $node->get($this->_getPrimaryKey())])
 415:                 ->count();
 416:         }
 417: 
 418:         $this->_ensureFields($node);
 419: 
 420:         return ($node->get($config['right']) - $node->get($config['left']) - 1) / 2;
 421:     }
 422: 
 423:     /**
 424:      * Get the children nodes of the current model
 425:      *
 426:      * Available options are:
 427:      *
 428:      * - for: The id of the record to read.
 429:      * - direct: Boolean, whether to return only the direct (true), or all (false) children,
 430:      *   defaults to false (all children).
 431:      *
 432:      * If the direct option is set to true, only the direct children are returned (based upon the parent_id field)
 433:      *
 434:      * @param \Cake\ORM\Query $query Query.
 435:      * @param array $options Array of options as described above
 436:      * @return \Cake\ORM\Query
 437:      * @throws \InvalidArgumentException When the 'for' key is not passed in $options
 438:      */
 439:     public function findChildren(Query $query, array $options)
 440:     {
 441:         $config = $this->getConfig();
 442:         $options += ['for' => null, 'direct' => false];
 443:         list($parent, $left, $right) = array_map(
 444:             function ($field) {
 445:                 return $this->_table->aliasField($field);
 446:             },
 447:             [$config['parent'], $config['left'], $config['right']]
 448:         );
 449: 
 450:         list($for, $direct) = [$options['for'], $options['direct']];
 451: 
 452:         if (empty($for)) {
 453:             throw new InvalidArgumentException("The 'for' key is required for find('children')");
 454:         }
 455: 
 456:         if ($query->clause('order') === null) {
 457:             $query->order([$left => 'ASC']);
 458:         }
 459: 
 460:         if ($direct) {
 461:             return $this->_scope($query)->where([$parent => $for]);
 462:         }
 463: 
 464:         $node = $this->_getNode($for);
 465: 
 466:         return $this->_scope($query)
 467:             ->where([
 468:                 "{$right} <" => $node->get($config['right']),
 469:                 "{$left} >" => $node->get($config['left']),
 470:             ]);
 471:     }
 472: 
 473:     /**
 474:      * Gets a representation of the elements in the tree as a flat list where the keys are
 475:      * the primary key for the table and the values are the display field for the table.
 476:      * Values are prefixed to visually indicate relative depth in the tree.
 477:      *
 478:      * ### Options
 479:      *
 480:      * - keyPath: A dot separated path to fetch the field to use for the array key, or a closure to
 481:      *   return the key out of the provided row.
 482:      * - valuePath: A dot separated path to fetch the field to use for the array value, or a closure to
 483:      *   return the value out of the provided row.
 484:      * - spacer: A string to be used as prefix for denoting the depth in the tree for each item
 485:      *
 486:      * @param \Cake\ORM\Query $query Query.
 487:      * @param array $options Array of options as described above.
 488:      * @return \Cake\ORM\Query
 489:      */
 490:     public function findTreeList(Query $query, array $options)
 491:     {
 492:         $left = $this->_table->aliasField($this->getConfig('left'));
 493: 
 494:         $results = $this->_scope($query)
 495:             ->find('threaded', [
 496:                 'parentField' => $this->getConfig('parent'),
 497:                 'order' => [$left => 'ASC'],
 498:             ]);
 499: 
 500:         return $this->formatTreeList($results, $options);
 501:     }
 502: 
 503:     /**
 504:      * Formats query as a flat list where the keys are the primary key for the table
 505:      * and the values are the display field for the table. Values are prefixed to visually
 506:      * indicate relative depth in the tree.
 507:      *
 508:      * ### Options
 509:      *
 510:      * - keyPath: A dot separated path to the field that will be the result array key, or a closure to
 511:      *   return the key from the provided row.
 512:      * - valuePath: A dot separated path to the field that is the array's value, or a closure to
 513:      *   return the value from the provided row.
 514:      * - spacer: A string to be used as prefix for denoting the depth in the tree for each item.
 515:      *
 516:      * @param \Cake\ORM\Query $query The query object to format.
 517:      * @param array $options Array of options as described above.
 518:      * @return \Cake\ORM\Query Augmented query.
 519:      */
 520:     public function formatTreeList(Query $query, array $options = [])
 521:     {
 522:         return $query->formatResults(function ($results) use ($options) {
 523:             /* @var \Cake\Collection\CollectionTrait $results */
 524:             $options += [
 525:                 'keyPath' => $this->_getPrimaryKey(),
 526:                 'valuePath' => $this->_table->getDisplayField(),
 527:                 'spacer' => '_',
 528:             ];
 529: 
 530:             return $results
 531:                 ->listNested()
 532:                 ->printer($options['valuePath'], $options['keyPath'], $options['spacer']);
 533:         });
 534:     }
 535: 
 536:     /**
 537:      * Removes the current node from the tree, by positioning it as a new root
 538:      * and re-parents all children up one level.
 539:      *
 540:      * Note that the node will not be deleted just moved away from its current position
 541:      * without moving its children with it.
 542:      *
 543:      * @param \Cake\Datasource\EntityInterface $node The node to remove from the tree
 544:      * @return \Cake\Datasource\EntityInterface|false the node after being removed from the tree or
 545:      * false on error
 546:      */
 547:     public function removeFromTree(EntityInterface $node)
 548:     {
 549:         return $this->_table->getConnection()->transactional(function () use ($node) {
 550:             $this->_ensureFields($node);
 551: 
 552:             return $this->_removeFromTree($node);
 553:         });
 554:     }
 555: 
 556:     /**
 557:      * Helper function containing the actual code for removeFromTree
 558:      *
 559:      * @param \Cake\Datasource\EntityInterface $node The node to remove from the tree
 560:      * @return \Cake\Datasource\EntityInterface|false the node after being removed from the tree or
 561:      * false on error
 562:      */
 563:     protected function _removeFromTree($node)
 564:     {
 565:         $config = $this->getConfig();
 566:         $left = $node->get($config['left']);
 567:         $right = $node->get($config['right']);
 568:         $parent = $node->get($config['parent']);
 569: 
 570:         $node->set($config['parent'], null);
 571: 
 572:         if ($right - $left == 1) {
 573:             return $this->_table->save($node);
 574:         }
 575: 
 576:         $primary = $this->_getPrimaryKey();
 577:         $this->_table->updateAll(
 578:             [$config['parent'] => $parent],
 579:             [$config['parent'] => $node->get($primary)]
 580:         );
 581:         $this->_sync(1, '-', 'BETWEEN ' . ($left + 1) . ' AND ' . ($right - 1));
 582:         $this->_sync(2, '-', "> {$right}");
 583:         $edge = $this->_getMax();
 584:         $node->set($config['left'], $edge + 1);
 585:         $node->set($config['right'], $edge + 2);
 586:         $fields = [$config['parent'], $config['left'], $config['right']];
 587: 
 588:         $this->_table->updateAll($node->extract($fields), [$primary => $node->get($primary)]);
 589: 
 590:         foreach ($fields as $field) {
 591:             $node->setDirty($field, false);
 592:         }
 593: 
 594:         return $node;
 595:     }
 596: 
 597:     /**
 598:      * Reorders the node without changing its parent.
 599:      *
 600:      * If the node is the first child, or is a top level node with no previous node
 601:      * this method will return false
 602:      *
 603:      * @param \Cake\Datasource\EntityInterface $node The node to move
 604:      * @param int|bool $number How many places to move the node, or true to move to first position
 605:      * @throws \Cake\Datasource\Exception\RecordNotFoundException When node was not found
 606:      * @return \Cake\Datasource\EntityInterface|bool $node The node after being moved or false on failure
 607:      */
 608:     public function moveUp(EntityInterface $node, $number = 1)
 609:     {
 610:         if ($number < 1) {
 611:             return false;
 612:         }
 613: 
 614:         return $this->_table->getConnection()->transactional(function () use ($node, $number) {
 615:             $this->_ensureFields($node);
 616: 
 617:             return $this->_moveUp($node, $number);
 618:         });
 619:     }
 620: 
 621:     /**
 622:      * Helper function used with the actual code for moveUp
 623:      *
 624:      * @param \Cake\Datasource\EntityInterface $node The node to move
 625:      * @param int|bool $number How many places to move the node, or true to move to first position
 626:      * @throws \Cake\Datasource\Exception\RecordNotFoundException When node was not found
 627:      * @return \Cake\Datasource\EntityInterface|bool $node The node after being moved or false on failure
 628:      */
 629:     protected function _moveUp($node, $number)
 630:     {
 631:         $config = $this->getConfig();
 632:         list($parent, $left, $right) = [$config['parent'], $config['left'], $config['right']];
 633:         list($nodeParent, $nodeLeft, $nodeRight) = array_values($node->extract([$parent, $left, $right]));
 634: 
 635:         $targetNode = null;
 636:         if ($number !== true) {
 637:             $targetNode = $this->_scope($this->_table->find())
 638:                 ->select([$left, $right])
 639:                 ->where(["$parent IS" => $nodeParent])
 640:                 ->where(function ($exp) use ($config, $nodeLeft) {
 641:                     /* @var \Cake\Database\Expression\QueryExpression $exp */
 642:                     return $exp->lt($config['rightField'], $nodeLeft);
 643:                 })
 644:                 ->orderDesc($config['leftField'])
 645:                 ->offset($number - 1)
 646:                 ->limit(1)
 647:                 ->first();
 648:         }
 649:         if (!$targetNode) {
 650:             $targetNode = $this->_scope($this->_table->find())
 651:                 ->select([$left, $right])
 652:                 ->where(["$parent IS" => $nodeParent])
 653:                 ->where(function ($exp) use ($config, $nodeLeft) {
 654:                     /* @var \Cake\Database\Expression\QueryExpression $exp */
 655:                     return $exp->lt($config['rightField'], $nodeLeft);
 656:                 })
 657:                 ->orderAsc($config['leftField'])
 658:                 ->limit(1)
 659:                 ->first();
 660: 
 661:             if (!$targetNode) {
 662:                 return $node;
 663:             }
 664:         }
 665: 
 666:         list($targetLeft) = array_values($targetNode->extract([$left, $right]));
 667:         $edge = $this->_getMax();
 668:         $leftBoundary = $targetLeft;
 669:         $rightBoundary = $nodeLeft - 1;
 670: 
 671:         $nodeToEdge = $edge - $nodeLeft + 1;
 672:         $shift = $nodeRight - $nodeLeft + 1;
 673:         $nodeToHole = $edge - $leftBoundary + 1;
 674:         $this->_sync($nodeToEdge, '+', "BETWEEN {$nodeLeft} AND {$nodeRight}");
 675:         $this->_sync($shift, '+', "BETWEEN {$leftBoundary} AND {$rightBoundary}");
 676:         $this->_sync($nodeToHole, '-', "> {$edge}");
 677: 
 678:         $node->set($left, $targetLeft);
 679:         $node->set($right, $targetLeft + ($nodeRight - $nodeLeft));
 680: 
 681:         $node->setDirty($left, false);
 682:         $node->setDirty($right, false);
 683: 
 684:         return $node;
 685:     }
 686: 
 687:     /**
 688:      * Reorders the node without changing the parent.
 689:      *
 690:      * If the node is the last child, or is a top level node with no subsequent node
 691:      * this method will return false
 692:      *
 693:      * @param \Cake\Datasource\EntityInterface $node The node to move
 694:      * @param int|bool $number How many places to move the node or true to move to last position
 695:      * @throws \Cake\Datasource\Exception\RecordNotFoundException When node was not found
 696:      * @return \Cake\Datasource\EntityInterface|bool the entity after being moved or false on failure
 697:      */
 698:     public function moveDown(EntityInterface $node, $number = 1)
 699:     {
 700:         if ($number < 1) {
 701:             return false;
 702:         }
 703: 
 704:         return $this->_table->getConnection()->transactional(function () use ($node, $number) {
 705:             $this->_ensureFields($node);
 706: 
 707:             return $this->_moveDown($node, $number);
 708:         });
 709:     }
 710: 
 711:     /**
 712:      * Helper function used with the actual code for moveDown
 713:      *
 714:      * @param \Cake\Datasource\EntityInterface $node The node to move
 715:      * @param int|bool $number How many places to move the node, or true to move to last position
 716:      * @throws \Cake\Datasource\Exception\RecordNotFoundException When node was not found
 717:      * @return \Cake\Datasource\EntityInterface|bool $node The node after being moved or false on failure
 718:      */
 719:     protected function _moveDown($node, $number)
 720:     {
 721:         $config = $this->getConfig();
 722:         list($parent, $left, $right) = [$config['parent'], $config['left'], $config['right']];
 723:         list($nodeParent, $nodeLeft, $nodeRight) = array_values($node->extract([$parent, $left, $right]));
 724: 
 725:         $targetNode = null;
 726:         if ($number !== true) {
 727:             $targetNode = $this->_scope($this->_table->find())
 728:                 ->select([$left, $right])
 729:                 ->where(["$parent IS" => $nodeParent])
 730:                 ->where(function ($exp) use ($config, $nodeRight) {
 731:                     /* @var \Cake\Database\Expression\QueryExpression $exp */
 732:                     return $exp->gt($config['leftField'], $nodeRight);
 733:                 })
 734:                 ->orderAsc($config['leftField'])
 735:                 ->offset($number - 1)
 736:                 ->limit(1)
 737:                 ->first();
 738:         }
 739:         if (!$targetNode) {
 740:             $targetNode = $this->_scope($this->_table->find())
 741:                 ->select([$left, $right])
 742:                 ->where(["$parent IS" => $nodeParent])
 743:                 ->where(function ($exp) use ($config, $nodeRight) {
 744:                     /* @var \Cake\Database\Expression\QueryExpression $exp */
 745:                     return $exp->gt($config['leftField'], $nodeRight);
 746:                 })
 747:                 ->orderDesc($config['leftField'])
 748:                 ->limit(1)
 749:                 ->first();
 750: 
 751:             if (!$targetNode) {
 752:                 return $node;
 753:             }
 754:         }
 755: 
 756:         list(, $targetRight) = array_values($targetNode->extract([$left, $right]));
 757:         $edge = $this->_getMax();
 758:         $leftBoundary = $nodeRight + 1;
 759:         $rightBoundary = $targetRight;
 760: 
 761:         $nodeToEdge = $edge - $nodeLeft + 1;
 762:         $shift = $nodeRight - $nodeLeft + 1;
 763:         $nodeToHole = $edge - $rightBoundary + $shift;
 764:         $this->_sync($nodeToEdge, '+', "BETWEEN {$nodeLeft} AND {$nodeRight}");
 765:         $this->_sync($shift, '-', "BETWEEN {$leftBoundary} AND {$rightBoundary}");
 766:         $this->_sync($nodeToHole, '-', "> {$edge}");
 767: 
 768:         $node->set($left, $targetRight - ($nodeRight - $nodeLeft));
 769:         $node->set($right, $targetRight);
 770: 
 771:         $node->setDirty($left, false);
 772:         $node->setDirty($right, false);
 773: 
 774:         return $node;
 775:     }
 776: 
 777:     /**
 778:      * Returns a single node from the tree from its primary key
 779:      *
 780:      * @param mixed $id Record id.
 781:      * @return \Cake\Datasource\EntityInterface
 782:      * @throws \Cake\Datasource\Exception\RecordNotFoundException When node was not found
 783:      */
 784:     protected function _getNode($id)
 785:     {
 786:         $config = $this->getConfig();
 787:         list($parent, $left, $right) = [$config['parent'], $config['left'], $config['right']];
 788:         $primaryKey = $this->_getPrimaryKey();
 789:         $fields = [$parent, $left, $right];
 790:         if ($config['level']) {
 791:             $fields[] = $config['level'];
 792:         }
 793: 
 794:         $node = $this->_scope($this->_table->find())
 795:             ->select($fields)
 796:             ->where([$this->_table->aliasField($primaryKey) => $id])
 797:             ->first();
 798: 
 799:         if (!$node) {
 800:             throw new RecordNotFoundException("Node \"{$id}\" was not found in the tree.");
 801:         }
 802: 
 803:         return $node;
 804:     }
 805: 
 806:     /**
 807:      * Recovers the lft and right column values out of the hierarchy defined by the
 808:      * parent column.
 809:      *
 810:      * @return void
 811:      */
 812:     public function recover()
 813:     {
 814:         $this->_table->getConnection()->transactional(function () {
 815:             $this->_recoverTree();
 816:         });
 817:     }
 818: 
 819:     /**
 820:      * Recursive method used to recover a single level of the tree
 821:      *
 822:      * @param int $counter The Last left column value that was assigned
 823:      * @param mixed $parentId the parent id of the level to be recovered
 824:      * @param int $level Node level
 825:      * @return int The next value to use for the left column
 826:      */
 827:     protected function _recoverTree($counter = 0, $parentId = null, $level = -1)
 828:     {
 829:         $config = $this->getConfig();
 830:         list($parent, $left, $right) = [$config['parent'], $config['left'], $config['right']];
 831:         $primaryKey = $this->_getPrimaryKey();
 832:         $aliasedPrimaryKey = $this->_table->aliasField($primaryKey);
 833:         $order = $config['recoverOrder'] ?: $aliasedPrimaryKey;
 834: 
 835:         $query = $this->_scope($this->_table->query())
 836:             ->select([$aliasedPrimaryKey])
 837:             ->where([$this->_table->aliasField($parent) . ' IS' => $parentId])
 838:             ->order($order)
 839:             ->disableHydration();
 840: 
 841:         $leftCounter = $counter;
 842:         $nextLevel = $level + 1;
 843:         foreach ($query as $row) {
 844:             $counter++;
 845:             $counter = $this->_recoverTree($counter, $row[$primaryKey], $nextLevel);
 846:         }
 847: 
 848:         if ($parentId === null) {
 849:             return $counter;
 850:         }
 851: 
 852:         $fields = [$left => $leftCounter, $right => $counter + 1];
 853:         if ($config['level']) {
 854:             $fields[$config['level']] = $level;
 855:         }
 856: 
 857:         $this->_table->updateAll(
 858:             $fields,
 859:             [$primaryKey => $parentId]
 860:         );
 861: 
 862:         return $counter + 1;
 863:     }
 864: 
 865:     /**
 866:      * Returns the maximum index value in the table.
 867:      *
 868:      * @return int
 869:      */
 870:     protected function _getMax()
 871:     {
 872:         $field = $this->_config['right'];
 873:         $rightField = $this->_config['rightField'];
 874:         $edge = $this->_scope($this->_table->find())
 875:             ->select([$field])
 876:             ->orderDesc($rightField)
 877:             ->first();
 878: 
 879:         if (empty($edge->{$field})) {
 880:             return 0;
 881:         }
 882: 
 883:         return $edge->{$field};
 884:     }
 885: 
 886:     /**
 887:      * Auxiliary function used to automatically alter the value of both the left and
 888:      * right columns by a certain amount that match the passed conditions
 889:      *
 890:      * @param int $shift the value to use for operating the left and right columns
 891:      * @param string $dir The operator to use for shifting the value (+/-)
 892:      * @param string $conditions a SQL snipped to be used for comparing left or right
 893:      * against it.
 894:      * @param bool $mark whether to mark the updated values so that they can not be
 895:      * modified by future calls to this function.
 896:      * @return void
 897:      */
 898:     protected function _sync($shift, $dir, $conditions, $mark = false)
 899:     {
 900:         $config = $this->_config;
 901: 
 902:         foreach ([$config['leftField'], $config['rightField']] as $field) {
 903:             $query = $this->_scope($this->_table->query());
 904:             $exp = $query->newExpr();
 905: 
 906:             $movement = clone $exp;
 907:             $movement->add($field)->add((string)$shift)->setConjunction($dir);
 908: 
 909:             $inverse = clone $exp;
 910:             $movement = $mark ?
 911:                 $inverse->add($movement)->setConjunction('*')->add('-1') :
 912:                 $movement;
 913: 
 914:             $where = clone $exp;
 915:             $where->add($field)->add($conditions)->setConjunction('');
 916: 
 917:             $query->update()
 918:                 ->set($exp->eq($field, $movement))
 919:                 ->where($where);
 920: 
 921:             $query->execute()->closeCursor();
 922:         }
 923:     }
 924: 
 925:     /**
 926:      * Alters the passed query so that it only returns scoped records as defined
 927:      * in the tree configuration.
 928:      *
 929:      * @param \Cake\ORM\Query $query the Query to modify
 930:      * @return \Cake\ORM\Query
 931:      */
 932:     protected function _scope($query)
 933:     {
 934:         $scope = $this->getConfig('scope');
 935: 
 936:         if (is_array($scope)) {
 937:             return $query->where($scope);
 938:         }
 939:         if (is_callable($scope)) {
 940:             return $scope($query);
 941:         }
 942: 
 943:         return $query;
 944:     }
 945: 
 946:     /**
 947:      * Ensures that the provided entity contains non-empty values for the left and
 948:      * right fields
 949:      *
 950:      * @param \Cake\Datasource\EntityInterface $entity The entity to ensure fields for
 951:      * @return void
 952:      */
 953:     protected function _ensureFields($entity)
 954:     {
 955:         $config = $this->getConfig();
 956:         $fields = [$config['left'], $config['right']];
 957:         $values = array_filter($entity->extract($fields));
 958:         if (count($values) === count($fields)) {
 959:             return;
 960:         }
 961: 
 962:         $fresh = $this->_table->get($entity->get($this->_getPrimaryKey()), $fields);
 963:         $entity->set($fresh->extract($fields), ['guard' => false]);
 964: 
 965:         foreach ($fields as $field) {
 966:             $entity->setDirty($field, false);
 967:         }
 968:     }
 969: 
 970:     /**
 971:      * Returns a single string value representing the primary key of the attached table
 972:      *
 973:      * @return string
 974:      */
 975:     protected function _getPrimaryKey()
 976:     {
 977:         if (!$this->_primaryKey) {
 978:             $primaryKey = (array)$this->_table->getPrimaryKey();
 979:             $this->_primaryKey = $primaryKey[0];
 980:         }
 981: 
 982:         return $this->_primaryKey;
 983:     }
 984: 
 985:     /**
 986:      * Returns the depth level of a node in the tree.
 987:      *
 988:      * @param int|string|\Cake\Datasource\EntityInterface $entity The entity or primary key get the level of.
 989:      * @return int|bool Integer of the level or false if the node does not exist.
 990:      */
 991:     public function getLevel($entity)
 992:     {
 993:         $primaryKey = $this->_getPrimaryKey();
 994:         $id = $entity;
 995:         if ($entity instanceof EntityInterface) {
 996:             $id = $entity->get($primaryKey);
 997:         }
 998:         $config = $this->getConfig();
 999:         $entity = $this->_table->find('all')
1000:             ->select([$config['left'], $config['right']])
1001:             ->where([$primaryKey => $id])
1002:             ->first();
1003: 
1004:         if ($entity === null) {
1005:             return false;
1006:         }
1007: 
1008:         $query = $this->_table->find('all')->where([
1009:             $config['left'] . ' <' => $entity[$config['left']],
1010:             $config['right'] . ' >' => $entity[$config['right']],
1011:         ]);
1012: 
1013:         return $this->_scope($query)->count();
1014:     }
1015: }
1016: