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 /** 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);
31 public static function fromArray(array $array, $depth = 1, $flat = false
)
33 return new PlArrayIterator($array, $depth, $flat);
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.
42 public static function sort(PlIterator
$iterator, $callback)
44 $heap = new PlHeap($callback);
45 while ($item = $iterator->next()) {
48 return $heap->iterator();
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.
58 public static function merge(array $iterators, $callback, $sorted = true
)
60 return new PlMergeIterator($iterators, $callback, $sorted);
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
71 public static function filter(PlIterator
$iterator, $callback)
73 return new PlFilterIterator($iterator, $callback);
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.
83 public static function map(PlIterator
$iterator, $callback)
85 return new PlMapIterator($iterator, $callback);
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.
94 public static function subIterator(PlIterator
$iterator, $callback)
96 return new SubIterator($iterator, $callback);
99 /** Returns the callback for '$x -> $x[$key]';
100 * @param $key the index to retrieve in arrays
103 public static function arrayValueCallback($key)
105 $callback = new _GetArrayValueCallback($key);
106 return array($callback, 'get');
109 /** Returns the callback for '$x -> $x->prop';
110 * @param $property The property to retrieve
113 public static function objectPropertyCallback($property)
115 $callback = new _GetObjectPropertyCallback($property);
116 return array($callback, 'get');
120 /** Iterates over an array.
122 class PlArrayIterator
implements PlIterator
127 private $_its = array();
135 public function __construct(array &$array, $depth = 1, $flat = false
)
137 $this->array =& $array;
138 $this->depth
= $depth;
139 $this->_total
= $this->count($array, $depth - 1);
141 $this->_first
= false
;
142 $this->_last
= false
;
143 $this->_flat
= $flat;
145 for ($i = 0 ; $i < $depth ; ++
$i) {
147 $this->_its
[] = $array;
149 $this->_its
[] = current($this->_its
[$i - 1]);
151 reset($this->_its
[$i]);
155 private function count(array &$array, $depth)
158 return count($array);
161 foreach ($array as &$item) {
162 $sum +
= $this->count($item, $depth - 1);
168 private function nextArray($depth)
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
) {
179 $this->_its
[$depth] = current($this->_its
[$depth - 1]);
181 reset($this->_its
[$depth]);
184 public function next()
187 $this->_first
= ($this->_total
> 0 && $this->_pos
== 1);
188 $this->_last
= ($this->_pos
== $this->_total
);
189 if ($this->_pos
> $this->_total
) {
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
) {
202 for ($i = 0 ; $i < $this->depth
; ++
$i) {
203 $keys[] = key($this->_its
[$i]);
205 next($this->_its
[$this->depth
- 1]);
209 return array('keys' => $keys,
214 public function total()
216 return $this->_total
;
219 public function first()
221 return $this->_first
;
224 public function last()
231 /** Iterator that return the result of a merge of several iterators.
233 class PlMergeIterator
implements PlIterator
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).
240 private $preComputed = false
;
246 public function __construct(array $iterators, $callback, $sorted = true
)
248 $this->heap
= new PlHeap(array($this, 'compare'));
250 $this->comparator
= $callback;
252 $this->iterators
= $iterators;
253 foreach ($this->iterators
as $key => &$it) {
254 $this->_total +
= $it->total();
256 if (!is_null($item)) {
257 $this->heap
->push(array('it' => $key, 'value' => $item));
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));
272 /** Compare two entries of the heap using the comparator of the user.
274 public function compare($a, $b)
276 $cp = call_user_func($this->comparator
, $a['value'], $b['value']);
278 return $a['it'] - $b['it'];
283 public function total()
285 return $this->_total
;
288 public function next()
291 $entry = $this->heap
->pop();
292 if (is_null($entry)) {
295 if ($this->preComputed
) {
296 return $entry['value'];
299 $item = $this->iterators
[$it]->next();
300 if (!is_null($item)) {
301 $this->heap
->push(array('it' => $it, 'value' => $item));
303 return $entry['value'];
306 public function last()
308 return $this->heap
->count() == 0;
311 public function first()
313 return $this->pos
== 1;
318 class PlFilterIterator
implements PlIterator
325 public function __construct(PlIterator
$source, $callback)
327 $this->source
= $source;
328 $this->callback
= $callback;
330 $this->element
= $this->fetchNext();
333 private function fetchNext()
336 $current = $this->source
->next();
337 if (is_null($current) ||
call_user_func($this->callback
, $current)) {
343 public function next()
346 $elt = $this->element
;
347 if (!is_null($this->element
)) {
348 $this->element
= $this->fetchNext();
353 public function total()
355 /* This is an approximation since the correct total
356 * cannot be computed without fetching all the elements
358 return $this->source
->total();
361 public function first()
363 return $this->pos
== 1;
366 public function last()
368 return is_null($this->element
);
373 class PlMapIterator
implements PlIterator
378 public function __construct(PlIterator
$source, $callback)
380 $this->source
= $source;
381 $this->callback
= $callback;
384 public function next()
386 $elt = $this->source
->next();
388 return call_user_func($this->callback
, $elt);
394 public function total()
396 return $this->source
->total();
399 public function first()
401 return $this->source
->first();
404 public function last()
406 return $this->source
->last();
410 class PlSubIterator
implements PlIterator
414 private $next = null
; // The next item, if it has been fetched too early by a subiterator
416 public function __construct(PlIterator
$source, $callback)
418 $this->source
= $source;
419 $this->callback
= $callback;
422 public function next()
427 return new PlInnerSubIterator($this->source
, $this->callback
, $this, $this->next
);
431 /** This will always be a too big number, but the actual result can't be easily computed
433 public function total()
435 return $this->source
->total();
438 public function last()
440 return ($this->source
->last() && $this->next
== null
);
443 public function first()
445 return $this->source
->first();
448 // Called by a subiterator to "rewind" the core iterator
449 public function setNext($item)
455 class PlInnerSubIterator
implements PlIterator
461 private $next; // Not null if the source has to be "rewinded"
463 private $curval = null
;
464 private $curelt = null
;
465 private $stepped = false
;
466 private $over = false
;
468 public function __construct(PlIterator
$source, $callback, PlSubIterator
$parent, $next = null
)
470 $this->source
= $source;
471 $this->callback
= $callback;
472 $this->parent
= $parent;
476 public function value()
479 return $this->curval
;
482 // Move one step, if the current element has been used
483 private function _step()
485 if ($this->stepped
) {
489 if ($this->next
!= null
) {
490 $this->curelt
= $this->next
;
493 $elt = $this->source
->next();
495 $this->stepped
= true
;
498 public function next()
501 $this->stepped
= false
;
504 $val = call_user_func($this->callback
, $this->elt
);
505 if ($val == $this->curval
) {
506 $this->curval
= $val;
509 $this->parent
->setNext($this->elt
);
516 /** This will always be a too big number, but the actual result can't be easily computed
518 public function total()
520 return $this->source
->total();
523 public function last()
528 public function first()
535 // Wrapper class for 'arrayValueCallback' (get field $key of the given array)
536 class _GetArrayValueCallback
540 public function __construct($key)
545 public function get(array $arr)
547 if (array_key_exists($this->key
, $arr)) {
548 return $arr[$this->key
];
555 // Wrapper class for 'objectPropertyCallback' (get property ->$blah of the given object)
556 class _GetObjectPropertyCallback
560 public function __construct($property)
562 $this->property
= $property;
565 public function get($obj)
567 $p = $this->property
;
572 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: