001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package com.google.gwt.junit.client.impl;
017:
018: import com.google.gwt.junit.client.Range;
019:
020: import java.util.Iterator;
021: import java.util.List;
022: import java.util.ArrayList;
023: import java.util.Arrays;
024:
025: /**
026: * Iterates over all the possible permutations available in a list of
027: * {@link com.google.gwt.junit.client.Range}s.
028: *
029: * <p>
030: * The simplest way to iterate over the permutations of multiple iterators is in
031: * a nested for loop. The PermutationIterator turns that for loop inside out
032: * into a single iterator, which enables you to access each permutation in a
033: * piecemeal fashion.
034: * </p>
035: */
036: public class PermutationIterator implements
037: Iterator<PermutationIterator.Permutation> {
038:
039: /**
040: * A single permutation of all the iterators. Contains the current value of
041: * each iterator for the permutation.
042: */
043: public static class Permutation {
044: private List<Object> values;
045:
046: public Permutation(List<?> values) {
047: this .values = new ArrayList<Object>(values);
048: }
049:
050: public List<Object> getValues() {
051: return values;
052: }
053:
054: @Override
055: public String toString() {
056: return values.toString();
057: }
058: }
059:
060: /**
061: * A Range implemented using a list of data.
062: *
063: * @param <T> the type of data in the range.
064: */
065: private static class ListRange<T> implements Range<T> {
066: private List<T> list;
067:
068: public ListRange(List<T> list) {
069: this .list = list;
070: }
071:
072: public Iterator<T> iterator() {
073: return list.iterator();
074: }
075: }
076:
077: public static void main(String[] args) {
078: List<Range<String>> ranges = new ArrayList<Range<String>>(3);
079: ranges.add(new ListRange<String>(Arrays.asList("a", "b", "c")));
080: ranges.add(new ListRange<String>(Arrays.asList("1", "2", "3")));
081: ranges.add(new ListRange<String>(Arrays.asList("alpha", "beta",
082: "gamma", "delta")));
083:
084: System.out.println("Testing normal iteration.");
085: for (Iterator<Permutation> it = new PermutationIterator(ranges); it
086: .hasNext();) {
087: Permutation p = it.next();
088: System.out.println(p);
089: }
090:
091: System.out.println("\nTesting skipping iteration.");
092:
093: Iterator<String> skipIterator = Arrays.asList("alpha", "beta",
094: "gamma", "delta").iterator();
095: boolean skipped = true;
096: String skipValue = null;
097: for (PermutationIterator it = new PermutationIterator(ranges); it
098: .hasNext();) {
099: Permutation p = it.next();
100:
101: if (skipped) {
102: if (skipIterator.hasNext()) {
103: skipValue = skipIterator.next();
104: skipped = false;
105: }
106: }
107:
108: System.out.println(p);
109:
110: Object value = p.getValues().get(p.getValues().size() - 1);
111:
112: if (value.equals(skipValue)) {
113: it.skipCurrentRange();
114: skipped = true;
115: }
116: }
117: }
118:
119: /**
120: * Is this the first run?
121: */
122: private boolean firstRun = true;
123:
124: /**
125: * The iterator from every range.
126: */
127: private List<Iterator<?>> iterators;
128:
129: /**
130: * Are more permutations available?
131: */
132: private boolean maybeHaveMore = true;
133:
134: /**
135: * The ranges to permutate.
136: */
137: private List<? extends Range<?>> ranges;
138:
139: /**
140: * Did we just skip a range? If so, the values List already contains the
141: * values of the next permutation.
142: */
143: private boolean rangeSkipped = false;
144:
145: /**
146: * The current permutation of values.
147: */
148: private List<Object> values;
149:
150: /**
151: * Constructs a new PermutationIterator that provides the values for each
152: * possible permutation of <code>ranges</code>.
153: *
154: * @param ranges non-null. Each {@link com.google.gwt.junit.client.Range} must
155: * have at least one element. ranges.size() must be > 1
156: *
157: * TODO(tobyr) Consider if empty Ranges ever make sense in the context of
158: * permutations.
159: *
160: */
161: public PermutationIterator(List<? extends Range<?>> ranges) {
162: this .ranges = ranges;
163:
164: iterators = new ArrayList<Iterator<?>>();
165:
166: for (Range<?> r : ranges) {
167: iterators.add(r.iterator());
168: }
169:
170: values = new ArrayList<Object>();
171: }
172:
173: /**
174: * Returns a new <code>Permutation</code> containing the values of the next
175: * permutation.
176: *
177: * @return a non-null <code>Permutation</code>
178: */
179: public boolean hasNext() {
180:
181: if (!maybeHaveMore) {
182: return false;
183: }
184:
185: // Walk the iterators from bottom to top checking to see if any still have
186: // any available values
187:
188: for (int currentIterator = iterators.size() - 1; currentIterator >= 0; --currentIterator) {
189: Iterator<?> it = iterators.get(currentIterator);
190: if (it.hasNext()) {
191: return true;
192: }
193: }
194:
195: return false;
196: }
197:
198: public Permutation next() {
199: assert hasNext() : "No more available permutations in this iterator.";
200:
201: if (firstRun) {
202:
203: // Initialize all of our iterators and values on the first run
204: for (Iterator<?> it : iterators) {
205: values.add(it.next());
206: }
207: firstRun = false;
208: return new Permutation(values);
209: }
210:
211: if (rangeSkipped) {
212: rangeSkipped = false;
213: return new Permutation(values);
214: }
215:
216: // Walk through the iterators from bottom to top, finding the first one
217: // which has a value available. Increment it, reset all of the subsequent
218: // iterators, and then return the current permutation.
219: for (int currentIteratorIndex = iterators.size() - 1; currentIteratorIndex >= 0; --currentIteratorIndex) {
220: Iterator<?> it = iterators.get(currentIteratorIndex);
221: if (it.hasNext()) {
222: values.set(currentIteratorIndex, it.next());
223: for (int i = currentIteratorIndex + 1; i < iterators
224: .size(); ++i) {
225: Range<?> resetRange = ranges.get(i);
226: Iterator<?> resetIterator = resetRange.iterator();
227: iterators.set(i, resetIterator);
228: values.set(i, resetIterator.next());
229: }
230:
231: return new Permutation(values);
232: }
233: }
234:
235: throw new AssertionError(
236: "Assertion failed - Couldn't find a non-empty iterator.");
237: }
238:
239: public void remove() {
240: throw new UnsupportedOperationException();
241: }
242:
243: /**
244: * Skips the remaining set of values in the bottom
245: * {@link com.google.gwt.junit.client.Range}. This method affects the results
246: * of both hasNext() and next().
247: *
248: */
249: public void skipCurrentRange() {
250:
251: rangeSkipped = true;
252:
253: for (int currentIteratorIndex = iterators.size() - 2; currentIteratorIndex >= 0; --currentIteratorIndex) {
254: Iterator<?> it = iterators.get(currentIteratorIndex);
255: if (it.hasNext()) {
256: values.set(currentIteratorIndex, it.next());
257: for (int i = currentIteratorIndex + 1; i < iterators
258: .size(); ++i) {
259: Range<?> resetRange = ranges.get(i);
260: Iterator<?> resetIterator = resetRange.iterator();
261: iterators.set(i, resetIterator);
262: values.set(i, resetIterator.next());
263: }
264: return;
265: }
266: }
267:
268: maybeHaveMore = false;
269: }
270: }
|