[libgee] Fix the iterators of the TreeMap and TreeSet implementations

[Didier Villevalois <dvillevalois src gnome org>]

commit 5aed214a1e6fd348b680c0eeef84cc37eaad1bf3
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Wed Sep 16 20:42:58 2009 +0200

    Fix the iterators of the TreeMap and TreeSet implementations

 gee/treemap.vala |  181 ++++++++++--------------------------------------------
 gee/treeset.vala |   62 +++++--------------
 2 files changed, 49 insertions(+), 194 deletions(-)
---
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 7ce274a..6a9b574 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -569,13 +569,15 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
-	private class KeyIterator<K,V> : Object, Gee.Iterator<K>, BidirIterator<K> {
-		private TreeMap<K,V> _map;
+	private class NodeIterator<K,V> : Object {
+		protected TreeMap<K,V> _map;
 
 		// concurrent modification protection
-		private int stamp;
+		protected int stamp;
 
-		public KeyIterator (TreeMap<K,V> map) {
+		protected weak Node<K, V>? current;
+
+		public NodeIterator (TreeMap<K,V> map) {
 			_map = map;
 			stamp = _map.stamp;
 		}
@@ -583,17 +585,21 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		public bool next () {
 			assert (stamp == _map.stamp);
 			if (current != null) {
-				current = current.next;
-			} else if (state == KeyIterator.State.BEFORE_THE_BEGIN) {
-				run = true;
+				if (current.next != null) {
+					current = current.next;
+					return true;
+				} else {
+					return false;
+				}
+			} else {
 				current = _map.first;
+				return current != null;
 			}
-			return current != null;
 		}
 
 		public bool has_next () {
 			assert (stamp == _map.stamp);
-			return (current == null && state == KeyIterator.State.BEFORE_THE_BEGIN) ||
+			return (current == null && _map.first != null) ||
 			       (current != null && current.next != null);
 		}
 
@@ -606,18 +612,19 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		public bool previous () {
 			assert (stamp == _map.stamp);
 			if (current != null) {
-				current = current.prev;
-			} else if (state == KeyIterator.State.PAST_THE_END) {
-				current = _map.last;
+				if (current.prev != null) {
+					current = current.prev;
+					return true;
+				} else {
+					return false;
+				}
 			}
-			state = KeyIterator.State.BEFORE_THE_BEGIN;
-			return current != null;
+			return false;
 		}
 
 		public bool has_previous () {
 			assert (stamp == _map.stamp);
-			return (current == null && state == KeyIterator.State.PAST_THE_END) ||
-			       (current != null && current.prev != null);
+			return (current != null && current.prev != null);
 		}
 
 		public bool last () {
@@ -625,6 +632,12 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			current = _map.last;
 			return current != null; // on false it is null anyway
 		}
+	}
+
+	private class KeyIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<K>, BidirIterator<K> {
+		public KeyIterator (TreeMap<K,V> map) {
+			base (map);
+		}
 
 		public new K get () {
 			assert (stamp == _map.stamp);
@@ -635,71 +648,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		public void remove () {
 			assert_not_reached ();
 		}
-
-		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;
 	}
 
-	private class ValueIterator<K,V> : Object, Gee.Iterator<V>, Gee.BidirIterator<V> {
-		private TreeMap<K,V> _map;
-
-		// concurrent modification protection
-		private int stamp;
-
+	private class ValueIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<V>, Gee.BidirIterator<V> {
 		public ValueIterator (TreeMap<K,V> map) {
-			_map = map;
-			stamp = _map.stamp;
-		}
-
-		public bool next () {
-			assert (stamp == _map.stamp);
-			if (current != null) {
-				current = current.next;
-			} 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 bool previous () {
-			assert (stamp == _map.stamp);
-			if (current != null) {
-				current = current.prev;
-			} else if (state == ValueIterator.State.PAST_THE_END) {
-				current = _map.last;
-			}
-			state = ValueIterator.State.BEFORE_THE_BEGIN;
-			return current != null;
-		}
-
-		public bool has_previous () {
-			assert (stamp == _map.stamp);
-			return (current == null && state == ValueIterator.State.PAST_THE_END) ||
-			       (current != null && current.prev != null);
-		}
-
-		public bool last () {
-			assert (stamp == _map.stamp);
-			current = _map.last;
-			return current != null; // on false it is null anyway
+			base (map);
 		}
 
 		public new V get () {
@@ -711,71 +664,11 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		public void remove () {
 			assert_not_reached ();
 		}
-
-		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;
 	}
 
-	private class EntryIterator<K,V> : Object, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
-		private TreeMap<K,V> _map;
-
-		// concurrent modification protection
-		private int stamp;
-
+	private class EntryIterator<K,V> : NodeIterator<K,V>, Gee.Iterator<Map.Entry<K,V>>, Gee.BidirIterator<Map.Entry<K,V>> {
 		public EntryIterator (TreeMap<K,V> map) {
-			_map = map;
-			stamp = _map.stamp;
-		}
-
-		public bool next () {
-			assert (stamp == _map.stamp);
-			if (current != null) {
-				current = current.next;
-			} else if (state == EntryIterator.State.BEFORE_THE_BEGIN) {
-				run = true;
-				current = _map.first;
-			}
-			return current != null;
-		}
-
-		public bool has_next () {
-			assert (stamp == _map.stamp);
-			return (current == null && state == EntryIterator.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 bool previous () {
-			assert (stamp == _map.stamp);
-			if (current != null) {
-				current = current.prev;
-			} else if (state == EntryIterator.State.PAST_THE_END) {
-				current = _map.last;
-			}
-			state = EntryIterator.State.BEFORE_THE_BEGIN;
-			return current != null;
-		}
-
-		public bool has_previous () {
-			assert (stamp == _map.stamp);
-			return (current == null && state == EntryIterator.State.PAST_THE_END) ||
-			       (current != null && current.prev != null);
-		}
-
-		public bool last () {
-			assert (stamp == _map.stamp);
-			current = _map.last;
-			return current != null; // on false it is null anyway
+			base (map);
 		}
 
 		public new Map.Entry<K,V> get () {
@@ -787,13 +680,5 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		public void remove () {
 			assert_not_reached ();
 		}
-
-		private weak Node<K, V>? current;
-		private enum State {
-			BEFORE_THE_BEGIN,
-			PAST_THE_END
-		}
-		private EntryIterator.State state = EntryIterator.State.BEFORE_THE_BEGIN;
-		private bool run = false;
 	}
 }
diff --git a/gee/treeset.vala b/gee/treeset.vala
index c3aa9b9..f8836af 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -342,33 +342,21 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			assert (stamp == _set.stamp);
 			if (current != null) {
 				current = current.next;
+			} else if (!started) {
+				current = _set.first;
+				started = true;
 			} 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 ();
-				}
+				current = _next;
+				_next = null;
+				_prev = null;
 			}
-			state = current != null ? Iterator.State.NORMAL : Iterator.State.PAST_THE_END;
 			return current != null;
 		}
 
 		public bool has_next () {
 			assert (stamp == _set.stamp);
-			if (_set.size == 0) {
-				return false;
-			}
-			return (current == null && state == Iterator.State.BEFORE_THE_BEGIN) ||
-			       (current == null && state == Iterator.State.NORMAL && _next != null) ||
+			return (!started && _set.first != null) ||
+			       (current == null && _next != null) ||
 			       (current != null && current.next != null);
 		}
 
@@ -385,29 +373,16 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			if (current != null) {
 				current = current.prev;
 			} else {
-				switch (state) {
-				case Iterator.State.BEFORE_THE_BEGIN:
-					break;
-				case Iterator.State.NORMAL: // After remove
-					current = _prev;
-					_next = null;
-					_prev = null;
-					break;
-				case Iterator.State.PAST_THE_END:
-					current = _set.last;
-					break;
-				default:
-					assert_not_reached ();
-				}
+				current = _prev;
+				_next = null;
+				_prev = null;
 			}
-			state = current != null ? Iterator.State.NORMAL : Iterator.State.BEFORE_THE_BEGIN;
 			return current != null;
 		}
 
 		public bool has_previous () {
 			assert (stamp == _set.stamp);
-			return (current == null && state == Iterator.State.PAST_THE_END) ||
-			       (current == null && state == Iterator.State.NORMAL && _prev != null) ||
+			return (current == null && _prev != null) ||
 			       (current != null && current.prev != null);
 		}
 
@@ -436,15 +411,10 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			assert (stamp == _set.stamp);
 		}
 
-		private weak Node<G>? current;
-		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 weak Node<G>? current = null;
+		private weak Node<G>? _next = null;
+		private weak Node<G>? _prev = null;
+		private bool started = false;
 	}
 
 	private Node<G>? root = null;