Merge: Fix nitiwiki: Fixes auto-index links.

[nit.git] / lib / standard / collection / hash_collection.nit

diff --git a/lib/standard/collection/hash_collection.nit b/lib/standard/collection/hash_collection.nit
index 8e27c80..f385729 100644 (file)
--- a/lib/standard/collection/hash_collection.nit
+++ b/lib/standard/collection/hash_collection.nit
@@ -10,36 +10,44 @@
 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
 # another product.
 
-# Introduce Hashmap and Hashset.
+# Introduce `HashMap` and `HashSet`.
 module hash_collection
 
 import array
 
+redef class Map[K, V]
+       # Get a `HashMap[K, V]` as default implementation
+       new do return new HashMap[K, V]
+end
+
 # A HashCollection is an array of HashNode[K] indexed by the K hash value
-private abstract class HashCollection[K: Object, N: HashNode[Object]]
+private abstract class HashCollection[K]
+       type N: HashNode[K]
 
-       private var array: nullable NativeArray[nullable N] = null # Used to store items
-       private var capacity: Int = 0 # Size of _array
-       private var the_length: Int = 0 # Number of items in the map
+       var array: nullable NativeArray[nullable N] = null # Used to store items
+       var capacity: Int = 0 # Size of _array
+       var the_length: Int = 0 # Number of items in the map
 
-       private var first_item: nullable N = null # First added item (used to visit items in nice order)
-       private var last_item: nullable N = null # Last added item (same)
+       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)
 
        # The last key accessed (used for cache)
-       private var last_accessed_key: nullable K = null
+       var last_accessed_key: nullable K = null
 
        # The last node accessed (used for cache)
-       private var last_accessed_node: nullable N = null
+       var last_accessed_node: nullable N = null
 
        # 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)
@@ -51,7 +59,7 @@ private abstract class HashCollection[K: Object, N: HashNode[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]
@@ -189,20 +197,33 @@ private abstract class HashCollection[K: Object, N: HashNode[Object]]
        end
 end
 
-private abstract class HashNode[K: Object]
-       private var key: K
+private abstract class HashNode[K]
+       var key: K
        type N: HashNode[K]
-       private var next_item: nullable N = null
-       private var prev_item: nullable N = null
-       private var prev_in_bucklet: nullable N = null
-       private var next_in_bucklet: nullable N = null
+       var next_item: nullable N = null
+       var prev_item: nullable N = null
+       var prev_in_bucklet: nullable N = null
+       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, HashMapNode[K, V]]
+       super HashCollection[K]
+
+       redef type N: HashMapNode[K, V] is fixed
 
        redef fun [](key)
        do
@@ -246,7 +267,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]
@@ -267,7 +288,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]
@@ -337,13 +358,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]
-       private var value: V
+       var value: V
 end
 
-class HashMapIterator[K: Object, V]
+# A `MapIterator` over a `HashMap`.
+class HashMapIterator[K, V]
        super MapIterator[K, V]
        redef fun is_ok do return _node != null
 
@@ -388,7 +410,9 @@ end
 # 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]]
+       super HashCollection[E]
+
+       redef type N: HashSetNode[E] is fixed
 
        redef fun length do return _the_length
 
@@ -460,10 +484,10 @@ private class HashSetIterator[E: Object]
        end
 
        # The set to iterate on
-       private var set: HashSet[E]
+       var set: HashSet[E]
 
        # The position in the internal map storage
-       private var node: nullable HashSetNode[E] = null
+       var node: nullable HashSetNode[E] = null
 
        init
        do