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

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 23b21c4..3cc0b57 100644
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -13,15 +13,17 @@
 
 # This module introduces the standard array structure.
 # It also implements two other abstract collections : ArrayMap and ArraySet
-package array
+module array is
+	no_warning "useless-type-test" # to avoid warning with nitc while compiling with c_src
+end
 
 import abstract_collection
 
-# One dimention array of objects.
-class AbstractArrayRead[E]
-special IndexedCollectionRead[E]
-	# The current length
-	redef readable var _length: Int = 0
+# One dimension array of objects.
+abstract class AbstractArrayRead[E]
+	super SequenceRead[E]
+
+	redef var length = 0
 
 	redef fun is_empty do return _length == 0
 
@@ -47,8 +49,6 @@ special IndexedCollectionRead[E]
 		return true
 	end
 
-	redef fun has_key(index) do return index >= 0 and index < length
-
 	redef fun count(item)
 	do
 		var res = 0
@@ -63,9 +63,9 @@ special IndexedCollectionRead[E]
 
 	redef fun index_of(item) do return index_of_from(item, 0)
 
-	fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
+	redef fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
 
-	fun index_of_from(item: E, pos: Int): Int
+	redef fun index_of_from(item: E, pos: Int): Int
 	do
 		var i = pos
 		var len = length
@@ -78,7 +78,7 @@ special IndexedCollectionRead[E]
 		return -1
 	end
 
-	fun last_index_of_from(item: E, pos: Int): Int
+	redef fun last_index_of_from(item: E, pos: Int): Int
 	do
 		var i = pos
 		while i >= 0 do
@@ -91,6 +91,9 @@ special IndexedCollectionRead[E]
 		return -1
 	end
 
+	# Return a new array that is the reverse of `self`
+	#
+	#     assert [1,2,3].reversed      ==  [3, 2, 1]
 	fun reversed: Array[E]
 	do
 		var cmp = _length
@@ -102,7 +105,13 @@ special IndexedCollectionRead[E]
 		return result
 	end
 
-	protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
+	# Copy a portion of `self` to an other array.
+	#
+	#     var a = [1, 2, 3, 4]
+	#     var b = [10, 20, 30, 40, 50]
+	#     a.copy_to(1, 2, b, 2)
+	#     assert b      ==  [10, 20, 2, 3, 50]
+	fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
 	do
 		# TODO native one
 		var i = len
@@ -123,27 +132,31 @@ special IndexedCollectionRead[E]
 		end
 	end
 
-	redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self)
-
-	# Two arrays are equals if they have the same items in the same order.
-	redef fun ==(o)
-	do
-		if not o isa AbstractArray[E] or o is null then return false
-		var l = length
-		if o.length != l then return false
-		var i = 0
-		while i < l do
-			if self[i] != o[i] then return false
-			i += 1
-		end
-		return true
+	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
 
-# Resizeable one dimention array of objects.
-class AbstractArray[E]
-special AbstractArrayRead[E]
-special IndexedCollection[E]
+# Resizable one dimension array of objects.
+abstract class AbstractArray[E]
+	super AbstractArrayRead[E]
+	super Sequence[E]
+
+	# Force the capacity to be at least `cap`.
+	# The capacity of the array is an internal information.
+	# However, this method can be used to prepare a large amount of add
 	fun enlarge(cap: Int) is abstract
 
 	redef fun push(item) do add(item)
@@ -173,20 +186,33 @@ special IndexedCollection[E]
 	redef fun unshift(item)
 	do
 		var i = length - 1
-		while i > 0 do
+		while i >= 0 do
 			self[i+1] = self[i]
 			i -= 1
 		end
 		self[0] = item
 	end
 
-	fun insert(item: E, pos: Int)
+	redef fun insert(item: E, pos: Int)
 	do
 		enlarge(length + 1)
 		copy_to(pos, length-pos, self, pos + 1)
 		self[pos] = item
 	end
 
+	redef fun insert_all(coll, pos)
+	do
+		var l = coll.length
+		if l == 0 then return
+		enlarge(length + l)
+		_length += l
+		copy_to(pos, length-pos-l, self, pos + l)
+		for c in coll do
+			self[pos] = c
+			pos += 1
+		end
+	end
+
 	redef fun add(item) do self[length] = item
 
 	redef fun clear do _length = 0
@@ -214,20 +240,35 @@ special IndexedCollection[E]
 			_length = l - 1
 		end
 	end
+
+	# Invert two elements in the array
+	#
+	#     var a = [10, 20, 30, 40]
+	#     a.swap_at(1, 3)
+	#     assert a      ==  [10, 40, 30, 20]
+	fun swap_at(a: Int,b: Int)
+	do
+	    var e = self[a]
+	    self[a] = self[b]
+	    self[b] = e
+	end
 end
 
-# Resizeable one dimention array of objects.
+# Resizable one dimension array of objects.
 #
 # Arrays have a literal representation.
-#     a = [12, 32, 8]
-# is equivalent with:
-#     a = new Array[Int]
-#     a.push(12)
-#     a.push(32)
-#     a.push(8)
+#
+#     var a = [12, 32, 8]
+#     # is equivalent with:
+#     var b = new Array[Int]
+#     b.push(12)
+#     b.push(32)
+#     b.push(8)
+#     assert a == b
 class Array[E]
-special AbstractArray[E]
-special ArrayCapable[E]
+	super AbstractArray[E]
+	super Cloneable
+
 	redef fun [](index)
 	do
 		assert index: index >= 0 and index < _length
@@ -256,12 +297,38 @@ special ArrayCapable[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
 		if cap <= c then return
 		while c <= cap do c = c * 2 + 2
-		var a = calloc_array(c)
+		var a = new NativeArray[E](c)
 		if _capacity > 0 then _items.copy_to(a, _length)
 		_items = a
 		_capacity = c
@@ -274,7 +341,13 @@ special ArrayCapable[E]
 		_length = 0
 	end
 
-	# Create an array with some `items'.
+	# Create an array from a collection.
+	init from(items: Collection[E]) do
+		with_capacity(items.length)
+		self.add_all(items)
+	end
+
+	# Create an array with some `objects`.
 	init with_items(objects: E...)
 	do
 		_items = objects._items
@@ -286,16 +359,16 @@ special ArrayCapable[E]
 	init with_capacity(cap: Int)
 	do
 		assert positive: cap >= 0
-		_items = calloc_array(cap)
+		_items = new NativeArray[E](cap)
 		_capacity = cap
 		_length = 0
 	end
 
-	# Create an array of `count' elements
+	# Create an array of `count` elements
 	init filled_with(value: E, count: Int)
 	do
 		assert positive: count >= 0
-		_items = calloc_array(count)
+		_items = new NativeArray[E](count)
 		_capacity = count
 		_length = count
 		var i = 0
@@ -315,19 +388,99 @@ special ArrayCapable[E]
 	end
 
 	# The internal storage.
-	var _items: nullable NativeArray[E] = null
+	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
 
-	# The size of `_items'.
-	var _capacity: Int = 0
+	redef fun ==(o)
+	do
+		if not o isa Array[nullable Object] then return super
+		# Efficient implementation
+		var l = length
+		if l != o.length then return false
+		var i = 0
+		var it = _items
+		var oit = o._items
+		while i < l do
+			if it[i] != oit[i] then return false
+			i += 1
+		end
+		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.
+	#
+	#     var a1 = [1,2,3]
+	#     var a2 = [4,5,6]
+	#     var a3 = a1 + a2
+	#     assert a3 == [1,2,3,4,5,6]
+	#
+	# Because a new array is always created, future modification on `self` and `other`
+	# does not impact the previously computed result.
+	#
+	#     a1.add(30)
+	#     a2.add(60)
+	#     assert a3      == [1,2,3,4,5,6] # unchanged
+	#     assert a1 + a2 == [1,2,3,30,4,5,6,60]
+	fun +(other: Array[E]): Array[E]
+	do
+		var res = new Array[E].with_capacity(length + other.length)
+		res.append(self)
+		res.append(other)
+		return res
+	end
+
+	# Repetition of arrays.
+	#
+	# 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
+	fun *(repeat: Int): Array[E]
+	do
+		assert repeat >= 0
+		var res = new Array[E].with_capacity(length * repeat)
+		while repeat > 0 do
+			res.add_all(self)
+			repeat -= 1
+		end
+		return res
+	end
 end
 
-# An `Iterator' on `AbstractArray'
-class ArrayIterator[E]
-special IndexedIterator[E]
+# An `Iterator` on `AbstractArray`
+private class ArrayIterator[E]
+	super IndexedIterator[E]
+
 	redef fun item do return _array[_index]
 
 	# redef fun item=(e) do _array[_index] = e
@@ -336,23 +489,35 @@ special IndexedIterator[E]
 
 	redef fun next do _index += 1
 
-	init(a: AbstractArrayRead[E])
+	redef var index = 0
+
+	var array: AbstractArrayRead[E]
+
+	redef fun finish do _array._free_iterator = self
+end
+
+private class ArrayReverseIterator[E]
+	super ArrayIterator[E]
+
+	redef fun is_ok do return _index >= 0
+
+	redef fun next do _index -= 1
+
+	init
 	do
-		_array = a
-		_index = 0
+		_index = _array.length - 1
 	end
-
-	redef readable var _index: Int = 0
-	var _array: AbstractArrayRead[E]
 end
 
 # Others collections ##########################################################
 
 # A set implemented with an Array.
 class ArraySet[E]
-special Set[E]
+	super Set[E]
+	super Cloneable
+
 	# The stored elements.
-	var _array: Array[E]
+	private var array: Array[E] is noinit
 
 	redef fun has(e) do return _array.has(e)
 
@@ -380,7 +545,7 @@ special Set[E]
 
 	redef fun iterator do return new ArraySetIterator[E](_array.iterator)
 
-	# Assume the capacitydd is at least `cap'.
+	# Assume the capacity is at least `cap`.
 	fun enlarge(cap: Int) do _array.enlarge(cap)
 
 	private fun remove_at(i: Int)
@@ -394,11 +559,44 @@ special Set[E]
 
 	# Create an empty set with a given capacity.
 	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.
-class ArraySetIterator[E]
-special Iterator[E]
+private class ArraySetIterator[E]
+	super Iterator[E]
 
 	redef fun is_ok do return _iter.is_ok
 
@@ -406,15 +604,14 @@ special Iterator[E]
 
 	redef fun item: E do return _iter.item
 
-	init(iter: ArrayIterator[E]) do _iter = iter
-
-	var _iter: ArrayIterator[E]
+	var iter: ArrayIterator[E]
 end
 
 
 # Associative arrays implemented with an array of (key, value) pairs.
 class ArrayMap[K, E]
-special CoupleMap[K, E]
+	super CoupleMap[K, E]
+	super Cloneable
 
 	# O(n)
 	redef fun [](key)
@@ -423,7 +620,7 @@ special CoupleMap[K, E]
 		if i >= 0 then
 			return _items[i].second
 		else
-			abort
+			return provide_default_value(key)
 		end
 	end
 
@@ -438,72 +635,19 @@ special CoupleMap[K, E]
 		end
 	end
 
-	# O(n)
-	redef fun has_key(key) do return index(key) >= 0
-
-	# O(n)
-	redef fun has(item)
-	do
-		for i in _items do if i.second == item then return true
-		return false
-	end
-
-	# O(n)
-	redef fun has_only(item)
-	do
-		for i in _items do if i.second != item then return false
-		return true
-	end
+	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
 
-	redef fun first do return _items.first.first
-
-	# O(n)
-	redef fun count(item)
-	do
-		var nb = 0
-		for i in _items do if i.second == item then nb += 1
-		return nb
-	end
-
-	redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_items.iterator)
+	redef fun couple_iterator do return _items.iterator
 
 	redef fun is_empty do return _items.is_empty
 
-	redef fun remove(item)
-	do
-		var i = _items.length - 1
-		while i >= 0 do
-			if _items[i].second == item then
-				remove_at_index(i)
-				return
-			end
-			i -= 1
-		end
-	end
-
-	redef fun remove_all(item: E)
-	do
-		var i = _items.length - 1
-		while i >= 0 do
-			if _items[i].second == item then
-				remove_at_index(i)
-			end
-			i -= 1
-		end
-	end
-
-	redef fun remove_at(key)
-	do
-		var i = index(key)
-		if i >= 0 then remove_at_index(i)
-	end
-
 	redef fun clear do _items.clear
 
-	# Assume the capacity to be at least `cap'.
+	# Assume the capacity to be at least `cap`.
 	fun enlarge(cap: Int) do _items.enlarge(cap)
 
 	redef fun couple_at(key)
@@ -517,7 +661,7 @@ special CoupleMap[K, E]
 	end
 
 	# Internal storage.
-	var _items: Array[Couple[K,E]]
+	private var items = new Array[Couple[K,E]]
 
 	# fast remove the ith element of the array
 	private fun remove_at_index(i: Int)
@@ -527,9 +671,9 @@ special CoupleMap[K, E]
 	end
 
 	# The last positive result given by a index(1) call
-	var _last_index: Int = 0
+	private var last_index: Int = 0
 
-	# Where is the `key' in `_item'?
+	# Where is the `key` in `_item`?
 	# return -1 if not found
 	private fun index(key: K): Int
 	do
@@ -547,17 +691,186 @@ special CoupleMap[K, E]
 		return -1
 	end
 
-	# A new empty map.
-	init
+	# 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, E]
+	super RemovableCollection[K]
+	# The original map
+	var map: ArrayMap[K, E]
+	redef fun count(k) do if self.has(k) then return 1 else return 0
+	redef fun first do return self.map._items.first.first
+	redef fun has(k) do return self.map.index(k) >= 0
+	redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
+	redef fun is_empty do return self.map.is_empty
+	redef fun length do return self.map.length
+	redef fun iterator do return new MapKeysIterator[K, E](self.map.iterator)
+	redef fun clear do self.map.clear
+	redef fun remove(key)
+	do
+		var i = self.map.index(key)
+		if i >= 0 then self.map.remove_at_index(i)
+	end
+	redef fun remove_all(key) do self.remove(key)
+end
+
+private class ArrayMapValues[K, E]
+	super RemovableCollection[E]
+	# The original map
+	var map: ArrayMap[K, E]
+	redef fun first do return self.map._items.first.second
+	redef fun is_empty do return self.map.is_empty
+	redef fun length do return self.map.length
+	redef fun iterator do return new MapValuesIterator[K, E](self.map.iterator)
+
+	# O(n)
+	redef fun has(item)
+	do
+		for i in self.map._items do if i.second == item then return true
+		return false
+	end
+
+	# O(n)
+	redef fun has_only(item)
+	do
+		for i in self.map._items do if i.second != item then return false
+		return true
+	end
+
+	# O(n)
+	redef fun count(item)
+	do
+		var nb = 0
+		for i in self.map._items do if i.second == item then nb += 1
+		return nb
+	end
+
+	redef fun clear do self.map.clear
+
+	redef fun remove(item)
+	do
+		var map = self.map
+		var i = map._items.length - 1
+		while i >= 0 do
+			if map._items[i].second == item then
+				map.remove_at_index(i)
+				return
+			end
+			i -= 1
+		end
+	end
+
+	redef fun remove_all(item)
 	do
-		_items = new Array[Couple[K,E]]
+		var map = self.map
+		var i = map._items.length - 1
+		while i >= 0 do
+			if map._items[i].second == item then
+				map.remove_at_index(i)
+			end
+			i -= 1
+		end
+	end
+end
+
+# Comparable array for comparable elements.
+#
+# For two arrays, if one is a prefix, then it is lower.
+#
+# ~~~
+# var a12 = new ArrayCmp[nullable Int].with_items(1,2)
+# var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
+# assert a12 < a123
+# ~~~
+#
+# Otherwise, the first element just after the longest
+# common prefix gives the order between the two arrays.
+#
+# ~~~
+# var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
+# var a13 = new ArrayCmp[nullable Int].with_items(1,3)
+# assert a12  < a123
+# assert a123 < a13
+# ~~~
+#
+# Obviously, two equal arrays are equal.
+#
+# ~~~
+# var b12 = new ArrayCmp[nullable Int].with_items(1,2)
+# assert (a12 <=> b12) == 0
+# ~~~
+#
+# `null` is considered lower than any other elements.
+# But is still greater than no element.
+#
+# ~~~
+# var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
+# assert a12n < a123
+# assert a12  < a12n
+# ~~~
+class ArrayCmp[E: nullable Comparable]
+	super Array[E]
+	super Comparable
+	redef type OTHER: ArrayCmp[E] is fixed
+
+	redef fun <(o) do return (self <=> o) < 0
+
+	redef fun <=>(o)
+	do
+		var it = _items
+		var oit = o._items
+		var i = 0
+		var l = length
+		var ol = o.length
+		var len
+		if l < ol then len = l else len = ol
+		while i < len do
+			var a = it[i]
+			var b = oit[i]
+			if a != null then
+				if b == null then return 1
+				var d = a <=> b.as(Comparable)
+				if d != 0 then return d
+			else
+				if b != null then return -1
+			end
+			i += 1
+		end
+		return l <=> ol
 	end
 end
 
 # Others tools ################################################################
 
 redef class Iterator[E]
-	# Interate on `self' and build an array
+	# Interate on `self` and build an array
 	fun to_a: Array[E]
 	do
 		var res = new Array[E]
@@ -573,22 +886,32 @@ redef class Collection[E]
 	# Build a new array from a collection
 	fun to_a: Array[E]
 	do
-		return iterator.to_a
+		var res = new Array[E].with_capacity(length)
+		res.add_all(self)
+		return res
 	end
 end
 
 # Native classes ##############################################################
 
-# Subclasses of this class can create native arrays
-interface ArrayCapable[E]
-	# Get a new array of `size' elements.
-	protected fun calloc_array(size: Int): NativeArray[E] is intern
-end
-
-# Native C array (void ...).
+# Native Nit array
+# Access are unchecked and it has a fixed size
+# Not for public use: may become private.
 universal NativeArray[E]
+	# Creates a new NativeArray of capacity `length`
+	new(length: Int) is intern
+	# The length of the array
+	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