1 files changed, 103 insertions, 0 deletions
diff --git a/trunk/test/ruby/allpairs.rb b/trunk/test/ruby/allpairs.rb
new file mode 100644
index 0000000000..393d0c3288
--- /dev/null
+++ b/trunk/test/ruby/allpairs.rb
@@ -0,0 +1,103 @@
+module AllPairs
+  module_function
+
+  def make_prime(v)
+    return 2 if v < 2
+    ary = [true] * (v*2)
+    2.upto(Math.sqrt(ary.length).ceil) {|i|
+      return i if ary[i] && v <= i
+      (i*2).step(ary.length, i) {|j|
+        ary[j] = false
+      }
+    }
+    v.upto(ary.length-1) {|i|
+      return i if ary[i]
+    }
+    raise "[bug] prime not found greater than #{v}"
+  end
+
+  def make_basic_block(prime)
+    prime.times {|i|
+      prime.times {|j|
+        row = [i]
+        0.upto(prime-1) {|m|
+          row << (i*m + j) % prime
+        }
+        yield row
+      }
+    }
+  end 
+
+  def combine_block(tbl1, tbl2)
+    result = []
+    tbl2.each {|row|
+      result << row * tbl1.first.length
+    }
+    tbl1.each_with_index {|row, k|
+      next if k == 0
+      result << row.map {|i| [i] * tbl2.first.length }.flatten
+    }
+    result
+  end
+
+  def make_large_block(v, prime)
+    if prime <= v+1
+      make_basic_block(v) {|row|
+        yield row
+      }
+    else
+      tbl = []
+      make_basic_block(v) {|row|
+        tbl << row
+      } 
+      tbls = [tbl]
+      while tbl.first.length ** 2 < prime
+        tbl = combine_block(tbl, tbl)
+        tbls << tbl
+      end
+      tbl1 = tbls.find {|t| prime <= t.first.length * tbl.first.length }
+      tbl = combine_block(tbl, tbl1)
+      tbl.each {|row|
+        yield row
+      }
+    end
+  end
+
+  def each_index(*vs)
+    n = vs.length
+    max_v = vs.max
+    prime = make_prime(max_v)
+    h = {}
+    make_large_block(max_v, n) {|row|
+      row = vs.zip(row).map {|v, i| i % v }
+      next if h[row]
+      h[row] = true
+      yield row
+    }
+  end
+
+  # generate all pairs test.
+  def each(*args)
+    args.map! {|a| a.to_a }
+    each_index(*args.map {|a| a.length}) {|is|
+      yield is.zip(args).map {|i, a| a[i] }
+    }
+  end
+
+  # generate all combination in cartesian product.  (not all-pairs test)
+  def exhaustive_each(*args)
+    args = args.map {|a| a.to_a }
+    i = 0
+    while true
+      n = i
+      as = []
+      args.reverse_each {|a|
+        n, m = n.divmod(a.length)
+        as.unshift a[m]
+      }
+      break if 0 < n
+      yield as
+      i += 1
+    end
+  end
+end