[libgee] Introduce the BidirIterator interface

[Didier 'Ptitjes' Villevalois <dvillevalois src gnome org>]

commit 968fca3ccf9151f573e5d559bf0dc79c011b7d8a
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date:   Mon Sep 14 20:09:43 2009 +0200

    Introduce the BidirIterator interface

 gee/Makefile.am        |    1 +
 gee/bidiriterator.vala |   47 ++++++++++++++++++++++++++++++++++++++++
 gee/treemap.vala       |   56 ++++++++++++++++++++++++++++++++++++++++++++++-
 gee/treeset.vala       |   54 +++++++++++++++++++++++++++++++++++++++++++++-
 4 files changed, 155 insertions(+), 3 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 15e13a4..4a899b0 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -20,6 +20,7 @@ libgee_la_VALASOURCES = \
 	abstractqueue.vala \
 	abstractset.vala \
 	arraylist.vala \
+	bidiriterator.vala \
 	collection.vala \
 	deque.vala \
 	functions.vala \
diff --git a/gee/bidiriterator.vala b/gee/bidiriterator.vala
new file mode 100644
index 0000000..070dd06
--- /dev/null
+++ b/gee/bidiriterator.vala
@@ -0,0 +1,47 @@
+/* bidiriterator.vala
+ *
+ * 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
+ * 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>
+ */
+
+/**
+ * A bi-directional iterator.
+ */
+public interface Gee.BidirIterator<G> : Gee.Iterator<G> {
+	/**
+	 * Rewinds to the previous element in the iteration.
+	 *
+	 * @return true if the iterator has a previous element
+	 */
+	public abstract bool previous ();
+
+	/**
+	 * Checks whether there is a previous element in the iteration.
+	 *
+	 * @return true if the iterator has a previous element
+	 */
+	public abstract bool has_previous ();
+
+	/**
+	 * Advances to the last element in the iteration.
+	 *
+	 * @return true if the iterator has a last element
+	 */
+	public abstract bool last ();
+}
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 4cb41e8..a9d7fef 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -151,6 +151,9 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			if (prev == null) {
 				first = node;
 			}
+			if (next == null) {
+				last = node;
+			}
 			_size++;
 		}
 
@@ -208,6 +211,8 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 		if (n.next != null) {
 			n.next.prev = n.prev;
+		} else {
+			last = n.next;
 		}
 		node = null;
 		_size--;
@@ -354,6 +359,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 
 	private Node<K, V>? root = null;
 	private weak Node<K, V>? first = null;
+	private weak Node<K, V>? last = null;
 	private int stamp = 0;
 
 	private class KeySet<K,V> : AbstractSet<K> {
@@ -450,7 +456,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
-	private class KeyIterator<K,V> : Object, Gee.Iterator<K> {
+	private class KeyIterator<K,V> : Object, Gee.Iterator<K>, BidirIterator<K> {
 		public TreeMap<K,V> map {
 			private set {
 				_map = value;
@@ -490,6 +496,29 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			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 == KeyIterator.State.PAST_THE_END) {
+				current = _map.last;
+			}
+			state = KeyIterator.State.BEFORE_THE_BEGIN;
+			return current != null;
+		}
+
+		public bool has_previous () {
+			assert (stamp == _map.stamp);
+			return (current == null && state == KeyIterator.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
+		}
+
 		public new K get () {
 			assert (stamp == _map.stamp);
 			assert (current != null);
@@ -509,7 +538,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		private bool run = false;
 	}
 
-	private class ValueIterator<K,V> : Object, Gee.Iterator<V> {
+	private class ValueIterator<K,V> : Object, Gee.Iterator<V>, Gee.BidirIterator<V> {
 		public TreeMap<K,V> map {
 			private set {
 				_map = value;
@@ -549,6 +578,29 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			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
+		}
+
 		public new V get () {
 			assert (stamp == _map.stamp);
 			assert (current != null);
diff --git a/gee/treeset.vala b/gee/treeset.vala
index 6b13e78..be49d62 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -119,6 +119,9 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			if (prev == null) {
 				first = node;
 			}
+			if (next == null) {
+				last = node;
+			}
 			_size++;
 			return true;
 		}
@@ -182,6 +185,8 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		}
 		if (n.next != null) {
 			n.next.prev = n.prev;
+		} else {
+			last = n.prev;
 		}
 		node = null;
 		_size--;
@@ -269,6 +274,13 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		return new Iterator<G> (this);
 	}
 
+	/**
+	 * @inheritDoc
+	 */
+	public BidirIterator<G> bidir_iterator () {
+		return new Iterator<G> (this);
+	}
+
 	[Compact]
 	private class Node<G> {
 		public enum Color {
@@ -315,7 +327,7 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 		public weak Node<G>? next;
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G> {
 		public new TreeSet<G> set {
 			private set {
 				_set = value;
@@ -371,6 +383,45 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			return current != null; // on false it is null anyway
 		}
 
+		public bool previous () {
+			assert (stamp == _set.stamp);
+			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 ();
+				}
+			}
+			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) ||
+			       (current != null && current.prev != null);
+		}
+
+		public bool last () {
+			assert (stamp == _set.stamp);
+			current = _set.last;
+			_next = null;
+			_prev = null;
+			return current != null; // on false it is null anyway
+		}
+
 		public new G get () {
 			assert (stamp == _set.stamp);
 			assert (current != null);
@@ -401,5 +452,6 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 
 	private Node<G>? root = null;
 	private weak Node<G>? first = null;
+	private weak Node<G>? last = null;
 	private int stamp = 0;
 }