Commit | Line | Data |
---|---|---|
7caf74d3 FB |
1 | <?php |
2 | /*************************************************************************** | |
3 | * Copyright (C) 2003-2010 Polytechnique.org * | |
4 | * http://opensource.polytechnique.org/ * | |
5 | * * | |
6 | * This program is free software; you can redistribute it and/or modify * | |
7 | * it under the terms of the GNU General Public License as published by * | |
8 | * the Free Software Foundation; either version 2 of the License, or * | |
9 | * (at your option) any later version. * | |
10 | * * | |
11 | * This program is distributed in the hope that it will be useful, * | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
14 | * GNU General Public License for more details. * | |
15 | * * | |
16 | * You should have received a copy of the GNU General Public License * | |
17 | * along with this program; if not, write to the Free Software * | |
18 | * Foundation, Inc., * | |
19 | * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * | |
20 | ***************************************************************************/ | |
21 | ||
22 | require_once dirname(__FILE__) . '/../include/test.inc.php'; | |
23 | ||
24 | class HeapTest extends PlTestCase | |
25 | { | |
26 | public static function compare($a, $b) | |
27 | { | |
28 | return $a - $b; | |
29 | } | |
30 | ||
31 | public function testHeap() | |
32 | { | |
33 | $heap = new PlHeap(array('HeapTest', 'compare')); | |
748543a7 | 34 | $this->assertSame(0, $heap->count()); |
7caf74d3 FB |
35 | $this->assertNull($heap->pop()); |
36 | ||
37 | $heap->push(1); | |
748543a7 FB |
38 | $this->assertSame(1, $heap->count()); |
39 | $this->assertSame(1, $heap->pop()); | |
40 | $this->assertSame(0, $heap->count()); | |
7caf74d3 FB |
41 | $this->assertNull($heap->pop()); |
42 | ||
43 | $heap->push(2); | |
44 | $heap->push(1); | |
45 | $heap->push(4); | |
46 | $heap->push(3); | |
748543a7 FB |
47 | $this->assertSame(4, $heap->count()); |
48 | $this->assertSame(1, $heap->pop()); | |
49 | $this->assertSame(3, $heap->count()); | |
50 | $this->assertSame(2, $heap->pop()); | |
51 | $this->assertSame(2, $heap->count()); | |
7caf74d3 | 52 | $heap->push(-1); |
748543a7 FB |
53 | $this->assertSame(3, $heap->count()); |
54 | $this->assertSame(-1, $heap->pop()); | |
55 | $this->assertSame(2, $heap->count()); | |
56 | $this->assertSame(3, $heap->pop()); | |
57 | $this->assertSame(1, $heap->count()); | |
58 | $this->assertSame(4, $heap->pop()); | |
59 | $this->assertSame(0, $heap->count()); | |
7caf74d3 FB |
60 | $this->assertNull($heap->pop()); |
61 | } | |
62 | ||
63 | public function testHeapIt() | |
64 | { | |
65 | $heap = new PlHeap(array('HeapTest', 'compare')); | |
66 | $heap->push(2); | |
67 | $heap->push(1); | |
68 | $heap->push(4); | |
69 | $heap->push(3); | |
70 | ||
71 | $it = $heap->iterator(); | |
748543a7 | 72 | $this->assertSame(4, $it->total()); |
7caf74d3 | 73 | |
748543a7 | 74 | $this->assertSame(1, $it->next()); |
7caf74d3 FB |
75 | $this->assertTrue($it->first()); |
76 | $this->assertFalse($it->last()); | |
77 | ||
748543a7 | 78 | $this->assertSame(2, $it->next()); |
7caf74d3 FB |
79 | $this->assertFalse($it->first()); |
80 | $this->assertFalse($it->last()); | |
81 | ||
748543a7 | 82 | $this->assertSame(3, $it->next()); |
7caf74d3 FB |
83 | $this->assertFalse($it->first()); |
84 | $this->assertFalse($it->last()); | |
85 | ||
748543a7 | 86 | $this->assertSame(4, $it->next()); |
7caf74d3 FB |
87 | $this->assertFalse($it->first()); |
88 | $this->assertTrue($it->last()); | |
89 | ||
90 | $this->assertNull($it->next()); | |
748543a7 | 91 | $this->assertSame(4, $heap->count()); |
7caf74d3 FB |
92 | } |
93 | ||
94 | public function testMergeSortedIterator() | |
95 | { | |
96 | $its = array(); | |
97 | $its[] = PlIteratorUtils::fromArray(array(2, 4, 8, 16), 1, true); | |
98 | $its[] = PlIteratorUtils::fromArray(array(3, 9, 27), 1, true); | |
99 | $its[] = PlIteratorUtils::fromArray(array(4, 16, 32), 1, true); | |
100 | $it = PlIteratorUtils::merge($its, array('HeapTest', 'compare')); | |
748543a7 | 101 | $this->assertSame(10, $it->total()); |
7caf74d3 | 102 | |
748543a7 | 103 | $this->assertSame(2, $it->next()); |
7caf74d3 FB |
104 | $this->assertTrue($it->first()); |
105 | $this->assertFalse($it->last()); | |
106 | ||
748543a7 | 107 | $this->assertSame(3, $it->next()); |
7caf74d3 FB |
108 | $this->assertFalse($it->first()); |
109 | $this->assertFalse($it->last()); | |
110 | ||
748543a7 | 111 | $this->assertSame(4, $it->next()); |
7caf74d3 FB |
112 | $this->assertFalse($it->first()); |
113 | $this->assertFalse($it->last()); | |
114 | ||
748543a7 | 115 | $this->assertSame(4, $it->next()); |
7caf74d3 FB |
116 | $this->assertFalse($it->first()); |
117 | $this->assertFalse($it->last()); | |
118 | ||
748543a7 | 119 | $this->assertSame(8, $it->next()); |
7caf74d3 FB |
120 | $this->assertFalse($it->first()); |
121 | $this->assertFalse($it->last()); | |
122 | ||
748543a7 | 123 | $this->assertSame(9, $it->next()); |
7caf74d3 FB |
124 | $this->assertFalse($it->first()); |
125 | $this->assertFalse($it->last()); | |
126 | ||
748543a7 | 127 | $this->assertSame(16, $it->next()); |
7caf74d3 FB |
128 | $this->assertFalse($it->first()); |
129 | $this->assertFalse($it->last()); | |
130 | ||
748543a7 | 131 | $this->assertSame(16, $it->next()); |
7caf74d3 FB |
132 | $this->assertFalse($it->first()); |
133 | $this->assertFalse($it->last()); | |
134 | ||
748543a7 | 135 | $this->assertSame(27, $it->next()); |
7caf74d3 FB |
136 | $this->assertFalse($it->first()); |
137 | $this->assertFalse($it->last()); | |
138 | ||
748543a7 | 139 | $this->assertSame(32, $it->next()); |
7caf74d3 FB |
140 | $this->assertFalse($it->first()); |
141 | $this->assertTrue($it->last()); | |
142 | ||
143 | $this->assertNull($it->next()); | |
144 | } | |
145 | ||
146 | public function testMergeUnsortedIterator() | |
147 | { | |
148 | $its = array(); | |
149 | $its[] = PlIteratorUtils::fromArray(array(8, 4, 16, 2), 1, true); | |
150 | $its[] = PlIteratorUtils::fromArray(array(3, 27, 9), 1, true); | |
151 | $its[] = PlIteratorUtils::fromArray(array(32, 4, 16), 1, true); | |
152 | $it = PlIteratorUtils::merge($its, array('HeapTest', 'compare'), false); | |
748543a7 | 153 | $this->assertSame(10, $it->total()); |
7caf74d3 | 154 | |
748543a7 | 155 | $this->assertSame(2, $it->next()); |
7caf74d3 FB |
156 | $this->assertTrue($it->first()); |
157 | $this->assertFalse($it->last()); | |
158 | ||
748543a7 | 159 | $this->assertSame(3, $it->next()); |
7caf74d3 FB |
160 | $this->assertFalse($it->first()); |
161 | $this->assertFalse($it->last()); | |
162 | ||
748543a7 | 163 | $this->assertSame(4, $it->next()); |
7caf74d3 FB |
164 | $this->assertFalse($it->first()); |
165 | $this->assertFalse($it->last()); | |
166 | ||
748543a7 | 167 | $this->assertSame(4, $it->next()); |
7caf74d3 FB |
168 | $this->assertFalse($it->first()); |
169 | $this->assertFalse($it->last()); | |
170 | ||
748543a7 | 171 | $this->assertSame(8, $it->next()); |
7caf74d3 FB |
172 | $this->assertFalse($it->first()); |
173 | $this->assertFalse($it->last()); | |
174 | ||
748543a7 | 175 | $this->assertSame(9, $it->next()); |
7caf74d3 FB |
176 | $this->assertFalse($it->first()); |
177 | $this->assertFalse($it->last()); | |
178 | ||
748543a7 | 179 | $this->assertSame(16, $it->next()); |
7caf74d3 FB |
180 | $this->assertFalse($it->first()); |
181 | $this->assertFalse($it->last()); | |
182 | ||
748543a7 | 183 | $this->assertSame(16, $it->next()); |
7caf74d3 FB |
184 | $this->assertFalse($it->first()); |
185 | $this->assertFalse($it->last()); | |
186 | ||
748543a7 | 187 | $this->assertSame(27, $it->next()); |
7caf74d3 FB |
188 | $this->assertFalse($it->first()); |
189 | $this->assertFalse($it->last()); | |
190 | ||
748543a7 | 191 | $this->assertSame(32, $it->next()); |
7caf74d3 FB |
192 | $this->assertFalse($it->first()); |
193 | $this->assertTrue($it->last()); | |
194 | ||
195 | $this->assertNull($it->next()); | |
196 | } | |
197 | ||
198 | } | |
199 | ||
200 | ||
201 | // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: | |
202 | ?> |