From 9b0b8ffab1782437375464d590e4d03c5037cc18 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Alexis=20Laferri=C3=A8re?= <alexis.laf@xymus.net>
Date: Thu, 18 Dec 2014 10:30:38 -0500
Subject: [PATCH] lib: update HashMap and ArrayMap to support nullable keys
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Signed-off-by: Alexis Laferrière <alexis.laf@xymus.net>
---
 lib/standard/collection/array.nit           |    6 ++---
 lib/standard/collection/hash_collection.nit |   35 ++++++++++++++++++---------
 2 files changed, 27 insertions(+), 14 deletions(-)

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 68f84e7..44ea5d3 100644
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -536,7 +536,7 @@ end
 
 
 # Associative arrays implemented with an array of (key, value) pairs.
-class ArrayMap[K: Object, E]
+class ArrayMap[K, E]
 	super CoupleMap[K, E]
 
 	# O(n)
@@ -618,7 +618,7 @@ class ArrayMap[K: Object, E]
 	end
 end
 
-private class ArrayMapKeys[K: Object, E]
+private class ArrayMapKeys[K, E]
 	super RemovableCollection[K]
 	# The original map
 	var map: ArrayMap[K, E]
@@ -638,7 +638,7 @@ private class ArrayMapKeys[K: Object, E]
 	redef fun remove_all(key) do self.remove(key)
 end
 
-private class ArrayMapValues[K: Object, E]
+private class ArrayMapValues[K, E]
 	super RemovableCollection[E]
 	# The original map
 	var map: ArrayMap[K, E]
diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit
index d389c5a..cae46fd 100644
--- a/lib/standard/collection/hash_collection.nit
+++ b/lib/standard/collection/hash_collection.nit
@@ -16,7 +16,7 @@ module hash_collection
 import array
 
 # A HashCollection is an array of HashNode[K] indexed by the K hash value
-private abstract class HashCollection[K: Object]
+private abstract class HashCollection[K]
 	type N: HashNode[K]
 
 	var array: nullable NativeArray[nullable N] = null # Used to store items
@@ -35,12 +35,14 @@ private abstract class HashCollection[K: Object]
 	# Return the index of the key k
 	fun index_at(k: K): Int
 	do
+		if k == null then return 0
+
 		var i = k.hash % _capacity
 		if i < 0 then i = - i
 		return i
 	end
 
-	# Return the node assosiated with the key
+	# Return the node associated with the key
 	fun node_at(k: K): nullable N
 	do
 		# cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
@@ -52,7 +54,7 @@ private abstract class HashCollection[K: Object]
 		return res
 	end
 
-	# Return the node assosiated with the key (but with the index already known)
+	# Return the node associated with the key (but with the index already known)
 	fun node_at_idx(i: Int, k: K): nullable N
 	do
 		var c = _array[i]
@@ -190,7 +192,7 @@ private abstract class HashCollection[K: Object]
 	end
 end
 
-private abstract class HashNode[K: Object]
+private abstract class HashNode[K]
 	var key: K
 	type N: HashNode[K]
 	var next_item: nullable N = null
@@ -199,9 +201,20 @@ private abstract class HashNode[K: Object]
 	var next_in_bucklet: nullable N = null
 end
 
-# A map implemented with a hash table.
-# Keys of such a map cannot be null and require a working `hash` method
-class HashMap[K: Object, V]
+# A `Map` implemented with a hash table.
+#
+# ~~~
+# var map = new HashMap[nullable String, Int]
+# map[null] = 0
+# map["one"] = 1
+# map["two"] = 2
+#
+# assert map[null] == 0
+# assert map["one"] == 1
+# assert map.keys.has("two")
+# assert map.values.length == 3
+# ~~~
+class HashMap[K, V]
 	super Map[K, V]
 	super HashCollection[K]
 
@@ -249,7 +262,7 @@ class HashMap[K: Object, V]
 end
 
 # View of the keys of a HashMap
-private class HashMapKeys[K: Object, V]
+private class HashMapKeys[K, V]
 	super RemovableCollection[K]
 	# The original map
 	var map: HashMap[K, V]
@@ -270,7 +283,7 @@ private class HashMapKeys[K: Object, V]
 end
 
 # View of the values of a Map
-private class HashMapValues[K: Object, V]
+private class HashMapValues[K, V]
 	super RemovableCollection[V]
 	# The original map
 	var map: HashMap[K, V]
@@ -340,14 +353,14 @@ private class HashMapValues[K: Object, V]
 	end
 end
 
-private class HashMapNode[K: Object, V]
+private class HashMapNode[K, V]
 	super HashNode[K]
 	redef type N: HashMapNode[K, V]
 	var value: V
 end
 
 # A `MapIterator` over a `HashMap`.
-class HashMapIterator[K: Object, V]
+class HashMapIterator[K, V]
 	super MapIterator[K, V]
 	redef fun is_ok do return _node != null
 
-- 
1.7.9.5