[libgee] Introduce the Map.Entry<K, V> class and the Map.entries property

[Didier Villevalois <dvillevalois src gnome org>]

commit 93ab6ba6e32056ef9f15ff8ce844143c207c99b6
Author: Didier 'Ptitjes <ptitjes free fr>
Date:   Sun Sep 20 16:25:17 2009 +0200

    Introduce the Map.Entry<K,V> class and the Map.entries property
    
    We also use Map.entries to optimize the implementations of
    set_all, has_all and HashMultiMap by avoiding the common pattern:
    iterate on keys and for each key get the associated value.

 gee/abstractmap.vala  |   13 +++-
 gee/hashmap.vala      |   96 ++++++++++++++++++++++++++++++
 gee/hashmultimap.vala |   10 ++--
 gee/map.vala          |   20 ++++++
 gee/readonlymap.vala  |    9 +++
 gee/treemap.vala      |  155 +++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 294 insertions(+), 9 deletions(-)
---
diff --git a/gee/abstractmap.vala b/gee/abstractmap.vala
index e753795..275ceea 100644
--- a/gee/abstractmap.vala
+++ b/gee/abstractmap.vala
@@ -57,6 +57,11 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
 	/**
 	 * @inheritDoc
 	 */
+	public abstract Set<Map.Entry<K,V>> entries { owned get; }
+
+	/**
+	 * @inheritDoc
+	 */
 	public abstract bool has_key (K key);
 
 	/**
@@ -107,8 +112,8 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
 	 * @inheritDoc
 	 */
 	public virtual void set_all (Map<K,V> map) {
-		foreach (K key in map.keys) {
-			set (key, map.get (key));
+		foreach (Map.Entry<K,V> entry in map.entries) {
+			set (entry.key, entry.value);
 		}
 	}
 
@@ -134,8 +139,8 @@ public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
 	 * @inheritDoc
 	 */
 	public virtual bool has_all (Map<K,V> map) {
-		foreach (K key in map.keys) {
-			if (!has (key, map.get (key))) {
+		foreach (Map.Entry<K,V> entry in map.entries) {
+			if (!has (entry.key, entry.value)) {
 				return false;
 			}
 		}
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index 31e359e..300dead 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -60,6 +60,15 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 	}
 
 	/**
+	 * @inheritDoc
+	 */
+	public override Set<Map.Entry<K,V>> entries {
+		owned get {
+			return new EntrySet<K,V> (this);
+		}
+	}
+
+	/**
 	 * The keys' hash function.
 	 */
 	public HashFunc key_hash_func { private set; get; }
@@ -242,11 +251,38 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		public V value;
 		public Node<K,V> next;
 		public uint key_hash;
+		public unowned Map.Entry<K,V>? entry;
 
 		public Node (owned K k, owned V v, uint hash) {
 			key = (owned) k;
 			value = (owned) v;
 			key_hash = hash;
+			 entry = null;
+		}
+	}
+
+	private class Entry<K,V> : Map.Entry<K,V> {
+		private unowned Node<K,V> _node;
+
+		public static Map.Entry<K,V> entry_for<K,V> (Node<K,V> node) {
+			Map.Entry<K,V> result = node.entry;
+			if (node.entry == null) {
+				result = new Entry<K,V> (node);
+				node.entry = result;
+				result.add_weak_pointer (&node.entry);
+			}
+			return result;
+		}
+
+		public Entry (Node<K,V> node) {
+			_node = node;
+		}
+
+		public override K key { get { return _node.key; } }
+
+		public override V value {
+			get { return _node.value; }
+			set { _node.value = value; }
 		}
 	}
 
@@ -345,6 +381,50 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
+	private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
+		private HashMap<K,V> _map;
+
+		public EntrySet (HashMap<K,V> map) {
+			_map = map;
+		}
+
+		public override Iterator<Map.Entry<K, V>> iterator () {
+			return new EntryIterator<K,V> (_map);
+		}
+
+		public override int size {
+			get { return _map.size; }
+		}
+
+		public override bool add (Map.Entry<K, V> entry) {
+			assert_not_reached ();
+		}
+
+		public override void clear () {
+			assert_not_reached ();
+		}
+
+		public override bool remove (Map.Entry<K, V> entry) {
+			assert_not_reached ();
+		}
+
+		public override bool contains (Map.Entry<K, V> entry) {
+			return _map.has (entry.key, entry.value);
+		}
+
+		public override bool add_all (Collection<Map.Entry<K, V>> entries) {
+			assert_not_reached ();
+		}
+
+		public override bool remove_all (Collection<Map.Entry<K, V>> entries) {
+			assert_not_reached ();
+		}
+
+		public override bool retain_all (Collection<Map.Entry<K, V>> entries) {
+			assert_not_reached ();
+		}
+	}
+
 	private abstract class NodeIterator<K,V> : Object {
 		protected HashMap<K,V> _map;
 		private int _index = -1;
@@ -460,5 +540,21 @@ public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
 			assert_not_reached ();
 		}
 	}
+
+	private class EntryIterator<K,V> : NodeIterator<K,V>, Iterator<Map.Entry<K,V>> {
+		public EntryIterator (HashMap map) {
+			base (map);
+		}
+
+		public new Map.Entry<K,V> get () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			return Entry<K,V>.entry_for<K,V> (_node);
+		}
+
+		public void remove () {
+			assert_not_reached ();
+		}
+	}
 }
 
diff --git a/gee/hashmultimap.vala b/gee/hashmultimap.vala
index 0c46a10..25fa8ac 100644
--- a/gee/hashmultimap.vala
+++ b/gee/hashmultimap.vala
@@ -67,9 +67,9 @@ public class Gee.HashMultiMap<K,V> : GLib.Object, MultiMap<K,V> {
 
 	public MultiSet<K> get_all_keys () {
 		MultiSet<K> result = new HashMultiSet<K> (_key_hash_func, _key_equal_func);
-		foreach (var key in _items.keys) {
-			for (int i = 0; i < _items.get (key).size; i++) {
-				result.add (key);
+		foreach (var entry in _items.entries) {
+			for (int i = 0; i < entry.value.size; i++) {
+				result.add (entry.key);
 			}
 		}
 		return result;
@@ -77,8 +77,8 @@ public class Gee.HashMultiMap<K,V> : GLib.Object, MultiMap<K,V> {
 
 	public Collection<V> get_values () {
 		var result = new ArrayList<V> (_value_equal_func);
-		foreach (var key in _items.keys) {
-			foreach (var value in _items.get (key)) {
+		foreach (var entry in _items.entries) {
+			foreach (var value in entry.value) {
 				result.add (value);
 			}
 		}
diff --git a/gee/map.vala b/gee/map.vala
index e98e995..733c2c1 100644
--- a/gee/map.vala
+++ b/gee/map.vala
@@ -45,6 +45,26 @@ public interface Gee.Map<K,V> : GLib.Object {
 	public abstract Collection<V> values { owned get; }
 
 	/**
+	 * The read-only view of the entries of this map.
+	 */
+	public abstract Set<Entry<K,V>> entries { owned get; }
+
+	/**
+	 * An entry of a map.
+	 */
+	public abstract class Entry<K,V> : Object {
+		/**
+		 * The key of this entry.
+		 */
+		public abstract K key { get; }
+
+		/**
+		 * The value of this entry.
+		 */
+		public abstract V value { get; set; }
+	}
+
+	/**
 	 * Determines whether this map has the specified key.
 	 *
 	 * @param key the key to locate in the map
diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala
index ddcc47e..0163c9a 100644
--- a/gee/readonlymap.vala
+++ b/gee/readonlymap.vala
@@ -65,6 +65,15 @@ internal class Gee.ReadOnlyMap<K,V> : Object, Map<K,V> {
 		}
 	}
 
+	/**
+	 * @inheritDoc
+	 */
+	public Set<Map.Entry<K,V>> entries {
+		owned get {
+			return _map.entries;
+		}
+	}
+
 	private Map<K,V> _map;
 
 	/**
diff --git a/gee/treemap.vala b/gee/treemap.vala
index d4f807b..32c6a70 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -58,6 +58,15 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 	}
 
 	/**
+	 * @inheritDoc
+	 */
+	public override Set<Map.Entry<K,V>> entries {
+		owned get {
+			return new EntrySet<K,V> (this);
+		}
+	}
+
+	/**
 	 * The keys' comparator function.
 	 */
 	public CompareFunc key_compare_func { private set; get; }
@@ -367,6 +376,7 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		public Node<K, V>? right;
 		public weak Node<K, V>? prev;
 		public weak Node<K, V>? next;
+		public unowned Map.Entry<K,V>? entry;
 	}
 
 	private Node<K, V>? root = null;
@@ -374,6 +384,31 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 	private weak Node<K, V>? last = null;
 	private int stamp = 0;
 
+	private class Entry<K,V> : Map.Entry<K,V> {
+		private unowned Node<K,V> _node;
+
+		public static Map.Entry<K,V> entry_for<K,V> (Node<K,V> node) {
+			Map.Entry<K,V> result = node.entry;
+			if (node.entry == null) {
+				result = new Entry<K,V> (node);
+				node.entry = result;
+				result.add_weak_pointer (&node.entry);
+			}
+			return result;
+		}
+
+		public Entry (Node<K,V> node) {
+			_node = node;
+		}
+
+		public override K key { get { return _node.key; } }
+
+		public override V value {
+			get { return _node.value; }
+			set { _node.value = value; }
+		}
+	}
+
 	private class KeySet<K,V> : AbstractSet<K> {
 		private TreeMap<K,V> _map;
 
@@ -468,6 +503,50 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		}
 	}
 
+	private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
+		private TreeMap<K,V> _map;
+
+		public EntrySet (TreeMap<K,V> map) {
+			_map = map;
+		}
+
+		public override Iterator<Map.Entry<K, V>> iterator () {
+			return new EntryIterator<K,V> (_map);
+		}
+
+		public override int size {
+			get { return _map.size; }
+		}
+
+		public override bool add (Map.Entry<K, V> entry) {
+			assert_not_reached ();
+		}
+
+		public override void clear () {
+			assert_not_reached ();
+		}
+
+		public override bool remove (Map.Entry<K, V> entry) {
+			assert_not_reached ();
+		}
+
+		public override bool contains (Map.Entry<K, V> entry) {
+			return _map.has (entry.key, entry.value);
+		}
+
+		public override bool add_all (Collection<Map.Entry<K, V>> entries) {
+			assert_not_reached ();
+		}
+
+		public override bool remove_all (Collection<Map.Entry<K, V>> entries) {
+			assert_not_reached ();
+		}
+
+		public override bool retain_all (Collection<Map.Entry<K, V>> entries) {
+			assert_not_reached ();
+		}
+	}
+
 	private class KeyIterator<K,V> : Object, Gee.Iterator<K>, BidirIterator<K> {
 		private TreeMap<K,V> _map;
 
@@ -619,4 +698,80 @@ public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
 		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;
+
+		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
+		}
+
+		public new Map.Entry<K,V> get () {
+			assert (stamp == _map.stamp);
+			assert (current != null);
+			return Entry<K,V>.entry_for<K,V> (current);
+		}
+
+		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;
+	}
 }