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