001/*
002 * $Id$
003 */
004
005package edu.jas.util;
006
007
008import java.util.ArrayList;
009import java.util.Iterator;
010import java.util.List;
011import java.util.NoSuchElementException;
012
013
014/**
015 * Cartesian product with iterator.
016 * @author Heinz Kredel
017 */
018public class CartesianProduct<E> implements Iterable<List<E>> {
019
020
021    /**
022     * data structure.
023     */
024    public final List<Iterable<E>> comps;
025
026
027    /**
028     * CartesianProduct constructor.
029     * @param comps components of the Cartesian product.
030     */
031    public CartesianProduct(List<Iterable<E>> comps) {
032        if (comps == null) {
033            throw new IllegalArgumentException("null components not allowed");
034        }
035        this.comps = comps;
036    }
037
038
039    //     /**
040    //      * CartesianProduct constructor.
041    //      * @param comps components of the Cartesian product.
042    //      */
043    //     public CartesianProduct(List<List<E>> comps) {
044    //         this( listToIterable(comps)  );
045    //     }
046
047
048    /**
049     * Get an iterator over subsets.
050     * @return an iterator.
051     */
052    public Iterator<List<E>> iterator() {
053        return new CartesianProductIterator<E>(comps);
054    }
055
056
057    /**
058     * Transform list to iterables.
059     * @param comp components of the Cartesian product.
060     * @return iterables taken from lists.
061     */
062    static <E> List<Iterable<E>> listToIterable(List<List<E>> comp) {
063        List<Iterable<E>> iter = new ArrayList<Iterable<E>>(comp.size());
064        for (List<E> list : comp) {
065            iter.add(list);
066        }
067        return iter;
068    }
069
070
071}
072
073
074/**
075 * Cartesian product iterator.
076 * @author Heinz Kredel
077 */
078class CartesianProductIterator<E> implements Iterator<List<E>> {
079
080
081    /**
082     * data structure.
083     */
084    final List<Iterable<E>> comps;
085
086
087    final List<Iterator<E>> compit;
088
089
090    List<E> current;
091
092
093    boolean empty;
094
095
096    /**
097     * CartesianProduct iterator constructor.
098     * @param comps components of the Cartesian product.
099     */
100    public CartesianProductIterator(List<Iterable<E>> comps) {
101        if (comps == null) {
102            throw new IllegalArgumentException("null comps not allowed");
103        }
104        this.comps = comps;
105        current = new ArrayList<E>(comps.size());
106        compit = new ArrayList<Iterator<E>>(comps.size());
107        empty = false;
108        for (Iterable<E> ci : comps) {
109            Iterator<E> it = ci.iterator();
110            if (!it.hasNext()) {
111                empty = true;
112                current.clear();
113                break;
114            }
115            current.add(it.next());
116            compit.add(it);
117        }
118        //System.out.println("current = " + current);
119    }
120
121
122    /**
123     * Test for availability of a next tuple.
124     * @return true if the iteration has more tuples, else false.
125     */
126    public synchronized boolean hasNext() {
127        return !empty;
128    }
129
130
131    /**
132     * Get next tuple.
133     * @return next tuple.
134     */
135    public synchronized List<E> next() {
136        if (empty) {
137            throw new NoSuchElementException("invalid call of next()");
138        }
139        List<E> res = new ArrayList<E>(current);
140        // search iterator which hasNext
141        int i = compit.size() - 1;
142        for (; i >= 0; i--) {
143            Iterator<E> iter = compit.get(i);
144            if (iter.hasNext()) {
145                break;
146            }
147        }
148        if (i < 0) {
149            empty = true;
150            return res;
151        }
152        // update iterators
153        for (int j = i + 1; j < compit.size(); j++) {
154            Iterator<E> iter = comps.get(j).iterator();
155            compit.set(j, iter);
156        }
157        // update current
158        for (int j = i; j < compit.size(); j++) {
159            Iterator<E> iter = compit.get(j);
160            E el = iter.next();
161            current.set(j, el);
162        }
163        return res;
164    }
165
166
167    /**
168     * Remove a tuple if allowed.
169     */
170    public void remove() {
171        throw new UnsupportedOperationException("cannot remove tuples");
172    }
173
174}