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 javax.annotation.Nullable;
037
038/**
039 * A {@link Table} whose contents will never change, with many other important
040 * properties detailed at {@link ImmutableCollection}.
041 *
042 * <p>See the Guava User Guide article on <a href=
043 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
044 * 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);
069    checkNotNull(columnFunction);
070    checkNotNull(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);
097    checkNotNull(columnFunction);
098    checkNotNull(valueFunction);
099    checkNotNull(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);
154      this.column = checkNotNull(column);
155      this.value = checkNotNull(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);
175      this.value = checkNotNull(mergeFunction.apply(this.value, value));
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<R, C, V>(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
194   * determines the iteration ordering of all views in the returned table. Note
195   * that some views of the original table and the copied table may have
196   * different iteration orders. For more control over the ordering, create a
197   * {@link Builder} and call {@link Builder#orderRowsBy},
198   * {@link Builder#orderColumnsBy}, and {@link Builder#putAll}
199   *
200   * <p>Despite the method name, this method attempts to avoid actually copying
201   * the data when it is safe to do so. The exact circumstances under which a
202   * copy will or will not be performed are undocumented and subject to change.
203   */
204  public static <R, C, V> ImmutableTable<R, C, V> copyOf(
205      Table<? extends R, ? extends C, ? extends V> table) {
206    if (table instanceof ImmutableTable) {
207      @SuppressWarnings("unchecked")
208      ImmutableTable<R, C, V> parameterizedTable = (ImmutableTable<R, C, V>) table;
209      return parameterizedTable;
210    } else {
211      return copyOf(table.cellSet());
212    }
213  }
214  
215  private static <R, C, V> ImmutableTable<R, C, V> copyOf(
216      Iterable<? extends Cell<? extends R, ? extends C, ? extends V>> cells) {
217    ImmutableTable.Builder<R, C, V> builder = ImmutableTable.builder();
218    for (Cell<? extends R, ? extends C, ? extends V> cell : cells) {
219      builder.put(cell);
220    }
221    return builder.build();
222  }
223
224  /**
225   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
226   * Builder#Builder() ImmutableTable.Builder()} constructor.
227   */
228  public static <R, C, V> Builder<R, C, V> builder() {
229    return new Builder<R, C, V>();
230  }
231
232  /**
233   * Verifies that {@code rowKey}, {@code columnKey} and {@code value} are
234   * non-null, and returns a new entry with those values.
235   */
236  static <R, C, V> Cell<R, C, V> cellOf(R rowKey, C columnKey, V value) {
237    return Tables.immutableCell(checkNotNull(rowKey), checkNotNull(columnKey), checkNotNull(value));
238  }
239
240  /**
241   * A builder for creating immutable table instances, especially {@code public
242   * static final} tables ("constant tables"). Example: <pre>   {@code
243   *
244   *   static final ImmutableTable<Integer, Character, String> SPREADSHEET =
245   *       new ImmutableTable.Builder<Integer, Character, String>()
246   *           .put(1, 'A', "foo")
247   *           .put(1, 'B', "bar")
248   *           .put(2, 'A', "baz")
249   *           .build();}</pre>
250   *
251   * <p>By default, the order in which cells are added to the builder determines
252   * the iteration ordering of all views in the returned table, with {@link
253   * #putAll} following the {@link Table#cellSet()} iteration order. However, if
254   * {@link #orderRowsBy} or {@link #orderColumnsBy} is called, the views are
255   * sorted by the supplied comparators.
256   *
257   * For empty or single-cell immutable tables, {@link #of()} and
258   * {@link #of(Object, Object, Object)} are even more convenient.
259   *
260   * <p>Builder instances can be reused - it is safe to call {@link #build}
261   * multiple times to build multiple tables in series. Each table is a superset
262   * of the tables created before it.
263   *
264   * @since 11.0
265   */
266  public static final class Builder<R, C, V> {
267    private final List<Cell<R, C, V>> cells = Lists.newArrayList();
268    private Comparator<? super R> rowComparator;
269    private Comparator<? super C> columnComparator;
270
271    /**
272     * Creates a new builder. The returned builder is equivalent to the builder
273     * generated by {@link ImmutableTable#builder}.
274     */
275    public Builder() {}
276
277    /**
278     * Specifies the ordering of the generated table's rows.
279     */
280    @CanIgnoreReturnValue
281    public Builder<R, C, V> orderRowsBy(Comparator<? super R> rowComparator) {
282      this.rowComparator = checkNotNull(rowComparator);
283      return this;
284    }
285
286    /**
287     * Specifies the ordering of the generated table's columns.
288     */
289    @CanIgnoreReturnValue
290    public Builder<R, C, V> orderColumnsBy(Comparator<? super C> columnComparator) {
291      this.columnComparator = checkNotNull(columnComparator);
292      return this;
293    }
294
295    /**
296     * Associates the ({@code rowKey}, {@code columnKey}) pair with {@code
297     * value} in the built table. Duplicate key pairs are not allowed and will
298     * cause {@link #build} to fail.
299     */
300    @CanIgnoreReturnValue
301    public Builder<R, C, V> put(R rowKey, C columnKey, V value) {
302      cells.add(cellOf(rowKey, columnKey, value));
303      return this;
304    }
305
306    /**
307     * Adds the given {@code cell} to the table, making it immutable if
308     * necessary. Duplicate key pairs are not allowed and will cause {@link
309     * #build} to fail.
310     */
311    @CanIgnoreReturnValue
312    public Builder<R, C, V> put(Cell<? extends R, ? extends C, ? extends V> cell) {
313      if (cell instanceof Tables.ImmutableCell) {
314        checkNotNull(cell.getRowKey());
315        checkNotNull(cell.getColumnKey());
316        checkNotNull(cell.getValue());
317        @SuppressWarnings("unchecked") // all supported methods are covariant
318        Cell<R, C, V> immutableCell = (Cell<R, C, V>) cell;
319        cells.add(immutableCell);
320      } else {
321        put(cell.getRowKey(), cell.getColumnKey(), cell.getValue());
322      }
323      return this;
324    }
325
326    /**
327     * Associates all of the given table's keys and values in the built table.
328     * Duplicate row key column key pairs are not allowed, and will cause
329     * {@link #build} to fail.
330     *
331     * @throws NullPointerException if any key or value in {@code table} is null
332     */
333    @CanIgnoreReturnValue
334    public Builder<R, C, V> putAll(Table<? extends R, ? extends C, ? extends V> table) {
335      for (Cell<? extends R, ? extends C, ? extends V> cell : table.cellSet()) {
336        put(cell);
337      }
338      return this;
339    }
340    
341    Builder<R, C, V> combine(Builder<R, C, V> other) {
342      this.cells.addAll(other.cells);
343      return this;
344    }
345
346    /**
347     * Returns a newly-created immutable table.
348     *
349     * @throws IllegalArgumentException if duplicate key pairs were added
350     */
351    public ImmutableTable<R, C, V> build() {
352      int size = cells.size();
353      switch (size) {
354        case 0:
355          return of();
356        case 1:
357          return new SingletonImmutableTable<R, C, V>(Iterables.getOnlyElement(cells));
358        default:
359          return RegularImmutableTable.forCells(cells, rowComparator, columnComparator);
360      }
361    }
362  }
363
364  ImmutableTable() {}
365
366  @Override
367  public ImmutableSet<Cell<R, C, V>> cellSet() {
368    return (ImmutableSet<Cell<R, C, V>>) super.cellSet();
369  }
370
371  @Override
372  abstract ImmutableSet<Cell<R, C, V>> createCellSet();
373
374  @Override
375  final UnmodifiableIterator<Cell<R, C, V>> cellIterator() {
376    throw new AssertionError("should never be called");
377  }
378
379  @Override
380  final Spliterator<Cell<R, C, V>> cellSpliterator() {
381    throw new AssertionError("should never be called");
382  }
383
384  @Override
385  public ImmutableCollection<V> values() {
386    return (ImmutableCollection<V>) super.values();
387  }
388
389  @Override
390  abstract ImmutableCollection<V> createValues();
391
392  @Override
393  final Iterator<V> valuesIterator() {
394    throw new AssertionError("should never be called");
395  }
396
397  /**
398   * {@inheritDoc}
399   *
400   * @throws NullPointerException if {@code columnKey} is {@code null}
401   */
402  @Override
403  public ImmutableMap<R, V> column(C columnKey) {
404    checkNotNull(columnKey);
405    return MoreObjects.firstNonNull(
406        (ImmutableMap<R, V>) columnMap().get(columnKey), ImmutableMap.<R, V>of());
407  }
408
409  @Override
410  public ImmutableSet<C> columnKeySet() {
411    return columnMap().keySet();
412  }
413
414  /**
415   * {@inheritDoc}
416   *
417   * <p>The value {@code Map<R, V>} instances in the returned map are
418   * {@link ImmutableMap} instances as well.
419   */
420  @Override
421  public abstract ImmutableMap<C, Map<R, V>> columnMap();
422
423  /**
424   * {@inheritDoc}
425   *
426   * @throws NullPointerException if {@code rowKey} is {@code null}
427   */
428  @Override
429  public ImmutableMap<C, V> row(R rowKey) {
430    checkNotNull(rowKey);
431    return MoreObjects.firstNonNull(
432        (ImmutableMap<C, V>) rowMap().get(rowKey), ImmutableMap.<C, V>of());
433  }
434
435  @Override
436  public ImmutableSet<R> rowKeySet() {
437    return rowMap().keySet();
438  }
439
440  /**
441   * {@inheritDoc}
442   *
443   * <p>The value {@code Map<C, V>} instances in the returned map are
444   * {@link ImmutableMap} instances as well.
445   */
446  @Override
447  public abstract ImmutableMap<R, Map<C, V>> rowMap();
448
449  @Override
450  public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) {
451    return get(rowKey, columnKey) != null;
452  }
453
454  @Override
455  public boolean containsValue(@Nullable Object value) {
456    return values().contains(value);
457  }
458
459  /**
460   * Guaranteed to throw an exception and leave the table unmodified.
461   *
462   * @throws UnsupportedOperationException always
463   * @deprecated Unsupported operation.
464   */
465  @Deprecated
466  @Override
467  public final void clear() {
468    throw new UnsupportedOperationException();
469  }
470
471  /**
472   * Guaranteed to throw an exception and leave the table unmodified.
473   *
474   * @throws UnsupportedOperationException always
475   * @deprecated Unsupported operation.
476   */
477  @CanIgnoreReturnValue
478  @Deprecated
479  @Override
480  public final V put(R rowKey, C columnKey, V value) {
481    throw new UnsupportedOperationException();
482  }
483
484  /**
485   * Guaranteed to throw an exception and leave the table unmodified.
486   *
487   * @throws UnsupportedOperationException always
488   * @deprecated Unsupported operation.
489   */
490  @Deprecated
491  @Override
492  public final void putAll(Table<? extends R, ? extends C, ? extends V> table) {
493    throw new UnsupportedOperationException();
494  }
495
496  /**
497   * Guaranteed to throw an exception and leave the table unmodified.
498   *
499   * @throws UnsupportedOperationException always
500   * @deprecated Unsupported operation.
501   */
502  @CanIgnoreReturnValue
503  @Deprecated
504  @Override
505  public final V remove(Object rowKey, Object columnKey) {
506    throw new UnsupportedOperationException();
507  }
508
509  /** Creates the common serialized form for this table. */
510  abstract SerializedForm createSerializedForm();
511
512  /**
513   * Serialized type for all ImmutableTable instances. It captures the logical contents and
514   * preserves iteration order of all views.
515   */
516  static final class SerializedForm implements Serializable {
517    private final Object[] rowKeys;
518    private final Object[] columnKeys;
519
520    private final Object[] cellValues;
521    private final int[] cellRowIndices;
522    private final int[] cellColumnIndices;
523
524    private SerializedForm(
525        Object[] rowKeys,
526        Object[] columnKeys,
527        Object[] cellValues,
528        int[] cellRowIndices,
529        int[] cellColumnIndices) {
530      this.rowKeys = rowKeys;
531      this.columnKeys = columnKeys;
532      this.cellValues = cellValues;
533      this.cellRowIndices = cellRowIndices;
534      this.cellColumnIndices = cellColumnIndices;
535    }
536
537    static SerializedForm create(
538        ImmutableTable<?, ?, ?> table, int[] cellRowIndices, int[] cellColumnIndices) {
539      return new SerializedForm(
540          table.rowKeySet().toArray(),
541          table.columnKeySet().toArray(),
542          table.values().toArray(),
543          cellRowIndices,
544          cellColumnIndices);
545    }
546
547    Object readResolve() {
548      if (cellValues.length == 0) {
549        return of();
550      }
551      if (cellValues.length == 1) {
552        return of(rowKeys[0], columnKeys[0], cellValues[0]);
553      }
554      ImmutableList.Builder<Cell<Object, Object, Object>> cellListBuilder =
555          new ImmutableList.Builder<Cell<Object, Object, Object>>(cellValues.length);
556      for (int i = 0; i < cellValues.length; i++) {
557        cellListBuilder.add(
558            cellOf(rowKeys[cellRowIndices[i]], columnKeys[cellColumnIndices[i]], cellValues[i]));
559      }
560      return RegularImmutableTable.forOrderedComponents(
561          cellListBuilder.build(), ImmutableSet.copyOf(rowKeys), ImmutableSet.copyOf(columnKeys));
562    }
563
564    private static final long serialVersionUID = 0;
565  }
566
567  final Object writeReplace() {
568    return createSerializedForm();
569  }
570}