[libgee] Add Traversable.tee

[Maciej Marcin Piechotka <mpiechotka src gnome org>]

commit 7259a93a0a9421e1f4fca788a008ef3f143651f1
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Thu Jul 25 18:11:36 2013 +0200

    Add Traversable.tee

 gee/Makefile.am      |    1 +
 gee/teeiterator.vala |  103 ++++++++++++++++++++++++++++++++++++++++++++++++++
 gee/traversable.vala |   55 ++++++++++++++++++++++++++-
 3 files changed, 158 insertions(+), 1 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 3974014..7094e57 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -71,6 +71,7 @@ libgee_0_8_la_SOURCES = \
        sortedset.vala \
        streamiterator.vala \
        task.vala \
+       teeiterator.vala \
        timsort.vala \
        traversable.vala \
        treemap.vala \
diff --git a/gee/teeiterator.vala b/gee/teeiterator.vala
new file mode 100644
index 0000000..1c2c05f
--- /dev/null
+++ b/gee/teeiterator.vala
@@ -0,0 +1,103 @@
+/* teeiterator.vala
+ *
+ * Copyright (C) 2013  Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
+ *
+ * Author:
+ *     Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+internal class Gee.TeeIterator<G> : Object, Traversable<G>, Iterator<G> {
+       internal TeeIterator (Node<G>? head, bool valid) {
+               _head = head;
+               _valid = valid;
+       }
+
+       public bool foreach (ForallFunc<G> f) {
+               Node<G> head = (owned)_head;
+               bool valid = _valid;
+               if (valid) {
+                       if (!f (head._data.get ())) {
+                               return false;
+                       }
+               }
+               unowned Node<G>? next_head = head._next.value;
+               while (next_head != null) {
+                       head = next_head;
+                       valid = true;
+                       if (!f (head._data.get ())) {
+                               _head = (owned)head;
+                               _valid = valid;
+                               return false;
+                       }
+               }
+               _head = (owned)head;
+               _valid = valid;
+               return true;
+       }
+
+       public bool next () {
+               unowned Node<G>? next = _head._next.value;
+               if (next != null) {
+                       _head = next;
+                       _valid = true;
+                       return true;
+               } else {
+                       return false;
+               }
+       }
+
+       public bool has_next () {
+               return _head._next.get () != null;
+       }
+
+       public G get () {
+               return _head._data.get ();
+       }
+
+       public void remove () {
+               assert_not_reached ();
+       }
+
+       public bool valid { get { return _valid; } }
+
+       public bool read_only { get { return true; } }
+
+       private Node<G> _head;
+       private bool _valid;
+
+       internal static Lazy<Node<G>?> create_nodes<G> (Iterator<G> iterator, Lazy<G> dependent) {
+               return new Lazy<Node<G>?>(() => {
+                       dependent.eval ();
+                       if (!iterator.next ())
+                               return null;
+                       Lazy<G> data = new Lazy<G> (() => {return iterator.get ();});
+                       Lazy<Node<G>?> next = create_nodes<G> (iterator, data);
+                       return new Node<G> ((owned)data, (owned)next);
+               });
+       }
+
+       internal class Node<G> {
+               public Node (owned Lazy<G> data, owned Lazy<Node<G>?> next) {
+                       _data = (owned)data;
+                       _next = (owned)next;
+               }
+               public Lazy<G> _data;
+               public Lazy<Node<G>?> _next;
+       }
+
+}
+
diff --git a/gee/traversable.vala b/gee/traversable.vala
index 4c514fc..eb34d0d 100644
--- a/gee/traversable.vala
+++ b/gee/traversable.vala
@@ -112,7 +112,7 @@ public interface Gee.Traversable<G> : Object {
                unowned Iterator<G>? self;
                unowned Iterable<G>? iself;
                // Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
-               if ((self = this as Iterator<G>) != null) { 
+               if ((self = this as Iterator<G>) != null) {
                        return new StreamIterator<A, G> (self, (owned)f);
                } else if ((iself = this as Iterable<G>) != null) {
                        return iself.iterator().stream<A> ((owned) f);
@@ -375,6 +375,59 @@ public interface Gee.Traversable<G> : Object {
                });
        }
 
+       /**
+        * Splits the traversable into multiple ones, caching the result if needed.
+        *
+        * Note: In { link Iterator} implementation using the parent iterator is
+        *   not allowed. However if any of the forked iterators { link next}
+        *   return false then it is treated as if the parent iterator
+        *   { link next} returned false.
+        *
+        * Note: The returned arrey might contain parent iterator if it is allowed
+        *   by implementation. For example the iteration over collection does
+        *   not need to generate and cache the results.
+        *
+        * Note: the resulting iterators does not need to be thread safe.
+        *
+        * @param forks Number of iterators in array
+        * @returns An array with created iterators
+        * @since 0.11.5
+        */
+       public Iterator<G>[] tee (uint forks) {
+               unowned Iterator<G>? self;
+               unowned Iterable<G>? iself;
+               // Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
+               if ((self = this as Iterator<G>) != null) {
+                       if (forks == 0) {
+                               return new Iterator<G>[0];
+                       } else if (forks == 1) {
+                               return new Iterator<G>[1]{self};
+                       } else {
+                               Iterator<G>[] result = new Iterator<G>[forks];
+                               Lazy<G>? data;
+                               bool is_valid = self.valid;
+                               if (is_valid) {
+                                       data = new Lazy<G>(() => {return self.get ();});
+                               } else {
+                                       data = new Lazy<G>.from_value (null);
+                               }
+                               var head = new TeeIterator.Node<G> (data, TeeIterator.create_nodes<G> (self, 
data));
+                               for (uint i = 0; i < forks; i++) {
+                                       result[i] = new TeeIterator<G> (head, is_valid);
+                               }
+                               return result;
+                       }
+               } else if ((iself = this as Iterable<G>) != null) {
+                       var result = new Iterator<G>[forks];
+                       for (uint i = 0; i < forks; i++) {
+                               result[i] = iself.iterator ();
+                       }
+                       return result;
+               } else {
+                       assert_not_reached ();
+               }
+       }
+
        public enum Stream {
                YIELD,
                CONTINUE,