[libgee] Add has_next and first methods to the Iterator interface



commit 5b2e267494ee7e20a02ab9e04ea1d984f20660c9
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Mon Sep 14 20:51:06 2009 +0200

    Add has_next and first methods to the Iterator interface

 gee/arraylist.vala          |   14 ++++++
 gee/hashmap.vala            |  102 +++++++++++++++++++++++--------------------
 gee/hashmultiset.vala       |   16 +++++++
 gee/hashset.vala            |   37 +++++++++++++---
 gee/iterator.vala           |   16 +++++++
 gee/linkedlist.vala         |   28 +++++++++---
 gee/priorityqueue.vala      |   53 +++++++++++++++++-----
 gee/readonlycollection.vala |    8 +++
 gee/treemap.vala            |   38 +++++++++++++++-
 gee/treeset.vala            |   45 +++++++++++++++++--
 tests/testcollection.vala   |   65 +++++++++++++++++++++++++++-
 11 files changed, 342 insertions(+), 80 deletions(-)
---
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index 1bbe2d2..b07ea2b 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -263,6 +263,20 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 			return (_index < _list._size);
 		}
 
+		public bool has_next () {
+			assert (_stamp == _list._stamp);
+			return (_index + 1 < _list._size);
+		}
+
+		public bool first () {
+			assert (_stamp == _list._stamp);
+			if (_list.size == 0) {
+				return false;
+			}
+			_index = 0;
+			return true;
+		}
+
 		public new G get () {
 			assert (_stamp == _list._stamp);
 			assert (_index >= 0);
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index f34f923..d98011e 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -281,43 +281,6 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 
 	}
 
-	private class KeyIterator<K,V> : Object, Iterator<K> {
-		public HashMap<K,V> map {
-			private set {
-				_map = value;
-				_stamp = _map._stamp;
-			}
-		}
-
-		private HashMap<K,V> _map;
-		private int _index = -1;
-		private weak Node<K,V> _node;
-
-		// concurrent modification protection
-		private int _stamp;
-
-		public KeyIterator (HashMap map) {
-			this.map = map;
-		}
-
-		public bool next () {
-			if (_node != null) {
-				_node = _node.next;
-			}
-			while (_node == null && _index + 1 < _map._array_size) {
-				_index++;
-				_node = _map._nodes[_index];
-			}
-			return (_node != null);
-		}
-
-		public new K get () {
-			assert (_stamp == _map._stamp);
-			assert (_node != null);
-			return _node.key;
-		}
-	}
-
 	private class ValueCollection<K,V> : AbstractCollection<V> {
 		public HashMap<K,V> map { private set; get; }
 
@@ -368,7 +331,7 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
-	private class ValueIterator<K,V> : Object, Iterator<V> {
+	private abstract class NodeIterator<K,V> : Object {
 		public HashMap<K,V> map {
 			private set {
 				_map = value;
@@ -376,28 +339,71 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 			}
 		}
 
-		private HashMap<V,K> _map;
+		protected HashMap<K,V> _map;
 		private int _index = -1;
-		private weak Node<K,V> _node;
+		protected weak Node<K,V> _node;
+		protected weak Node<K,V> _next;
 
 		// concurrent modification protection
-		private int _stamp;
+		protected int _stamp;
 
-		public ValueIterator (HashMap map) {
+		public NodeIterator (HashMap map) {
 			this.map = map;
 		}
 
 		public bool next () {
-			if (_node != null) {
-				_node = _node.next;
-			}
-			while (_node == null && _index + 1 < _map._array_size) {
-				_index++;
-				_node = _map._nodes[_index];
+			assert (_stamp == _map._stamp);
+			if (!has_next ()) {
+				return false;
 			}
+			_node = _next;
+			_next = null;
 			return (_node != null);
 		}
 
+		public bool has_next () {
+			assert (_stamp == _map._stamp);
+			if (_next == null) {
+				_next = _node;
+				if (_next != null) {
+					_next = _next.next;
+				}
+				while (_next == null && _index + 1 < _map._array_size) {
+					_index++;
+					_next = _map._nodes[_index];
+				}
+			}
+			return (_next != null);
+		}
+
+		public bool first () {
+			assert (_stamp == _map._stamp);
+			if (_map.size == 0) {
+				return false;
+			}
+			_index = -1;
+			_next = null;
+			return next ();
+		}
+	}
+
+	private class KeyIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
+		public KeyIterator (HashMap map) {
+			base (map);
+		}
+
+		public new K get () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			return _node.key;
+		}
+	}
+
+	private class ValueIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
+		public ValueIterator (HashMap map) {
+			base (map);
+		}
+
 		public new V get () {
 			assert (_stamp == _map._stamp);
 			assert (_node != null);
diff --git a/gee/hashmultiset.vala b/gee/hashmultiset.vala
index c977426..33dc76e 100644
--- a/gee/hashmultiset.vala
+++ b/gee/hashmultiset.vala
@@ -120,6 +120,22 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
 			return false;
 		}
 
+		public bool has_next () {
+			return _pending > 0 || _iter.has_next ();
+		}
+
+		public bool first () {
+			if (set._nitems == 0) {
+				return false;
+			}
+			_pending = 0;
+			if (_iter.first ()) {
+				var key = _iter.get ();
+				_pending = set._items.get (key) - 1;
+			}
+			return true;
+		}
+
 		public new G get () {
 			return _iter.get ();
 		}
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 0763350..34103d8 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -211,6 +211,7 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 		private HashSet<G> _set;
 		private int _index = -1;
 		private weak Node<G> _node;
+		private weak Node<G> _next;
 
 		// concurrent modification protection
 		private int _stamp = 0;
@@ -220,16 +221,40 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 		}
 
 		public bool next () {
-			if (_node != null) {
-				_node = _node.next;
-			}
-			while (_node == null && _index + 1 < _set._array_size) {
-				_index++;
-				_node = _set._nodes[_index];
+			assert (_stamp == _set._stamp);
+			if (!has_next ()) {
+				return false;
 			}
+			_node = _next;
+			_next = null;
 			return (_node != null);
 		}
 
+		public bool has_next () {
+			assert (_stamp == _set._stamp);
+			if (_next == null) {
+				_next = _node;
+				if (_next != null) {
+					_next = _next.next;
+				}
+				while (_next == null && _index + 1 < _set._array_size) {
+					_index++;
+					_next = _set._nodes[_index];
+				}
+			}
+			return (_next != null);
+		}
+
+		public bool first () {
+			assert (_stamp == _set._stamp);
+			if (_set.size == 0) {
+				return false;
+			}
+			_index = -1;
+			_next = null;
+			return next ();
+		}
+
 		public new G get () {
 			assert (_stamp == _set._stamp);
 			assert (_node != null);
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 41de156..2acaca3 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -1,6 +1,7 @@
 /* iterator.vala
  *
  * Copyright (C) 2007-2008  Jürg Billeter
+ * Copyright (C) 2009  Didier Villevalois, Maciej Piechotka
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -18,6 +19,7 @@
  *
  * Author:
  * 	Jürg Billeter <j bitron ch>
+ * 	Maciej Piechotka <uzytkownik2 gmail com>
  */
 
 /**
@@ -32,6 +34,20 @@ public interface Gee.Iterator<G> : GLib.Object {
 	public abstract bool next ();
 
 	/**
+	 * Checks whether there is a next element in the iteration.
+	 *
+	 * @return true if the iterator has a next element
+	 */
+	public abstract bool has_next ();
+
+	/**
+	 * Rewinds to the first element in the iteration.
+	 *
+	 * @return true if the iterator has a first element
+	 */
+	public abstract bool first ();
+
+	/**
 	 * Returns the current element in the iteration.
 	 *
 	 * @return the current element in the iteration
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index 2572fc5..c01c8d7 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -393,7 +393,7 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 
 		public Iterator (LinkedList<G> list) {
 			this._list = list;
-			this.position = list._head;
+			this.position = null;
 			this._stamp = list._stamp;
 		}
 
@@ -402,13 +402,29 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 
 			if (!this.started) {
 				this.started = true;
-				return this.position != null;
-			} else if (this.position.next == null) {
-				return false;
-			} else {
+				this.position = this._list._head;
+			} else if (this.position != null) {
 				this.position = this.position.next;
-				return true;
 			}
+			return this.position != null;
+		}
+
+		public bool has_next () {
+			assert (this._stamp == this._list._stamp);
+
+			if (!this.started) {
+				return this._list._head != null;
+			} else if (this.position != null) {
+				return this.position.next != null;
+			}
+			return false;
+		}
+
+		public bool first () {
+			assert (this._stamp == this._list._stamp);
+			this.position = null;
+			this.started = false;
+			return next ();
 		}
 
 		public new G get () {
diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala
index 7bcf503..3779934 100644
--- a/gee/priorityqueue.vala
+++ b/gee/priorityqueue.vala
@@ -760,6 +760,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 		private bool from_type1_children = false;
 		private bool from_type2_child = false;
 		private unowned Node<G>? position;
+		private unowned Node<G>? _next;
 		private int stamp;
 
 		public Iterator (PriorityQueue<G> queue) {
@@ -770,44 +771,72 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 
 		public bool next () {
 			assert (stamp == queue._stamp);
+			if (!has_next ()) {
+				return false;
+			}
+			position = _next;
+			_next = null;
+			return (position != null);
+		}
+
+		public bool has_next () {
+			assert (stamp == queue._stamp);
+			if (_next == null) {
+				_next = position;
+				if (!_has_next ()) {
+					_next = null;
+				}
+			}
+			return (_next != null);
+		}
 
+		private bool _has_next() {
 			if (!started) {
 				started = true;
-				return position != null;
-			} else if (position is Type1Node) {
-				var node = position as Type1Node<G>;
+				return _next != null;
+			} else if (_next is Type1Node) {
+				var node = _next as Type1Node<G>;
 				if (!from_type1_children && node.type1_children_head != null) {
-					position = node.type1_children_head;
+					_next = node.type1_children_head;
 					from_type1_children = false;
 					from_type2_child = false;
 					return true;
 				} else if (!from_type2_child && node.type2_child != null) {
-					position = node.type2_child;
+					_next = node.type2_child;
 					from_type1_children = false;
 					from_type2_child = false;
 					return true;
 				} else if (node.brothers_next != null) {
-					position = node.brothers_next;
+					_next = node.brothers_next;
 					return true;
 				}
 				from_type1_children = true;
-			} else if (position is Type2Node) {
-				var node = position as Type2Node<G>;
+			} else if (_next is Type2Node) {
+				var node = _next as Type2Node<G>;
 				if (!from_type1_children && node.type1_children_head != null) {
-					position = node.type1_children_head;
+					_next = node.type1_children_head;
 					from_type1_children = false;
 					from_type2_child = false;
 					return true;
 				}
 				from_type2_child = true;
 			}
-			if (position != queue._r) {
-				position = position.parent;
-				return next ();
+			if (_next != queue._r) {
+				_next = _next.parent;
+				return _has_next ();
 			}
 			return false;
 		}
 
+		public bool first () {
+			assert (stamp == queue._stamp);
+			position = queue._r;
+			started = false;
+			from_type1_children = false;
+			from_type2_child = false;
+			return next ();
+		}
+
 		public new G get () {
 			assert (stamp == queue._stamp);
 			assert (position != null);
diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala
index b29f914..abaec4e 100644
--- a/gee/readonlycollection.vala
+++ b/gee/readonlycollection.vala
@@ -141,6 +141,14 @@ internal class Gee.ReadOnlyCollection<G> : Object, Iterable<G>, Collection<G> {
 			return false;
 		}
 
+		public bool has_next () {
+			return false;
+		}
+
+		public bool first () {
+			return false;
+		}
+
 		public new G? get () {
 			return null;
 		}
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 56940be..fe7d4ff 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -471,13 +471,25 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			assert (stamp == _map.stamp);
 			if (current != null) {
 				current = current.next;
-			} else if (!run){
+			} else if (state == KeyIterator.State.BEFORE_THE_BEGIN) {
 				run = true;
 				current = _map.first;
 			}
 			return current != null;
 		}
 
+		public bool has_next () {
+			assert (stamp == _map.stamp);
+			return (current == null && state == KeyIterator.State.BEFORE_THE_BEGIN) ||
+			       (current != null && current.next != null);
+		}
+
+		public bool first () {
+			assert (stamp == _map.stamp);
+			current = _map.first;
+			return current != null; // on false it is null anyway
+		}
+
 		public new K get () {
 			assert (stamp == _map.stamp);
 			assert (current != null);
@@ -485,6 +497,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 
 		private weak Node<K, V>? current;
+		private enum State {
+			BEFORE_THE_BEGIN,
+			PAST_THE_END
+		}
+		private KeyIterator.State state = KeyIterator.State.BEFORE_THE_BEGIN;
 		private bool run = false;
 	}
 
@@ -509,13 +526,25 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			assert (stamp == _map.stamp);
 			if (current != null) {
 				current = current.next;
-			} else if (!run){
+			} else if (state == ValueIterator.State.BEFORE_THE_BEGIN) {
 				run = true;
 				current = _map.first;
 			}
 			return current != null;
 		}
 
+		public bool has_next () {
+			assert (stamp == _map.stamp);
+			return (current == null && state == ValueIterator.State.BEFORE_THE_BEGIN) ||
+			       (current != null && current.next != null);
+		}
+
+		public bool first () {
+			assert (stamp == _map.stamp);
+			current = _map.first;
+			return current != null; // on false it is null anyway
+		}
+
 		public new V get () {
 			assert (stamp == _map.stamp);
 			assert (current != null);
@@ -523,6 +552,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 
 		private weak Node<K, V>? current;
+		private enum State {
+			BEFORE_THE_BEGIN,
+			PAST_THE_END
+		}
+		private ValueIterator.State state = ValueIterator.State.BEFORE_THE_BEGIN;
 		private bool run = false;
 	}
 }
diff --git a/gee/treeset.vala b/gee/treeset.vala
index e6a53e8..ba047b3 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -266,7 +266,7 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 	 * @inheritDoc
 	 */
 	public override Gee.Iterator<G> iterator () {
-		return  new Iterator<G> (this);
+		return new Iterator<G> (this);
 	}
 
 	[Compact]
@@ -336,13 +336,41 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			assert (stamp == _set.stamp);
 			if (current != null) {
 				current = current.next;
-			} else if (!run){
-				run = true;
-				current = _set.first;
+			} else {
+				switch (state) {
+				case Iterator.State.BEFORE_THE_BEGIN:
+					current = _set.first;
+					break;
+				case Iterator.State.NORMAL: // After remove
+					current = _next;
+					_next = null;
+					_prev = null;
+					break;
+				case Iterator.State.PAST_THE_END:
+					break;
+				default:
+					assert_not_reached ();
+				}
 			}
+			state = current != null ? Iterator.State.NORMAL : Iterator.State.PAST_THE_END;
 			return current != null;
 		}
 
+		public bool has_next () {
+			assert (stamp == _set.stamp);
+			return (current == null && state == Iterator.State.BEFORE_THE_BEGIN) ||
+			       (current == null && state == Iterator.State.NORMAL && _next != null) ||
+			       (current != null && current.next != null);
+		}
+
+		public bool first () {
+			assert (stamp == _set.stamp);
+			current = _set.first;
+			_next = null;
+			_prev = null;
+			return current != null; // on false it is null anyway
+		}
+
 		public new G get () {
 			assert (stamp == _set.stamp);
 			assert (current != null);
@@ -350,7 +378,14 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		}
 
 		private weak Node<G>? current;
-		private bool run = false;
+		private weak Node<G>? _next;
+		private weak Node<G>? _prev;
+		private enum State {
+			BEFORE_THE_BEGIN,
+			NORMAL,
+			PAST_THE_END
+		}
+		private Iterator.State state = Iterator.State.BEFORE_THE_BEGIN;
 	}
 
 	private Node<G>? root = null;
diff --git a/tests/testcollection.vala b/tests/testcollection.vala
index f37cd6d..295bb2c 100644
--- a/tests/testcollection.vala
+++ b/tests/testcollection.vala
@@ -55,7 +55,15 @@ public abstract class CollectionTests : Gee.TestCase {
 	public void test_iterator_returns_all_elements_once () {
 		// Check the collection exists
 		assert (test_collection != null);
+		bool has_next;
 
+		// Check with an empty collection
+		Iterator<string> iterator = test_collection.iterator ();
+		assert (! iterator.has_next ());
+		assert (! iterator.next ());
+		assert (! iterator.first ());
+
+		// Check for some elements in the collection
 		assert (test_collection.add ("one"));
 		assert (test_collection.add ("two"));
 		assert (test_collection.add ("three"));
@@ -66,7 +74,53 @@ public abstract class CollectionTests : Gee.TestCase {
 		bool one_found_once = true;
 		bool two_found_once = true;
 		bool three_found_once = true;
-		foreach (string element in test_collection) {
+		iterator = test_collection.iterator ();
+		while (true) {
+			has_next = iterator.has_next ();
+			assert (has_next == iterator.next ());
+			if (! has_next) {
+				break;
+			}
+
+			string element = iterator.get ();
+			if (element == "one") {
+				if (one_found) {
+					one_found_once = false;
+				}
+				one_found = true;
+			} else if (element == "two") {
+				if (two_found) {
+					two_found_once = false;
+				}
+				two_found = true;
+			} else if (element == "three") {
+				if (three_found) {
+					three_found_once = false;
+				}
+				three_found = true;
+			}
+		}
+		has_next = iterator.has_next ();
+		assert (! has_next);
+		assert (has_next == iterator.next ());
+		assert (one_found);
+		assert (one_found_once);
+		assert (two_found);
+		assert (two_found_once);
+		assert (three_found);
+		assert (three_found_once);
+
+		// Do it twice to check first ()
+		assert (iterator.first ());
+
+		one_found = false;
+		two_found = false;
+		three_found = false;
+		one_found_once = true;
+		two_found_once = true;
+		three_found_once = true;
+		while (true) {
+			string element = iterator.get ();
 			if (element == "one") {
 				if (one_found) {
 					one_found_once = false;
@@ -83,7 +137,16 @@ public abstract class CollectionTests : Gee.TestCase {
 				}
 				three_found = true;
 			}
+
+			has_next = iterator.has_next ();
+			assert (has_next == iterator.next ());
+			if (! has_next) {
+				break;
+			}
 		}
+		has_next = iterator.has_next ();
+		assert (! has_next);
+		assert (has_next == iterator.next ());
 		assert (one_found);
 		assert (one_found_once);
 		assert (two_found);



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]