Merge branch 'master' into polymorphic_extern_classes

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

diff --git a/lib/standard/collection/abstract_collection.nit b/lib/standard/collection/abstract_collection.nit
index a08f7d4..7320e83 100644 (file)
--- a/lib/standard/collection/abstract_collection.nit
+++ b/lib/standard/collection/abstract_collection.nit
@@ -188,7 +188,7 @@ class Container[E]
        init(e: E) do item = e
 
        # The stored item
-       var item: E writable
+       var item: E is writable
 end
 
 # This iterator is quite stupid since it is used for only one item.
@@ -202,7 +202,7 @@ private class ContainerIterator[E]
 
        redef var is_ok: Bool = true
 
-       var _container: Container[E]
+       private var container: Container[E]
 end
 
 # Items can be removed from this collection
@@ -304,8 +304,11 @@ interface Set[E: Object]
        # Because of the law between `==` and `hash`, `hash` is redefined to be the sum of the hash of the elements
        redef fun hash
        do
-               var res = 0
-               for e in self do res += res.hash
+               # 23 is a magic number empirically determined to be not so bad.
+               var res = 23 + length
+               # Note: the order of the elements must not change the hash value.
+               # So, unlike usual hash functions, the accumulator is not combined with itself.
+               for e in self do res += e.hash
                return res
        end
 
@@ -624,7 +627,7 @@ interface SequenceRead[E]
                var p = 0
                var i = iterator
                while i.is_ok do
-                       if p>pos and i.item == item then return i.index
+                       if p>=pos and i.item == item then return i.index
                        i.next
                        p += 1
                end
@@ -677,8 +680,14 @@ interface SequenceRead[E]
        # Because of the law between `==` and `hash`, `hash` is redefined to be the sum of the hash of the elements
        redef fun hash
        do
-               var res = 0
-               for e in self do res += res.hash
+               # The 17 and 2/3 magic numbers were determined empirically.
+               # Note: the standard hash functions djb2, sbdm and fnv1 were also
+               # tested but were comparable (or worse).
+               var res = 17 + length
+               for e in self do
+                       res = res * 3 / 2
+                       if e != null then res += e.hash
+               end
                return res
        end
 
@@ -772,7 +781,9 @@ interface Sequence[E]
        #     var a = [1,2,3]
        #     a.append([7..9])
        #     assert a  == [1,2,3,7,8,9]
-       fun append(coll: Collection[E]) do for i in coll do push(i)
+       #
+       # Alias of `add_all`
+       fun append(coll: Collection[E]) do add_all(coll)
 
        # Remove the last item.
        #
@@ -792,6 +803,15 @@ interface Sequence[E]
        #     assert a  == [20,10,1,2,3]
        fun unshift(e: E) is abstract
 
+       # Add all items of `coll` before the first one.
+       #
+       #     var a = [1,2,3]
+       #     a.prepend([7..9])
+       #     assert a  == [7,8,9,1,2,3]
+       #
+       # Alias of `insert_at(coll, 0)`
+       fun prepend(coll: Collection[E]) do insert_all(coll, 0)
+
        # Remove the first item.
        # The second item thus become the first.
        #
@@ -824,10 +844,30 @@ interface Sequence[E]
        #     a.insert(100, 2)
        #     assert a      ==  [10, 20, 100, 30, 40]
        #
-       # REQUIRE `index >= 0 and index < length`
+       # REQUIRE `index >= 0 and index <= length`
        # ENSURE `self[index] == item`
        fun insert(item: E, index: Int) is abstract
 
+       # Insert all elements at a given position, following elements are shifted.
+       #
+       #     var a = [10, 20, 30, 40]
+       #     a.insert_all([100..102], 2)
+       #     assert a      ==  [10, 20, 100, 101, 102, 30, 40]
+       #
+       # REQUIRE `index >= 0 and index <= length`
+       # ENSURE `self[index] == coll.first`
+       fun insert_all(coll: Collection[E], index: Int)
+       do
+               assert index >= 0 and index < length
+               if index == length then
+                       add_all(coll)
+               end
+               for c in coll do
+                       insert(c, index)
+                       index += 1
+               end
+       end
+
        # Remove the item at `index` and shift all following elements
        #
        #     var a = [10,20,30]
@@ -889,7 +929,7 @@ private class CoupleMapIterator[K: Object, E]
                _iter.next
        end
 
-       var _iter: Iterator[Couple[K,E]]
+       private var iter: Iterator[Couple[K,E]]
 
        init(i: Iterator[Couple[K,E]]) do _iter = i
 end
@@ -900,10 +940,10 @@ end
 class Couple[F, S]
 
        # The first element of the couple.
-       var first: F writable
+       var first: F is writable
 
        # The second element of the couple.
-       var second: S writable
+       var second: S is writable
 
        # Create a new instance with a first and a second object.
        init(f: F, s: S)