001 /*
002 * $Id: KsubSet.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 import java.util.NoSuchElementException;
012
013
014 /**
015 * K-Subset with iterator.
016 * @author Heinz Kredel
017 */
018 public 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 this.set = set;
040 if (k < 0 || k > set.size()) {
041 throw new IllegalArgumentException("k out of range");
042 }
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 */
068 class 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 this.set = set;
102 if (k < 2 || k > set.size()) {
103 throw new IllegalArgumentException("k out of range");
104 }
105 this.k = k;
106 iter = set.iterator();
107 current = iter.next();
108 //System.out.println("current = " + current);
109 rest = new LinkedList<E>(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("cannnot remove subsets");
163 }
164
165 }
166
167
168 /**
169 * One-subset iterator.
170 * @author Heinz Kredel
171 */
172 class 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 = 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("cannnot remove subsets");
226 }
227
228 }
229
230
231 /**
232 * Zero-subset iterator.
233 * @author Heinz Kredel
234 */
235 class 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 }
251
252
253 /**
254 * Test for availability of a next subset.
255 * @return true if the iteration has more subsets, else false.
256 */
257 public boolean hasNext() {
258 return hasNext;
259 }
260
261
262 /**
263 * Get next subset.
264 * @return next subset.
265 */
266 public List<E> next() {
267 List<E> next = new LinkedList<E>();
268 hasNext = false;
269 return next;
270 }
271
272
273 /**
274 * Remove the last subset returned from underlying set if allowed.
275 */
276 public void remove() {
277 throw new UnsupportedOperationException("cannnot remove subsets");
278 }
279
280 }