001 /*
002 * $Id: CartesianProductLong.java 3308 2010-09-01 11:12:11Z 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 for Long with iterator.
016 * Similar to CartesianProduct but returns only tuples of given total degree.
017 * @author Heinz Kredel
018 */
019 public class CartesianProductLong implements Iterable<List<Long>> {
020
021
022 /**
023 * data structure.
024 */
025 public final List<LongIterable> comps;
026
027
028 public final long upperBound;
029
030
031 /**
032 * CartesianProduct constructor.
033 * @param comps components of the cartesian product.
034 * @param ub an upper bound for the total degree of the elements.
035 */
036 public CartesianProductLong(List<LongIterable> comps, long ub) {
037 if (comps == null) {
038 throw new IllegalArgumentException("null components not allowed");
039 }
040 this.comps = comps;
041 this.upperBound = ub;
042 }
043
044
045 /**
046 * Get an iterator over subsets.
047 * @return an iterator.
048 */
049 public Iterator<List<Long>> iterator() {
050 return new CartesianProductLongIterator(comps,upperBound);
051 }
052
053 }
054
055
056 /**
057 * Cartesian product iterator for Longs.
058 * Similar to CartesianProductIterator but returns only tuples of given total degree.
059 * @author Heinz Kredel
060 */
061 class CartesianProductLongIterator implements Iterator<List<Long>> {
062
063
064 /**
065 * data structure.
066 */
067 final List<LongIterable> comps;
068
069
070 final List<LongIterator> compit;
071
072
073 List<Long> current;
074
075
076 boolean empty;
077
078
079 public final long upperBound;
080
081
082 /**
083 * CartesianProduct iterator constructor.
084 * @param comps components of the cartesian product.
085 * @param un an upper bound for the total degree of the elements.
086 */
087 public CartesianProductLongIterator(List<LongIterable> comps, long ub) {
088 if (comps == null) {
089 throw new IllegalArgumentException("null comps not allowed");
090 }
091 this.comps = comps;
092 this.upperBound = ub;
093 current = new ArrayList<Long>(comps.size());
094 compit = new ArrayList<LongIterator>(comps.size());
095 empty = false;
096 for (LongIterable ci : comps) {
097 LongIterator it = (LongIterator) ci.iterator();
098 if ( it.getUpperBound() < this.upperBound ) {
099 throw new IllegalArgumentException("each iterator (" + it.getUpperBound()
100 + ") must be able to reach total upper bound " + upperBound);
101 }
102 if (!it.hasNext()) {
103 empty = true;
104 current.clear();
105 return;
106 }
107 current.add(it.next());
108 compit.add(it);
109 }
110 // start with last component equal to upper bound
111 LongIterator it = compit.get(compit.size()-1);
112 long d = -1L;
113 while ( it.hasNext() ) {
114 d = it.next();
115 if ( d >= upperBound ) {
116 break;
117 }
118 }
119 if ( d >= 0L ) {
120 current.set(current.size()-1,d);
121 }
122 if ( totalDegree(current) != upperBound ) {
123 empty = true;
124 current.clear();
125 }
126 //System.out.println("current = " + current);
127 }
128
129
130 /**
131 * Test for availability of a next tuple.
132 * @return true if the iteration has more tuples, else false.
133 */
134 public synchronized boolean hasNext() {
135 return !empty;
136 }
137
138
139 /**
140 * Get next tuple.
141 * @return next tuple.
142 */
143 public synchronized List<Long> next() {
144 if (empty) {
145 throw new NoSuchElementException("invalid call of next()");
146 }
147 List<Long> res = new ArrayList<Long>(current);
148 //int waist = 0;
149 while ( true ) {
150 // search iterator which hasNext
151 int i = compit.size() - 1;
152 for (; i >= 0; i--) {
153 LongIterator iter = compit.get(i);
154 if (iter.hasNext()) {
155 break;
156 }
157 }
158 if (i < 0) {
159 empty = true;
160 //System.out.println("inner waist = " + waist);
161 return res;
162 }
163 long pd = 0L;
164 for (int j = 0; j < i; j++) {
165 pd += current.get(j);
166 }
167 if ( pd >= upperBound ) {
168 if ( current.get(0) == upperBound ) {
169 empty = true;
170 //System.out.println("inner waist = " + waist);
171 return res;
172 }
173 pd = upperBound;
174 }
175 long rd = upperBound - pd;
176 // update iterators
177 for (int j = i + 1; j < compit.size(); j++) {
178 LongIterator iter = (LongIterator) comps.get(j).iterator();
179 iter.setUpperBound(rd);
180 compit.set(j, iter);
181 }
182 // update current
183 for (int j = i; j < compit.size(); j++) {
184 LongIterator iter = compit.get(j);
185 Long el = iter.next();
186 current.set(j, el);
187 }
188 long td = totalDegree(current);
189 if ( td == upperBound ) {
190 //System.out.println("inner waist = " + waist);
191 return res;
192 }
193 //System.out.println("current = " + current + ", td = " + td);
194 if ( td > upperBound ) {
195 //waist++;
196 continue;
197 }
198 // adjust last component to total degree
199 LongIterator it = compit.get(compit.size()-1);
200 long d = -1L;
201 while ( td < upperBound && it.hasNext() ) {
202 td++;
203 d = it.next();
204 }
205 //System.out.println("d = " + d);
206 if ( d >= 0L ) {
207 current.set(current.size()-1,d);
208 }
209 if ( td == upperBound ) {
210 //System.out.println("inner waist = " + waist);
211 return res;
212 }
213 //waist++;
214 // continue search
215 }
216 //return res;
217 }
218
219
220 /**
221 * Total degree of a tuple.
222 * @param e list of Longs.
223 * @return sum of all elements in e.
224 */
225 public long totalDegree(List<Long> e) {
226 long d = 0L;
227 for (Long i : e) {
228 d += i;
229 }
230 return d;
231 }
232
233
234 /**
235 * Remove a tuple if allowed.
236 */
237 public void remove() {
238 throw new UnsupportedOperationException("cannnot remove tuples");
239 }
240
241 }