/*
 * $Id$
 */

package edu.jas.util;


import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;


/**
 * K-Subset with iterator.
 * @author Heinz Kredel
 */
public class KsubSet implements Iterable> {


    /**
     * data structure.
     */
    public final List set; // Iterable also ok


    public final int k;


    /**
     * KsubSet constructor.
     * @param set generating set.
     * @param k size of subsets.
     */
    public KsubSet(List set, int k) {
        if (set == null) {
            throw new IllegalArgumentException("null set not allowed");
        }
        if (k < 0 || k > set.size()) {
            throw new IllegalArgumentException("k out of range");
        }
        this.set = set;
        this.k = k;
    }


    /**
     * Get an iterator over subsets.
     * @return an iterator.
     */
    public Iterator> iterator() {
        if (k == 0) {
            return new ZeroSubSetIterator(set);
        }
        if (k == 1) {
            return new OneSubSetIterator(set);
        }
        return new KsubSetIterator(set, k);
    }

}


/**
 * Power set iterator.
 * @author Heinz Kredel
 */
class KsubSetIterator implements Iterator> {


    /**
     * data structure.
     */
    public final List set;


    public final int k;


    final List rest;


    private E current;


    private Iterator> recIter;


    private final Iterator iter;


    /**
     * KsubSetIterator constructor.
     * @param set generating set.
     * @param k subset size.
     */
    public KsubSetIterator(List set, int k) {
        if (set == null || set.size() == 0) {
            throw new IllegalArgumentException("null or empty set not allowed");
        }
        if (k < 2 || k > set.size()) {
            throw new IllegalArgumentException("k out of range");
        }
        this.set = set;
        this.k = k;
        iter = this.set.iterator();
        current = iter.next();
        //System.out.println("current = " + current);
        rest = new LinkedList(this.set);
        rest.remove(0);
        //System.out.println("rest = " + rest);
        if (k == 2) {
            recIter = new OneSubSetIterator(rest);
        } else {
            recIter = new KsubSetIterator(rest, k - 1);
        }
    }


    /**
     * Test for availability of a next subset.
     * @return true if the iteration has more subsets, else false.
     */
    public boolean hasNext() {
        return recIter.hasNext() || (iter.hasNext() && rest.size() >= k);
    }


    /**
     * Get next subset.
     * @return next subset.
     */
    public List next() {
        if (recIter.hasNext()) {
            List next = new LinkedList(recIter.next());
            next.add(0, current);
            return next;
        }
        if (iter.hasNext()) {
            current = iter.next();
            //System.out.println("current = " + current);
            rest.remove(0);
            //System.out.println("rest = " + rest);
            if (rest.size() < k - 1) {
                throw new NoSuchElementException("invalid call of next()");
            }
            if (k == 2) {
                recIter = new OneSubSetIterator(rest);
            } else {
                recIter = new KsubSetIterator(rest, k - 1);
            }
            return this.next(); // retry
        }
        throw new NoSuchElementException("invalid call of next()");
    }


    /**
     * Remove the last subset returned from underlying set if allowed.
     */
    public void remove() {
        throw new UnsupportedOperationException("cannnot remove subsets");
    }

}


/**
 * One-subset iterator.
 * @author Heinz Kredel
 */
class OneSubSetIterator implements Iterator> {


    /**
     * data structure.
     */
    public final List set;


    private Iterator iter;


    /**
     * OneSubSetIterator constructor.
     * @param set generating set.
     */
    public OneSubSetIterator(List set) {
        this.set = set;
        if (set == null || set.size() == 0) {
            iter = null;
            return;
        }
        iter = this.set.iterator();
    }


    /**
     * Test for availability of a next subset.
     * @return true if the iteration has more subsets, else false.
     */
    public boolean hasNext() {
        if (iter == null) {
            return false;
        }
        return iter.hasNext();
    }


    /**
     * Get next subset.
     * @return next subset.
     */
    public List next() {
        List next = new LinkedList();
        next.add(iter.next());
        return next;
    }


    /**
     * Remove the last subset returned from underlying set if allowed.
     */
    public void remove() {
        throw new UnsupportedOperationException("cannnot remove subsets");
    }

}


/**
 * Zero-subset iterator.
 * @author Heinz Kredel
 */
class ZeroSubSetIterator implements Iterator> {


    /**
     * data structure.
     */
    private boolean hasNext;


    /**
     * ZeroSubSetIterator constructor.
     * @param set generating set (ignored).
     */
    public ZeroSubSetIterator(List set) {
        hasNext = true;
    }


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


    /**
     * Get next subset.
     * @return next subset.
     */
    public List next() {
        List next = new LinkedList();
        hasNext = false;
        return next;
    }


    /**
     * Remove the last subset returned from underlying set if allowed.
     */
    public void remove() {
        throw new UnsupportedOperationException("cannnot remove subsets");
    }

}