KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > google > gwt > junit > client > impl > PermutationIterator


1 /*
2  * Copyright 2007 Google Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5  * use this file except in compliance with the License. You may obtain a copy of
6  * the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13  * License for the specific language governing permissions and limitations under
14  * the License.
15  */

16 package com.google.gwt.junit.client.impl;
17
18 import com.google.gwt.junit.client.Range;
19
20 import java.util.Iterator JavaDoc;
21 import java.util.List JavaDoc;
22 import java.util.ArrayList JavaDoc;
23 import java.util.Arrays JavaDoc;
24
25 /**
26  * Iterates over all the possible permutations available in a list of
27  * {@link com.google.gwt.junit.client.Range}s.
28  *
29  * <p>The simplest way to iterate over the permutations of multiple iterators
30  * is in a nested for loop. The PermutationIterator turns that for loop inside
31  * out into a single iterator, which enables you to access each permutation
32  * in a piecemeal fashion.</p>
33  *
34  */

35 public class PermutationIterator implements Iterator JavaDoc {
36
37   /**
38    * A single permutation of all the iterators. Contains the current value
39    * of each iterator for the permutation.
40    *
41    */

42   public static class Permutation {
43     private List JavaDoc values;
44     public Permutation( List JavaDoc values ) {
45       this.values = new ArrayList JavaDoc( values );
46     }
47     public List JavaDoc getValues() {
48       return values;
49     }
50     public String JavaDoc toString() {
51       return values.toString();
52     }
53   }
54
55   private static class ListRange implements Range {
56     private List JavaDoc list;
57     public ListRange( List JavaDoc list ) {
58       this.list = list;
59     }
60     public Iterator JavaDoc iterator() {
61       return list.iterator();
62     }
63   }
64   public static void main( String JavaDoc[] args ) {
65     List JavaDoc ranges = Arrays.asList(
66       new Range[] {
67         new ListRange( Arrays.asList( new String JavaDoc[] {"a", "b", "c" } ) ),
68         new ListRange( Arrays.asList( new String JavaDoc[] {"1", "2", "3" } ) ),
69         new ListRange( Arrays.asList( new String JavaDoc[] {"alpha", "beta", "gamma", "delta" } ) ),
70       }
71     );
72
73     System.out.println("Testing normal iteration.");
74     for ( Iterator JavaDoc 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 JavaDoc skipIterator = Arrays.asList( new String JavaDoc[] {"alpha", "beta", "gamma", "delta" } ).iterator();
82     boolean skipped = true;
83     String JavaDoc 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 JavaDoc) skipIterator.next();
90           skipped = false;
91         }
92       }
93
94       System.out.println(p);
95
96       String JavaDoc value = (String JavaDoc) 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 JavaDoc iterators;
106   private boolean maybeHaveMore = true;
107   private List JavaDoc ranges;
108
109   private boolean rangeSkipped = false;
110
111   private List JavaDoc values;
112
113   /**
114    * Constructs a new PermutationIterator that provides the values for each
115    * possible permutation of <code>ranges</code>.
116    *
117    * @param ranges non-null. Each {@link com.google.gwt.junit.client.Range}
118    * must have at least one element. ranges.size() must be > 1
119    *
120    * TODO(tobyr) Consider if empty Ranges ever make sense in the context of
121    * permutations.
122    *
123    */

124   public PermutationIterator( List JavaDoc ranges ) {
125     this.ranges = ranges;
126
127     iterators = new ArrayList JavaDoc();
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 JavaDoc();
135   }
136
137   /**
138    * Returns a new <code>Permutation</code> containing the values of the next
139    * permutation.
140    *
141    * @return a non-null <code>Permutation</code>
142    */

143   public boolean hasNext() {
144
145     if ( ! maybeHaveMore ) {
146       return false;
147     }
148
149     // Walk the iterators from bottom to top checking to see if any still have
150
// any available values
151

152     for ( int currentIterator = iterators.size() - 1; currentIterator >= 0; --currentIterator ) {
153       Iterator JavaDoc it = (Iterator JavaDoc) iterators.get( currentIterator );
154       if ( it.hasNext() ) {
155         return true;
156       }
157     }
158
159     return false;
160   }
161
162   public Object JavaDoc next() {
163     assert hasNext() : "No more available permutations in this iterator.";
164
165     if ( firstRun ) {
166
167       // Initialize all of our iterators and values on the first run
168
for ( int i = 0; i < iterators.size(); ++i ) {
169         Iterator JavaDoc it = ( Iterator JavaDoc ) 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     // Walk through the iterators from bottom to top, finding the first one
182
// which has a value available. Increment it, reset all of the subsequent
183
// iterators, and then return the current permutation.
184
for ( int currentIteratorIndex = iterators.size() - 1; currentIteratorIndex >= 0; --currentIteratorIndex ) {
185       Iterator JavaDoc it = (Iterator JavaDoc) 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 JavaDoc 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 JavaDoc( "Assertion failed - Couldn't find a non-empty iterator." );
200   }
201
202   public void remove() {
203     throw new UnsupportedOperationException JavaDoc();
204   }
205
206   /**
207    * Skips the remaining set of values in the bottom
208    * {@link com.google.gwt.junit.client.Range}. This method affects the results
209    * of both hasNext() and next().
210    *
211    */

212   public void skipCurrentRange() {
213
214     rangeSkipped = true;
215
216     for ( int currentIteratorIndex = iterators.size() - 2; currentIteratorIndex >= 0; --currentIteratorIndex ) {
217       Iterator JavaDoc it = (Iterator JavaDoc) 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 JavaDoc 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