This module introduces the standard array structure.

# This module introduces the standard array structure.
# It also implements two other abstract collections : ArrayMap and ArraySet
module array is
	no_warning "useless-type-test" # to avoid warning with nitc while compiling with c_src
end

import abstract_collection

# One dimension array of objects.
abstract class AbstractArrayRead[E]
	super SequenceRead[E]

	redef var length = 0

	redef fun is_empty do return _length == 0

	redef fun has(item)
	do
		var i = 0
		var l = length
		while i < l do
			if self[i] == item then return true
			i += 1
		end
		return false
	end

	redef fun has_only(item)
	do
		var i = 0
		var l = length
		while i < l do
			if self[i] != item then return false
			i += 1
		end
		return true
	end

	redef fun count(item)
	do
		var res = 0
		var i = 0
		var l = length
		while i < l do
			if self[i] == item then res += 1
			i += 1
		end
		return res
	end

	redef fun index_of(item) do return index_of_from(item, 0)

	redef fun last_index_of(item) do return last_index_of_from(item, length-1)

	redef fun index_of_from(item, pos) do
		var i = pos
		var len = length
		while i < len do
			if self[i] == item then
				return i
			end
			i += 1
		end
		return -1
	end

	redef fun last_index_of_from(item, pos)	do
		var i = pos
		while i >= 0 do
			if self[i] == item then
				return i
			else
				i -= 1
			end
		end
		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
		var result = new Array[E].with_capacity(cmp)
		while cmp > 0 do
			cmp -= 1
			result.add(self[cmp])
		end
		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]
	fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
	do
		if start < new_start then
			var i = len
			while i > 0 do
				i -= 1
				dest[new_start+i] = self[start+i]
			end
		else
			var i = 0
			while i < len do
				dest[new_start+i] = self[start+i]
				i += 1
			end
		end
	end

	redef fun output
	do
		var i = 0
		var l = length
		while i < l do
			var e = self[i]
			if e != null then e.output
			i += 1
		end
	end

	redef fun iterator: IndexedIterator[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.
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 pop
	do
		assert not_empty: not is_empty
		var r = last
		_length -= 1
		return r
	end

	redef fun shift
	do
		assert not_empty: not is_empty
		var r = first
		var l = length-1
		copy_to(1, l, self, 0)
		_length = l
		return r
	end

	redef fun unshift(item)
	do
		var l = length
		if l > 0 then
			enlarge(l + 1)
			copy_to(0, l, self, 1)
		end
		self[0] = item
	end

	redef fun insert(item, pos) 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

	redef fun remove(item) do remove_at(index_of(item))

	redef fun remove_all(item)
	do
		var i = index_of(item)
		while i >= 0 do
			remove_at(i)
			i = index_of_from(item, i)
		end
	end

	redef fun remove_at(i)
	do
		var l = length
		if i >= 0 and i < l then
			var j = i + 1
			while j < l do
				self[j-1] = self[j]
				j += 1
			end
			_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

# Resizable one dimension array of objects.
#
# Arrays have a literal representation.
#
#     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 Cloneable

	redef fun [](index)
	do
		assert index: index >= 0 and index < _length
		return _items.as(not null)[index]
	end

	redef fun []=(index, item)
	do
		assert index: index >= 0 and index < _length + 1
		if _capacity <= index then
			enlarge(index + 1)
		end
		if _length <= index then
			_length = index + 1
		end
		_items.as(not null)[index] = item
	end

	redef fun add(item)
	do
		var l = _length
		if _capacity <= l then
			enlarge(l + 1)
		end
		_length = l + 1
		_items.as(not null)[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.as(not null)[l] = items._items.as(not null)[k]
				l += 1
				k += 1
			end
		else
			for item in items do
				_items.as(not null)[l] = item
				l += 1
			end
		end

		_length = nl
	end

	redef fun copy_to(start, len, dest, new_start)
	do
		# Fast code when source and destination are two arrays

		if not dest isa Array[E] then
			super
			return
		end

		# Enlarge dest if required
		var dest_len = new_start + len
		if dest_len > dest.length then
			dest.enlarge(dest_len)
			dest.length = dest_len
		end

		# Get underlying native arrays
		var items = self.items
		if items == null then return
		var dest_items = dest.items
		assert dest_items != null

		# Native copy
		items.memmove(start, len, dest_items, new_start)
	end

	redef fun enlarge(cap)
	do
		var c = _capacity
		if cap <= c then return
		while c <= cap do c = c * 2 + 2
		var a = new NativeArray[E](c)
		if _capacity > 0 then _items.as(not null).copy_to(a, _length)
		_items = a
		_capacity = c
	end

	# Create an empty array.
	init
	do
		_capacity = 0
		_length = 0
	end

	# 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
		_capacity = objects._capacity
		_length = objects.length
	end

	# Create an empty array with a given capacity.
	init with_capacity(cap: Int)
	do
		assert positive: cap >= 0
		_items = new NativeArray[E](cap)
		_capacity = cap
		_length = 0
	end

	# Create an array of `count` elements
	init filled_with(value: E, count: Int)
	do
		assert positive: count >= 0
		_items = new NativeArray[E](count)
		_capacity = count
		_length = count
		var i = 0
		while i < count do
			self[i] = value
			i += 1
		end
	end

	# Create a array filled with a given native array.
	init with_native(nat: NativeArray[E], size: Int)
	do
		assert positive: size >= 0
		_items = nat
		_capacity = size
		_length = size
	end

	# The internal storage.
	private var items: nullable NativeArray[E] = null

	# The size of `_items`.
	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
		if l == 0 then return true
		var i = 0
		var it = _items.as(not null)
		var oit = o._items.as(not null)
		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`
private class ArrayIterator[E]
	super IndexedIterator[E]

	redef fun item do return _array[_index]

	# redef fun item=(e) do _array[_index] = e

	redef fun is_ok do return _index < _array.length

	redef fun next do _index += 1

	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
		_index = _array.length - 1
	end

	# Do not cache `self`
	redef fun finish do end
end

# Others collections ##########################################################

# A set implemented with an Array.
class ArraySet[E]
	super Set[E]

	# The stored elements.
	private var array: Array[E] is noinit

	redef fun has(e) do return _array.has(e)

	redef fun add(e) do if not _array.has(e) then _array.add(e)

	redef fun is_empty do return _array.is_empty

	redef fun length do return _array.length

	redef fun first
	do
		assert _array.length > 0
		return _array.first
	end

	redef fun remove(item)
	do
		var i = _array.index_of(item)
		if i >= 0 then remove_at(i)
	end

	redef fun remove_all(item) do remove(item)

	redef fun clear do _array.clear

	redef fun iterator do return new ArraySetIterator[E](_array.iterator)

	# Assume the capacity is at least `cap`.
	fun enlarge(cap: Int) do _array.enlarge(cap)

	private fun remove_at(i: Int)
	do
		_array[i] = _array.last
		_array.pop
	end

	# Create an empty set
	init do _array = new Array[E]

	# 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.
private class ArraySetIterator[E]
	super Iterator[E]

	redef fun is_ok do return _iter.is_ok

	redef fun next do _iter.next

	redef fun item: E do return _iter.item

	var iter: Iterator[E]
end


# Associative arrays implemented with an array of (key, value) pairs.
class ArrayMap[K, E]
	super CoupleMap[K, E]
	super Cloneable

	# O(n)
	redef fun [](key)
	do
		var i = index(key)
		if i >= 0 then
			return _items[i].second
		else
			return provide_default_value(key)
		end
	end

	# O(n)
	redef fun []=(key, item)
	do
		var i = index(key)
		if i >= 0 then
			_items[i].second = item
		else
			_items.push(new Couple[K,E](key, item))
		end
	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 couple_iterator do return _items.iterator

	redef fun is_empty do return _items.is_empty

	redef fun clear do _items.clear

	# Assume the capacity to be at least `cap`.
	fun enlarge(cap: Int) do _items.enlarge(cap)

	redef fun couple_at(key)
	do
		var i = index(key)
		if i >= 0 then
			return _items[i]
		else
			return null
		end
	end

	# Internal storage.
	private var items = new Array[Couple[K,E]]

	# fast remove the ith element of the array
	private fun remove_at_index(i: Int)
	do
		_items[i] = _items.last
		_items.pop
	end

	# The last positive result given by a index(1) call
	private var last_index: Int = 0

	# Where is the `key` in `_item`?
	# return -1 if not found
	private fun index(key: K): Int
	do
		var l = _last_index
		if l < _items.length and _items[l].first == key then return l

		var i = 0
		while i < _items.length do
			if _items[i].first == key then
				_last_index = i
				return i
			end
			i += 1
		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.add_all 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
		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 i = 0
		var l = length
		if l == 0 then return 0
		var it = _items.as(not null)
		var oit = o._items.as(not null)
		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
				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
	fun to_a: Array[E]
	do
		var res = new Array[E]
		while is_ok do
			res.add(item)
			next
		end
		finish
		return res
	end
end

redef class Collection[E]
	# Build a new array from a collection
	fun to_a: Array[E]
	do
		var res = new Array[E].with_capacity(length)
		res.add_all(self)
		return res
	end
end

# Native classes ##############################################################

# 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

	# Copy `length` items to `dest` starting from `dest`.
	fun memmove(start: Int, length: Int, dest: NativeArray[E], dest_start: Int) is intern do
		if start < dest_start then
			var i = length
			while i > 0 do
				i -= 1
				dest[dest_start+i] = self[start+i]
			end
		else
			var i = 0
			while i < length do
				dest[dest_start+i] = self[start+i]
				i += 1
			end
		end
	end

	#fun =(o: NativeArray[E]): Bool is intern
	#fun !=(o: NativeArray[E]): Bool is intern
end

lib/core/collection/array.nit:14,1--1016,3

module array

Summary

This module introduces the standard array structure.

Introduced classes

AbstractArray

AbstractArrayRead

Array

ArrayCmp

ArrayMap

ArraySet

NativeArray

Redefined classes

Collection

Iterator

This module introduces the standard array structure.

Introduced classes

abstract class AbstractArray[E: nullable Object]

abstract class AbstractArrayRead[E: nullable Object]

class Array[E: nullable Object]

class ArrayCmp[E: nullable Comparable]

class ArrayMap[K: nullable Object, E: nullable Object]

class ArraySet[E: nullable Object]

enum NativeArray[E: nullable Object]

Redefined classes

redef interface Collection[E: nullable Object]

redef interface Iterator[E: nullable Object]

Summary

All class definitions

AbstractArray

AbstractArrayRead

Array

ArrayCmp

ArrayMap

ArraySet

Collection

Iterator

NativeArray

All class definitions

abstract class AbstractArray[E: nullable Object]

abstract class AbstractArrayRead[E: nullable Object]

class Array[E: nullable Object]

class ArrayCmp[E: nullable Comparable]

class ArrayMap[K: nullable Object, E: nullable Object]

class ArraySet[E: nullable Object]

redef interface Collection[E: nullable Object]

redef interface Iterator[E: nullable Object]

enum NativeArray[E: nullable Object]

Summary

Ancestors

kernel

Parents

abstract_collection

Children

circular_array

hash_collection

sorter

Descendants

a_star

a_star-m

abstract_text

abstract_tree

activities

actors

agent_simulation

ai

all

android

android19

angles

api

app

app

app_base

app_kit

array_debug

assets

assets

assets

assets_and_resources

at_boot