8f46e581bd75f8896607f31113a86c4668b05629
[Packages/TYPO3.CMS.git] / typo3 / sysext / backend / Classes / Tree / SortedTreeNodeCollection.php
1 <?php
2 namespace TYPO3\CMS\Backend\Tree;
3
4 /*
5 * This file is part of the TYPO3 CMS project.
6 *
7 * It is free software; you can redistribute it and/or modify it under
8 * the terms of the GNU General Public License, either version 2
9 * of the License, or any later version.
10 *
11 * For the full copyright and license information, please read the
12 * LICENSE.txt file that was distributed with this source code.
13 *
14 * The TYPO3 project - inspiring people to share!
15 */
16
17 /**
18 * Sorted Tree Node Collection
19 *
20 * Note: This collection works only with integers as offset keys and not
21 * with much datasets. You have been warned!
22 */
23 class SortedTreeNodeCollection extends \TYPO3\CMS\Backend\Tree\TreeNodeCollection
24 {
25 /**
26 * Checks if a specific node is inside the collection
27 *
28 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
29 * @return bool
30 */
31 public function contains(\TYPO3\CMS\Backend\Tree\TreeNode $node)
32 {
33 return $this->offsetOf($node) !== -1;
34 }
35
36 /**
37 * Returns the offset key of given node
38 *
39 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
40 * @return int
41 */
42 protected function offsetOf(\TYPO3\CMS\Backend\Tree\TreeNode $node)
43 {
44 return $this->binarySearch($node, 0, $this->count() - 1);
45 }
46
47 /**
48 * Binary search that returns the offset of a given node
49 *
50 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
51 * @param int $start
52 * @param int $end
53 * @return int
54 */
55 protected function binarySearch(\TYPO3\CMS\Backend\Tree\TreeNode $node, $start, $end)
56 {
57 if (!$start && $end - $start >= 2 || $end - $start > 2) {
58 $divider = ceil(($end - $start) / 2);
59 if ($this->offsetGet($divider)->equals($node)) {
60 return $divider;
61 } elseif ($this->offsetGet($divider)->compareTo($node) > 0) {
62 return $this->binarySearch($node, $start, $divider - 1);
63 } else {
64 return $this->binarySearch($node, $divider + 1, $end);
65 }
66 } else {
67 if ($this->offsetGet($start)->equals($node)) {
68 return $start;
69 } elseif ($this->offsetGet($end)->equals($node)) {
70 return $end;
71 } else {
72 return -1;
73 }
74 }
75 }
76
77 /**
78 * Normalizes the array by reordering the keys
79 */
80 protected function normalize()
81 {
82 $nodes = [];
83 foreach ($this as $node) {
84 $nodes[] = $node;
85 }
86 $this->exchangeArray($nodes);
87 }
88
89 /**
90 * Adds a node to the internal list in a sorted approach
91 *
92 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
93 */
94 public function append($node)
95 {
96 parent::append($node);
97 $this->asort();
98 $this->normalize();
99 }
100 }