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