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