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 19 import java.util.LinkedHashMap; 20 import java.util.Map; 21 22 import javax.annotation.concurrent.Immutable; 23 24 /** 25 * A {@code RegularImmutableTable} optimized for sparse data. 26 */ 27 @GwtCompatible 28 @Immutable 29 final class SparseImmutableTable<R, C, V> 30 extends RegularImmutableTable<R, C, V> { 31 32 private final ImmutableMap<R, Map<C, V>> rowMap; 33 private final ImmutableMap<C, Map<R, V>> columnMap; 34 private final int[] iterationOrderRow; 35 private final int[] iterationOrderColumn; 36 SparseImmutableTable(ImmutableList<Cell<R, C, V>> cellList, ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace)37 SparseImmutableTable(ImmutableList<Cell<R, C, V>> cellList, 38 ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace) { 39 Map<R, Integer> rowIndex = Maps.newHashMap(); 40 Map<R, Map<C, V>> rows = Maps.newLinkedHashMap(); 41 for (R row : rowSpace) { 42 rowIndex.put(row, rows.size()); 43 rows.put(row, new LinkedHashMap<C, V>()); 44 } 45 Map<C, Map<R, V>> columns = Maps.newLinkedHashMap(); 46 for (C col : columnSpace) { 47 columns.put(col, new LinkedHashMap<R, V>()); 48 } 49 int[] iterationOrderRow = new int[cellList.size()]; 50 int[] iterationOrderColumn = new int[cellList.size()]; 51 for (int i = 0; i < cellList.size(); i++) { 52 Cell<R, C, V> cell = cellList.get(i); 53 R rowKey = cell.getRowKey(); 54 C columnKey = cell.getColumnKey(); 55 V value = cell.getValue(); 56 57 iterationOrderRow[i] = rowIndex.get(rowKey); 58 Map<C, V> thisRow = rows.get(rowKey); 59 iterationOrderColumn[i] = thisRow.size(); 60 V oldValue = thisRow.put(columnKey, value); 61 if (oldValue != null) { 62 throw new IllegalArgumentException("Duplicate value for row=" + rowKey + ", column=" 63 + columnKey + ": " + value + ", " + oldValue); 64 } 65 columns.get(columnKey).put(rowKey, value); 66 } 67 this.iterationOrderRow = iterationOrderRow; 68 this.iterationOrderColumn = iterationOrderColumn; 69 ImmutableMap.Builder<R, Map<C, V>> rowBuilder = ImmutableMap.builder(); 70 for (Map.Entry<R, Map<C, V>> row : rows.entrySet()) { 71 rowBuilder.put(row.getKey(), ImmutableMap.copyOf(row.getValue())); 72 } 73 this.rowMap = rowBuilder.build(); 74 75 ImmutableMap.Builder<C, Map<R, V>> columnBuilder = ImmutableMap.builder(); 76 for (Map.Entry<C, Map<R, V>> col : columns.entrySet()) { 77 columnBuilder.put(col.getKey(), ImmutableMap.copyOf(col.getValue())); 78 } 79 this.columnMap = columnBuilder.build(); 80 } 81 columnMap()82 @Override public ImmutableMap<C, Map<R, V>> columnMap() { 83 return columnMap; 84 } 85 rowMap()86 @Override public ImmutableMap<R, Map<C, V>> rowMap() { 87 return rowMap; 88 } 89 90 @Override size()91 public int size() { 92 return iterationOrderRow.length; 93 } 94 95 @Override getCell(int index)96 Cell<R, C, V> getCell(int index) { 97 int rowIndex = iterationOrderRow[index]; 98 Map.Entry<R, Map<C, V>> rowEntry = rowMap.entrySet().asList().get(rowIndex); 99 ImmutableMap<C, V> row = (ImmutableMap<C, V>) rowEntry.getValue(); 100 int columnIndex = iterationOrderColumn[index]; 101 Map.Entry<C, V> colEntry = row.entrySet().asList().get(columnIndex); 102 return cellOf(rowEntry.getKey(), colEntry.getKey(), colEntry.getValue()); 103 } 104 105 @Override getValue(int index)106 V getValue(int index) { 107 int rowIndex = iterationOrderRow[index]; 108 ImmutableMap<C, V> row = (ImmutableMap<C, V>) rowMap.values().asList().get(rowIndex); 109 int columnIndex = iterationOrderColumn[index]; 110 return row.values().asList().get(columnIndex); 111 } 112 } 113