Coverage Summary for Class: CartesianList (com.google.common.collect)

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 
15 package com.google.common.collect;
16 
17 import static com.google.common.base.Preconditions.checkElementIndex;
18 
19 import com.google.common.annotations.GwtCompatible;
20 import com.google.common.math.IntMath;
21 import java.util.AbstractList;
22 import java.util.List;
23 import java.util.ListIterator;
24 import java.util.RandomAccess;
25 import org.checkerframework.checker.nullness.qual.Nullable;
26 
27 /**
28  * Implementation of {@link Lists#cartesianProduct(List)}.
29  *
30  * @author Louis Wasserman
31  */
32 @GwtCompatible
33 final class CartesianList<E> extends AbstractList<List<E>> implements RandomAccess {
34 
35   private final transient ImmutableList<List<E>> axes;
36   private final transient int[] axesSizeProduct;
37 
38   static <E> List<List<E>> create(List<? extends List<? extends E>> lists) {
39     ImmutableList.Builder<List<E>> axesBuilder = new ImmutableList.Builder<>(lists.size());
40     for (List<? extends E> list : lists) {
41       List<E> copy = ImmutableList.copyOf(list);
42       if (copy.isEmpty()) {
43         return ImmutableList.of();
44       }
45       axesBuilder.add(copy);
46     }
47     return new CartesianList<E>(axesBuilder.build());
48   }
49 
50   CartesianList(ImmutableList<List<E>> axes) {
51     this.axes = axes;
52     int[] axesSizeProduct = new int[axes.size() + 1];
53     axesSizeProduct[axes.size()] = 1;
54     try {
55       for (int i = axes.size() - 1; i >= 0; i--) {
56         axesSizeProduct[i] = IntMath.checkedMultiply(axesSizeProduct[i + 1], axes.get(i).size());
57       }
58     } catch (ArithmeticException e) {
59       throw new IllegalArgumentException(
60           "Cartesian product too large; must have size at most Integer.MAX_VALUE");
61     }
62     this.axesSizeProduct = axesSizeProduct;
63   }
64 
65   private int getAxisIndexForProductIndex(int index, int axis) {
66     return (index / axesSizeProduct[axis + 1]) % axes.get(axis).size();
67   }
68 
69   @Override
70   public int indexOf(Object o) {
71     if (!(o instanceof List)) {
72       return -1;
73     }
74     List<?> list = (List<?>) o;
75     if (list.size() != axes.size()) {
76       return -1;
77     }
78     ListIterator<?> itr = list.listIterator();
79     int computedIndex = 0;
80     while (itr.hasNext()) {
81       int axisIndex = itr.nextIndex();
82       int elemIndex = axes.get(axisIndex).indexOf(itr.next());
83       if (elemIndex == -1) {
84         return -1;
85       }
86       computedIndex += elemIndex * axesSizeProduct[axisIndex + 1];
87     }
88     return computedIndex;
89   }
90 
91   @Override
92   public int lastIndexOf(Object o) {
93     if (!(o instanceof List)) {
94       return -1;
95     }
96     List<?> list = (List<?>) o;
97     if (list.size() != axes.size()) {
98       return -1;
99     }
100     ListIterator<?> itr = list.listIterator();
101     int computedIndex = 0;
102     while (itr.hasNext()) {
103       int axisIndex = itr.nextIndex();
104       int elemIndex = axes.get(axisIndex).lastIndexOf(itr.next());
105       if (elemIndex == -1) {
106         return -1;
107       }
108       computedIndex += elemIndex * axesSizeProduct[axisIndex + 1];
109     }
110     return computedIndex;
111   }
112 
113   @Override
114   public ImmutableList<E> get(final int index) {
115     checkElementIndex(index, size());
116     return new ImmutableList<E>() {
117 
118       @Override
119       public int size() {
120         return axes.size();
121       }
122 
123       @Override
124       public E get(int axis) {
125         checkElementIndex(axis, size());
126         int axisIndex = getAxisIndexForProductIndex(index, axis);
127         return axes.get(axis).get(axisIndex);
128       }
129 
130       @Override
131       boolean isPartialView() {
132         return true;
133       }
134     };
135   }
136 
137   @Override
138   public int size() {
139     return axesSizeProduct[0];
140   }
141 
142   @Override
143   public boolean contains(@Nullable Object object) {
144     if (!(object instanceof List)) {
145       return false;
146     }
147     List<?> list = (List<?>) object;
148     if (list.size() != axes.size()) {
149       return false;
150     }
151     int i = 0;
152     for (Object o : list) {
153       if (!axes.get(i).contains(o)) {
154         return false;
155       }
156       i++;
157     }
158     return true;
159   }
160 }