| 1 | <?php |
| 2 | /*************************************************************************** |
| 3 | * Copyright (C) 2003-2009 Polytechnique.org * |
| 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 | |
| 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 | */ |
| 31 | public static function fromArray(array $array, $depth = 1, $flat = false) |
| 32 | { |
| 33 | return new PlArrayIterator($array, $depth, $flat); |
| 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 | } |
| 62 | } |
| 63 | |
| 64 | |
| 65 | /** Iterates over an array. |
| 66 | */ |
| 67 | class PlArrayIterator implements PlIterator |
| 68 | { |
| 69 | private $array; |
| 70 | private $depth; |
| 71 | |
| 72 | private $_its = array(); |
| 73 | |
| 74 | private $_total; |
| 75 | private $_first; |
| 76 | private $_last; |
| 77 | private $_pos; |
| 78 | private $_flat; |
| 79 | |
| 80 | public function __construct(array &$array, $depth = 1, $flat = false) |
| 81 | { |
| 82 | $this->array =& $array; |
| 83 | $this->depth = $depth; |
| 84 | $this->_total = $this->count($array, $depth - 1); |
| 85 | $this->_pos = 0; |
| 86 | $this->_first = false; |
| 87 | $this->_last = false; |
| 88 | $this->_flat = $flat; |
| 89 | |
| 90 | for ($i = 0 ; $i < $depth ; ++$i) { |
| 91 | if ($i == 0) { |
| 92 | $this->_its[] = $array; |
| 93 | } else { |
| 94 | $this->_its[] = current($this->_its[$i - 1]); |
| 95 | } |
| 96 | reset($this->_its[$i]); |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | private function count(array &$array, $depth) |
| 101 | { |
| 102 | if ($depth == 0) { |
| 103 | return count($array); |
| 104 | } else { |
| 105 | $sum = 0; |
| 106 | foreach ($array as &$item) { |
| 107 | $sum += $this->count($item, $depth - 1); |
| 108 | } |
| 109 | return $sum; |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | private function nextArray($depth) |
| 114 | { |
| 115 | if ($depth == 0) { |
| 116 | return; |
| 117 | } |
| 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) { |
| 122 | return; |
| 123 | } |
| 124 | $this->_its[$depth] = current($this->_its[$depth - 1]); |
| 125 | } |
| 126 | reset($this->_its[$depth]); |
| 127 | } |
| 128 | |
| 129 | public function next() |
| 130 | { |
| 131 | ++$this->_pos; |
| 132 | $this->_first = ($this->_total > 0 && $this->_pos == 1); |
| 133 | $this->_last = ($this->_pos == $this->_total); |
| 134 | if ($this->_pos > $this->_total) { |
| 135 | return null; |
| 136 | } |
| 137 | |
| 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) { |
| 143 | return null; |
| 144 | } |
| 145 | } |
| 146 | $keys = array(); |
| 147 | for ($i = 0 ; $i < $this->depth ; ++$i) { |
| 148 | $keys[] = key($this->_its[$i]); |
| 149 | } |
| 150 | next($this->_its[$this->depth - 1]); |
| 151 | if ($this->_flat) { |
| 152 | return $val; |
| 153 | } else { |
| 154 | return array('keys' => $keys, |
| 155 | 'value' => $val); |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | public function total() |
| 160 | { |
| 161 | return $this->_total; |
| 162 | } |
| 163 | |
| 164 | public function first() |
| 165 | { |
| 166 | return $this->_first; |
| 167 | } |
| 168 | |
| 169 | public function last() |
| 170 | { |
| 171 | return $this->_last; |
| 172 | } |
| 173 | } |
| 174 | |
| 175 | |
| 176 | /** Iterator that return the result of a merge of several iterators. |
| 177 | */ |
| 178 | class PlMergeIterator implements PlIterator |
| 179 | { |
| 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). |
| 183 | */ |
| 184 | private $heap; |
| 185 | private $preComputed = false; |
| 186 | private $comparator; |
| 187 | private $iterators; |
| 188 | private $_total; |
| 189 | private $pos; |
| 190 | |
| 191 | public function __construct(array $iterators, $callback, $sorted = true) |
| 192 | { |
| 193 | $this->heap = new PlHeap(array($this, 'compare')); |
| 194 | $this->_total = 0; |
| 195 | $this->comparator = $callback; |
| 196 | if ($sorted) { |
| 197 | $this->iterators = $iterators; |
| 198 | foreach ($this->iterators as $key => &$it) { |
| 199 | $this->_total += $it->total(); |
| 200 | $item = $it->next(); |
| 201 | if (!is_null($item)) { |
| 202 | $this->heap->push(array('it' => $key, 'value' => $item)); |
| 203 | } |
| 204 | } |
| 205 | } else { |
| 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)); |
| 211 | } |
| 212 | } |
| 213 | } |
| 214 | $this->pos = 0; |
| 215 | } |
| 216 | |
| 217 | /** Compare two entries of the heap using the comparator of the user. |
| 218 | */ |
| 219 | public function compare($a, $b) |
| 220 | { |
| 221 | $cp = call_user_func($this->comparator, $a['value'], $b['value']); |
| 222 | if ($cp == 0) { |
| 223 | return $a['it'] - $b['it']; |
| 224 | } |
| 225 | return $cp; |
| 226 | } |
| 227 | |
| 228 | public function total() |
| 229 | { |
| 230 | return $this->_total; |
| 231 | } |
| 232 | |
| 233 | public function next() |
| 234 | { |
| 235 | ++$this->pos; |
| 236 | $entry = $this->heap->pop(); |
| 237 | if (is_null($entry)) { |
| 238 | return null; |
| 239 | } |
| 240 | if ($this->preComputed) { |
| 241 | return $entry['value']; |
| 242 | } |
| 243 | $it = $entry['it']; |
| 244 | $item = $this->iterators[$it]->next(); |
| 245 | if (!is_null($item)) { |
| 246 | $this->heap->push(array('it' => $it, 'value' => $item)); |
| 247 | } |
| 248 | return $entry['value']; |
| 249 | } |
| 250 | |
| 251 | public function last() |
| 252 | { |
| 253 | return $this->heap->count() == 0; |
| 254 | } |
| 255 | |
| 256 | public function first() |
| 257 | { |
| 258 | return $this->pos == 1; |
| 259 | } |
| 260 | } |
| 261 | |
| 262 | // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8: |
| 263 | ?> |