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     /** 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.
  92      * @return an iterator
  93      */
  94     public static function subIterator(PlIterator $iterator, $callback)
  95     {
  96         return new SubIterator($iterator, $callback);
  97     }
  98
  99     /** Returns the callback for '$x -> $x[$key]';
 100      * @param $key the index to retrieve in arrays
 101      * @return a callback
 102      */
 103     public static function arrayValueCallback($key)
 104     {
 105         $callback = new _GetArrayValueCallback($key);
 106         return array($callback, 'get');
 107     }
 108 }
 109
 110 /** Iterates over an array.
 111  */
 112 class PlArrayIterator implements PlIterator
 113 {
 114     private $array;
 115     private $depth;
 116
 117     private $_its = array();
 118
 119     private $_total;
 120     private $_first;
 121     private $_last;
 122     private $_pos;
 123     private $_flat;
 124
 125     public function __construct(array &$array, $depth = 1, $flat = false)
 126     {
 127         $this->array  =& $array;
 128         $this->depth  = $depth;
 129         $this->_total = $this->count($array, $depth - 1);
 130         $this->_pos   = 0;
 131         $this->_first = false;
 132         $this->_last  = false;
 133         $this->_flat  = $flat;
 134
 135         for ($i = 0 ; $i < $depth ; ++$i) {
 136             if ($i == 0) {
 137                 $this->_its[] = $array;
 138             } else {
 139                 $this->_its[] = current($this->_its[$i - 1]);
 140             }
 141             reset($this->_its[$i]);
 142         }
 143     }
 144
 145     private function count(array &$array, $depth)
 146     {
 147         if ($depth == 0) {
 148             return count($array);
 149         } else {
 150             $sum = 0;
 151             foreach ($array as &$item) {
 152                 $sum += $this->count($item, $depth - 1);
 153             }
 154             return $sum;
 155         }
 156     }
 157
 158     private function nextArray($depth)
 159     {
 160         if ($depth == 0) {
 161             return;
 162         }
 163         $this->_its[$depth] = next($this->_its[$depth - 1]);
 164         if ($this->_its[$depth] === false) {
 165             $this->nextArray($depth - 1);
 166             if ($this->_its[$depth - 1] === false) {
 167                 return;
 168             }
 169             $this->_its[$depth] = current($this->_its[$depth - 1]);
 170         }
 171         reset($this->_its[$depth]);
 172     }
 173
 174     public function next()
 175     {
 176         ++$this->_pos;
 177         $this->_first = ($this->_total > 0 && $this->_pos == 1);
 178         $this->_last  = ($this->_pos == $this->_total);
 179         if ($this->_pos > $this->_total) {
 180             return null;
 181         }
 182
 183         $val = current($this->_its[$this->depth - 1]);
 184         if ($val === false) {
 185             $this->nextArray($this->depth - 1);
 186             $val = current($this->_its[$this->depth - 1]);
 187             if ($val === false) {
 188                 return null;
 189             }
 190         }
 191         $keys = array();
 192         for ($i = 0 ; $i < $this->depth ; ++$i) {
 193             $keys[] = key($this->_its[$i]);
 194         }
 195         next($this->_its[$this->depth - 1]);
 196         if ($this->_flat) {
 197             return $val;
 198         } else {
 199             return array('keys'  => $keys,
 200                          'value' => $val);
 201         }
 202     }
 203
 204     public function total()
 205     {
 206         return $this->_total;
 207     }
 208
 209     public function first()
 210     {
 211         return $this->_first;
 212     }
 213
 214     public function last()
 215     {
 216         return $this->_last;
 217     }
 218 }
 219
 220
 221 /** Iterator that return the result of a merge of several iterators.
 222  */
 223 class PlMergeIterator implements PlIterator
 224 {
 225     /* The heap is field with entries with the form:
 226      *  array('it' => id of the iterator this entry come from,
 227      *        'value' => value of the entry).
 228      */
 229     private $heap;
 230     private $preComputed = false;
 231     private $comparator;
 232     private $iterators;
 233     private $_total;
 234     private $pos;
 235
 236     public function __construct(array $iterators, $callback, $sorted = true)
 237     {
 238         $this->heap = new PlHeap(array($this, 'compare'));
 239         $this->_total = 0;
 240         $this->comparator = $callback;
 241         if ($sorted) {
 242             $this->iterators = $iterators;
 243             foreach ($this->iterators as $key => &$it) {
 244                 $this->_total += $it->total();
 245                 $item = $it->next();
 246                 if (!is_null($item)) {
 247                     $this->heap->push(array('it' => $key, 'value' => $item));
 248                 }
 249             }
 250         } else {
 251             $this->preComputed = true;
 252             foreach ($iterators as $key => &$it) {
 253                 $this->_total += $it->total();
 254                 while (!is_null($item = $it->next())) {
 255                     $this->heap->push(array('it' => $key, 'value' => $item));
 256                 }
 257             }
 258         }
 259         $this->pos = 0;
 260     }
 261
 262     /** Compare two entries of the heap using the comparator of the user.
 263      */
 264     public function compare($a, $b)
 265     {
 266         $cp = call_user_func($this->comparator, $a['value'], $b['value']);
 267         if ($cp == 0) {
 268             return $a['it'] - $b['it'];
 269         }
 270         return $cp;
 271     }
 272
 273     public function total()
 274     {
 275         return $this->_total;
 276     }
 277
 278     public function next()
 279     {
 280         ++$this->pos;
 281         $entry = $this->heap->pop();
 282         if (is_null($entry)) {
 283            return null;
 284         }
 285         if ($this->preComputed) {
 286             return $entry['value'];
 287         }
 288         $it = $entry['it'];
 289         $item = $this->iterators[$it]->next();
 290         if (!is_null($item)) {
 291             $this->heap->push(array('it' => $it, 'value' => $item));
 292         }
 293         return $entry['value'];
 294     }
 295
 296     public function last()
 297     {
 298         return $this->heap->count() == 0;
 299     }
 300
 301     public function first()
 302     {
 303         return $this->pos == 1;
 304     }
 305 }
 306
 307
 308 class PlFilterIterator implements PlIterator {
 309     private $source;
 310     private $callback;
 311     private $element;
 312     private $start;
 313
 314     public function __construct(PlIterator $source, $callback)
 315     {
 316         $this->source = $source;
 317         $this->callback = $callback;
 318         $this->start = true;
 319         $this->element = null;
 320     }
 321
 322     private function fetchNext()
 323     {
 324         do {
 325             $current = $this->source->next();
 326             if (!$current) {
 327                 $this->element = null;
 328                 $this->start   = false;
 329                 return;
 330             }
 331             $res = call_user_func($this->callback, $current);
 332             if ($res) {
 333                 $this->element = $current;
 334                 return;
 335             }
 336         } while (true);
 337     }
 338
 339     public function next()
 340     {
 341         if ($this->element && $this->start) {
 342             $this->start = false;
 343         }
 344         $elt = $this->element;
 345         if ($elt) {
 346             $this->fetchNext();
 347         }
 348         return $elt;
 349     }
 350
 351     public function total()
 352     {
 353         /* This is an approximation since the correct total
 354          * cannot be computed without fetching all the elements
 355          */
 356         return $this->source->total();
 357     }
 358
 359     public function first()
 360     {
 361         return $this->start;
 362     }
 363
 364     public function last()
 365     {
 366         return !$this->start && !$this->element;
 367     }
 368 }
 369
 370
 371 class PlMapIterator implements PlIterator
 372 {
 373     private $source;
 374     private $callback;
 375
 376     public function __construct(PlIterator $source, $callback)
 377     {
 378         $this->source = $source;
 379         $this->callback = $callback;
 380     }
 381
 382     public function next()
 383     {
 384         $elt = $this->source->next();
 385         if ($elt) {
 386             return call_user_func($this->callback, $elt);
 387         } else {
 388             return null;
 389         }
 390     }
 391
 392     public function total()
 393     {
 394         return $this->source->total();
 395     }
 396
 397     public function first()
 398     {
 399         return $this->source->first();
 400     }
 401
 402     public function last()
 403     {
 404         return $this->source->last();
 405     }
 406 }
 407
 408 class PlSubIterator implements PlIterator
 409 {
 410     private $source;
 411     private $callback;
 412     private $next = null; // The next item, if it has been fetched too early by a subiterator
 413
 414     public function __construct(PlIterator $source, $callback)
 415     {
 416         $this->source = $source;
 417         $this->callback = $callback;
 418     }
 419
 420     public function next()
 421     {
 422         if ($this->last()) {
 423             return null;
 424         } else {
 425             return new PlInnerSubIterator($this->source, $this->callback, $this, $this->next);
 426         }
 427     }
 428
 429     /** This will always be a too big number, but the actual result can't be easily computed
 430      */
 431     public function total()
 432     {
 433         return $this->source->total();
 434     }
 435
 436     public function last()
 437     {
 438         return ($this->source->last() && $this->next == null);
 439     }
 440
 441     // Called by a subiterator to "rewind" the core iterator
 442     public function setNext($item)
 443     {
 444         $this->next = $item;
 445     }
 446 }
 447
 448 class PlInnerSubIterator implements PlIterator
 449 {
 450     private $source;
 451     private $callback;
 452     private $parent;
 453
 454     private $next; // Not null if the source has to be "rewinded"
 455
 456     private $curval = null;
 457     private $curelt = null;
 458     private $stepped = false;
 459     private $over = false;
 460
 461     public function __construct(PlIterator $source, $callback, PlSubIterator $parent, $next = null)
 462     {
 463         $this->source = $source;
 464         $this->callback = $callback;
 465         $this->parent = $parent;
 466         $this->next = $next;
 467     }
 468
 469     public function value()
 470     {
 471         $this->_step();
 472         return $this->curval;
 473     }
 474
 475     // Move one step, if the current element has been used
 476     private function _step()
 477     {
 478         if ($this->stepped) {
 479             return;
 480         }
 481
 482         if ($this->next != null) {
 483             $this->curelt = $this->next;
 484             $this->next = null;
 485         } else {
 486             $elt = $this->source->next();
 487         }
 488         $this->stepped = true;
 489     }
 490
 491     public function next()
 492     {
 493         $this->_step();
 494         $this->stepped = false;
 495
 496         if ($this->elt) {
 497             $val = call_user_func($this->callback, $this->elt);
 498             if ($val == $this->curval) {
 499                 $this->curval = $val;
 500                 return $this->elt;
 501             } else {
 502                 $this->parent->setNext($this->elt);
 503             }
 504         }
 505         $this->over = true;
 506         return null;
 507     }
 508
 509     /** This will always be a too big number, but the actual result can't be easily computed
 510      */
 511     public function total()
 512     {
 513         return $this->source->total();
 514     }
 515
 516     public function last()
 517     {
 518         return $this->over;
 519     }
 520
 521 }
 522
 523 // Wrapper class for 'arrayValueCallback' (get field $key of the given array)
 524 class _GetArrayValueCallback
 525 {
 526     private $key;
 527
 528     public function __construct($key)
 529     {
 530         $this->key = $key;
 531     }
 532
 533     public function get(array $arr)
 534     {
 535         if (array_key_exists($key, $arr)) {
 536             return $arr[$key];
 537         } else {
 538             return null;
 539         }
 540     }
 541 }
 542
 543 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8:
 544 ?>