GNOME.org
 

[libgee] Introduce remove method to the Iterator interface

commit a372fb799e3a7ac8a6df639153ceee5e9feed375
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Tue Sep 15 17:07:36 2009 +0200

    Introduce remove method to the Iterator interface

 gee/Makefile.am               |    1 +
 gee/arraylist.vala            |   15 ++++++
 gee/hashmap.vala              |   46 +++++++++++++++++++
 gee/hashmultiset.vala         |   22 +++++++---
 gee/hashset.vala              |   10 ++++
 gee/iterator.vala             |   16 +++++++
 gee/linkedlist.vala           |   23 +++++++++-
 gee/priorityqueue.vala        |   17 +++++++-
 gee/readonlycollection.vala   |   24 +++++++---
 gee/treemap.vala              |    8 +++
 gee/treeset.vala              |   11 +++++
 gee/updatablekeyiterator.vala |   41 +++++++++++++++++
 tests/testcollection.vala     |  101 +++++++++++++++++++++++++++++++++++++++++
 13 files changed, 319 insertions(+), 16 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 22f6113..15e13a4 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -44,6 +44,7 @@ libgee_la_VALASOURCES = \
 	timsort.vala \
 	treemap.vala \
 	treeset.vala \
+	updatablekeyiterator.vala \
 	$(NULL)
 
 libgee_la_SOURCES = \
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index b07ea2b..e4810e0 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -247,6 +247,7 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 
 		private ArrayList<G> _list;
 		private int _index = -1;
+		private bool _removed = false;
 
 		// concurrent modification protection
 		private int _stamp = 0;
@@ -260,6 +261,7 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 			if (_index < _list._size) {
 				_index++;
 			}
+			_removed = false;
 			return (_index < _list._size);
 		}
 
@@ -274,6 +276,7 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 				return false;
 			}
 			_index = 0;
+			_removed = false;
 			return true;
 		}
 
@@ -281,8 +284,20 @@ public class Gee.ArrayList<G> : AbstractList<G> {
 			assert (_stamp == _list._stamp);
 			assert (_index >= 0);
 			assert (_index < _list._size);
+			assert (! _removed);
 			return _list.get (_index);
 		}
+
+		public void remove () {
+			assert (_stamp == _list._stamp);
+			assert (_index >= 0);
+			assert (_index < _list._size);
+			assert (! _removed);
+			_list.remove_at (_index);
+			_index--;
+			_removed = true;
+			_stamp = _list._stamp;
+		}
 	}
 }
 
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index d98011e..2e67fed 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -107,6 +107,10 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		return new ValueCollection<K,V> (this);
 	}
 
+	internal Gee.UpdatableKeyIterator<K,V> updatable_key_iterator () {
+		return new UpdatableKeyIterator<K,V> (this);
+	}
+
 	private Node<K,V>** lookup_node (K key) {
 		uint hash_value = key_hash_func (key);
 		Node<K,V>** node = &_nodes[hash_value % _array_size];
@@ -397,6 +401,44 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 			assert (_node != null);
 			return _node.key;
 		}
+
+		public void remove () {
+			assert_not_reached ();
+		}
+	}
+
+	private class UpdatableKeyIterator<K,V> : NodeIterator<K,V>, Iterator<K>, Gee.UpdatableKeyIterator<K,V> {
+		public UpdatableKeyIterator (HashMap map) {
+			base (map);
+		}
+
+		public new K get () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			return _node.key;
+		}
+
+		public void remove () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			has_next ();
+			_map.remove (_node.key);
+			_node = null;
+			_stamp = _map._stamp;
+		}
+
+		public V get_value () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			return _node.value;
+		}
+
+		public void set_value (V value) {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			_map.set (_node.key, value);
+			_stamp = _map._stamp;
+		}
 	}
 
 	private class ValueIterator<K,V> : NodeIterator<K,V>, Iterator<K> {
@@ -409,6 +451,10 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 			assert (_node != null);
 			return _node.value;
 		}
+
+		public void remove () {
+			assert_not_reached ();
+		}
 	}
 }
 
diff --git a/gee/hashmultiset.vala b/gee/hashmultiset.vala
index 33dc76e..ed7d2eb 100644
--- a/gee/hashmultiset.vala
+++ b/gee/hashmultiset.vala
@@ -95,11 +95,12 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
 	private class Iterator<G> : Object, Gee.Iterator<G> {
 		public new HashMultiSet<G> set { construct; get; }
 
-		private Gee.Iterator<G> _iter;
+		private Gee.UpdatableKeyIterator<G, int> _iter;
 		private int _pending = 0;
+		private bool _removed = false;
 
 		construct {
-			_iter = set._items.get_keys ().iterator ();
+			_iter = set._items.updatable_key_iterator ();
 		}
 
 		public Iterator (HashMultiSet<G> set) {
@@ -107,10 +108,10 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
 		}
 
 		public bool next () {
+			_removed = false;
 			if (_pending == 0) {
 				if (_iter.next ()) {
-					var key = _iter.get ();
-					_pending = set._items.get (key) - 1;
+					_pending = _iter.get_value () - 1;
 					return true;
 				}
 			} else {
@@ -130,14 +131,23 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
 			}
 			_pending = 0;
 			if (_iter.first ()) {
-				var key = _iter.get ();
-				_pending = set._items.get (key) - 1;
+				_pending = _iter.get_value () - 1;
 			}
 			return true;
 		}
 
 		public new G get () {
+			assert (! _removed);
 			return _iter.get ();
 		}
+
+		public void remove () {
+			assert (! _removed);
+			_iter.set_value (_pending = _iter.get_value () - 1);
+			if (_pending == 0) {
+				_iter.remove ();
+			}
+			_removed = true;
+		}
 	}
 }
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 34103d8..70751b7 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -130,6 +130,7 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 	public override bool remove (G key) {
 		Node<G>** node = lookup_node (key);
 		if (*node != null) {
+			assert (*node != null);
 			Node<G> next = (owned) (*node)->next;
 
 			(*node)->key = null;
@@ -260,6 +261,15 @@ public class Gee.HashSet<G> : AbstractSet<G> {
 			assert (_node != null);
 			return _node.key;
 		}
+
+		public void remove () {
+			assert (_stamp == _set._stamp);
+			assert (_node != null);
+			has_next ();
+			_set.remove (_node.key);
+			_node = null;
+			_stamp = _set._stamp;
+		}
 	}
 }
 
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 2acaca3..bf9deac 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -20,10 +20,19 @@
  * Author:
  * 	Jürg Billeter <j bitron ch>
  * 	Maciej Piechotka <uzytkownik2 gmail com>
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
  */
 
 /**
  * An iterator over a collection.
+ *
+ * Gee's iterators are "on-track" iterators. They always point to an item
+ * except before the first call to { link next} or { link first}, or, when an
+ * item has been removed, until the next call to { link next} or { link first}.
+ *
+ * Please note that when the iterator is out of track, neither { link get} nor
+ * { link remove} are defined and both will fail. After the next call to
+ * { link next} or { link first}, they will be defined again.
  */
 public interface Gee.Iterator<G> : GLib.Object {
 	/**
@@ -53,5 +62,12 @@ public interface Gee.Iterator<G> : GLib.Object {
 	 * @return the current element in the iteration
 	 */
 	public abstract G get ();
+
+	/**
+	 * Removes the current element in the iteration. The cursor is set in an
+	 * in-between state. Both { link get} and { link remove} will fail until
+	 * the next move of the cursor (calling { link next} or { link first}).
+	 */
+	public abstract void remove ();
 }
 
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index c01c8d7..1918033 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -387,6 +387,7 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 
 	private class Iterator<G> : Object, Gee.Iterator<G> {
 		private bool started = false;
+		private bool removed = false;
 		private unowned Node<G>? position;
 		private int _stamp;
 		private LinkedList<G> _list;
@@ -400,7 +401,9 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 		public bool next () {
 			assert (this._stamp == this._list._stamp);
 
-			if (!this.started) {
+			if (this.removed) {
+				this.removed = false;
+			} else if (!this.started) {
 				this.started = true;
 				this.position = this._list._head;
 			} else if (this.position != null) {
@@ -412,7 +415,9 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 		public bool has_next () {
 			assert (this._stamp == this._list._stamp);
 
-			if (!this.started) {
+			if (this.removed) {
+				return this.position != null;
+			} else if (!this.started) {
 				return this._list._head != null;
 			} else if (this.position != null) {
 				return this.position.next != null;
@@ -433,6 +438,20 @@ public class Gee.LinkedList<G> : AbstractList<G>, Queue<G>, Deque<G> {
 
 			return this.position.data;
 		}
+
+		public void remove () {
+			assert (this._stamp == this._list._stamp);
+			assert (this.position != null);
+
+			unowned Node<G>? new_position = this.position.next;
+			if (new_position == null) {
+				started = false;
+			}
+			_list._remove_node (this.position);
+			this.position = new_position;
+			this.removed = true;
+			this._stamp = this._list._stamp;
+		}
 	}
 
 	private unowned Node<G>? _get_node_at (int index) {
diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala
index 3779934..e988e12 100644
--- a/gee/priorityqueue.vala
+++ b/gee/priorityqueue.vala
@@ -762,6 +762,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 		private unowned Node<G>? position;
 		private unowned Node<G>? _next;
 		private int stamp;
+		private bool removed = false;
 
 		public Iterator (PriorityQueue<G> queue) {
 			this.queue = queue;
@@ -774,6 +775,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 			if (!has_next ()) {
 				return false;
 			}
+			removed = false;
 			position = _next;
 			_next = null;
 			return (position != null);
@@ -821,7 +823,7 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 				}
 				from_type2_child = true;
 			}
-			if (_next != queue._r) {
+			if (_next != null && _next != queue._r) {
 				_next = _next.parent;
 				return _has_next ();
 			}
@@ -840,9 +842,22 @@ public class Gee.PriorityQueue<G> : Gee.AbstractQueue<G> {
 		public new G get () {
 			assert (stamp == queue._stamp);
 			assert (position != null);
+			assert (! removed);
 			return position.data;
 		}
 
+		public void remove () {
+			assert (stamp == queue._stamp);
+			assert (position != null);
+			assert (! removed);
+			has_next ();
+			Node<G> node = position;
+			position = null;
+			queue._delete (node);
+			stamp = queue._stamp;
+			removed = true;
+		}
+
 		internal Node<G> get_node () {
 			assert (stamp == queue._stamp);
 			assert (position != null);
diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala
index abaec4e..3fe34ba 100644
--- a/gee/readonlycollection.vala
+++ b/gee/readonlycollection.vala
@@ -70,7 +70,7 @@ internal class Gee.ReadOnlyCollection<G> : Object, Iterable<G>, Collection<G> {
 	 * @inheritDoc
 	 */
 	public Gee.Iterator<G> iterator () {
-		return _collection.iterator ();
+		return new Iterator<G> (_collection.iterator ());
 	}
 
 	/**
@@ -136,21 +136,31 @@ internal class Gee.ReadOnlyCollection<G> : Object, Iterable<G>, Collection<G> {
 		return _collection.to_array ();
 	}
 
-	private class Iterator<G> : Object, Gee.Iterator<G> {
+	protected class Iterator<G> : Object, Gee.Iterator<G> {
+		protected Gee.Iterator<G> _iter;
+
+		public Iterator (Gee.Iterator<G> iterator) {
+			_iter = iterator;
+		}
+
 		public bool next () {
-			return false;
+			return _iter.next ();
 		}
 
 		public bool has_next () {
-			return false;
+			return _iter.has_next ();
 		}
 
 		public bool first () {
-			return false;
+			return _iter.first ();
+		}
+
+		public new G get () {
+			return _iter.get ();
 		}
 
-		public new G? get () {
-			return null;
+		public void remove () {
+			assert_not_reached ();
 		}
 	}
 
diff --git a/gee/treemap.vala b/gee/treemap.vala
index fe7d4ff..4cb41e8 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -496,6 +496,10 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			return current.key;
 		}
 
+		public void remove () {
+			assert_not_reached ();
+		}
+
 		private weak Node<K, V>? current;
 		private enum State {
 			BEFORE_THE_BEGIN,
@@ -551,6 +555,10 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			return current.value;
 		}
 
+		public void remove () {
+			assert_not_reached ();
+		}
+
 		private weak Node<K, V>? current;
 		private enum State {
 			BEFORE_THE_BEGIN,
diff --git a/gee/treeset.vala b/gee/treeset.vala
index ba047b3..6b13e78 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -377,6 +377,17 @@ public class Gee.TreeSet<G> : AbstractSet<G> {
 			return current.key;
 		}
 
+		public void remove () {
+			assert (stamp == _set.stamp);
+			assert (current != null);
+			_next = current.next;
+			_prev = current.prev;
+			_set.remove (get ());
+			stamp++;
+			current = null;
+			assert (stamp == _set.stamp);
+		}
+
 		private weak Node<G>? current;
 		private weak Node<G>? _next;
 		private weak Node<G>? _prev;
diff --git a/gee/updatablekeyiterator.vala b/gee/updatablekeyiterator.vala
new file mode 100644
index 0000000..8e7e4de
--- /dev/null
+++ b/gee/updatablekeyiterator.vala
@@ -0,0 +1,41 @@
+/* updatablekeyiterator.vala
+ *
+ * Copyright (C) 2009  Didier Villevalois
+ *
+ * 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:
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
+ */
+
+/**
+ * An updatable key iterator.
+ */
+internal interface Gee.UpdatableKeyIterator<K,V> : GLib.Object, Iterator<K> {
+	/**
+	 * Returns the value associated with the current key in the iteration.
+	 *
+	 * @return the value for the current key
+	 */
+	public abstract V get_value ();
+
+	/**
+	 * Sets the value associated with the current key in the iteration.
+	 *
+	 * @param value the new value for the current key
+	 */
+	public abstract void set_value (V value);
+}
+
diff --git a/tests/testcollection.vala b/tests/testcollection.vala
index 295bb2c..7f26259 100644
--- a/tests/testcollection.vala
+++ b/tests/testcollection.vala
@@ -32,6 +32,7 @@ public abstract class CollectionTests : Gee.TestCase {
 		add_test ("[Collection] type correctness", test_type_correctness);
 		add_test ("[Collection] iterator returns all elements once",
 		          test_iterator_returns_all_elements_once);
+		add_test ("[Collection] mutable iterator", test_mutable_iterator);
 		add_test ("[Collection] contains, size and is_empty",
 		          test_contains_size_and_is_empty);
 		add_test ("[Collection] add_all", test_add_all);
@@ -155,6 +156,106 @@ public abstract class CollectionTests : Gee.TestCase {
 		assert (three_found_once);
 	}
 
+	public void test_mutable_iterator () {
+		// Check the collection exists
+		assert (test_collection != null);
+		bool has_next;
+
+		// Check with an empty collection
+		Iterator<string> iterator = test_collection.iterator ();
+		// ...
+
+		// Check for some elements in the collection and remove one
+		assert (test_collection.add ("one"));
+		assert (test_collection.add ("two"));
+		assert (test_collection.add ("three"));
+
+		bool one_found = false;
+		bool two_found = false;
+		bool three_found = false;
+		bool one_found_once = true;
+		bool two_found_once = true;
+		bool three_found_once = true;
+		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;
+
+				// Remove this element
+				iterator.remove ();
+			} 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);
+
+		// Check after removal
+		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;
+				}
+				one_found = true;
+			} else if (element == "two") {
+				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 == 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);
+		assert (three_found);
+		assert (three_found_once);
+	}
+
 	public void test_contains_size_and_is_empty () {
 		// Check the collection exists
 		assert (test_collection != null);
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]