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     /** Builds a new empty iterator
  25      */
  26     public static function emptyIterator()
  27     {
  28         return new PlEmptyIterator();
  29     }
  30
  31     /** Build an iterator over an array.
  32      * @param array The array.
  33      * @param depth The depth of iteration.
  34      * @return an iterator that return entries in the form
  35      *          array(key   => array(0 => key_for_depth0 [, 1 => key_for_depths1, ...]),
  36      *                value => the value);
  37      */
  38     public static function fromArray(array $array, $depth = 1, $flat = false)
  39     {
  40         return new PlArrayIterator($array, $depth, $flat);
  41     }
  42
  43
  44     /** Sort an iterator using the given sort callback.
  45      * @param iterator The iterator to sort.
  46      * @param callback The callback for comparison.
  47      * @return a new iterator with the entries sorted.
  48      */
  49     public static function sort(PlIterator $iterator, $callback)
  50     {
  51         $heap = new PlHeap($callback);
  52         while ($item = $iterator->next()) {
  53             $heap->push($item);
  54         }
  55         return $heap->iterator();
  56     }
  57
  58
  59     /** Merge several iterator into a unique one.
  60      * @param iterators Array of iterators.
  61      * @param callback  The callback for comparison.
  62      * @param sorted    Tell wether the iterators are already sorted using the given callback.
  63      * @return an iterator.
  64      */
  65     public static function merge(array $iterators, $callback, $sorted = true)
  66     {
  67         return new PlMergeIterator($iterators, $callback, $sorted);
  68     }
  69
  70
  71     /** Build an iterator that contains only the elements of the given iterator that
  72      * match the given condition. The condition should be a callback that takes an element
  73      * and returns a boolean.
  74      * @param iterator The source iterator
  75      * @param callback The condition
  76      * @return an iterator
  77      */
  78     public static function filter(PlIterator $iterator, $callback)
  79     {
  80         return new PlFilterIterator($iterator, $callback);
  81     }
  82
  83
  84     /** Build an iterator that transforms the element of another iterator. The callback
  85      * takes an element and transform it into another one. Be careful: if the result
  86      * of the callback is null, the iteration ends.
  87      * @param iterator The source iterator
  88      * @param callback The transformer.
  89      */
  90     public static function map(PlIterator $iterator, $callback)
  91     {
  92         return new PlMapIterator($iterator, $callback);
  93     }
  94
  95     /** Build an iterator whose values are iterators too; such a 'subIterator' will end
  96      * when the value of $callback changes;
  97      * WARNING: will fast-forward the current subiterator until it is over !
  98      * @param iterator The source iterator
  99      * @param callback The callback for detecting changes. XXX: Might be called twice on a given object
 100      * @return an iterator
 101      */
 102     public static function subIterator(PlIterator $iterator, $callback)
 103     {
 104         return new PlSubIterator($iterator, $callback);
 105     }
 106
 107     /** Build an iterator that will iterate over the given set of iterators, returning consistent
 108      * sets of values (i.e only the values for which the result of the callback is the same as that
 109      * for the master)
 110      * @param iterators The set of iterators
 111      * @param callbacks A list of callbacks (one for each iterator), or a single, common, callback
 112      * @param master The id of the "master" iterator in the first list
 113      */
 114     public static function parallelIterator(array $iterators, $callbacks, $master)
 115     {
 116         return new PlParallelIterator($iterators, $callbacks, $master);
 117     }
 118
 119     /** Returns the callback for '$x -> $x[$key]';
 120      * @param $key the index to retrieve in arrays
 121      * @return a callback
 122      */
 123     public static function arrayValueCallback($key)
 124     {
 125         $callback = new _GetArrayValueCallback($key);
 126         return array($callback, 'get');
 127     }
 128
 129     /** Returns the callback for '$x -> $x->prop';
 130      * @param $property The property to retrieve
 131      * @return a callback
 132      */
 133     public static function objectPropertyCallback($property)
 134     {
 135         $callback = new _GetObjectPropertyCallback($property);
 136         return array($callback, 'get');
 137     }
 138 }
 139
 140 /** Empty iterator
 141  */
 142 class PlEmptyIterator implements PlIterator
 143 {
 144     public function first()
 145     {
 146         return false;
 147     }
 148
 149     public function last()
 150     {
 151         return false;
 152     }
 153
 154     public function next()
 155     {
 156         return null;
 157     }
 158
 159     public function total()
 160     {
 161         return 0;
 162     }
 163 }
 164
 165 /** Iterates over an array.
 166  */
 167 class PlArrayIterator implements PlIterator
 168 {
 169     private $array;
 170     private $depth;
 171
 172     private $_its = array();
 173
 174     private $_total;
 175     private $_first;
 176     private $_last;
 177     private $_pos;
 178     private $_flat;
 179
 180     public function __construct(array &$array, $depth = 1, $flat = false)
 181     {
 182         $this->array  =& $array;
 183         $this->depth  = $depth;
 184         $this->_total = $this->count($array, $depth - 1);
 185         $this->_pos   = 0;
 186         $this->_first = false;
 187         $this->_last  = false;
 188         $this->_flat  = $flat;
 189
 190         for ($i = 0 ; $i < $depth ; ++$i) {
 191             if ($i == 0) {
 192                 $this->_its[] = $array;
 193             } else {
 194                 $this->_its[] = current($this->_its[$i - 1]);
 195             }
 196             reset($this->_its[$i]);
 197         }
 198     }
 199
 200     private function count(array &$array, $depth)
 201     {
 202         if ($depth == 0) {
 203             return count($array);
 204         } else {
 205             $sum = 0;
 206             foreach ($array as &$item) {
 207                 $sum += $this->count($item, $depth - 1);
 208             }
 209             return $sum;
 210         }
 211     }
 212
 213     private function nextArray($depth)
 214     {
 215         if ($depth == 0) {
 216             return;
 217         }
 218         $this->_its[$depth] = next($this->_its[$depth - 1]);
 219         if ($this->_its[$depth] === false) {
 220             $this->nextArray($depth - 1);
 221             if ($this->_its[$depth - 1] === false) {
 222                 return;
 223             }
 224             $this->_its[$depth] = current($this->_its[$depth - 1]);
 225         }
 226         reset($this->_its[$depth]);
 227     }
 228
 229     public function next()
 230     {
 231         ++$this->_pos;
 232         $this->_first = ($this->_total > 0 && $this->_pos == 1);
 233         $this->_last  = ($this->_pos == $this->_total);
 234         if ($this->_pos > $this->_total) {
 235             return null;
 236         }
 237
 238         $val = current($this->_its[$this->depth - 1]);
 239         if ($val === false) {
 240             $this->nextArray($this->depth - 1);
 241             $val = current($this->_its[$this->depth - 1]);
 242             if ($val === false) {
 243                 return null;
 244             }
 245         }
 246         $keys = array();
 247         for ($i = 0 ; $i < $this->depth ; ++$i) {
 248             $keys[] = key($this->_its[$i]);
 249         }
 250         next($this->_its[$this->depth - 1]);
 251         if ($this->_flat) {
 252             return $val;
 253         } else {
 254             return array('keys'  => $keys,
 255                          'value' => $val);
 256         }
 257     }
 258
 259     public function total()
 260     {
 261         return $this->_total;
 262     }
 263
 264     public function first()
 265     {
 266         return $this->_first;
 267     }
 268
 269     public function last()
 270     {
 271         return $this->_last;
 272     }
 273 }
 274
 275
 276 /** Iterator that return the result of a merge of several iterators.
 277  */
 278 class PlMergeIterator implements PlIterator
 279 {
 280     /* The heap is field with entries with the form:
 281      *  array('it' => id of the iterator this entry come from,
 282      *        'value' => value of the entry).
 283      */
 284     private $heap;
 285     private $preComputed = false;
 286     private $comparator;
 287     private $iterators;
 288     private $_total;
 289     private $pos;
 290
 291     public function __construct(array $iterators, $callback, $sorted = true)
 292     {
 293         $this->heap = new PlHeap(array($this, 'compare'));
 294         $this->_total = 0;
 295         $this->comparator = $callback;
 296         if ($sorted) {
 297             $this->iterators = $iterators;
 298             foreach ($this->iterators as $key => &$it) {
 299                 $this->_total += $it->total();
 300                 $item = $it->next();
 301                 if (!is_null($item)) {
 302                     $this->heap->push(array('it' => $key, 'value' => $item));
 303                 }
 304             }
 305         } else {
 306             $this->preComputed = true;
 307             foreach ($iterators as $key => &$it) {
 308                 $this->_total += $it->total();
 309                 while (!is_null($item = $it->next())) {
 310                     $this->heap->push(array('it' => $key, 'value' => $item));
 311                 }
 312             }
 313         }
 314         $this->pos = 0;
 315     }
 316
 317     /** Compare two entries of the heap using the comparator of the user.
 318      */
 319     public function compare($a, $b)
 320     {
 321         $cp = call_user_func($this->comparator, $a['value'], $b['value']);
 322         if ($cp == 0) {
 323             return $a['it'] - $b['it'];
 324         }
 325         return $cp;
 326     }
 327
 328     public function total()
 329     {
 330         return $this->_total;
 331     }
 332
 333     public function next()
 334     {
 335         ++$this->pos;
 336         $entry = $this->heap->pop();
 337         if (is_null($entry)) {
 338            return null;
 339         }
 340         if ($this->preComputed) {
 341             return $entry['value'];
 342         }
 343         $it = $entry['it'];
 344         $item = $this->iterators[$it]->next();
 345         if (!is_null($item)) {
 346             $this->heap->push(array('it' => $it, 'value' => $item));
 347         }
 348         return $entry['value'];
 349     }
 350
 351     public function last()
 352     {
 353         return $this->heap->count() == 0;
 354     }
 355
 356     public function first()
 357     {
 358         return $this->pos == 1;
 359     }
 360 }
 361
 362
 363 class PlFilterIterator implements PlIterator
 364 {
 365     private $pos;
 366     private $source;
 367     private $callback;
 368     private $element;
 369
 370     public function __construct(PlIterator $source, $callback)
 371     {
 372         $this->source   = $source;
 373         $this->callback = $callback;
 374         $this->pos      = 0;
 375         $this->element  = $this->fetchNext();
 376     }
 377
 378     private function fetchNext()
 379     {
 380         do {
 381             $current = $this->source->next();
 382             if (is_null($current) || call_user_func($this->callback, $current)) {
 383                 return $current;
 384             }
 385         } while (true);
 386     }
 387
 388     public function next()
 389     {
 390         ++$this->pos;
 391         $elt = $this->element;
 392         if (!is_null($this->element)) {
 393             $this->element = $this->fetchNext();
 394         }
 395         return $elt;
 396     }
 397
 398     public function total()
 399     {
 400         /* This is an approximation since the correct total
 401          * cannot be computed without fetching all the elements
 402          */
 403         return $this->source->total();
 404     }
 405
 406     public function first()
 407     {
 408         return $this->pos == 1;
 409     }
 410
 411     public function last()
 412     {
 413         return is_null($this->element);
 414     }
 415 }
 416
 417
 418 class PlMapIterator implements PlIterator
 419 {
 420     private $source;
 421     private $callback;
 422
 423     public function __construct(PlIterator $source, $callback)
 424     {
 425         $this->source = $source;
 426         $this->callback = $callback;
 427     }
 428
 429     public function next()
 430     {
 431         $elt = $this->source->next();
 432         if ($elt) {
 433             return call_user_func($this->callback, $elt);
 434         } else {
 435             return null;
 436         }
 437     }
 438
 439     public function total()
 440     {
 441         return $this->source->total();
 442     }
 443
 444     public function first()
 445     {
 446         return $this->source->first();
 447     }
 448
 449     public function last()
 450     {
 451         return $this->source->last();
 452     }
 453 }
 454
 455 class PlSubIterator implements PlIterator
 456 {
 457     private $source;
 458     private $callback;
 459     private $next = null; // The next item, if it has been fetched too early by a subiterator
 460     private $pos = 0;
 461     private $sub = null;
 462
 463     public function __construct(PlIterator $source, $callback)
 464     {
 465         $this->source = $source;
 466         $this->callback = $callback;
 467     }
 468
 469     /** WARNING: this will "fast-forward" the subiterator to its end
 470      */
 471     public function next()
 472     {
 473         if ($this->last()) {
 474             return null;
 475         } else {
 476             if ($this->sub != null) {
 477                 while (!$this->sub->last()) {
 478                     $this->sub->next();
 479                 }
 480             }
 481
 482             if ($this->last()) {
 483                 return null;
 484             }
 485
 486             ++$this->pos;
 487             $this->sub = new PlInnerSubIterator($this->source, $this->callback, $this, $this->next);
 488             return $this->sub;
 489         }
 490     }
 491
 492     /** This will always be a too big number, but the actual result can't be easily computed
 493      */
 494     public function total()
 495     {
 496         return $this->source->total();
 497     }
 498
 499     /** This will only return true if the current subiterator was the last one,
 500      * and if it has been fully used
 501      */
 502     public function last()
 503     {
 504         if ($this->sub != null && !$this->sub->last()) {
 505             return false;
 506         }
 507         return ($this->source->last() && $this->next == null);
 508     }
 509
 510     public function first()
 511     {
 512         return $this->pos == 1;
 513     }
 514
 515     // Called by a subiterator to "rewind" the core iterator
 516     public function setNext($item)
 517     {
 518         $this->next = $item;
 519     }
 520 }
 521
 522 class PlInnerSubIterator implements PlIterator
 523 {
 524     private $source;
 525     private $callback;
 526     private $parent;
 527
 528     private $next; // Not null if the source has to be "rewinded"
 529
 530     private $curval = null;
 531     private $curelt = null;
 532     private $val = null;
 533     private $pos = 0;
 534     private $stepped = false;
 535     private $over = false;
 536
 537     public function __construct(PlIterator $source, $callback, PlSubIterator $parent, $next = null)
 538     {
 539         $this->source = $source;
 540         $this->callback = $callback;
 541         $this->parent = $parent;
 542         $this->next = $next;
 543         $this->parent->setNext(null);
 544     }
 545
 546     public function value()
 547     {
 548         $this->_step();
 549         return $this->curval;
 550     }
 551
 552     // Move one step, if the current element has been used
 553     private function _step()
 554     {
 555         if ($this->stepped) {
 556             return;
 557         }
 558
 559         if ($this->next != null) {
 560             $this->curelt = $this->next;
 561             $this->next = null;
 562         } else {
 563             if ($this->source->last()) {
 564                 $this->over = true;
 565                 return;
 566             }
 567             $this->curelt = $this->source->next();
 568         }
 569
 570         if ($this->pos == 0) {
 571             $this->val = call_user_func($this->callback, $this->curelt);
 572             $this->curval = $this->val;
 573         } else {
 574             $this->curval = call_user_func($this->callback, $this->curelt);
 575         }
 576
 577         $this->stepped = true;
 578     }
 579
 580     public function next()
 581     {
 582         if ($this->over) {
 583             return null;
 584         }
 585
 586         $this->_step();
 587
 588         if ($this->over) {
 589             return null;
 590         }
 591
 592         ++$this->pos;
 593         $this->stepped = false;
 594
 595         if ($this->val == $this->curval) {
 596             return $this->curelt;
 597         }
 598
 599         $this->parent->setNext($this->curelt);
 600         $this->over = true;
 601         return null;
 602     }
 603
 604     /** This will always be a too big number, but the actual result can't be easily computed
 605      */
 606     public function total()
 607     {
 608         return $this->source->total();
 609     }
 610
 611     public function last()
 612     {
 613         if ($this->over) {
 614             return true;
 615         }
 616         $this->_step();
 617         return $this->over || ($this->val != $this->curval);
 618     }
 619
 620     public function first()
 621     {
 622         return $this->pos == 1;
 623     }
 624
 625 }
 626
 627 /** Builds an iterator over a set of iterators, from which one is given as 'master';
 628  * The arguments are :
 629  *  - An array of iterators, to iterate simultaneously
 630  *  - An array of callbacks (one attached to each iterator), or a single callback (to
 631  *      use for all iterators)
 632  *  - The id of the 'master' iterator
 633  *
 634  * This ParallelIterator will iterate over the iterators, and, at each
 635  * step of the master iterator, it will apply the callbacks to the corresponding
 636  * iterators and return the values of the "slaves" for which the callback returned the
 637  * same value as the callback of the master.
 638  *
 639  * The callback should compute some kind of index, and never return the same value
 640  * twice for a given iterator
 641  *
 642  * It is assumed that, if the callback for a slave doesn't have the same value
 643  * as the value for the master, this means that there is a "hole" in the values
 644  * of that slave.
 645  *
 646  * Example :
 647  *   - The callback is 'get the first cell'
 648  *   - The master is :
 649  *      [0, 1], [1, 13], [2, 42]
 650  *   - The first slave (slave1) is :
 651  *      [0, 'a'], [2, 'b']
 652  *   - The second slave (slave2) is :
 653  *      [1, 42], [2, 0]
 654  * The resulting iterator would yield :
 655  * - array(master => [0, 1], slave1 => [0, 'a'], slave2 => null)
 656  * - array(master => [1, 13], slave1 => null, slave2 => [1, 42])
 657  * - array(master => [2, 42], slave1 => [1, 'b'], slave2 => [2, 0])
 658  */
 659 class PlParallelIterator implements PlIterator
 660 {
 661     private $iterators;
 662     private $ids;
 663     private $callbacks;
 664
 665     private $master_id;
 666     private $master;
 667
 668     private $over = array();
 669     private $stepped = array();
 670     private $current_elts = array();
 671     private $callback_res = array();
 672
 673     public function __construct(array $iterators, $callbacks, $master)
 674     {
 675         $this->iterators = $iterators;
 676         $this->master_id = $master;
 677         $this->master = $iterators[$master];
 678
 679         $this->ids = array_keys($iterators);
 680
 681         $v = array_values($callbacks);
 682         if (is_array($v[0])) {
 683             $this->callbacks = $callbacks;
 684         } else {
 685             $this->callbacks = array();
 686             foreach ($this->ids as $id) {
 687                 $this->callbacks[$id] = $callbacks;
 688             }
 689         }
 690
 691         foreach ($this->ids as $id) {
 692             $this->stepped[$id] = false;
 693             $this->over[$id] = false;
 694             $this->current_elts[$id] = null;
 695             $this->callback_res[$id] = null;
 696         }
 697     }
 698
 699     private function step($id)
 700     {
 701         if ($this->stepped[$id]) {
 702             return;
 703         }
 704
 705         // Don't do anything if the iterator is at its end
 706         if ($this->over[$id]) {
 707             $this->stepped[$id] = true;
 708             return;
 709         }
 710
 711         $it = $this->iterators[$id];
 712         $nxt = $it->next();
 713         $this->stepped[$id] = true;
 714         if ($nxt === null) {
 715             $this->over[$id] = true;
 716             $this->current_elts[$id] = null;
 717             $this->callback_res[$id] = null;
 718             return;
 719         }
 720         $res = call_user_func($this->callbacks[$id], $nxt);
 721         $this->current_elts[$id] = $nxt;
 722         $this->callback_res[$id] = $res;
 723     }
 724
 725     private function stepAll()
 726     {
 727         foreach ($this->ids as $id) {
 728             $this->step($id);
 729         }
 730     }
 731
 732     public function next()
 733     {
 734         $this->stepAll();
 735         if ($this->current_elts[$this->master_id] === null) {
 736             return null;
 737         }
 738
 739         $res = array();
 740         $master = $this->callback_res[$this->master_id];
 741         foreach ($this->ids as $id) {
 742             if ($this->callback_res[$id] == $master) {
 743                 $res[$id] = $this->current_elts[$id];
 744                 $this->stepped[$id] = false;
 745             } else {
 746                 $res[$id] = null;
 747             }
 748         }
 749
 750         return $res;
 751     }
 752
 753     public function first()
 754     {
 755         return $this->master->first();
 756     }
 757
 758     public function total()
 759     {
 760         return $this->master->total();
 761     }
 762
 763     public function last()
 764     {
 765         return $this->master->last();
 766     }
 767 }
 768
 769 // Wrapper class for 'arrayValueCallback' (get field $key of the given array)
 770 class _GetArrayValueCallback
 771 {
 772     private $key;
 773
 774     public function __construct($key)
 775     {
 776         $this->key = $key;
 777     }
 778
 779     public function get(array $arr)
 780     {
 781         if (array_key_exists($this->key, $arr)) {
 782             return $arr[$this->key];
 783         } else {
 784             return null;
 785         }
 786     }
 787 }
 788
 789 // Wrapper class for 'objectPropertyCallback' (get property ->$blah of the given object)
 790 class _GetObjectPropertyCallback
 791 {
 792     private $property;
 793
 794     public function __construct($property)
 795     {
 796         $this->property = $property;
 797     }
 798
 799     public function get($obj)
 800     {
 801         $p = $this->property;
 802         return @$obj->$p;
 803     }
 804 }
 805
 806 // vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8:
 807 ?>