[TASK] Clean up the phpDoc of t3lib/tree/
[Packages/TYPO3.CMS.git] / t3lib / tree / class.t3lib_tree_sortednodecollection.php
1 <?php
2 /***************************************************************
3 * Copyright notice
4 *
5 * (c) 2010-2011 TYPO3 Tree Team <http://forge.typo3.org/projects/typo3v4-extjstrees>
6 * All rights reserved
7 *
8 * This script is part of the TYPO3 project. The TYPO3 project is
9 * free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
13 *
14 * The GNU General Public License can be found at
15 * http://www.gnu.org/copyleft/gpl.html.
16 * A copy is found in the textfile GPL.txt and important notices to the license
17 * from the author is found in LICENSE.txt distributed with these scripts.
18 *
19 *
20 * This script is distributed in the hope that it will be useful,
21 * but WITHOUT ANY WARRANTY; without even the implied warranty of
22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 * GNU General Public License for more details.
24 *
25 * This copyright notice MUST APPEAR in all copies of the script!
26 ***************************************************************/
27
28 /**
29 * Sorted Tree Node Collection
30 *
31 * Note: This collection works only with integers as offset keys and not
32 * with much datasets. You have been warned!
33 *
34 * @author Stefan Galinski <stefan.galinski@gmail.com>
35 * @author Steffen Ritter <info@steffen-ritter.net>
36 * @package TYPO3
37 * @subpackage t3lib
38 */
39 class t3lib_tree_SortedNodeCollection extends t3lib_tree_NodeCollection {
40 /**
41 * Checks if a specific node is inside the collection
42 *
43 * @param t3lib_tree_Node $node
44 * @return boolean
45 */
46 public function contains(t3lib_tree_Node $node) {
47 return $this->offsetOf($node) !== -1;
48 }
49
50 /**
51 * Returns the offset key of given node
52 *
53 * @param t3lib_tree_Node $node
54 * @return int
55 */
56 protected function offsetOf(t3lib_tree_Node $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 t3lib_tree_Node $node
64 * @param integer $start
65 * @param integer $end
66 * @return integer
67 */
68 protected function binarySearch(t3lib_tree_Node $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 t3lib_tree_Node $node
106 * @return void
107 */
108 public function append(t3lib_tree_Node $node) {
109 parent::append($node);
110 $this->asort();
111 $this->normalize();
112 }
113
114 }
115 ?>