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