001/*
002 * $Id: CartesianProductInfinite.java 4638 2013-09-13 19:14:05Z kredel $
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 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 */
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("cannnot 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 comps components of the Cartesian product.
157     */
158    public CartesianTwoProductInfiniteIterator(Iterable<E> comps0, Iterable<E> comps1) {
159        if (comps0 == null || comps1 == null) {
160            throw new IllegalArgumentException("null comps not allowed");
161        }
162        empty = false;
163        level = 0;
164        current = new ArrayList<E>(2);
165
166        compit0 = comps0.iterator();
167        E e = compit0.next();
168        current.add(e);
169        fincomps0 = new ArrayList<E>();
170        fincomps0.add(e);
171        fincompit0 = fincomps0.iterator();
172        //E d = 
173        fincompit0.next(); // remove current
174
175        compit1 = comps1.iterator();
176        e = compit1.next();
177        current.add(e);
178        fincomps1 = new ArrayList<E>();
179        fincomps1.add(e);
180        fincompit1 = fincomps1.iterator();
181        //@SuppressWarnings("unused")
182        //d = 
183        fincompit1.next(); // remove current
184        //System.out.println("current   = " + current);
185    }
186
187
188    /**
189     * Test for availability of a next tuple.
190     * @return true if the iteration has more tuples, else false.
191     */
192    public synchronized boolean hasNext() {
193        return !empty;
194    }
195
196
197    /**
198     * Get next tuple.
199     * @return next tuple.
200     */
201    public synchronized List<E> next() {
202        if (empty) {
203            throw new NoSuchElementException("invalid call of next()");
204        }
205        List<E> res = current; // new ArrayList<E>(current); // copy
206        if (fincompit0.hasNext() && fincompit1.hasNext()) {
207            E e0 = fincompit0.next();
208            E e1 = fincompit1.next();
209            current = new ArrayList<E>();
210            current.add(e0);
211            current.add(e1);
212            return res;
213        }
214        level++;
215        if (level % 2 == 1) {
216            Collections.reverse(fincomps0);
217        } else {
218            Collections.reverse(fincomps1);
219        }
220        if (compit0.hasNext() && compit1.hasNext()) {
221            fincomps0.add(compit0.next());
222            fincomps1.add(compit1.next());
223        } else {
224            empty = true;
225            return res;
226        }
227        if (level % 2 == 0) {
228            Collections.reverse(fincomps0);
229        } else {
230            Collections.reverse(fincomps1);
231        }
232        //System.out.println("list(0) = " + fincomps0);
233        //System.out.println("list(1) = " + fincomps1);
234        fincompit0 = fincomps0.iterator();
235        fincompit1 = fincomps1.iterator();
236        E e0 = fincompit0.next();
237        E e1 = fincompit1.next();
238        current = new ArrayList<E>();
239        current.add(e0);
240        current.add(e1);
241        return res;
242    }
243
244
245    /**
246     * Remove a tuple if allowed.
247     */
248    public void remove() {
249        throw new UnsupportedOperationException("cannnot remove tuples");
250    }
251
252}
253
254
255/**
256 * Cartesian product infinite iterator, two factors list version.
257 * @author Heinz Kredel
258 */
259class CartesianTwoProductInfiniteIteratorList<E> implements Iterator<List<E>> {
260
261
262    /**
263     * data structure.
264     */
265    final Iterator<List<E>> compit0;
266
267
268    final Iterator<List<E>> compit1;
269
270
271    final List<List<E>> fincomps0;
272
273
274    final List<List<E>> fincomps1;
275
276
277    Iterator<List<E>> fincompit0;
278
279
280    Iterator<List<E>> fincompit1;
281
282
283    List<E> current;
284
285
286    boolean empty;
287
288
289    long level;
290
291
292    /**
293     * CartesianProduct iterator constructor.
294     * @param comps components of the Cartesian product.
295     */
296    public CartesianTwoProductInfiniteIteratorList(Iterable<List<E>> comps0, Iterable<List<E>> comps1) {
297        if (comps0 == null || comps1 == null) {
298            throw new IllegalArgumentException("null comps not allowed");
299        }
300        current = new ArrayList<E>();
301        empty = false;
302        level = 0;
303
304        compit0 = comps0.iterator();
305        List<E> e = compit0.next();
306        current.addAll(e);
307        fincomps0 = new ArrayList<List<E>>();
308        fincomps0.add(e);
309        fincompit0 = fincomps0.iterator();
310        //List<E> d = 
311        fincompit0.next(); // remove current
312
313        compit1 = comps1.iterator();
314        e = compit1.next();
315        current.addAll(e);
316        fincomps1 = new ArrayList<List<E>>();
317        fincomps1.add(e);
318        fincompit1 = fincomps1.iterator();
319        //@SuppressWarnings("unused")
320        //d = 
321        fincompit1.next(); // remove current
322        //System.out.println("current   = " + current);
323    }
324
325
326    /**
327     * Test for availability of a next tuple.
328     * @return true if the iteration has more tuples, else false.
329     */
330    public synchronized boolean hasNext() {
331        return !empty;
332    }
333
334
335    /**
336     * Get next tuple.
337     * @return next tuple.
338     */
339    public synchronized List<E> next() {
340        if (empty) {
341            throw new NoSuchElementException("invalid call of next()");
342        }
343        List<E> res = current; // new ArrayList<E>(current);
344        if (fincompit0.hasNext() && fincompit1.hasNext()) {
345            List<E> e0 = fincompit0.next();
346            List<E> e1 = fincompit1.next();
347            current = new ArrayList<E>();
348            current.addAll(e0);
349            current.addAll(e1);
350            return res;
351        }
352        level++;
353        if (level % 2 == 1) {
354            Collections.reverse(fincomps0);
355        } else {
356            Collections.reverse(fincomps1);
357        }
358        if (compit0.hasNext() && compit1.hasNext()) {
359            fincomps0.add(compit0.next());
360            fincomps1.add(compit1.next());
361        } else {
362            empty = true;
363            return res;
364        }
365        if (level % 2 == 0) {
366            Collections.reverse(fincomps0);
367        } else {
368            Collections.reverse(fincomps1);
369        }
370        //System.out.println("list(0) = " + fincomps0);
371        //System.out.println("list(1) = " + fincomps1);
372        fincompit0 = fincomps0.iterator();
373        fincompit1 = fincomps1.iterator();
374        List<E> e0 = fincompit0.next();
375        List<E> e1 = fincompit1.next();
376        current = new ArrayList<E>();
377        current.addAll(e0);
378        current.addAll(e1);
379        return res;
380    }
381
382
383    /**
384     * Remove a tuple if allowed.
385     */
386    public void remove() {
387        throw new UnsupportedOperationException("cannnot remove tuples");
388    }
389
390}