# Queues are collection that controls how elements are retrieved.
#
# This interface is used for data structures and algorithms that need
# some queuing but that let their users control how the queuing is done.
#
# Most concrete queues have an efficient implementation of the basic methods
# `is_empty`, `length`, `add`, `peek`, and `take`.
# However, the `remove` method is possibly inefficient.
# To workaround an inefficient implementation, one can instead mark the removed
# elements (with a flag or in a set), and ignore then when `take` returns one.
#
# Unless stated otherwise, the `iterator` method is unrelated with the queue
# logic and may visit the elements in a order dependent on implementation.
interface Queue[E]
	super SimpleCollection[E]

	# Take the next element (according to the specific queue)
	# ~~~
	# var a = (new Array[Int]).as_lifo
	# a.add 1
	# a.add 2
	# assert a.take == 2
	# assert a.take == 1
	#
	# var h = new MinHeap[Int].default
	# h.add 2
	# h.add 1
	# h.add 10
	# assert h.take == 1
	# assert h.take == 2
	# assert h.take == 10
	# ~~~
	# ensure `result == peek`
	fun take: E is abstract

	# Look at the next element but does not remove it
	#
	# ~~~
	# var a = (new Array[Int]).as_lifo
	# a.add 1
	# assert a.peek == 1
	# a.add 2
	# assert a.peek == 2
	# assert a.take == 2
	# assert a.peek == 1
	# ~~~
	fun peek: E is abstract

	# `first` is made an alias of `peek` to avoid bad surprises
	redef fun first do return peek

	# Take and return all elements until the queue is empty.
	#
	# Ensure:
	# * `is_empty`
	# * `result.length == old(length)`
	# * `not old(is_empty) implies result.first == old(peek)`
	#
	# ~~~
	# var a = (new Array[Int]).as_lifo
	# a.add 1
	# a.add 2
	# a.add 3
	# assert a.take_all == [3, 2, 1]
	# assert a.is_empty
	# ~~~
	fun take_all: Array[E]
	do
		var res = new Array[E]
		while not is_empty do res.add take
		return res
	end
end