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

1 /*
2  * Copyright (C) 2009 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.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 
20 import com.google.common.annotations.GwtCompatible;
21 import com.google.j2objc.annotations.WeakOuter;
22 import java.util.Collections;
23 import java.util.Comparator;
24 import java.util.LinkedHashSet;
25 import java.util.List;
26 import java.util.Set;
27 import org.checkerframework.checker.nullness.qual.Nullable;
28 
29 /**
30  * An implementation of {@link ImmutableTable} holding an arbitrary number of cells.
31  *
32  * @author Gregory Kick
33  */
34 @GwtCompatible
35 abstract class RegularImmutableTable<R, C, V> extends ImmutableTable<R, C, V> {
36   RegularImmutableTable() {}
37 
38   abstract Cell<R, C, V> getCell(int iterationIndex);
39 
40   @Override
41   final ImmutableSet<Cell<R, C, V>> createCellSet() {
42     return isEmpty() ? ImmutableSet.<Cell<R, C, V>>of() : new CellSet();
43   }
44 
45   @WeakOuter
46   private final class CellSet extends IndexedImmutableSet<Cell<R, C, V>> {
47     @Override
48     public int size() {
49       return RegularImmutableTable.this.size();
50     }
51 
52     @Override
53     Cell<R, C, V> get(int index) {
54       return getCell(index);
55     }
56 
57     @Override
58     public boolean contains(@Nullable Object object) {
59       if (object instanceof Cell) {
60         Cell<?, ?, ?> cell = (Cell<?, ?, ?>) object;
61         Object value = RegularImmutableTable.this.get(cell.getRowKey(), cell.getColumnKey());
62         return value != null && value.equals(cell.getValue());
63       }
64       return false;
65     }
66 
67     @Override
68     boolean isPartialView() {
69       return false;
70     }
71   }
72 
73   abstract V getValue(int iterationIndex);
74 
75   @Override
76   final ImmutableCollection<V> createValues() {
77     return isEmpty() ? ImmutableList.<V>of() : new Values();
78   }
79 
80   @WeakOuter
81   private final class Values extends ImmutableList<V> {
82     @Override
83     public int size() {
84       return RegularImmutableTable.this.size();
85     }
86 
87     @Override
88     public V get(int index) {
89       return getValue(index);
90     }
91 
92     @Override
93     boolean isPartialView() {
94       return true;
95     }
96   }
97 
98   static <R, C, V> RegularImmutableTable<R, C, V> forCells(
99       List<Cell<R, C, V>> cells,
100       final @Nullable Comparator<? super R> rowComparator,
101       final @Nullable Comparator<? super C> columnComparator) {
102     checkNotNull(cells);
103     if (rowComparator != null || columnComparator != null) {
104       /*
105        * This sorting logic leads to a cellSet() ordering that may not be expected and that isn't
106        * documented in the Javadoc. If a row Comparator is provided, cellSet() iterates across the
107        * columns in the first row, the columns in the second row, etc. If a column Comparator is
108        * provided but a row Comparator isn't, cellSet() iterates across the rows in the first
109        * column, the rows in the second column, etc.
110        */
111       Comparator<Cell<R, C, V>> comparator =
112           new Comparator<Cell<R, C, V>>() {
113             @Override
114             public int compare(Cell<R, C, V> cell1, Cell<R, C, V> cell2) {
115               int rowCompare =
116                   (rowComparator == null)
117                       ? 0
118                       : rowComparator.compare(cell1.getRowKey(), cell2.getRowKey());
119               if (rowCompare != 0) {
120                 return rowCompare;
121               }
122               return (columnComparator == null)
123                   ? 0
124                   : columnComparator.compare(cell1.getColumnKey(), cell2.getColumnKey());
125             }
126           };
127       Collections.sort(cells, comparator);
128     }
129     return forCellsInternal(cells, rowComparator, columnComparator);
130   }
131 
132   static <R, C, V> RegularImmutableTable<R, C, V> forCells(Iterable<Cell<R, C, V>> cells) {
133     return forCellsInternal(cells, null, null);
134   }
135 
136   private static <R, C, V> RegularImmutableTable<R, C, V> forCellsInternal(
137       Iterable<Cell<R, C, V>> cells,
138       @Nullable Comparator<? super R> rowComparator,
139       @Nullable Comparator<? super C> columnComparator) {
140     Set<R> rowSpaceBuilder = new LinkedHashSet<>();
141     Set<C> columnSpaceBuilder = new LinkedHashSet<>();
142     ImmutableList<Cell<R, C, V>> cellList = ImmutableList.copyOf(cells);
143     for (Cell<R, C, V> cell : cells) {
144       rowSpaceBuilder.add(cell.getRowKey());
145       columnSpaceBuilder.add(cell.getColumnKey());
146     }
147 
148     ImmutableSet<R> rowSpace =
149         (rowComparator == null)
150             ? ImmutableSet.copyOf(rowSpaceBuilder)
151             : ImmutableSet.copyOf(ImmutableList.sortedCopyOf(rowComparator, rowSpaceBuilder));
152     ImmutableSet<C> columnSpace =
153         (columnComparator == null)
154             ? ImmutableSet.copyOf(columnSpaceBuilder)
155             : ImmutableSet.copyOf(ImmutableList.sortedCopyOf(columnComparator, columnSpaceBuilder));
156 
157     return forOrderedComponents(cellList, rowSpace, columnSpace);
158   }
159 
160   /** A factory that chooses the most space-efficient representation of the table. */
161   static <R, C, V> RegularImmutableTable<R, C, V> forOrderedComponents(
162       ImmutableList<Cell<R, C, V>> cellList,
163       ImmutableSet<R> rowSpace,
164       ImmutableSet<C> columnSpace) {
165     // use a dense table if more than half of the cells have values
166     // TODO(gak): tune this condition based on empirical evidence
167     return (cellList.size() > (((long) rowSpace.size() * columnSpace.size()) / 2))
168         ? new DenseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace)
169         : new SparseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace);
170   }
171 
172   /** @throws IllegalArgumentException if {@code existingValue} is not null. */
173   /*
174    * We could have declared this method 'static' but the additional compile-time checks achieved by
175    * referencing the type variables seem worthwhile.
176    */
177   final void checkNoDuplicate(R rowKey, C columnKey, V existingValue, V newValue) {
178     checkArgument(
179         existingValue == null,
180         "Duplicate key: (row=%s, column=%s), values: [%s, %s].",
181         rowKey,
182         columnKey,
183         newValue,
184         existingValue);
185   }
186 }