    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.iterators;
    018
    019import java.util.ArrayList;
    020import java.util.Iterator;
    021import java.util.List;
    022import java.util.NoSuchElementException;
    023import java.util.Objects;
    024
    025/**
    026 * This iterator creates a Cartesian product of the input iterables,
    027 * equivalent to nested for-loops.
    028 * <p>
    029 * The iterables provided to the constructor are used in reverse order, each
    030 * until exhaustion before proceeding to the next element of the prior iterable
    031 * and repeating. Consider the following example:
    032 * </p>
    033 * <pre>{@code
    034 * List<Character> iterable1 = Arrays.asList('A', 'B', 'C');
    035 * List<Character> iterable2 = Arrays.asList('1', '2', '3');
    036 * CartesianProductIterator<Character> it = new CartesianProductIterator<>(
    037 *         iterable1,
    038 *         iterable2);
    039 * while (it.hasNext()) {
    040 *     List<Character> tuple = it.next();
    041 *     System.out.println(tuple.get(0) + ", " + tuple.get(1));
    042 * }
    043 * }</pre>
    044 * <p>
    045 * The output will be:
    046 * </p>
    047 * <pre>
    048 * A, 1
    049 * A, 2
    050 * A, 3
    051 * B, 1
    052 * B, 2
    053 * B, 3
    054 * C, 1
    055 * C, 2
    056 * C, 3
    057 * </pre>
    058 * <p>
    059 * The {@code remove()} operation is not supported, and will throw an
    060 * {@code UnsupportedOperationException}.
    061 * </p>
    062 * <p>
    063 * If any of the input iterables is empty, the Cartesian product will be empty.
    064 * If any of the input iterables is infinite, the Cartesian product will be
    065 * infinite.
    066 * </p>
    067 *
    068 * @param <E> the type of the objects being permuted
    069 * @since 4.5.0-M3
    070 */
    071public class CartesianProductIterator<E> implements Iterator<List<E>> {
    072
    073    /**
    074     * The iterables to create the Cartesian product from.
    075     */
    076    private final List<Iterable<? extends E>> iterables;
    077
    078    /**
    079     * The iterators to generate the Cartesian product tuple from.
    080     */
    081    private final List<Iterator<? extends E>> iterators;
    082
    083    /**
    084     * The previous generated tuple of elements.
    085     */
    086    private List<E> previousTuple;
    087
    088    /**
    089     * Constructs a new {@code CartesianProductIterator} instance with given iterables.
    090     *
    091     * @param iterables the iterables to create the Cartesian product from
    092     * @throws NullPointerException if any of the iterables is null
    093     */
    094    @SafeVarargs
    095    public CartesianProductIterator(final Iterable<? extends E>... iterables) {
    096        Objects.requireNonNull(iterables, "iterables");
    097        this.iterables = new ArrayList<>(iterables.length);
    098        this.iterators = new ArrayList<>(iterables.length);
    099        for (final Iterable<? extends E> iterable : iterables) {
    100            Objects.requireNonNull(iterable, "iterable");
    101            this.iterables.add(iterable);
    102            final Iterator<? extends E> iterator = iterable.iterator();
    103            if (!iterator.hasNext()) {
    104                iterators.clear();
    105                break;
    106            }
    107            iterators.add(iterator);
    108        }
    109    }
    110
    111    /**
    112     * Returns {@code true} if the iteration has more elements.
    113     *
    114     * @return true if there are more tuples, otherwise false
    115     */
    116    @Override
    117    public boolean hasNext() {
    118        return iterators.stream().anyMatch(Iterator::hasNext);
    119    }
    120
    121    /**
    122     * Returns the next tuple of the input iterables.
    123     *
    124     * @return a list of the input iterables' elements
    125     * @throws NoSuchElementException if there are no more tuples
    126     */
    127    @Override
    128    public List<E> next() {
    129        if (!hasNext()) {
    130            throw new NoSuchElementException();
    131        }
    132        if (previousTuple == null) {
    133            previousTuple = new ArrayList<>(iterables.size());
    134            for (final Iterator<? extends E> iterator : iterators) {
    135                previousTuple.add(iterator.next());
    136            }
    137            return new ArrayList<>(previousTuple);
    138        }
    139        for (int i = iterators.size() - 1; i >= 0; i--) {
    140            Iterator<? extends E> iterator = iterators.get(i);
    141            if (iterator.hasNext()) {
    142                previousTuple.set(i, iterator.next());
    143                return new ArrayList<>(previousTuple);
    144            }
    145            iterator = iterables.get(i).iterator();
    146            iterators.set(i, iterator);
    147            previousTuple.set(i, iterator.next());
    148        }
    149        throw new IllegalStateException("reached unreachable code");
    150    }
    151
    152    @Override
    153    public void remove() {
    154        throw new UnsupportedOperationException("remove");
    155    }
    156}