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