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