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