
package de.ivu.elect.business.ergebniskonflikt.control.util;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import com.google.common.math.IntMath;

/**
 * Returns a {@link List} of all the lists containing a given fixed number of elements of the specified
 * {@link Collection} in the same order.
 * <p/>
 * If the input list contains equal elements, some of the generated permutations will be equal.
 * 
 * @param elements
 *          the original collection whose elements have to be permuted.
 * @return an immutable {@link List} containing all the different permutations of the original collection.
 * @throws NullPointerException
 *           if the specified collection is null
 */
public class SublistList<E> extends AbstractList<List<E>> {

  private final List<E> elements;
  private final int n;
  private final int k;

  public SublistList(Collection<E> elements, int sizeOfSublists) {
    super();
    this.elements = new ArrayList<>(elements);
    this.n = elements.size();
    this.k = sizeOfSublists;
    if (k < 0 || n < k) {
      throw new IllegalArgumentException();
    }
  }

  @Override
  public List<E> get(int index) {
    if (index < 0 || index >= size()) {
      throw new IndexOutOfBoundsException("SublistList: size = " + size() + ", index = " + index);
    }

    List<E> result = new ArrayList<>(k);
    int rest = index;
    int restOfK = k;
    for (int i = 0; i < n; i++) {
      if (restOfK == 0) {
        return result;
      }
      int binomial = safeBinomial(n - i - 1, restOfK - 1);
      if (rest < binomial) {
        result.add(elements.get(i));
        restOfK--;
      } else {
        rest -= binomial;
      }
    }
    return result;
  }

  private int safeBinomial(int n, int k) {
    if (k < 0 || k > n) {
      return 0;
    } else {
      return IntMath.binomial(n, k);
    }
  }

  @Override
  public int size() {
    return IntMath.binomial(n, k);
  }

  @Override
  public String toString() {
    return getClass().getSimpleName() + " (elements = " + elements.toString() + ")";
  }
}
