#--
# Cross product adapted from code by Michael Neuman.
#++
require 'generator'

module Enumerable

  #  Provides the cross-product of two or more Enumerables.
  #  This is the class-level method. The instance method
  #  calls on this.
  #
  #    Enumerable.cross([1,2], [4], ["apple", "banana"])
  #    #=> [[1, 4, "apple"], [1, 4, "banana"], [2, 4, "apple"], [2, 4, "banana"]]
  #
  #    Enumerable.cross([1,2], [3,4])
  #    #=> [[1, 3], [1, 4], [2, 3], [2, 4]]
  #
  #--
  # TODO Make a more efficient version just for Array (?)
  #++
  def self.cross(*enums, &block)

    raise if enums.empty?
    gens = enums.map{|e| Generator.new(e)}
    return [] if gens.any? {|g| g.end?}

    sz = gens.size
    res = []
    tuple = Array.new(sz)

    loop do
      # fill tuple
      (0 ... sz).each { |i|
        tuple[i] = gens[i].current
      }
      if block.nil?
        res << tuple.dup
      else
        block.call(tuple.dup)
      end

      # step forward
      gens[-1].next
      (sz-1).downto(0) do |i|
        if gens[i].end?
          if i > 0
            gens[i].rewind
            gens[i-1].next
          else
            return res
          end
        end
      end
    end #loop

  end

end



#  _____         _
# |_   _|__  ___| |_
#   | |/ _ \/ __| __|
#   | |  __/\__ \ |_
#   |_|\___||___/\__|
#
=begin test

  require 'test/unit'

  class TCEnumerable < Test::Unit::TestCase

    def test_cross
      i = [[1,2], [3,4]]
      o = [[1, 3], [1, 4], [2, 3], [2, 4]]
      assert_equal( o, Enumerable.cross(*i) )
      i = [[1,2], [4], ["apple", "banana"]]
      o = [[1, 4, "apple"], [1, 4, "banana"], [2, 4, "apple"], [2, 4, "banana"]]
      assert_equal( o, Enumerable.cross(*i) )
    end

  end

=end