X-Git-Url: http://git.polytechnique.org/?a=blobdiff_plain;f=classes%2Fpliteratorutils.php;h=a78c85138dddc235a56e6c88858ea2bbcd669abf;hb=fa7ffd661d77b24cdb385aca7bdb04c938214061;hp=d70b0509d1706c3ee72cfc2901df448419e857cf;hpb=2ab75571bf840471fa9559292b75852bfce004d3;p=platal.git

diff --git a/classes/pliteratorutils.php b/classes/pliteratorutils.php
index d70b050..a78c851 100644
--- a/classes/pliteratorutils.php
+++ b/classes/pliteratorutils.php
@@ -1,6 +1,6 @@
 <?php
 /***************************************************************************
- *  Copyright (C) 2003-2010 Polytechnique.org                              *
+ *  Copyright (C) 2003-2011 Polytechnique.org                              *
  *  http://opensource.polytechnique.org/                                   *
  *                                                                         *
  *  This program is free software; you can redistribute it and/or modify   *
@@ -21,6 +21,13 @@
 
 class PlIteratorUtils
 {
+    /** Builds a new empty iterator
+     */
+    public static function emptyIterator()
+    {
+        return new PlEmptyIterator();
+    }
+
     /** Build an iterator over an array.
      * @param array The array.
      * @param depth The depth of iteration.
@@ -59,8 +66,108 @@ class PlIteratorUtils
     {
         return new PlMergeIterator($iterators, $callback, $sorted);
     }
+
+
+    /** Build an iterator that contains only the elements of the given iterator that
+     * match the given condition. The condition should be a callback that takes an element
+     * and returns a boolean.
+     * @param iterator The source iterator
+     * @param callback The condition
+     * @return an iterator
+     */
+    public static function filter(PlIterator $iterator, $callback)
+    {
+        return new PlFilterIterator($iterator, $callback);
+    }
+
+
+    /** Build an iterator that transforms the element of another iterator. The callback
+     * takes an element and transform it into another one. Be careful: if the result
+     * of the callback is null, the iteration ends.
+     * @param iterator The source iterator
+     * @param callback The transformer.
+     */
+    public static function map(PlIterator $iterator, $callback)
+    {
+        return new PlMapIterator($iterator, $callback);
+    }
+
+    /** Build an iterator whose values are iterators too; such a 'subIterator' will end
+     * when the value of $callback changes;
+     * WARNING: will fast-forward the current subiterator until it is over !
+     * @param iterator The source iterator
+     * @param callback The callback for detecting changes. XXX: Might be called twice on a given object
+     * @return an iterator
+     */
+    public static function subIterator(PlIterator $iterator, $callback)
+    {
+        return new PlSubIterator($iterator, $callback);
+    }
+
+    /** Build an iterator that will iterate over the given set of iterators, returning consistent
+     * sets of values (i.e only the values for which the result of the callback is the same as that
+     * for the master)
+     * @param iterators The set of iterators
+     * @param callbacks A list of callbacks (one for each iterator), or a single, common, callback
+     * @param master The id of the "master" iterator in the first list
+     */
+    public static function parallelIterator(array $iterators, $callbacks, $master)
+    {
+        return new PlParallelIterator($iterators, $callbacks, $master);
+    }
+
+    /** Returns the callback for '$x -> $x[$key]';
+     * @param $key the index to retrieve in arrays
+     * @return a callback
+     */
+    public static function arrayValueCallback($key)
+    {
+        $callback = new _GetArrayValueCallback($key);
+        return array($callback, 'get');
+    }
+
+    /** Returns the callback for '$x -> $x->prop';
+     * @param $property The property to retrieve
+     * @return a callback
+     */
+    public static function objectPropertyCallback($property)
+    {
+        $callback = new _GetObjectPropertyCallback($property);
+        return array($callback, 'get');
+    }
+
+    /** Returns a wrapper around the PlIterator suitable for foreach() iterations
+     */
+    public static function foreachIterator(PlIterator $iterator)
+    {
+        return new SPLIterator($iterator);
+    }
 }
 
+/** Empty iterator
+ */
+class PlEmptyIterator implements PlIterator
+{
+    public function first()
+    {
+        return false;
+    }
+
+    public function last()
+    {
+        return false;
+    }
+
+    public function next()
+    {
+        return null;
+    }
+
+    public function total()
+    {
+        return 0;
+    }
+}
 
 /** Iterates over an array.
  */
@@ -259,5 +366,492 @@ class PlMergeIterator implements PlIterator
     }
 }
 
-// vim:set et sw=4 sts=4 sws=4 foldmethod=marker enc=utf-8:
+
+class PlFilterIterator implements PlIterator
+{
+    private $pos;
+    private $source;
+    private $callback;
+    private $element;
+
+    public function __construct(PlIterator $source, $callback)
+    {
+        $this->source   = $source;
+        $this->callback = $callback;
+        $this->pos      = 0;
+        $this->element  = $this->fetchNext();
+    }
+
+    private function fetchNext()
+    {
+        do {
+            $current = $this->source->next();
+            if (is_null($current) || call_user_func($this->callback, $current)) {
+                return $current;
+            }
+        } while (true);
+    }
+
+    public function next()
+    {
+        ++$this->pos;
+        $elt = $this->element;
+        if (!is_null($this->element)) {
+            $this->element = $this->fetchNext();
+        }
+        return $elt;
+    }
+
+    public function total()
+    {
+        /* This is an approximation since the correct total
+         * cannot be computed without fetching all the elements
+         */
+        return $this->source->total();
+    }
+
+    public function first()
+    {
+        return $this->pos == 1;
+    }
+
+    public function last()
+    {
+        return is_null($this->element);
+    }
+}
+
+
+class PlMapIterator implements PlIterator
+{
+    private $source;
+    private $callback;
+
+    public function __construct(PlIterator $source, $callback)
+    {
+        $this->source = $source;
+        $this->callback = $callback;
+    }
+
+    public function next()
+    {
+        $elt = $this->source->next();
+        if ($elt) {
+            return call_user_func($this->callback, $elt);
+        } else {
+            return null;
+        }
+    }
+
+    public function total()
+    {
+        return $this->source->total();
+    }
+
+    public function first()
+    {
+        return $this->source->first();
+    }
+
+    public function last()
+    {
+        return $this->source->last();
+    }
+}
+
+class PlSubIterator implements PlIterator
+{
+    private $source;
+    private $callback;
+    private $next = null; // The next item, if it has been fetched too early by a subiterator
+    private $pos = 0;
+    private $sub = null;
+
+    public function __construct(PlIterator $source, $callback)
+    {
+        $this->source = $source;
+        $this->callback = $callback;
+    }
+
+    /** WARNING: this will "fast-forward" the subiterator to its end
+     */
+    public function next()
+    {
+        if ($this->last()) {
+            return null;
+        } else {
+            if ($this->sub != null) {
+                while (!$this->sub->last()) {
+                    $this->sub->next();
+                }
+            }
+
+            if ($this->last()) {
+                return null;
+            }
+
+            ++$this->pos;
+            $this->sub = new PlInnerSubIterator($this->source, $this->callback, $this, $this->next);
+            return $this->sub;
+        }
+    }
+
+    /** This will always be a too big number, but the actual result can't be easily computed
+     */
+    public function total()
+    {
+        return $this->source->total();
+    }
+
+    /** This will only return true if the current subiterator was the last one,
+     * and if it has been fully used
+     */
+    public function last()
+    {
+        if ($this->sub != null && !$this->sub->last()) {
+            return false;
+        }
+        return ($this->source->last() && $this->next == null);
+    }
+
+    public function first()
+    {
+        return $this->pos == 1;
+    }
+
+    // Called by a subiterator to "rewind" the core iterator
+    public function setNext($item)
+    {
+        $this->next = $item;
+    }
+}
+
+class PlInnerSubIterator implements PlIterator
+{
+    private $source;
+    private $callback;
+    private $parent;
+
+    private $next; // Not null if the source has to be "rewinded"
+
+    private $curval = null;
+    private $curelt = null;
+    private $val = null;
+    private $pos = 0;
+    private $stepped = false;
+    private $over = false;
+
+    public function __construct(PlIterator $source, $callback, PlSubIterator $parent, $next = null)
+    {
+        $this->source = $source;
+        $this->callback = $callback;
+        $this->parent = $parent;
+        $this->next = $next;
+        $this->parent->setNext(null);
+    }
+
+    public function value()
+    {
+        $this->_step();
+        return $this->curval;
+    }
+
+    // Move one step, if the current element has been used
+    private function _step()
+    {
+        if ($this->stepped) {
+            return;
+        }
+
+        if ($this->next != null) {
+            $this->curelt = $this->next;
+            $this->next = null;
+        } else {
+            if ($this->source->last()) {
+                $this->over = true;
+                return;
+            }
+            $this->curelt = $this->source->next();
+        }
+
+        if ($this->pos == 0) {
+            $this->val = call_user_func($this->callback, $this->curelt);
+            $this->curval = $this->val;
+        } else {
+            $this->curval = call_user_func($this->callback, $this->curelt);
+        }
+
+        $this->stepped = true;
+    }
+
+    public function next()
+    {
+        if ($this->over) {
+            return null;
+        }
+
+        $this->_step();
+
+        if ($this->over) {
+            return null;
+        }
+
+        ++$this->pos;
+        $this->stepped = false;
+
+        if ($this->val == $this->curval) {
+            return $this->curelt;
+        }
+
+        $this->parent->setNext($this->curelt);
+        $this->over = true;
+        return null;
+    }
+
+    /** This will always be a too big number, but the actual result can't be easily computed
+     */
+    public function total()
+    {
+        return $this->source->total();
+    }
+
+    public function last()
+    {
+        if ($this->over) {
+            return true;
+        }
+        $this->_step();
+        return $this->over || ($this->val != $this->curval);
+    }
+
+    public function first()
+    {
+        return $this->pos == 1;
+    }
+
+}
+
+/** Builds an iterator over a set of iterators, from which one is given as 'master';
+ * The arguments are :
+ *  - An array of iterators, to iterate simultaneously
+ *  - An array of callbacks (one attached to each iterator), or a single callback (to
+ *      use for all iterators)
+ *  - The id of the 'master' iterator
+ *
+ * This ParallelIterator will iterate over the iterators, and, at each
+ * step of the master iterator, it will apply the callbacks to the corresponding
+ * iterators and return the values of the "slaves" for which the callback returned the
+ * same value as the callback of the master.
+ *
+ * The callback should compute some kind of index, and never return the same value
+ * twice for a given iterator
+ *
+ * It is assumed that, if the callback for a slave doesn't have the same value
+ * as the value for the master, this means that there is a "hole" in the values
+ * of that slave.
+ *
+ * Example :
+ *   - The callback is 'get the first cell'
+ *   - The master is :
+ *      [0, 1], [1, 13], [2, 42]
+ *   - The first slave (slave1) is :
+ *      [0, 'a'], [2, 'b']
+ *   - The second slave (slave2) is :
+ *      [1, 42], [2, 0]
+ * The resulting iterator would yield :
+ * - array(master => [0, 1], slave1 => [0, 'a'], slave2 => null)
+ * - array(master => [1, 13], slave1 => null, slave2 => [1, 42])
+ * - array(master => [2, 42], slave1 => [1, 'b'], slave2 => [2, 0])
+ */
+class PlParallelIterator implements PlIterator
+{
+    private $iterators;
+    private $ids;
+    private $callbacks;
+
+    private $master_id;
+    private $master;
+
+    private $over = array();
+    private $stepped = array();
+    private $current_elts = array();
+    private $callback_res = array();
+
+    public function __construct(array $iterators, $callbacks, $master)
+    {
+        $this->iterators = $iterators;
+        $this->master_id = $master;
+        $this->master = $iterators[$master];
+
+        $this->ids = array_keys($iterators);
+
+        $v = array_values($callbacks);
+        if (is_array($v[0])) {
+            $this->callbacks = $callbacks;
+        } else {
+            $this->callbacks = array();
+            foreach ($this->ids as $id) {
+                $this->callbacks[$id] = $callbacks;
+            }
+        }
+
+        foreach ($this->ids as $id) {
+            $this->stepped[$id] = false;
+            $this->over[$id] = false;
+            $this->current_elts[$id] = null;
+            $this->callback_res[$id] = null;
+        }
+    }
+
+    private function step($id)
+    {
+        if ($this->stepped[$id]) {
+            return;
+        }
+
+        // Don't do anything if the iterator is at its end
+        if ($this->over[$id]) {
+            $this->stepped[$id] = true;
+            return;
+        }
+
+        $it = $this->iterators[$id];
+        $nxt = $it->next();
+        $this->stepped[$id] = true;
+        if ($nxt === null) {
+            $this->over[$id] = true;
+            $this->current_elts[$id] = null;
+            $this->callback_res[$id] = null;
+            return;
+        }
+        $res = call_user_func($this->callbacks[$id], $nxt);
+        $this->current_elts[$id] = $nxt;
+        $this->callback_res[$id] = $res;
+    }
+
+    private function stepAll()
+    {
+        foreach ($this->ids as $id) {
+            $this->step($id);
+        }
+    }
+
+    public function next()
+    {
+        $this->stepAll();
+        if ($this->current_elts[$this->master_id] === null) {
+            return null;
+        }
+
+        $res = array();
+        $master = $this->callback_res[$this->master_id];
+        foreach ($this->ids as $id) {
+            if ($this->callback_res[$id] == $master) {
+                $res[$id] = $this->current_elts[$id];
+                $this->stepped[$id] = false;
+            } else {
+                $res[$id] = null;
+            }
+        }
+
+        return $res;
+    }
+
+    public function first()
+    {
+        return $this->master->first();
+    }
+
+    public function total()
+    {
+        return $this->master->total();
+    }
+
+    public function last()
+    {
+        return $this->master->last();
+    }
+}
+
+// Wrapper class for 'arrayValueCallback' (get field $key of the given array)
+class _GetArrayValueCallback
+{
+    private $key;
+
+    public function __construct($key)
+    {
+        $this->key = $key;
+    }
+
+    public function get(array $arr)
+    {
+        if (array_key_exists($this->key, $arr)) {
+            return $arr[$this->key];
+        } else {
+            return null;
+        }
+    }
+}
+
+// Wrapper class for 'objectPropertyCallback' (get property ->$blah of the given object)
+class _GetObjectPropertyCallback
+{
+    private $property;
+
+    public function __construct($property)
+    {
+        $this->property = $property;
+    }
+
+    public function get($obj)
+    {
+        $p = $this->property;
+        return @$obj->$p;
+    }
+}
+
+// Wrapper class to build a SPL iterator from a PlIterator
+class SPLIterator implements Iterator
+{
+    private $it;
+    private $pos;
+    private $value;
+
+    public function __construct(PlIterator $it)
+    {
+        $this->it = $it;
+        $this->pos = 0;
+        $this->value = $this->it->next();
+    }
+
+    public function rewind()
+    {
+        if ($this->pos != 0) {
+            throw new Exception("Rewind not supported on this iterator");
+        }
+    }
+
+    public function current()
+    {
+        return $this->value;
+    }
+
+    public function key()
+    {
+        return $this->pos;
+    }
+
+    public function next()
+    {
+        ++$this->pos;
+        $this->value = $this->it->next();
+    }
+
+    public function valid()
+    {
+        return !!$this->value;
+    }
+}
+
+// vim:set et sw=4 sts=4 sws=4 foldmethod=marker fenc=utf-8:
 ?>