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

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

import com.google.common.math.IntMath;

/**
 * Returns a {@link List} of all the permutations of the specified {@link Collection}.
 * <p/>
 * If the input list contains equal elements, some of the generated permutations will be equal.
 * <p/>
 * An empty collection has only one permutation, which is an empty list.
 * 
 * @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 PermutationList<E> extends AbstractList<List<E>> {

  private final List<E> elements;

  public PermutationList(Collection<E> elements) {
    super();
    this.elements = new ArrayList<>(elements);
  }

  @Override
  public List<E> get(int index) {
    if (index < 0 || index >= size()) {
      throw new IndexOutOfBoundsException("PermutationList: size = " + size() + ", index = " + index);
    }
    LinkedList<E> linkedList = new LinkedList<>(elements);
    int size = elements.size();
    List<E> result = new ArrayList<>(size);
    int rest = index;
    for (int i = 0; i < size; i++) {
      int fac = IntMath.factorial(size - i - 1);
      if (fac == Integer.MAX_VALUE) {
        result.add(linkedList.removeFirst());
      } else {
        result.add(linkedList.remove(rest / fac));
        rest = rest % fac;
      }
    }
    return result;
  }

  @Override
  public int size() {
    return IntMath.factorial(elements.size());
  }

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