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

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 88d76c1..133ea5b 100644
--- a/lib/standard/collection/array.nit
+++ b/lib/standard/collection/array.nit
@@ -19,7 +19,7 @@ import abstract_collection
 
 # One dimention array of objects.
 class AbstractArrayRead[E]
-special SequenceRead[E]
+	super SequenceRead[E]
 	# The current length
 	redef readable var _length: Int = 0
 
@@ -142,8 +142,8 @@ end
 
 # Resizeable one dimention array of objects.
 class AbstractArray[E]
-special AbstractArrayRead[E]
-special Sequence[E]
+	super AbstractArrayRead[E]
+	super Sequence[E]
 	fun enlarge(cap: Int) is abstract
 
 	redef fun push(item) do add(item)
@@ -226,8 +226,8 @@ end
 #     a.push(32)
 #     a.push(8)
 class Array[E]
-special AbstractArray[E]
-special ArrayCapable[E]
+	super AbstractArray[E]
+	super ArrayCapable[E]
 	redef fun iterate
 		!each(e: E)
 	do
@@ -335,11 +335,63 @@ special ArrayCapable[E]
 
 	# 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]
-special IndexedIterator[E]
+	super IndexedIterator[E]
 	redef fun item do return _array[_index]
 
 	# redef fun item=(e) do _array[_index] = e
@@ -361,8 +413,8 @@ end
 # Others collections ##########################################################
 
 # A set implemented with an Array.
-class ArraySet[E]
-special Set[E]
+class ArraySet[E: Object]
+	super Set[E]
 	# The stored elements.
 	var _array: Array[E]
 
@@ -409,8 +461,8 @@ special Set[E]
 end
 
 # Iterators on sets implemented with arrays.
-class ArraySetIterator[E]
-special Iterator[E]
+class ArraySetIterator[E: Object]
+	super Iterator[E]
 
 	redef fun is_ok do return _iter.is_ok
 
@@ -425,8 +477,8 @@ end
 
 
 # Associative arrays implemented with an array of (key, value) pairs.
-class ArrayMap[K, E]
-special CoupleMap[K, E]
+class ArrayMap[K: Object, E]
+	super CoupleMap[K, E]
 
 	# O(n)
 	redef fun [](key)
@@ -470,7 +522,7 @@ special CoupleMap[K, E]
 	# O(1)
 	redef fun length do return _items.length
 
-	redef fun first do return _items.first.first
+	redef fun first do return _items.first.second
 
 	# O(n)
 	redef fun count(item)