# 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