common/collect/Tables.java

/*
 * Copyright (C) 2008 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import com.google.common.base.Objects;
import com.google.common.base.Supplier;
import com.google.common.collect.Collections2.TransformedCollection;
import com.google.common.collect.Table.Cell;

import java.io.Serializable;
import java.util.Collection;
import java.util.Collections;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;

import javax.annotation.Nullable;

/**
 * Provides static methods that involve a {@code Table}.
 *
 * @author Jared Levy
 * @author Louis Wasserman
 * @since 7.0
 */
@GwtCompatible
@Beta
public final class Tables {
  private Tables() {}

  /**
   * Returns an immutable cell with the specified row key, column key, and
   * value.
   *
   * <p>The returned cell is serializable.
   *
   * @param rowKey the row key to be associated with the returned cell
   * @param columnKey the column key to be associated with the returned cell
   * @param value the value to be associated with the returned cell
   */
  public static <R, C, V> Cell<R, C, V> immutableCell(
      @Nullable R rowKey, @Nullable C columnKey, @Nullable V value) {
    return new ImmutableCell<R, C, V>(rowKey, columnKey, value);
  }

  static final class ImmutableCell<R, C, V>
      extends AbstractCell<R, C, V> implements Serializable {
    private final R rowKey;
    private final C columnKey;
    private final V value;

    ImmutableCell(
        @Nullable R rowKey, @Nullable C columnKey, @Nullable V value) {
      this.rowKey = rowKey;
      this.columnKey = columnKey;
      this.value = value;
    }

    @Override
    public R getRowKey() {
      return rowKey;
    }
    @Override
    public C getColumnKey() {
      return columnKey;
    }
    @Override
    public V getValue() {
      return value;
    }

    private static final long serialVersionUID = 0;
  }

  abstract static class AbstractCell<R, C, V> implements Cell<R, C, V> {
    // needed for serialization
    AbstractCell() {}

    @Override public boolean equals(Object obj) {
      if (obj == this) {
        return true;
      }
      if (obj instanceof Cell) {
        Cell<?, ?, ?> other = (Cell<?, ?, ?>) obj;
        return Objects.equal(getRowKey(), other.getRowKey())
            && Objects.equal(getColumnKey(), other.getColumnKey())
            && Objects.equal(getValue(), other.getValue());
      }
      return false;
    }

    @Override public int hashCode() {
      return Objects.hashCode(getRowKey(), getColumnKey(), getValue());
    }

    @Override public String toString() {
      return "(" + getRowKey() + "," + getColumnKey() + ")=" + getValue();
    }
  }

  /**
   * Creates a transposed view of a given table that flips its row and column
   * keys. In other words, calling {@code get(columnKey, rowKey)} on the
   * generated table always returns the same value as calling {@code
   * get(rowKey, columnKey)} on the original table. Updating the original table
   * changes the contents of the transposed table and vice versa.
   *
   * <p>The returned table supports update operations as long as the input table
   * supports the analogous operation with swapped rows and columns. For
   * example, in a {@link HashBasedTable} instance, {@code
   * rowKeySet().iterator()} supports {@code remove()} but {@code
   * columnKeySet().iterator()} doesn't. With a transposed {@link
   * HashBasedTable}, it's the other way around.
   */
  public static <R, C, V> Table<C, R, V> transpose(Table<R, C, V> table) {
    return (table instanceof TransposeTable)
        ? ((TransposeTable<R, C, V>) table).original
        : new TransposeTable<C, R, V>(table);
  }

  private static class TransposeTable<C, R, V> implements Table<C, R, V> {
    final Table<R, C, V> original;

    TransposeTable(Table<R, C, V> original) {
      this.original = checkNotNull(original);
    }

    @Override
    public void clear() {
      original.clear();
    }

    @Override
    public Map<C, V> column(R columnKey) {
      return original.row(columnKey);
    }

    @Override
    public Set<R> columnKeySet() {
      return original.rowKeySet();
    }

    @Override
    public Map<R, Map<C, V>> columnMap() {
      return original.rowMap();
    }

    @Override
    public boolean contains(
        @Nullable Object rowKey, @Nullable Object columnKey) {
      return original.contains(columnKey, rowKey);
    }

    @Override
    public boolean containsColumn(@Nullable Object columnKey) {
      return original.containsRow(columnKey);
    }

    @Override
    public boolean containsRow(@Nullable Object rowKey) {
      return original.containsColumn(rowKey);
    }

    @Override
    public boolean containsValue(@Nullable Object value) {
      return original.containsValue(value);
    }

    @Override
    public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
      return original.get(columnKey, rowKey);
    }

    @Override
    public boolean isEmpty() {
      return original.isEmpty();
    }

    @Override
    public V put(C rowKey, R columnKey, V value) {
      return original.put(columnKey, rowKey, value);
    }

    @Override
    public void putAll(Table<? extends C, ? extends R, ? extends V> table) {
      original.putAll(transpose(table));
    }

    @Override
    public V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
      return original.remove(columnKey, rowKey);
    }

    @Override
    public Map<R, V> row(C rowKey) {
      return original.column(rowKey);
    }

    @Override
    public Set<C> rowKeySet() {
      return original.columnKeySet();
    }

    @Override
    public Map<C, Map<R, V>> rowMap() {
      return original.columnMap();
    }

    @Override
    public int size() {
      return original.size();
    }

    @Override
    public Collection<V> values() {
      return original.values();
    }

    @Override public boolean equals(@Nullable Object obj) {
      if (obj == this) {
        return true;
      }
      if (obj instanceof Table) {
        Table<?, ?, ?> other = (Table<?, ?, ?>) obj;
        return cellSet().equals(other.cellSet());
      }
      return false;
    }

    @Override public int hashCode() {
      return cellSet().hashCode();
    }

    @Override public String toString() {
      return rowMap().toString();
    }

    // Will cast TRANSPOSE_CELL to a type that always succeeds
    private static final Function<Cell<?, ?, ?>, Cell<?, ?, ?>> TRANSPOSE_CELL =
        new Function<Cell<?, ?, ?>, Cell<?, ?, ?>>() {
          @Override
          public Cell<?, ?, ?> apply(Cell<?, ?, ?> cell) {
            return immutableCell(
                cell.getColumnKey(), cell.getRowKey(), cell.getValue());
          }
        };

    CellSet cellSet;

    @Override
    public Set<Cell<C, R, V>> cellSet() {
      CellSet result = cellSet;
      return (result == null) ? cellSet = new CellSet() : result;
    }

    class CellSet extends TransformedCollection<Cell<R, C, V>, Cell<C, R, V>>
        implements Set<Cell<C, R, V>> {
      // Casting TRANSPOSE_CELL to a type that always succeeds
      @SuppressWarnings("unchecked")
      CellSet() {
        super(original.cellSet(), (Function) TRANSPOSE_CELL);
      }

      @Override public boolean equals(Object obj) {
        if (obj == this) {
          return true;
        }
        if (!(obj instanceof Set)) {
          return false;
        }
        Set<?> os = (Set<?>) obj;
        if (os.size() != size()) {
          return false;
        }
        return containsAll(os);
      }

      @Override public int hashCode() {
        return Sets.hashCodeImpl(this);
      }

      @Override public boolean contains(Object obj) {
        if (obj instanceof Cell) {
          Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
          return original.cellSet().contains(immutableCell(
              cell.getColumnKey(), cell.getRowKey(), cell.getValue()));
        }
        return false;
      }

      @Override public boolean remove(Object obj) {
        if (obj instanceof Cell) {
          Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
          return original.cellSet().remove(immutableCell(
              cell.getColumnKey(), cell.getRowKey(), cell.getValue()));
        }
        return false;
      }
    }
  }

  /**
   * Creates a table that uses the specified backing map and factory. It can
   * generate a table based on arbitrary {@link Map} classes.
   *
   * <p>The {@code factory}-generated and {@code backingMap} classes determine
   * the table iteration order. However, the table's {@code row()} method
   * returns instances of a different class than {@code factory.get()} does.
   *
   * <p>Call this method only when the simpler factory methods in classes like
   * {@link HashBasedTable} and {@link TreeBasedTable} won't suffice.
   *
   * <p>The views returned by the {@code Table} methods {@link Table#column},
   * {@link Table#columnKeySet}, and {@link Table#columnMap} have iterators that
   * don't support {@code remove()}. Otherwise, all optional operations are
   * supported. Null row keys, columns keys, and values are not supported.
   *
   * <p>Lookups by row key are often faster than lookups by column key, because
   * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like
   * {@code column(columnKey).get(rowKey)} still runs quickly, since the row key
   * is provided. However, {@code column(columnKey).size()} takes longer, since
   * an iteration across all row keys occurs.
   *
   * <p>Note that this implementation is not synchronized. If multiple threads
   * access this table concurrently and one of the threads modifies the table,
   * it must be synchronized externally.
   *
   * <p>The table is serializable if {@code backingMap}, {@code factory}, the
   * maps generated by {@code factory}, and the table contents are all
   * serializable.
   *
   * <p>Note: the table assumes complete ownership over of {@code backingMap}
   * and the maps returned by {@code factory}. Those objects should not be
   * manually updated and they should not use soft, weak, or phantom references.
   *
   * @param backingMap place to store the mapping from each row key to its
   *     corresponding column key / value map
   * @param factory supplier of new, empty maps that will each hold all column
   *     key / value mappings for a given row key
   * @throws IllegalArgumentException if {@code backingMap} is not empty
   * @since 10.0
   */
  public static <R, C, V> Table<R, C, V> newCustomTable(
      Map<R, Map<C, V>> backingMap, Supplier<? extends Map<C, V>> factory) {
    checkArgument(backingMap.isEmpty());
    checkNotNull(factory);
    // TODO(jlevy): Wrap factory to validate that the supplied maps are empty?
    return new StandardTable<R, C, V>(backingMap, factory);
  }

  /**
   * Returns a view of a table where each value is transformed by a function.
   * All other properties of the table, such as iteration order, are left
   * intact.
   *
   * <p>Changes in the underlying table are reflected in this view. Conversely,
   * this view supports removal operations, and these are reflected in the
   * underlying table.
   *
   * <p>It's acceptable for the underlying table to contain null keys, and even
   * null values provided that the function is capable of accepting null input.
   * The transformed table might contain null values, if the function sometimes
   * gives a null result.
   *
   * <p>The returned table is not thread-safe or serializable, even if the
   * underlying table is.
   *
   * <p>The function is applied lazily, invoked when needed. This is necessary
   * for the returned table to be a view, but it means that the function will be
   * applied many times for bulk operations like {@link Table#containsValue} and
   * {@code Table.toString()}. For this to perform well, {@code function} should
   * be fast. To avoid lazy evaluation when the returned table doesn't need to
   * be a view, copy the returned table into a new table of your choosing.
   *
   * @since 10.0
   */
  public static <R, C, V1, V2> Table<R, C, V2> transformValues(
      Table<R, C, V1> fromTable, Function<? super V1, V2> function) {
    return new TransformedTable<R, C, V1, V2>(fromTable, function);
  }

  private static class TransformedTable<R, C, V1, V2>
      implements Table<R, C, V2> {
    final Table<R, C, V1> fromTable;
    final Function<? super V1, V2> function;

    TransformedTable(
        Table<R, C, V1> fromTable, Function<? super V1, V2> function) {
      this.fromTable = checkNotNull(fromTable);
      this.function = checkNotNull(function);
    }

    @Override public boolean contains(Object rowKey, Object columnKey) {
      return fromTable.contains(rowKey, columnKey);
    }

    @Override public boolean containsRow(Object rowKey) {
      return fromTable.containsRow(rowKey);
    }

    @Override public boolean containsColumn(Object columnKey) {
      return fromTable.containsColumn(columnKey);
    }

    @Override public boolean containsValue(Object value) {
      return values().contains(value);
    }

    @Override public V2 get(Object rowKey, Object columnKey) {
      // The function is passed a null input only when the table contains a null
      // value.
      return contains(rowKey, columnKey)
          ? function.apply(fromTable.get(rowKey, columnKey)) : null;
    }

    @Override public boolean isEmpty() {
      return fromTable.isEmpty();
    }

    @Override public int size() {
      return fromTable.size();
    }

    @Override public void clear() {
      fromTable.clear();
    }

    @Override public V2 put(R rowKey, C columnKey, V2 value) {
      throw new UnsupportedOperationException();
    }

    @Override public void putAll(
        Table<? extends R, ? extends C, ? extends V2> table) {
      throw new UnsupportedOperationException();
    }

    @Override public V2 remove(Object rowKey, Object columnKey) {
      return contains(rowKey, columnKey)
          ? function.apply(fromTable.remove(rowKey, columnKey)) : null;
    }

    @Override public Map<C, V2> row(R rowKey) {
      return Maps.transformValues(fromTable.row(rowKey), function);
    }

    @Override public Map<R, V2> column(C columnKey) {
      return Maps.transformValues(fromTable.column(columnKey), function);
    }

    Function<Cell<R, C, V1>, Cell<R, C, V2>> cellFunction() {
      return new Function<Cell<R, C, V1>, Cell<R, C, V2>>() {
        @Override public Cell<R, C, V2> apply(Cell<R, C, V1> cell) {
          return immutableCell(
              cell.getRowKey(), cell.getColumnKey(),
              function.apply(cell.getValue()));
        }
      };
    }

    class CellSet extends TransformedCollection<Cell<R, C, V1>, Cell<R, C, V2>>
        implements Set<Cell<R, C, V2>> {
      CellSet() {
        super(fromTable.cellSet(), cellFunction());
      }
      @Override public boolean equals(Object obj) {
        return Sets.equalsImpl(this, obj);
      }
      @Override public int hashCode() {
        return Sets.hashCodeImpl(this);
      }
      @Override public boolean contains(Object obj) {
        if (obj instanceof Cell) {
          Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
          if (!Objects.equal(
              cell.getValue(), get(cell.getRowKey(), cell.getColumnKey()))) {
            return false;
          }
          return cell.getValue() != null
              || fromTable.contains(cell.getRowKey(), cell.getColumnKey());
        }
        return false;
      }
      @Override public boolean remove(Object obj) {
        if (contains(obj)) {
          Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
          fromTable.remove(cell.getRowKey(), cell.getColumnKey());
          return true;
        }
        return false;
      }
    }

    CellSet cellSet;

    @Override public Set<Cell<R, C, V2>> cellSet() {
      return (cellSet == null) ? cellSet = new CellSet() : cellSet;
    }

    @Override public Set<R> rowKeySet() {
      return fromTable.rowKeySet();
    }

    @Override public Set<C> columnKeySet() {
      return fromTable.columnKeySet();
    }

    Collection<V2> values;

    @Override public Collection<V2> values() {
      return (values == null)
          ? values = Collections2.transform(fromTable.values(), function)
          : values;
    }

    Map<R, Map<C, V2>> createRowMap() {
      Function<Map<C, V1>, Map<C, V2>> rowFunction =
          new Function<Map<C, V1>, Map<C, V2>>() {
            @Override public Map<C, V2> apply(Map<C, V1> row) {
              return Maps.transformValues(row, function);
            }
          };
      return Maps.transformValues(fromTable.rowMap(), rowFunction);
    }

    Map<R, Map<C, V2>> rowMap;

    @Override public Map<R, Map<C, V2>> rowMap() {
      return (rowMap == null) ? rowMap = createRowMap() : rowMap;
    }

    Map<C, Map<R, V2>> createColumnMap() {
      Function<Map<R, V1>, Map<R, V2>> columnFunction =
          new Function<Map<R, V1>, Map<R, V2>>() {
            @Override public Map<R, V2> apply(Map<R, V1> column) {
              return Maps.transformValues(column, function);
            }
          };
      return Maps.transformValues(fromTable.columnMap(), columnFunction);
    }

    Map<C, Map<R, V2>> columnMap;

    @Override public Map<C, Map<R, V2>> columnMap() {
      return (columnMap == null) ? columnMap = createColumnMap() : columnMap;
    }

    @Override public boolean equals(@Nullable Object obj) {
      if (obj == this) {
        return true;
      }
      if (obj instanceof Table) {
        Table<?, ?, ?> other = (Table<?, ?, ?>) obj;
        return cellSet().equals(other.cellSet());
      }
      return false;
    }

    @Override public int hashCode() {
      return cellSet().hashCode();
    }

    @Override public String toString() {
      return rowMap().toString();
    }
  }

  /**
   * Returns an unmodifiable view of the specified table. This method allows modules to provide
   * users with "read-only" access to internal tables. Query operations on the returned table
   * "read through" to the specified table, and attempts to modify the returned table, whether
   * direct or via its collection views, result in an {@code UnsupportedOperationException}.
   *
   * <p>The returned table will be serializable if the specified table is serializable.
   *
   * <p>Consider using an {@link ImmutableTable}, which is guaranteed never to change.
   *
   * @param table
   *          the table for which an unmodifiable view is to be returned
   * @return an unmodifiable view of the specified table
   * @since 11.0
   */
  public static <R, C, V> Table<R, C, V> unmodifiableTable(
      Table<? extends R, ? extends C, ? extends V> table) {
    return new UnmodifiableTable<R, C, V>(table);
  }

  private static class UnmodifiableTable<R, C, V>
      extends ForwardingTable<R, C, V> implements Serializable {
    final Table<? extends R, ? extends C, ? extends V> delegate;

    UnmodifiableTable(Table<? extends R, ? extends C, ? extends V> delegate) {
      this.delegate = checkNotNull(delegate);
    }

    @SuppressWarnings("unchecked") // safe, covariant cast
    @Override
    protected Table<R, C, V> delegate() {
      return (Table<R, C, V>) delegate;
    }

    @Override
    public Set<Cell<R, C, V>> cellSet() {
      return Collections.unmodifiableSet(super.cellSet());
    }

    @Override
    public void clear() {
      throw new UnsupportedOperationException();
    }

    @Override
    public Map<R, V> column(@Nullable C columnKey) {
      return Collections.unmodifiableMap(super.column(columnKey));
    }

    @Override
    public Set<C> columnKeySet() {
      return Collections.unmodifiableSet(super.columnKeySet());
    }

    @Override
    public Map<C, Map<R, V>> columnMap() {
      Function<Map<R, V>, Map<R, V>> wrapper = unmodifiableWrapper();
      return Collections.unmodifiableMap(Maps.transformValues(super.columnMap(), wrapper));
    }

    @Override
    public V put(@Nullable R rowKey, @Nullable C columnKey, @Nullable V value) {
      throw new UnsupportedOperationException();
    }

    @Override
    public void putAll(Table<? extends R, ? extends C, ? extends V> table) {
      throw new UnsupportedOperationException();
    }

    @Override
    public V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
      throw new UnsupportedOperationException();
    }

    @Override
    public Map<C, V> row(@Nullable R rowKey) {
      return Collections.unmodifiableMap(super.row(rowKey));
    }

    @Override
    public Set<R> rowKeySet() {
      return Collections.unmodifiableSet(super.rowKeySet());
    }

    @Override
    public Map<R, Map<C, V>> rowMap() {
      Function<Map<C, V>, Map<C, V>> wrapper = unmodifiableWrapper();
      return Collections.unmodifiableMap(Maps.transformValues(super.rowMap(), wrapper));
    }

    @Override
    public Collection<V> values() {
      return Collections.unmodifiableCollection(super.values());
    }

    private static final long serialVersionUID = 0;
  }

  /**
   * Returns an unmodifiable view of the specified row-sorted table. This method allows modules to
   * provide users with "read-only" access to internal tables. Query operations on the returned
   * table "read through" to the specified table, and attemps to modify the returned table, whether
   * direct or via its collection views, result in an {@code UnsupportedOperationException}.
   *
   * <p>The returned table will be serializable if the specified table is serializable.
   *
   * @param table the row-sorted table for which an unmodifiable view is to be returned
   * @return an unmodifiable view of the specified table
   * @since 11.0
   */
  public static <R, C, V> RowSortedTable<R, C, V> unmodifiableRowSortedTable(
      RowSortedTable<R, ? extends C, ? extends V> table) {
    /*
     * It's not ? extends R, because it's technically not covariant in R. Specifically,
     * table.rowMap().comparator() could return a comparator that only works for the ? extends R.
     * Collections.unmodifiableSortedMap makes the same distinction.
     */
    return new UnmodifiableRowSortedMap<R, C, V>(table);
  }

  static final class UnmodifiableRowSortedMap<R, C, V> extends UnmodifiableTable<R, C, V>
      implements RowSortedTable<R, C, V> {

    public UnmodifiableRowSortedMap(RowSortedTable<R, ? extends C, ? extends V> delegate) {
      super(delegate);
    }

    @Override
    protected RowSortedTable<R, C, V> delegate() {
      return (RowSortedTable<R, C, V>) super.delegate();
    }

    @Override
    public SortedMap<R, Map<C, V>> rowMap() {
      Function<Map<C, V>, Map<C, V>> wrapper = unmodifiableWrapper();
      return Collections.unmodifiableSortedMap(Maps.transformValues(delegate().rowMap(), wrapper));
    }

    @Override
    public SortedSet<R> rowKeySet() {
      return Collections.unmodifiableSortedSet(delegate().rowKeySet());
    }

    private static final long serialVersionUID = 0;
  }

  @SuppressWarnings("unchecked")
  private static <K, V> Function<Map<K, V>, Map<K, V>> unmodifiableWrapper() {
    return (Function) UNMODIFIABLE_WRAPPER;
  }

  private static final Function<? extends Map<?, ?>, ? extends Map<?, ?>> UNMODIFIABLE_WRAPPER =
      new Function<Map<Object, Object>, Map<Object, Object>>() {
        @Override
        public Map<Object, Object> apply(Map<Object, Object> input) {
          return Collections.unmodifiableMap(input);
        }
      };
}