CartesianProductIterator.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.collections4.iterators;

  18. import java.util.ArrayList;
  19. import java.util.Iterator;
  20. import java.util.List;
  21. import java.util.NoSuchElementException;
  22. import java.util.Objects;

  23. /**
  24.  * This iterator creates a Cartesian product of the input iterables,
  25.  * equivalent to nested for-loops.
  26.  * <p>
  27.  * The iterables provided to the constructor are used in reverse order, each
  28.  * until exhaustion before proceeding to the next element of the prior iterable
  29.  * and repeating. Consider the following example:
  30.  * </p>
  31.  * <pre>{@code
  32.  * List<Character> iterable1 = Arrays.asList('A', 'B', 'C');
  33.  * List<Character> iterable2 = Arrays.asList('1', '2', '3');
  34.  * CartesianProductIterator<Character> it = new CartesianProductIterator<>(
  35.  *         iterable1,
  36.  *         iterable2);
  37.  * while (it.hasNext()) {
  38.  *     List<Character> tuple = it.next();
  39.  *     System.out.println(tuple.get(0) + ", " + tuple.get(1));
  40.  * }
  41.  * }</pre>
  42.  * <p>
  43.  * The output will be:
  44.  * </p>
  45.  * <pre>
  46.  * A, 1
  47.  * A, 2
  48.  * A, 3
  49.  * B, 1
  50.  * B, 2
  51.  * B, 3
  52.  * C, 1
  53.  * C, 2
  54.  * C, 3
  55.  * </pre>
  56.  * <p>
  57.  * The {@code remove()} operation is not supported, and will throw an
  58.  * {@code UnsupportedOperationException}.
  59.  * </p>
  60.  * <p>
  61.  * If any of the input iterables is empty, the Cartesian product will be empty.
  62.  * If any of the input iterables is infinite, the Cartesian product will be
  63.  * infinite.
  64.  * </p>
  65.  *
  66.  * @param <E> the type of the objects being permuted
  67.  * @since 4.5.0-M3
  68.  */
  69. public class CartesianProductIterator<E> implements Iterator<List<E>> {

  70.     /**
  71.      * The iterables to create the Cartesian product from.
  72.      */
  73.     private final List<Iterable<? extends E>> iterables;

  74.     /**
  75.      * The iterators to generate the Cartesian product tuple from.
  76.      */
  77.     private final List<Iterator<? extends E>> iterators;

  78.     /**
  79.      * The previous generated tuple of elements.
  80.      */
  81.     private List<E> previousTuple;

  82.     /**
  83.      * Constructs a new {@code CartesianProductIterator} instance with given iterables.
  84.      *
  85.      * @param iterables the iterables to create the Cartesian product from
  86.      * @throws NullPointerException if any of the iterables is null
  87.      */
  88.     @SafeVarargs
  89.     public CartesianProductIterator(final Iterable<? extends E>... iterables) {
  90.         Objects.requireNonNull(iterables, "iterables");
  91.         this.iterables = new ArrayList<>(iterables.length);
  92.         this.iterators = new ArrayList<>(iterables.length);
  93.         for (final Iterable<? extends E> iterable : iterables) {
  94.             Objects.requireNonNull(iterable, "iterable");
  95.             this.iterables.add(iterable);
  96.             final Iterator<? extends E> iterator = iterable.iterator();
  97.             if (!iterator.hasNext()) {
  98.                 iterators.clear();
  99.                 break;
  100.             }
  101.             iterators.add(iterator);
  102.         }
  103.     }

  104.     /**
  105.      * Returns {@code true} if the iteration has more elements.
  106.      *
  107.      * @return true if there are more tuples, otherwise false
  108.      */
  109.     @Override
  110.     public boolean hasNext() {
  111.         return iterators.stream().anyMatch(Iterator::hasNext);
  112.     }

  113.     /**
  114.      * Returns the next tuple of the input iterables.
  115.      *
  116.      * @return a list of the input iterables' elements
  117.      * @throws NoSuchElementException if there are no more tuples
  118.      */
  119.     @Override
  120.     public List<E> next() {
  121.         if (!hasNext()) {
  122.             throw new NoSuchElementException();
  123.         }
  124.         if (previousTuple == null) {
  125.             previousTuple = new ArrayList<>(iterables.size());
  126.             for (final Iterator<? extends E> iterator : iterators) {
  127.                 previousTuple.add(iterator.next());
  128.             }
  129.             return new ArrayList<>(previousTuple);
  130.         }
  131.         for (int i = iterators.size() - 1; i >= 0; i--) {
  132.             Iterator<? extends E> iterator = iterators.get(i);
  133.             if (iterator.hasNext()) {
  134.                 previousTuple.set(i, iterator.next());
  135.                 return new ArrayList<>(previousTuple);
  136.             }
  137.             iterator = iterables.get(i).iterator();
  138.             iterators.set(i, iterator);
  139.             previousTuple.set(i, iterator.next());
  140.         }
  141.         throw new IllegalStateException("reached unreachable code");
  142.     }

  143.     @Override
  144.     public void remove() {
  145.         throw new UnsupportedOperationException("remove");
  146.     }
  147. }