# This module introduces the standard array structure.
# It also implements two other abstract collections : ArrayMap and ArraySet
-package array
+module array is
+ no_warning "useless-type-test" # to avoid warning with nitc while compiling with c_src
+end
import abstract_collection
-# One dimention array of objects.
-class AbstractArrayRead[E]
-special IndexedCollectionRead[E]
- # The current length
- redef readable var _length: Int = 0
+# One dimension array of objects.
+abstract class AbstractArrayRead[E]
+ super SequenceRead[E]
+
+ redef var length = 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)
- 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)
- 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
- 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
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
- protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
+ # 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]
+ fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
do
# TODO native one
var i = len
end
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[E] 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
+ redef fun iterator: ArrayIterator[E] do
+ var res = _free_iterator
+ if res == null then return new ArrayIterator[E](self)
+ res._index = 0
+ _free_iterator = null
+ return res
end
+
+ # An old iterator, free to reuse.
+ # Once an iterator is `finish`, it become reusable.
+ # Since some arrays are iterated a lot, this avoid most of the
+ # continuous allocation/garbage-collection of the needed iterators.
+ private var free_iterator: nullable ArrayIterator[E] = null
+
+ redef fun reverse_iterator do return new ArrayReverseIterator[E](self)
end
-# Resizeable one dimention array of objects.
-class AbstractArray[E]
-special AbstractArrayRead[E]
-special IndexedCollection[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)
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
- 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)
self[pos] = item
end
+ redef fun insert_all(coll, pos)
+ do
+ var l = coll.length
+ if l == 0 then return
+ enlarge(length + l)
+ _length += l
+ copy_to(pos, length-pos-l, self, pos + l)
+ for c in coll do
+ self[pos] = c
+ pos += 1
+ end
+ end
+
redef fun add(item) do self[length] = item
redef fun clear do _length = 0
_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] = self[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 Cloneable
+
redef fun [](index)
do
assert index: index >= 0 and index < _length
_items[l] = item
end
+ # Slight optimization for arrays
+ redef fun add_all(items)
+ do
+ var l = _length
+ var nl = l + items.length
+ if _capacity < nl then
+ enlarge nl
+ end
+
+ if items isa Array[E] then
+ var k = 0
+ while l < nl do
+ _items[l] = items._items[k]
+ l += 1
+ k += 1
+ end
+ else
+ for item in items do
+ _items[l] = item
+ l += 1
+ end
+ end
+
+ _length = nl
+ end
+
redef fun enlarge(cap)
do
var c = _capacity
if cap <= c then return
while c <= cap do c = c * 2 + 2
- var a = calloc_array(c)
+ var a = new NativeArray[E](c)
if _capacity > 0 then _items.copy_to(a, _length)
_items = a
_capacity = c
_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
init with_capacity(cap: Int)
do
assert positive: cap >= 0
- _items = calloc_array(cap)
+ _items = new NativeArray[E](cap)
_capacity = cap
_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
- _items = calloc_array(count)
+ _items = new NativeArray[E](count)
_capacity = count
_length = count
var i = 0
end
# The internal storage.
- var _items: nullable NativeArray[E] = null
+ private var items: nullable NativeArray[E] = null
- # Do not use this method
- # 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`.
+ private var capacity: Int = 0
- # The size of `_items'.
- var _capacity: Int = 0
+ redef fun ==(o)
+ do
+ if not o isa Array[nullable Object] then return super
+ # Efficient implementation
+ var l = length
+ if l != o.length then return false
+ var i = 0
+ var it = _items
+ var oit = o._items
+ while i < l do
+ if it[i] != oit[i] then return false
+ i += 1
+ end
+ return true
+ end
+
+ # Shallow clone of `self`
+ #
+ # ~~~
+ # var a = [1,2,3]
+ # var b = a.clone
+ # assert a == b
+ # a.add 4
+ # assert a != b
+ # b.add 4
+ # assert a == b
+ # ~~~
+ #
+ # Note that the clone is shallow and elements are shared between `self` and the result.
+ #
+ # ~~~
+ # var aa = [a]
+ # var bb = aa.clone
+ # assert aa == bb
+ # aa.first.add 5
+ # assert aa == bb
+ # ~~~
+ redef fun clone do return to_a
+
+ # Concatenation of arrays.
+ #
+ # Returns a new array built by concatenating `self` and `other` together.
+ #
+ # var a1 = [1,2,3]
+ # var a2 = [4,5,6]
+ # var a3 = a1 + a2
+ # assert a3 == [1,2,3,4,5,6]
+ #
+ # Because a new array is always created, future modification on `self` and `other`
+ # does not impact the previously computed result.
+ #
+ # a1.add(30)
+ # a2.add(60)
+ # assert a3 == [1,2,3,4,5,6] # unchanged
+ # assert a1 + a2 == [1,2,3,30,4,5,6,60]
+ fun +(other: Array[E]): Array[E]
+ do
+ var res = new Array[E].with_capacity(length + other.length)
+ res.append(self)
+ res.append(other)
+ return res
+ end
+
+ # Repetition of arrays.
+ #
+ # returns a new array built by concatenating `self` `repeat` times.
+ #
+ # var a = [1,2,3]
+ # assert (a * 0).is_empty
+ # assert a * 1 == [1,2,3]
+ # assert a * 2 == [1,2,3,1,2,3]
+ # assert (a * 10).length == 30
+ fun *(repeat: Int): Array[E]
+ do
+ assert repeat >= 0
+ var res = new Array[E].with_capacity(length * repeat)
+ while repeat > 0 do
+ res.add_all(self)
+ repeat -= 1
+ end
+ return res
+ end
end
-# An `Iterator' on `AbstractArray'
-class ArrayIterator[E]
-special IndexedIterator[E]
+# An `Iterator` on `AbstractArray`
+private class ArrayIterator[E]
+ super IndexedIterator[E]
+
redef fun item do return _array[_index]
# redef fun item=(e) do _array[_index] = e
redef fun next do _index += 1
- init(a: AbstractArrayRead[E])
+ redef var index = 0
+
+ var array: AbstractArrayRead[E]
+
+ redef fun finish do _array._free_iterator = self
+end
+
+private class ArrayReverseIterator[E]
+ super ArrayIterator[E]
+
+ redef fun is_ok do return _index >= 0
+
+ redef fun next do _index -= 1
+
+ init
do
- _array = a
- _index = 0
+ _index = _array.length - 1
end
-
- redef readable var _index: Int = 0
- var _array: AbstractArrayRead[E]
end
# Others collections ##########################################################
# A set implemented with an Array.
class ArraySet[E]
-special Set[E]
+ super Set[E]
+ super Cloneable
+
# The stored elements.
- var _array: Array[E]
+ private var array: Array[E] is noinit
redef fun has(e) do return _array.has(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)
# 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]
+
+ # Shallow clone of `self`
+ #
+ # ~~~
+ # var a = new ArraySet[Int]
+ # a.add 1
+ # a.add 2
+ # var b = a.clone
+ # assert a == b
+ # a.add 3
+ # assert a != b
+ # b.add 3
+ # assert a == b
+ # ~~~
+ #
+ # Note that the clone is shallow and keys and values are shared between `self` and the result.
+ #
+ # ~~~
+ # var aa = new ArraySet[Array[Int]]
+ # aa.add([1,2])
+ # var bb = aa.clone
+ # assert aa == bb
+ # aa.first.add 5
+ # assert aa == bb
+ # ~~~
+ redef fun clone
+ do
+ var res = new ArraySet[E]
+ res.add_all self
+ return res
+ end
end
# Iterators on sets implemented with arrays.
-class ArraySetIterator[E]
-special Iterator[E]
+private class ArraySetIterator[E]
+ super Iterator[E]
redef fun is_ok do return _iter.is_ok
redef fun item: E do return _iter.item
- init(iter: ArrayIterator[E]) do _iter = iter
-
- var _iter: ArrayIterator[E]
+ var iter: ArrayIterator[E]
end
# Associative arrays implemented with an array of (key, value) pairs.
class ArrayMap[K, E]
-special CoupleMap[K, E]
+ super CoupleMap[K, E]
+ super Cloneable
# O(n)
redef fun [](key)
if i >= 0 then
return _items[i].second
else
- abort
+ return provide_default_value(key)
end
end
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: RemovableCollection[K] = new ArrayMapKeys[K, E](self) is lazy
+ redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self) is lazy
# 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 couple_iterator do return _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)
end
# Internal storage.
- var _items: Array[Couple[K,E]]
+ private var items = new Array[Couple[K,E]]
# fast remove the ith element of the array
private fun remove_at_index(i: Int)
end
# The last positive result given by a index(1) call
- var _last_index: Int = 0
+ private 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
return -1
end
- # A new empty map.
- init
+ # Shallow clone of `self`
+ #
+ # ~~~
+ # var a = new ArrayMap[String,Int]
+ # a["one"] = 1
+ # a["two"] = 2
+ # var b = a.clone
+ # assert a == b
+ # a["zero"] = 0
+ # assert a != b
+ # ~~~
+ #
+ # Note that the clone is shallow and keys and values are shared between `self` and the result.
+ #
+ # ~~~
+ # var aa = new ArrayMap[String, Array[Int]]
+ # aa["two"] = [1,2]
+ # var bb = aa.clone
+ # assert aa == bb
+ # aa["two"].add 5
+ # assert aa == bb
+ # ~~~
+ redef fun clone
+ do
+ var res = new ArrayMap[K,E]
+ res.recover_with self
+ return res
+ end
+end
+
+private class ArrayMapKeys[K, 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
+
+private class ArrayMapValues[K, 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
- _items = new Array[Couple[K,E]]
+ 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
+
+# Comparable array for comparable elements.
+#
+# For two arrays, if one is a prefix, then it is lower.
+#
+# ~~~
+# var a12 = new ArrayCmp[nullable Int].with_items(1,2)
+# var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
+# assert a12 < a123
+# ~~~
+#
+# Otherwise, the first element just after the longest
+# common prefix gives the order between the two arrays.
+#
+# ~~~
+# var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
+# var a13 = new ArrayCmp[nullable Int].with_items(1,3)
+# assert a12 < a123
+# assert a123 < a13
+# ~~~
+#
+# Obviously, two equal arrays are equal.
+#
+# ~~~
+# var b12 = new ArrayCmp[nullable Int].with_items(1,2)
+# assert (a12 <=> b12) == 0
+# ~~~
+#
+# `null` is considered lower than any other elements.
+# But is still greater than no element.
+#
+# ~~~
+# var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
+# assert a12n < a123
+# assert a12 < a12n
+# ~~~
+class ArrayCmp[E: nullable Comparable]
+ super Array[E]
+ super Comparable
+ redef type OTHER: ArrayCmp[E] is fixed
+
+ redef fun <(o) do return (self <=> o) < 0
+
+ redef fun <=>(o)
+ do
+ var it = _items
+ var oit = o._items
+ var i = 0
+ var l = length
+ var ol = o.length
+ var len
+ if l < ol then len = l else len = ol
+ while i < len do
+ var a = it[i]
+ var b = oit[i]
+ if a != null then
+ if b == null then return 1
+ var d = a <=> b.as(Comparable)
+ if d != 0 then return d
+ else
+ if b != null then return -1
+ end
+ i += 1
+ end
+ return l <=> ol
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]
# Build a new array from a collection
fun to_a: Array[E]
do
- return iterator.to_a
+ var res = new Array[E].with_capacity(length)
+ res.add_all(self)
+ return res
end
end
# Native classes ##############################################################
-# Subclasses of this class can create native arrays
-interface ArrayCapable[E]
- # Get a new array of `size' elements.
- 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]
+ # Creates a new NativeArray of capacity `length`
+ new(length: Int) is intern
+ # 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)
+
+ # Get item at `index`.
fun [](index: Int): E is intern
+
+ # Set `item` at `index`.
fun []=(index: Int, item: E) is intern
+
+ # Copy `length` items to `dest`.
fun copy_to(dest: NativeArray[E], length: Int) is intern
#fun =(o: NativeArray[E]): Bool is intern
#fun !=(o: NativeArray[E]): Bool is intern
nitlanguage / nit.git / blobdiff