user/src/com/google/gwt/benchmarks/client/impl/PermutationIterator.java

/*
 * Copyright 2008 Google Inc.
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package com.google.gwt.benchmarks.client.impl;

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * Iterates over all the possible permutations available in a list of {@link
 * Iterable Iterables}.
 * 
 * <p>
 * The simplest way to iterate over the permutations of multiple iterators is in
 * a nested for loop. The PermutationIterator turns that for loop inside out
 * into a single iterator, which enables you to access each permutation in a
 * piecemeal fashion.
 * </p>
 */
public class PermutationIterator implements
    Iterator<PermutationIterator.Permutation> {

  /**
   * A single permutation of all the iterators. Contains the current value of
   * each iterator for the permutation.
   */
  public static class Permutation {

    private List<Object> values;

    public Permutation(List<?> values) {
      this.values = new ArrayList<Object>(values);
    }

    public List<Object> getValues() {
      return values;
    }

    @Override
    public String toString() {
      return values.toString();
    }
  }

  public static void main(String[] args) {
    List<Iterable<String>> iterables = new ArrayList<Iterable<String>>(3);
    iterables.add(Arrays.asList("a", "b", "c"));
    iterables.add(Arrays.asList("1", "2", "3"));
    iterables.add(Arrays.asList("alpha", "beta", "gamma", "delta"));

    System.out.println("Testing normal iteration.");
    for (Iterator<Permutation> it = new PermutationIterator(iterables); it.hasNext();) {
      Permutation p = it.next();
      System.out.println(p);
    }

    System.out.println("\nTesting skipping iteration.");

    Iterator<String> skipIterator = Arrays.asList("alpha", "beta", "gamma",
        "delta").iterator();
    boolean skipped = true;
    String skipValue = null;
    for (PermutationIterator it = new PermutationIterator(iterables); it.hasNext();) {
      Permutation p = it.next();

      if (skipped) {
        if (skipIterator.hasNext()) {
          skipValue = skipIterator.next();
          skipped = false;
        }
      }

      System.out.println(p);

      Object value = p.getValues().get(p.getValues().size() - 1);

      if (value.equals(skipValue)) {
        it.skipCurrentRange();
        skipped = true;
      }
    }
  }

  /**
   * Is this the first run?
   */
  private boolean firstRun = true;

  /**
   * The iterator from every range.
   */
  private List<Iterator<?>> iterators;

  /**
   * Are more permutations available?
   */
  private boolean maybeHaveMore = true;

  /**
   * The {@code Iterables} to permute.
   */
  private List<? extends Iterable<?>> iterables;

  /**
   * Did we just skip a range? If so, the values List already contains the
   * values of the next permutation.
   */
  private boolean rangeSkipped = false;

  /**
   * The current permutation of values.
   */
  private List<Object> values;

  /**
   * Constructs a new PermutationIterator that provides the values for each
   * possible permutation of <code>iterables</code>.
   * 
   * @param iterables non-null. Each {@link Iterable} must have at least one
   *          element. iterables.size() must be > 1
   * 
   * TODO(tobyr) Consider if empty Iterables ever make sense in the context of
   * permutations.
   */
  public PermutationIterator(List<? extends Iterable<?>> iterables) {
    this.iterables = iterables;

    iterators = new ArrayList<Iterator<?>>();

    for (Iterable<?> iterable : iterables) {
      iterators.add(iterable.iterator());
    }

    values = new ArrayList<Object>();
  }

  /**
   * Returns a new <code>Permutation</code> containing the values of the next
   * permutation.
   * 
   * @return a non-null <code>Permutation</code>
   */
  public boolean hasNext() {

    if (!maybeHaveMore) {
      return false;
    }

    // Walk the iterators from bottom to top checking to see if any still have
    // any available values

    for (int currentIterator = iterators.size() - 1; currentIterator >= 0; --currentIterator) {
      Iterator<?> it = iterators.get(currentIterator);
      if (it.hasNext()) {
        return true;
      }
    }

    return false;
  }

  public Permutation next() {
    assert hasNext() : "No more available permutations in this iterator.";

    if (firstRun) {

      // Initialize all of our iterators and values on the first run
      for (Iterator<?> it : iterators) {
        values.add(it.next());
      }
      firstRun = false;
      return new Permutation(values);
    }

    if (rangeSkipped) {
      rangeSkipped = false;
      return new Permutation(values);
    }

    // Walk through the iterators from bottom to top, finding the first one
    // which has a value available. Increment it, reset all of the subsequent
    // iterators, and then return the current permutation.
    for (int currentIteratorIndex = iterators.size() - 1; currentIteratorIndex >= 0; --currentIteratorIndex) {
      Iterator<?> it = iterators.get(currentIteratorIndex);
      if (it.hasNext()) {
        values.set(currentIteratorIndex, it.next());
        for (int i = currentIteratorIndex + 1; i < iterators.size(); ++i) {
          Iterable<?> resetIterable = iterables.get(i);
          Iterator<?> resetIterator = resetIterable.iterator();
          iterators.set(i, resetIterator);
          values.set(i, resetIterator.next());
        }

        return new Permutation(values);
      }
    }

    throw new AssertionError(
        "Assertion failed - Couldn't find a non-empty iterator.");
  }

  public void remove() {
    throw new UnsupportedOperationException();
  }

  /**
   * Skips the remaining set of values in the bottom {@code Iterable}. This
   * method affects the results of both hasNext() and next().
   */
  public void skipCurrentRange() {

    rangeSkipped = true;

    for (int currentIteratorIndex = iterators.size() - 2; currentIteratorIndex >= 0; --currentIteratorIndex) {
      Iterator<?> it = iterators.get(currentIteratorIndex);
      if (it.hasNext()) {
        values.set(currentIteratorIndex, it.next());
        for (int i = currentIteratorIndex + 1; i < iterators.size(); ++i) {
          Iterable<?> resetIterable = iterables.get(i);
          Iterator<?> resetIterator = resetIterable.iterator();
          iterators.set(i, resetIterator);
          values.set(i, resetIterator.next());
        }
        return;
      }
    }

    maybeHaveMore = false;
  }
}