2 /***************************************************************************
3 * Copyright (C) 2003-2011 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');
139 /** Returns a wrapper around the PlIterator suitable for foreach() iterations
141 public static function foreachIterator(PlIterator
$iterator)
143 return new SPLIterator($iterator);
149 class PlEmptyIterator
implements PlIterator
151 public function first()
156 public function last()
161 public function next()
166 public function total()
172 /** Iterates over an array.
174 class PlArrayIterator
implements PlIterator
179 private $_its = array();
187 public function __construct(array &$array, $depth = 1, $flat = false
)
189 $this->array =& $array;
190 $this->depth
= $depth;
191 $this->_total
= $this->count($array, $depth - 1);
193 $this->_first
= false
;
194 $this->_last
= false
;
195 $this->_flat
= $flat;
197 for ($i = 0 ; $i < $depth ; ++
$i) {
199 $this->_its
[] = $array;
201 $this->_its
[] = current($this->_its
[$i - 1]);
203 reset($this->_its
[$i]);
207 private function count(array &$array, $depth)
210 return count($array);
213 foreach ($array as &$item) {
214 $sum +
= $this->count($item, $depth - 1);
220 private function nextArray($depth)
225 $this->_its
[$depth] = next($this->_its
[$depth - 1]);
226 if ($this->_its
[$depth] === false
) {
227 $this->nextArray($depth - 1);
228 if ($this->_its
[$depth - 1] === false
) {
231 $this->_its
[$depth] = current($this->_its
[$depth - 1]);
233 reset($this->_its
[$depth]);
236 public function next()
239 $this->_first
= ($this->_total
> 0 && $this->_pos
== 1);
240 $this->_last
= ($this->_pos
== $this->_total
);
241 if ($this->_pos
> $this->_total
) {
245 $val = current($this->_its
[$this->depth
- 1]);
246 if ($val === false
) {
247 $this->nextArray($this->depth
- 1);
248 $val = current($this->_its
[$this->depth
- 1]);
249 if ($val === false
) {
254 for ($i = 0 ; $i < $this->depth
; ++
$i) {
255 $keys[] = key($this->_its
[$i]);
257 next($this->_its
[$this->depth
- 1]);
261 return array('keys' => $keys,
266 public function total()
268 return $this->_total
;
271 public function first()
273 return $this->_first
;
276 public function last()
283 /** Iterator that return the result of a merge of several iterators.
285 class PlMergeIterator
implements PlIterator
287 /* The heap is field with entries with the form:
288 * array('it' => id of the iterator this entry come from,
289 * 'value' => value of the entry).
292 private $preComputed = false
;
298 public function __construct(array $iterators, $callback, $sorted = true
)
300 $this->heap
= new PlHeap(array($this, 'compare'));
302 $this->comparator
= $callback;
304 $this->iterators
= $iterators;
305 foreach ($this->iterators
as $key => &$it) {
306 $this->_total +
= $it->total();
308 if (!is_null($item)) {
309 $this->heap
->push(array('it' => $key, 'value' => $item));
313 $this->preComputed
= true
;
314 foreach ($iterators as $key => &$it) {
315 $this->_total +
= $it->total();
316 while (!is_null($item = $it->next())) {
317 $this->heap
->push(array('it' => $key, 'value' => $item));
324 /** Compare two entries of the heap using the comparator of the user.
326 public function compare($a, $b)
328 $cp = call_user_func($this->comparator
, $a['value'], $b['value']);
330 return $a['it'] - $b['it'];
335 public function total()
337 return $this->_total
;
340 public function next()
343 $entry = $this->heap
->pop();
344 if (is_null($entry)) {
347 if ($this->preComputed
) {
348 return $entry['value'];
351 $item = $this->iterators
[$it]->next();
352 if (!is_null($item)) {
353 $this->heap
->push(array('it' => $it, 'value' => $item));
355 return $entry['value'];
358 public function last()
360 return $this->heap
->count() == 0;
363 public function first()
365 return $this->pos
== 1;
370 class PlFilterIterator
implements PlIterator
377 public function __construct(PlIterator
$source, $callback)
379 $this->source
= $source;
380 $this->callback
= $callback;
382 $this->element
= $this->fetchNext();
385 private function fetchNext()
388 $current = $this->source
->next();
389 if (is_null($current) ||
call_user_func($this->callback
, $current)) {
395 public function next()
398 $elt = $this->element
;
399 if (!is_null($this->element
)) {
400 $this->element
= $this->fetchNext();
405 public function total()
407 /* This is an approximation since the correct total
408 * cannot be computed without fetching all the elements
410 return $this->source
->total();
413 public function first()
415 return $this->pos
== 1;
418 public function last()
420 return is_null($this->element
);
425 class PlMapIterator
implements PlIterator
430 public function __construct(PlIterator
$source, $callback)
432 $this->source
= $source;
433 $this->callback
= $callback;
436 public function next()
438 $elt = $this->source
->next();
440 return call_user_func($this->callback
, $elt);
446 public function total()
448 return $this->source
->total();
451 public function first()
453 return $this->source
->first();
456 public function last()
458 return $this->source
->last();
462 class PlSubIterator
implements PlIterator
466 private $next = null
; // The next item, if it has been fetched too early by a subiterator
470 public function __construct(PlIterator
$source, $callback)
472 $this->source
= $source;
473 $this->callback
= $callback;
476 /** WARNING: this will "fast-forward" the subiterator to its end
478 public function next()
483 if ($this->sub
!= null
) {
484 while (!$this->sub
->last()) {
494 $this->sub
= new PlInnerSubIterator($this->source
, $this->callback
, $this, $this->next
);
499 /** This will always be a too big number, but the actual result can't be easily computed
501 public function total()
503 return $this->source
->total();
506 /** This will only return true if the current subiterator was the last one,
507 * and if it has been fully used
509 public function last()
511 if ($this->sub
!= null
&& !$this->sub
->last()) {
514 return ($this->source
->last() && $this->next
== null
);
517 public function first()
519 return $this->pos
== 1;
522 // Called by a subiterator to "rewind" the core iterator
523 public function setNext($item)
529 class PlInnerSubIterator
implements PlIterator
535 private $next; // Not null if the source has to be "rewinded"
537 private $curval = null
;
538 private $curelt = null
;
541 private $stepped = false
;
542 private $over = false
;
544 public function __construct(PlIterator
$source, $callback, PlSubIterator
$parent, $next = null
)
546 $this->source
= $source;
547 $this->callback
= $callback;
548 $this->parent
= $parent;
550 $this->parent
->setNext(null
);
553 public function value()
556 return $this->curval
;
559 // Move one step, if the current element has been used
560 private function _step()
562 if ($this->stepped
) {
566 if ($this->next
!= null
) {
567 $this->curelt
= $this->next
;
570 if ($this->source
->last()) {
574 $this->curelt
= $this->source
->next();
577 if ($this->pos
== 0) {
578 $this->val
= call_user_func($this->callback
, $this->curelt
);
579 $this->curval
= $this->val
;
581 $this->curval
= call_user_func($this->callback
, $this->curelt
);
584 $this->stepped
= true
;
587 public function next()
600 $this->stepped
= false
;
602 if ($this->val
== $this->curval
) {
603 return $this->curelt
;
606 $this->parent
->setNext($this->curelt
);
611 /** This will always be a too big number, but the actual result can't be easily computed
613 public function total()
615 return $this->source
->total();
618 public function last()
624 return $this->over ||
($this->val
!= $this->curval
);
627 public function first()
629 return $this->pos
== 1;
634 /** Builds an iterator over a set of iterators, from which one is given as 'master';
635 * The arguments are :
636 * - An array of iterators, to iterate simultaneously
637 * - An array of callbacks (one attached to each iterator), or a single callback (to
638 * use for all iterators)
639 * - The id of the 'master' iterator
641 * This ParallelIterator will iterate over the iterators, and, at each
642 * step of the master iterator, it will apply the callbacks to the corresponding
643 * iterators and return the values of the "slaves" for which the callback returned the
644 * same value as the callback of the master.
646 * The callback should compute some kind of index, and never return the same value
647 * twice for a given iterator
649 * It is assumed that, if the callback for a slave doesn't have the same value
650 * as the value for the master, this means that there is a "hole" in the values
654 * - The callback is 'get the first cell'
656 * [0, 1], [1, 13], [2, 42]
657 * - The first slave (slave1) is :
659 * - The second slave (slave2) is :
661 * The resulting iterator would yield :
662 * - array(master => [0, 1], slave1 => [0, 'a'], slave2 => null)
663 * - array(master => [1, 13], slave1 => null, slave2 => [1, 42])
664 * - array(master => [2, 42], slave1 => [1, 'b'], slave2 => [2, 0])
666 class PlParallelIterator
implements PlIterator
675 private $over = array();
676 private $stepped = array();
677 private $current_elts = array();
678 private $callback_res = array();
680 public function __construct(array $iterators, $callbacks, $master)
682 $this->iterators
= $iterators;
683 $this->master_id
= $master;
684 $this->master
= $iterators[$master];
686 $this->ids
= array_keys($iterators);
688 $v = array_values($callbacks);
689 if (is_array($v[0])) {
690 $this->callbacks
= $callbacks;
692 $this->callbacks
= array();
693 foreach ($this->ids
as $id) {
694 $this->callbacks
[$id] = $callbacks;
698 foreach ($this->ids
as $id) {
699 $this->stepped
[$id] = false
;
700 $this->over
[$id] = false
;
701 $this->current_elts
[$id] = null
;
702 $this->callback_res
[$id] = null
;
706 private function step($id)
708 if ($this->stepped
[$id]) {
712 // Don't do anything if the iterator is at its end
713 if ($this->over
[$id]) {
714 $this->stepped
[$id] = true
;
718 $it = $this->iterators
[$id];
720 $this->stepped
[$id] = true
;
722 $this->over
[$id] = true
;
723 $this->current_elts
[$id] = null
;
724 $this->callback_res
[$id] = null
;
727 $res = call_user_func($this->callbacks
[$id], $nxt);
728 $this->current_elts
[$id] = $nxt;
729 $this->callback_res
[$id] = $res;
732 private function stepAll()
734 foreach ($this->ids
as $id) {
739 public function next()
742 if ($this->current_elts
[$this->master_id
] === null
) {
747 $master = $this->callback_res
[$this->master_id
];
748 foreach ($this->ids
as $id) {
749 if ($this->callback_res
[$id] == $master) {
750 $res[$id] = $this->current_elts
[$id];
751 $this->stepped
[$id] = false
;
760 public function first()
762 return $this->master
->first();
765 public function total()
767 return $this->master
->total();
770 public function last()
772 return $this->master
->last();
776 // Wrapper class for 'arrayValueCallback' (get field $key of the given array)
777 class _GetArrayValueCallback
781 public function __construct($key)
786 public function get(array $arr)
788 if (array_key_exists($this->key
, $arr)) {
789 return $arr[$this->key
];
796 // Wrapper class for 'objectPropertyCallback' (get property ->$blah of the given object)
797 class _GetObjectPropertyCallback
801 public function __construct($property)
803 $this->property
= $property;
806 public function get($obj)
808 $p = $this->property
;
813 // Wrapper class to build a SPL iterator from a PlIterator
814 class SPLIterator
implements Iterator
820 public function __construct(PlIterator
$it)
824 $this->value
= $this->it
->next();
827 public function rewind()
829 if ($this->pos
!= 0) {
830 throw new Exception("Rewind not supported on this iterator");
834 public function current()
839 public function key()
844 public function next()
847 $this->value
= $this->it
->next();
850 public function valid()
852 return !!$this->value
;
856 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker fenc=utf-8: