# The root of the collection hierarchy.
#
# Collections modelize finite groups of objects, called elements.
#
# The specific behavior and representation of collections is determined
# by the subclasses of the hierarchy.
#
# The main service of Collection is to provide a stable `iterator`
# method usable to retrieve all the elements of the collection.
#
# Additional services are provided.
# For an implementation point of view, Collection provide a basic
# implementation of these services using the `iterator` method.
# Subclasses often provide a more efficient implementation.
#
# Because of the `iterator` method, Collections instances can use
# the `for` control structure.
#
# ~~~nitish
# var x: Collection[U]
# # ...
# for u in x do
#	# u is a U
#	# ...
# end
# ~~~
#
# that is equivalent with the following:
#
# ~~~nitish
# var x: Collection[U]
# # ...
# var i = x.iterator
# while i.is_ok do
#     var u = i.item # u is a U
#     # ...
#     i.next
# end
# ~~~
interface Collection[E]
	# Get a new iterator on the collection.
	fun iterator: Iterator[E] is abstract

	# Is there no item in the collection?
	#
	#     assert [1,2,3].is_empty  == false
	#     assert [1..1[.is_empty   == true
	fun is_empty: Bool do return length == 0

	# Alias for `not is_empty`.
	#
	# Some people prefer to have conditions grammatically easier to read.
	#
	#     assert [1,2,3].not_empty  == true
	#     assert [1..1[.not_empty   == false
	fun not_empty: Bool do return not self.is_empty

	# Number of items in the collection.
	#
	#     assert [10,20,30].length == 3
	#     assert [20..30[.length   == 10
	fun length: Int
	do
		var nb = 0
		for i in self do nb += 1
		return nb
	end

	# Is `item` in the collection ?
	# Comparisons are done with ==
	#
	#     assert [1,2,3].has(2)    == true
	#     assert [1,2,3].has(9)    == false
	#     assert [1..5[.has(2)     == true
	#     assert [1..5[.has(9)     == false
	fun has(item: nullable Object): Bool
	do
		for i in self do if i == item then return true
		return false
	end

	# Is the collection contain only `item`?
	# Comparisons are done with ==
	# Return true if the collection is empty.
	#
	#     assert [1,1,1].has_only(1)         == true
	#     assert [1,2,3].has_only(1)         == false
	#     assert [1..1].has_only(1)          == true
	#     assert [1..3].has_only(1)          == false
	#     assert [3..3[.has_only(1)          == true # empty collection
	#
	# ENSURE `is_empty implies result == true`
	fun has_only(item: nullable Object): Bool
	do
		for i in self do if i != item then return false
		return true
	end

	# How many occurrences of `item` are in the collection?
	# Comparisons are done with ==
	#
	#     assert [10,20,10].count(10)         == 2
	fun count(item: nullable Object): Int
	do
		var nb = 0
		for i in self do if i == item then nb += 1
		return nb
	end

	# Return the first item of the collection
	#
	#     assert [1,2,3].first                == 1
	fun first: E
	do
		assert length > 0
		return iterator.item
	end

	# Does the collection contain at least each element of `other`?
	#
	#     assert [1,3,4,2].has_all([1..2])    == true
	#     assert [1,3,4,2].has_all([1..5])    == false
	#
	# Repeated elements in the collections are not considered.
	#
	#     assert [1,1,1].has_all([1])         == true
	#     assert [1..5].has_all([1,1,1])      == true
	#
	# Note that the default implementation is general and correct for any lawful Collections.
	# It is memory-efficient but relies on `has` so may be CPU-inefficient for some kind of collections.
	fun has_all(other: Collection[nullable Object]): Bool
	do
		if is_same_instance(other) then return true
		var ol = other.length
		var  l = length
		if ol == 0 then return true
		if l == 0 then return false
		if ol == 1 then return has(other.first)
		for x in other do if not has(x) then return false
		return true
	end

	# Does the collection contain exactly all the elements of `other`?
	#
	# The same elements must be present in both `self` and `other`,
	# but the order of the elements in the collections are not considered.
	#
	#     assert [1..3].has_exactly([3,1,2]) == true  # the same elements
	#     assert [1..3].has_exactly([3,1])   == false # 2 is not in the array
	#     assert [1..2].has_exactly([3,1,2]) == false # 3 is not in the range
	#
	# Repeated elements must be present in both collections in the same amount.
	# So basically it is a multi-set comparison.
	#
	#     assert [1,2,3,2].has_exactly([1,2,2,3]) == true  # the same elements
	#     assert [1,2,3,2].has_exactly([1,2,3])   == false # more 2 in the first array
	#     assert [1,2,3].has_exactly([1,2,2,3])   == false # more 2 in the second array
	#
	# Note that the default implementation is general and correct for any lawful Collections.
	# It is memory-efficient but relies on `count` so may be CPU-inefficient for some kind of collections.
	fun has_exactly(other: Collection[nullable Object]): Bool
	do
		if length != other.length then return false
		for e in self do if self.count(e) != other.count(e) then return false
		return true
	end

	# Does the collection contain at least one element of `other`?
	#
	#     assert [1,3,4,2].has_any([1..10])    == true
	#     assert [1,3,4,2].has_any([5..10])    == false
	#
	# Note that the default implementation is general and correct for any lawful Collections.
	# It is memory-efficient but relies on `has` so may be CPU-inefficient for some kind of collections.
	fun has_any(other: Collection[nullable Object]): Bool
	do
		for o in other do
			if has(o) then return true
		end
		return false
	end
end