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