lib/array: remember the last used iterator so it could be used again

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

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 68f84e7..acc189c 100644 (file)
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -130,7 +130,20 @@ abstract class AbstractArrayRead[E]
                end
        end
 
-       redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self)
+       redef fun iterator: ArrayIterator[E] do
+               var res = _free_iterator
+               if res == null then return new ArrayIterator[E](self)
+               res._index = 0
+               _free_iterator = null
+               return res
+       end
+
+       # An old iterator, free to reuse.
+       # Once an iterator is `finish`, it become reusable.
+       # Since some arrays are iterated a lot, this avoid most of the
+       # continuous allocation/garbage-collection of the needed iterators.
+       private var free_iterator: nullable ArrayIterator[E] = null
+
        redef fun reverse_iterator do return new ArrayReverseIterator[E](self)
 end
 
@@ -252,6 +265,7 @@ end
 #     assert a == b
 class Array[E]
        super AbstractArray[E]
+       super Cloneable
 
        redef fun [](index)
        do
@@ -393,6 +407,29 @@ class Array[E]
                return true
        end
 
+       # Shallow clone of `self`
+       #
+       # ~~~
+       # var a = [1,2,3]
+       # var b = a.clone
+       # assert a == b
+       # a.add 4
+       # assert a != b
+       # b.add 4
+       # assert a == b
+       # ~~~
+       #
+       # Note that the clone is shallow and elements are shared between `self` and the result.
+       #
+       # ~~~
+       # var aa = [a]
+       # var bb = aa.clone
+       # assert aa == bb
+       # aa.first.add 5
+       # assert aa == bb
+       # ~~~
+       redef fun clone do return to_a
+
        # Concatenation of arrays.
        #
        # Returns a new array built by concatenating `self` and `other` together.
@@ -453,6 +490,8 @@ private class ArrayIterator[E]
        redef var index = 0
 
        var array: AbstractArrayRead[E]
+
+       redef fun finish do _array._free_iterator = self
 end
 
 private class ArrayReverseIterator[E]
@@ -471,8 +510,9 @@ end
 # Others collections ##########################################################
 
 # A set implemented with an Array.
-class ArraySet[E: Object]
+class ArraySet[E]
        super Set[E]
+       super Cloneable
 
        # The stored elements.
        private var array: Array[E] is noinit
@@ -519,10 +559,41 @@ class ArraySet[E: Object]
        init with_capacity(i: Int) do _array = new Array[E].with_capacity(i)
 
        redef fun new_set do return new ArraySet[E]
+
+       # Shallow clone of `self`
+       #
+       # ~~~
+       # var a = new ArraySet[Int]
+       # a.add 1
+       # a.add 2
+       # var b = a.clone
+       # assert a == b
+       # a.add 3
+       # assert a != b
+       # b.add 3
+       # assert a == b
+       # ~~~
+       #
+       # Note that the clone is shallow and keys and values are shared between `self` and the result.
+       #
+       # ~~~
+       # var aa = new ArraySet[Array[Int]]
+       # aa.add([1,2])
+       # var bb = aa.clone
+       # assert aa == bb
+       # aa.first.add 5
+       # assert aa == bb
+       # ~~~
+       redef fun clone
+       do
+               var res = new ArraySet[E]
+               res.add_all self
+               return res
+       end
 end
 
 # Iterators on sets implemented with arrays.
-private class ArraySetIterator[E: Object]
+private class ArraySetIterator[E]
        super Iterator[E]
 
        redef fun is_ok do return _iter.is_ok
@@ -536,8 +607,9 @@ end
 
 
 # Associative arrays implemented with an array of (key, value) pairs.
-class ArrayMap[K: Object, E]
+class ArrayMap[K, E]
        super CoupleMap[K, E]
+       super Cloneable
 
        # O(n)
        redef fun [](key)
@@ -616,9 +688,38 @@ class ArrayMap[K: Object, E]
                end
                return -1
        end
+
+       # Shallow clone of `self`
+       #
+       # ~~~
+       # var a = new ArrayMap[String,Int]
+       # a["one"] = 1
+       # a["two"] = 2
+       # var b = a.clone
+       # assert a == b
+       # a["zero"] = 0
+       # assert a != b
+       # ~~~
+       #
+       # Note that the clone is shallow and keys and values are shared between `self` and the result.
+       #
+       # ~~~
+       # var aa = new ArrayMap[String, Array[Int]]
+       # aa["two"] = [1,2]
+       # var bb = aa.clone
+       # assert aa == bb
+       # aa["two"].add 5
+       # assert aa == bb
+       # ~~~
+       redef fun clone
+       do
+               var res = new ArrayMap[K,E]
+               res.recover_with self
+               return res
+       end
 end
 
-private class ArrayMapKeys[K: Object, E]
+private class ArrayMapKeys[K, E]
        super RemovableCollection[K]
        # The original map
        var map: ArrayMap[K, E]
@@ -638,7 +739,7 @@ private class ArrayMapKeys[K: Object, E]
        redef fun remove_all(key) do self.remove(key)
 end
 
-private class ArrayMapValues[K: Object, E]
+private class ArrayMapValues[K, E]
        super RemovableCollection[E]
        # The original map
        var map: ArrayMap[K, E]