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