GNOME.org
 

[libgee] Introduce MapIterator<K, V> and implement it in HashMap and TreeMap

commit 3212acd739671301b2a9bef681627ac8b8f854f1
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Wed Sep 23 22:33:04 2009 +0200

    Introduce MapIterator<K,V> and implement it in HashMap and TreeMap

 gee/Makefile.am               |    2 +-
 gee/abstractmap.vala          |    5 ++
 gee/hashmap.vala              |   19 +++++----
 gee/hashmultiset.vala         |    8 ++--
 gee/map.vala                  |    7 +++
 gee/mapiterator.vala          |   84 +++++++++++++++++++++++++++++++++++++++++
 gee/readonlymap.vala          |   42 ++++++++++++++++++++
 gee/treemap.vala              |   52 +++++++++++++++++++++++++-
 gee/updatablekeyiterator.vala |   41 --------------------
 9 files changed, 205 insertions(+), 55 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 58cd296..96fb3e3 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -35,6 +35,7 @@ libgee_la_VALASOURCES = \
 	list.vala \
 	listiterator.vala \
 	map.vala \
+	mapiterator.vala \
 	multimap.vala \
 	multiset.vala \
 	priorityqueue.vala \
@@ -47,7 +48,6 @@ libgee_la_VALASOURCES = \
 	timsort.vala \
 	treemap.vala \
 	treeset.vala \
-	updatablekeyiterator.vala \
 	$(NULL)
 
 libgee_la_SOURCES = \
diff --git a/gee/abstractmap.vala b/gee/abstractmap.vala
index 275ceea..a68ceda 100644
--- a/gee/abstractmap.vala
+++ b/gee/abstractmap.vala
@@ -94,6 +94,11 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
 	/**
 	 * @inheritDoc
 	 */
+	public abstract MapIterator<K,V> map_iterator ();
+
+	/**
+	 * @inheritDoc
+	 */
 	public bool remove (K key, out V? value = null) {
 		V removed_value;
 		bool result = unset (key, out removed_value);
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index 0976fa4..7cd87e6 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -140,10 +140,6 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		_nodes = new Node<K,V>[_array_size];
 	}
 
-	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];
@@ -240,6 +236,13 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		resize ();
 	}
 
+	/**
+	 * @inheritDoc
+	 */
+	public override Gee.MapIterator<K,V> map_iterator () {
+		return new MapIterator<K,V> (this);
+	}
+
 	private void resize () {
 		if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 		    (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
@@ -513,18 +516,18 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
-	private class UpdatableKeyIterator<K,V> : NodeIterator<K,V>, Iterator<K>, Gee.UpdatableKeyIterator<K,V> {
-		public UpdatableKeyIterator (HashMap map) {
+	private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V> {
+		public MapIterator (HashMap map) {
 			base (map);
 		}
 
-		public new K get () {
+		public new K get_key () {
 			assert (_stamp == _map._stamp);
 			assert (_node != null);
 			return _node.key;
 		}
 
-		public void remove () {
+		public void unset () {
 			assert (_stamp == _map._stamp);
 			assert (_node != null);
 			has_next ();
diff --git a/gee/hashmultiset.vala b/gee/hashmultiset.vala
index 37f0a3c..0e9cdbb 100644
--- a/gee/hashmultiset.vala
+++ b/gee/hashmultiset.vala
@@ -95,13 +95,13 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
 	private class Iterator<G> : Object, Gee.Iterator<G> {
 		private HashMultiSet<G> _set;
 
-		private Gee.UpdatableKeyIterator<G, int> _iter;
+		private MapIterator<G, int> _iter;
 		private int _pending = 0;
 		private bool _removed = false;
 
 		public Iterator (HashMultiSet<G> set) {
 			_set = set;
-			_iter = _set._items.updatable_key_iterator ();
+			_iter = _set._items.map_iterator ();
 		}
 
 		public bool next () {
@@ -135,14 +135,14 @@ public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
 
 		public new G get () {
 			assert (! _removed);
-			return _iter.get ();
+			return _iter.get_key ();
 		}
 
 		public void remove () {
 			assert (! _removed);
 			_iter.set_value (_pending = _iter.get_value () - 1);
 			if (_pending == 0) {
-				_iter.remove ();
+				_iter.unset ();
 			}
 			_removed = true;
 		}
diff --git a/gee/map.vala b/gee/map.vala
index 733c2c1..bdcbd53 100644
--- a/gee/map.vala
+++ b/gee/map.vala
@@ -139,6 +139,13 @@ public interface Gee.Map<K,V> : GLib.Object {
 	public abstract void clear ();
 
 	/**
+	 * Returns an iterator for this map.
+	 *
+	 * @return a map iterator
+	 */
+	public abstract MapIterator<K,V> map_iterator ();
+
+	/**
 	 * Inserts all items that are contained in the input map to this map.
 	 *
 	 * @param map the map which items are inserted to this map
diff --git a/gee/mapiterator.vala b/gee/mapiterator.vala
new file mode 100644
index 0000000..edb9b75
--- /dev/null
+++ b/gee/mapiterator.vala
@@ -0,0 +1,84 @@
+/* mapiterator.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 iterator over a map.
+ *
+ * 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.MapIterator<K,V> : GLib.Object {
+	/**
+	 * Advances to the next entry in the iteration.
+	 *
+	 * @return true if the iterator has a next entry
+	 */
+	public abstract bool next ();
+
+	/**
+	 * Checks whether there is a next entry in the iteration.
+	 *
+	 * @return true if the iterator has a next entry
+	 */
+	public abstract bool has_next ();
+
+	/**
+	 * Rewinds to the first entry in the iteration.
+	 *
+	 * @return true if the iterator has a first entry
+	 */
+	public abstract bool first ();
+
+	/**
+	 * Returns the current key in the iteration.
+	 *
+	 * @return the current key in the iteration
+	 */
+	public abstract K get_key ();
+
+	/**
+	 * 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);
+
+	/**
+	 * Unsets the current entry in the iteration. The cursor is set in an
+	 * in-between state. Both { link get} and { link unset} will fail until
+	 * the next move of the cursor (calling { link next} or { link first}).
+	 */
+	public abstract void unset ();
+}
+
diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala
index 0163c9a..6241853 100644
--- a/gee/readonlymap.vala
+++ b/gee/readonlymap.vala
@@ -142,6 +142,13 @@ internal class Gee.ReadOnlyMap<K,V> : Object, Map<K,V> {
 	}
 
 	/**
+	 * @inheritDoc
+	 */
+	public Gee.MapIterator<K,V> map_iterator () {
+		return new MapIterator<K,V> (_map.map_iterator ());
+	}
+
+	/**
 	 * Unimplemented method (read only map).
 	 */
 	public void set_all (Map<K,V> map) {
@@ -180,5 +187,40 @@ internal class Gee.ReadOnlyMap<K,V> : Object, Map<K,V> {
 		owned get { return this; }
 	}
 
+	protected class MapIterator<K,V> : Object, Gee.MapIterator<K,V> {
+		protected Gee.MapIterator<K,V> _iter;
+
+		public MapIterator (Gee.MapIterator<K,V> iterator) {
+			_iter = iterator;
+		}
+
+		public bool next () {
+			return _iter.next ();
+		}
+
+		public bool has_next () {
+			return _iter.has_next ();
+		}
+
+		public bool first () {
+			return _iter.first ();
+		}
+
+		public K get_key () {
+			return _iter.get_key ();
+		}
+
+		public V get_value () {
+			return _iter.get_value ();
+		}
+
+		public void set_value (V value) {
+			assert_not_reached ();
+		}
+
+		public void unset () {
+			assert_not_reached ();
+		}
+	}
 }
 
diff --git a/gee/treemap.vala b/gee/treemap.vala
index 6a9b574..facecec 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -352,6 +352,13 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		stamp++;
 	}
 
+	/**
+	 * @inheritDoc
+	 */
+	public override Gee.MapIterator<K,V> map_iterator () {
+		return new MapIterator<K,V> (this);
+	}
+
 	[Compact]
 	private class Node<K, V> {
 		public enum Color {
@@ -582,7 +589,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			stamp = _map.stamp;
 		}
 
-		public bool next () {
+		public virtual bool next () {
 			assert (stamp == _map.stamp);
 			if (current != null) {
 				if (current.next != null) {
@@ -681,4 +688,47 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 			assert_not_reached ();
 		}
 	}
+
+	private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V> {
+		private bool removed = false;
+
+		public MapIterator (TreeMap<K,V> map) {
+			base (map);
+		}
+
+		public override bool next () {
+			removed = false;
+			return base.next ();
+		}
+
+		public K get_key () {
+			assert (! removed);
+			assert (stamp == _map.stamp);
+			assert (current != null);
+			return current.key;
+		}
+
+		public V get_value () {
+			assert (! removed);
+			assert (stamp == _map.stamp);
+			assert (current != null);
+			return current.value;
+		}
+
+		public void set_value (V value) {
+			assert (! removed);
+			assert (stamp == _map.stamp);
+			assert (current != null);
+			current.value = value;
+		}
+
+		public void unset () {
+			assert (stamp == _map.stamp);
+			assert (current != null);
+			_map.unset (current.key);
+			removed = true;
+			stamp++;
+			assert (stamp == _map.stamp);
+		}
+	}
 }
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]