[TASK] Remove @package and @subpackage annotations
[Packages/TYPO3.CMS.git] / typo3 / sysext / backend / Classes / Tree / SortedTreeNodeCollection.php
1 <?php
2 namespace TYPO3\CMS\Backend\Tree;
3
4 /***************************************************************
5 * Copyright notice
6 *
7 * (c) 2010-2011 TYPO3 Tree Team <http://forge.typo3.org/projects/typo3v4-extjstrees>
8 * All rights reserved
9 *
10 * This script is part of the TYPO3 project. The TYPO3 project is
11 * free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version.
15 *
16 * The GNU General Public License can be found at
17 * http://www.gnu.org/copyleft/gpl.html.
18 * A copy is found in the textfile GPL.txt and important notices to the license
19 * from the author is found in LICENSE.txt distributed with these scripts.
20 *
21 *
22 * This script is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
26 *
27 * This copyright notice MUST APPEAR in all copies of the script!
28 ***************************************************************/
29 /**
30 * Sorted Tree Node Collection
31 *
32 * Note: This collection works only with integers as offset keys and not
33 * with much datasets. You have been warned!
34 *
35 * @author Stefan Galinski <stefan.galinski@gmail.com>
36 * @author Steffen Ritter <info@steffen-ritter.net>
37 */
38 class SortedTreeNodeCollection extends \TYPO3\CMS\Backend\Tree\TreeNodeCollection {
39
40 /**
41 * Checks if a specific node is inside the collection
42 *
43 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
44 * @return boolean
45 */
46 public function contains(\TYPO3\CMS\Backend\Tree\TreeNode $node) {
47 return $this->offsetOf($node) !== -1;
48 }
49
50 /**
51 * Returns the offset key of given node
52 *
53 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
54 * @return int
55 */
56 protected function offsetOf(\TYPO3\CMS\Backend\Tree\TreeNode $node) {
57 return $this->binarySearch($node, 0, $this->count() - 1);
58 }
59
60 /**
61 * Binary search that returns the offset of a given node
62 *
63 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
64 * @param integer $start
65 * @param integer $end
66 * @return integer
67 */
68 protected function binarySearch(\TYPO3\CMS\Backend\Tree\TreeNode $node, $start, $end) {
69 if (!$start && $end - $start >= 2 || $end - $start > 2) {
70 $divider = ceil(($end - $start) / 2);
71 if ($this->offsetGet($divider)->equals($node)) {
72 return $divider;
73 } elseif ($this->offsetGet($divider)->compareTo($node) > 0) {
74 return $this->binarySearch($node, $start, $divider - 1);
75 } else {
76 return $this->binarySearch($node, $divider + 1, $end);
77 }
78 } else {
79 if ($this->offsetGet($start)->equals($node)) {
80 return $start;
81 } elseif ($this->offsetGet($end)->equals($node)) {
82 return $end;
83 } else {
84 return -1;
85 }
86 }
87 }
88
89 /**
90 * Normalizes the array by reordering the keys
91 *
92 * @return void
93 */
94 protected function normalize() {
95 $nodes = array();
96 foreach ($this as $node) {
97 $nodes[] = $node;
98 }
99 $this->exchangeArray($nodes);
100 }
101
102 /**
103 * Adds a node to the internal list in a sorted approach
104 *
105 * @param \TYPO3\CMS\Backend\Tree\TreeNode $node
106 * @return void
107 */
108 public function append(\TYPO3\CMS\Backend\Tree\TreeNode $node) {
109 parent::append($node);
110 $this->asort();
111 $this->normalize();
112 }
113
114 }
115
116
117 ?>