# Cross product adapted from code by Michael Neuman.
#
# CREDIT Michael Neuman

require 'generator'

module Enumerable

  class << self

    # 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 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


  # The instance level version of <tt>Enumerable::cartesian_product</tt>.
  #
  #   a = []
  #   [1,2].cart([4,5]){|elem| a << elem }
  #   a  #=> [[1, 4],[1, 5],[2, 4],[2, 5]]
  #
  #--
  # TODO Make a more efficient version just for Array (?)
  #++

  def cross(*enums, &block)
    Enumerable.cross(self, *enums, &block)
  end

end



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

  require 'test/unit'

  class TCEnumerableClass < 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


  class TCEnumerable < Test::Unit::TestCase

    def test_cross
      a = [1,2,3].cross([4,5,6])
      assert_equal( [[1, 4],[1, 5],[1, 6],[2, 4],[2, 5],[2, 6],[3, 4],[3, 5],[3, 6]], a )
      a = []
      [1,2,3].cross([4,5,6]) {|elem| a << elem }
      assert_equal( [[1, 4],[1, 5],[1, 6],[2, 4],[2, 5],[2, 6],[3, 4],[3, 5],[3, 6]], a )
    end

  end

=end
