package org.matheclipse.combinatoric;

import java.util.Iterator;

/**
 * 

 * Combinations of a multiset
 * 
 * 

 * These are the combinations of k elements chosen from a sorted
 * int[] array, that can contain duplicates (a multiset).
 * 
 * 

 * For example, given the multiset {0, 1, 1, 2, 2, 2, 3}, the
 * 4-combinations are:
 * 
 * 
 * 
 * [0, 1, 1, 2]
 * [0, 1, 1, 3]
 * [0, 1, 2, 2]
 * [0, 1, 2, 3]
 * [0, 2, 2, 2]
 * [0, 2, 2, 3]
 * [1, 1, 2, 2]
 * [1, 1, 2, 3]
 * [1, 2, 2, 2]
 * [1, 2, 2, 3]
 * [2, 2, 2, 3]
 * 
 * 
 * 

 * This algorithm produces the combinations in lexicographic order, with the
 * elements in each combination in increasing order.
 * 
 * 

 * Begin with the first combination, which is the first k elements of
 * the multiset ([0, 1, 1, 2] in the example above), and then at each step:
 * 
 * 

 * 
Find the rightmost element that is less than the maximum value it can
 * have (which is the element in the multiset that is the same distance from the
 * right).
 * 
Replace it with the first multiset element greater than it.
 * 
Replace the remainder of the combination with the elements that follow
 * the replacement in the multiset.
 * 
 * 
 * 

 * See: martinbroadhurst.com Combinations of a Multiset
 */
public class MultisetCombinationIterator implements Iterator {

	private int[] result;
	private final int[] multiset;
	private final int n;
	private final int k;

	/**
	 * 

	 * Combinations of a multiset
	 * 
	 * 

	 * These are the combinations of k elements chosen from a sorted
	 * int[] array, that can contain duplicates (a multiset).
	 * 
	 */
	public MultisetCombinationIterator(int[] multiset, final int k) {
		this.multiset = multiset;
		this.n = multiset.length;
		this.k = k;
		this.result = null;
	}

	public void reset() {
		this.result = null;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @see Iterator#next()
	 */
	public int[] next() {
		if (result == null) {
			result = new int[k];
			System.arraycopy(multiset, 0, result, 0, k);
		} else { 
			for (int i = k - 1; i >= 0; i--) {
				if (result[i] < multiset[i + (n - k)]) {
					// Find the successor
					int j;
					for (j = 0; multiset[j] <= result[i]; j++) {

					}
					// Replace this element with it
					result[i] = multiset[j];
					if (i < k - 1) {
						// Make the elements after it the same as this part of the multiset
						int l;
						for (l = i + 1, j = j + 1; l < k; l++, j++) {
							result[l] = multiset[j];
						}
					}
					return result;
				} 
			}
		}
		return result;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @see Iterator#hasNext()
	 */
	public final boolean hasNext() {
		if (result == null) {
			return true;
		}
		for (int i = k - 1; i >= 0; i--) {
			if (result[i] < multiset[i + (n - k)]) {
				return true;
			} 
		}
		return false;
	}

	/**
	 * Throws an UnsupportedOperationException
	 */
	@Override
	public void remove() {
		throw new UnsupportedOperationException("This iterator doesn't support the remove() method");
	}

}