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
19 import java.util.ArrayList;
20 import java.util.Iterator;
21 import java.util.List;
22 import java.util.NoSuchElementException;
23 import java.util.Objects;
24
25 /**
26 * This iterator creates a Cartesian product of the input iterables,
27 * equivalent to nested for-loops.
28 * <p>
29 * The iterables provided to the constructor are used in reverse order, each
30 * until exhaustion before proceeding to the next element of the prior iterable
31 * and repeating. Consider the following example:
32 * </p>
33 * <pre>{@code
34 * List<Character> iterable1 = Arrays.asList('A', 'B', 'C');
35 * List<Character> iterable2 = Arrays.asList('1', '2', '3');
36 * CartesianProductIterator<Character> it = new CartesianProductIterator<>(
37 * iterable1,
38 * iterable2);
39 * while (it.hasNext()) {
40 * List<Character> tuple = it.next();
41 * System.out.println(tuple.get(0) + ", " + tuple.get(1));
42 * }
43 * }</pre>
44 * <p>
45 * The output will be:
46 * </p>
47 * <pre>
48 * A, 1
49 * A, 2
50 * A, 3
51 * B, 1
52 * B, 2
53 * B, 3
54 * C, 1
55 * C, 2
56 * C, 3
57 * </pre>
58 * <p>
59 * The {@code remove()} operation is not supported, and will throw an
60 * {@code UnsupportedOperationException}.
61 * </p>
62 * <p>
63 * If any of the input iterables is empty, the Cartesian product will be empty.
64 * If any of the input iterables is infinite, the Cartesian product will be
65 * infinite.
66 * </p>
67 *
68 * @param <E> the type of the objects being permuted
69 * @since 4.5.0-M3
70 */
71 public class CartesianProductIterator<E> implements Iterator<List<E>> {
72
73 /**
74 * The iterables to create the Cartesian product from.
75 */
76 private final List<Iterable<? extends E>> iterables;
77
78 /**
79 * The iterators to generate the Cartesian product tuple from.
80 */
81 private final List<Iterator<? extends E>> iterators;
82
83 /**
84 * The previous generated tuple of elements.
85 */
86 private List<E> previousTuple;
87
88 /**
89 * Constructs a new {@code CartesianProductIterator} instance with given iterables.
90 *
91 * @param iterables the iterables to create the Cartesian product from
92 * @throws NullPointerException if any of the iterables is null
93 */
94 @SafeVarargs
95 public CartesianProductIterator(final Iterable<? extends E>... iterables) {
96 Objects.requireNonNull(iterables, "iterables");
97 this.iterables = new ArrayList<>(iterables.length);
98 this.iterators = new ArrayList<>(iterables.length);
99 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 }