[libgee] Add Iterator.unfold function

[Maciej Marcin Piechotka <mpiechotka src gnome org>]

commit aa690781fc66c035d5550b0324a1d96f620c3fd5
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Sat Apr 30 10:30:16 2011 +0200

    Add Iterator.unfold function

 gee/Makefile.am           |    1 +
 gee/iterator.vala         |   12 ++++++
 gee/unfolditerator.vala   |   93 +++++++++++++++++++++++++++++++++++++++++++++
 tests/testcollection.vala |    2 +
 tests/testfunctions.vala  |   24 ++++++++++++
 5 files changed, 132 insertions(+), 0 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index e7eff2d..f5a0a81 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -52,6 +52,7 @@ libgee_la_SOURCES = \
 	treemultimap.vala \
 	treemultiset.vala \
 	treeset.vala \
+	unfolditerator.vala \
 	$(NULL)
 
 libgee_la_VALAFLAGS = \
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 0a286d0..14a5f1f 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -27,6 +27,7 @@
 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> ();
 }
 
 /**
@@ -111,5 +112,16 @@ public interface Gee.Iterator<G> : Object {
 		while (next ())
 			f (get ());
 	}
+
+	/**
+	 * Create iterator from unfolding function. The lazy value is
+         * force-evaluated before progressing to next element.
+         *
+         * @param f Unfolding function
+         * @param current If iterator is to be valid it contains the current value of it
+	 */
+	public static Iterator<A> unfold<A> (owned UnfoldFunc<A> f, owned Lazy<G>? current = null) {
+		return new UnfoldIterator<A> ((owned) f, (owned) current);
+	}
 }
 
diff --git a/gee/unfolditerator.vala b/gee/unfolditerator.vala
new file mode 100644
index 0000000..98a8a7e
--- /dev/null
+++ b/gee/unfolditerator.vala
@@ -0,0 +1,93 @@
+/* unfolditerator.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>
+ */
+
+internal class Gee.UnfoldIterator<G> : Object, Iterator<G> {
+	public UnfoldIterator (owned UnfoldFunc<G> func, owned Lazy<G>? current = null) {
+		_current = (owned)current;
+		_func = (owned)func;
+		_end = false;
+	}
+
+	public bool next () {
+		if (has_next ()) {
+			if (_current != null)
+				_current.eval ();
+			_current = (owned)_next;
+			return true;
+		}
+		return false;
+	}
+
+	public bool has_next () {
+		if (_end)
+			return false;
+		if (_next != null)
+			return true;
+		_next = _func ();
+		if (_next == null)
+			_end = true;
+		return _next != null;
+	}
+
+	public new G get () {
+		assert (_current != null);
+		return _current.value;
+	}
+
+	public void remove () {
+		assert_not_reached ();
+	}
+
+	public bool valid { get { return _current != null; } }
+	public bool read_only { get { return true; } }
+
+	public void foreach (ForallFunc f) {
+		if (_current != null) {
+			f (_current);
+		}
+		if (_next != null) {
+			_current = (owned)_next;
+			f (_current);
+		} else if (_end) {
+			return;
+		}
+		if (_current == null) {
+			_current = _func ();
+			if (_current == null) {
+				_end = true;
+				return;
+			} else {
+				f (_current);
+			}
+		}
+		while ((_next = _func ()) != null) {
+			_current = (owned)_next;
+			f (_current);
+		}
+		_end = true;
+	}
+
+	private UnfoldFunc<G> _func;
+	private Lazy<G>? _current;
+	private Lazy<G>? _next;
+	private bool _end;
+}
diff --git a/tests/testcollection.vala b/tests/testcollection.vala
index f662cc6..eba36aa 100644
--- a/tests/testcollection.vala
+++ b/tests/testcollection.vala
@@ -2,6 +2,7 @@
  *
  * Copyright (C) 2008  JÃrg Billeter
  * Copyright (C) 2009  Didier Villevalois, Julien Peeters
+ * 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
@@ -21,6 +22,7 @@
  * 	JÃrg Billeter <j bitron ch>
  * 	Didier 'Ptitjes' Villevalois <ptitjes free fr>
  * 	Julien Peeters <contact julienpeeters fr>
+ *      Maciej Piechotka <uzytkownik2 gmail com>
  */
 
 using Gee;
diff --git a/tests/testfunctions.vala b/tests/testfunctions.vala
index f71ccc7..a76b1d3 100644
--- a/tests/testfunctions.vala
+++ b/tests/testfunctions.vala
@@ -27,6 +27,7 @@ public class FunctionsTests : Gee.TestCase {
 		add_test ("[Functions] comparing and hashing int", test_int_func);
 		add_test ("[Functions] comparing instances of Comparable", test_compare_func);
 		add_test ("[Functions] comparing and hashing instances of Hashable", test_hash_func);
+		add_test ("[Iterator] unfold", test_unfold);
 	}
 
 	public void test_string_func () {
@@ -140,6 +141,29 @@ public class FunctionsTests : Gee.TestCase {
 		assert (!eq (minus_one, minus_one));
 	}
 
+	public void test_unfold () {
+		int i = 0;
+		int j = -1;
+		var iter = Gee.Iterator.unfold<int> (() => {
+			assert (j + 1 == i);
+			if (i == 10)
+				return null;
+			int k = i++;
+			return new Gee.Lazy<int> (() => {
+				assert (k + 1 == i);
+				j = k;
+				return k;
+			});
+		});
+		int k = 0;
+		while (iter.next ()) {
+			assert (iter.get () == k);
+			assert (iter.get () == k);
+			k++;
+		}
+		assert (k == 10);
+	}
+
 	private class MyComparable : GLib.Object, Gee.Comparable<MyComparable> {
 		public MyComparable (int i) {
 			this.i = i;