001    /*
002     * $Id: PowerSet.java 3571 2011-03-18 22:02:51Z kredel $
003     */
004    
005    package edu.jas.util;
006    
007    
008    import java.util.Iterator;
009    import java.util.LinkedList;
010    import java.util.List;
011    
012    
013    /**
014     * Power set with iterator.
015     * @author Heinz Kredel
016     */
017    public 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     */
050    class 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 = set.get(0);
091            rest = new LinkedList<E>(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("cannnot remove subsets");
146        }
147    
148    }