X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit index 6ae145d..7d710bd 100644 --- a/lib/standard/collection/array.nit +++ b/lib/standard/collection/array.nit @@ -21,8 +21,7 @@ import abstract_collection abstract class AbstractArrayRead[E] super SequenceRead[E] - var _length: Int = 0 - redef fun length do return _length + redef var length = 0 redef fun is_empty do return _length == 0 @@ -186,6 +185,19 @@ abstract class AbstractArray[E] 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 @@ -334,14 +346,74 @@ class Array[E] 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`. - var _capacity: Int = 0 + private 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 + + # 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` @@ -356,15 +428,9 @@ private class ArrayIterator[E] redef fun next do _index += 1 - init(a: AbstractArrayRead[E]) - do - _array = a - _index = 0 - end + redef var index = 0 - var _index: Int = 0 - redef fun index do return _index - var _array: AbstractArrayRead[E] + private var array: AbstractArrayRead[E] end private class ArrayReverseIterator[E] @@ -374,10 +440,9 @@ private class ArrayReverseIterator[E] redef fun next do _index -= 1 - init(a: AbstractArrayRead[E]) + init do - _array = a - _index = a.length - 1 + _index = _array.length - 1 end end @@ -388,7 +453,7 @@ class ArraySet[E: Object] super Set[E] # The stored elements. - var _array: Array[E] + private var array: Array[E] is noinit redef fun has(e) do return _array.has(e) @@ -444,9 +509,7 @@ private class ArraySetIterator[E: Object] redef fun item: E do return _iter.item - init(iter: ArrayIterator[E]) do _iter = iter - - var _iter: ArrayIterator[E] + private var iter: ArrayIterator[E] end @@ -502,7 +565,7 @@ class ArrayMap[K: Object, E] 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) @@ -512,7 +575,7 @@ class ArrayMap[K: Object, E] 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`? # return -1 if not found @@ -531,12 +594,6 @@ class ArrayMap[K: Object, E] end return -1 end - - # A new empty map. - init - do - _items = new Array[Couple[K,E]] - end end private class ArrayMapKeys[K: Object, E] @@ -618,6 +675,72 @@ private class ArrayMapValues[K: Object, E] 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 ################################################################ @@ -638,7 +761,9 @@ redef class Collection[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 @@ -654,6 +779,8 @@ end # 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.