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

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 8a11c88..c664719 100644
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -13,14 +13,14 @@
 
 # This module introduces the standard array structure.
 # It also implements two other abstract collections : ArrayMap and ArraySet
-package array
+module array
 
 import abstract_collection
 
-# One dimention array of objects.
-class AbstractArrayRead[E]
+# One dimension array of objects.
+abstract class AbstractArrayRead[E]
 	super SequenceRead[E]
-	# The current length
+
 	redef readable var _length: Int = 0
 
 	redef fun is_empty do return _length == 0
@@ -61,9 +61,9 @@ class AbstractArrayRead[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
@@ -76,7 +76,7 @@ class AbstractArrayRead[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
@@ -89,6 +89,9 @@ class AbstractArrayRead[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
@@ -100,6 +103,12 @@ class AbstractArrayRead[E]
 		return result
 	end
 
+	# 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]
 	protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
 	do
 		# TODO native one
@@ -122,26 +131,16 @@ class AbstractArrayRead[E]
 	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
-	end
 end
 
-# Resizeable one dimention array of objects.
-class AbstractArray[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)
@@ -171,14 +170,14 @@ class AbstractArray[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)
@@ -212,31 +211,33 @@ class AbstractArray[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]
 	super AbstractArray[E]
 	super ArrayCapable[E]
-	redef fun iterate
-		!each(e: E)
-	do
-		var i = 0
-		var l = _length
-		var items = _items
-		while i < length do
-			each(items[i])
-			i += 1
-		end
-	end
 
 	redef fun [](index)
 	do
@@ -284,7 +285,13 @@ class Array[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
@@ -301,7 +308,7 @@ class Array[E]
 		_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
@@ -331,65 +338,14 @@ class Array[E]
 	# 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'.
+	# The size of `_items`.
 	var _capacity: Int = 0
-
-	# Sort the array using the !cmp function.
-	fun sort
-		!cmp(e1,e2: E): Int
-	do
-		sub_sort(0, length-1) !cmp(x,y) = cmp(x, y)
-	end
-
-	# Sort `array' between `from' and `to' indices
-	private fun sub_sort(from: Int, to: Int)
-		!cmp(e1,e2: E): Int
-	do
-		if from >= to then
-			return
-		else if from + 7 < to then
-			var pivot = self[from]
-			var i = from
-			var j = to
-			while j > i do
-				while i <= to and cmp(self[i], pivot) <= 0 do i += 1
-				while j > i and cmp(self[j], pivot) >= 0 do j -= 1
-				if j > i then
-					var t = self[i]
-					self[i] = self[j]
-					self[j] = t
-				end
-			end
-			self[from] = self[i-1]
-			self[i-1] = pivot
-			sub_sort(from, i-2) !cmp(x,y) = cmp(x, y)
-			sub_sort(i, to) !cmp(x,y) = cmp(x, y)
-		else
-			var i = from
-			while i < to do
-				var min = i
-				var min_v = self[i]
-				var j = i
-				while j <= to do
-					if cmp(min_v, self[j]) > 0 then
-						min = j
-						min_v = self[j]
-					end
-					j += 1
-				end
-				if min != i then
-					self[min] = self[i]
-					self[i] = min_v
-				end
-				i += 1
-			end
-		end
-	end
 end
 
-# An `Iterator' on `AbstractArray'
-class ArrayIterator[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
@@ -413,6 +369,7 @@ end
 # A set implemented with an Array.
 class ArraySet[E: Object]
 	super Set[E]
+
 	# The stored elements.
 	var _array: Array[E]
 
@@ -442,7 +399,7 @@ class ArraySet[E: Object]
 
 	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)
@@ -459,7 +416,7 @@ class ArraySet[E: Object]
 end
 
 # Iterators on sets implemented with arrays.
-class ArraySetIterator[E: Object]
+private class ArraySetIterator[E: Object]
 	super Iterator[E]
 
 	redef fun is_ok do return _iter.is_ok
@@ -485,7 +442,7 @@ class ArrayMap[K: Object, E]
 		if i >= 0 then
 			return _items[i].second
 		else
-			abort
+			return provide_default_value(key)
 		end
 	end
 
@@ -506,42 +463,13 @@ class ArrayMap[K: Object, E]
 	# O(1)
 	redef fun length do return _items.length
 
-	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)
@@ -567,7 +495,7 @@ class ArrayMap[K: Object, E]
 	# The last positive result given by a index(1) call
 	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
@@ -592,8 +520,8 @@ class ArrayMap[K: Object, E]
 	end
 end
 
-class ArrayMapKeys[K: Object, E]
-	super Collection[K]
+private class ArrayMapKeys[K: Object, 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
@@ -603,13 +531,20 @@ class ArrayMapKeys[K: Object, E]
 	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
 
-class ArrayMapValues[K: Object, E]
-	super Collection[K]
+private class ArrayMapValues[K: Object, E]
+	super RemovableCollection[E]
 	# The original map
 	var map: ArrayMap[K, E]
-	redef fun first do return self.map._items.first.first
+	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)
@@ -636,13 +571,39 @@ class ArrayMapValues[K: Object, E]
 		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
+		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
 
 
 # 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]
@@ -666,7 +627,7 @@ end
 
 # Subclasses of this class can create native arrays
 interface ArrayCapable[E]
-	# Get a new array of `size' elements.
+	# Get a new array of `size` elements.
 	protected fun calloc_array(size: Int): NativeArray[E] is intern
 end