/**
 * Uses Heap's algorithm to produce all permutations of a given list.
 * We use an iterator to avoid having to use too much memory.
 *
 * @author t.wood
 *
 * Copyright 2016 Tim Wood
 *
 * Permission is hereby granted, free of charge, to any person 
 * obtaining a copy of this software and associated documentation 
 * files (the "Software"), to deal in the Software without restriction,
 * including without limitation the rights to use, copy, modify, merge,
 * publish, distribute, sublicense, and/or sell copies of the Software,
 * and to permit persons to whom the Software is furnished to do so, 
 * subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 * @param <T> The type of item being permuted
 * @param <R> The type resulting from decorating the permutation
 */
public final class PermutationIterator<T,R> implements Iterator<R> {
    private final Function<List<T>, R> defensiveDecorator;
    private final List<T> a;
    private R pending;
 
    private final int[] skel;
    private int i;
 
    /**
     * An iterator of permutations
     *
     * @param a the list to permute
     * @param decorator a decorator to apply to the permutation, a defensive copy
     *                  of the permutation is taken before it is passed to the decorator
     */
    public PermutationIterator(final List<T> a, final Function<List<T>,R> decorator) {
        defensiveDecorator = t -> decorator.apply(new ArrayList<>(t));
        pending = defensiveDecorator.apply(a);
        this.a = new ArrayList<>(a);
        skel = new int[a.size()];
        i = 0;
    }
 
    @Override public boolean hasNext() {
        return pending != null;
    }
 
    @Override public R next() {
        if(pending == null) {
            throw new IndexOutOfBoundsException();
        }
        final R result = pending;
        pending = permute();
        return result;
    }
 
    private R permute() {
        while(i < a.size()) {
            if (skel[i] < i) {
                if (even(i)) {
                    swap(a, 0, i);
                } else {
                    swap(a, skel[i], i);
                }
                skel[i] += 1;
                i = 0;
                return defensiveDecorator.apply(a);
            } else {
                skel[i] = 0;
                i += 1;
            }
        }
        return null;
    }
 
    private void swap(final List<T> a, final int i0, final int i1) {
        final T t = a.get(i0);
        a.set(i0, a.get(i1));
        a.set(i1, t);
    }
 
    private boolean even(final int i) {
        return i % 2 == 0;
    }
}