CartesianProductIterator.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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 org.apache.commons.collections4.iterators;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * This iterator creates a Cartesian product of the input iterables,
 * equivalent to nested for-loops.
 * <p>
 * The iterables provided to the constructor are used in reverse order, each
 * until exhaustion before proceeding to the next element of the prior iterable
 * and repeating. Consider the following example:
 * </p>
 * <pre>{@code
 * List<Character> iterable1 = Arrays.asList('A', 'B', 'C');
 * List<Character> iterable2 = Arrays.asList('1', '2', '3');
 * CartesianProductIterator<Character> it = new CartesianProductIterator<>(
 *         iterable1,
 *         iterable2);
 * while (it.hasNext()) {
 *     List<Character> tuple = it.next();
 *     System.out.println(tuple.get(0) + ", " + tuple.get(1));
 * }
 * }</pre>
 * <p>
 * The output will be:
 * </p>
 * <pre>
 * A, 1
 * A, 2
 * A, 3
 * B, 1
 * B, 2
 * B, 3
 * C, 1
 * C, 2
 * C, 3
 * </pre>
 * <p>
 * The {@code remove()} operation is not supported, and will throw an
 * {@code UnsupportedOperationException}.
 * </p>
 * <p>
 * If any of the input iterables is empty, the Cartesian product will be empty.
 * If any of the input iterables is infinite, the Cartesian product will be
 * infinite.
 * </p>
 *
 * @param <E> the type of the objects being permuted
 * @since 4.5.0-M3
 */
public class CartesianProductIterator<E> implements Iterator<List<E>> {

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

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

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

    /**
     * Constructs a new {@code CartesianProductIterator} instance with given iterables.
     *
     * @param iterables the iterables to create the Cartesian product from
     * @throws NullPointerException if any of the iterables is null
     */
    @SafeVarargs
    public CartesianProductIterator(final Iterable<? extends E>... iterables) {
        Objects.requireNonNull(iterables, "iterables");
        this.iterables = new ArrayList<>(iterables.length);
        this.iterators = new ArrayList<>(iterables.length);
        for (final Iterable<? extends E> iterable : iterables) {
            Objects.requireNonNull(iterable, "iterable");
            this.iterables.add(iterable);
            final Iterator<? extends E> iterator = iterable.iterator();
            if (!iterator.hasNext()) {
                iterators.clear();
                break;
            }
            iterators.add(iterator);
        }
    }

    /**
     * Returns {@code true} if the iteration has more elements.
     *
     * @return true if there are more tuples, otherwise false
     */
    @Override
    public boolean hasNext() {
        return iterators.stream().anyMatch(Iterator::hasNext);
    }

    /**
     * Returns the next tuple of the input iterables.
     *
     * @return a list of the input iterables' elements
     * @throws NoSuchElementException if there are no more tuples
     */
    @Override
    public List<E> next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        if (previousTuple == null) {
            previousTuple = new ArrayList<>(iterables.size());
            for (final Iterator<? extends E> iterator : iterators) {
                previousTuple.add(iterator.next());
            }
            return new ArrayList<>(previousTuple);
        }
        for (int i = iterators.size() - 1; i >= 0; i--) {
            Iterator<? extends E> iterator = iterators.get(i);
            if (iterator.hasNext()) {
                previousTuple.set(i, iterator.next());
                return new ArrayList<>(previousTuple);
            }
            iterator = iterables.get(i).iterator();
            iterators.set(i, iterator);
            previousTuple.set(i, iterator.next());
        }
        throw new IllegalStateException("reached unreachable code");
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("remove");
    }
}