/*
 * $Id$
 */

package edu.jas.util;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;


/**
 * Cartesian product of infinite components with iterator. Works also for finite
 * iterables.
 * @author Heinz Kredel
 */
public class CartesianProductInfinite implements Iterable> {


    /**
     * data structure.
     */
    public final List> comps;


    /**
     * CartesianProduct constructor.
     * @param comps components of the Cartesian product.
     */
    public CartesianProductInfinite(List> comps) {
        if (comps == null || comps.size() == 0) {
            throw new IllegalArgumentException("null components not allowed");
        }
        this.comps = comps;
    }


    /**
     * Get an iterator over subsets.
     * @return an iterator.
     */
    public Iterator> iterator() {
        if (comps.size() == 1) {
            return new CartesianOneProductInfiniteIterator(comps.get(0));
        }
        //         if ( comps.size() == 2 ) { // this part is not realy required
        //             return new CartesianTwoProductInfiniteIterator(comps.get(0),comps.get(1));
        //         }
        int n = comps.size();
        int k = n / 2 + n % 2; // ceiling
        Iterable> c0 = new CartesianProductInfinite(comps.subList(0, k));
        Iterable> c1 = new CartesianProductInfinite(comps.subList(k, n));
        return new CartesianTwoProductInfiniteIteratorList(c0, c1);
    }

}


/**
 * Cartesian product infinite iterator, one factor.
 * @author Heinz Kredel
 */
class CartesianOneProductInfiniteIterator implements Iterator> {


    /**
     * data structure.
     */
    final Iterator compit;


    /**
     * CartesianProduct iterator constructor.
     * @param comps components of the cartesian product.
     */
    public CartesianOneProductInfiniteIterator(Iterable comps) {
        if (comps == null) {
            throw new IllegalArgumentException("null comps not allowed");
        }
        compit = comps.iterator();
    }


    /**
     * Test for availability of a next tuple.
     * @return true if the iteration has more tuples, else false.
     */
    public synchronized boolean hasNext() {
        return compit.hasNext();
    }


    /**
     * Get next tuple.
     * @return next tuple.
     */
    public synchronized List next() {
        List res = new ArrayList(1);
        res.add(compit.next());
        return res;
    }


    /**
     * Remove a tuple if allowed.
     */
    public void remove() {
        throw new UnsupportedOperationException("cannnot remove tuples");
    }

}


/**
 * Cartesian product infinite iterator, two factors.
 * @author Heinz Kredel
 */
class CartesianTwoProductInfiniteIterator implements Iterator> {


    /**
     * data structure.
     */
    final Iterator compit0;


    final Iterator compit1;


    final List fincomps0;


    final List fincomps1;


    Iterator fincompit0;


    Iterator fincompit1;


    List current;


    boolean empty;


    long level;


    /**
     * CartesianProduct iterator constructor.
     * @param comps components of the Cartesian product.
     */
    public CartesianTwoProductInfiniteIterator(Iterable comps0, Iterable comps1) {
        if (comps0 == null || comps1 == null) {
            throw new IllegalArgumentException("null comps not allowed");
        }
        empty = false;
        level = 0;
        current = new ArrayList(2);

        compit0 = comps0.iterator();
        E e = compit0.next();
        current.add(e);
        fincomps0 = new ArrayList();
        fincomps0.add(e);
        fincompit0 = fincomps0.iterator();
        //E d = 
        fincompit0.next(); // remove current

        compit1 = comps1.iterator();
        e = compit1.next();
        current.add(e);
        fincomps1 = new ArrayList();
        fincomps1.add(e);
        fincompit1 = fincomps1.iterator();
        //@SuppressWarnings("unused")
        //d = 
        fincompit1.next(); // remove current
        //System.out.println("current   = " + current);
    }


    /**
     * Test for availability of a next tuple.
     * @return true if the iteration has more tuples, else false.
     */
    public synchronized boolean hasNext() {
        return !empty;
    }


    /**
     * Get next tuple.
     * @return next tuple.
     */
    public synchronized List next() {
        if (empty) {
            throw new NoSuchElementException("invalid call of next()");
        }
        List res = current; // new ArrayList(current); // copy
        if (fincompit0.hasNext() && fincompit1.hasNext()) {
            E e0 = fincompit0.next();
            E e1 = fincompit1.next();
            current = new ArrayList();
            current.add(e0);
            current.add(e1);
            return res;
        }
        level++;
        if (level % 2 == 1) {
            Collections.reverse(fincomps0);
        } else {
            Collections.reverse(fincomps1);
        }
        if (compit0.hasNext() && compit1.hasNext()) {
            fincomps0.add(compit0.next());
            fincomps1.add(compit1.next());
        } else {
            empty = true;
            return res;
        }
        if (level % 2 == 0) {
            Collections.reverse(fincomps0);
        } else {
            Collections.reverse(fincomps1);
        }
        //System.out.println("list(0) = " + fincomps0);
        //System.out.println("list(1) = " + fincomps1);
        fincompit0 = fincomps0.iterator();
        fincompit1 = fincomps1.iterator();
        E e0 = fincompit0.next();
        E e1 = fincompit1.next();
        current = new ArrayList();
        current.add(e0);
        current.add(e1);
        return res;
    }


    /**
     * Remove a tuple if allowed.
     */
    public void remove() {
        throw new UnsupportedOperationException("cannnot remove tuples");
    }

}


/**
 * Cartesian product infinite iterator, two factors list version.
 * @author Heinz Kredel
 */
class CartesianTwoProductInfiniteIteratorList implements Iterator> {


    /**
     * data structure.
     */
    final Iterator> compit0;


    final Iterator> compit1;


    final List> fincomps0;


    final List> fincomps1;


    Iterator> fincompit0;


    Iterator> fincompit1;


    List current;


    boolean empty;


    long level;


    /**
     * CartesianProduct iterator constructor.
     * @param comps components of the Cartesian product.
     */
    public CartesianTwoProductInfiniteIteratorList(Iterable> comps0, Iterable> comps1) {
        if (comps0 == null || comps1 == null) {
            throw new IllegalArgumentException("null comps not allowed");
        }
        current = new ArrayList();
        empty = false;
        level = 0;

        compit0 = comps0.iterator();
        List e = compit0.next();
        current.addAll(e);
        fincomps0 = new ArrayList>();
        fincomps0.add(e);
        fincompit0 = fincomps0.iterator();
        //List d = 
        fincompit0.next(); // remove current

        compit1 = comps1.iterator();
        e = compit1.next();
        current.addAll(e);
        fincomps1 = new ArrayList>();
        fincomps1.add(e);
        fincompit1 = fincomps1.iterator();
        //@SuppressWarnings("unused")
        //d = 
        fincompit1.next(); // remove current
        //System.out.println("current   = " + current);
    }


    /**
     * Test for availability of a next tuple.
     * @return true if the iteration has more tuples, else false.
     */
    public synchronized boolean hasNext() {
        return !empty;
    }


    /**
     * Get next tuple.
     * @return next tuple.
     */
    public synchronized List next() {
        if (empty) {
            throw new NoSuchElementException("invalid call of next()");
        }
        List res = current; // new ArrayList(current);
        if (fincompit0.hasNext() && fincompit1.hasNext()) {
            List e0 = fincompit0.next();
            List e1 = fincompit1.next();
            current = new ArrayList();
            current.addAll(e0);
            current.addAll(e1);
            return res;
        }
        level++;
        if (level % 2 == 1) {
            Collections.reverse(fincomps0);
        } else {
            Collections.reverse(fincomps1);
        }
        if (compit0.hasNext() && compit1.hasNext()) {
            fincomps0.add(compit0.next());
            fincomps1.add(compit1.next());
        } else {
            empty = true;
            return res;
        }
        if (level % 2 == 0) {
            Collections.reverse(fincomps0);
        } else {
            Collections.reverse(fincomps1);
        }
        //System.out.println("list(0) = " + fincomps0);
        //System.out.println("list(1) = " + fincomps1);
        fincompit0 = fincomps0.iterator();
        fincompit1 = fincomps1.iterator();
        List e0 = fincompit0.next();
        List e1 = fincompit1.next();
        current = new ArrayList();
        current.addAll(e0);
        current.addAll(e1);
        return res;
    }


    /**
     * Remove a tuple if allowed.
     */
    public void remove() {
        throw new UnsupportedOperationException("cannnot remove tuples");
    }

}