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

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

commit ca8d154e9eee12e704ef296b09e73ee82741427e
Author: Ali Sabil <ali sabil gmail com>
Date:   Sun Sep 6 20:35:53 2009 +0200

    Introduce the MultiSet interface and its hash based implementation

 gee/Makefile.am             |    2 +
 gee/hashmultiset.vala       |  127 +++++++++++++++++++++++++++++++++++++++++++
 gee/multiset.vala           |   34 ++++++++++++
 tests/Makefile.am           |    2 +
 tests/testhashmultiset.vala |   53 ++++++++++++++++++
 tests/testmain.vala         |    1 +
 tests/testmultiset.vala     |   75 +++++++++++++++++++++++++
 7 files changed, 294 insertions(+), 0 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 26228b1..439801b 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -20,12 +20,14 @@ libgee_la_VALASOURCES = \
 	collection.vala \
 	functions.vala \
 	hashmap.vala \
+	hashmultiset.vala \
 	hashset.vala \
 	iterable.vala \
 	iterator.vala \
 	linkedlist.vala \
 	list.vala \
 	map.vala \
+	multiset.vala \
 	readonlycollection.vala \
 	readonlylist.vala \
 	readonlymap.vala \
diff --git a/gee/hashmultiset.vala b/gee/hashmultiset.vala
new file mode 100644
index 0000000..123ea32
--- /dev/null
+++ b/gee/hashmultiset.vala
@@ -0,0 +1,127 @@
+/* hashmultiset.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 hash based implementation of the { link Gee.MultiSet} interface.
+ */
+public class Gee.HashMultiSet<G> : AbstractCollection<G>, MultiSet<G> {
+	public override int size {
+		get { return _nitems; }
+	}
+
+	public HashFunc hash_func {
+		get { return _items.key_hash_func; }
+	}
+
+	public EqualFunc equal_func {
+		get { return _items.key_equal_func; }
+	}
+
+	private HashMap<G, int> _items;
+	private int _nitems = 0;
+
+	/**
+	 * Constructs a new, empty hash multi set.
+	 */
+	public HashMultiSet (HashFunc? hash_func = null, EqualFunc? equal_func = null) {
+		this._items = new HashMap<G, int> (hash_func, equal_func, int_equal);
+	}
+
+	public int count (G item) {
+		int result = 0;
+		if (_items.contains (item)) {
+			result = _items.get (item);
+		}
+		return result;
+	}
+
+	public override bool contains (G item) {
+		return _items.contains (item);
+	}
+
+	public override Gee.Iterator<G> iterator () {
+		return new Iterator<G> (this);
+	}
+
+	public override bool add (G item) {
+		if (_items.contains (item)) {
+			int current_count = _items.get (item);
+			_items.set (item, current_count + 1);
+		} else {
+			_items.set (item, 1);
+		}
+		_nitems++;
+		return true;
+	}
+
+	public override bool remove (G item) {
+		if (_nitems > 0 && _items.contains (item)) {
+			int current_count = _items.get (item);
+			if (current_count <= 1) {
+				_items.remove (item);
+			} else {
+				_items.set (item, current_count - 1);
+			}
+			_nitems--;
+			return true;
+		}
+		return false;
+	}
+
+	public override void clear () {
+		_items.clear ();
+		_nitems = 0;
+	}
+
+	private class Iterator<G> : Object, Gee.Iterator<G> {
+		public new HashMultiSet<G> set { construct; get; }
+
+		private Gee.Iterator<G> _iter;
+		private int _pending = 0;
+
+		construct {
+			_iter = set._items.get_keys ().iterator ();
+		}
+
+		public Iterator (HashMultiSet<G> set) {
+			this.set = set;
+		}
+
+		public bool next () {
+			if (_pending == 0) {
+				if (_iter.next ()) {
+					var key = _iter.get ();
+					_pending = set._items.get (key) - 1;
+					return true;
+				}
+			} else {
+				_pending--;
+				return true;
+			}
+			return false;
+		}
+
+		public new G? get () {
+			return _iter.get ();
+		}
+	}
+}
diff --git a/gee/multiset.vala b/gee/multiset.vala
new file mode 100644
index 0000000..85d44be
--- /dev/null
+++ b/gee/multiset.vala
@@ -0,0 +1,34 @@
+/* multiset.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 MultiSet is a collection allowing duplicates.
+ */
+public interface Gee.MultiSet<G> : Collection<G> {
+	/**
+	 * Returns the number of occurences of an item in this MultiSet
+	 *
+	 * @param item the item to count occurences of
+	 * @return the number of occurences of the item in this multiset.
+	 */
+	public abstract int count (G item);
+}
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 14b575c..df457d5 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,9 +18,11 @@ tests_VALASOURCES = \
        testarraylist.vala \
        testcase.vala \
        testcollection.vala \
+       testhashmultiset.vala \
        testlinkedlist.vala \
        testlist.vala \
        testmain.vala \
+       testmultiset.vala \
        $(NULL)
 
 tests_SOURCES = tests.vala.stamp $(tests_VALASOURCES:.vala=.c)
diff --git a/tests/testhashmultiset.vala b/tests/testhashmultiset.vala
new file mode 100644
index 0000000..869d70e
--- /dev/null
+++ b/tests/testhashmultiset.vala
@@ -0,0 +1,53 @@
+/* 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 HashMultiSetTests : MultiSetTests {
+
+	public HashMultiSetTests () {
+		base ("HashMultiSet");
+		add_test ("[HashMultiSet] selected functions", test_selected_functions);
+	}
+
+	public override void set_up () {
+		test_collection = new HashMultiSet<string> ();
+	}
+
+	public override void tear_down () {
+		test_collection = null;
+	}
+
+	private void test_selected_functions () {
+		var test_multi_set = test_collection as HashMultiSet<string>;
+
+		// Check the collection exists
+		assert (test_multi_set != null);
+
+		// Check the selected hash and equal functions
+		assert (test_multi_set.hash_func == str_hash);
+		assert (test_multi_set.equal_func == str_equal);
+	}
+}
diff --git a/tests/testmain.vala b/tests/testmain.vala
index e9720ff..b675e2b 100644
--- a/tests/testmain.vala
+++ b/tests/testmain.vala
@@ -26,6 +26,7 @@ void main (string[] 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 HashMultiSetTests ().get_suite ());
 
 	Test.run ();
 }
diff --git a/tests/testmultiset.vala b/tests/testmultiset.vala
new file mode 100644
index 0000000..df6b823
--- /dev/null
+++ b/tests/testmultiset.vala
@@ -0,0 +1,75 @@
+/* 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 MultiSetTests : CollectionTests {
+
+	public MultiSetTests (string name) {
+		base (name);
+		add_test ("[MultiSet] duplicates are retained",
+		          test_duplicates_are_retained);
+	}
+
+	private void test_duplicates_are_retained () {
+		var test_multi_set = test_collection as MultiSet<string>;
+
+		// Check the test set is not null
+		assert (test_multi_set != null);
+
+		assert (test_multi_set.count ("one") == 0);
+
+		assert (test_multi_set.add ("one"));
+		assert (test_multi_set.contains ("one"));
+		assert (test_multi_set.size == 1);
+		assert (test_multi_set.count ("one") == 1);
+
+		assert (test_multi_set.add ("one"));
+		assert (test_multi_set.contains ("one"));
+		assert (test_multi_set.size == 2);
+		assert (test_multi_set.count ("one") == 2);
+
+		assert (test_multi_set.add ("one"));
+		assert (test_multi_set.contains ("one"));
+		assert (test_multi_set.size == 3);
+		assert (test_multi_set.count ("one") == 3);
+
+		assert (test_multi_set.remove ("one"));
+		assert (test_multi_set.contains ("one"));
+		assert (test_multi_set.size == 2);
+		assert (test_multi_set.count ("one") == 2);
+
+		assert (test_multi_set.remove ("one"));
+		assert (test_multi_set.contains ("one"));
+		assert (test_multi_set.size == 1);
+		assert (test_multi_set.count ("one") == 1);
+
+		assert (test_multi_set.remove ("one"));
+		assert (!test_multi_set.contains ("one"));
+		assert (test_multi_set.size == 0);
+		assert (test_multi_set.count ("one") == 0);
+	}
+}