niti: fix type in tool description

[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 9a53f99..2def742 100644 (file)
--- a/lib/standard/collection/hash_collection.nit
+++ b/lib/standard/collection/hash_collection.nit
@@ -23,7 +23,7 @@ private abstract class HashCollection[K: Object, N: HashNode[Object]]
        var _capacity: Int = 0 # Size of _array
        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 _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)
@@ -44,7 +44,7 @@ private abstract class HashCollection[K: Object, N: HashNode[Object]]
        fun node_at(k: K): nullable N
        do
                # 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
+               if k.is_same_instance(_last_accessed_key) then return _last_accessed_node
 
                var res = node_at_idx(index_at(k), k)
                _last_accessed_key = k
@@ -58,7 +58,7 @@ private abstract class HashCollection[K: Object, N: HashNode[Object]]
                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_same_instance(k) or ck == k then # FIXME prefilter because the compiler is not smart enought yet
                                break
                        end
                        c = c._next_in_bucklet
@@ -91,9 +91,13 @@ private abstract class HashCollection[K: Object, N: HashNode[Object]]
                # Enlarge if needed
                var l = _length
                _length = l + 1
-               l = (l + 5) * 3 / 2
+
+               # Magic values determined empirically
+               # We do not want to enlarge too much
+               # We also want a odd capacity so that the modulo is more distributive
+               l = (l + 5) * 2 + 1
                if l >= _capacity then
-                       enlarge(l * 2)
+                       enlarge(l * 3 / 2 + 1)
                end
        end
 
@@ -178,6 +182,7 @@ private abstract class HashCollection[K: Object, N: HashNode[Object]]
                        # Then store it in the array
                        var next = new_array[index]
                        new_array[index] = node
+                       node._prev_in_bucklet = null
                        node._next_in_bucklet = next
                        if next != null then next._prev_in_bucklet = node
                        node = node._next_item
@@ -188,8 +193,8 @@ end
 private abstract class HashNode[K: Object]
        var _key: K
        type N: HashNode[K]
-       readable writable var _next_item: nullable N = null
-       readable writable var _prev_item: 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
        init(k: K)
@@ -208,7 +213,7 @@ class HashMap[K: Object, V]
        do
                var c = node_at(key)
                if c == null then
-                       abort
+                       return provide_default_value(key)
                else
                        return c._value
                end
@@ -241,12 +246,12 @@ class HashMap[K: Object, V]
                enlarge(0)
        end
 
-       redef var keys: HashMapKeys[K, V] = new HashMapKeys[K, V](self)
-       redef var values: HashMapValues[K, V] = new HashMapValues[K, V](self)
+       redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self)
+       redef var values: RemovableCollection[V] = new HashMapValues[K, V](self)
 end
 
 # View of the keys of a HashMap
-class HashMapKeys[K: Object, V]
+private class HashMapKeys[K: Object, V]
        super RemovableCollection[K]
        # The original map
        var map: HashMap[K, V]
@@ -267,7 +272,7 @@ class HashMapKeys[K: Object, V]
 end
 
 # View of the values of a Map
-class HashMapValues[K: Object, V]
+private class HashMapValues[K: Object, V]
        super RemovableCollection[V]
        # The original map
        var map: HashMap[K, V]
@@ -386,7 +391,7 @@ class HashMapIterator[K: Object, V]
        init(map: HashMap[K, V])
        do
                _map = map
-               _node = map.first_item
+               _node = map._first_item
        end
 end
 
@@ -440,6 +445,8 @@ class HashSet[E: Object]
                init
                add_all(coll)
        end
+
+       redef fun new_set do return new HashSet[E]
 end
 
 private class HashSetNode[E: Object]
@@ -452,7 +459,7 @@ private class HashSetNode[E: Object]
        end
 end
 
-class HashSetIterator[E: Object]
+private class HashSetIterator[E: Object]
        super Iterator[E]
        redef fun is_ok do return _node != null