# Abstract sets.
#
# Set is a collection without duplicates (according to `==`)
#
#      var s: Set[String] = new ArraySet[String]
#      var a = "Hello"
#      var b = "Hel" + "lo"
#      # ...
#      s.add(a)
#      assert s.has(b)      ==  true
interface Set[E]
	super SimpleCollection[E]
	super Cloneable

	redef fun has_only(item)
	do
		var l = length
		if l == 1 then
			return has(item)
		else if l == 0 then
			return true
		else
			return false
		end
	end

	# Only 0 or 1
	redef fun count(item)
	do
		if has(item) then
			return 1
		else
			return 0
		end
	end

	# Synonym of remove since there is only one item
	redef fun remove_all(item) do remove(item)

	# Equality is defined on set and means that each set contains the same elements
	redef fun ==(other)
	do
		if not other isa Set[nullable Object] then return false
		if other.length != length then return false
		return has_all(other)
	end

	# Because of the law between `==` and `hash`, `hash` is redefined to be the sum of the hash of the elements
	redef fun hash
	do
		# 23 is a magic number empirically determined to be not so bad.
		var res = 23 + length
		# Note: the order of the elements must not change the hash value.
		# So, unlike usual hash functions, the accumulator is not combined with itself.
		for e in self do
			if e != null then res += e.hash
		end
		return res
	end

	# Returns the union of this set with the `other` set
	fun union(other: Set[E]): Set[E]
	do
		var nhs = new_set
		nhs.add_all self
		nhs.add_all other
		return nhs
	end

	# Returns the intersection of this set with the `other` set
	fun intersection(other: Set[E]): Set[E]
	do
		var nhs = new_set
		for v in self do if other.has(v) then nhs.add(v)
		return nhs
	end

	redef fun clone do return union(self)

	# Returns a new instance of `Set`.
	#
	# Depends on the subclass, mainly used for copy services
	# like `union` or `intersection`.
	protected fun new_set: Set[E] is abstract
end