Coverage Summary for Class: SparseImmutableTable (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.errorprone.annotations.Immutable;
19 import java.util.LinkedHashMap;
20 import java.util.Map;
21 import java.util.Map.Entry;
22 
23 /** A {@code RegularImmutableTable} optimized for sparse data. */
24 @GwtCompatible
25 @Immutable(containerOf = {"R", "C", "V"})
26 final class SparseImmutableTable<R, C, V> extends RegularImmutableTable<R, C, V> {
27   static final ImmutableTable<Object, Object, Object> EMPTY =
28       new SparseImmutableTable<>(
29           ImmutableList.<Cell<Object, Object, Object>>of(), ImmutableSet.of(), ImmutableSet.of());
30 
31   private final ImmutableMap<R, ImmutableMap<C, V>> rowMap;
32   private final ImmutableMap<C, ImmutableMap<R, V>> columnMap;
33 
34   // For each cell in iteration order, the index of that cell's row key in the row key list.
35   @SuppressWarnings("Immutable") // We don't modify this after construction.
36   private final int[] cellRowIndices;
37 
38   // For each cell in iteration order, the index of that cell's column key in the list of column
39   // keys present in that row.
40   @SuppressWarnings("Immutable") // We don't modify this after construction.
41   private final int[] cellColumnInRowIndices;
42 
43   SparseImmutableTable(
44       ImmutableList<Cell<R, C, V>> cellList,
45       ImmutableSet<R> rowSpace,
46       ImmutableSet<C> columnSpace) {
47     Map<R, Integer> rowIndex = Maps.indexMap(rowSpace);
48     Map<R, Map<C, V>> rows = Maps.newLinkedHashMap();
49     for (R row : rowSpace) {
50       rows.put(row, new LinkedHashMap<C, V>());
51     }
52     Map<C, Map<R, V>> columns = Maps.newLinkedHashMap();
53     for (C col : columnSpace) {
54       columns.put(col, new LinkedHashMap<R, V>());
55     }
56     int[] cellRowIndices = new int[cellList.size()];
57     int[] cellColumnInRowIndices = new int[cellList.size()];
58     for (int i = 0; i < cellList.size(); i++) {
59       Cell<R, C, V> cell = cellList.get(i);
60       R rowKey = cell.getRowKey();
61       C columnKey = cell.getColumnKey();
62       V value = cell.getValue();
63 
64       cellRowIndices[i] = rowIndex.get(rowKey);
65       Map<C, V> thisRow = rows.get(rowKey);
66       cellColumnInRowIndices[i] = thisRow.size();
67       V oldValue = thisRow.put(columnKey, value);
68       checkNoDuplicate(rowKey, columnKey, oldValue, value);
69       columns.get(columnKey).put(rowKey, value);
70     }
71     this.cellRowIndices = cellRowIndices;
72     this.cellColumnInRowIndices = cellColumnInRowIndices;
73     ImmutableMap.Builder<R, ImmutableMap<C, V>> rowBuilder =
74         new ImmutableMap.Builder<>(rows.size());
75     for (Entry<R, Map<C, V>> row : rows.entrySet()) {
76       rowBuilder.put(row.getKey(), ImmutableMap.copyOf(row.getValue()));
77     }
78     this.rowMap = rowBuilder.build();
79 
80     ImmutableMap.Builder<C, ImmutableMap<R, V>> columnBuilder =
81         new ImmutableMap.Builder<>(columns.size());
82     for (Entry<C, Map<R, V>> col : columns.entrySet()) {
83       columnBuilder.put(col.getKey(), ImmutableMap.copyOf(col.getValue()));
84     }
85     this.columnMap = columnBuilder.build();
86   }
87 
88   @Override
89   public ImmutableMap<C, Map<R, V>> columnMap() {
90     // Casts without copying.
91     ImmutableMap<C, ImmutableMap<R, V>> columnMap = this.columnMap;
92     return ImmutableMap.<C, Map<R, V>>copyOf(columnMap);
93   }
94 
95   @Override
96   public ImmutableMap<R, Map<C, V>> rowMap() {
97     // Casts without copying.
98     ImmutableMap<R, ImmutableMap<C, V>> rowMap = this.rowMap;
99     return ImmutableMap.<R, Map<C, V>>copyOf(rowMap);
100   }
101 
102   @Override
103   public int size() {
104     return cellRowIndices.length;
105   }
106 
107   @Override
108   Cell<R, C, V> getCell(int index) {
109     int rowIndex = cellRowIndices[index];
110     Entry<R, ImmutableMap<C, V>> rowEntry = rowMap.entrySet().asList().get(rowIndex);
111     ImmutableMap<C, V> row = rowEntry.getValue();
112     int columnIndex = cellColumnInRowIndices[index];
113     Entry<C, V> colEntry = row.entrySet().asList().get(columnIndex);
114     return cellOf(rowEntry.getKey(), colEntry.getKey(), colEntry.getValue());
115   }
116 
117   @Override
118   V getValue(int index) {
119     int rowIndex = cellRowIndices[index];
120     ImmutableMap<C, V> row = rowMap.values().asList().get(rowIndex);
121     int columnIndex = cellColumnInRowIndices[index];
122     return row.values().asList().get(columnIndex);
123   }
124 
125   @Override
126   SerializedForm createSerializedForm() {
127     Map<C, Integer> columnKeyToIndex = Maps.indexMap(columnKeySet());
128     int[] cellColumnIndices = new int[cellSet().size()];
129     int i = 0;
130     for (Cell<R, C, V> cell : cellSet()) {
131       cellColumnIndices[i++] = columnKeyToIndex.get(cell.getColumnKey());
132     }
133     return SerializedForm.create(this, cellRowIndices, cellColumnIndices);
134   }
135 }