001/*
002 * $Id$
003 */
004
005package edu.jas.util;
006
007
008import java.util.Iterator;
009import java.util.LinkedList;
010import java.util.List;
011import java.util.NoSuchElementException;
012
013
014/**
015 * K-Subset with iterator.
016 * @author Heinz Kredel
017 */
018public class KsubSet<E> implements Iterable<List<E>> {
019
020
021    /**
022     * data structure.
023     */
024    public final List<E> set; // Iterable<E> also ok
025
026
027    public final int k;
028
029
030    /**
031     * KsubSet constructor.
032     * @param set generating set.
033     * @param k size of subsets.
034     */
035    public KsubSet(List<E> set, int k) {
036        if (set == null) {
037            throw new IllegalArgumentException("null set not allowed");
038        }
039        if (k < 0 || k > set.size()) {
040            throw new IllegalArgumentException("k out of range");
041        }
042        this.set = set;
043        this.k = k;
044    }
045
046
047    /**
048     * Get an iterator over subsets.
049     * @return an iterator.
050     */
051    public Iterator<List<E>> iterator() {
052        if (k == 0) {
053            return new ZeroSubSetIterator<E>(set);
054        }
055        if (k == 1) {
056            return new OneSubSetIterator<E>(set);
057        }
058        return new KsubSetIterator<E>(set, k);
059    }
060
061}
062
063
064/**
065 * Power set iterator.
066 * @author Heinz Kredel
067 */
068class KsubSetIterator<E> implements Iterator<List<E>> {
069
070
071    /**
072     * data structure.
073     */
074    public final List<E> set;
075
076
077    public final int k;
078
079
080    final List<E> rest;
081
082
083    private E current;
084
085
086    private Iterator<List<E>> recIter;
087
088
089    private final Iterator<E> iter;
090
091
092    /**
093     * KsubSetIterator constructor.
094     * @param set generating set.
095     * @param k subset size.
096     */
097    public KsubSetIterator(List<E> set, int k) {
098        if (set == null || set.size() == 0) {
099            throw new IllegalArgumentException("null or empty set not allowed");
100        }
101        if (k < 2 || k > set.size()) {
102            throw new IllegalArgumentException("k out of range");
103        }
104        this.set = set;
105        this.k = k;
106        iter = this.set.iterator();
107        current = iter.next();
108        //System.out.println("current = " + current);
109        rest = new LinkedList<E>(this.set);
110        rest.remove(0);
111        //System.out.println("rest = " + rest);
112        if (k == 2) {
113            recIter = new OneSubSetIterator<E>(rest);
114        } else {
115            recIter = new KsubSetIterator<E>(rest, k - 1);
116        }
117    }
118
119
120    /**
121     * Test for availability of a next subset.
122     * @return true if the iteration has more subsets, else false.
123     */
124    public boolean hasNext() {
125        return recIter.hasNext() || (iter.hasNext() && rest.size() >= k);
126    }
127
128
129    /**
130     * Get next subset.
131     * @return next subset.
132     */
133    public List<E> next() {
134        if (recIter.hasNext()) {
135            List<E> next = new LinkedList<E>(recIter.next());
136            next.add(0, current);
137            return next;
138        }
139        if (iter.hasNext()) {
140            current = iter.next();
141            //System.out.println("current = " + current);
142            rest.remove(0);
143            //System.out.println("rest = " + rest);
144            if (rest.size() < k - 1) {
145                throw new NoSuchElementException("invalid call of next()");
146            }
147            if (k == 2) {
148                recIter = new OneSubSetIterator<E>(rest);
149            } else {
150                recIter = new KsubSetIterator<E>(rest, k - 1);
151            }
152            return this.next(); // retry
153        }
154        throw new NoSuchElementException("invalid call of next()");
155    }
156
157
158    /**
159     * Remove the last subset returned from underlying set if allowed.
160     */
161    public void remove() {
162        throw new UnsupportedOperationException("cannot remove subsets");
163    }
164
165}
166
167
168/**
169 * One-subset iterator.
170 * @author Heinz Kredel
171 */
172class OneSubSetIterator<E> implements Iterator<List<E>> {
173
174
175    /**
176     * data structure.
177     */
178    public final List<E> set;
179
180
181    private Iterator<E> iter;
182
183
184    /**
185     * OneSubSetIterator constructor.
186     * @param set generating set.
187     */
188    public OneSubSetIterator(List<E> set) {
189        this.set = set;
190        if (set == null || set.size() == 0) {
191            iter = null;
192            return;
193        }
194        iter = this.set.iterator();
195    }
196
197
198    /**
199     * Test for availability of a next subset.
200     * @return true if the iteration has more subsets, else false.
201     */
202    public boolean hasNext() {
203        if (iter == null) {
204            return false;
205        }
206        return iter.hasNext();
207    }
208
209
210    /**
211     * Get next subset.
212     * @return next subset.
213     */
214    public List<E> next() {
215        List<E> next = new LinkedList<E>();
216        next.add(iter.next());
217        return next;
218    }
219
220
221    /**
222     * Remove the last subset returned from underlying set if allowed.
223     */
224    public void remove() {
225        throw new UnsupportedOperationException("cannot remove subsets");
226    }
227
228}
229
230
231/**
232 * Zero-subset iterator.
233 * @author Heinz Kredel
234 */
235class ZeroSubSetIterator<E> implements Iterator<List<E>> {
236
237
238    /**
239     * data structure.
240     */
241    private boolean hasNext;
242
243
244    /**
245     * ZeroSubSetIterator constructor.
246     * @param set generating set (ignored).
247     */
248    public ZeroSubSetIterator(List<E> set) {
249        hasNext = true;
250        if (set == null || set.size() == 0) {
251            hasNext = false;
252        }
253    }
254
255
256    /**
257     * Test for availability of a next subset.
258     * @return true if the iteration has more subsets, else false.
259     */
260    public boolean hasNext() {
261        return hasNext;
262    }
263
264
265    /**
266     * Get next subset.
267     * @return next subset.
268     */
269    public List<E> next() {
270        List<E> next = new LinkedList<E>();
271        hasNext = false;
272        return next;
273    }
274
275
276    /**
277     * Remove the last subset returned from underlying set if allowed.
278     */
279    public void remove() {
280        throw new UnsupportedOperationException("cannot remove subsets");
281    }
282
283}