package Sequenic.T2.Engines;
import java.math.BigInteger;
/**
 * The CombinationGenerator by Michael Gilleland. See <a href="http://www.merriampark.com/comb.htm">
 * http://www.merriampark.com/comb.htm </a>.
 * 
 * <p>This implements a generator producing all combinations of n elements, 
 * taken r at a time. The algorithm is described by Kenneth H. Rosen, in
 * Discrete Mathematics and Its Applications, 2nd edition, McGraw-Hill, 1991, 
 * pp. 284-286.
 * 
 * <p>A "combination" of r elements from a set V of n (distinct) items is a 
 * subset of V with r number of elements. Note that a combination is therefore
 * unordered.
 * 
 * @author Michael Gilleland, adapted by Wishnu Prasetya
 */
public class CombinationGenerator extends AbstractCombinationGenerator {

  protected int n;
  protected int r;

  protected CombinationGenerator() { }
  
  /**
   * Create a generator that would generate all combinations of r elements
   * out of a set V of n distinct elements. The set V will be represented by
   * indices 0..n-1.
   */
  public CombinationGenerator (int n, int r) {
	    
    if (r > n) {
      throw new IllegalArgumentException ();
    }
    if (n < 1) {
      throw new IllegalArgumentException ();
    }
    this.n = n;
    this.r = r;
    a = new int[r];
    try {
    	long nFact = getFactorial (n);
    	long rFact = getFactorial (r);
    	long nminusrFact = getFactorial (n - r);
    	long total = nFact / (rFact * nminusrFact);
    	if (total <= (long) Integer.MAX_VALUE)
    		this.total = (int) total ;
    	else
    		throw new Error("The number of combinations is too large.") ;
    }
    catch (ArithmeticException e) {
    	throw new Error("The number of combinations is too large.",e) ;
    }
    reset ();
  }

  
  @Override
  public void reset () {
    for (int i = 0; i < a.length; i++) {
      a[i] = i;
    }
    numLeft = total ;
  }

  
  /**
   * Give the next combination (algorithm from Rosen p. 286).
   * @return
   */
  @Override
  public void getNext (int[] res) {

	assert res.length == a.length ;
	
    if (numLeft == total) {
      numLeft-- ;
      copyArray(a,res) ;
      return ;
    }

    int i = r - 1;
    while (a[i] == n - r + i) {
      i--;
    }
    a[i] = a[i] + 1;
    for (int j = i + 1; j < r; j++) {
      a[j] = a[i] + j - i;
    }

    numLeft-- ; 
    copyArray(a,res) ;
    return ;
  }
  
}