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