# 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