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}