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}