Commit | Line | Data |
---|---|---|
63f00a3f FB |
1 | <?php |
2 | /*************************************************************************** | |
2ab75571 | 3 | * Copyright (C) 2003-2010 Polytechnique.org * |
63f00a3f FB |
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 | ||
5177a1b5 FB |
22 | class PlIteratorUtils |
23 | { | |
24 | /** Build an iterator over an array. | |
25 | * @param array The array. | |
26 | * @param depth The depth of iteration. | |
27 | * @return an iterator that return entries in the form | |
28 | * array(key => array(0 => key_for_depth0 [, 1 => key_for_depths1, ...]), | |
29 | * value => the value); | |
30 | */ | |
e94c4a17 | 31 | public static function fromArray(array $array, $depth = 1, $flat = false) |
5177a1b5 | 32 | { |
e94c4a17 | 33 | return new PlArrayIterator($array, $depth, $flat); |
5177a1b5 FB |
34 | } |
35 | ||
36 | ||
37 | /** Sort an iterator using the given sort callback. | |
38 | * @param iterator The iterator to sort. | |
39 | * @param callback The callback for comparison. | |
40 | * @return a new iterator with the entries sorted. | |
41 | */ | |
42 | public static function sort(PlIterator $iterator, $callback) | |
43 | { | |
44 | $heap = new PlHeap($callback); | |
45 | while ($item = $iterator->next()) { | |
46 | $heap->push($item); | |
47 | } | |
48 | return $heap->iterator(); | |
49 | } | |
50 | ||
51 | ||
52 | /** Merge several iterator into a unique one. | |
53 | * @param iterators Array of iterators. | |
54 | * @param callback The callback for comparison. | |
55 | * @param sorted Tell wether the iterators are already sorted using the given callback. | |
56 | * @return an iterator. | |
57 | */ | |
58 | public static function merge(array $iterators, $callback, $sorted = true) | |
59 | { | |
60 | return new PlMergeIterator($iterators, $callback, $sorted); | |
61 | } | |
8d37a362 FB |
62 | |
63 | ||
64 | /** Build an iterator that contains only the elements of the given iterator that | |
65 | * match the given condition. The condition should be a callback that takes an element | |
66 | * and returns a boolean. | |
67 | * @param iterator The source iterator | |
68 | * @param callback The condition | |
69 | * @return an iterator | |
70 | */ | |
71 | public static function filter(PlIterator $iterator, $callback) | |
72 | { | |
73 | return new PlFilterIterator($iterator, $callback); | |
74 | } | |
75 | ||
76 | ||
77 | /** Build an iterator that transforms the element of another iterator. The callback | |
78 | * takes an element and transform it into another one. Be careful: if the result | |
79 | * of the callback is null, the iteration ends. | |
80 | * @param iterator The source iterator | |
81 | * @param callback The transformer. | |
82 | */ | |
83 | public static function map(PlIterator $iterator, $callback) | |
84 | { | |
85 | return new PlMapIterator($iterator, $callback); | |
86 | } | |
5177a1b5 | 87 | |
22c8b530 RB |
88 | /** Build an iterator whose values are iterators too; such a 'subIterator' will end |
89 | * when the value of $callback changes | |
90 | * @param iterator The source iterator | |
91 | * @param callback The callback for detecting changes. | |
92 | * @return an iterator | |
93 | */ | |
94 | public static function subIterator(PlIterator $iterator, $callback) | |
95 | { | |
96 | return new SubIterator($iterator, $callback); | |
97 | } | |
98 | ||
99 | /** Returns the callback for '$x -> $x[$key]'; | |
100 | * @param $key the index to retrieve in arrays | |
101 | * @return a callback | |
102 | */ | |
103 | public static function arrayValueCallback($key) | |
104 | { | |
105 | $callback = new _GetArrayValueCallback($key); | |
106 | return array($callback, 'get'); | |
107 | } | |
108 | } | |
5177a1b5 FB |
109 | |
110 | /** Iterates over an array. | |
111 | */ | |
63f00a3f FB |
112 | class PlArrayIterator implements PlIterator |
113 | { | |
114 | private $array; | |
115 | private $depth; | |
116 | ||
117 | private $_its = array(); | |
118 | ||
119 | private $_total; | |
120 | private $_first; | |
121 | private $_last; | |
122 | private $_pos; | |
e94c4a17 | 123 | private $_flat; |
63f00a3f | 124 | |
e94c4a17 | 125 | public function __construct(array &$array, $depth = 1, $flat = false) |
63f00a3f FB |
126 | { |
127 | $this->array =& $array; | |
128 | $this->depth = $depth; | |
129 | $this->_total = $this->count($array, $depth - 1); | |
130 | $this->_pos = 0; | |
131 | $this->_first = false; | |
132 | $this->_last = false; | |
e94c4a17 | 133 | $this->_flat = $flat; |
63f00a3f FB |
134 | |
135 | for ($i = 0 ; $i < $depth ; ++$i) { | |
136 | if ($i == 0) { | |
137 | $this->_its[] = $array; | |
138 | } else { | |
139 | $this->_its[] = current($this->_its[$i - 1]); | |
140 | } | |
141 | reset($this->_its[$i]); | |
142 | } | |
143 | } | |
144 | ||
145 | private function count(array &$array, $depth) | |
146 | { | |
147 | if ($depth == 0) { | |
148 | return count($array); | |
149 | } else { | |
150 | $sum = 0; | |
151 | foreach ($array as &$item) { | |
152 | $sum += $this->count($item, $depth - 1); | |
153 | } | |
154 | return $sum; | |
155 | } | |
156 | } | |
157 | ||
158 | private function nextArray($depth) | |
159 | { | |
160 | if ($depth == 0) { | |
161 | return; | |
162 | } | |
163 | $this->_its[$depth] = next($this->_its[$depth - 1]); | |
164 | if ($this->_its[$depth] === false) { | |
165 | $this->nextArray($depth - 1); | |
166 | if ($this->_its[$depth - 1] === false) { | |
167 | return; | |
168 | } | |
169 | $this->_its[$depth] = current($this->_its[$depth - 1]); | |
170 | } | |
171 | reset($this->_its[$depth]); | |
172 | } | |
173 | ||
174 | public function next() | |
175 | { | |
176 | ++$this->_pos; | |
177 | $this->_first = ($this->_total > 0 && $this->_pos == 1); | |
178 | $this->_last = ($this->_pos == $this->_total); | |
179 | if ($this->_pos > $this->_total) { | |
180 | return null; | |
181 | } | |
182 | ||
183 | $val = current($this->_its[$this->depth - 1]); | |
184 | if ($val === false) { | |
185 | $this->nextArray($this->depth - 1); | |
186 | $val = current($this->_its[$this->depth - 1]); | |
187 | if ($val === false) { | |
188 | return null; | |
189 | } | |
190 | } | |
191 | $keys = array(); | |
192 | for ($i = 0 ; $i < $this->depth ; ++$i) { | |
193 | $keys[] = key($this->_its[$i]); | |
194 | } | |
195 | next($this->_its[$this->depth - 1]); | |
e94c4a17 FB |
196 | if ($this->_flat) { |
197 | return $val; | |
198 | } else { | |
199 | return array('keys' => $keys, | |
200 | 'value' => $val); | |
201 | } | |
63f00a3f FB |
202 | } |
203 | ||
204 | public function total() | |
205 | { | |
206 | return $this->_total; | |
207 | } | |
208 | ||
209 | public function first() | |
210 | { | |
211 | return $this->_first; | |
212 | } | |
213 | ||
214 | public function last() | |
215 | { | |
216 | return $this->_last; | |
217 | } | |
218 | } | |
219 | ||
5177a1b5 FB |
220 | |
221 | /** Iterator that return the result of a merge of several iterators. | |
222 | */ | |
223 | class PlMergeIterator implements PlIterator | |
224 | { | |
225 | /* The heap is field with entries with the form: | |
226 | * array('it' => id of the iterator this entry come from, | |
227 | * 'value' => value of the entry). | |
228 | */ | |
229 | private $heap; | |
230 | private $preComputed = false; | |
231 | private $comparator; | |
232 | private $iterators; | |
233 | private $_total; | |
234 | private $pos; | |
235 | ||
236 | public function __construct(array $iterators, $callback, $sorted = true) | |
237 | { | |
238 | $this->heap = new PlHeap(array($this, 'compare')); | |
239 | $this->_total = 0; | |
240 | $this->comparator = $callback; | |
241 | if ($sorted) { | |
242 | $this->iterators = $iterators; | |
243 | foreach ($this->iterators as $key => &$it) { | |
244 | $this->_total += $it->total(); | |
245 | $item = $it->next(); | |
246 | if (!is_null($item)) { | |
247 | $this->heap->push(array('it' => $key, 'value' => $item)); | |
248 | } | |
249 | } | |
250 | } else { | |
251 | $this->preComputed = true; | |
252 | foreach ($iterators as $key => &$it) { | |
253 | $this->_total += $it->total(); | |
254 | while (!is_null($item = $it->next())) { | |
255 | $this->heap->push(array('it' => $key, 'value' => $item)); | |
256 | } | |
257 | } | |
258 | } | |
259 | $this->pos = 0; | |
260 | } | |
261 | ||
262 | /** Compare two entries of the heap using the comparator of the user. | |
263 | */ | |
264 | public function compare($a, $b) | |
265 | { | |
266 | $cp = call_user_func($this->comparator, $a['value'], $b['value']); | |
267 | if ($cp == 0) { | |
268 | return $a['it'] - $b['it']; | |
269 | } | |
270 | return $cp; | |
271 | } | |
272 | ||
273 | public function total() | |
274 | { | |
275 | return $this->_total; | |
276 | } | |
277 | ||
278 | public function next() | |
279 | { | |
280 | ++$this->pos; | |
281 | $entry = $this->heap->pop(); | |
282 | if (is_null($entry)) { | |
283 | return null; | |
284 | } | |
285 | if ($this->preComputed) { | |
286 | return $entry['value']; | |
287 | } | |
288 | $it = $entry['it']; | |
289 | $item = $this->iterators[$it]->next(); | |
290 | if (!is_null($item)) { | |
291 | $this->heap->push(array('it' => $it, 'value' => $item)); | |
292 | } | |
293 | return $entry['value']; | |
294 | } | |
295 | ||
296 | public function last() | |
297 | { | |
298 | return $this->heap->count() == 0; | |
299 | } | |
300 | ||
301 | public function first() | |
302 | { | |
303 | return $this->pos == 1; | |
304 | } | |
305 | } | |
306 | ||
8d37a362 FB |
307 | |
308 | class PlFilterIterator implements PlIterator { | |
309 | private $source; | |
310 | private $callback; | |
311 | private $element; | |
312 | private $start; | |
313 | ||
314 | public function __construct(PlIterator $source, $callback) | |
315 | { | |
316 | $this->source = $source; | |
317 | $this->callback = $callback; | |
318 | $this->start = true; | |
319 | $this->element = null; | |
320 | } | |
321 | ||
322 | private function fetchNext() | |
323 | { | |
324 | do { | |
325 | $current = $this->source->next(); | |
326 | if (!$current) { | |
327 | $this->element = null; | |
328 | $this->start = false; | |
329 | return; | |
330 | } | |
331 | $res = call_user_func($this->callback, $current); | |
332 | if ($res) { | |
333 | $this->element = $current; | |
334 | return; | |
335 | } | |
336 | } while (true); | |
337 | } | |
338 | ||
339 | public function next() | |
340 | { | |
341 | if ($this->element && $this->start) { | |
342 | $this->start = false; | |
343 | } | |
344 | $elt = $this->element; | |
345 | if ($elt) { | |
346 | $this->fetchNext(); | |
347 | } | |
348 | return $elt; | |
349 | } | |
350 | ||
351 | public function total() | |
352 | { | |
353 | /* This is an approximation since the correct total | |
354 | * cannot be computed without fetching all the elements | |
355 | */ | |
356 | return $this->source->total(); | |
357 | } | |
358 | ||
359 | public function first() | |
360 | { | |
361 | return $this->start; | |
362 | } | |
363 | ||
364 | public function last() | |
365 | { | |
366 | return !$this->start && !$this->element; | |
367 | } | |
368 | } | |
369 | ||
370 | ||
371 | class PlMapIterator implements PlIterator | |
372 | { | |
373 | private $source; | |
374 | private $callback; | |
375 | ||
376 | public function __construct(PlIterator $source, $callback) | |
377 | { | |
378 | $this->source = $source; | |
379 | $this->callback = $callback; | |
380 | } | |
381 | ||
382 | public function next() | |
383 | { | |
384 | $elt = $this->source->next(); | |
385 | if ($elt) { | |
386 | return call_user_func($this->callback, $elt); | |
387 | } else { | |
388 | return null; | |
389 | } | |
390 | } | |
391 | ||
392 | public function total() | |
393 | { | |
394 | return $this->source->total(); | |
395 | } | |
396 | ||
397 | public function first() | |
398 | { | |
399 | return $this->source->first(); | |
400 | } | |
401 | ||
402 | public function last() | |
403 | { | |
404 | return $this->source->last(); | |
405 | } | |
406 | } | |
407 | ||
22c8b530 RB |
408 | class PlSubIterator implements PlIterator |
409 | { | |
410 | private $source; | |
411 | private $callback; | |
412 | private $next = null; // The next item, if it has been fetched too early by a subiterator | |
413 | ||
414 | public function __construct(PlIterator $source, $callback) | |
415 | { | |
416 | $this->source = $source; | |
417 | $this->callback = $callback; | |
418 | } | |
419 | ||
420 | public function next() | |
421 | { | |
422 | if ($this->last()) { | |
423 | return null; | |
424 | } else { | |
425 | return new PlInnerSubIterator($this->source, $this->callback, $this, $this->next); | |
426 | } | |
427 | } | |
428 | ||
429 | /** This will always be a too big number, but the actual result can't be easily computed | |
430 | */ | |
431 | public function total() | |
432 | { | |
433 | return $this->source->total(); | |
434 | } | |
435 | ||
436 | public function last() | |
437 | { | |
438 | return ($this->source->last() && $this->next == null); | |
439 | } | |
440 | ||
9d865d03 FB |
441 | public function first() |
442 | { | |
443 | return $this->source->first(); | |
444 | } | |
445 | ||
22c8b530 RB |
446 | // Called by a subiterator to "rewind" the core iterator |
447 | public function setNext($item) | |
448 | { | |
449 | $this->next = $item; | |
450 | } | |
451 | } | |
452 | ||
453 | class PlInnerSubIterator implements PlIterator | |
454 | { | |
455 | private $source; | |
456 | private $callback; | |
457 | private $parent; | |
458 | ||
459 | private $next; // Not null if the source has to be "rewinded" | |
460 | ||
461 | private $curval = null; | |
462 | private $curelt = null; | |
463 | private $stepped = false; | |
464 | private $over = false; | |
465 | ||
466 | public function __construct(PlIterator $source, $callback, PlSubIterator $parent, $next = null) | |
467 | { | |
468 | $this->source = $source; | |
469 | $this->callback = $callback; | |
470 | $this->parent = $parent; | |
471 | $this->next = $next; | |
472 | } | |
473 | ||
474 | public function value() | |
475 | { | |
476 | $this->_step(); | |
477 | return $this->curval; | |
478 | } | |
479 | ||
480 | // Move one step, if the current element has been used | |
481 | private function _step() | |
482 | { | |
483 | if ($this->stepped) { | |
484 | return; | |
485 | } | |
486 | ||
487 | if ($this->next != null) { | |
488 | $this->curelt = $this->next; | |
489 | $this->next = null; | |
490 | } else { | |
491 | $elt = $this->source->next(); | |
492 | } | |
493 | $this->stepped = true; | |
494 | } | |
495 | ||
496 | public function next() | |
497 | { | |
498 | $this->_step(); | |
499 | $this->stepped = false; | |
500 | ||
501 | if ($this->elt) { | |
502 | $val = call_user_func($this->callback, $this->elt); | |
503 | if ($val == $this->curval) { | |
504 | $this->curval = $val; | |
505 | return $this->elt; | |
506 | } else { | |
507 | $this->parent->setNext($this->elt); | |
508 | } | |
509 | } | |
510 | $this->over = true; | |
511 | return null; | |
512 | } | |
513 | ||
514 | /** This will always be a too big number, but the actual result can't be easily computed | |
515 | */ | |
516 | public function total() | |
517 | { | |
518 | return $this->source->total(); | |
519 | } | |
520 | ||
521 | public function last() | |
522 | { | |
523 | return $this->over; | |
524 | } | |
525 | ||
9d865d03 FB |
526 | public function first() |
527 | { | |
528 | return false; | |
529 | } | |
530 | ||
22c8b530 RB |
531 | } |
532 | ||
533 | // Wrapper class for 'arrayValueCallback' (get field $key of the given array) | |
534 | class _GetArrayValueCallback | |
535 | { | |
536 | private $key; | |
537 | ||
538 | public function __construct($key) | |
539 | { | |
540 | $this->key = $key; | |
541 | } | |
542 | ||
543 | public function get(array $arr) | |
544 | { | |
545 | if (array_key_exists($key, $arr)) { | |
546 | return $arr[$key]; | |
547 | } else { | |
548 | return null; | |
549 | } | |
550 | } | |
551 | } | |
8d37a362 | 552 | |
63f00a3f FB |
553 | // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: |
554 | ?> |