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 | } | |
ce06a3ea RB |
108 | |
109 | /** Returns the callback for '$x -> $x->prop'; | |
110 | * @param $property The property to retrieve | |
111 | * @return a callback | |
112 | */ | |
d40e45a2 | 113 | public static function objectPropertyCallback($property) |
ce06a3ea RB |
114 | { |
115 | $callback = new _GetObjectPropertyCallback($property); | |
116 | return array($callback, 'get'); | |
117 | } | |
22c8b530 | 118 | } |
5177a1b5 FB |
119 | |
120 | /** Iterates over an array. | |
121 | */ | |
63f00a3f FB |
122 | class PlArrayIterator implements PlIterator |
123 | { | |
124 | private $array; | |
125 | private $depth; | |
126 | ||
127 | private $_its = array(); | |
128 | ||
129 | private $_total; | |
130 | private $_first; | |
131 | private $_last; | |
132 | private $_pos; | |
e94c4a17 | 133 | private $_flat; |
63f00a3f | 134 | |
e94c4a17 | 135 | public function __construct(array &$array, $depth = 1, $flat = false) |
63f00a3f FB |
136 | { |
137 | $this->array =& $array; | |
138 | $this->depth = $depth; | |
139 | $this->_total = $this->count($array, $depth - 1); | |
140 | $this->_pos = 0; | |
141 | $this->_first = false; | |
142 | $this->_last = false; | |
e94c4a17 | 143 | $this->_flat = $flat; |
63f00a3f FB |
144 | |
145 | for ($i = 0 ; $i < $depth ; ++$i) { | |
146 | if ($i == 0) { | |
147 | $this->_its[] = $array; | |
148 | } else { | |
149 | $this->_its[] = current($this->_its[$i - 1]); | |
150 | } | |
151 | reset($this->_its[$i]); | |
152 | } | |
153 | } | |
154 | ||
155 | private function count(array &$array, $depth) | |
156 | { | |
157 | if ($depth == 0) { | |
158 | return count($array); | |
159 | } else { | |
160 | $sum = 0; | |
161 | foreach ($array as &$item) { | |
162 | $sum += $this->count($item, $depth - 1); | |
163 | } | |
164 | return $sum; | |
165 | } | |
166 | } | |
167 | ||
168 | private function nextArray($depth) | |
169 | { | |
170 | if ($depth == 0) { | |
171 | return; | |
172 | } | |
173 | $this->_its[$depth] = next($this->_its[$depth - 1]); | |
174 | if ($this->_its[$depth] === false) { | |
175 | $this->nextArray($depth - 1); | |
176 | if ($this->_its[$depth - 1] === false) { | |
177 | return; | |
178 | } | |
179 | $this->_its[$depth] = current($this->_its[$depth - 1]); | |
180 | } | |
181 | reset($this->_its[$depth]); | |
182 | } | |
183 | ||
184 | public function next() | |
185 | { | |
186 | ++$this->_pos; | |
187 | $this->_first = ($this->_total > 0 && $this->_pos == 1); | |
188 | $this->_last = ($this->_pos == $this->_total); | |
189 | if ($this->_pos > $this->_total) { | |
190 | return null; | |
191 | } | |
192 | ||
193 | $val = current($this->_its[$this->depth - 1]); | |
194 | if ($val === false) { | |
195 | $this->nextArray($this->depth - 1); | |
196 | $val = current($this->_its[$this->depth - 1]); | |
197 | if ($val === false) { | |
198 | return null; | |
199 | } | |
200 | } | |
201 | $keys = array(); | |
202 | for ($i = 0 ; $i < $this->depth ; ++$i) { | |
203 | $keys[] = key($this->_its[$i]); | |
204 | } | |
205 | next($this->_its[$this->depth - 1]); | |
e94c4a17 FB |
206 | if ($this->_flat) { |
207 | return $val; | |
208 | } else { | |
209 | return array('keys' => $keys, | |
210 | 'value' => $val); | |
211 | } | |
63f00a3f FB |
212 | } |
213 | ||
214 | public function total() | |
215 | { | |
216 | return $this->_total; | |
217 | } | |
218 | ||
219 | public function first() | |
220 | { | |
221 | return $this->_first; | |
222 | } | |
223 | ||
224 | public function last() | |
225 | { | |
226 | return $this->_last; | |
227 | } | |
228 | } | |
229 | ||
5177a1b5 FB |
230 | |
231 | /** Iterator that return the result of a merge of several iterators. | |
232 | */ | |
233 | class PlMergeIterator implements PlIterator | |
234 | { | |
235 | /* The heap is field with entries with the form: | |
236 | * array('it' => id of the iterator this entry come from, | |
237 | * 'value' => value of the entry). | |
238 | */ | |
239 | private $heap; | |
240 | private $preComputed = false; | |
241 | private $comparator; | |
242 | private $iterators; | |
243 | private $_total; | |
244 | private $pos; | |
245 | ||
246 | public function __construct(array $iterators, $callback, $sorted = true) | |
247 | { | |
248 | $this->heap = new PlHeap(array($this, 'compare')); | |
249 | $this->_total = 0; | |
250 | $this->comparator = $callback; | |
251 | if ($sorted) { | |
252 | $this->iterators = $iterators; | |
253 | foreach ($this->iterators as $key => &$it) { | |
254 | $this->_total += $it->total(); | |
255 | $item = $it->next(); | |
256 | if (!is_null($item)) { | |
257 | $this->heap->push(array('it' => $key, 'value' => $item)); | |
258 | } | |
259 | } | |
260 | } else { | |
261 | $this->preComputed = true; | |
262 | foreach ($iterators as $key => &$it) { | |
263 | $this->_total += $it->total(); | |
264 | while (!is_null($item = $it->next())) { | |
265 | $this->heap->push(array('it' => $key, 'value' => $item)); | |
266 | } | |
267 | } | |
268 | } | |
269 | $this->pos = 0; | |
270 | } | |
271 | ||
272 | /** Compare two entries of the heap using the comparator of the user. | |
273 | */ | |
274 | public function compare($a, $b) | |
275 | { | |
276 | $cp = call_user_func($this->comparator, $a['value'], $b['value']); | |
277 | if ($cp == 0) { | |
278 | return $a['it'] - $b['it']; | |
279 | } | |
280 | return $cp; | |
281 | } | |
282 | ||
283 | public function total() | |
284 | { | |
285 | return $this->_total; | |
286 | } | |
287 | ||
288 | public function next() | |
289 | { | |
290 | ++$this->pos; | |
291 | $entry = $this->heap->pop(); | |
292 | if (is_null($entry)) { | |
293 | return null; | |
294 | } | |
295 | if ($this->preComputed) { | |
296 | return $entry['value']; | |
297 | } | |
298 | $it = $entry['it']; | |
299 | $item = $this->iterators[$it]->next(); | |
300 | if (!is_null($item)) { | |
301 | $this->heap->push(array('it' => $it, 'value' => $item)); | |
302 | } | |
303 | return $entry['value']; | |
304 | } | |
305 | ||
306 | public function last() | |
307 | { | |
308 | return $this->heap->count() == 0; | |
309 | } | |
310 | ||
311 | public function first() | |
312 | { | |
313 | return $this->pos == 1; | |
314 | } | |
315 | } | |
316 | ||
8d37a362 FB |
317 | |
318 | class PlFilterIterator implements PlIterator { | |
319 | private $source; | |
320 | private $callback; | |
321 | private $element; | |
322 | private $start; | |
323 | ||
324 | public function __construct(PlIterator $source, $callback) | |
325 | { | |
326 | $this->source = $source; | |
327 | $this->callback = $callback; | |
328 | $this->start = true; | |
329 | $this->element = null; | |
330 | } | |
331 | ||
332 | private function fetchNext() | |
333 | { | |
334 | do { | |
335 | $current = $this->source->next(); | |
336 | if (!$current) { | |
337 | $this->element = null; | |
338 | $this->start = false; | |
339 | return; | |
340 | } | |
341 | $res = call_user_func($this->callback, $current); | |
342 | if ($res) { | |
343 | $this->element = $current; | |
344 | return; | |
345 | } | |
346 | } while (true); | |
347 | } | |
348 | ||
349 | public function next() | |
350 | { | |
351 | if ($this->element && $this->start) { | |
352 | $this->start = false; | |
353 | } | |
354 | $elt = $this->element; | |
355 | if ($elt) { | |
356 | $this->fetchNext(); | |
357 | } | |
358 | return $elt; | |
359 | } | |
360 | ||
361 | public function total() | |
362 | { | |
363 | /* This is an approximation since the correct total | |
364 | * cannot be computed without fetching all the elements | |
365 | */ | |
366 | return $this->source->total(); | |
367 | } | |
368 | ||
369 | public function first() | |
370 | { | |
371 | return $this->start; | |
372 | } | |
373 | ||
374 | public function last() | |
375 | { | |
376 | return !$this->start && !$this->element; | |
377 | } | |
378 | } | |
379 | ||
380 | ||
381 | class PlMapIterator implements PlIterator | |
382 | { | |
383 | private $source; | |
384 | private $callback; | |
385 | ||
386 | public function __construct(PlIterator $source, $callback) | |
387 | { | |
388 | $this->source = $source; | |
389 | $this->callback = $callback; | |
390 | } | |
391 | ||
392 | public function next() | |
393 | { | |
394 | $elt = $this->source->next(); | |
395 | if ($elt) { | |
396 | return call_user_func($this->callback, $elt); | |
397 | } else { | |
398 | return null; | |
399 | } | |
400 | } | |
401 | ||
402 | public function total() | |
403 | { | |
404 | return $this->source->total(); | |
405 | } | |
406 | ||
407 | public function first() | |
408 | { | |
409 | return $this->source->first(); | |
410 | } | |
411 | ||
412 | public function last() | |
413 | { | |
414 | return $this->source->last(); | |
415 | } | |
416 | } | |
417 | ||
22c8b530 RB |
418 | class PlSubIterator implements PlIterator |
419 | { | |
420 | private $source; | |
421 | private $callback; | |
422 | private $next = null; // The next item, if it has been fetched too early by a subiterator | |
423 | ||
424 | public function __construct(PlIterator $source, $callback) | |
425 | { | |
426 | $this->source = $source; | |
427 | $this->callback = $callback; | |
428 | } | |
429 | ||
430 | public function next() | |
431 | { | |
432 | if ($this->last()) { | |
433 | return null; | |
434 | } else { | |
435 | return new PlInnerSubIterator($this->source, $this->callback, $this, $this->next); | |
436 | } | |
437 | } | |
438 | ||
439 | /** This will always be a too big number, but the actual result can't be easily computed | |
440 | */ | |
441 | public function total() | |
442 | { | |
443 | return $this->source->total(); | |
444 | } | |
445 | ||
446 | public function last() | |
447 | { | |
448 | return ($this->source->last() && $this->next == null); | |
449 | } | |
450 | ||
9d865d03 FB |
451 | public function first() |
452 | { | |
453 | return $this->source->first(); | |
454 | } | |
455 | ||
22c8b530 RB |
456 | // Called by a subiterator to "rewind" the core iterator |
457 | public function setNext($item) | |
458 | { | |
459 | $this->next = $item; | |
460 | } | |
461 | } | |
462 | ||
463 | class PlInnerSubIterator implements PlIterator | |
464 | { | |
465 | private $source; | |
466 | private $callback; | |
467 | private $parent; | |
468 | ||
469 | private $next; // Not null if the source has to be "rewinded" | |
470 | ||
471 | private $curval = null; | |
472 | private $curelt = null; | |
473 | private $stepped = false; | |
474 | private $over = false; | |
475 | ||
476 | public function __construct(PlIterator $source, $callback, PlSubIterator $parent, $next = null) | |
477 | { | |
478 | $this->source = $source; | |
479 | $this->callback = $callback; | |
480 | $this->parent = $parent; | |
481 | $this->next = $next; | |
482 | } | |
483 | ||
484 | public function value() | |
485 | { | |
486 | $this->_step(); | |
487 | return $this->curval; | |
488 | } | |
489 | ||
490 | // Move one step, if the current element has been used | |
491 | private function _step() | |
492 | { | |
493 | if ($this->stepped) { | |
494 | return; | |
495 | } | |
496 | ||
497 | if ($this->next != null) { | |
498 | $this->curelt = $this->next; | |
499 | $this->next = null; | |
500 | } else { | |
501 | $elt = $this->source->next(); | |
502 | } | |
503 | $this->stepped = true; | |
504 | } | |
505 | ||
506 | public function next() | |
507 | { | |
508 | $this->_step(); | |
509 | $this->stepped = false; | |
510 | ||
511 | if ($this->elt) { | |
512 | $val = call_user_func($this->callback, $this->elt); | |
513 | if ($val == $this->curval) { | |
514 | $this->curval = $val; | |
515 | return $this->elt; | |
516 | } else { | |
517 | $this->parent->setNext($this->elt); | |
518 | } | |
519 | } | |
520 | $this->over = true; | |
521 | return null; | |
522 | } | |
523 | ||
524 | /** This will always be a too big number, but the actual result can't be easily computed | |
525 | */ | |
526 | public function total() | |
527 | { | |
528 | return $this->source->total(); | |
529 | } | |
530 | ||
531 | public function last() | |
532 | { | |
533 | return $this->over; | |
534 | } | |
535 | ||
9d865d03 FB |
536 | public function first() |
537 | { | |
538 | return false; | |
539 | } | |
540 | ||
22c8b530 RB |
541 | } |
542 | ||
543 | // Wrapper class for 'arrayValueCallback' (get field $key of the given array) | |
544 | class _GetArrayValueCallback | |
545 | { | |
546 | private $key; | |
547 | ||
548 | public function __construct($key) | |
549 | { | |
550 | $this->key = $key; | |
551 | } | |
552 | ||
553 | public function get(array $arr) | |
554 | { | |
381a28e9 RB |
555 | if (array_key_exists($this->key, $arr)) { |
556 | return $arr[$this->key]; | |
22c8b530 RB |
557 | } else { |
558 | return null; | |
559 | } | |
560 | } | |
561 | } | |
8d37a362 | 562 | |
ce06a3ea RB |
563 | // Wrapper class for 'objectPropertyCallback' (get property ->$blah of the given object) |
564 | class _GetObjectPropertyCallback | |
565 | { | |
566 | private $property; | |
567 | ||
568 | public function __construct($property) | |
569 | { | |
570 | $this->property = $property; | |
571 | } | |
572 | ||
573 | public function get($obj) | |
574 | { | |
575 | $p = $this->property; | |
576 | return @$obj->$p; | |
577 | } | |
578 | } | |
579 | ||
63f00a3f FB |
580 | // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: |
581 | ?> |