Coverage Summary for Class: DenseImmutableTable (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 com.google.common.annotations.GwtCompatible;
18 import com.google.common.collect.ImmutableMap.IteratorBasedImmutableMap;
19 import com.google.errorprone.annotations.Immutable;
20 import com.google.j2objc.annotations.WeakOuter;
21 import java.util.Map;
22 import org.checkerframework.checker.nullness.qual.Nullable;
23 
24 /** A {@code RegularImmutableTable} optimized for dense data. */
25 @GwtCompatible
26 @Immutable(containerOf = {"R", "C", "V"})
27 final class DenseImmutableTable<R, C, V> extends RegularImmutableTable<R, C, V> {
28   private final ImmutableMap<R, Integer> rowKeyToIndex;
29   private final ImmutableMap<C, Integer> columnKeyToIndex;
30   private final ImmutableMap<R, ImmutableMap<C, V>> rowMap;
31   private final ImmutableMap<C, ImmutableMap<R, V>> columnMap;
32 
33   @SuppressWarnings("Immutable") // We don't modify this after construction.
34   private final int[] rowCounts;
35 
36   @SuppressWarnings("Immutable") // We don't modify this after construction.
37   private final int[] columnCounts;
38 
39   @SuppressWarnings("Immutable") // We don't modify this after construction.
40   private final V[][] values;
41 
42   // For each cell in iteration order, the index of that cell's row key in the row key list.
43   @SuppressWarnings("Immutable") // We don't modify this after construction.
44   private final int[] cellRowIndices;
45 
46   // For each cell in iteration order, the index of that cell's column key in the column key list.
47   @SuppressWarnings("Immutable") // We don't modify this after construction.
48   private final int[] cellColumnIndices;
49 
50   DenseImmutableTable(
51       ImmutableList<Cell<R, C, V>> cellList,
52       ImmutableSet<R> rowSpace,
53       ImmutableSet<C> columnSpace) {
54     @SuppressWarnings("unchecked")
55     V[][] array = (V[][]) new Object[rowSpace.size()][columnSpace.size()];
56     this.values = array;
57     this.rowKeyToIndex = Maps.indexMap(rowSpace);
58     this.columnKeyToIndex = Maps.indexMap(columnSpace);
59     rowCounts = new int[rowKeyToIndex.size()];
60     columnCounts = new int[columnKeyToIndex.size()];
61     int[] cellRowIndices = new int[cellList.size()];
62     int[] cellColumnIndices = new int[cellList.size()];
63     for (int i = 0; i < cellList.size(); i++) {
64       Cell<R, C, V> cell = cellList.get(i);
65       R rowKey = cell.getRowKey();
66       C columnKey = cell.getColumnKey();
67       int rowIndex = rowKeyToIndex.get(rowKey);
68       int columnIndex = columnKeyToIndex.get(columnKey);
69       V existingValue = values[rowIndex][columnIndex];
70       checkNoDuplicate(rowKey, columnKey, existingValue, cell.getValue());
71       values[rowIndex][columnIndex] = cell.getValue();
72       rowCounts[rowIndex]++;
73       columnCounts[columnIndex]++;
74       cellRowIndices[i] = rowIndex;
75       cellColumnIndices[i] = columnIndex;
76     }
77     this.cellRowIndices = cellRowIndices;
78     this.cellColumnIndices = cellColumnIndices;
79     this.rowMap = new RowMap();
80     this.columnMap = new ColumnMap();
81   }
82 
83   /** An immutable map implementation backed by an indexed nullable array. */
84   private abstract static class ImmutableArrayMap<K, V> extends IteratorBasedImmutableMap<K, V> {
85     private final int size;
86 
87     ImmutableArrayMap(int size) {
88       this.size = size;
89     }
90 
91     abstract ImmutableMap<K, Integer> keyToIndex();
92 
93     // True if getValue never returns null.
94     private boolean isFull() {
95       return size == keyToIndex().size();
96     }
97 
98     K getKey(int index) {
99       return keyToIndex().keySet().asList().get(index);
100     }
101 
102     abstract @Nullable V getValue(int keyIndex);
103 
104     @Override
105     ImmutableSet<K> createKeySet() {
106       return isFull() ? keyToIndex().keySet() : super.createKeySet();
107     }
108 
109     @Override
110     public int size() {
111       return size;
112     }
113 
114     @Override
115     public V get(@Nullable Object key) {
116       Integer keyIndex = keyToIndex().get(key);
117       return (keyIndex == null) ? null : getValue(keyIndex);
118     }
119 
120     @Override
121     UnmodifiableIterator<Entry<K, V>> entryIterator() {
122       return new AbstractIterator<Entry<K, V>>() {
123         private int index = -1;
124         private final int maxIndex = keyToIndex().size();
125 
126         @Override
127         protected Entry<K, V> computeNext() {
128           for (index++; index < maxIndex; index++) {
129             V value = getValue(index);
130             if (value != null) {
131               return Maps.immutableEntry(getKey(index), value);
132             }
133           }
134           return endOfData();
135         }
136       };
137     }
138   }
139 
140   private final class Row extends ImmutableArrayMap<C, V> {
141     private final int rowIndex;
142 
143     Row(int rowIndex) {
144       super(rowCounts[rowIndex]);
145       this.rowIndex = rowIndex;
146     }
147 
148     @Override
149     ImmutableMap<C, Integer> keyToIndex() {
150       return columnKeyToIndex;
151     }
152 
153     @Override
154     V getValue(int keyIndex) {
155       return values[rowIndex][keyIndex];
156     }
157 
158     @Override
159     boolean isPartialView() {
160       return true;
161     }
162   }
163 
164   private final class Column extends ImmutableArrayMap<R, V> {
165     private final int columnIndex;
166 
167     Column(int columnIndex) {
168       super(columnCounts[columnIndex]);
169       this.columnIndex = columnIndex;
170     }
171 
172     @Override
173     ImmutableMap<R, Integer> keyToIndex() {
174       return rowKeyToIndex;
175     }
176 
177     @Override
178     V getValue(int keyIndex) {
179       return values[keyIndex][columnIndex];
180     }
181 
182     @Override
183     boolean isPartialView() {
184       return true;
185     }
186   }
187 
188   @WeakOuter
189   private final class RowMap extends ImmutableArrayMap<R, ImmutableMap<C, V>> {
190     private RowMap() {
191       super(rowCounts.length);
192     }
193 
194     @Override
195     ImmutableMap<R, Integer> keyToIndex() {
196       return rowKeyToIndex;
197     }
198 
199     @Override
200     ImmutableMap<C, V> getValue(int keyIndex) {
201       return new Row(keyIndex);
202     }
203 
204     @Override
205     boolean isPartialView() {
206       return false;
207     }
208   }
209 
210   @WeakOuter
211   private final class ColumnMap extends ImmutableArrayMap<C, ImmutableMap<R, V>> {
212     private ColumnMap() {
213       super(columnCounts.length);
214     }
215 
216     @Override
217     ImmutableMap<C, Integer> keyToIndex() {
218       return columnKeyToIndex;
219     }
220 
221     @Override
222     ImmutableMap<R, V> getValue(int keyIndex) {
223       return new Column(keyIndex);
224     }
225 
226     @Override
227     boolean isPartialView() {
228       return false;
229     }
230   }
231 
232   @Override
233   public ImmutableMap<C, Map<R, V>> columnMap() {
234     // Casts without copying.
235     ImmutableMap<C, ImmutableMap<R, V>> columnMap = this.columnMap;
236     return ImmutableMap.<C, Map<R, V>>copyOf(columnMap);
237   }
238 
239   @Override
240   public ImmutableMap<R, Map<C, V>> rowMap() {
241     // Casts without copying.
242     ImmutableMap<R, ImmutableMap<C, V>> rowMap = this.rowMap;
243     return ImmutableMap.<R, Map<C, V>>copyOf(rowMap);
244   }
245 
246   @Override
247   public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
248     Integer rowIndex = rowKeyToIndex.get(rowKey);
249     Integer columnIndex = columnKeyToIndex.get(columnKey);
250     return ((rowIndex == null) || (columnIndex == null)) ? null : values[rowIndex][columnIndex];
251   }
252 
253   @Override
254   public int size() {
255     return cellRowIndices.length;
256   }
257 
258   @Override
259   Cell<R, C, V> getCell(int index) {
260     int rowIndex = cellRowIndices[index];
261     int columnIndex = cellColumnIndices[index];
262     R rowKey = rowKeySet().asList().get(rowIndex);
263     C columnKey = columnKeySet().asList().get(columnIndex);
264     V value = values[rowIndex][columnIndex];
265     return cellOf(rowKey, columnKey, value);
266   }
267 
268   @Override
269   V getValue(int index) {
270     return values[cellRowIndices[index]][cellColumnIndices[index]];
271   }
272 
273   @Override
274   SerializedForm createSerializedForm() {
275     return SerializedForm.create(this, cellRowIndices, cellColumnIndices);
276   }
277 }