# 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