[libgee] Export the function part of interface into Traversable

[Maciej Marcin Piechotka <mpiechotka src gnome org>]

commit a67484dafa5a4a40af9e206eefd01d28551c1e2e
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Fri Jul 22 02:07:18 2011 +0100

    Export the function part of interface into Traversable

 gee/Makefile.am             |    1 +
 gee/abstractmultiset.vala   |   19 ++++-
 gee/arraylist.vala          |    6 +-
 gee/hashmap.vala            |   77 +++++++++++++++++-
 gee/hashset.vala            |    6 +-
 gee/iterator.vala           |  185 +++++-------------------------------------
 gee/linkedlist.vala         |    6 +-
 gee/priorityqueue.vala      |   22 ++---
 gee/readonlycollection.vala |    5 +-
 gee/traversable.vala        |  165 ++++++++++++++++++++++++++++++++++++++
 gee/treemap.vala            |  113 ++++++++++++++++++++++++--
 gee/treeset.vala            |   19 ++++-
 gee/unfolditerator.vala     |    6 +-
 13 files changed, 435 insertions(+), 195 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index f5a0a81..98e14b8 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -48,6 +48,7 @@ libgee_la_SOURCES = \
 	sortedmap.vala \
 	sortedset.vala \
 	timsort.vala \
+	traversable.vala \
 	treemap.vala \
 	treemultimap.vala \
 	treemultiset.vala \
diff --git a/gee/abstractmultiset.vala b/gee/abstractmultiset.vala
index 6b4955e..99d1540 100644
--- a/gee/abstractmultiset.vala
+++ b/gee/abstractmultiset.vala
@@ -92,7 +92,7 @@ public abstract class Gee.AbstractMultiSet<G> : AbstractCollection<G>, MultiSet<
 		_nitems = 0;
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 		private AbstractMultiSet<G> _set;
 
 		private MapIterator<G, int> _iter;
@@ -148,5 +148,22 @@ public abstract class Gee.AbstractMultiSet<G> : AbstractCollection<G>, MultiSet<
 				return ! _removed && _iter.valid;
 			}
 		}
+
+		public void foreach (ForallFunc<G> f) {
+			if(!_removed && _iter.valid)
+				f(_iter.get_key());
+			if(_iter.valid)
+				for(int i = _pending - 1; i > 0; --i)
+					f(_iter.get_key());
+			while(_iter.next())
+				for(int i = _iter.get_value(); i > 0; --i)
+					f(_iter.get_key());
+			_pending = 0;
+			_removed = false;
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
 	}
 }
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index 2cfe751..33cf575 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -256,7 +256,7 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 		_items.resize (value);
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G> {
+	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G> {
 		private ArrayList<G> _list;
 		private int _index = -1;
 		private bool _removed = false;
@@ -391,6 +391,10 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 			}
 			_index = _list._size;
 		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
 	}
 }
 
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index cf258c4..fd1f6f5 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -474,7 +474,7 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 
 	private abstract class NodeIterator<K,V> : Object {
 		protected HashMap<K,V> _map;
-		private int _index = -1;
+		protected int _index = -1;
 		protected weak Node<K,V> _node;
 		protected weak Node<K,V> _next;
 
@@ -524,7 +524,7 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
-	private class KeyIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
+	private class KeyIterator<K,V> : NodeIterator<K,V>, Traversable<K>, Iterator<K> {
 		public KeyIterator (HashMap map) {
 			base (map);
 		}
@@ -538,6 +538,29 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		public void remove () {
 			assert_not_reached ();
 		}
+
+		public void foreach(ForallFunc<K> f) {
+			if (_node != null) {
+				f(_node.key);
+				if(_next == null)
+					_next = _node.next;
+			}
+			do {
+				while(_next != null) {
+					_node = _next;
+					f(_node.key);
+					_next = _next.next;
+				}
+                                if (_index + 1 < _map._array_size)
+					_next = _map._nodes[++_index];
+				else
+					break;
+			} while(true);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, K> f) {
+			return Gee.Iterator.stream_impl<K, A>(this, (owned)f);
+		}
 	}
 
 	private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V> {
@@ -586,7 +609,7 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
-	private class ValueIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
+	private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Iterator<V> {
 		public ValueIterator (HashMap map) {
 			base (map);
 		}
@@ -600,9 +623,32 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		public void remove () {
 			assert_not_reached ();
 		}
+
+		public void foreach(ForallFunc<V> f) {
+			if (_node != null) {
+				f(_node.value);
+				if(_next == null)
+					_next = _node.next;
+			}
+			do {
+				while(_next != null) {
+					_node = _next;
+					f(_node.value);
+					_next = _next.next;
+				}
+                                if (_index + 1 < _map._array_size)
+					_next = _map._nodes[++_index];
+				else
+					break;
+			} while(true);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, V> f) {
+			return Gee.Iterator.stream_impl<V, A>(this, (owned)f);
+		}
 	}
 
-	private class EntryIterator<K,V> : NodeIterator<K,V>, Iterator<Map.Entry<K,V>> {
+	private class EntryIterator<K,V> : NodeIterator<K,V>, Traversable<Map.Entry<K,V>>, Iterator<Map.Entry<K,V>> {
 		public EntryIterator (HashMap map) {
 			base (map);
 		}
@@ -616,6 +662,29 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		public void remove () {
 			assert_not_reached ();
 		}
+
+		public void foreach(ForallFunc<Map.Entry<K,V>> f) {
+			if (_node != null) {
+				f(Entry<K,V>.entry_for<K,V> (_node));
+				if(_next == null)
+					_next = _node.next;
+			}
+			do {
+				while(_next != null) {
+					_node = _next;
+					f(Entry<K,V>.entry_for<K,V> (_node));
+					_next = _next.next;
+				}
+                                if (_index + 1 < _map._array_size)
+					_next = _map._nodes[++_index];
+				else
+					break;
+			} while(true);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<Map.Entry<K,V>, A> f) {
+			return Gee.Iterator.stream_impl<Map.Entry<K,V>, A>(this, (owned)f);
+		}
 	}
 }
 
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 98ae682..debbe17 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -213,7 +213,7 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 		}
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 		private HashSet<G> _set;
 		private int _index = -1;
 		private weak Node<G> _node;
@@ -294,6 +294,10 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 				}
 			}
 		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
 	}
 }
 
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 0427654..f3b74d1 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -24,14 +24,6 @@
  * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
  */
 
-namespace Gee {
-	public delegate A FoldFunc<A, G> (owned G g, owned A a);
-	public delegate void ForallFunc<G> (owned G g);
-	public delegate Lazy<A>? UnfoldFunc<A> ();
-	public delegate Iterator.Stream StreamFunc<A, G> (Iterator.Stream state, owned G? g, out Lazy<A>? lazy);
-	public delegate A MapFunc<A, G> (owned G g);
-}
-
 /**
  * An iterator over a collection.
  *
@@ -43,7 +35,7 @@ namespace Gee {
  * { link remove} are defined and both will fail. After the next call to
  * { link next}, they will be defined again.
  */
-public interface Gee.Iterator<G> : Object {
+public interface Gee.Iterator<G> : Object, Traversable<G> {
 	/**
 	 * Advances to the next element in the iteration.
 	 *
@@ -84,120 +76,56 @@ public interface Gee.Iterator<G> : Object {
 	 * of iterator may cache it.
 	 */
 	public abstract bool read_only { get; }
-	
-	/**
-	 * Standard aggragation function.
-	 *
-	 * It takes a function, seed and first element, returns the new seed and
-	 * progress to next element when the operation repeats.
-	 *
-	 * Operation moves the iterator to last element in iteration. If iterator
-	 * points at some element it will be included in iteration.
-	 *
-	 * Note: Default implementation uses { link foreach}.
-	 */
-	public virtual A fold<A> (FoldFunc<A, G> f, owned A seed)
-	{
-		this.foreach ((item) => {seed = f ((owned) item, (owned) seed);});
-		return (owned) seed;
-	}
-	
-	/**
-	 * Apply function to each element returned by iterator. 
-	 *
-	 * Operation moves the iterator to last element in iteration. If iterator
-	 * points at some element it will be included in iteration.
-	 */
-	public new virtual void foreach (ForallFunc<G> f) {
-		if (valid)
-			f (get ());
-		while (next ())
-			f (get ());
-	}
-
 
-	/**
-	 * Stream function is an abstract function allowing writing many
-	 * operations.
-	 *
-	 * The stream function accepts three parameter:
-	 *
-	 *   1. state. It is usually the last returned value from function but
-	 *      it may be Stream.END when the previous value was Stream.CONTINUE
-	 *      and threre was no next element.
-	 *   2. input. It is valid only if first argument is Stream.CONTINUE
-	 *   3. output. It is valid only if result is Stream.YIELD
-	 *
-	 * It may return one of 3 results:
-	 *
-	 *   1. Stream.YIELD. It means that value was yielded and can be passed
-	 *      to outgoint iterator
-	 *   2. Stream.CONTINUE. It means that the function needs to be rerun
-	 *      with next element (or Stream.END if it is end of stream). If
-	 *      the state argument is Stream.END the function MUST NOT return
-	 *      this value.
-	 *   3. Stream.END. It means that the last argument was yielded.
-	 *
-	 * If the function yields the value immidiatly then the returning iterator
-	 * is { link valid} and points to this value as well as in case when the
-	 * parent iterator is { link valid} and function yields after consuming
-	 * 1 input. In other case returned iterator is invalid.
-	 *
-	 * Usage of the parent is invalid before the { link next} or
-	 * { link has_next} returns false and the value will be force-evaluated.
-	 *
-	 * @param f function generating stream
-	 * @return iterator containing values yielded by stream
-	 */
-	public virtual Iterator<A> stream<A> (owned StreamFunc<A, G> f_) {
-		Stream str;
+	public static Iterator<A> stream_impl<G, A> (Iterator<G> self, owned StreamFunc<A, G> f_) {
+		Traversable.Stream str;
 		Lazy<A>? initial = null;
 		bool need_next = true;
-		StreamFunc<A, G> f = (owned)f_;
-		str = f (Stream.YIELD, null, out initial);
+		StreamFunc<G, A> f = (owned)f_;
+		str = f (Traversable.Stream.YIELD, null, out initial);
 		switch (str) {
-		case Stream.CONTINUE:
-			if (valid) {
-				str = f (Stream.CONTINUE, get (), out initial);
+		case Traversable.Stream.CONTINUE:
+			if (self.valid) {
+				str = f (Traversable.Stream.CONTINUE, self.get (), out initial);
 				switch (str) {
-				case Stream.YIELD:
-				case Stream.CONTINUE:
+				case Traversable.Stream.YIELD:
+				case Traversable.Stream.CONTINUE:
 					break;
-				case Stream.END:
+				case Traversable.Stream.END:
 					return unfold<A> (() => {return null;});
 				default:
 					assert_not_reached ();
 				}
 			}
 			break;
-		case Stream.YIELD:
-			if (valid)
+		case Traversable.Stream.YIELD:
+			if (self.valid)
 				need_next = false;
 			break;
-		case Stream.END:
+		case Traversable.Stream.END:
 			return unfold<A> (() => {return null;});
 		default:
 			assert_not_reached ();
 		}
 		return unfold<A> (() => {
 			Lazy<A>? val;
-			str = f (Stream.YIELD, null, out val);
-			while (str == Stream.CONTINUE) {
+			str = f (Traversable.Stream.YIELD, null, out val);
+			while (str == Traversable.Stream.CONTINUE) {
 				if (need_next) {
-					if (!next ()) {
-						str = f (Stream.END, null, out val);
-						assert (str != Stream.CONTINUE);
+					if (!self.next ()) {
+						str = f (Traversable.Stream.END, null, out val);
+						assert (str != Traversable.Stream.CONTINUE);
 						break;
 					}
 				} else {
 					need_next = true;
 				}
-				str = f (Stream.CONTINUE, get (), out val);
+				str = f (Traversable.Stream.CONTINUE, self.get (), out val);
 			}
 			switch (str) {
-			case Stream.YIELD:
+			case Traversable.Stream.YIELD:
 				return val;
-			case Stream.END:
+			case Traversable.Stream.END:
 				return null;
 			default:
 				assert_not_reached ();
@@ -206,75 +134,6 @@ public interface Gee.Iterator<G> : Object {
 	}
 
 	/**
-	 * Maps the iterator. It produces iterator that is get by applying
-	 * map function to the values of this iterator.
-	 *
-	 * The value is lazy evaluated but previous value is guaranteed to be
-	 * evaluated before { link next} call.
-	 *
-	 * If the current iterator is { link valid} so is the resulting. Using
-	 * the iterator after this called is not allowed.
-	 *
-	 * @param f Mapping function
-	 * @return Iterator listing mapped value
-	 */
-	public virtual Iterator<A> map<A> (MapFunc<A, G> f) {
-		return stream<A>((state, item, out val) => {
-			switch (state) {
-			case Stream.YIELD:
-				return Stream.CONTINUE;
-			case Stream.CONTINUE:
-				val = new Lazy<A>(() => {return (f ((owned)item));});
-				return Stream.YIELD;
-			case Stream.END:
-				return Stream.END;
-			default:
-				assert_not_reached ();
-			}
-		});
-	}
-
-	/**
-	 * Creates a new iterator that is initialy pointing to seed. Then
-	 * subsequent values are obtained after applying the function to previous
-	 * value and the current item.
-	 *
-	 * The resulting iterator is always valid and it contains the seed value.
-	 *
-	 * @param f Folding function
-	 * @param seed original seed value
-	 * @return Iterator containing values of subsequent values of seed
-	 */
-	public virtual Iterator<A> scan<A> (FoldFunc<A, G> f, owned A seed) {
-		bool seed_emitted = false;
-		return stream<A>((state, item, out val) => {
-			switch (state) {
-			case Stream.YIELD:
-				if (seed_emitted) {
-					return Stream.CONTINUE;
-				} else {
-					val = new Lazy<A>.from_value (seed);
-					seed_emitted = true;
-					return Stream.YIELD;
-				}
-			case Stream.CONTINUE:
-				val = new Lazy<A> (() => {seed = f ((owned)item, (owned) seed); return seed;});
-				return Stream.YIELD;
-			case Stream.END:
-				return Stream.END;
-			default:
-				assert_not_reached ();
-			}
-		});
-	}
-
-	public enum Stream {
-		YIELD,
-		CONTINUE,
-		END
-	}
-
-	/**
 	 * Create iterator from unfolding function. The lazy value is
          * force-evaluated before progressing to next element.
          *
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index 8ba00ba..4c6f87f 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -413,7 +413,7 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 		}
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G> {
+	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G>, ListIterator<G> {
 		private bool started = false;
 		private bool removed = false;
 		private unowned Node<G>? position;
@@ -612,6 +612,10 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 			}
 			position = _list._tail;
 		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
 	}
 
 	private unowned Node<G>? _get_node_at (int index) {
diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala
index 93c41d5..f65df83 100644
--- a/gee/priorityqueue.vala
+++ b/gee/priorityqueue.vala
@@ -912,7 +912,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 		}
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 		private PriorityQueue<G> queue;
 		private bool started = false;
 		private bool from_type1_children = false;
@@ -1027,19 +1027,15 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 			}
 		}
 
-		/*public void foreach (ForallFunc<G> f) {
-			assert (stamp == queue._stamp);
-			if (position != null)
+		public void foreach (ForallFunc<G> f) {
+			if (valid)
 				f (position.data);
-			else if (_next != null)
-				removed = false;
-			if (_next == null)
-				_has_next ();
-			while (_next != null) {
-				position = _next;
+			while (next ())
 				f (position.data);
-				_has_next ();
-			}
-		}*/
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
 	}
 }
diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala
index 82a41b6..efaaf84 100644
--- a/gee/readonlycollection.vala
+++ b/gee/readonlycollection.vala
@@ -143,7 +143,7 @@ internal class Gee.ReadOnlyCollection<G> : Object, Iterable<G>, Collection<G> {
 		return _collection.to_array ();
 	}
 
-	protected class Iterator<G> : Object, Gee.Iterator<G> {
+	protected class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 		protected Gee.Iterator<G> _iter;
 
 		public Iterator (Gee.Iterator<G> iterator) {
@@ -182,6 +182,9 @@ internal class Gee.ReadOnlyCollection<G> : Object, Iterable<G>, Collection<G> {
 			_iter.foreach (f);
 		}
 
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
 	}
 
 	public virtual Collection<G> read_only_view {
diff --git a/gee/traversable.vala b/gee/traversable.vala
new file mode 100644
index 0000000..016130e
--- /dev/null
+++ b/gee/traversable.vala
@@ -0,0 +1,165 @@
+/* traversable.vala
+ *
+ * Copyright (C) 2011  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>
+ */
+
+
+
+namespace Gee {
+	public delegate A FoldFunc<A, G> (owned G g, owned A a);
+	public delegate void ForallFunc<G> (owned G g);
+	public delegate Lazy<A>? UnfoldFunc<A> ();
+	public delegate Traversable.Stream StreamFunc<G, A> (Traversable.Stream state, owned G? g, out Lazy<A>? lazy);
+	public delegate A MapFunc<A, G> (owned G g);
+}
+
+public interface Gee.Traversable<G> : Object
+{	
+	/**
+	 * Apply function to each element returned by iterator. 
+	 *
+	 * Operation moves the iterator to last element in iteration. If iterator
+	 * points at some element it will be included in iteration.
+	 */
+	public new abstract void foreach (ForallFunc<G> f);
+
+	/**
+	 * Stream function is an abstract function allowing writing many
+	 * operations.
+	 *
+	 * The stream function accepts three parameter:
+	 *
+	 *   1. state. It is usually the last returned value from function but
+	 *      it may be Stream.END when the previous value was Stream.CONTINUE
+	 *      and threre was no next element.
+	 *   2. input. It is valid only if first argument is Stream.CONTINUE
+	 *   3. output. It is valid only if result is Stream.YIELD
+	 *
+	 * It may return one of 3 results:
+	 *
+	 *   1. Stream.YIELD. It means that value was yielded and can be passed
+	 *      to outgoint iterator
+	 *   2. Stream.CONTINUE. It means that the function needs to be rerun
+	 *      with next element (or Stream.END if it is end of stream). If
+	 *      the state argument is Stream.END the function MUST NOT return
+	 *      this value.
+	 *   3. Stream.END. It means that the last argument was yielded.
+	 *
+	 * If the function yields the value immidiatly then the returning iterator
+	 * is { link valid} and points to this value as well as in case when the
+	 * parent iterator is { link valid} and function yields after consuming
+	 * 1 input. In other case returned iterator is invalid.
+	 *
+	 * Usage of the parent is invalid before the { link next} or
+	 * { link has_next} returns false and the value will be force-evaluated.
+	 *
+	 * @param f function generating stream
+	 * @return iterator containing values yielded by stream
+	 */
+	public abstract Iterator<A> stream<A> (owned StreamFunc<G, A> f_);
+
+	/**
+	 * Standard aggragation function.
+	 *
+	 * It takes a function, seed and first element, returns the new seed and
+	 * progress to next element when the operation repeats.
+	 *
+	 * Operation moves the iterator to last element in iteration. If iterator
+	 * points at some element it will be included in iteration.
+	 *
+	 * Note: Default implementation uses { link foreach}.
+	 */
+	public virtual A fold<A> (FoldFunc<A, G> f, owned A seed)
+	{
+		this.foreach ((item) => {seed = f ((owned) item, (owned) seed);});
+		return (owned) seed;
+	}
+
+	/**
+	 * Maps the iterator. It produces iterator that is get by applying
+	 * map function to the values of this iterator.
+	 *
+	 * The value is lazy evaluated but previous value is guaranteed to be
+	 * evaluated before { link next} call.
+	 *
+	 * If the current iterator is { link valid} so is the resulting. Using
+	 * the iterator after this called is not allowed.
+	 *
+	 * @param f Mapping function
+	 * @return Iterator listing mapped value
+	 */
+	public virtual Iterator<A> map<A> (MapFunc<A, G> f) {
+		return stream<A>((state, item, out val) => {
+			switch (state) {
+			case Stream.YIELD:
+				return Stream.CONTINUE;
+			case Stream.CONTINUE:
+				val = new Lazy<A>(() => {return (f ((owned)item));});
+				return Stream.YIELD;
+			case Stream.END:
+				return Stream.END;
+			default:
+				assert_not_reached ();
+			}
+		});
+	}
+
+	/**
+	 * Creates a new iterator that is initialy pointing to seed. Then
+	 * subsequent values are obtained after applying the function to previous
+	 * value and the current item.
+	 *
+	 * The resulting iterator is always valid and it contains the seed value.
+	 *
+	 * @param f Folding function
+	 * @param seed original seed value
+	 * @return Iterator containing values of subsequent values of seed
+	 */
+	public virtual Iterator<A> scan<A> (FoldFunc<A, G> f, owned A seed) {
+		bool seed_emitted = false;
+		return stream<A>((state, item, out val) => {
+			switch (state) {
+			case Stream.YIELD:
+				if (seed_emitted) {
+					return Stream.CONTINUE;
+				} else {
+					val = new Lazy<A>.from_value (seed);
+					seed_emitted = true;
+					return Stream.YIELD;
+				}
+			case Stream.CONTINUE:
+				val = new Lazy<A> (() => {seed = f ((owned)item, (owned) seed); return seed;});
+				return Stream.YIELD;
+			case Stream.END:
+				return Stream.END;
+			default:
+				assert_not_reached ();
+			}
+		});
+	}
+
+	public enum Stream {
+		YIELD,
+		CONTINUE,
+		END
+	}
+
+}
+
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 4081528..8b60c34 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -1624,7 +1624,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 				return iterator != null && iterator.valid;
 			}
 		}
-		
+
 		protected virtual NodeIterator<K,V> iterator_pointing_at (Node<K,V> node) {
 			return new NodeIterator<K,V>.pointing (_map, node);
 		}
@@ -1634,7 +1634,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 		protected NodeIterator<K,V>? iterator = null;
 	}
 
-	private class KeyIterator<K,V> : NodeIterator<K, V>, Gee.Iterator<K>, BidirIterator<K> {
+	private class KeyIterator<K,V> : NodeIterator<K, V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
 		public KeyIterator (TreeMap<K,V> map) {
 			base (map);
 		}
@@ -1648,9 +1648,31 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 			assert (current != null);
 			return current.key;
 		}
+
+		public void foreach (ForallFunc<K> f) {
+			if (current != null) {
+				f (current.key);
+				current = current.next;
+			} else if (_next == null) {
+				current = _map.first;
+				started = true;
+			} else {
+				current = _next;
+				if (current != null) {
+					_next = null;
+					_prev = null;
+				}
+			}
+			for (; current != null; current = current.next)
+				f (current.key);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, K> f) {
+			return Gee.Iterator.stream_impl<K, A>(this, (owned)f);
+		}
 	}
 
-	private class SubKeyIterator<K,V> : SubNodeIterator<K,V>, Gee.Iterator<K>, BidirIterator<K> {
+	private class SubKeyIterator<K,V> : SubNodeIterator<K,V>, Traversable<K>, Gee.Iterator<K>, BidirIterator<K> {
 		public SubKeyIterator (TreeMap<K,V> map, Range<K,V> range) {
 			base (map, range);
 		}
@@ -1663,9 +1685,20 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 			assert (valid);
 			return iterator.current.key;
 		}
+
+		public void foreach (ForallFunc<K> f) {
+			if (valid)
+				f (iterator.current.key);
+			while (iterator.next ())
+				f (iterator.current.key);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, K> f) {
+			return Gee.Iterator.stream_impl<K, A>(this, (owned)f);
+		}
 	}
 
-	private class ValueIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
+	private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
 		public ValueIterator (TreeMap<K,V> map) {
 			base (map);
 		}
@@ -1679,9 +1712,31 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 			assert (valid);
 			return current.value;
 		}
+
+		public void foreach (ForallFunc<V> f) {
+			if (current != null) {
+				f (current.key);
+				current = current.next;
+			} else if (_next == null) {
+				current = _map.first;
+				started = true;
+			} else {
+				current = _next;
+				if (current != null) {
+					_next = null;
+					_prev = null;
+				}
+			}
+			for (; current != null; current = current.next)
+				f (current.key);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, V> f) {
+			return Gee.Iterator.stream_impl<V, A>(this, (owned)f);
+		}
 	}
 
-	private class SubValueIterator<K,V> : SubNodeIterator<K,V>, Gee.Iterator<K>, BidirIterator<K> {
+	private class SubValueIterator<K,V> : SubNodeIterator<K,V>, Traversable<V>, Gee.Iterator<V>, BidirIterator<V> {
 		public SubValueIterator (TreeMap<K,V> map, Range<K,V> range) {
 			base (map, range);
 		}
@@ -1694,9 +1749,20 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 			assert (valid);
 			return iterator.current.value;
 		}
+
+		public void foreach (ForallFunc<V> f) {
+			if (valid)
+				f (iterator.current.key);
+			while (iterator.next ())
+				f (iterator.current.key);
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, V> f) {
+			return Gee.Iterator.stream_impl<V, A>(this, (owned)f);
+		}
 	}
 
-	private class EntryIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
+	private class EntryIterator<K,V> : NodeIterator<K,V>, Traversable<Map.Entry<K, V>>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
 		public EntryIterator (TreeMap<K,V> map) {
 			base (map);
 		}
@@ -1714,9 +1780,31 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 		public new void remove () {
 			unset ();
 		}
+
+		public void foreach (ForallFunc<Map.Entry<K, V>> f) {
+			if (current != null) {
+				f (Entry.entry_for<K,V> (current));
+				current = current.next;
+			} else if (_next == null) {
+				current = _map.first;
+				started = true;
+			} else {
+				current = _next;
+				if (current != null) {
+					_next = null;
+					_prev = null;
+				}
+			}
+			for (; current != null; current = current.next)
+				f (Entry.entry_for<K,V> (current));
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<Map.Entry<K, V>, A> f) {
+			return Gee.Iterator.stream_impl<Map.Entry<K, V>, A>(this, (owned)f);
+		}
 	}
 
-	private class SubEntryIterator<K,V> : SubNodeIterator<K,V>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
+	private class SubEntryIterator<K,V> : SubNodeIterator<K,V>, Traversable<Map.Entry<K, V>>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
 		public SubEntryIterator (TreeMap<K,V> map, Range<K,V> range) {
 			base (map, range);
 		}
@@ -1733,6 +1821,17 @@ public class Gee.TreeMap<K,V> : Gee.AbstractSortedMap<K,V> {
 		public new void remove () {
 			unset ();
 		}
+
+		public void foreach (ForallFunc<Map.Entry<K, V>> f) {
+			if (valid)
+				f (Entry.entry_for<K,V> (iterator.current));
+			while (iterator.next ())
+				f (Entry.entry_for<K,V> (iterator.current));
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<Map.Entry<K, V>, A> f) {
+			return Gee.Iterator.stream_impl<Map.Entry<K, V>, A>(this, (owned)f);
+		}
 	}
 	
 	private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V>, BidirMapIterator<K,V> {
diff --git a/gee/treeset.vala b/gee/treeset.vala
index e9dbfef..112fbe5 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -575,7 +575,7 @@ public class Gee.TreeSet<G> : AbstractSortedSet<G> {
 		public weak Node<G>? next;
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G> {
+	private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G> {
 		private TreeSet<G> _set;
 
 		// concurrent modification protection
@@ -733,6 +733,10 @@ public class Gee.TreeSet<G> : AbstractSortedSet<G> {
 			}
 		}
 
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
+
 		private weak Node<G>? current = null;
 		private weak Node<G>? _next = null;
 		private weak Node<G>? _prev = null;
@@ -1025,7 +1029,7 @@ public class Gee.TreeSet<G> : AbstractSortedSet<G> {
 		private Range<G> range;
 	}
 
-	private class SubIterator<G> : Object, Gee.Iterator<G>, BidirIterator<G> {
+	private class SubIterator<G> : Object, Traversable<G>, Gee.Iterator<G>, BidirIterator<G> {
 		public SubIterator (TreeSet<G> set, Range<G> range) {
 			this.set = set;
 			this.range = range;
@@ -1117,6 +1121,17 @@ public class Gee.TreeSet<G> : AbstractSortedSet<G> {
 			}
 		}
 
+		public void foreach(ForallFunc<G> f) {
+			if(valid)
+				f(get());
+			while(next())
+				f(get());
+		}
+
+		public Gee.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+			return Gee.Iterator.stream_impl<G, A>(this, (owned)f);
+		}
+
 		private new TreeSet<G> set;
 		private Range<G> range;
 		private Iterator<G>? iterator = null;
diff --git a/gee/unfolditerator.vala b/gee/unfolditerator.vala
index 98a8a7e..b017544 100644
--- a/gee/unfolditerator.vala
+++ b/gee/unfolditerator.vala
@@ -20,7 +20,7 @@
  * 	Maciej Piechotka <uzytkownik2 gmail com>
  */
 
-internal class Gee.UnfoldIterator<G> : Object, Iterator<G> {
+internal class Gee.UnfoldIterator<G> : Object, Traversable<G>, Iterator<G> {
 	public UnfoldIterator (owned UnfoldFunc<G> func, owned Lazy<G>? current = null) {
 		_current = (owned)current;
 		_func = (owned)func;
@@ -86,6 +86,10 @@ internal class Gee.UnfoldIterator<G> : Object, Iterator<G> {
 		_end = true;
 	}
 
+	public Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+		return Iterator.stream_impl<G, A>(this, (owned)f);
+	}
+
 	private UnfoldFunc<G> _func;
 	private Lazy<G>? _current;
 	private Lazy<G>? _next;