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