001 /*
002 * $Id: CartesianProductInfinite.java 3297 2010-08-26 19:09:03Z kredel $
003 */
004
005 package edu.jas.util;
006
007
008 import java.util.ArrayList;
009 import java.util.Iterator;
010 import java.util.List;
011 import java.util.Collections;
012 import java.util.NoSuchElementException;
013
014
015 /**
016 * Cartesian product of infinite components with iterator.
017 * Works also for finite iterables.
018 * @author Heinz Kredel
019 */
020 public class CartesianProductInfinite<E> implements Iterable<List<E>> {
021
022
023 /**
024 * data structure.
025 */
026 public final List<Iterable<E>> comps;
027
028
029 /**
030 * CartesianProduct constructor.
031 * @param comps components of the cartesian product.
032 */
033 public CartesianProductInfinite(List<Iterable<E>> comps) {
034 if (comps == null || comps.size() == 0) {
035 throw new IllegalArgumentException("null components not allowed");
036 }
037 this.comps = comps;
038 }
039
040
041 /**
042 * Get an iterator over subsets.
043 * @return an iterator.
044 */
045 public Iterator<List<E>> iterator() {
046 if ( comps.size() == 1 ) {
047 return new CartesianOneProductInfiniteIterator<E>(comps.get(0));
048 }
049 // if ( comps.size() == 2 ) { // this part is not realy required
050 // return new CartesianTwoProductInfiniteIterator<E>(comps.get(0),comps.get(1));
051 // }
052 int n = comps.size();
053 int k = n / 2 + n % 2; // ceiling
054 Iterable<List<E>> c0 = new CartesianProductInfinite<E>( comps.subList(0,k) );
055 Iterable<List<E>> c1 = new CartesianProductInfinite<E>( comps.subList(k,n) );
056 return new CartesianTwoProductInfiniteIteratorList<E>(c0,c1);
057 }
058
059 }
060
061
062 /**
063 * Cartesian product infinite iterator, one factor.
064 * @author Heinz Kredel
065 */
066 class CartesianOneProductInfiniteIterator<E> implements Iterator<List<E>> {
067
068
069 /**
070 * data structure.
071 */
072 final Iterator<E> compit;
073
074
075 /**
076 * CartesianProduct iterator constructor.
077 * @param comps components of the cartesian product.
078 */
079 public CartesianOneProductInfiniteIterator(Iterable<E> comps) {
080 if (comps == null) {
081 throw new IllegalArgumentException("null comps not allowed");
082 }
083 compit = comps.iterator();
084 }
085
086
087 /**
088 * Test for availability of a next tuple.
089 * @return true if the iteration has more tuples, else false.
090 */
091 public synchronized boolean hasNext() {
092 return compit.hasNext();
093 }
094
095
096 /**
097 * Get next tuple.
098 * @return next tuple.
099 */
100 public synchronized List<E> next() {
101 List<E> res = new ArrayList<E>(1);
102 res.add( compit.next() );
103 return res;
104 }
105
106
107 /**
108 * Remove a tuple if allowed.
109 */
110 public void remove() {
111 throw new UnsupportedOperationException("cannnot remove tuples");
112 }
113
114 }
115
116
117 /**
118 * Cartesian product infinite iterator, two factors.
119 * @author Heinz Kredel
120 */
121 class CartesianTwoProductInfiniteIterator<E> implements Iterator<List<E>> {
122
123
124 /**
125 * data structure.
126 */
127 final Iterator<E> compit0;
128 final Iterator<E> compit1;
129
130
131 final List<E> fincomps0;
132 final List<E> fincomps1;
133
134
135 Iterator<E> fincompit0;
136 Iterator<E> fincompit1;
137
138
139 List<E> current;
140
141
142 boolean empty;
143
144
145 long level;
146
147
148 /**
149 * CartesianProduct iterator constructor.
150 * @param comps components of the cartesian product.
151 */
152 public CartesianTwoProductInfiniteIterator(Iterable<E> comps0, Iterable<E> comps1) {
153 if (comps0 == null || comps1 == null) {
154 throw new IllegalArgumentException("null comps not allowed");
155 }
156 empty = false;
157 level = 0;
158 current = new ArrayList<E>(2);
159
160 compit0 = comps0.iterator();
161 E e = compit0.next();
162 current.add(e);
163 fincomps0 = new ArrayList<E>();
164 fincomps0.add(e);
165 fincompit0 = fincomps0.iterator();
166 E d = fincompit0.next(); // remove current
167
168 compit1 = comps1.iterator();
169 e = compit1.next();
170 current.add(e);
171 fincomps1 = new ArrayList<E>();
172 fincomps1.add(e);
173 fincompit1 = fincomps1.iterator();
174 d = fincompit1.next(); // remove current
175 //System.out.println("current = " + current);
176 }
177
178
179 /**
180 * Test for availability of a next tuple.
181 * @return true if the iteration has more tuples, else false.
182 */
183 public synchronized boolean hasNext() {
184 return !empty;
185 }
186
187
188 /**
189 * Get next tuple.
190 * @return next tuple.
191 */
192 public synchronized List<E> next() {
193 if (empty) {
194 throw new NoSuchElementException("invalid call of next()");
195 }
196 List<E> res = current; // new ArrayList<E>(current); // copy
197 if ( fincompit0.hasNext() && fincompit1.hasNext() ) {
198 E e0 = fincompit0.next();
199 E e1 = fincompit1.next();
200 current = new ArrayList<E>();
201 current.add(e0);
202 current.add(e1);
203 return res;
204 }
205 level++;
206 if ( level % 2 == 1 ) {
207 Collections.reverse(fincomps0);
208 } else {
209 Collections.reverse(fincomps1);
210 }
211 if ( compit0.hasNext() && compit1.hasNext() ) {
212 fincomps0.add( compit0.next() );
213 fincomps1.add( compit1.next() );
214 } else {
215 empty = true;
216 return res;
217 }
218 if ( level % 2 == 0 ) {
219 Collections.reverse(fincomps0);
220 } else {
221 Collections.reverse(fincomps1);
222 }
223 //System.out.println("list(0) = " + fincomps0);
224 //System.out.println("list(1) = " + fincomps1);
225 fincompit0 = fincomps0.iterator();
226 fincompit1 = fincomps1.iterator();
227 E e0 = fincompit0.next();
228 E e1 = fincompit1.next();
229 current = new ArrayList<E>();
230 current.add(e0);
231 current.add(e1);
232 return res;
233 }
234
235
236 /**
237 * Remove a tuple if allowed.
238 */
239 public void remove() {
240 throw new UnsupportedOperationException("cannnot remove tuples");
241 }
242
243 }
244
245
246 /**
247 * Cartesian product infinite iterator, two factors list version.
248 * @author Heinz Kredel
249 */
250 class CartesianTwoProductInfiniteIteratorList<E> implements Iterator<List<E>> {
251
252
253 /**
254 * data structure.
255 */
256 final Iterator<List<E>> compit0;
257 final Iterator<List<E>> compit1;
258
259
260 final List<List<E>> fincomps0;
261 final List<List<E>> fincomps1;
262
263
264 Iterator<List<E>> fincompit0;
265 Iterator<List<E>> fincompit1;
266
267
268 List<E> current;
269
270
271 boolean empty;
272
273
274 long level;
275
276
277 /**
278 * CartesianProduct iterator constructor.
279 * @param comps components of the cartesian product.
280 */
281 public CartesianTwoProductInfiniteIteratorList(Iterable<List<E>> comps0, Iterable<List<E>> comps1) {
282 if (comps0 == null || comps1 == null) {
283 throw new IllegalArgumentException("null comps not allowed");
284 }
285 current = new ArrayList<E>();
286 empty = false;
287 level = 0;
288
289 compit0 = comps0.iterator();
290 List<E> e = compit0.next();
291 current.addAll(e);
292 fincomps0 = new ArrayList<List<E>>();
293 fincomps0.add(e);
294 fincompit0 = fincomps0.iterator();
295 List<E> d = fincompit0.next(); // remove current
296
297 compit1 = comps1.iterator();
298 e = compit1.next();
299 current.addAll(e);
300 fincomps1 = new ArrayList<List<E>>();
301 fincomps1.add(e);
302 fincompit1 = fincomps1.iterator();
303 d = fincompit1.next(); // remove current
304 //System.out.println("current = " + current);
305 }
306
307
308 /**
309 * Test for availability of a next tuple.
310 * @return true if the iteration has more tuples, else false.
311 */
312 public synchronized boolean hasNext() {
313 return !empty;
314 }
315
316
317 /**
318 * Get next tuple.
319 * @return next tuple.
320 */
321 public synchronized List<E> next() {
322 if (empty) {
323 throw new NoSuchElementException("invalid call of next()");
324 }
325 List<E> res = current; // new ArrayList<E>(current);
326 if ( fincompit0.hasNext() && fincompit1.hasNext() ) {
327 List<E> e0 = fincompit0.next();
328 List<E> e1 = fincompit1.next();
329 current = new ArrayList<E>();
330 current.addAll(e0);
331 current.addAll(e1);
332 return res;
333 }
334 level++;
335 if ( level % 2 == 1 ) {
336 Collections.reverse(fincomps0);
337 } else {
338 Collections.reverse(fincomps1);
339 }
340 if ( compit0.hasNext() && compit1.hasNext() ) {
341 fincomps0.add( compit0.next() );
342 fincomps1.add( compit1.next() );
343 } else {
344 empty = true;
345 return res;
346 }
347 if ( level % 2 == 0 ) {
348 Collections.reverse(fincomps0);
349 } else {
350 Collections.reverse(fincomps1);
351 }
352 //System.out.println("list(0) = " + fincomps0);
353 //System.out.println("list(1) = " + fincomps1);
354 fincompit0 = fincomps0.iterator();
355 fincompit1 = fincomps1.iterator();
356 List<E> e0 = fincompit0.next();
357 List<E> e1 = fincompit1.next();
358 current = new ArrayList<E>();
359 current.addAll(e0);
360 current.addAll(e1);
361 return res;
362 }
363
364
365 /**
366 * Remove a tuple if allowed.
367 */
368 public void remove() {
369 throw new UnsupportedOperationException("cannnot remove tuples");
370 }
371
372 }