View Javadoc
1   /*
2    * Copyright (C) 2009 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  
21  import com.google.common.annotations.Beta;
22  import com.google.common.annotations.GwtCompatible;
23  import com.google.common.base.MoreObjects;
24  import com.google.common.collect.Tables.AbstractCell;
25  import com.google.errorprone.annotations.CanIgnoreReturnValue;
26  import java.io.Serializable;
27  import java.util.ArrayList;
28  import java.util.Comparator;
29  import java.util.Iterator;
30  import java.util.List;
31  import java.util.Map;
32  import java.util.Spliterator;
33  import java.util.function.BinaryOperator;
34  import java.util.function.Function;
35  import java.util.stream.Collector;
36  import javax.annotation.Nullable;
37  
38  /**
39   * A {@link Table} whose contents will never change, with many other important
40   * properties detailed at {@link ImmutableCollection}.
41   *
42   * <p>See the Guava User Guide article on <a href=
43   * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
44   * immutable collections</a>.
45   *
46   * @author Gregory Kick
47   * @since 11.0
48   */
49  @GwtCompatible
50  public abstract class ImmutableTable<R, C, V> extends AbstractTable<R, C, V>
51      implements Serializable {
52  
53    /**
54     * Returns a {@code Collector} that accumulates elements into an {@code ImmutableTable}. Each
55     * input element is mapped to one cell in the returned table, with the rows, columns, and values
56     * generated by applying the specified functions.
57     *
58     * <p>The returned {@code Collector} will throw a {@code NullPointerException} at collection time
59     * if the row, column, or value functions return null on any input.
60     *
61     * @since 21.0
62     */
63    @Beta
64    public static <T, R, C, V> Collector<T, ?, ImmutableTable<R, C, V>> toImmutableTable(
65        Function<? super T, ? extends R> rowFunction,
66        Function<? super T, ? extends C> columnFunction,
67        Function<? super T, ? extends V> valueFunction) {
68      checkNotNull(rowFunction);
69      checkNotNull(columnFunction);
70      checkNotNull(valueFunction);
71      return Collector.of(
72          () -> new ImmutableTable.Builder<R, C, V>(),
73          (builder, t) ->
74              builder.put(rowFunction.apply(t), columnFunction.apply(t), valueFunction.apply(t)),
75          (b1, b2) -> b1.combine(b2),
76          b -> b.build());
77    }
78  
79    /**
80     * Returns a {@code Collector} that accumulates elements into an {@code ImmutableTable}. Each
81     * input element is mapped to one cell in the returned table, with the rows, columns, and values
82     * generated by applying the specified functions. If multiple inputs are mapped to the same row
83     * and column pair, they will be combined with the specified merging function in encounter order.
84     *
85     * <p>The returned {@code Collector} will throw a {@code NullPointerException} at collection time
86     * if the row, column, value, or merging functions return null on any input.
87     *
88     * @since 21.0
89     */
90    public static <T, R, C, V> Collector<T, ?, ImmutableTable<R, C, V>> toImmutableTable(
91        Function<? super T, ? extends R> rowFunction,
92        Function<? super T, ? extends C> columnFunction,
93        Function<? super T, ? extends V> valueFunction,
94        BinaryOperator<V> mergeFunction) {
95  
96      checkNotNull(rowFunction);
97      checkNotNull(columnFunction);
98      checkNotNull(valueFunction);
99      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<>(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<>();
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<>(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<>(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 }