import abstract_collection
-# One dimention array of objects.
-class AbstractArrayRead[E]
-special SequenceRead[E]
- # The current length
+# One dimension array of objects.
+abstract class AbstractArrayRead[E]
+ super SequenceRead[E]
+
redef readable var _length: Int = 0
redef fun is_empty do return _length == 0
return true
end
- redef fun has_key(index) do return index >= 0 and index < length
-
redef fun count(item)
do
var res = 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)
+ # 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
do
var i = pos
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
do
var i = pos
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
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
# 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
+ 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
end
end
-# Resizeable one dimention array of objects.
-class AbstractArray[E]
-special AbstractArrayRead[E]
-special Sequence[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)
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)
do
enlarge(length + 1)
_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] = 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]
-special AbstractArray[E]
-special ArrayCapable[E]
+ super AbstractArray[E]
+ super ArrayCapable[E]
+
redef fun iterate
!each(e: E)
do
_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
_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
# 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'
+# 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]
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)
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)
end
end
- # O(n)
- redef fun has_key(key) do return index(key) >= 0
-
- # O(n)
- redef fun has(item)
- do
- for i in _items do if i.second == item then return true
- return false
- end
-
- # O(n)
- redef fun has_only(item)
- do
- for i in _items do if i.second != item then return false
- return true
- end
+ redef var keys: ArrayMapKeys[K, E] = new ArrayMapKeys[K, E](self)
+ redef var values: ArrayMapValues[K, E] = new ArrayMapValues[K, E](self)
# O(1)
redef fun length do return _items.length
- redef fun first do return _items.first.first
-
- # O(n)
- redef fun count(item)
- do
- var nb = 0
- for i in _items do if i.second == item then nb += 1
- return nb
- end
-
redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_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)
# 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
end
end
+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
+ redef fun first do return self.map._items.first.first
+ redef fun has(k) do return self.map.index(k) >= 0
+ redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
+ 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 RemovableCollection[E]
+ # The original map
+ var map: ArrayMap[K, E]
+ 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)
+
+ # O(n)
+ redef fun has(item)
+ do
+ for i in self.map._items do if i.second == item then return true
+ return false
+ end
+
+ # O(n)
+ redef fun has_only(item)
+ do
+ for i in self.map._items do if i.second != item then return false
+ return true
+ end
+
+ # O(n)
+ redef fun count(item)
+ do
+ var nb = 0
+ for i in self.map._items do if i.second == item then nb += 1
+ 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]
# 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
nitlanguage / nit.git / blobdiff