2 /***************************************************************************
3 * Copyright (C) 2003-2009 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);
65 /** Iterates over an array.
67 class PlArrayIterator
implements PlIterator
72 private $_its = array();
80 public function __construct(array &$array, $depth = 1, $flat = false
)
82 $this->array =& $array;
83 $this->depth
= $depth;
84 $this->_total
= $this->count($array, $depth - 1);
86 $this->_first
= false
;
90 for ($i = 0 ; $i < $depth ; ++
$i) {
92 $this->_its
[] = $array;
94 $this->_its
[] = current($this->_its
[$i - 1]);
96 reset($this->_its
[$i]);
100 private function count(array &$array, $depth)
103 return count($array);
106 foreach ($array as &$item) {
107 $sum +
= $this->count($item, $depth - 1);
113 private function nextArray($depth)
118 $this->_its
[$depth] = next($this->_its
[$depth - 1]);
119 if ($this->_its
[$depth] === false
) {
120 $this->nextArray($depth - 1);
121 if ($this->_its
[$depth - 1] === false
) {
124 $this->_its
[$depth] = current($this->_its
[$depth - 1]);
126 reset($this->_its
[$depth]);
129 public function next()
132 $this->_first
= ($this->_total
> 0 && $this->_pos
== 1);
133 $this->_last
= ($this->_pos
== $this->_total
);
134 if ($this->_pos
> $this->_total
) {
138 $val = current($this->_its
[$this->depth
- 1]);
139 if ($val === false
) {
140 $this->nextArray($this->depth
- 1);
141 $val = current($this->_its
[$this->depth
- 1]);
142 if ($val === false
) {
147 for ($i = 0 ; $i < $this->depth
; ++
$i) {
148 $keys[] = key($this->_its
[$i]);
150 next($this->_its
[$this->depth
- 1]);
154 return array('keys' => $keys,
159 public function total()
161 return $this->_total
;
164 public function first()
166 return $this->_first
;
169 public function last()
176 /** Iterator that return the result of a merge of several iterators.
178 class PlMergeIterator
implements PlIterator
180 /* The heap is field with entries with the form:
181 * array('it' => id of the iterator this entry come from,
182 * 'value' => value of the entry).
185 private $preComputed = false
;
191 public function __construct(array $iterators, $callback, $sorted = true
)
193 $this->heap
= new PlHeap(array($this, 'compare'));
195 $this->comparator
= $callback;
197 $this->iterators
= $iterators;
198 foreach ($this->iterators
as $key => &$it) {
199 $this->_total +
= $it->total();
201 if (!is_null($item)) {
202 $this->heap
->push(array('it' => $key, 'value' => $item));
206 $this->preComputed
= true
;
207 foreach ($iterators as $key => &$it) {
208 $this->_total +
= $it->total();
209 while (!is_null($item = $it->next())) {
210 $this->heap
->push(array('it' => $key, 'value' => $item));
217 /** Compare two entries of the heap using the comparator of the user.
219 public function compare($a, $b)
221 $cp = call_user_func($this->comparator
, $a['value'], $b['value']);
223 return $a['it'] - $b['it'];
228 public function total()
230 return $this->_total
;
233 public function next()
236 $entry = $this->heap
->pop();
237 if (is_null($entry)) {
240 if ($this->preComputed
) {
241 return $entry['value'];
244 $item = $this->iterators
[$it]->next();
245 if (!is_null($item)) {
246 $this->heap
->push(array('it' => $it, 'value' => $item));
248 return $entry['value'];
251 public function last()
253 return $this->heap
->count() == 0;
256 public function first()
258 return $this->pos
== 1;
262 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: