package tjg.testing;

import java.util.ArrayList;
import java.util.List;

/**
 * Not a classic iterator, it returns all the permutations of the list of items passed in the constructor
 * the number of items to iterate through will be list.size()! (factorial)
 * 
 * The design is recursive. The first element of the list is set on positions 0 to list.size()-1 and the 
 * permutations of the other elements returned by the iterator of dimension smaller by 1 are placed around it
 * 
 * DO NOT use for large sizes (>10)
 * 
 * @author tgil
 *
 * @param <T>
 */
public class PermutationsIterator<T>
{
    public boolean hasNext()
    {
        if ( one == -1 )
            return false;
        if ( canonical.size() == 1 )
            return true;
        if ( (one == canonical.size()-1 &&  !sub.hasNext() ) )
            return false;
        return true;
    }
    
    public List<T> next()
    {
        if ( canonical.size() == 1 )
        {
            one = -1;
            return canonical;
        }
        
        if ( !sub.hasNext() )
        {
            one++;
            List<T> n = new ArrayList<T>();
            n.addAll(canonical.subList(0, one));
            if ( one < canonical.size() )
            {
                List<T> n2 = canonical.subList(one+1, canonical.size());
                n.addAll(n2);
            }
            sub = new PermutationsIterator<T>(n);
        }
        
        List<T> r = new ArrayList<T>();
        r.add(canonical.get(one));
        r.addAll(sub.next());
        return r;
        
    }
    
    private List<T> canonical;
    private int one;
    private PermutationsIterator<T> sub;
    
    public PermutationsIterator(List<T> s)
    {
        canonical = s;
        one = 0;
        if ( s == null || s.size() == 0 )
        {
            one = -1;
            return;
        }
        if ( canonical.size() == 1)
            return;
        sub = new PermutationsIterator<T>(canonical.subList(1, canonical.size()));
    }
}