metamodel: rename 'universal' to 'enum'

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

diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit
index 88d76c1..133ea5b 100644 (file)
--- 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)