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