X-Git-Url: http://nitlanguage.org

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index ca6e9fa..3cc0b57 100644
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -13,7 +13,9 @@
 
 # This module introduces the standard array structure.
 # It also implements two other abstract collections : ArrayMap and ArraySet
-module array
+module array is
+	no_warning "useless-type-test" # to avoid warning with nitc while compiling with c_src
+end
 
 import abstract_collection
 
@@ -109,7 +111,7 @@ abstract class AbstractArrayRead[E]
 	#     var b = [10, 20, 30, 40, 50]
 	#     a.copy_to(1, 2, b, 2)
 	#     assert b      ==  [10, 20, 2, 3, 50]
-	protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
+	fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
 	do
 		# TODO native one
 		var i = len
@@ -130,7 +132,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
 
@@ -242,6 +257,7 @@ end
 # Resizable one dimension array of objects.
 #
 # Arrays have a literal representation.
+#
 #     var a = [12, 32, 8]
 #     # is equivalent with:
 #     var b = new Array[Int]
@@ -251,6 +267,7 @@ end
 #     assert a == b
 class Array[E]
 	super AbstractArray[E]
+	super Cloneable
 
 	redef fun [](index)
 	do
@@ -280,6 +297,32 @@ class Array[E]
 		_items[l] = item
 	end
 
+	# Slight optimization for arrays
+	redef fun add_all(items)
+	do
+		var l = _length
+		var nl = l + items.length
+		if _capacity < nl then
+			enlarge nl
+		end
+
+		if items isa Array[E] then
+			var k = 0
+			while l < nl do
+				_items[l] = items._items[k]
+				l += 1
+				k += 1
+			end
+		else
+			for item in items do
+				_items[l] = item
+				l += 1
+			end
+		end
+
+		_length = nl
+	end
+
 	redef fun enlarge(cap)
 	do
 		var c = _capacity
@@ -347,10 +390,6 @@ class Array[E]
 	# The internal storage.
 	private var items: nullable NativeArray[E] = null
 
-	# Do not use this method
-	# FIXME: Remove it once modules can intrude non local modules
-	fun intern_items: NativeArray[E] do return _items.as(not null)
-
 	# The size of `_items`.
 	private var capacity: Int = 0
 
@@ -370,6 +409,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.
@@ -398,11 +460,11 @@ class Array[E]
 	#
 	# returns a new array built by concatenating `self` `repeat` times.
 	#
-	#    var a = [1,2,3]
-	#    assert (a * 0).is_empty
-	#    assert a * 1  ==  [1,2,3]
-	#    assert a * 2  ==  [1,2,3,1,2,3]
-	#    assert (a * 10).length  ==  30
+	#     var a = [1,2,3]
+	#     assert (a * 0).is_empty
+	#     assert a * 1  ==  [1,2,3]
+	#     assert a * 2  ==  [1,2,3,1,2,3]
+	#     assert (a * 10).length  ==  30
 	fun *(repeat: Int): Array[E]
 	do
 		assert repeat >= 0
@@ -429,7 +491,9 @@ private class ArrayIterator[E]
 
 	redef var index = 0
 
-	private var array: AbstractArrayRead[E]
+	var array: AbstractArrayRead[E]
+
+	redef fun finish do _array._free_iterator = self
 end
 
 private class ArrayReverseIterator[E]
@@ -448,8 +512,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
@@ -496,10 +561,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
@@ -508,13 +604,14 @@ private class ArraySetIterator[E: Object]
 
 	redef fun item: E do return _iter.item
 
-	private var iter: ArrayIterator[E]
+	var iter: ArrayIterator[E]
 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)
@@ -538,8 +635,8 @@ class ArrayMap[K: Object, E]
 		end
 	end
 
-	redef var keys: RemovableCollection[K] = new ArrayMapKeys[K, E](self)
-	redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self)
+	redef var keys: RemovableCollection[K] = new ArrayMapKeys[K, E](self) is lazy
+	redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self) is lazy
 
 	# O(1)
 	redef fun length do return _items.length
@@ -593,9 +690,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]
@@ -615,7 +741,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]
@@ -778,8 +904,14 @@ universal NativeArray[E]
 	fun length: Int is intern
 	# Use `self` to initialize a standard Nit Array.
 	fun to_a: Array[E] do return new Array[E].with_native(self, length)
+
+	# Get item at `index`.
 	fun [](index: Int): E is intern
+
+	# Set `item` at `index`.
 	fun []=(index: Int, item: E) is intern
+
+	# Copy `length` items to `dest`.
 	fun copy_to(dest: NativeArray[E], length: Int) is intern
 	#fun =(o: NativeArray[E]): Bool is intern
 	#fun !=(o: NativeArray[E]): Bool is intern