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