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