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}