Fixed quick_sort when array is length 0 or 1

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

diff --git a/lib/core/collection/hash_collection.nit b/lib/core/collection/hash_collection.nit
index 930c371..25cf2b9 100644 (file)
--- a/lib/core/collection/hash_collection.nit
+++ b/lib/core/collection/hash_collection.nit
@@ -20,11 +20,16 @@ redef class Map[K, V]
        new do return new HashMap[K, V]
 end
 
+redef class Set[E]
+       # Get an instance of `HashSet[E]`, the default implementation
+       new do return new HashSet[E]
+end
+
 # A HashCollection is an array of HashNode[K] indexed by the K hash value
 private abstract class HashCollection[K]
        type N: HashNode[K]
 
-       var array: nullable NativeArray[nullable N] = null # Used to store items
+       var array: NativeArray[nullable N] is noautoinit # Used to store items
        var capacity: Int = 0 # Size of _array
        var the_length: Int = 0 # Number of items in the map
 
@@ -165,7 +170,6 @@ private abstract class HashCollection[K]
        # Force a capacity
        fun enlarge(cap: Int)
        do
-               var old_cap = _capacity
                # get a new capacity
                if cap < _the_length + 1 then cap = _the_length + 1
                if cap <= _capacity then return
@@ -176,16 +180,6 @@ private abstract class HashCollection[K]
                var new_array = new NativeArray[nullable N](cap)
                _array = new_array
 
-               # clean the new array
-               var i = cap - 1
-               while i >=0 do
-                       new_array[i] = null
-                       i -= 1
-               end
-
-               if _the_length == 0 then return
-               if _capacity <= old_cap then return
-
                # Reput items in the array
                var node = _first_item
                while node != null do
@@ -249,7 +243,7 @@ class HashMap[K, V]
                end
        end
 
-       redef fun iterator: HashMapIterator[K, V] do return new HashMapIterator[K,V](self)
+       redef fun iterator do return new HashMapIterator[K,V](self)
 
        redef fun length do return _the_length
 
@@ -257,6 +251,7 @@ class HashMap[K, V]
 
        redef fun []=(key, v)
        do
+               if _capacity == 0 then enlarge(17) # 17 because magic in `store`
                var i = index_at(key)
                var c = node_at_idx(i, key)
                if c != null then
@@ -273,7 +268,12 @@ class HashMap[K, V]
        do
                _capacity = 0
                _the_length = 0
-               enlarge(0)
+       end
+
+       # Build a list filled with the items of `coll`.
+       init from(coll: Map[K, V]) do
+               init
+               add_all(coll)
        end
 
        redef var keys: RemovableCollection[K] = new HashMapKeys[K, V](self) is lazy
@@ -446,6 +446,7 @@ class HashSet[E]
 
        redef fun add(item)
        do
+               if _capacity == 0 then enlarge(17) # 17 because magic in `store`
                var i = index_at(item)
                var c = node_at_idx(i, item)
                if c != null then
@@ -465,7 +466,6 @@ class HashSet[E]
        do
                _capacity = 0
                _the_length = 0
-               enlarge(0)
        end
 
        # Build a list filled with the items of `coll`.