001/*
002 * $Id$
003 */
004
005package edu.jas.util;
006
007
008import java.util.ArrayList;
009import java.util.Collections;
010import java.util.Iterator;
011import java.util.List;
012import java.util.NoSuchElementException;
013
014
015/**
016 * Cartesian product of infinite components with iterator. Works also for finite
017 * iterables.
018 * @author Heinz Kredel
019 */
020public 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 really 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 */
066class 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("cannot remove tuples");
112    }
113
114}
115
116
117/**
118 * Cartesian product infinite iterator, two factors.
119 * @author Heinz Kredel
120 */
121class CartesianTwoProductInfiniteIterator<E> implements Iterator<List<E>> {
122
123
124    /**
125     * data structure.
126     */
127    final Iterator<E> compit0;
128
129
130    final Iterator<E> compit1;
131
132
133    final List<E> fincomps0;
134
135
136    final List<E> fincomps1;
137
138
139    Iterator<E> fincompit0;
140
141
142    Iterator<E> fincompit1;
143
144
145    List<E> current;
146
147
148    boolean empty;
149
150
151    long level;
152
153
154    /**
155     * CartesianProduct iterator constructor.
156     * @param comps0 first components of the Cartesian product.
157     * @param comps1 second components of the Cartesian product.
158     */
159    public CartesianTwoProductInfiniteIterator(Iterable<E> comps0, Iterable<E> comps1) {
160        if (comps0 == null || comps1 == null) {
161            throw new IllegalArgumentException("null comps not allowed");
162        }
163        empty = false;
164        level = 0;
165        current = new ArrayList<E>(2);
166
167        compit0 = comps0.iterator();
168        E e = compit0.next();
169        current.add(e);
170        fincomps0 = new ArrayList<E>();
171        fincomps0.add(e);
172        fincompit0 = fincomps0.iterator();
173        //E d = 
174        fincompit0.next(); // remove current
175
176        compit1 = comps1.iterator();
177        e = compit1.next();
178        current.add(e);
179        fincomps1 = new ArrayList<E>();
180        fincomps1.add(e);
181        fincompit1 = fincomps1.iterator();
182        //@SuppressWarnings("unused")
183        //d = 
184        fincompit1.next(); // remove current
185        //System.out.println("current   = " + current);
186    }
187
188
189    /**
190     * Test for availability of a next tuple.
191     * @return true if the iteration has more tuples, else false.
192     */
193    public synchronized boolean hasNext() {
194        return !empty;
195    }
196
197
198    /**
199     * Get next tuple.
200     * @return next tuple.
201     */
202    public synchronized List<E> next() {
203        if (empty) {
204            throw new NoSuchElementException("invalid call of next()");
205        }
206        List<E> res = current; // new ArrayList<E>(current); // copy
207        if (fincompit0.hasNext() && fincompit1.hasNext()) {
208            E e0 = fincompit0.next();
209            E e1 = fincompit1.next();
210            current = new ArrayList<E>();
211            current.add(e0);
212            current.add(e1);
213            return res;
214        }
215        level++;
216        if (level % 2 == 1) {
217            Collections.reverse(fincomps0);
218        } else {
219            Collections.reverse(fincomps1);
220        }
221        if (compit0.hasNext() && compit1.hasNext()) {
222            fincomps0.add(compit0.next());
223            fincomps1.add(compit1.next());
224        } else {
225            empty = true;
226            return res;
227        }
228        if (level % 2 == 0) {
229            Collections.reverse(fincomps0);
230        } else {
231            Collections.reverse(fincomps1);
232        }
233        //System.out.println("list(0) = " + fincomps0);
234        //System.out.println("list(1) = " + fincomps1);
235        fincompit0 = fincomps0.iterator();
236        fincompit1 = fincomps1.iterator();
237        E e0 = fincompit0.next();
238        E e1 = fincompit1.next();
239        current = new ArrayList<E>();
240        current.add(e0);
241        current.add(e1);
242        return res;
243    }
244
245
246    /**
247     * Remove a tuple if allowed.
248     */
249    public void remove() {
250        throw new UnsupportedOperationException("cannot remove tuples");
251    }
252
253}
254
255
256/**
257 * Cartesian product infinite iterator, two factors list version.
258 * @author Heinz Kredel
259 */
260class CartesianTwoProductInfiniteIteratorList<E> implements Iterator<List<E>> {
261
262
263    /**
264     * data structure.
265     */
266    final Iterator<List<E>> compit0;
267
268
269    final Iterator<List<E>> compit1;
270
271
272    final List<List<E>> fincomps0;
273
274
275    final List<List<E>> fincomps1;
276
277
278    Iterator<List<E>> fincompit0;
279
280
281    Iterator<List<E>> fincompit1;
282
283
284    List<E> current;
285
286
287    boolean empty;
288
289
290    long level;
291
292
293    /**
294     * CartesianProduct iterator constructor.
295     * @param comps0 first components of the Cartesian product.
296     * @param comps1 second components of the Cartesian product.
297     */
298    public CartesianTwoProductInfiniteIteratorList(Iterable<List<E>> comps0, Iterable<List<E>> comps1) {
299        if (comps0 == null || comps1 == null) {
300            throw new IllegalArgumentException("null comps not allowed");
301        }
302        current = new ArrayList<E>();
303        empty = false;
304        level = 0;
305
306        compit0 = comps0.iterator();
307        List<E> e = compit0.next();
308        current.addAll(e);
309        fincomps0 = new ArrayList<List<E>>();
310        fincomps0.add(e);
311        fincompit0 = fincomps0.iterator();
312        //List<E> d = 
313        fincompit0.next(); // remove current
314
315        compit1 = comps1.iterator();
316        e = compit1.next();
317        current.addAll(e);
318        fincomps1 = new ArrayList<List<E>>();
319        fincomps1.add(e);
320        fincompit1 = fincomps1.iterator();
321        //@SuppressWarnings("unused")
322        //d = 
323        fincompit1.next(); // remove current
324        //System.out.println("current   = " + current);
325    }
326
327
328    /**
329     * Test for availability of a next tuple.
330     * @return true if the iteration has more tuples, else false.
331     */
332    public synchronized boolean hasNext() {
333        return !empty;
334    }
335
336
337    /**
338     * Get next tuple.
339     * @return next tuple.
340     */
341    public synchronized List<E> next() {
342        if (empty) {
343            throw new NoSuchElementException("invalid call of next()");
344        }
345        List<E> res = current; // new ArrayList<E>(current);
346        if (fincompit0.hasNext() && fincompit1.hasNext()) {
347            List<E> e0 = fincompit0.next();
348            List<E> e1 = fincompit1.next();
349            current = new ArrayList<E>();
350            current.addAll(e0);
351            current.addAll(e1);
352            return res;
353        }
354        level++;
355        if (level % 2 == 1) {
356            Collections.reverse(fincomps0);
357        } else {
358            Collections.reverse(fincomps1);
359        }
360        if (compit0.hasNext() && compit1.hasNext()) {
361            fincomps0.add(compit0.next());
362            fincomps1.add(compit1.next());
363        } else {
364            empty = true;
365            return res;
366        }
367        if (level % 2 == 0) {
368            Collections.reverse(fincomps0);
369        } else {
370            Collections.reverse(fincomps1);
371        }
372        //System.out.println("list(0) = " + fincomps0);
373        //System.out.println("list(1) = " + fincomps1);
374        fincompit0 = fincomps0.iterator();
375        fincompit1 = fincomps1.iterator();
376        List<E> e0 = fincompit0.next();
377        List<E> e1 = fincompit1.next();
378        current = new ArrayList<E>();
379        current.addAll(e0);
380        current.addAll(e1);
381        return res;
382    }
383
384
385    /**
386     * Remove a tuple if allowed.
387     */
388    public void remove() {
389        throw new UnsupportedOperationException("cannot remove tuples");
390    }
391
392}