[libgee] Introduce the MultiMap interface and its hash based implementation

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

commit 0bcddda2f1f00f609ee1916a4acbda15cded167c
Author: Ali Sabil <ali sabil gmail com>
Date:   Sun Sep 6 21:24:35 2009 +0200

    Introduce the MultiMap interface and its hash based implementation

 gee/Makefile.am             |    2 +
 gee/hashmultimap.vala       |  143 +++++++++++++++++++++++++++++++++++++++++++
 gee/multimap.vala           |  103 +++++++++++++++++++++++++++++++
 tests/Makefile.am           |    2 +
 tests/testhashmultimap.vala |   55 ++++++++++++++++
 tests/testmain.vala         |    3 +-
 tests/testmultimap.vala     |   81 ++++++++++++++++++++++++
 7 files changed, 388 insertions(+), 1 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 439801b..32567e4 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -20,6 +20,7 @@ libgee_la_VALASOURCES = \
 	collection.vala \
 	functions.vala \
 	hashmap.vala \
+	hashmultimap.vala \
 	hashmultiset.vala \
 	hashset.vala \
 	iterable.vala \
@@ -27,6 +28,7 @@ libgee_la_VALASOURCES = \
 	linkedlist.vala \
 	list.vala \
 	map.vala \
+	multimap.vala \
 	multiset.vala \
 	readonlycollection.vala \
 	readonlylist.vala \
diff --git a/gee/hashmultimap.vala b/gee/hashmultimap.vala
new file mode 100644
index 0000000..14dbb97
--- /dev/null
+++ b/gee/hashmultimap.vala
@@ -0,0 +1,143 @@
+/* hashmultimap.vala
+ *
+ * Copyright (C) 2009  Ali Sabil
+ *
+ * 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:
+ * 	Ali Sabil <ali sabil gmail com>
+ */
+
+/**
+ * A MultiMap implemented using a HashMap of Sets
+ */
+public class Gee.HashMultiMap<K,V> : GLib.Object, MultiMap<K,V> {
+	public int size {
+		get { return _nitems; }
+	}
+
+	public HashFunc key_hash_func { private set; get; }
+
+	public EqualFunc key_equal_func { private set; get; }
+
+	public HashFunc value_hash_func { private set; get; }
+
+	public EqualFunc value_equal_func { private set; get; }
+
+	private Map<K, Collection<V>> _items;
+	private int _nitems = 0;
+	private Set<V> _empty_value_set;
+
+	public HashMultiMap (HashFunc? key_hash_func = null, EqualFunc? key_equal_func = null, HashFunc? value_hash_func = null, EqualFunc? value_equal_func = null) {
+		if (key_hash_func == null) {
+			key_hash_func = Functions.get_hash_func_for (typeof (K));
+		}
+		if (key_equal_func == null) {
+			key_equal_func = Functions.get_equal_func_for (typeof (K));
+		}
+		if (value_hash_func == null) {
+			value_hash_func = Functions.get_hash_func_for (typeof (V));
+		}
+		if (value_equal_func == null) {
+			value_equal_func = Functions.get_equal_func_for (typeof (V));
+		}
+		this.key_hash_func = key_hash_func;
+		this.key_equal_func = key_equal_func;
+		this.value_hash_func = value_hash_func;
+		this.value_equal_func = value_equal_func;
+		this._items = new HashMap<K, Set<V>> (key_hash_func, key_equal_func, direct_equal);
+		this._empty_value_set = new ReadOnlySet<V> (new HashSet<V> (_value_hash_func, _value_equal_func));
+	}
+
+	public Set<K> get_keys () {
+		return _items.get_keys ();
+	}
+
+	public MultiSet<K> get_all_keys () {
+		MultiSet<K> result = new HashMultiSet<K> (_key_hash_func, _key_equal_func);
+		foreach (var key in _items.get_keys ()) {
+			for (int i = 0; i < _items.get (key).size; i++) {
+				result.add (key);
+			}
+		}
+		return result;
+	}
+
+	public Collection<V> get_values () {
+		var result = new ArrayList<V> (_value_equal_func);
+		foreach (var key in _items.get_keys ()) {
+			foreach (var value in _items.get (key)) {
+				result.add (value);
+			}
+		}
+		return result;
+	}
+
+	public bool contains (K key) {
+		return _items.contains (key);
+	}
+
+	public new Collection<V> get (K key) {
+		if (_items.contains (key)) {
+			return new ReadOnlyCollection<V> (_items.get (key));
+		} else {
+			return _empty_value_set;
+		}
+	}
+
+	public new void set (K key, V value) {
+		if (_items.contains (key)) {
+			if (_items.get (key).add (value)) {
+				_nitems++;
+			}
+		} else {
+			var s = new HashSet<V> (_value_hash_func, _value_equal_func);
+			s.add (value);
+			_items.set (key, s);
+			_nitems++;
+		}
+	}
+
+	public bool remove (K key, V value) {
+		if (_items.contains (key)) {
+			var values = _items.get (key);
+			if (values.contains (value)) {
+				values.remove (value);
+				_nitems--;
+				if (values.size == 0) {
+					_items.remove (key);
+				}
+				return true;
+			}
+		}
+		return false;
+	}
+
+	public bool remove_all (K key) {
+		if (_items.contains (key)) {
+			int size = _items.get (key).size;
+			if (_items.remove (key)) {
+				_nitems -= size;
+				return true;
+			}
+		}
+		return false;
+	}
+
+	public void clear () {
+		_items.clear ();
+		_nitems = 0;
+	}
+}
diff --git a/gee/multimap.vala b/gee/multimap.vala
new file mode 100644
index 0000000..757b535
--- /dev/null
+++ b/gee/multimap.vala
@@ -0,0 +1,103 @@
+/* multimap.vala
+ *
+ * Copyright (C) 2009  Ali Sabil
+ *
+ * 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:
+ * 	Ali Sabil <ali sabil gmail com>
+ */
+
+/**
+ * A MultiMap is a map where you can associate multiple values to the
+ * same key.
+ */
+public interface Gee.MultiMap<K,V> : GLib.Object {
+	/**
+	 * The number of key/value pairs in this map.
+	 */
+	public abstract int size { get; }
+
+	/**
+	 * Returns the keys of this multimap as a read-only set.
+	 *
+	 * @return the keys of the map
+	 */
+	public abstract Set<K> get_keys ();
+
+	/**
+	 * Returns the keys of this multimap as a read-only set.
+	 *
+	 * @return the keys of the map
+	 */
+	public abstract MultiSet<K> get_all_keys ();
+
+	/**
+	 * Returns the values of this map as a read-only collection.
+	 *
+	 * @return the values of the map
+	 */
+	public abstract Collection<V> get_values ();
+
+	/**
+	 * Determines whether this map contains the specified key.
+	 *
+	 * @param key the key to locate in the map
+	 *
+	 * @return    true if key is found, false otherwise
+	 */
+	public abstract bool contains (K key);
+
+	/**
+	 * Returns the values for the specified key in this map.
+	 *
+	 * @param key the key whose values are to be retrieved
+	 *
+	 * @return    a Collection of values associated with the given key
+	 */
+	public abstract Collection<V> get (K key);
+
+	/**
+	 * Inserts a key/value pair into this map.
+	 *
+	 * @param key   the key to insert
+	 * @param value the value to associate with the key
+	 */
+	public abstract void set (K key, V value);
+
+	/**
+	 * Removes the specified key/value pair from this multimap.
+	 *
+	 * @param key   the key to remove from the map
+	 * @param value the value to remove from the map
+	 *
+	 * @return    true if the map has been changed, false otherwise
+	 */
+	public abstract bool remove (K key, V value);
+
+	/**
+	 * Removes the specified key and all the associated values from this multimap.
+	 *
+	 * @param key   the key to remove from the map
+	 *
+	 * @return    true if the map has been changed, false otherwise
+	 */
+	public abstract bool remove_all (K key);
+
+	/**
+	 * Removes all items from this collection.
+	 */
+	public abstract void clear ();
+}
diff --git a/tests/Makefile.am b/tests/Makefile.am
index df457d5..9007792 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,10 +18,12 @@ tests_VALASOURCES = \
        testarraylist.vala \
        testcase.vala \
        testcollection.vala \
+       testhashmultimap.vala \
        testhashmultiset.vala \
        testlinkedlist.vala \
        testlist.vala \
        testmain.vala \
+       testmultimap.vala \
        testmultiset.vala \
        $(NULL)
 
diff --git a/tests/testhashmultimap.vala b/tests/testhashmultimap.vala
new file mode 100644
index 0000000..4b2cbb0
--- /dev/null
+++ b/tests/testhashmultimap.vala
@@ -0,0 +1,55 @@
+/* testarraylist.vala
+ *
+ * Copyright (C) 2008  Jürg Billeter
+ * Copyright (C) 2009  Didier Villevalois, Julien Peeters
+ *
+ * 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:
+ * 	Jürg Billeter <j bitron ch>
+ * 	Didier 'Ptitjes Villevalois <ptitjes free fr>
+ * 	Julien Peeters <contact julienpeeters fr>
+ */
+
+using Gee;
+
+public class HashMultiMapTests : MultiMapTests {
+
+	public HashMultiMapTests () {
+		base ("HashMultiMap");
+		add_test ("[HashMultiMap] selected functions", test_selected_functions);
+	}
+
+	public override void set_up () {
+		test_multi_map = new HashMultiMap<string,string> ();
+	}
+
+	public override void tear_down () {
+		test_multi_map = null;
+	}
+
+	private void test_selected_functions () {
+		var test_hash_multi_map = test_multi_map as HashMultiMap<string,string>;
+
+		// Check the map exists
+		assert (test_hash_multi_map != null);
+
+		// Check the selected hash and equal functions
+		assert (test_hash_multi_map.key_hash_func == str_hash);
+		assert (test_hash_multi_map.key_equal_func == str_equal);
+		assert (test_hash_multi_map.value_hash_func == str_hash);
+		assert (test_hash_multi_map.value_equal_func == str_equal);
+	}
+}
diff --git a/tests/testmain.vala b/tests/testmain.vala
index b675e2b..ec916f4 100644
--- a/tests/testmain.vala
+++ b/tests/testmain.vala
@@ -25,8 +25,9 @@ void main (string[] args) {
 	Test.init (ref args);
 
 	TestSuite.get_root ().add_suite (new ArrayListTests ().get_suite ());
-	TestSuite.get_root ().add_suite (new LinkedListTests ().get_suite ());
+	TestSuite.get_root ().add_suite (new HashMultiMapTests ().get_suite ());
 	TestSuite.get_root ().add_suite (new HashMultiSetTests ().get_suite ());
+	TestSuite.get_root ().add_suite (new LinkedListTests ().get_suite ());
 
 	Test.run ();
 }
diff --git a/tests/testmultimap.vala b/tests/testmultimap.vala
new file mode 100644
index 0000000..61de75e
--- /dev/null
+++ b/tests/testmultimap.vala
@@ -0,0 +1,81 @@
+/* testlist.vala
+ *
+ * Copyright (C) 2008  Jürg Billeter
+ * Copyright (C) 2009  Didier Villevalois, Julien Peeters
+ *
+ * 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:
+ * 	Jürg Billeter <j bitron ch>
+ * 	Didier 'Ptitjes' Villevalois <ptitjes free fr>
+ * 	Julien Peeters <contact julienpeeters fr>
+ */
+
+using GLib;
+using Gee;
+
+public abstract class MultiMapTests : Gee.TestCase {
+
+	public MultiMapTests (string name) {
+		base (name);
+		add_test ("[MultiMap] size", test_size);
+		add_test ("[MultiMap] getting and setting", test_getting_setting);
+	}
+
+	protected MultiMap<string,string> test_multi_map;
+
+	private void test_size () {
+		// Check the map exists
+		assert (test_multi_map != null);
+
+		assert (test_multi_map.size == 0);
+		test_multi_map.set ("0", "0");
+		assert (test_multi_map.size == 1);
+		test_multi_map.set ("0", "1");
+		assert (test_multi_map.size == 2);
+		test_multi_map.remove ("0", "1");
+		assert (test_multi_map.size == 1);
+		test_multi_map.set ("0", "1");
+		test_multi_map.remove_all ("0");
+		assert (test_multi_map.size == 0);
+		test_multi_map.set ("0", "0");
+		assert (test_multi_map.size == 1);
+		test_multi_map.set ("1", "1");
+		assert (test_multi_map.size == 2);
+	}
+
+	private void test_getting_setting () {
+		// Check the map exists
+		assert (test_multi_map != null);
+
+		test_multi_map.set ("0", "0");
+		assert (test_multi_map.get ("0").size == 1);
+		assert (test_multi_map.get ("0").contains ("0"));
+
+		assert (test_multi_map.get ("1").size == 0);
+
+		test_multi_map.set ("0", "1");
+		assert (test_multi_map.get ("0").size == 2);
+		assert (test_multi_map.get ("0").contains ("0"));
+		assert (test_multi_map.get ("0").contains ("1"));
+
+		test_multi_map.set ("1", "1");
+		assert (test_multi_map.get ("0").size == 2);
+		assert (test_multi_map.get ("0").contains ("0"));
+		assert (test_multi_map.get ("0").contains ("1"));
+		assert (test_multi_map.get ("1").size == 1);
+		assert (test_multi_map.get ("0").contains ("1"));
+	}
+}