X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit index 70e0b94..cdb5242 100644 --- a/lib/standard/collection/array.nit +++ b/lib/standard/collection/array.nit @@ -13,7 +13,9 @@ # This module introduces the standard array structure. # It also implements two other abstract collections : ArrayMap and ArraySet -module array +module array is + no_warning "useless-type-test" # to avoid warning with nitc while compiling with c_src +end import abstract_collection @@ -109,7 +111,7 @@ abstract class AbstractArrayRead[E] # 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) + fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int) do # TODO native one var i = len @@ -130,8 +132,70 @@ abstract class AbstractArrayRead[E] end end - redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self) + 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) + + # Returns a sub-array containing `count` elements starting from `from`. + # + # For most cases (see other case bellow), + # the first element is `from` and + # the last element is `from+count-1`. + # + # ~~~ + # var a = [10, 20, 30, 40, 50] + # assert a.sub(0, 3) == [10, 20, 30] + # assert a.sub(3, 2) == [40, 50] + # assert a.sub(3, 1) == [40] + # ~~~ + # + # If `count` is 0 or negative then an empty array is returned + # + # ~~~ + # assert a.sub(3,0).is_empty + # assert a.sub(3,-1).is_empty + # ~~~ + # + # If `from < 0` or `from+count>length` then inexistent elements are ignored. + # In this case the length of the result is lower than count. + # + # ~~~ + # assert a.sub(-2, 4) == [10, 20] + # assert a.sub(4, 99) == [50] + # assert a.sub(-9, 99) == [10,20,30,40,50] + # assert a.sub(-99, 9).is_empty + # ~~~ + fun sub(from: Int, count: Int): Array[E] do + if from < 0 then + count += from + from = 0 + end + if count < 0 then + count = 0 + end + var to = from + count + if to > length then + to = length + end + var res = new Array[E].with_capacity(to - from) + while from < to do + res.add(self[from]) + from += 1 + end + return res + end end # Resizable one dimension array of objects. @@ -242,6 +306,7 @@ end # Resizable one dimension array of objects. # # Arrays have a literal representation. +# # var a = [12, 32, 8] # # is equivalent with: # var b = new Array[Int] @@ -251,7 +316,7 @@ end # assert a == b class Array[E] super AbstractArray[E] - super ArrayCapable[E] + super Cloneable redef fun [](index) do @@ -281,12 +346,38 @@ class Array[E] _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 @@ -317,7 +408,7 @@ class Array[E] init with_capacity(cap: Int) do assert positive: cap >= 0 - _items = calloc_array(cap) + _items = new NativeArray[E](cap) _capacity = cap _length = 0 end @@ -326,7 +417,7 @@ class Array[E] 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 @@ -348,10 +439,6 @@ class Array[E] # The internal storage. 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 @@ -371,6 +458,29 @@ class Array[E] 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. @@ -394,6 +504,26 @@ class Array[E] 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` @@ -408,15 +538,11 @@ private class ArrayIterator[E] redef fun next do _index += 1 - init(a: AbstractArrayRead[E]) - do - _array = a - _index = 0 - end - redef var index = 0 - private var array: AbstractArrayRead[E] + var array: AbstractArrayRead[E] + + redef fun finish do _array._free_iterator = self end private class ArrayReverseIterator[E] @@ -426,18 +552,18 @@ 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 # Others collections ########################################################## # A set implemented with an Array. -class ArraySet[E: Object] +class ArraySet[E] super Set[E] + super Cloneable # The stored elements. private var array: Array[E] is noinit @@ -484,10 +610,41 @@ class ArraySet[E: Object] 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. -private class ArraySetIterator[E: Object] +private class ArraySetIterator[E] super Iterator[E] redef fun is_ok do return _iter.is_ok @@ -496,15 +653,14 @@ private class ArraySetIterator[E: Object] redef fun item: E do return _iter.item - init(iter: ArrayIterator[E]) do _iter = iter - - private var iter: ArrayIterator[E] + var iter: ArrayIterator[E] end # Associative arrays implemented with an array of (key, value) pairs. -class ArrayMap[K: Object, E] +class ArrayMap[K, E] super CoupleMap[K, E] + super Cloneable # O(n) redef fun [](key) @@ -528,8 +684,8 @@ class ArrayMap[K: Object, E] end end - redef var keys: RemovableCollection[K] = new ArrayMapKeys[K, E](self) - redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self) + 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 @@ -583,9 +739,38 @@ class ArrayMap[K: Object, E] end return -1 end + + # 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: Object, E] +private class ArrayMapKeys[K, E] super RemovableCollection[K] # The original map var map: ArrayMap[K, E] @@ -605,7 +790,7 @@ private class ArrayMapKeys[K: Object, E] redef fun remove_all(key) do self.remove(key) end -private class ArrayMapValues[K: Object, E] +private class ArrayMapValues[K, E] super RemovableCollection[E] # The original map var map: ArrayMap[K, E] @@ -758,12 +943,6 @@ 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 Nit array # Access are unchecked and it has a fixed size # Not for public use: may become private. @@ -774,8 +953,14 @@ universal NativeArray[E] 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