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