# This file is part of NIT ( http://www.nitlanguage.org ).
#
# This file is free software, which comes along with NIT.  This software is
# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
# without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
# PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
# is kept unaltered, and a notification of the changes is added.
# You  are  allowed  to  redistribute it and sell it, alone or is a part of
# another product.

# Cartesian products on heterogeneous collections.
#
# This module is a proof-of-concept to propose memory-efficient views on collections.
#
# This is a specific alternative to `combinations`, that focuses only highly efficient
# Cartesian products between collections of different types.
#
#    Collection[Int] X Collection[String] -> Collection[(Int,String)]
#
# However, in Nit, there in no native *tuple* type.
# So we need a first building block, a pair.

# A simple read-only pair of two elements `e` and `f`.
class Pair[E, F]
	# The first element of the pair
	var e: E

	# The second element of the pair
	var f: F

	# The parenthesized notation.
	#
	# ~~~
	# var p = new Pair[Int, String](1, "hello")
	# assert p.to_s == "(1,hello)"
	# ~~~
	redef fun to_s
	do
		var es = e or else ""
		var fs = f or else ""
		return "({es},{fs})"
	end

	# Untyped pair equality.
	#
	# ~~~
	# var p1 = new Pair[Object, Object](1, 2)
	# var p2 = new Pair[Int, Int](1, 2)
	# var p3 = new Pair[Int, Int](1, 3)
	#
	# assert p1 == p2
	# assert p2 != p3
	# ~~~
	#
	# Untyped because we want that `p1 == p2` above.
	# So the method just ignores the real types of `E` and `F`.
	redef fun ==(o) do return o isa Pair[nullable Object, nullable Object] and e == o.e and f == o.f

	redef fun hash do return e.hash * 13 + f.hash * 27 # Magic numbers are magic!
end

# A view of a Cartesian-product collection over two collections.
#
# A Cartesian product over two collections is just a collection of pairs.
# Therefore, this view *contains* all the pairs of elements constructed by associating each
# element of the first collection to each element of the second collection.
#
# However the view is memory-efficient and the pairs are created only when needed.
#
# A simple Cartesian product
# ~~~~
# var c1 = [1,2]
# var c2 = ["a","b","c"]
# var c12 = new Cartesian[Int,String](c1, c2)
# assert c12.length    == 6
# assert c12.join(";") == "(1,a);(1,b);(1,c);(2,a);(2,b);(2,c)" # All the 6 pairs
# ~~~~
#
# Note: because it is a view, changes on the base collections are reflected on the view.
#
# E.g. c12 is a view on c1 and c2, so if c1 changes, then c12 "changes".
# ~~~~
# assert c2.pop        == "c"
# assert c12.length    == 4
# assert c12.join(";") == "(1,a);(1,b);(2,a);(2,b)" # All the 4 remaining pairs
# ~~~~
#
# Cartesian objects are collections, so can be used to build another Cartesian object.
# ~~~~
# var c3 = [1000..2000[
# var c123 = new Cartesian[Pair[Int,String],Int](c12, c3)
# assert c123.length   == 4000
# ~~~~
#
# All methods of Collection are inherited, it is so great!
#
# E.g. search elements?
# ~~~~
# var p12 = new Pair[Int,String](2,"b")
# assert c12.has(p12)      == true
# var p123 = new Pair[Pair[Int, String], Int](p12, 1500)
# var p123bis = new Pair[Pair[Int, String], Int](p12, 0)
# assert c123.has(p123)    == true
# assert c123.has(p123bis) == false
# ~~~~
class Cartesian[E, F]
	super Collection[Pair[E,F]]

	# The first collection
	var ce: Collection[E]

	# The second collection
	var cf: Collection[F]

	redef fun length do return ce.length * cf.length # optional, but so efficient...

	redef fun iterator do return new CartesianIterator[E,F](self)

	# Returns a new Cartesian where the first collection is the second.
	# Because the full collection is virtual, the operation is cheap!
	fun swap: Cartesian[F, E] do return new Cartesian[F, E](cf, ce)
end

# An iterator over a `Cartesian`-product collection.
class CartesianIterator[E,F]
	super Iterator[Pair[E,F]]

	# The associated Cartesian-product collection.
	var collection: Cartesian[E,F]

	# The iterator over the first collection of the Cartesian product.
	# Will be used only once.
	private var ice: Iterator[E] is noinit

	# The iterator over the second collection of the Cartesian product.
	# Will be used once for each element of the first collection.
	private var icf: Iterator[F] is noinit

	init do
		# Initialize each iterator
		ice = collection.ce.iterator
		icf = collection.cf.iterator
	end

	redef fun is_ok do return ice.is_ok and icf.is_ok

	redef fun item do
		# We lazily create the pair here
		var res = item_cache
		if res == null then
			res = new Pair[E,F](ice.item, icf.item)
			item_cache = res
		end
		return res
	end

	# Cached pair created by `item` and cleared by `next`.
	private var item_cache: nullable Pair[E,F] = null

	redef fun next do
		# Next item in the second iterator
		icf.next
		if not icf.is_ok then
			# If it is over, then reset it and advance the first iterator
			icf = collection.cf.iterator
			ice.next
		end
		# Reset the cache
		item_cache = null
	end

	# First member of `item`.
	#
	# This method shortcut the allocation of a `Pair`, thus should be more time and memory efficient.
	fun item_e: E do return ice.item

	# Second member of `item`.
	#
	# This method shortcut the allocation of a `Pair`, thus should be more time and memory efficient.
	fun item_f: E do return icf.item
end