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