# A view of some combinations over a base collections.
#
# This view *generates* some combinations and permutations on a collection.
#
# By default, the generated sequences are combinations:
#
#   * each sequence has a length of `repeat`
#   * elements are in sorted order (see `are_sorted` for details)
#   * no repeated element (see `are_unique` for details)
#
# ~~~~
# var xs = [1, 2, 3]
# var cxs = new CombinationCollection[Int](xs, 2)
# assert cxs.length == 3
# assert cxs.to_a == [[1,2], [1,3], [2,3]]
# ~~~~
#
# Other kind of combinations can be generated by tweaking the attributes `are_sorted` and `are_unique`.
#
# * for permutation:
#
# ~~~~
# cxs.are_sorted = false
# cxs.are_unique = true
# assert cxs.length == 6
# assert cxs.to_a == [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
# ~~~~
#
# * for combinations with replacement:
#
# ~~~~
# cxs.are_sorted = true
# cxs.are_unique = false
# assert cxs.length == 6
# assert cxs.to_a == [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]
# ~~~~
#
# * for product:
#
# ~~~~
# cxs.are_sorted = false
# cxs.are_unique = false
# assert cxs.length == 9
# assert cxs.to_a == [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]]
# ~~~~
#
# However, in the last case, a faster alternative is to use `CartesianCollection`:
#
# ~~~~
# var cp = new CartesianCollection[Int]([xs] * 2)
# assert cp.to_a == cxs.to_a
# ~~~~
#
# As seen in the examples, the patterns of the generated sequences produce a lexicographical order.
#
# Because it is a generator, it is memory-efficient and the sequences are created only when needed.
#
# Note: because it is a view, changes on the base collection are reflected on the view.
#
# ~~~~
# assert xs.pop == 3
# cxs.are_sorted = true
# cxs.are_unique = true
# assert cxs.to_a == [[1,2]]
# ~~~~
class CombinationCollection[E]
	super Collection[SequenceRead[E]]

	# The base collection used to generate the sequences.
	var collection: Collection[E]

	# The maximum length of each generated sequence.
	var repeat: Int

	init
	do
		assert repeat >= 0
	end

	# Are the elements in the generated sequences sorted?
	# Default `true`.
	#
	# When `true`, the original order is preserved.
	#
	# Elements are compared by their order in the base collection,
	# not by their intrinsic value or comparability.
	#
	# ~~~~
	# var xs = [1, 1, 2]
	# var cxs = new CombinationCollection[Int](xs, 2)
	# cxs.are_sorted = true
	# assert cxs.to_a == [[1,1], [1,2], [1, 2]]
	# cxs.are_sorted = false
	# assert cxs.to_a == [[1,1], [1,2], [1, 1], [1, 2], [2, 1], [2, 1]]
	# ~~~~
	var are_sorted = true is writable

	# Are the element in the generated sequence unique?
	# Default `true`.
	#
	# When `true`, an element cannot be reused in the same sequence (no replacement).
	#
	# Elements are distinguished by their order in the base collection,
	# not by their intrinsic value or equality.
	#
	# ~~~~
	# var xs = [1, 1, 2]
	# var cxs = new CombinationCollection[Int](xs, 2)
	# cxs.are_unique = true
	# assert cxs.to_a == [[1,1], [1,2], [1, 2]]
	# cxs.are_unique = false
	# assert cxs.to_a == [[1,1], [1,1], [1,2], [1,1], [1,2], [2,2]]
	# ~~~~
	var are_unique = true is writable

	redef fun length
	do
		var n = collection.length
		if are_unique then
			if repeat > n then
				return 0
			end
			if are_sorted then
				return n.factorial / repeat.factorial
			else
				return n.factorial / (n-repeat).factorial
			end
		else
			if are_sorted then
				return (n+repeat-1).factorial / repeat.factorial / (n-1).factorial
			else
				return n ** repeat
			end
		end
	end

	redef fun iterator do
		return new CombinationIterator[E](self)
	end
end