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