1 16 package com.google.gwt.junit.client.impl; 17 18 import com.google.gwt.junit.client.Range; 19 20 import java.util.Iterator ; 21 import java.util.List ; 22 import java.util.ArrayList ; 23 import java.util.Arrays ; 24 25 35 public class PermutationIterator implements Iterator { 36 37 42 public static class Permutation { 43 private List values; 44 public Permutation( List values ) { 45 this.values = new ArrayList ( values ); 46 } 47 public List getValues() { 48 return values; 49 } 50 public String toString() { 51 return values.toString(); 52 } 53 } 54 55 private static class ListRange implements Range { 56 private List list; 57 public ListRange( List list ) { 58 this.list = list; 59 } 60 public Iterator iterator() { 61 return list.iterator(); 62 } 63 } 64 public static void main( String [] args ) { 65 List ranges = Arrays.asList( 66 new Range[] { 67 new ListRange( Arrays.asList( new String [] {"a", "b", "c" } ) ), 68 new ListRange( Arrays.asList( new String [] {"1", "2", "3" } ) ), 69 new ListRange( Arrays.asList( new String [] {"alpha", "beta", "gamma", "delta" } ) ), 70 } 71 ); 72 73 System.out.println("Testing normal iteration."); 74 for ( Iterator it = new PermutationIterator(ranges); it.hasNext(); ) { 75 Permutation p = (Permutation) it.next(); 76 System.out.println(p); 77 } 78 79 System.out.println("\nTesting skipping iteration."); 80 81 Iterator skipIterator = Arrays.asList( new String [] {"alpha", "beta", "gamma", "delta" } ).iterator(); 82 boolean skipped = true; 83 String skipValue = null; 84 for ( PermutationIterator it = new PermutationIterator(ranges); it.hasNext(); ) { 85 Permutation p = (Permutation) it.next(); 86 87 if ( skipped ) { 88 if ( skipIterator.hasNext() ) { 89 skipValue = (String ) skipIterator.next(); 90 skipped = false; 91 } 92 } 93 94 System.out.println(p); 95 96 String value = (String ) p.getValues().get(p.getValues().size() - 1); 97 98 if ( value.equals(skipValue) ) { 99 it.skipCurrentRange(); 100 skipped = true; 101 } 102 } 103 } 104 private boolean firstRun = true; 105 private List iterators; 106 private boolean maybeHaveMore = true; 107 private List ranges; 108 109 private boolean rangeSkipped = false; 110 111 private List values; 112 113 124 public PermutationIterator( List ranges ) { 125 this.ranges = ranges; 126 127 iterators = new ArrayList (); 128 129 for ( int i = 0; i < ranges.size(); ++i ) { 130 Range r = ( Range ) ranges.get( i ); 131 iterators.add( r.iterator() ); 132 } 133 134 values = new ArrayList (); 135 } 136 137 143 public boolean hasNext() { 144 145 if ( ! maybeHaveMore ) { 146 return false; 147 } 148 149 152 for ( int currentIterator = iterators.size() - 1; currentIterator >= 0; --currentIterator ) { 153 Iterator it = (Iterator ) iterators.get( currentIterator ); 154 if ( it.hasNext() ) { 155 return true; 156 } 157 } 158 159 return false; 160 } 161 162 public Object next() { 163 assert hasNext() : "No more available permutations in this iterator."; 164 165 if ( firstRun ) { 166 167 for ( int i = 0; i < iterators.size(); ++i ) { 169 Iterator it = ( Iterator ) iterators.get( i ); 170 values.add( it.next() ); 171 } 172 firstRun = false; 173 return new Permutation( values ); 174 } 175 176 if ( rangeSkipped ) { 177 rangeSkipped = false; 178 return new Permutation( values ); 179 } 180 181 for ( int currentIteratorIndex = iterators.size() - 1; currentIteratorIndex >= 0; --currentIteratorIndex ) { 185 Iterator it = (Iterator ) iterators.get( currentIteratorIndex ); 186 if ( it.hasNext() ) { 187 values.set( currentIteratorIndex, it.next() ); 188 for ( int i = currentIteratorIndex + 1; i < iterators.size(); ++i ) { 189 Range resetRange = (Range) ranges.get( i ); 190 Iterator resetIterator = resetRange.iterator(); 191 iterators.set(i, resetIterator); 192 values.set( i, resetIterator.next() ); 193 } 194 195 return new Permutation( values ); 196 } 197 } 198 199 throw new AssertionError ( "Assertion failed - Couldn't find a non-empty iterator." ); 200 } 201 202 public void remove() { 203 throw new UnsupportedOperationException (); 204 } 205 206 212 public void skipCurrentRange() { 213 214 rangeSkipped = true; 215 216 for ( int currentIteratorIndex = iterators.size() - 2; currentIteratorIndex >= 0; --currentIteratorIndex ) { 217 Iterator it = (Iterator ) iterators.get( currentIteratorIndex ); 218 if ( it.hasNext() ) { 219 values.set( currentIteratorIndex, it.next() ); 220 for ( int i = currentIteratorIndex + 1; i < iterators.size(); ++i ) { 221 Range resetRange = (Range) ranges.get( i ); 222 Iterator resetIterator = resetRange.iterator(); 223 iterators.set( i, resetIterator ); 224 values.set( i, resetIterator.next() ); 225 } 226 return; 227 } 228 } 229 230 maybeHaveMore = false; 231 } 232 } | Popular Tags |