X-Git-Url: http://nitlanguage.org diff --git a/lib/standard/collection/array.nit b/lib/standard/collection/array.nit index 8db629b..5de71cd 100644 --- a/lib/standard/collection/array.nit +++ b/lib/standard/collection/array.nit @@ -13,14 +13,14 @@ # This module introduces the standard array structure. # It also implements two other abstract collections : ArrayMap and ArraySet -package array +module array import abstract_collection -# One dimention array of objects. -class AbstractArrayRead[E] +# One dimension array of objects. +abstract class AbstractArrayRead[E] super SequenceRead[E] - # The current length + redef readable var _length: Int = 0 redef fun is_empty do return _length == 0 @@ -61,8 +61,12 @@ class AbstractArrayRead[E] 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 @@ -76,6 +80,8 @@ class AbstractArrayRead[E] 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 @@ -89,6 +95,9 @@ class AbstractArrayRead[E] 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 @@ -100,6 +109,12 @@ class AbstractArrayRead[E] 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 @@ -122,26 +137,16 @@ class AbstractArrayRead[E] 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 - end end -# Resizeable one dimention array of objects. -class AbstractArray[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) @@ -178,6 +183,11 @@ class AbstractArray[E] 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) @@ -212,31 +222,33 @@ class AbstractArray[E] _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] 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 @@ -284,7 +296,13 @@ class Array[E] _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 @@ -301,7 +319,7 @@ class Array[E] _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 @@ -331,65 +349,14 @@ class Array[E] # 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] super IndexedIterator[E] + redef fun item do return _array[_index] # redef fun item=(e) do _array[_index] = e @@ -413,6 +380,7 @@ end # A set implemented with an Array. class ArraySet[E: Object] super Set[E] + # The stored elements. var _array: Array[E] @@ -442,7 +410,7 @@ class ArraySet[E: Object] 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) @@ -512,7 +480,7 @@ class ArrayMap[K: Object, E] 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) @@ -538,7 +506,7 @@ class ArrayMap[K: Object, E] # 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 @@ -584,10 +552,10 @@ class ArrayMapKeys[K: Object, E] end class ArrayMapValues[K: Object, E] - super RemovableCollection[K] + super RemovableCollection[E] # The original map var map: ArrayMap[K, E] - redef fun first do return self.map._items.first.first + 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) @@ -646,7 +614,7 @@ 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] @@ -670,7 +638,7 @@ end # 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