001 /*
002 * $Id: CartesianProduct.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.NoSuchElementException;
012
013
014 /**
015 * Cartesian product with iterator.
016 * @author Heinz Kredel
017 */
018 public 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 fom 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 */
078 class 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("cannnot remove tuples");
172 }
173
174 }