001/*
002 * $Id$
003 */
004
005package edu.jas.util;
006
007
008import java.util.Iterator;
009import java.util.LinkedList;
010import java.util.List;
011
012
013/**
014 * Power set with iterator.
015 * @author Heinz Kredel
016 */
017public class PowerSet<E> implements Iterable<List<E>> {
018
019
020    /**
021     * data structure.
022     */
023    public final List<E> set; // Iterable<E> also ok
024
025
026    /**
027     * PowerSet constructor.
028     * @param set generating set.
029     */
030    public PowerSet(List<E> set) {
031        this.set = set;
032    }
033
034
035    /**
036     * get an iterator over subsets.
037     * @return an iterator.
038     */
039    public Iterator<List<E>> iterator() {
040        return new PowerSetIterator<E>(set);
041    }
042
043}
044
045
046/**
047 * Power set iterator.
048 * @author Heinz Kredel
049 */
050class PowerSetIterator<E> implements Iterator<List<E>> {
051
052
053    /**
054     * data structure.
055     */
056    public final List<E> set;
057
058
059    final List<E> rest;
060
061
062    final E current;
063
064
065    private PowerSetIterator<E> recIter;
066
067
068    enum Mode {
069        copy, extend, first, done
070    };
071
072
073    Mode mode;
074
075
076    /**
077     * PowerSetIterator constructor.
078     * @param set generating set.
079     */
080    public PowerSetIterator(List<E> set) {
081        this.set = set;
082        if (set == null || set.size() == 0) {
083            current = null;
084            recIter = null;
085            rest = null;
086            mode = Mode.first;
087            return;
088        }
089        mode = Mode.copy;
090        current = this.set.get(0);
091        rest = new LinkedList<E>(this.set);
092        rest.remove(0);
093        recIter = new PowerSetIterator<E>(rest);
094    }
095
096
097    /**
098     * Test for availability of a next subset.
099     * @return true if the iteration has more subsets, else false.
100     */
101    public boolean hasNext() {
102        if (mode == Mode.first) {
103            return true;
104        }
105        if (recIter == null) {
106            return false;
107        }
108        return recIter.hasNext() || mode == Mode.copy;
109    }
110
111
112    /**
113     * Get next subset.
114     * @return next subset.
115     */
116    public List<E> next() {
117        if (mode == Mode.first) {
118            mode = Mode.done;
119            List<E> first = new LinkedList<E>();
120            return first;
121        }
122        if (mode == Mode.extend) {
123            if (recIter.hasNext()) {
124                List<E> next = new LinkedList<E>(recIter.next());
125                next.add(current);
126                return next;
127            }
128        }
129        if (mode == Mode.copy) {
130            if (recIter.hasNext()) {
131                return recIter.next();
132            }
133            mode = Mode.extend;
134            recIter = new PowerSetIterator<E>(rest);
135            return this.next();
136        }
137        return null;
138    }
139
140
141    /**
142     * Remove the last subset returned from underlying set if allowed.
143     */
144    public void remove() {
145        throw new UnsupportedOperationException("cannot remove subsets");
146    }
147
148}