classes/pliteratorutils.php

   1 <?php
   2 /***************************************************************************
   3  *  Copyright (C) 2003-2010 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     /** 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
  69      * @return an iterator
  70      */
  71     public static function filter(PlIterator $iterator, $callback)
  72     {
  73         return new PlFilterIterator($iterator, $callback);
  74     }
  75
  76
  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.
  82      */
  83     public static function map(PlIterator $iterator, $callback)
  84     {
  85         return new PlMapIterator($iterator, $callback);
  86     }
  87 }
  88
  89
  90 /** Iterates over an array.
  91  */
  92 class PlArrayIterator implements PlIterator
  93 {
  94     private $array;
  95     private $depth;
  96
  97     private $_its = array();
  98
  99     private $_total;
 100     private $_first;
 101     private $_last;
 102     private $_pos;
 103     private $_flat;
 104
 105     public function __construct(array &$array, $depth = 1, $flat = false)
 106     {
 107         $this->array  =& $array;
 108         $this->depth  = $depth;
 109         $this->_total = $this->count($array, $depth - 1);
 110         $this->_pos   = 0;
 111         $this->_first = false;
 112         $this->_last  = false;
 113         $this->_flat  = $flat;
 114
 115         for ($i = 0 ; $i < $depth ; ++$i) {
 116             if ($i == 0) {
 117                 $this->_its[] = $array;
 118             } else {
 119                 $this->_its[] = current($this->_its[$i - 1]);
 120             }
 121             reset($this->_its[$i]);
 122         }
 123     }
 124
 125     private function count(array &$array, $depth)
 126     {
 127         if ($depth == 0) {
 128             return count($array);
 129         } else {
 130             $sum = 0;
 131             foreach ($array as &$item) {
 132                 $sum += $this->count($item, $depth - 1);
 133             }
 134             return $sum;
 135         }
 136     }
 137
 138     private function nextArray($depth)
 139     {
 140         if ($depth == 0) {
 141             return;
 142         }
 143         $this->_its[$depth] = next($this->_its[$depth - 1]);
 144         if ($this->_its[$depth] === false) {
 145             $this->nextArray($depth - 1);
 146             if ($this->_its[$depth - 1] === false) {
 147                 return;
 148             }
 149             $this->_its[$depth] = current($this->_its[$depth - 1]);
 150         }
 151         reset($this->_its[$depth]);
 152     }
 153
 154     public function next()
 155     {
 156         ++$this->_pos;
 157         $this->_first = ($this->_total > 0 && $this->_pos == 1);
 158         $this->_last  = ($this->_pos == $this->_total);
 159         if ($this->_pos > $this->_total) {
 160             return null;
 161         }
 162
 163         $val = current($this->_its[$this->depth - 1]);
 164         if ($val === false) {
 165             $this->nextArray($this->depth - 1);
 166             $val = current($this->_its[$this->depth - 1]);
 167             if ($val === false) {
 168                 return null;
 169             }
 170         }
 171         $keys = array();
 172         for ($i = 0 ; $i < $this->depth ; ++$i) {
 173             $keys[] = key($this->_its[$i]);
 174         }
 175         next($this->_its[$this->depth - 1]);
 176         if ($this->_flat) {
 177             return $val;
 178         } else {
 179             return array('keys'  => $keys,
 180                          'value' => $val);
 181         }
 182     }
 183
 184     public function total()
 185     {
 186         return $this->_total;
 187     }
 188
 189     public function first()
 190     {
 191         return $this->_first;
 192     }
 193
 194     public function last()
 195     {
 196         return $this->_last;
 197     }
 198 }
 199
 200
 201 /** Iterator that return the result of a merge of several iterators.
 202  */
 203 class PlMergeIterator implements PlIterator
 204 {
 205     /* The heap is field with entries with the form:
 206      *  array('it' => id of the iterator this entry come from,
 207      *        'value' => value of the entry).
 208      */
 209     private $heap;
 210     private $preComputed = false;
 211     private $comparator;
 212     private $iterators;
 213     private $_total;
 214     private $pos;
 215
 216     public function __construct(array $iterators, $callback, $sorted = true)
 217     {
 218         $this->heap = new PlHeap(array($this, 'compare'));
 219         $this->_total = 0;
 220         $this->comparator = $callback;
 221         if ($sorted) {
 222             $this->iterators = $iterators;
 223             foreach ($this->iterators as $key => &$it) {
 224                 $this->_total += $it->total();
 225                 $item = $it->next();
 226                 if (!is_null($item)) {
 227                     $this->heap->push(array('it' => $key, 'value' => $item));
 228                 }
 229             }
 230         } else {
 231             $this->preComputed = true;
 232             foreach ($iterators as $key => &$it) {
 233                 $this->_total += $it->total();
 234                 while (!is_null($item = $it->next())) {
 235                     $this->heap->push(array('it' => $key, 'value' => $item));
 236                 }
 237             }
 238         }
 239         $this->pos = 0;
 240     }
 241
 242     /** Compare two entries of the heap using the comparator of the user.
 243      */
 244     public function compare($a, $b)
 245     {
 246         $cp = call_user_func($this->comparator, $a['value'], $b['value']);
 247         if ($cp == 0) {
 248             return $a['it'] - $b['it'];
 249         }
 250         return $cp;
 251     }
 252
 253     public function total()
 254     {
 255         return $this->_total;
 256     }
 257
 258     public function next()
 259     {
 260         ++$this->pos;
 261         $entry = $this->heap->pop();
 262         if (is_null($entry)) {
 263            return null;
 264         }
 265         if ($this->preComputed) {
 266             return $entry['value'];
 267         }
 268         $it = $entry['it'];
 269         $item = $this->iterators[$it]->next();
 270         if (!is_null($item)) {
 271             $this->heap->push(array('it' => $it, 'value' => $item));
 272         }
 273         return $entry['value'];
 274     }
 275
 276     public function last()
 277     {
 278         return $this->heap->count() == 0;
 279     }
 280
 281     public function first()
 282     {
 283         return $this->pos == 1;
 284     }
 285 }
 286
 287
 288 class PlFilterIterator implements PlIterator {
 289     private $source;
 290     private $callback;
 291     private $element;
 292     private $start;
 293
 294     public function __construct(PlIterator $source, $callback)
 295     {
 296         $this->source = $source;
 297         $this->callback = $callback;
 298         $this->start = true;
 299         $this->element = null;
 300     }
 301
 302     private function fetchNext()
 303     {
 304         do {
 305             $current = $this->source->next();
 306             if (!$current) {
 307                 $this->element = null;
 308                 $this->start   = false;
 309                 return;
 310             }
 311             $res = call_user_func($this->callback, $current);
 312             if ($res) {
 313                 $this->element = $current;
 314                 return;
 315             }
 316         } while (true);
 317     }
 318
 319     public function next()
 320     {
 321         if ($this->element && $this->start) {
 322             $this->start = false;
 323         }
 324         $elt = $this->element;
 325         if ($elt) {
 326             $this->fetchNext();
 327         }
 328         return $elt;
 329     }
 330
 331     public function total()
 332     {
 333         /* This is an approximation since the correct total
 334          * cannot be computed without fetching all the elements
 335          */
 336         return $this->source->total();
 337     }
 338
 339     public function first()
 340     {
 341         return $this->start;
 342     }
 343
 344     public function last()
 345     {
 346         return !$this->start && !$this->element;
 347     }
 348 }
 349
 350
 351 class PlMapIterator implements PlIterator
 352 {
 353     private $source;
 354     private $callback;
 355
 356     public function __construct(PlIterator $source, $callback)
 357     {
 358         $this->source = $source;
 359         $this->callback = $callback;
 360     }
 361
 362     public function next()
 363     {
 364         $elt = $this->source->next();
 365         if ($elt) {
 366             return call_user_func($this->callback, $elt);
 367         } else {
 368             return null;
 369         }
 370     }
 371
 372     public function total()
 373     {
 374         return $this->source->total();
 375     }
 376
 377     public function first()
 378     {
 379         return $this->source->first();
 380     }
 381
 382     public function last()
 383     {
 384         return $this->source->last();
 385     }
 386 }
 387
 388
 389 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8:
 390 ?>