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 22 import java.util.AbstractList; 23 import java.util.List; 24 import java.util.ListIterator; 25 import java.util.RandomAccess; 26 27 import javax.annotation.Nullable; 28 29 /** 30 * Implementation of {@link Lists#cartesianProduct(List)}. 31 * 32 * @author Louis Wasserman 33 */ 34 @GwtCompatible 35 final 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
