1/* 2 * Copyright (C) 2009 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.base.Preconditions.checkNotNull; 21 22import com.google.common.annotations.GwtCompatible; 23import com.google.common.annotations.VisibleForTesting; 24import com.google.common.base.Function; 25import com.google.common.base.Objects; 26 27import java.util.Collections; 28import java.util.Comparator; 29import java.util.List; 30import java.util.Map; 31 32import javax.annotation.Nullable; 33import javax.annotation.concurrent.Immutable; 34 35/** 36 * An implementation of {@link ImmutableTable} holding an arbitrary number of 37 * cells. 38 * 39 * @author gak@google.com (Gregory Kick) 40 */ 41@GwtCompatible 42abstract class RegularImmutableTable<R, C, V> extends ImmutableTable<R, C, V> { 43 private final ImmutableSet<Cell<R, C, V>> cellSet; 44 45 private RegularImmutableTable(ImmutableSet<Cell<R, C, V>> cellSet) { 46 this.cellSet = cellSet; 47 } 48 49 private static final Function<Cell<Object, Object, Object>, Object> 50 GET_VALUE_FUNCTION = 51 new Function<Cell<Object, Object, Object>, Object>() { 52 @Override public Object apply(Cell<Object, Object, Object> from) { 53 return from.getValue(); 54 } 55 }; 56 57 @SuppressWarnings("unchecked") 58 private Function<Cell<R, C, V>, V> getValueFunction() { 59 return (Function) GET_VALUE_FUNCTION; 60 } 61 62 @Nullable private transient volatile ImmutableList<V> valueList; 63 64 @Override public final ImmutableCollection<V> values() { 65 ImmutableList<V> result = valueList; 66 if (result == null) { 67 valueList = result = ImmutableList.copyOf( 68 Iterables.transform(cellSet(), getValueFunction())); 69 } 70 return result; 71 } 72 73 @Override public final int size() { 74 return cellSet().size(); 75 } 76 77 @Override public final boolean containsValue(@Nullable Object value) { 78 return values().contains(value); 79 } 80 81 @Override public final boolean isEmpty() { 82 return false; 83 } 84 85 @Override public final ImmutableSet<Cell<R, C, V>> cellSet() { 86 return cellSet; 87 } 88 89 static final <R, C, V> RegularImmutableTable<R, C, V> forCells( 90 List<Cell<R, C, V>> cells, 91 @Nullable final Comparator<? super R> rowComparator, 92 @Nullable final Comparator<? super C> columnComparator) { 93 checkNotNull(cells); 94 if (rowComparator != null || columnComparator != null) { 95 /* 96 * This sorting logic leads to a cellSet() ordering that may not be 97 * expected and that isn't documented in the Javadoc. If a row Comparator 98 * is provided, cellSet() iterates across the columns in the first row, 99 * the columns in the second row, etc. If a column Comparator is provided 100 * but a row Comparator isn't, cellSet() iterates across the rows in the 101 * first column, the rows in the second column, etc. 102 */ 103 Comparator<Cell<R, C, V>> comparator = new Comparator<Cell<R, C, V>>() { 104 @Override public int compare(Cell<R, C, V> cell1, Cell<R, C, V> cell2) { 105 int rowCompare = (rowComparator == null) ? 0 106 : rowComparator.compare(cell1.getRowKey(), cell2.getRowKey()); 107 if (rowCompare != 0) { 108 return rowCompare; 109 } 110 return (columnComparator == null) ? 0 111 : columnComparator.compare( 112 cell1.getColumnKey(), cell2.getColumnKey()); 113 } 114 }; 115 Collections.sort(cells, comparator); 116 } 117 return forCellsInternal(cells, rowComparator, columnComparator); 118 } 119 120 static final <R, C, V> RegularImmutableTable<R, C, V> forCells( 121 Iterable<Cell<R, C, V>> cells) { 122 return forCellsInternal(cells, null, null); 123 } 124 125 /** 126 * A factory that chooses the most space-efficient representation of the 127 * table. 128 */ 129 private static final <R, C, V> RegularImmutableTable<R, C, V> 130 forCellsInternal(Iterable<Cell<R, C, V>> cells, 131 @Nullable Comparator<? super R> rowComparator, 132 @Nullable Comparator<? super C> columnComparator) { 133 ImmutableSet.Builder<Cell<R, C, V>> cellSetBuilder = ImmutableSet.builder(); 134 ImmutableSet.Builder<R> rowSpaceBuilder = ImmutableSet.builder(); 135 ImmutableSet.Builder<C> columnSpaceBuilder = ImmutableSet.builder(); 136 for (Cell<R, C, V> cell : cells) { 137 cellSetBuilder.add(cell); 138 rowSpaceBuilder.add(cell.getRowKey()); 139 columnSpaceBuilder.add(cell.getColumnKey()); 140 } 141 ImmutableSet<Cell<R, C, V>> cellSet = cellSetBuilder.build(); 142 143 ImmutableSet<R> rowSpace = rowSpaceBuilder.build(); 144 if (rowComparator != null) { 145 List<R> rowList = Lists.newArrayList(rowSpace); 146 Collections.sort(rowList, rowComparator); 147 rowSpace = ImmutableSet.copyOf(rowList); 148 } 149 ImmutableSet<C> columnSpace = columnSpaceBuilder.build(); 150 if (columnComparator != null) { 151 List<C> columnList = Lists.newArrayList(columnSpace); 152 Collections.sort(columnList, columnComparator); 153 columnSpace = ImmutableSet.copyOf(columnList); 154 } 155 156 // use a dense table if more than half of the cells have values 157 // TODO(gak): tune this condition based on empirical evidence 158 return (cellSet.size() > ((rowSpace.size() * columnSpace.size()) / 2 )) ? 159 new DenseImmutableTable<R, C, V>(cellSet, rowSpace, columnSpace) : 160 new SparseImmutableTable<R, C, V>(cellSet, rowSpace, columnSpace); 161 } 162 163 /** 164 * A {@code RegularImmutableTable} optimized for sparse data. 165 */ 166 @Immutable 167 @VisibleForTesting 168 static final class SparseImmutableTable<R, C, V> 169 extends RegularImmutableTable<R, C, V> { 170 171 private final ImmutableMap<R, Map<C, V>> rowMap; 172 private final ImmutableMap<C, Map<R, V>> columnMap; 173 174 /** 175 * Creates a {@link Map} over the key space with 176 * {@link ImmutableMap.Builder}s ready for values. 177 */ 178 private static final <A, B, V> Map<A, ImmutableMap.Builder<B, V>> 179 makeIndexBuilder(ImmutableSet<A> keySpace) { 180 Map<A, ImmutableMap.Builder<B, V>> indexBuilder = Maps.newLinkedHashMap(); 181 for (A key : keySpace) { 182 indexBuilder.put(key, ImmutableMap.<B, V>builder()); 183 } 184 return indexBuilder; 185 } 186 187 /** 188 * Builds the value maps of the index and creates an immutable copy of the 189 * map. 190 */ 191 private static final <A, B, V> ImmutableMap<A, Map<B, V>> buildIndex( 192 Map<A, ImmutableMap.Builder<B, V>> indexBuilder) { 193 return ImmutableMap.copyOf(Maps.transformValues(indexBuilder, 194 new Function<ImmutableMap.Builder<B, V>, Map<B, V>>() { 195 @Override public Map<B, V> apply(ImmutableMap.Builder<B, V> from) { 196 return from.build(); 197 } 198 })); 199 } 200 201 SparseImmutableTable(ImmutableSet<Cell<R, C, V>> cellSet, 202 ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace) { 203 super(cellSet); 204 Map<R, ImmutableMap.Builder<C, V>> rowIndexBuilder 205 = makeIndexBuilder(rowSpace); 206 Map<C, ImmutableMap.Builder<R, V>> columnIndexBuilder 207 = makeIndexBuilder(columnSpace); 208 for (Cell<R, C, V> cell : cellSet) { 209 R rowKey = cell.getRowKey(); 210 C columnKey = cell.getColumnKey(); 211 V value = cell.getValue(); 212 rowIndexBuilder.get(rowKey).put(columnKey, value); 213 columnIndexBuilder.get(columnKey).put(rowKey, value); 214 } 215 this.rowMap = buildIndex(rowIndexBuilder); 216 this.columnMap = buildIndex(columnIndexBuilder); 217 } 218 219 @Override public ImmutableMap<R, V> column(C columnKey) { 220 checkNotNull(columnKey); 221 // value maps are guaranteed to be immutable maps 222 return Objects.firstNonNull((ImmutableMap<R, V>) columnMap.get(columnKey), 223 ImmutableMap.<R, V>of()); 224 } 225 226 @Override public ImmutableSet<C> columnKeySet() { 227 return columnMap.keySet(); 228 } 229 230 @Override public ImmutableMap<C, Map<R, V>> columnMap() { 231 return columnMap; 232 } 233 234 @Override public ImmutableMap<C, V> row(R rowKey) { 235 checkNotNull(rowKey); 236 // value maps are guaranteed to be immutable maps 237 return Objects.firstNonNull((ImmutableMap<C, V>) rowMap.get(rowKey), 238 ImmutableMap.<C, V>of()); 239 } 240 241 @Override public ImmutableSet<R> rowKeySet() { 242 return rowMap.keySet(); 243 } 244 245 @Override public ImmutableMap<R, Map<C, V>> rowMap() { 246 return rowMap; 247 } 248 249 @Override public boolean contains(@Nullable Object rowKey, 250 @Nullable Object columnKey) { 251 Map<C, V> row = rowMap.get(rowKey); 252 return (row != null) && row.containsKey(columnKey); 253 } 254 255 @Override public boolean containsColumn(@Nullable Object columnKey) { 256 return columnMap.containsKey(columnKey); 257 } 258 259 @Override public boolean containsRow(@Nullable Object rowKey) { 260 return rowMap.containsKey(rowKey); 261 } 262 263 @Override public V get(@Nullable Object rowKey, 264 @Nullable Object columnKey) { 265 Map<C, V> row = rowMap.get(rowKey); 266 return (row == null) ? null : row.get(columnKey); 267 } 268 } 269 270 /** 271 * A {@code RegularImmutableTable} optimized for dense data. 272 */ 273 @Immutable @VisibleForTesting 274 static final class DenseImmutableTable<R, C, V> 275 extends RegularImmutableTable<R, C, V> { 276 277 private final ImmutableBiMap<R, Integer> rowKeyToIndex; 278 private final ImmutableBiMap<C, Integer> columnKeyToIndex; 279 private final V[][] values; 280 281 private static <E> ImmutableBiMap<E, Integer> makeIndex( 282 ImmutableSet<E> set) { 283 ImmutableBiMap.Builder<E, Integer> indexBuilder = 284 ImmutableBiMap.builder(); 285 int i = 0; 286 for (E key : set) { 287 indexBuilder.put(key, i); 288 i++; 289 } 290 return indexBuilder.build(); 291 } 292 293 DenseImmutableTable(ImmutableSet<Cell<R, C, V>> cellSet, 294 ImmutableSet<R> rowSpace, ImmutableSet<C> columnSpace) { 295 super(cellSet); 296 @SuppressWarnings("unchecked") 297 V[][] array = (V[][]) new Object[rowSpace.size()][columnSpace.size()]; 298 this.values = array; 299 this.rowKeyToIndex = makeIndex(rowSpace); 300 this.columnKeyToIndex = makeIndex(columnSpace); 301 for (Cell<R, C, V> cell : cellSet) { 302 R rowKey = cell.getRowKey(); 303 C columnKey = cell.getColumnKey(); 304 int rowIndex = rowKeyToIndex.get(rowKey); 305 int columnIndex = columnKeyToIndex.get(columnKey); 306 V existingValue = values[rowIndex][columnIndex]; 307 checkArgument(existingValue == null, "duplicate key: (%s, %s)", rowKey, 308 columnKey); 309 values[rowIndex][columnIndex] = cell.getValue(); 310 } 311 } 312 313 @Override public ImmutableMap<R, V> column(C columnKey) { 314 checkNotNull(columnKey); 315 Integer columnIndexInteger = columnKeyToIndex.get(columnKey); 316 if (columnIndexInteger == null) { 317 return ImmutableMap.of(); 318 } else { 319 // unbox only once 320 int columnIndex = columnIndexInteger; 321 ImmutableMap.Builder<R, V> columnBuilder = ImmutableMap.builder(); 322 for (int i = 0; i < values.length; i++) { 323 V value = values[i][columnIndex]; 324 if (value != null) { 325 columnBuilder.put(rowKeyToIndex.inverse().get(i), value); 326 } 327 } 328 return columnBuilder.build(); 329 } 330 } 331 332 @Override public ImmutableSet<C> columnKeySet() { 333 return columnKeyToIndex.keySet(); 334 } 335 336 private transient volatile ImmutableMap<C, Map<R, V>> columnMap; 337 338 private ImmutableMap<C, Map<R, V>> makeColumnMap() { 339 ImmutableMap.Builder<C, Map<R, V>> columnMapBuilder = 340 ImmutableMap.builder(); 341 for (int c = 0; c < columnKeyToIndex.size(); c++) { 342 ImmutableMap.Builder<R, V> rowMapBuilder = ImmutableMap.builder(); 343 for (int r = 0; r < rowKeyToIndex.size(); r++) { 344 V value = values[r][c]; 345 if (value != null) { 346 rowMapBuilder.put(rowKeyToIndex.inverse().get(r), value); 347 } 348 } 349 columnMapBuilder.put(columnKeyToIndex.inverse().get(c), 350 rowMapBuilder.build()); 351 } 352 return columnMapBuilder.build(); 353 } 354 355 @Override public ImmutableMap<C, Map<R, V>> columnMap() { 356 ImmutableMap<C, Map<R, V>> result = columnMap; 357 if (result == null) { 358 columnMap = result = makeColumnMap(); 359 } 360 return result; 361 } 362 363 @Override public boolean contains(@Nullable Object rowKey, 364 @Nullable Object columnKey) { 365 return (get(rowKey, columnKey) != null); 366 } 367 368 @Override public boolean containsColumn(@Nullable Object columnKey) { 369 return columnKeyToIndex.containsKey(columnKey); 370 } 371 372 @Override public boolean containsRow(@Nullable Object rowKey) { 373 return rowKeyToIndex.containsKey(rowKey); 374 } 375 376 @Override public V get(@Nullable Object rowKey, 377 @Nullable Object columnKey) { 378 Integer rowIndex = rowKeyToIndex.get(rowKey); 379 Integer columnIndex = columnKeyToIndex.get(columnKey); 380 return ((rowIndex == null) || (columnIndex == null)) ? null 381 : values[rowIndex][columnIndex]; 382 } 383 384 @Override public ImmutableMap<C, V> row(R rowKey) { 385 checkNotNull(rowKey); 386 Integer rowIndex = rowKeyToIndex.get(rowKey); 387 if (rowIndex == null) { 388 return ImmutableMap.of(); 389 } else { 390 ImmutableMap.Builder<C, V> rowBuilder = ImmutableMap.builder(); 391 V[] row = values[rowIndex]; 392 for (int r = 0; r < row.length; r++) { 393 V value = row[r]; 394 if (value != null) { 395 rowBuilder.put(columnKeyToIndex.inverse().get(r), value); 396 } 397 } 398 return rowBuilder.build(); 399 } 400 } 401 402 @Override public ImmutableSet<R> rowKeySet() { 403 return rowKeyToIndex.keySet(); 404 } 405 406 private transient volatile ImmutableMap<R, Map<C, V>> rowMap; 407 408 private ImmutableMap<R, Map<C, V>> makeRowMap() { 409 ImmutableMap.Builder<R, Map<C, V>> rowMapBuilder = ImmutableMap.builder(); 410 for (int r = 0; r < values.length; r++) { 411 V[] row = values[r]; 412 ImmutableMap.Builder<C, V> columnMapBuilder = ImmutableMap.builder(); 413 for (int c = 0; c < row.length; c++) { 414 V value = row[c]; 415 if (value != null) { 416 columnMapBuilder.put(columnKeyToIndex.inverse().get(c), value); 417 } 418 } 419 rowMapBuilder.put(rowKeyToIndex.inverse().get(r), 420 columnMapBuilder.build()); 421 } 422 return rowMapBuilder.build(); 423 } 424 425 @Override public ImmutableMap<R, Map<C, V>> rowMap() { 426 ImmutableMap<R, Map<C, V>> result = rowMap; 427 if (result == null) { 428 rowMap = result = makeRowMap(); 429 } 430 return result; 431 } 432 } 433} 434