# This module introduces the standard array structure.
# It also implements two other abstract collections : ArrayMap and ArraySet
-package array
+module array
import abstract_collection
abstract class AbstractArrayRead[E]
super SequenceRead[E]
- redef readable var _length: Int = 0
+ var _length: Int = 0
+ redef fun length do return _length
redef fun is_empty do return _length == 0
redef fun index_of(item) do return index_of_from(item, 0)
- # The index of the last occurrence of an element.
- # Return -1 if not found.
- 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)
- # The index of the first occurrence of an element starting from pos.
- # Return -1 if not found.
- 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
return -1
end
- # The index of the last occurrence of an element starting from pos.
- # Return -1 if not found.
- 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
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[nullable Object] 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
+ redef fun reverse_iterator do return new ArrayReverseIterator[E](self)
end
# Resizable one dimension array of objects.
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
- # Insert an element at a given position, following elements are shifted.
- #
- # var a= [10, 20, 30, 40]
- # a.insert(100, 2)
- # assert a == [10, 20, 100, 30, 40]
- 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)
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]
+private class ArrayIterator[E]
super IndexedIterator[E]
redef fun item do return _array[_index]
_index = 0
end
- redef readable var _index: Int = 0
+ var _index: Int = 0
+ redef fun index do return _index
var _array: AbstractArrayRead[E]
end
+private class ArrayReverseIterator[E]
+ super ArrayIterator[E]
+
+ redef fun is_ok do return _index >= 0
+
+ redef fun next do _index -= 1
+
+ init(a: AbstractArrayRead[E])
+ do
+ _array = a
+ _index = a.length - 1
+ end
+end
+
# Others collections ##########################################################
# A set implemented with an Array.
# 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]
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
if i >= 0 then
return _items[i].second
else
- abort
+ return provide_default_value(key)
end
end
end
end
- redef var keys: ArrayMapKeys[K, E] = new ArrayMapKeys[K, E](self)
- redef var values: ArrayMapValues[K, E] = new ArrayMapValues[K, E](self)
+ redef var keys: RemovableCollection[K] = new ArrayMapKeys[K, E](self)
+ redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self)
# 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
end
end
-class ArrayMapKeys[K: Object, E]
+private class ArrayMapKeys[K: Object, E]
super RemovableCollection[K]
# The original map
var map: ArrayMap[K, E]
redef fun remove_all(key) do self.remove(key)
end
-class ArrayMapValues[K: Object, E]
+private class ArrayMapValues[K: Object, E]
super RemovableCollection[E]
# The original map
var map: ArrayMap[K, E]
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]
+ # 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)
fun [](index: Int): E is intern
fun []=(index: Int, item: E) is intern
fun copy_to(dest: NativeArray[E], length: Int) is intern
nitlanguage / nit.git / blobdiff