/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed 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 com.google.common.collect;

import static com.google.common.base.Preconditions.checkElementIndex;

import com.google.common.annotations.GwtCompatible;
import com.google.common.math.IntMath;
import java.util.AbstractList;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;
import org.checkerframework.checker.nullness.qual.Nullable;

Author:Louis Wasserman
/** * Implementation of {@link Lists#cartesianProduct(List)}. * * @author Louis Wasserman */
@GwtCompatible final class CartesianList<E> extends AbstractList<List<E>> implements RandomAccess { private final transient ImmutableList<List<E>> axes; private final transient int[] axesSizeProduct; static <E> List<List<E>> create(List<? extends List<? extends E>> lists) { ImmutableList.Builder<List<E>> axesBuilder = new ImmutableList.Builder<>(lists.size()); for (List<? extends E> list : lists) { List<E> copy = ImmutableList.copyOf(list); if (copy.isEmpty()) { return ImmutableList.of(); } axesBuilder.add(copy); } return new CartesianList<E>(axesBuilder.build()); } CartesianList(ImmutableList<List<E>> axes) { this.axes = axes; int[] axesSizeProduct = new int[axes.size() + 1]; axesSizeProduct[axes.size()] = 1; try { for (int i = axes.size() - 1; i >= 0; i--) { axesSizeProduct[i] = IntMath.checkedMultiply(axesSizeProduct[i + 1], axes.get(i).size()); } } catch (ArithmeticException e) { throw new IllegalArgumentException( "Cartesian product too large; must have size at most Integer.MAX_VALUE"); } this.axesSizeProduct = axesSizeProduct; } private int getAxisIndexForProductIndex(int index, int axis) { return (index / axesSizeProduct[axis + 1]) % axes.get(axis).size(); } @Override public ImmutableList<E> get(final int index) { checkElementIndex(index, size()); return new ImmutableList<E>() { @Override public int size() { return axes.size(); } @Override public E get(int axis) { checkElementIndex(axis, size()); int axisIndex = getAxisIndexForProductIndex(index, axis); return axes.get(axis).get(axisIndex); } @Override boolean isPartialView() { return true; } }; } @Override public int size() { return axesSizeProduct[0]; } @Override public boolean contains(@Nullable Object o) { if (!(o instanceof List)) { return false; } List<?> list = (List<?>) o; if (list.size() != axes.size()) { return false; } ListIterator<?> itr = list.listIterator(); while (itr.hasNext()) { int index = itr.nextIndex(); if (!axes.get(index).contains(itr.next())) { return false; } } return true; } }