X-Git-Url: http://nitlanguage.org

diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit
index 66a301d..9a53f99 100644
--- a/lib/standard/collection/hash_collection.nit
+++ b/lib/standard/collection/hash_collection.nit
@@ -11,18 +11,17 @@
 # another product.
 
 # Introduce Hashmap and Hashset.
-package hash_collection
+module hash_collection
 
 import array
-import hash
 
 # A HashCollection is an array of HashNode[K] indexed by the K hash value
-private class HashCollection[K: Object, N: HashNode[K], E]
-special Collection[E]
-special ArrayCapable[nullable N]
+private abstract class HashCollection[K: Object, N: HashNode[Object]]
+	super ArrayCapable[nullable N]
+
 	var _array: nullable NativeArray[nullable N] = null # Used to store items
 	var _capacity: Int = 0 # Size of _array
-	redef readable var _length: Int = 0 # Number of items in the map
+	var _length: Int = 0 # Number of items in the map
 
 	readable var _first_item: nullable N = null # First added item (used to visit items in nice order)
 	var _last_item: nullable N = null # Last added item (same)
@@ -44,7 +43,7 @@ special ArrayCapable[nullable N]
 	# Return the node assosiated 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)
+		# cache: `is` is used instead of `==` because it is a faster filter (even if not exact)
 		if k is _last_accessed_key then return _last_accessed_node
 
 		var res = node_at_idx(index_at(k), k)
@@ -59,7 +58,7 @@ special ArrayCapable[nullable N]
 		var c = _array[i]
 		while c != null do
 			var ck = c._key
-			if ck is k or ck == k then # prefilter with `is' because the compiler is not smart enought yet
+			if ck is k or ck == k then # prefilter with `is` because the compiler is not smart enought yet
 				break
 			end
 			c = c._next_in_bucklet
@@ -135,6 +134,7 @@ special ArrayCapable[nullable N]
 		_last_accessed_key = null
 	end
 
+	# Clear the whole structure
 	fun raz
 	do
 		var i = _capacity - 1
@@ -148,6 +148,7 @@ special ArrayCapable[nullable N]
 		_last_accessed_key = null
 	end
 
+	# Force a capacity
 	fun enlarge(cap: Int)
 	do
 		var old_cap = _capacity
@@ -184,7 +185,7 @@ special ArrayCapable[nullable N]
 	end
 end
 
-private class HashNode[K]
+private abstract class HashNode[K: Object]
 	var _key: K
 	type N: HashNode[K]
 	readable writable var _next_item: nullable N = null
@@ -197,9 +198,11 @@ private class HashNode[K]
 	end
 end
 
-class HashMap[K, V]
-special Map[K, V]
-special HashCollection[K, HashMapNode[K, V], V]
+# 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]
+	super Map[K, V]
+	super HashCollection[K, HashMapNode[K, V]]
 
 	redef fun [](key)
 	do
@@ -211,42 +214,79 @@ special HashCollection[K, HashMapNode[K, V], V]
 		end
 	end
 
-	redef fun has_key(key) do return node_at(key) != null
-
 	redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
 
-	redef fun iterate
-		!each(e: V)
+	redef fun length do return _length
+
+	redef fun is_empty do return _length == 0
+
+	redef fun []=(key, v)
 	do
-		var c = _first_item
-		while c != null do
-			each(c._value)
-			c = c._next_item
+		var i = index_at(key)
+		var c = node_at_idx(i, key)
+		if c != null then
+			c._key = key
+			c._value = v
+		else
+			store(i, new HashMapNode[K, V](key, v))
 		end
 	end
 
-	redef fun first
+	redef fun clear do raz
+
+	init
 	do
-		assert _length > 0
-		return _first_item._value
+		_capacity = 0
+		_length = 0
+		enlarge(0)
 	end
 
-	redef fun is_empty do return _length == 0
+	redef var keys: HashMapKeys[K, V] = new HashMapKeys[K, V](self)
+	redef var values: HashMapValues[K, V] = new HashMapValues[K, V](self)
+end
+
+# View of the keys of a HashMap
+class HashMapKeys[K: Object, V]
+	super RemovableCollection[K]
+	# The original map
+	var map: HashMap[K, V]
+
+	redef fun count(k) do if self.has(k) then return 1 else return 0
+	redef fun first do return self.map._first_item._key
+	redef fun has(k) do return self.map.node_at(k) != null
+	redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
+	redef fun is_empty do return self.map.is_empty
+	redef fun length do return self.map.length
+
+	redef fun iterator do return new MapKeysIterator[K, V](self.map.iterator)
+
+	redef fun clear do self.map.clear
+
+	redef fun remove(key) do self.map.remove_node(key)
+	redef fun remove_all(key) do self.map.remove_node(key)
+end
+
+# View of the values of a Map
+class HashMapValues[K: Object, V]
+	super RemovableCollection[V]
+	# The original map
+	var map: HashMap[K, V]
 
 	redef fun count(item)
 	do
 		var nb = 0
-		var c = _first_item
+		var c = self.map._first_item
 		while c != null do
 			if c._value == item then nb += 1
 			c = c._next_item
 		end
 		return nb
 	end
+	redef fun first do return self.map._first_item._value
 
 	redef fun has(item)
 	do
-		var c = _first_item
+		var c = self.map._first_item
 		while c != null do
 			if c._value == item then return true
 			c = c._next_item
@@ -256,7 +296,7 @@ special HashCollection[K, HashMapNode[K, V], V]
 
 	redef fun has_only(item)
 	do
-		var c = _first_item
+		var c = self.map._first_item
 		while c != null do
 			if c._value != item then return false
 			c = c._next_item
@@ -264,45 +304,41 @@ special HashCollection[K, HashMapNode[K, V], V]
 		return true
 	end
 
-	redef fun []=(key, v)
-	do
-		assert key != null
-		var i = index_at(key)
-		var c = node_at_idx(i, key)
-		if c != null then
-			c._key = key
-			c._value = v
-		else
-			store(i, new HashMapNode[K, V](key, v))
-		end
-	end
+	redef fun is_empty do return self.map.is_empty
+	redef fun length do return self.map.length
+
+	redef fun iterator do return new MapValuesIterator[K, V](self.map.iterator)
+
+	redef fun clear do self.map.clear
 
 	redef fun remove(item)
 	do
-		var c = _first_item
+		var map = self.map
+		var c = map._first_item
 		while c != null do
 			if c._value == item then
-				remove_node(c._key)
+				map.remove_node(c._key)
 				return
 			end
 			c = c._next_item
 		end
 	end
 
-	redef fun remove_at(key) do remove_node(key)
-
-	redef fun clear do raz
-
-	init
+	redef fun remove_all(item)
 	do
-		_capacity = 0
-		_length = 0
-		enlarge(0)
+		var map = self.map
+		var c = map._first_item
+		while c != null do
+			if c._value == item then
+				map.remove_node(c._key)
+			end
+			c = c._next_item
+		end
 	end
 end
 
-class HashMapNode[K, V]
-special HashNode[K]
+private class HashMapNode[K: Object, V]
+	super HashNode[K]
 	redef type N: HashMapNode[K, V]
 	var _value: V
 
@@ -313,8 +349,8 @@ special HashNode[K]
 	end
 end
 
-class HashMapIterator[K, V]
-special MapIterator[K, V]
+class HashMapIterator[K: Object, V]
+	super MapIterator[K, V]
 	redef fun is_ok do return _node != null
 
 	redef fun item
@@ -354,9 +390,13 @@ special MapIterator[K, V]
 	end
 end
 
-class HashSet[E]
-special Set[E]
-special HashCollection[E, HashSetNode[E], E]
+# A `Set` implemented with a hash table.
+# Keys of such a map cannot be null and require a working `hash` method
+class HashSet[E: Object]
+	super Set[E]
+	super HashCollection[E, HashSetNode[E]]
+
+	redef fun length do return _length
 
 	redef fun is_empty do return _length == 0
 
@@ -394,10 +434,16 @@ special HashCollection[E, HashSetNode[E], E]
 		_length = 0
 		enlarge(0)
 	end
+
+	# Build a list filled with the items of `coll`.
+	init from(coll: Collection[E]) do
+		init
+		add_all(coll)
+	end
 end
 
-class HashSetNode[E]
-special HashNode[E]
+private class HashSetNode[E: Object]
+	super HashNode[E]
 	redef type N: HashSetNode[E]
 
 	init(e: E)
@@ -406,8 +452,8 @@ special HashNode[E]
 	end
 end
 
-class HashSetIterator[E]
-special Iterator[E]
+class HashSetIterator[E: Object]
+	super Iterator[E]
 	redef fun is_ok do return _node != null
 
 	redef fun item