# One dimention array of objects.
class AbstractArrayRead[E]
-special SequenceRead[E]
+ super SequenceRead[E]
# The current length
redef readable var _length: Int = 0
# 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)
# 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
+ var i = 0
+ var l = _length
+ var items = _items
+ while i < length do
+ each(items[i])
+ i += 1
+ end
+ end
+
redef fun [](index)
do
assert index: index >= 0 and index < _length
# 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
# 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]
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
# 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)
# 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)