1/*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkElementIndex;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.math.IntMath;
21
22import java.util.AbstractList;
23import java.util.List;
24import java.util.ListIterator;
25import java.util.RandomAccess;
26
27import javax.annotation.Nullable;
28
29/**
30 * Implementation of {@link Lists#cartesianProduct(List)}.
31 *
32 * @author Louis Wasserman
33 */
34@GwtCompatible
35final class CartesianList<E> extends AbstractList<List<E>> implements RandomAccess {
36
37  private transient final ImmutableList<List<E>> axes;
38  private transient final int[] axesSizeProduct;
39
40  static <E> List<List<E>> create(List<? extends List<? extends E>> lists) {
41    ImmutableList.Builder<List<E>> axesBuilder =
42        new ImmutableList.Builder<List<E>>(lists.size());
43    for (List<? extends E> list : lists) {
44      List<E> copy = ImmutableList.copyOf(list);
45      if (copy.isEmpty()) {
46        return ImmutableList.of();
47      }
48      axesBuilder.add(copy);
49    }
50    return new CartesianList<E>(axesBuilder.build());
51  }
52
53  CartesianList(ImmutableList<List<E>> axes) {
54    this.axes = axes;
55    int[] axesSizeProduct = new int[axes.size() + 1];
56    axesSizeProduct[axes.size()] = 1;
57    try {
58      for (int i = axes.size() - 1; i >= 0; i--) {
59        axesSizeProduct[i] =
60            IntMath.checkedMultiply(axesSizeProduct[i + 1], axes.get(i).size());
61      }
62    } catch (ArithmeticException e) {
63      throw new IllegalArgumentException(
64          "Cartesian product too large; must have size at most Integer.MAX_VALUE");
65    }
66    this.axesSizeProduct = axesSizeProduct;
67  }
68
69  private int getAxisIndexForProductIndex(int index, int axis) {
70    return (index / axesSizeProduct[axis + 1]) % axes.get(axis).size();
71  }
72
73  @Override
74  public ImmutableList<E> get(final int index) {
75    checkElementIndex(index, size());
76    return new ImmutableList<E>() {
77
78      @Override
79      public int size() {
80        return axes.size();
81      }
82
83      @Override
84      public E get(int axis) {
85        checkElementIndex(axis, size());
86        int axisIndex = getAxisIndexForProductIndex(index, axis);
87        return axes.get(axis).get(axisIndex);
88      }
89
90      @Override
91      boolean isPartialView() {
92        return true;
93      }
94    };
95  }
96
97  @Override
98  public int size() {
99    return axesSizeProduct[0];
100  }
101
102  @Override
103  public boolean contains(@Nullable Object o) {
104    if (!(o instanceof List)) {
105      return false;
106    }
107    List<?> list = (List<?>) o;
108    if (list.size() != axes.size()) {
109      return false;
110    }
111    ListIterator<?> itr = list.listIterator();
112    while (itr.hasNext()) {
113      int index = itr.nextIndex();
114      if (!axes.get(index).contains(itr.next())) {
115        return false;
116      }
117    }
118    return true;
119  }
120}
121