2 /***************************************************************************
3 * Copyright (C) 2003-2010 Polytechnique.org *
4 * http://opensource.polytechnique.org/ *
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. *
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. *
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 *
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
20 ***************************************************************************/
24 /** Builds a new empty iterator
26 public static function emptyIterator()
28 return new PlEmptyIterator();
31 /** Build an iterator over an array.
32 * @param array The array.
33 * @param depth The depth of iteration.
34 * @return an iterator that return entries in the form
35 * array(key => array(0 => key_for_depth0 [, 1 => key_for_depths1, ...]),
36 * value => the value);
38 public static function fromArray(array $array, $depth = 1, $flat = false
)
40 return new PlArrayIterator($array, $depth, $flat);
44 /** Sort an iterator using the given sort callback.
45 * @param iterator The iterator to sort.
46 * @param callback The callback for comparison.
47 * @return a new iterator with the entries sorted.
49 public static function sort(PlIterator
$iterator, $callback)
51 $heap = new PlHeap($callback);
52 while ($item = $iterator->next()) {
55 return $heap->iterator();
59 /** Merge several iterator into a unique one.
60 * @param iterators Array of iterators.
61 * @param callback The callback for comparison.
62 * @param sorted Tell wether the iterators are already sorted using the given callback.
63 * @return an iterator.
65 public static function merge(array $iterators, $callback, $sorted = true
)
67 return new PlMergeIterator($iterators, $callback, $sorted);
71 /** Build an iterator that contains only the elements of the given iterator that
72 * match the given condition. The condition should be a callback that takes an element
73 * and returns a boolean.
74 * @param iterator The source iterator
75 * @param callback The condition
78 public static function filter(PlIterator
$iterator, $callback)
80 return new PlFilterIterator($iterator, $callback);
84 /** Build an iterator that transforms the element of another iterator. The callback
85 * takes an element and transform it into another one. Be careful: if the result
86 * of the callback is null, the iteration ends.
87 * @param iterator The source iterator
88 * @param callback The transformer.
90 public static function map(PlIterator
$iterator, $callback)
92 return new PlMapIterator($iterator, $callback);
95 /** Build an iterator whose values are iterators too; such a 'subIterator' will end
96 * when the value of $callback changes;
97 * WARNING: will fast-forward the current subiterator until it is over !
98 * @param iterator The source iterator
99 * @param callback The callback for detecting changes. XXX: Might be called twice on a given object
100 * @return an iterator
102 public static function subIterator(PlIterator
$iterator, $callback)
104 return new PlSubIterator($iterator, $callback);
107 /** Build an iterator that will iterate over the given set of iterators, returning consistent
108 * sets of values (i.e only the values for which the result of the callback is the same as that
110 * @param iterators The set of iterators
111 * @param callbacks A list of callbacks (one for each iterator), or a single, common, callback
112 * @param master The id of the "master" iterator in the first list
114 public static function parallelIterator(array $iterators, $callbacks, $master)
116 return new PlParallelIterator($iterators, $callbacks, $master);
119 /** Returns the callback for '$x -> $x[$key]';
120 * @param $key the index to retrieve in arrays
123 public static function arrayValueCallback($key)
125 $callback = new _GetArrayValueCallback($key);
126 return array($callback, 'get');
129 /** Returns the callback for '$x -> $x->prop';
130 * @param $property The property to retrieve
133 public static function objectPropertyCallback($property)
135 $callback = new _GetObjectPropertyCallback($property);
136 return array($callback, 'get');
142 class PlEmptyIterator
implements PlIterator
144 public function first()
149 public function last()
154 public function next()
159 public function total()
165 /** Iterates over an array.
167 class PlArrayIterator
implements PlIterator
172 private $_its = array();
180 public function __construct(array &$array, $depth = 1, $flat = false
)
182 $this->array =& $array;
183 $this->depth
= $depth;
184 $this->_total
= $this->count($array, $depth - 1);
186 $this->_first
= false
;
187 $this->_last
= false
;
188 $this->_flat
= $flat;
190 for ($i = 0 ; $i < $depth ; ++
$i) {
192 $this->_its
[] = $array;
194 $this->_its
[] = current($this->_its
[$i - 1]);
196 reset($this->_its
[$i]);
200 private function count(array &$array, $depth)
203 return count($array);
206 foreach ($array as &$item) {
207 $sum +
= $this->count($item, $depth - 1);
213 private function nextArray($depth)
218 $this->_its
[$depth] = next($this->_its
[$depth - 1]);
219 if ($this->_its
[$depth] === false
) {
220 $this->nextArray($depth - 1);
221 if ($this->_its
[$depth - 1] === false
) {
224 $this->_its
[$depth] = current($this->_its
[$depth - 1]);
226 reset($this->_its
[$depth]);
229 public function next()
232 $this->_first
= ($this->_total
> 0 && $this->_pos
== 1);
233 $this->_last
= ($this->_pos
== $this->_total
);
234 if ($this->_pos
> $this->_total
) {
238 $val = current($this->_its
[$this->depth
- 1]);
239 if ($val === false
) {
240 $this->nextArray($this->depth
- 1);
241 $val = current($this->_its
[$this->depth
- 1]);
242 if ($val === false
) {
247 for ($i = 0 ; $i < $this->depth
; ++
$i) {
248 $keys[] = key($this->_its
[$i]);
250 next($this->_its
[$this->depth
- 1]);
254 return array('keys' => $keys,
259 public function total()
261 return $this->_total
;
264 public function first()
266 return $this->_first
;
269 public function last()
276 /** Iterator that return the result of a merge of several iterators.
278 class PlMergeIterator
implements PlIterator
280 /* The heap is field with entries with the form:
281 * array('it' => id of the iterator this entry come from,
282 * 'value' => value of the entry).
285 private $preComputed = false
;
291 public function __construct(array $iterators, $callback, $sorted = true
)
293 $this->heap
= new PlHeap(array($this, 'compare'));
295 $this->comparator
= $callback;
297 $this->iterators
= $iterators;
298 foreach ($this->iterators
as $key => &$it) {
299 $this->_total +
= $it->total();
301 if (!is_null($item)) {
302 $this->heap
->push(array('it' => $key, 'value' => $item));
306 $this->preComputed
= true
;
307 foreach ($iterators as $key => &$it) {
308 $this->_total +
= $it->total();
309 while (!is_null($item = $it->next())) {
310 $this->heap
->push(array('it' => $key, 'value' => $item));
317 /** Compare two entries of the heap using the comparator of the user.
319 public function compare($a, $b)
321 $cp = call_user_func($this->comparator
, $a['value'], $b['value']);
323 return $a['it'] - $b['it'];
328 public function total()
330 return $this->_total
;
333 public function next()
336 $entry = $this->heap
->pop();
337 if (is_null($entry)) {
340 if ($this->preComputed
) {
341 return $entry['value'];
344 $item = $this->iterators
[$it]->next();
345 if (!is_null($item)) {
346 $this->heap
->push(array('it' => $it, 'value' => $item));
348 return $entry['value'];
351 public function last()
353 return $this->heap
->count() == 0;
356 public function first()
358 return $this->pos
== 1;
363 class PlFilterIterator
implements PlIterator
370 public function __construct(PlIterator
$source, $callback)
372 $this->source
= $source;
373 $this->callback
= $callback;
375 $this->element
= $this->fetchNext();
378 private function fetchNext()
381 $current = $this->source
->next();
382 if (is_null($current) ||
call_user_func($this->callback
, $current)) {
388 public function next()
391 $elt = $this->element
;
392 if (!is_null($this->element
)) {
393 $this->element
= $this->fetchNext();
398 public function total()
400 /* This is an approximation since the correct total
401 * cannot be computed without fetching all the elements
403 return $this->source
->total();
406 public function first()
408 return $this->pos
== 1;
411 public function last()
413 return is_null($this->element
);
418 class PlMapIterator
implements PlIterator
423 public function __construct(PlIterator
$source, $callback)
425 $this->source
= $source;
426 $this->callback
= $callback;
429 public function next()
431 $elt = $this->source
->next();
433 return call_user_func($this->callback
, $elt);
439 public function total()
441 return $this->source
->total();
444 public function first()
446 return $this->source
->first();
449 public function last()
451 return $this->source
->last();
455 class PlSubIterator
implements PlIterator
459 private $next = null
; // The next item, if it has been fetched too early by a subiterator
463 public function __construct(PlIterator
$source, $callback)
465 $this->source
= $source;
466 $this->callback
= $callback;
469 /** WARNING: this will "fast-forward" the subiterator to its end
471 public function next()
476 if ($this->sub
!= null
) {
477 while (!$this->sub
->last()) {
487 $this->sub
= new PlInnerSubIterator($this->source
, $this->callback
, $this, $this->next
);
492 /** This will always be a too big number, but the actual result can't be easily computed
494 public function total()
496 return $this->source
->total();
499 /** This will only return true if the current subiterator was the last one,
500 * and if it has been fully used
502 public function last()
504 if ($this->sub
!= null
&& !$this->sub
->last()) {
507 return ($this->source
->last() && $this->next
== null
);
510 public function first()
512 return $this->pos
== 1;
515 // Called by a subiterator to "rewind" the core iterator
516 public function setNext($item)
522 class PlInnerSubIterator
implements PlIterator
528 private $next; // Not null if the source has to be "rewinded"
530 private $curval = null
;
531 private $curelt = null
;
534 private $stepped = false
;
535 private $over = false
;
537 public function __construct(PlIterator
$source, $callback, PlSubIterator
$parent, $next = null
)
539 $this->source
= $source;
540 $this->callback
= $callback;
541 $this->parent
= $parent;
543 $this->parent
->setNext(null
);
546 public function value()
549 return $this->curval
;
552 // Move one step, if the current element has been used
553 private function _step()
555 if ($this->stepped
) {
559 if ($this->next
!= null
) {
560 $this->curelt
= $this->next
;
563 if ($this->source
->last()) {
567 $this->curelt
= $this->source
->next();
570 if ($this->pos
== 0) {
571 $this->val
= call_user_func($this->callback
, $this->curelt
);
572 $this->curval
= $this->val
;
574 $this->curval
= call_user_func($this->callback
, $this->curelt
);
577 $this->stepped
= true
;
580 public function next()
593 $this->stepped
= false
;
595 if ($this->val
== $this->curval
) {
596 return $this->curelt
;
599 $this->parent
->setNext($this->curelt
);
604 /** This will always be a too big number, but the actual result can't be easily computed
606 public function total()
608 return $this->source
->total();
611 public function last()
617 return $this->over ||
($this->val
!= $this->curval
);
620 public function first()
622 return $this->pos
== 1;
627 /** Builds an iterator over a set of iterators, from which one is given as 'master';
628 * The arguments are :
629 * - An array of iterators, to iterate simultaneously
630 * - An array of callbacks (one attached to each iterator), or a single callback (to
631 * use for all iterators)
632 * - The id of the 'master' iterator
634 * This ParallelIterator will iterate over the iterators, and, at each
635 * step of the master iterator, it will apply the callbacks to the corresponding
636 * iterators and return the values of the "slaves" for which the callback returned the
637 * same value as the callback of the master.
639 * The callback should compute some kind of index, and never return the same value
640 * twice for a given iterator
642 * It is assumed that, if the callback for a slave doesn't have the same value
643 * as the value for the master, this means that there is a "hole" in the values
647 * - The callback is 'get the first cell'
649 * [0, 1], [1, 13], [2, 42]
650 * - The first slave (slave1) is :
652 * - The second slave (slave2) is :
654 * The resulting iterator would yield :
655 * - array(master => [0, 1], slave1 => [0, 'a'], slave2 => null)
656 * - array(master => [1, 13], slave1 => null, slave2 => [1, 42])
657 * - array(master => [2, 42], slave1 => [1, 'b'], slave2 => [2, 0])
659 class PlParallelIterator
implements PlIterator
668 private $over = array();
669 private $stepped = array();
670 private $current_elts = array();
671 private $callback_res = array();
673 public function __construct(array $iterators, $callbacks, $master)
675 $this->iterators
= $iterators;
676 $this->master_id
= $master;
677 $this->master
= $iterators[$master];
679 $this->ids
= array_keys($iterators);
681 $v = array_values($callbacks);
682 if (is_array($v[0])) {
683 $this->callbacks
= $callbacks;
685 $this->callbacks
= array();
686 foreach ($this->ids
as $id) {
687 $this->callbacks
[$id] = $callbacks;
691 foreach ($this->ids
as $id) {
692 $this->stepped
[$id] = false
;
693 $this->over
[$id] = false
;
694 $this->current_elts
[$id] = null
;
695 $this->callback_res
[$id] = null
;
699 private function step($id)
701 if ($this->stepped
[$id]) {
705 // Don't do anything if the iterator is at its end
706 if ($this->over
[$id]) {
707 $this->stepped
[$id] = true
;
711 $it = $this->iterators
[$id];
713 $this->stepped
[$id] = true
;
715 $this->over
[$id] = true
;
716 $this->current_elts
[$id] = null
;
717 $this->callback_res
[$id] = null
;
720 $res = call_user_func($this->callbacks
[$id], $nxt);
721 $this->current_elts
[$id] = $nxt;
722 $this->callback_res
[$id] = $res;
725 private function stepAll()
727 foreach ($this->ids
as $id) {
732 public function next()
735 if ($this->current_elts
[$this->master_id
] === null
) {
740 $master = $this->callback_res
[$this->master_id
];
741 foreach ($this->ids
as $id) {
742 if ($this->callback_res
[$id] == $master) {
743 $res[$id] = $this->current_elts
[$id];
744 $this->stepped
[$id] = false
;
753 public function first()
755 return $this->master
->first();
758 public function total()
760 return $this->master
->total();
763 public function last()
765 return $this->master
->last();
769 // Wrapper class for 'arrayValueCallback' (get field $key of the given array)
770 class _GetArrayValueCallback
774 public function __construct($key)
779 public function get(array $arr)
781 if (array_key_exists($this->key
, $arr)) {
782 return $arr[$this->key
];
789 // Wrapper class for 'objectPropertyCallback' (get property ->$blah of the given object)
790 class _GetObjectPropertyCallback
794 public function __construct($property)
796 $this->property
= $property;
799 public function get($obj)
801 $p = $this->property
;
806 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: