001/*
002 * Copyright (C) 2009 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.checkNotNull;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.annotations.GwtIncompatible;
023import com.google.common.base.MoreObjects;
024import com.google.errorprone.annotations.CanIgnoreReturnValue;
025import com.google.errorprone.annotations.DoNotCall;
026import com.google.errorprone.annotations.DoNotMock;
027import java.io.InvalidObjectException;
028import java.io.ObjectInputStream;
029import java.io.Serializable;
030import java.util.Comparator;
031import java.util.Iterator;
032import java.util.List;
033import java.util.Map;
034import java.util.Spliterator;
035import java.util.function.BinaryOperator;
036import java.util.function.Function;
037import java.util.stream.Collector;
038import javax.annotation.CheckForNull;
039import org.checkerframework.checker.nullness.qual.Nullable;
040
041/**
042 * A {@link Table} whose contents will never change, with many other important properties detailed
043 * at {@link ImmutableCollection}.
044 *
045 * <p>See the Guava User Guide article on <a href=
046 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
047 *
048 * @author Gregory Kick
049 * @since 11.0
050 */
051@GwtCompatible
052@ElementTypesAreNonnullByDefault
053public abstract class ImmutableTable<R, C, V> extends AbstractTable<R, C, V>
054    implements Serializable {
055
056  /**
057   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableTable}. Each
058   * input element is mapped to one cell in the returned table, with the rows, columns, and values
059   * generated by applying the specified functions.
060   *
061   * <p>The returned {@code Collector} will throw a {@code NullPointerException} at collection time
062   * if the row, column, or value functions return null on any input.
063   *
064   * @since 21.0
065   */
066  public static <T extends @Nullable Object, R, C, V>
067      Collector<T, ?, ImmutableTable<R, C, V>> toImmutableTable(
068          Function<? super T, ? extends R> rowFunction,
069          Function<? super T, ? extends C> columnFunction,
070          Function<? super T, ? extends V> valueFunction) {
071    return TableCollectors.toImmutableTable(rowFunction, columnFunction, valueFunction);
072  }
073
074  /**
075   * Returns a {@code Collector} that accumulates elements into an {@code ImmutableTable}. Each
076   * input element is mapped to one cell in the returned table, with the rows, columns, and values
077   * generated by applying the specified functions. If multiple inputs are mapped to the same row
078   * and column pair, they will be combined with the specified merging function in encounter order.
079   *
080   * <p>The returned {@code Collector} will throw a {@code NullPointerException} at collection time
081   * if the row, column, value, or merging functions return null on any input.
082   *
083   * @since 21.0
084   */
085  public static <T extends @Nullable Object, R, C, V>
086      Collector<T, ?, ImmutableTable<R, C, V>> toImmutableTable(
087          Function<? super T, ? extends R> rowFunction,
088          Function<? super T, ? extends C> columnFunction,
089          Function<? super T, ? extends V> valueFunction,
090          BinaryOperator<V> mergeFunction) {
091    return TableCollectors.toImmutableTable(
092        rowFunction, columnFunction, valueFunction, mergeFunction);
093  }
094
095  /**
096   * Returns an empty immutable table.
097   *
098   * <p><b>Performance note:</b> the instance returned is a singleton.
099   */
100  @SuppressWarnings("unchecked")
101  public static <R, C, V> ImmutableTable<R, C, V> of() {
102    return (ImmutableTable<R, C, V>) SparseImmutableTable.EMPTY;
103  }
104
105  /** Returns an immutable table containing a single cell. */
106  public static <R, C, V> ImmutableTable<R, C, V> of(R rowKey, C columnKey, V value) {
107    return new SingletonImmutableTable<>(rowKey, columnKey, value);
108  }
109
110  /**
111   * Returns an immutable copy of the provided table.
112   *
113   * <p>The {@link Table#cellSet()} iteration order of the provided table determines the iteration
114   * ordering of all views in the returned table. Note that some views of the original table and the
115   * copied table may have different iteration orders. For more control over the ordering, create a
116   * {@link Builder} and call {@link Builder#orderRowsBy}, {@link Builder#orderColumnsBy}, and
117   * {@link Builder#putAll}
118   *
119   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
120   * safe to do so. The exact circumstances under which a copy will or will not be performed are
121   * undocumented and subject to change.
122   */
123  public static <R, C, V> ImmutableTable<R, C, V> copyOf(
124      Table<? extends R, ? extends C, ? extends V> table) {
125    if (table instanceof ImmutableTable) {
126      @SuppressWarnings("unchecked")
127      ImmutableTable<R, C, V> parameterizedTable = (ImmutableTable<R, C, V>) table;
128      return parameterizedTable;
129    } else {
130      return copyOf(table.cellSet());
131    }
132  }
133
134  static <R, C, V> ImmutableTable<R, C, V> copyOf(
135      Iterable<? extends Cell<? extends R, ? extends C, ? extends V>> cells) {
136    ImmutableTable.Builder<R, C, V> builder = ImmutableTable.builder();
137    for (Cell<? extends R, ? extends C, ? extends V> cell : cells) {
138      builder.put(cell);
139    }
140    return builder.build();
141  }
142
143  /**
144   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
145   * Builder#Builder() ImmutableTable.Builder()} constructor.
146   */
147  public static <R, C, V> Builder<R, C, V> builder() {
148    return new Builder<>();
149  }
150
151  /**
152   * Verifies that {@code rowKey}, {@code columnKey} and {@code value} are non-null, and returns a
153   * new entry with those values.
154   */
155  static <R, C, V> Cell<R, C, V> cellOf(R rowKey, C columnKey, V value) {
156    return Tables.immutableCell(
157        checkNotNull(rowKey, "rowKey"),
158        checkNotNull(columnKey, "columnKey"),
159        checkNotNull(value, "value"));
160  }
161
162  /**
163   * A builder for creating immutable table instances, especially {@code public static final} tables
164   * ("constant tables"). Example:
165   *
166   * <pre>{@code
167   * static final ImmutableTable<Integer, Character, String> SPREADSHEET =
168   *     new ImmutableTable.Builder<Integer, Character, String>()
169   *         .put(1, 'A', "foo")
170   *         .put(1, 'B', "bar")
171   *         .put(2, 'A', "baz")
172   *         .buildOrThrow();
173   * }</pre>
174   *
175   * <p>By default, the order in which cells are added to the builder determines the iteration
176   * ordering of all views in the returned table, with {@link #putAll} following the {@link
177   * Table#cellSet()} iteration order. However, if {@link #orderRowsBy} or {@link #orderColumnsBy}
178   * is called, the views are sorted by the supplied comparators.
179   *
180   * <p>For empty or single-cell immutable tables, {@link #of()} and {@link #of(Object, Object,
181   * Object)} are even more convenient.
182   *
183   * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to
184   * build multiple tables in series. Each table is a superset of the tables created before it.
185   *
186   * @since 11.0
187   */
188  @DoNotMock
189  public static final class Builder<R, C, V> {
190    private final List<Cell<R, C, V>> cells = Lists.newArrayList();
191    @CheckForNull private Comparator<? super R> rowComparator;
192    @CheckForNull private Comparator<? super C> columnComparator;
193
194    /**
195     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
196     * ImmutableTable#builder}.
197     */
198    public Builder() {}
199
200    /** Specifies the ordering of the generated table's rows. */
201    @CanIgnoreReturnValue
202    public Builder<R, C, V> orderRowsBy(Comparator<? super R> rowComparator) {
203      this.rowComparator = checkNotNull(rowComparator, "rowComparator");
204      return this;
205    }
206
207    /** Specifies the ordering of the generated table's columns. */
208    @CanIgnoreReturnValue
209    public Builder<R, C, V> orderColumnsBy(Comparator<? super C> columnComparator) {
210      this.columnComparator = checkNotNull(columnComparator, "columnComparator");
211      return this;
212    }
213
214    /**
215     * Associates the ({@code rowKey}, {@code columnKey}) pair with {@code value} in the built
216     * table. Duplicate key pairs are not allowed and will cause {@link #build} to fail.
217     */
218    @CanIgnoreReturnValue
219    public Builder<R, C, V> put(R rowKey, C columnKey, V value) {
220      cells.add(cellOf(rowKey, columnKey, value));
221      return this;
222    }
223
224    /**
225     * Adds the given {@code cell} to the table, making it immutable if necessary. Duplicate key
226     * pairs are not allowed and will cause {@link #build} to fail.
227     */
228    @CanIgnoreReturnValue
229    public Builder<R, C, V> put(Cell<? extends R, ? extends C, ? extends V> cell) {
230      if (cell instanceof Tables.ImmutableCell) {
231        checkNotNull(cell.getRowKey(), "row");
232        checkNotNull(cell.getColumnKey(), "column");
233        checkNotNull(cell.getValue(), "value");
234        @SuppressWarnings("unchecked") // all supported methods are covariant
235        Cell<R, C, V> immutableCell = (Cell<R, C, V>) cell;
236        cells.add(immutableCell);
237      } else {
238        put(cell.getRowKey(), cell.getColumnKey(), cell.getValue());
239      }
240      return this;
241    }
242
243    /**
244     * Associates all of the given table's keys and values in the built table. Duplicate row key
245     * column key pairs are not allowed, and will cause {@link #build} to fail.
246     *
247     * @throws NullPointerException if any key or value in {@code table} is null
248     */
249    @CanIgnoreReturnValue
250    public Builder<R, C, V> putAll(Table<? extends R, ? extends C, ? extends V> table) {
251      for (Cell<? extends R, ? extends C, ? extends V> cell : table.cellSet()) {
252        put(cell);
253      }
254      return this;
255    }
256
257    @CanIgnoreReturnValue
258    Builder<R, C, V> combine(Builder<R, C, V> other) {
259      this.cells.addAll(other.cells);
260      return this;
261    }
262
263    /**
264     * Returns a newly-created immutable table.
265     *
266     * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method
267     * will throw an exception if there are duplicate key pairs. The {@code build()} method will
268     * soon be deprecated.
269     *
270     * @throws IllegalArgumentException if duplicate key pairs were added
271     */
272    public ImmutableTable<R, C, V> build() {
273      return buildOrThrow();
274    }
275
276    /**
277     * Returns a newly-created immutable table, or throws an exception if duplicate key pairs were
278     * added.
279     *
280     * @throws IllegalArgumentException if duplicate key pairs were added
281     * @since 31.0
282     */
283    public ImmutableTable<R, C, V> buildOrThrow() {
284      int size = cells.size();
285      switch (size) {
286        case 0:
287          return of();
288        case 1:
289          return new SingletonImmutableTable<>(Iterables.getOnlyElement(cells));
290        default:
291          return RegularImmutableTable.forCells(cells, rowComparator, columnComparator);
292      }
293    }
294  }
295
296  ImmutableTable() {}
297
298  @Override
299  public ImmutableSet<Cell<R, C, V>> cellSet() {
300    return (ImmutableSet<Cell<R, C, V>>) super.cellSet();
301  }
302
303  @Override
304  abstract ImmutableSet<Cell<R, C, V>> createCellSet();
305
306  @Override
307  final UnmodifiableIterator<Cell<R, C, V>> cellIterator() {
308    throw new AssertionError("should never be called");
309  }
310
311  @Override
312  final Spliterator<Cell<R, C, V>> cellSpliterator() {
313    throw new AssertionError("should never be called");
314  }
315
316  @Override
317  public ImmutableCollection<V> values() {
318    return (ImmutableCollection<V>) super.values();
319  }
320
321  @Override
322  abstract ImmutableCollection<V> createValues();
323
324  @Override
325  final Iterator<V> valuesIterator() {
326    throw new AssertionError("should never be called");
327  }
328
329  /**
330   * {@inheritDoc}
331   *
332   * @throws NullPointerException if {@code columnKey} is {@code null}
333   */
334  @Override
335  public ImmutableMap<R, V> column(C columnKey) {
336    checkNotNull(columnKey, "columnKey");
337    return MoreObjects.firstNonNull(
338        (ImmutableMap<R, V>) columnMap().get(columnKey), ImmutableMap.<R, V>of());
339  }
340
341  @Override
342  public ImmutableSet<C> columnKeySet() {
343    return columnMap().keySet();
344  }
345
346  /**
347   * {@inheritDoc}
348   *
349   * <p>The value {@code Map<R, V>} instances in the returned map are {@link ImmutableMap} instances
350   * as well.
351   */
352  @Override
353  public abstract ImmutableMap<C, Map<R, V>> columnMap();
354
355  /**
356   * {@inheritDoc}
357   *
358   * @throws NullPointerException if {@code rowKey} is {@code null}
359   */
360  @Override
361  public ImmutableMap<C, V> row(R rowKey) {
362    checkNotNull(rowKey, "rowKey");
363    return MoreObjects.firstNonNull(
364        (ImmutableMap<C, V>) rowMap().get(rowKey), ImmutableMap.<C, V>of());
365  }
366
367  @Override
368  public ImmutableSet<R> rowKeySet() {
369    return rowMap().keySet();
370  }
371
372  /**
373   * {@inheritDoc}
374   *
375   * <p>The value {@code Map<C, V>} instances in the returned map are {@link ImmutableMap} instances
376   * as well.
377   */
378  @Override
379  public abstract ImmutableMap<R, Map<C, V>> rowMap();
380
381  @Override
382  public boolean contains(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
383    return get(rowKey, columnKey) != null;
384  }
385
386  @Override
387  public boolean containsValue(@CheckForNull Object value) {
388    return values().contains(value);
389  }
390
391  /**
392   * Guaranteed to throw an exception and leave the table unmodified.
393   *
394   * @throws UnsupportedOperationException always
395   * @deprecated Unsupported operation.
396   */
397  @Deprecated
398  @Override
399  @DoNotCall("Always throws UnsupportedOperationException")
400  public final void clear() {
401    throw new UnsupportedOperationException();
402  }
403
404  /**
405   * Guaranteed to throw an exception and leave the table unmodified.
406   *
407   * @throws UnsupportedOperationException always
408   * @deprecated Unsupported operation.
409   */
410  @CanIgnoreReturnValue
411  @Deprecated
412  @Override
413  @DoNotCall("Always throws UnsupportedOperationException")
414  @CheckForNull
415  public final V put(R rowKey, C columnKey, V value) {
416    throw new UnsupportedOperationException();
417  }
418
419  /**
420   * Guaranteed to throw an exception and leave the table unmodified.
421   *
422   * @throws UnsupportedOperationException always
423   * @deprecated Unsupported operation.
424   */
425  @Deprecated
426  @Override
427  @DoNotCall("Always throws UnsupportedOperationException")
428  public final void putAll(Table<? extends R, ? extends C, ? extends V> table) {
429    throw new UnsupportedOperationException();
430  }
431
432  /**
433   * Guaranteed to throw an exception and leave the table unmodified.
434   *
435   * @throws UnsupportedOperationException always
436   * @deprecated Unsupported operation.
437   */
438  @CanIgnoreReturnValue
439  @Deprecated
440  @Override
441  @DoNotCall("Always throws UnsupportedOperationException")
442  @CheckForNull
443  public final V remove(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
444    throw new UnsupportedOperationException();
445  }
446
447  /** Creates the common serialized form for this table. */
448  abstract SerializedForm createSerializedForm();
449
450  /**
451   * Serialized type for all ImmutableTable instances. It captures the logical contents and
452   * preserves iteration order of all views.
453   */
454  static final class SerializedForm implements Serializable {
455    private final Object[] rowKeys;
456    private final Object[] columnKeys;
457
458    private final Object[] cellValues;
459    private final int[] cellRowIndices;
460    private final int[] cellColumnIndices;
461
462    private SerializedForm(
463        Object[] rowKeys,
464        Object[] columnKeys,
465        Object[] cellValues,
466        int[] cellRowIndices,
467        int[] cellColumnIndices) {
468      this.rowKeys = rowKeys;
469      this.columnKeys = columnKeys;
470      this.cellValues = cellValues;
471      this.cellRowIndices = cellRowIndices;
472      this.cellColumnIndices = cellColumnIndices;
473    }
474
475    static SerializedForm create(
476        ImmutableTable<?, ?, ?> table, int[] cellRowIndices, int[] cellColumnIndices) {
477      return new SerializedForm(
478          table.rowKeySet().toArray(),
479          table.columnKeySet().toArray(),
480          table.values().toArray(),
481          cellRowIndices,
482          cellColumnIndices);
483    }
484
485    Object readResolve() {
486      if (cellValues.length == 0) {
487        return of();
488      }
489      if (cellValues.length == 1) {
490        return of(rowKeys[0], columnKeys[0], cellValues[0]);
491      }
492      ImmutableList.Builder<Cell<Object, Object, Object>> cellListBuilder =
493          new ImmutableList.Builder<>(cellValues.length);
494      for (int i = 0; i < cellValues.length; i++) {
495        cellListBuilder.add(
496            cellOf(rowKeys[cellRowIndices[i]], columnKeys[cellColumnIndices[i]], cellValues[i]));
497      }
498      return RegularImmutableTable.forOrderedComponents(
499          cellListBuilder.build(), ImmutableSet.copyOf(rowKeys), ImmutableSet.copyOf(columnKeys));
500    }
501
502    private static final long serialVersionUID = 0;
503  }
504
505  final Object writeReplace() {
506    return createSerializedForm();
507  }
508
509  @GwtIncompatible // serialization
510  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
511    throw new InvalidObjectException("Use SerializedForm");
512  }
513}