GNOME.org
 

[libgee] Add Map.is_empty|set_all|remove_all|contains_all and AbstractMap implementations

commit 539ea0cf401afd44861807f8ad3fc39de31de3a7
Author: Tomaž Vajngerl <quikee gmail com>
Date:   Sun Jul 26 12:49:27 2009 +0200

    Add Map.is_empty|set_all|remove_all|contains_all and AbstractMap implementations
    
    Fixes bug 589902.

 gee/Makefile.am        |    1 +
 gee/abstractmap.vala   |   71 +++++++++++++++
 gee/hashmap.vala       |   18 ++--
 gee/map.vala           |   27 ++++++
 gee/readonlymap.vala   |   20 ++++
 gee/treemap.vala       |   18 ++--
 tests/testhashmap.vala |  232 ++++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 369 insertions(+), 18 deletions(-)
---
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 9008f23..72f59a6 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -15,6 +15,7 @@ lib_LTLIBRARIES = \
 libgee_la_VALASOURCES = \
 	abstractcollection.vala \
 	abstractlist.vala \
+	abstractmap.vala \
 	arraylist.vala \
 	collection.vala \
 	functions.vala \
diff --git a/gee/abstractmap.vala b/gee/abstractmap.vala
new file mode 100644
index 0000000..fb17b2a
--- /dev/null
+++ b/gee/abstractmap.vala
@@ -0,0 +1,71 @@
+/* abstractmap.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ * 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:
+ * 	Tomaž Vajngerl <quikee gmail com>
+ */
+ 
+ /**
+ * Serves as the base class for implementing map classes.
+ */
+public abstract class Gee.AbstractMap<K,V> : Object, Map<K,V> {
+
+	public abstract int size { get; }
+
+	public virtual bool is_empty {
+		get { return size == 0; }
+	}
+
+	public abstract Set<K> get_keys ();
+
+	public abstract Collection<V> get_values ();
+
+	public abstract bool contains (K key);
+
+	public abstract new V? get (K key);
+
+	public abstract new void set (K key, V value);
+
+	public abstract bool remove (K key);
+
+	public abstract void clear ();
+
+	public virtual void set_all (Map<K,V> map) {
+		foreach (K key in map.get_keys ()) {
+			set (key, map.get (key));
+		}
+	}
+
+	public virtual bool remove_all (Map<K,V> map) {
+		bool changed = false;
+		foreach (K key in map.get_keys ()) {
+			changed = changed | remove (key);
+		}
+		return changed;
+	}
+
+	public virtual bool contains_all (Map<K,V> map) {
+		foreach (K key in map.get_keys ()) {
+			if (!contains (key)) {
+				return false;
+			}
+		}
+		return true;
+	}
+}
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index 824fae1..8e48328 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -27,8 +27,8 @@ using GLib;
 /**
  * Hashtable implementation of the Map interface.
  */
-public class Gee.HashMap<K,V> : Object, Map<K,V> {
-	public int size {
+public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
+	public override int size {
 		get { return _nnodes; }
 	}
 
@@ -59,11 +59,11 @@ public class Gee.HashMap<K,V> : Object, Map<K,V> {
 		_nodes = new Node<K,V>[_array_size];
 	}
 
-	public Set<K> get_keys () {
+	public override Set<K> get_keys () {
 		return new KeySet<K,V> (this);
 	}
 
-	public Collection<V> get_values () {
+	public override Collection<V> get_values () {
 		return new ValueCollection<K,V> (this);
 	}
 
@@ -76,12 +76,12 @@ public class Gee.HashMap<K,V> : Object, Map<K,V> {
 		return node;
 	}
 
-	public bool contains (K key) {
+	public override bool contains (K key) {
 		Node<K,V>** node = lookup_node (key);
 		return (*node != null);
 	}
 
-	public new V? get (K key) {
+	public override V? get (K key) {
 		Node<K,V>* node = (*lookup_node (key));
 		if (node != null) {
 			return node->value;
@@ -90,7 +90,7 @@ public class Gee.HashMap<K,V> : Object, Map<K,V> {
 		}
 	}
 
-	public new void set (K key, V value) {
+	public override void set (K key, V value) {
 		Node<K,V>** node = lookup_node (key);
 		if (*node != null) {
 			(*node)->value = value;
@@ -103,7 +103,7 @@ public class Gee.HashMap<K,V> : Object, Map<K,V> {
 		_stamp++;
 	}
 
-	public bool remove (K key) {
+	public override bool remove (K key) {
 		Node<K,V>** node = lookup_node (key);
 		if (*node != null) {
 			Node<K,V> next = (owned) (*node)->next;
@@ -122,7 +122,7 @@ public class Gee.HashMap<K,V> : Object, Map<K,V> {
 		return false;
 	}
 
-	public void clear () {
+	public override void clear () {
 		for (int i = 0; i < _array_size; i++) {
 			Node<K,V> node = (owned) _nodes[i];
 			while (node != null) {
diff --git a/gee/map.vala b/gee/map.vala
index 78858ce..9d6996e 100644
--- a/gee/map.vala
+++ b/gee/map.vala
@@ -30,6 +30,11 @@ public interface Gee.Map<K,V> : GLib.Object {
 	public abstract int size { get; }
 
 	/**
+	 * Specifies whether this map is empty.
+	 */
+	public abstract bool is_empty { get; }
+
+	/**
 	 * Returns the keys of this map as a read-only set.
 	 *
 	 * @return the keys of the map
@@ -84,5 +89,27 @@ public interface Gee.Map<K,V> : GLib.Object {
 	 * read-only collections.
 	 */
 	public abstract void clear ();
+
+	/**
+	 * Inserts all items that are contained in the input map to this map.
+	 *
+	 *  @param map the map which items are inserted to this map
+	 */
+	public abstract void set_all (Map<K,V> map);
+
+	/**
+	 * Removes all items from this map that are common to the input map 
+	 * and this map.
+	 *
+	 *  @param map the map which common items are deleted from this map
+	 */
+	public abstract bool remove_all (Map<K,V> map);
+
+	/**
+	 * Returns true it this map contains all items as the input map.
+	 *
+	 * @param map the map which items will be compared with this map.
+	 */
+	public abstract bool contains_all (Map<K,V> map);
 }
 
diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala
index de5632b..37d7730 100644
--- a/gee/readonlymap.vala
+++ b/gee/readonlymap.vala
@@ -30,6 +30,10 @@ public class Gee.ReadOnlyMap<K,V> : Object, Map<K,V> {
 		get { return _map.size; }
 	}
 
+	public bool is_empty {
+		get { return _map.is_empty; }
+	}
+
 	public Map<K,V> map {
 		construct { _map = value; }
 	}
@@ -83,5 +87,21 @@ public class Gee.ReadOnlyMap<K,V> : Object, Map<K,V> {
 	public void clear () {
 		assert_not_reached ();
 	}
+
+	public void set_all (Map<K,V> map) {
+		assert_not_reached ();
+	}
+
+	public bool remove_all (Map<K,V> map) {
+		assert_not_reached ();
+	}
+
+	public bool contains_all (Map<K,V> map) {
+		if (_map == null) {
+			return false;
+		}
+
+		return _map.contains_all (map);
+	}
 }
 
diff --git a/gee/treemap.vala b/gee/treemap.vala
index a819153..a9c1806 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -25,8 +25,8 @@ using GLib;
 /**
  * Left-leaning red-black tree implementation of the Map interface.
  */
-public class Gee.TreeMap<K,V> : Object, Map<K,V> {
-	public int size {
+public class Gee.TreeMap<K,V> : Gee.AbstractMap<K,V> {
+	public override int size {
 		get { return _size; }
 	}
 
@@ -40,11 +40,11 @@ public class Gee.TreeMap<K,V> : Object, Map<K,V> {
 		this.value_equal_func = value_equal_func;
 	}
 
-	public Set<K> get_keys () {
+	public override Set<K> get_keys () {
 		return new KeySet<K,V> (this);
 	}
 
-	public Collection<V> get_values () {
+	public override Collection<V> get_values () {
 		return new ValueCollection<K,V> (this);
 	}
 
@@ -74,7 +74,7 @@ public class Gee.TreeMap<K,V> : Object, Map<K,V> {
 		return n == null || n.color == Node.Color.BLACK;
 	}
 
-	public bool contains (K key) {
+	public override bool contains (K key) {
 		weak Node<K, V>? cur = root;
 		while (cur != null) {
 			int res = key_compare_func (key, cur.key);
@@ -89,7 +89,7 @@ public class Gee.TreeMap<K,V> : Object, Map<K,V> {
 		return false;
 	}
 
-	public new V? get (K key) {
+	public override V? get (K key) {
 		weak Node<K, V>? cur = root;
 		while (cur != null) {
 			int res = key_compare_func (key, cur.key);
@@ -129,7 +129,7 @@ public class Gee.TreeMap<K,V> : Object, Map<K,V> {
 		fix_up (ref node);
 	}
 
-	public new void set (K key, V value) {
+	public override void set (K key, V value) {
 		set_to_node (ref root, key, value, null, null);
 		root.color = Node.Color.BLACK;
 	}
@@ -219,7 +219,7 @@ public class Gee.TreeMap<K,V> : Object, Map<K,V> {
 		}
 	}
 
-	public bool remove (K key) {
+	public override bool remove (K key) {
 		bool b = remove_from_node (ref root, key);
 		if (root != null) {
 			root.color = Node.Color.BLACK;
@@ -228,7 +228,7 @@ public class Gee.TreeMap<K,V> : Object, Map<K,V> {
 		return b;
 	}
 
-	public void clear () {
+	public override void clear () {
 		root = null;
 		_size = 0;
 		stamp++;
diff --git a/tests/testhashmap.vala b/tests/testhashmap.vala
index cba44a6..731d931 100644
--- a/tests/testhashmap.vala
+++ b/tests/testhashmap.vala
@@ -297,9 +297,237 @@ void test_hashmap_clear () {
 	assert (hashmap.size == 0);
 }
 
+void test_hashmap_empty () {
+	var hashmap = new HashMap<string,string> (str_hash, str_equal, str_equal);
+
+	// Check empty map
+	assert (hashmap.is_empty);
+
+	// Check when one item
+	hashmap.set ("1", "1");
+	assert (!hashmap.is_empty);
+
+	// Check when more items
+	hashmap.set ("2", "2");
+	assert (!hashmap.is_empty);
+
+	// Check when items cleared
+	hashmap.clear ();
+	assert (hashmap.is_empty);
+}
+
+void test_hashmap_set_all () {
+	var hashmap1 = new HashMap<string,string> (str_hash, str_equal, str_equal);
+	var hashmap2 = new HashMap<string,string> (str_hash, str_equal, str_equal);
+
+	hashmap1.set ("a", "1");
+	hashmap1.set ("b", "2");
+	hashmap1.set ("c", "3");
+	hashmap2.set ("d", "4");
+	hashmap2.set ("e", "5");
+	hashmap2.set ("f", "6");
+
+	hashmap1.set_all (hashmap2);
+
+	assert (hashmap1.size == 6);
+	assert (hashmap1.contains ("a"));
+	assert (hashmap1.contains ("b"));
+	assert (hashmap1.contains ("c"));
+	assert (hashmap1.contains ("d"));
+	assert (hashmap1.contains ("e"));
+	assert (hashmap1.contains ("f"));
+
+	assert (hashmap1.get ("a") == "1");
+	assert (hashmap1.get ("b") == "2");
+	assert (hashmap1.get ("c") == "3");
+	assert (hashmap1.get ("d") == "4");
+	assert (hashmap1.get ("e") == "5");
+	assert (hashmap1.get ("f") == "6");
+}
+
+void test_hashmap_remove_all () {
+	var map1 = new HashMap<string,string> (str_hash, str_equal, str_equal);
+	var map2 = new HashMap<string,string> (str_hash, str_equal, str_equal);
+	
+	// Check remove all on empty maps.
+
+	assert (map1.is_empty);
+	assert (map2.is_empty);
+
+	map1.remove_all (map2);	
+
+	assert (map1.is_empty);
+	assert (map2.is_empty);
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 is empty, map2 has entries. -> no change
+
+	map2.set ("a", "1");
+	map2.set ("b", "2");
+
+	assert (map1.is_empty);
+	assert (map2.size == 2);
+
+	map1.remove_all (map2);	
+
+	assert (map1.is_empty);
+	assert (map2.size == 2);
+
+	map1.clear ();
+	map2.clear ();
+	
+	// Map1 has entries, map2 is empty. -> no change
+
+	map1.set ("a", "1");
+	map1.set ("b", "2");
+
+	assert (map1.size == 2);
+	assert (map2.is_empty);
+
+	map1.remove_all (map2);	
+
+	assert (map1.size == 2);
+	assert (map2.is_empty);
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 and map2 have the same entries -> map1 is cleared
+
+	map1.set ("a", "0");
+	map1.set ("b", "1");
+	map2.set ("a", "1");
+	map2.set ("b", "0");
+
+	assert (map1.size == 2);
+	assert (map2.size == 2);
+
+	map1.remove_all (map2);	
+
+	assert (map1.is_empty);
+	assert (map2.size == 2);
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 has some common keys with map2 but both have also unique keys -> common key are cleared from map1
+
+	map1.set ("x", "2");
+	map1.set ("a", "1");
+	map1.set ("b", "1");
+	map1.set ("y", "2");
+
+	map2.set ("i", "100");
+	map2.set ("a", "200");
+	map2.set ("j", "300");
+	map2.set ("b", "400");
+	map2.set ("k", "500");
+
+	assert (map1.size == 4);
+	assert (map2.size == 5);
+
+	map1.remove_all (map2);	
+
+	assert (map1.size == 2);
+	assert (map2.size == 5);
+	
+	assert (map1.contains ("x"));
+	assert (map1.contains ("y"));
+
+	map1.clear ();
+	map2.clear ();
+
+}
+
+void test_hashmap_contains_all() {
+	var map1 = new HashMap<string,string> (str_hash, str_equal, str_equal);
+	var map2 = new HashMap<string,string> (str_hash, str_equal, str_equal);
+
+	// Check empty.
+	assert (map1.contains_all (map2));
+
+	// Map1 has items, map2 is empty.
+	
+	map1.set ("1", "1");
+
+	assert (map1.contains_all (map2));
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 is empty, map2 has items.
+	
+	map2.set ("1", "1");
+
+	assert (!map1.contains_all (map2));
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 and map2 are the same.
+	
+	map1.set ("1", "a");
+	map1.set ("2", "b");
+
+	map2.set ("1", "c");
+	map2.set ("2", "d");
+
+	assert (map1.contains_all (map2));
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 and map2 are not the same
+	map1.set ("1", "a");
+	map2.set ("2", "b");
+
+	assert (!map1.contains_all (map2));
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 has a subset of map2
+	map1.set ("1", "a");
+	map1.set ("2", "b");
+	map1.set ("3", "c");
+	map1.set ("4", "d");
+	map1.set ("5", "e");
+	map1.set ("6", "f");
+
+	map2.set ("2", "g");
+	map2.set ("4", "h");
+	map2.set ("6", "i");
+
+	assert (map1.contains_all (map2));
+
+	map1.clear ();
+	map2.clear ();
+
+	// Map1 has a subset of map2 in all but one element map2
+	map1.set ("1", "a");
+	map1.set ("2", "b");
+	map1.set ("3", "c");
+	map1.set ("4", "d");
+	map1.set ("5", "e");
+	map1.set ("6", "f");
+
+	map2.set ("2", "g");
+	map2.set ("4", "h");
+	map2.set ("6", "i");
+	map2.set ("7", "j");
+
+	assert (!map1.contains_all (map2));
+
+	map1.clear ();
+	map2.clear ();
+}
+
 void main (string[] args) {
 	Test.init (ref args);
 
+	// Methods of Map interface
 	Test.add_func ("/HashMap/Map/get", test_hashmap_get);
 	Test.add_func ("/HashMap/Map/set", test_hashmap_set);
 	Test.add_func ("/HashMap/Map/remove", test_hashmap_remove);
@@ -308,6 +536,10 @@ void main (string[] args) {
 	Test.add_func ("/HashMap/Map/get_keys", test_hashmap_get_keys);
 	Test.add_func ("/HashMap/Map/get_values", test_hashmap_get_values);
 	Test.add_func ("/HashMap/Map/clear", test_hashmap_clear);
+	Test.add_func ("/HashMap/Map/empty", test_hashmap_empty);
+	Test.add_func ("/HashMap/Map/set_all", test_hashmap_set_all);
+	Test.add_func ("/HashMap/Map/remove_all", test_hashmap_remove_all);
+	Test.add_func ("/HashMap/Map/contains_all", test_hashmap_contains_all);
 
 	Test.run ();
 }
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]