001/* 002 * Copyright (C) 2008 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.base.Function; 025import com.google.common.base.Objects; 026import com.google.common.base.Supplier; 027import com.google.common.collect.Table.Cell; 028import java.io.Serializable; 029import java.util.Collection; 030import java.util.Collections; 031import java.util.Iterator; 032import java.util.Map; 033import java.util.Set; 034import java.util.SortedMap; 035import java.util.SortedSet; 036import javax.annotation.CheckForNull; 037import org.checkerframework.checker.nullness.qual.Nullable; 038 039/** 040 * Provides static methods that involve a {@code Table}. 041 * 042 * <p>See the Guava User Guide article on <a href= 043 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#tables">{@code Tables}</a>. 044 * 045 * @author Jared Levy 046 * @author Louis Wasserman 047 * @since 7.0 048 */ 049@GwtCompatible 050@ElementTypesAreNonnullByDefault 051public final class Tables { 052 private Tables() {} 053 054 /** 055 * Returns an immutable cell with the specified row key, column key, and value. 056 * 057 * <p>The returned cell is serializable. 058 * 059 * @param rowKey the row key to be associated with the returned cell 060 * @param columnKey the column key to be associated with the returned cell 061 * @param value the value to be associated with the returned cell 062 */ 063 public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 064 Cell<R, C, V> immutableCell( 065 @ParametricNullness R rowKey, 066 @ParametricNullness C columnKey, 067 @ParametricNullness V value) { 068 return new ImmutableCell<>(rowKey, columnKey, value); 069 } 070 071 static final class ImmutableCell< 072 R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 073 extends AbstractCell<R, C, V> implements Serializable { 074 @ParametricNullness private final R rowKey; 075 @ParametricNullness private final C columnKey; 076 @ParametricNullness private final V value; 077 078 ImmutableCell( 079 @ParametricNullness R rowKey, 080 @ParametricNullness C columnKey, 081 @ParametricNullness V value) { 082 this.rowKey = rowKey; 083 this.columnKey = columnKey; 084 this.value = value; 085 } 086 087 @Override 088 @ParametricNullness 089 public R getRowKey() { 090 return rowKey; 091 } 092 093 @Override 094 @ParametricNullness 095 public C getColumnKey() { 096 return columnKey; 097 } 098 099 @Override 100 @ParametricNullness 101 public V getValue() { 102 return value; 103 } 104 105 private static final long serialVersionUID = 0; 106 } 107 108 abstract static class AbstractCell< 109 R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 110 implements Cell<R, C, V> { 111 // needed for serialization 112 AbstractCell() {} 113 114 @Override 115 public boolean equals(@CheckForNull Object obj) { 116 if (obj == this) { 117 return true; 118 } 119 if (obj instanceof Cell) { 120 Cell<?, ?, ?> other = (Cell<?, ?, ?>) obj; 121 return Objects.equal(getRowKey(), other.getRowKey()) 122 && Objects.equal(getColumnKey(), other.getColumnKey()) 123 && Objects.equal(getValue(), other.getValue()); 124 } 125 return false; 126 } 127 128 @Override 129 public int hashCode() { 130 return Objects.hashCode(getRowKey(), getColumnKey(), getValue()); 131 } 132 133 @Override 134 public String toString() { 135 return "(" + getRowKey() + "," + getColumnKey() + ")=" + getValue(); 136 } 137 } 138 139 /** 140 * Creates a transposed view of a given table that flips its row and column keys. In other words, 141 * calling {@code get(columnKey, rowKey)} on the generated table always returns the same value as 142 * calling {@code get(rowKey, columnKey)} on the original table. Updating the original table 143 * changes the contents of the transposed table and vice versa. 144 * 145 * <p>The returned table supports update operations as long as the input table supports the 146 * analogous operation with swapped rows and columns. For example, in a {@link HashBasedTable} 147 * instance, {@code rowKeySet().iterator()} supports {@code remove()} but {@code 148 * columnKeySet().iterator()} doesn't. With a transposed {@link HashBasedTable}, it's the other 149 * way around. 150 */ 151 public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 152 Table<C, R, V> transpose(Table<R, C, V> table) { 153 return (table instanceof TransposeTable) 154 ? ((TransposeTable<R, C, V>) table).original 155 : new TransposeTable<C, R, V>(table); 156 } 157 158 private static class TransposeTable< 159 C extends @Nullable Object, R extends @Nullable Object, V extends @Nullable Object> 160 extends AbstractTable<C, R, V> { 161 final Table<R, C, V> original; 162 163 TransposeTable(Table<R, C, V> original) { 164 this.original = checkNotNull(original); 165 } 166 167 @Override 168 public void clear() { 169 original.clear(); 170 } 171 172 @Override 173 public Map<C, V> column(@ParametricNullness R columnKey) { 174 return original.row(columnKey); 175 } 176 177 @Override 178 public Set<R> columnKeySet() { 179 return original.rowKeySet(); 180 } 181 182 @Override 183 public Map<R, Map<C, V>> columnMap() { 184 return original.rowMap(); 185 } 186 187 @Override 188 public boolean contains(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 189 return original.contains(columnKey, rowKey); 190 } 191 192 @Override 193 public boolean containsColumn(@CheckForNull Object columnKey) { 194 return original.containsRow(columnKey); 195 } 196 197 @Override 198 public boolean containsRow(@CheckForNull Object rowKey) { 199 return original.containsColumn(rowKey); 200 } 201 202 @Override 203 public boolean containsValue(@CheckForNull Object value) { 204 return original.containsValue(value); 205 } 206 207 @Override 208 @CheckForNull 209 public V get(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 210 return original.get(columnKey, rowKey); 211 } 212 213 @Override 214 @CheckForNull 215 public V put( 216 @ParametricNullness C rowKey, 217 @ParametricNullness R columnKey, 218 @ParametricNullness V value) { 219 return original.put(columnKey, rowKey, value); 220 } 221 222 @Override 223 public void putAll(Table<? extends C, ? extends R, ? extends V> table) { 224 original.putAll(transpose(table)); 225 } 226 227 @Override 228 @CheckForNull 229 public V remove(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 230 return original.remove(columnKey, rowKey); 231 } 232 233 @Override 234 public Map<R, V> row(@ParametricNullness C rowKey) { 235 return original.column(rowKey); 236 } 237 238 @Override 239 public Set<C> rowKeySet() { 240 return original.columnKeySet(); 241 } 242 243 @Override 244 public Map<C, Map<R, V>> rowMap() { 245 return original.columnMap(); 246 } 247 248 @Override 249 public int size() { 250 return original.size(); 251 } 252 253 @Override 254 public Collection<V> values() { 255 return original.values(); 256 } 257 258 // Will cast TRANSPOSE_CELL to a type that always succeeds 259 private static final Function TRANSPOSE_CELL = 260 new Function<Cell<?, ?, ?>, Cell<?, ?, ?>>() { 261 @Override 262 public Cell<?, ?, ?> apply(Cell<?, ?, ?> cell) { 263 return immutableCell(cell.getColumnKey(), cell.getRowKey(), cell.getValue()); 264 } 265 }; 266 267 @SuppressWarnings("unchecked") 268 @Override 269 Iterator<Cell<C, R, V>> cellIterator() { 270 return Iterators.transform( 271 original.cellSet().iterator(), (Function<Cell<R, C, V>, Cell<C, R, V>>) TRANSPOSE_CELL); 272 } 273 } 274 275 /** 276 * Creates a table that uses the specified backing map and factory. It can generate a table based 277 * on arbitrary {@link Map} classes. 278 * 279 * <p>The {@code factory}-generated and {@code backingMap} classes determine the table iteration 280 * order. However, the table's {@code row()} method returns instances of a different class than 281 * {@code factory.get()} does. 282 * 283 * <p>Call this method only when the simpler factory methods in classes like {@link 284 * HashBasedTable} and {@link TreeBasedTable} won't suffice. 285 * 286 * <p>The views returned by the {@code Table} methods {@link Table#column}, {@link 287 * Table#columnKeySet}, and {@link Table#columnMap} have iterators that don't support {@code 288 * remove()}. Otherwise, all optional operations are supported. Null row keys, columns keys, and 289 * values are not supported. 290 * 291 * <p>Lookups by row key are often faster than lookups by column key, because the data is stored 292 * in a {@code Map<R, Map<C, V>>}. A method call like {@code column(columnKey).get(rowKey)} still 293 * runs quickly, since the row key is provided. However, {@code column(columnKey).size()} takes 294 * longer, since an iteration across all row keys occurs. 295 * 296 * <p>Note that this implementation is not synchronized. If multiple threads access this table 297 * concurrently and one of the threads modifies the table, it must be synchronized externally. 298 * 299 * <p>The table is serializable if {@code backingMap}, {@code factory}, the maps generated by 300 * {@code factory}, and the table contents are all serializable. 301 * 302 * <p>Note: the table assumes complete ownership over of {@code backingMap} and the maps returned 303 * by {@code factory}. Those objects should not be manually updated and they should not use soft, 304 * weak, or phantom references. 305 * 306 * @param backingMap place to store the mapping from each row key to its corresponding column key 307 * / value map 308 * @param factory supplier of new, empty maps that will each hold all column key / value mappings 309 * for a given row key 310 * @throws IllegalArgumentException if {@code backingMap} is not empty 311 * @since 10.0 312 */ 313 public static <R, C, V> Table<R, C, V> newCustomTable( 314 Map<R, Map<C, V>> backingMap, Supplier<? extends Map<C, V>> factory) { 315 checkArgument(backingMap.isEmpty()); 316 checkNotNull(factory); 317 // TODO(jlevy): Wrap factory to validate that the supplied maps are empty? 318 return new StandardTable<>(backingMap, factory); 319 } 320 321 /** 322 * Returns a view of a table where each value is transformed by a function. All other properties 323 * of the table, such as iteration order, are left intact. 324 * 325 * <p>Changes in the underlying table are reflected in this view. Conversely, this view supports 326 * removal operations, and these are reflected in the underlying table. 327 * 328 * <p>It's acceptable for the underlying table to contain null keys, and even null values provided 329 * that the function is capable of accepting null input. The transformed table might contain null 330 * values, if the function sometimes gives a null result. 331 * 332 * <p>The returned table is not thread-safe or serializable, even if the underlying table is. 333 * 334 * <p>The function is applied lazily, invoked when needed. This is necessary for the returned 335 * table to be a view, but it means that the function will be applied many times for bulk 336 * operations like {@link Table#containsValue} and {@code Table.toString()}. For this to perform 337 * well, {@code function} should be fast. To avoid lazy evaluation when the returned table doesn't 338 * need to be a view, copy the returned table into a new table of your choosing. 339 * 340 * @since 10.0 341 */ 342 public static < 343 R extends @Nullable Object, 344 C extends @Nullable Object, 345 V1 extends @Nullable Object, 346 V2 extends @Nullable Object> 347 Table<R, C, V2> transformValues( 348 Table<R, C, V1> fromTable, Function<? super V1, V2> function) { 349 return new TransformedTable<>(fromTable, function); 350 } 351 352 private static class TransformedTable< 353 R extends @Nullable Object, 354 C extends @Nullable Object, 355 V1 extends @Nullable Object, 356 V2 extends @Nullable Object> 357 extends AbstractTable<R, C, V2> { 358 final Table<R, C, V1> fromTable; 359 final Function<? super V1, V2> function; 360 361 TransformedTable(Table<R, C, V1> fromTable, Function<? super V1, V2> function) { 362 this.fromTable = checkNotNull(fromTable); 363 this.function = checkNotNull(function); 364 } 365 366 @Override 367 public boolean contains(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 368 return fromTable.contains(rowKey, columnKey); 369 } 370 371 @Override 372 @CheckForNull 373 public V2 get(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 374 // The function is passed a null input only when the table contains a null 375 // value. 376 // The cast is safe because of the contains() check. 377 return contains(rowKey, columnKey) 378 ? function.apply(uncheckedCastNullableTToT(fromTable.get(rowKey, columnKey))) 379 : null; 380 } 381 382 @Override 383 public int size() { 384 return fromTable.size(); 385 } 386 387 @Override 388 public void clear() { 389 fromTable.clear(); 390 } 391 392 @Override 393 @CheckForNull 394 public V2 put( 395 @ParametricNullness R rowKey, 396 @ParametricNullness C columnKey, 397 @ParametricNullness V2 value) { 398 throw new UnsupportedOperationException(); 399 } 400 401 @Override 402 public void putAll(Table<? extends R, ? extends C, ? extends V2> table) { 403 throw new UnsupportedOperationException(); 404 } 405 406 @Override 407 @CheckForNull 408 public V2 remove(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 409 return contains(rowKey, columnKey) 410 // The cast is safe because of the contains() check. 411 ? function.apply(uncheckedCastNullableTToT(fromTable.remove(rowKey, columnKey))) 412 : null; 413 } 414 415 @Override 416 public Map<C, V2> row(@ParametricNullness R rowKey) { 417 return Maps.transformValues(fromTable.row(rowKey), function); 418 } 419 420 @Override 421 public Map<R, V2> column(@ParametricNullness C columnKey) { 422 return Maps.transformValues(fromTable.column(columnKey), function); 423 } 424 425 Function<Cell<R, C, V1>, Cell<R, C, V2>> cellFunction() { 426 return new Function<Cell<R, C, V1>, Cell<R, C, V2>>() { 427 @Override 428 public Cell<R, C, V2> apply(Cell<R, C, V1> cell) { 429 return immutableCell( 430 cell.getRowKey(), cell.getColumnKey(), function.apply(cell.getValue())); 431 } 432 }; 433 } 434 435 @Override 436 Iterator<Cell<R, C, V2>> cellIterator() { 437 return Iterators.transform(fromTable.cellSet().iterator(), cellFunction()); 438 } 439 440 @Override 441 public Set<R> rowKeySet() { 442 return fromTable.rowKeySet(); 443 } 444 445 @Override 446 public Set<C> columnKeySet() { 447 return fromTable.columnKeySet(); 448 } 449 450 @Override 451 Collection<V2> createValues() { 452 return Collections2.transform(fromTable.values(), function); 453 } 454 455 @Override 456 public Map<R, Map<C, V2>> rowMap() { 457 Function<Map<C, V1>, Map<C, V2>> rowFunction = 458 new Function<Map<C, V1>, Map<C, V2>>() { 459 @Override 460 public Map<C, V2> apply(Map<C, V1> row) { 461 return Maps.transformValues(row, function); 462 } 463 }; 464 return Maps.transformValues(fromTable.rowMap(), rowFunction); 465 } 466 467 @Override 468 public Map<C, Map<R, V2>> columnMap() { 469 Function<Map<R, V1>, Map<R, V2>> columnFunction = 470 new Function<Map<R, V1>, Map<R, V2>>() { 471 @Override 472 public Map<R, V2> apply(Map<R, V1> column) { 473 return Maps.transformValues(column, function); 474 } 475 }; 476 return Maps.transformValues(fromTable.columnMap(), columnFunction); 477 } 478 } 479 480 /** 481 * Returns an unmodifiable view of the specified table. This method allows modules to provide 482 * users with "read-only" access to internal tables. Query operations on the returned table "read 483 * through" to the specified table, and attempts to modify the returned table, whether direct or 484 * via its collection views, result in an {@code UnsupportedOperationException}. 485 * 486 * <p>The returned table will be serializable if the specified table is serializable. 487 * 488 * <p>Consider using an {@link ImmutableTable}, which is guaranteed never to change. 489 * 490 * @since 11.0 491 */ 492 public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 493 Table<R, C, V> unmodifiableTable(Table<? extends R, ? extends C, ? extends V> table) { 494 return new UnmodifiableTable<>(table); 495 } 496 497 private static class UnmodifiableTable< 498 R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 499 extends ForwardingTable<R, C, V> implements Serializable { 500 final Table<? extends R, ? extends C, ? extends V> delegate; 501 502 UnmodifiableTable(Table<? extends R, ? extends C, ? extends V> delegate) { 503 this.delegate = checkNotNull(delegate); 504 } 505 506 @SuppressWarnings("unchecked") // safe, covariant cast 507 @Override 508 protected Table<R, C, V> delegate() { 509 return (Table<R, C, V>) delegate; 510 } 511 512 @Override 513 public Set<Cell<R, C, V>> cellSet() { 514 return Collections.unmodifiableSet(super.cellSet()); 515 } 516 517 @Override 518 public void clear() { 519 throw new UnsupportedOperationException(); 520 } 521 522 @Override 523 public Map<R, V> column(@ParametricNullness C columnKey) { 524 return Collections.unmodifiableMap(super.column(columnKey)); 525 } 526 527 @Override 528 public Set<C> columnKeySet() { 529 return Collections.unmodifiableSet(super.columnKeySet()); 530 } 531 532 @Override 533 public Map<C, Map<R, V>> columnMap() { 534 Function<Map<R, V>, Map<R, V>> wrapper = unmodifiableWrapper(); 535 return Collections.unmodifiableMap(Maps.transformValues(super.columnMap(), wrapper)); 536 } 537 538 @Override 539 @CheckForNull 540 public V put( 541 @ParametricNullness R rowKey, 542 @ParametricNullness C columnKey, 543 @ParametricNullness V value) { 544 throw new UnsupportedOperationException(); 545 } 546 547 @Override 548 public void putAll(Table<? extends R, ? extends C, ? extends V> table) { 549 throw new UnsupportedOperationException(); 550 } 551 552 @Override 553 @CheckForNull 554 public V remove(@CheckForNull Object rowKey, @CheckForNull Object columnKey) { 555 throw new UnsupportedOperationException(); 556 } 557 558 @Override 559 public Map<C, V> row(@ParametricNullness R rowKey) { 560 return Collections.unmodifiableMap(super.row(rowKey)); 561 } 562 563 @Override 564 public Set<R> rowKeySet() { 565 return Collections.unmodifiableSet(super.rowKeySet()); 566 } 567 568 @Override 569 public Map<R, Map<C, V>> rowMap() { 570 Function<Map<C, V>, Map<C, V>> wrapper = unmodifiableWrapper(); 571 return Collections.unmodifiableMap(Maps.transformValues(super.rowMap(), wrapper)); 572 } 573 574 @Override 575 public Collection<V> values() { 576 return Collections.unmodifiableCollection(super.values()); 577 } 578 579 private static final long serialVersionUID = 0; 580 } 581 582 /** 583 * Returns an unmodifiable view of the specified row-sorted table. This method allows modules to 584 * provide users with "read-only" access to internal tables. Query operations on the returned 585 * table "read through" to the specified table, and attempts to modify the returned table, whether 586 * direct or via its collection views, result in an {@code UnsupportedOperationException}. 587 * 588 * <p>The returned table will be serializable if the specified table is serializable. 589 * 590 * @param table the row-sorted table for which an unmodifiable view is to be returned 591 * @return an unmodifiable view of the specified table 592 * @since 11.0 593 */ 594 public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 595 RowSortedTable<R, C, V> unmodifiableRowSortedTable( 596 RowSortedTable<R, ? extends C, ? extends V> table) { 597 /* 598 * It's not ? extends R, because it's technically not covariant in R. Specifically, 599 * table.rowMap().comparator() could return a comparator that only works for the ? extends R. 600 * Collections.unmodifiableSortedMap makes the same distinction. 601 */ 602 return new UnmodifiableRowSortedMap<>(table); 603 } 604 605 static final class UnmodifiableRowSortedMap< 606 R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 607 extends UnmodifiableTable<R, C, V> implements RowSortedTable<R, C, V> { 608 609 public UnmodifiableRowSortedMap(RowSortedTable<R, ? extends C, ? extends V> delegate) { 610 super(delegate); 611 } 612 613 @Override 614 protected RowSortedTable<R, C, V> delegate() { 615 return (RowSortedTable<R, C, V>) super.delegate(); 616 } 617 618 @Override 619 public SortedMap<R, Map<C, V>> rowMap() { 620 Function<Map<C, V>, Map<C, V>> wrapper = unmodifiableWrapper(); 621 return Collections.unmodifiableSortedMap(Maps.transformValues(delegate().rowMap(), wrapper)); 622 } 623 624 @Override 625 public SortedSet<R> rowKeySet() { 626 return Collections.unmodifiableSortedSet(delegate().rowKeySet()); 627 } 628 629 private static final long serialVersionUID = 0; 630 } 631 632 @SuppressWarnings("unchecked") 633 private static <K extends @Nullable Object, V extends @Nullable Object> 634 Function<Map<K, V>, Map<K, V>> unmodifiableWrapper() { 635 return (Function) UNMODIFIABLE_WRAPPER; 636 } 637 638 private static final Function<? extends Map<?, ?>, ? extends Map<?, ?>> UNMODIFIABLE_WRAPPER = 639 new Function<Map<Object, Object>, Map<Object, Object>>() { 640 @Override 641 public Map<Object, Object> apply(Map<Object, Object> input) { 642 return Collections.unmodifiableMap(input); 643 } 644 }; 645 646 /** 647 * Returns a synchronized (thread-safe) table backed by the specified table. In order to guarantee 648 * serial access, it is critical that <b>all</b> access to the backing table is accomplished 649 * through the returned table. 650 * 651 * <p>It is imperative that the user manually synchronize on the returned table when accessing any 652 * of its collection views: 653 * 654 * <pre>{@code 655 * Table<R, C, V> table = Tables.synchronizedTable(HashBasedTable.<R, C, V>create()); 656 * ... 657 * Map<C, V> row = table.row(rowKey); // Needn't be in synchronized block 658 * ... 659 * synchronized (table) { // Synchronizing on table, not row! 660 * Iterator<Entry<C, V>> i = row.entrySet().iterator(); // Must be in synchronized block 661 * while (i.hasNext()) { 662 * foo(i.next()); 663 * } 664 * } 665 * }</pre> 666 * 667 * <p>Failure to follow this advice may result in non-deterministic behavior. 668 * 669 * <p>The returned table will be serializable if the specified table is serializable. 670 * 671 * @param table the table to be wrapped in a synchronized view 672 * @return a synchronized view of the specified table 673 * @since 22.0 674 */ 675 public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object> 676 Table<R, C, V> synchronizedTable(Table<R, C, V> table) { 677 return Synchronized.table(table, null); 678 } 679 680 static boolean equalsImpl(Table<?, ?, ?> table, @CheckForNull Object obj) { 681 if (obj == table) { 682 return true; 683 } else if (obj instanceof Table) { 684 Table<?, ?, ?> that = (Table<?, ?, ?>) obj; 685 return table.cellSet().equals(that.cellSet()); 686 } else { 687 return false; 688 } 689 } 690}