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.checkArgument;
020import static com.google.common.base.Preconditions.checkElementIndex;
021import static com.google.common.base.Preconditions.checkNotNull;
022import static java.util.Collections.emptyMap;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.GwtIncompatible;
027import com.google.common.base.Objects;
028import com.google.common.collect.Maps.IteratorBasedAbstractMap;
029import com.google.errorprone.annotations.CanIgnoreReturnValue;
030import com.google.errorprone.annotations.DoNotCall;
031import com.google.j2objc.annotations.WeakOuter;
032import java.io.Serializable;
033import java.lang.reflect.Array;
034import java.util.Arrays;
035import java.util.Collection;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.Set;
039import java.util.Spliterator;
040import javax.annotation.CheckForNull;
041import org.checkerframework.checker.nullness.qual.Nullable;
042
043/**
044 * Fixed-size {@link Table} implementation backed by a two-dimensional array.
045 *
046 * <p><b>Warning:</b> {@code ArrayTable} is rarely the {@link Table} implementation you want. First,
047 * it requires that the complete universe of rows and columns be specified at construction time.
048 * Second, it is always backed by an array large enough to hold a value for every possible
049 * combination of row and column keys. (This is rarely optimal unless the table is extremely dense.)
050 * Finally, every possible combination of row and column keys is always considered to have a value
051 * associated with it: It is not possible to "remove" a value, only to replace it with {@code null},
052 * which will still appear when iterating over the table's contents in a foreach loop or a call to a
053 * null-hostile method like {@link ImmutableTable#copyOf}. For alternatives, please see <a
054 * href="https://github.com/google/guava/wiki/NewCollectionTypesExplained#table">the wiki</a>.
055 *
056 * <p>The allowed row and column keys must be supplied when the table is created. The table always
057 * contains a mapping for every row key / column pair. The value corresponding to a given row and
058 * column is null unless another value is provided.
059 *
060 * <p>The table's size is constant: the product of the number of supplied row keys and the number of
061 * supplied column keys. The {@code remove} and {@code clear} methods are not supported by the table
062 * or its views. The {@link #erase} and {@link #eraseAll} methods may be used instead.
063 *
064 * <p>The ordering of the row and column keys provided when the table is constructed determines the
065 * iteration ordering across rows and columns in the table's views. None of the view iterators
066 * support {@link Iterator#remove}. If the table is modified after an iterator is created, the
067 * iterator remains valid.
068 *
069 * <p>This class requires less memory than the {@link HashBasedTable} and {@link TreeBasedTable}
070 * implementations, except when the table is sparse.
071 *
072 * <p>Null row keys or column keys are not permitted.
073 *
074 * <p>This class provides methods involving the underlying array structure, where the array indices
075 * correspond to the position of a row or column in the lists of allowed keys and values. See the
076 * {@link #at}, {@link #set}, {@link #toArray}, {@link #rowKeyList}, and {@link #columnKeyList}
077 * methods for more details.
078 *
079 * <p>Note that this implementation is not synchronized. If multiple threads access the same cell of
080 * an {@code ArrayTable} concurrently and one of the threads modifies its value, there is no
081 * guarantee that the new value will be fully visible to the other threads. To guarantee that
082 * modifications are visible, synchronize access to the table. Unlike other {@code Table}
083 * implementations, synchronization is unnecessary between a thread that writes to one cell and a
084 * thread that reads from another.
085 *
086 * <p>See the Guava User Guide article on <a href=
087 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#table"> {@code Table}</a>.
088 *
089 * @author Jared Levy
090 * @since 10.0
091 */
092@Beta
093@GwtCompatible(emulated = true)
094@ElementTypesAreNonnullByDefault
095public final class ArrayTable<R, C, V> extends AbstractTable<R, C, @Nullable V>
096    implements Serializable {
097
098  /**
099   * Creates an {@code ArrayTable} filled with {@code null}.
100   *
101   * @param rowKeys row keys that may be stored in the generated table
102   * @param columnKeys column keys that may be stored in the generated table
103   * @throws NullPointerException if any of the provided keys is null
104   * @throws IllegalArgumentException if {@code rowKeys} or {@code columnKeys} contains duplicates
105   *     or if exactly one of {@code rowKeys} or {@code columnKeys} is empty.
106   */
107  public static <R, C, V> ArrayTable<R, C, V> create(
108      Iterable<? extends R> rowKeys, Iterable<? extends C> columnKeys) {
109    return new ArrayTable<>(rowKeys, columnKeys);
110  }
111
112  /*
113   * TODO(jlevy): Add factory methods taking an Enum class, instead of an
114   * iterable, to specify the allowed row keys and/or column keys. Note that
115   * custom serialization logic is needed to support different enum sizes during
116   * serialization and deserialization.
117   */
118
119  /**
120   * Creates an {@code ArrayTable} with the mappings in the provided table.
121   *
122   * <p>If {@code table} includes a mapping with row key {@code r} and a separate mapping with
123   * column key {@code c}, the returned table contains a mapping with row key {@code r} and column
124   * key {@code c}. If that row key / column key pair in not in {@code table}, the pair maps to
125   * {@code null} in the generated table.
126   *
127   * <p>The returned table allows subsequent {@code put} calls with the row keys in {@code
128   * table.rowKeySet()} and the column keys in {@code table.columnKeySet()}. Calling {@link #put}
129   * with other keys leads to an {@code IllegalArgumentException}.
130   *
131   * <p>The ordering of {@code table.rowKeySet()} and {@code table.columnKeySet()} determines the
132   * row and column iteration ordering of the returned table.
133   *
134   * @throws NullPointerException if {@code table} has a null key
135   */
136  public static <R, C, V> ArrayTable<R, C, V> create(Table<R, C, ? extends @Nullable V> table) {
137    return (table instanceof ArrayTable)
138        ? new ArrayTable<R, C, V>((ArrayTable<R, C, V>) table)
139        : new ArrayTable<R, C, V>(table);
140  }
141
142  private final ImmutableList<R> rowList;
143  private final ImmutableList<C> columnList;
144
145  // TODO(jlevy): Add getters returning rowKeyToIndex and columnKeyToIndex?
146  private final ImmutableMap<R, Integer> rowKeyToIndex;
147  private final ImmutableMap<C, Integer> columnKeyToIndex;
148  private final @Nullable V[][] array;
149
150  private ArrayTable(Iterable<? extends R> rowKeys, Iterable<? extends C> columnKeys) {
151    this.rowList = ImmutableList.copyOf(rowKeys);
152    this.columnList = ImmutableList.copyOf(columnKeys);
153    checkArgument(rowList.isEmpty() == columnList.isEmpty());
154
155    /*
156     * TODO(jlevy): Support only one of rowKey / columnKey being empty? If we
157     * do, when columnKeys is empty but rowKeys isn't, rowKeyList() can contain
158     * elements but rowKeySet() will be empty and containsRow() won't
159     * acknowledge them.
160     */
161    rowKeyToIndex = Maps.indexMap(rowList);
162    columnKeyToIndex = Maps.indexMap(columnList);
163
164    @SuppressWarnings("unchecked")
165    @Nullable
166    V[][] tmpArray = (@Nullable V[][]) new Object[rowList.size()][columnList.size()];
167    array = tmpArray;
168    // Necessary because in GWT the arrays are initialized with "undefined" instead of null.
169    eraseAll();
170  }
171
172  private ArrayTable(Table<R, C, ? extends @Nullable V> table) {
173    this(table.rowKeySet(), table.columnKeySet());
174    putAll(table);
175  }
176
177  private ArrayTable(ArrayTable<R, C, V> table) {
178    rowList = table.rowList;
179    columnList = table.columnList;
180    rowKeyToIndex = table.rowKeyToIndex;
181    columnKeyToIndex = table.columnKeyToIndex;
182    @SuppressWarnings("unchecked")
183    @Nullable
184    V[][] copy = (@Nullable V[][]) new Object[rowList.size()][columnList.size()];
185    array = copy;
186    for (int i = 0; i < rowList.size(); i++) {
187      System.arraycopy(table.array[i], 0, copy[i], 0, table.array[i].length);
188    }
189  }
190
191  private abstract static class ArrayMap<K, V extends @Nullable Object>
192      extends IteratorBasedAbstractMap<K, V> {
193    private final ImmutableMap<K, Integer> keyIndex;
194
195    private ArrayMap(ImmutableMap<K, Integer> keyIndex) {
196      this.keyIndex = keyIndex;
197    }
198
199    @Override
200    public Set<K> keySet() {
201      return keyIndex.keySet();
202    }
203
204    K getKey(int index) {
205      return keyIndex.keySet().asList().get(index);
206    }
207
208    abstract String getKeyRole();
209
210    @ParametricNullness
211    abstract V getValue(int index);
212
213    @ParametricNullness
214    abstract V setValue(int index, @ParametricNullness V newValue);
215
216    @Override
217    public int size() {
218      return keyIndex.size();
219    }
220
221    @Override
222    public boolean isEmpty() {
223      return keyIndex.isEmpty();
224    }
225
226    Entry<K, V> getEntry(final int index) {
227      checkElementIndex(index, size());
228      return new AbstractMapEntry<K, V>() {
229        @Override
230        public K getKey() {
231          return ArrayMap.this.getKey(index);
232        }
233
234        @Override
235        @ParametricNullness
236        public V getValue() {
237          return ArrayMap.this.getValue(index);
238        }
239
240        @Override
241        @ParametricNullness
242        public V setValue(@ParametricNullness V value) {
243          return ArrayMap.this.setValue(index, value);
244        }
245      };
246    }
247
248    @Override
249    Iterator<Entry<K, V>> entryIterator() {
250      return new AbstractIndexedListIterator<Entry<K, V>>(size()) {
251        @Override
252        protected Entry<K, V> get(final int index) {
253          return getEntry(index);
254        }
255      };
256    }
257
258    @Override
259    Spliterator<Entry<K, V>> entrySpliterator() {
260      return CollectSpliterators.indexed(size(), Spliterator.ORDERED, this::getEntry);
261    }
262
263    // TODO(lowasser): consider an optimized values() implementation
264
265    @Override
266    public boolean containsKey(@CheckForNull Object key) {
267      return keyIndex.containsKey(key);
268    }
269
270    @CheckForNull
271    @Override
272    public V get(@CheckForNull Object key) {
273      Integer index = keyIndex.get(key);
274      if (index == null) {
275        return null;
276      } else {
277        return getValue(index);
278      }
279    }
280
281    @Override
282    @CheckForNull
283    public V put(K key, @ParametricNullness V value) {
284      Integer index = keyIndex.get(key);
285      if (index == null) {
286        throw new IllegalArgumentException(
287            getKeyRole() + " " + key + " not in " + keyIndex.keySet());
288      }
289      return setValue(index, value);
290    }
291
292    @Override
293    @CheckForNull
294    public V remove(@CheckForNull Object key) {
295      throw new UnsupportedOperationException();
296    }
297
298    @Override
299    public void clear() {
300      throw new UnsupportedOperationException();
301    }
302  }
303
304  /**
305   * Returns, as an immutable list, the row keys provided when the table was constructed, including
306   * those that are mapped to null values only.
307   */
308  public ImmutableList<R> rowKeyList() {
309    return rowList;
310  }
311
312  /**
313   * Returns, as an immutable list, the column keys provided when the table was constructed,
314   * including those that are mapped to null values only.
315   */
316  public ImmutableList<C> columnKeyList() {
317    return columnList;
318  }
319
320  /**
321   * Returns the value corresponding to the specified row and column indices. The same value is
322   * returned by {@code get(rowKeyList().get(rowIndex), columnKeyList().get(columnIndex))}, but this
323   * method runs more quickly.
324   *
325   * @param rowIndex position of the row key in {@link #rowKeyList()}
326   * @param columnIndex position of the row key in {@link #columnKeyList()}
327   * @return the value with the specified row and column
328   * @throws IndexOutOfBoundsException if either index is negative, {@code rowIndex} is greater than
329   *     or equal to the number of allowed row keys, or {@code columnIndex} is greater than or equal
330   *     to the number of allowed column keys
331   */
332  @CheckForNull
333  public V at(int rowIndex, int columnIndex) {
334    // In GWT array access never throws IndexOutOfBoundsException.
335    checkElementIndex(rowIndex, rowList.size());
336    checkElementIndex(columnIndex, columnList.size());
337    return array[rowIndex][columnIndex];
338  }
339
340  /**
341   * Associates {@code value} with the specified row and column indices. The logic {@code
342   * put(rowKeyList().get(rowIndex), columnKeyList().get(columnIndex), value)} has the same
343   * behavior, but this method runs more quickly.
344   *
345   * @param rowIndex position of the row key in {@link #rowKeyList()}
346   * @param columnIndex position of the row key in {@link #columnKeyList()}
347   * @param value value to store in the table
348   * @return the previous value with the specified row and column
349   * @throws IndexOutOfBoundsException if either index is negative, {@code rowIndex} is greater than
350   *     or equal to the number of allowed row keys, or {@code columnIndex} is greater than or equal
351   *     to the number of allowed column keys
352   */
353  @CanIgnoreReturnValue
354  @CheckForNull
355  public V set(int rowIndex, int columnIndex, @CheckForNull V value) {
356    // In GWT array access never throws IndexOutOfBoundsException.
357    checkElementIndex(rowIndex, rowList.size());
358    checkElementIndex(columnIndex, columnList.size());
359    V oldValue = array[rowIndex][columnIndex];
360    array[rowIndex][columnIndex] = value;
361    return oldValue;
362  }
363
364  /**
365   * Returns a two-dimensional array with the table contents. The row and column indices correspond
366   * to the positions of the row and column in the iterables provided during table construction. If
367   * the table lacks a mapping for a given row and column, the corresponding array element is null.
368   *
369   * <p>Subsequent table changes will not modify the array, and vice versa.
370   *
371   * @param valueClass class of values stored in the returned array
372   */
373  @GwtIncompatible // reflection
374  public @Nullable V[][] toArray(Class<V> valueClass) {
375    @SuppressWarnings("unchecked") // TODO: safe?
376    @Nullable
377    V[][] copy = (@Nullable V[][]) Array.newInstance(valueClass, rowList.size(), columnList.size());
378    for (int i = 0; i < rowList.size(); i++) {
379      System.arraycopy(array[i], 0, copy[i], 0, array[i].length);
380    }
381    return copy;
382  }
383
384  /**
385   * Not supported. Use {@link #eraseAll} instead.
386   *
387   * @throws UnsupportedOperationException always
388   * @deprecated Use {@link #eraseAll}
389   */
390  @DoNotCall("Always throws UnsupportedOperationException")
391  @Override
392  @Deprecated
393  public void clear() {
394    throw new UnsupportedOperationException();
395  }
396
397  /** Associates the value {@code null} with every pair of allowed row and column keys. */
398  public void eraseAll() {
399    for (@Nullable V[] row : array) {
400      Arrays.fill(row, null);
401    }
402  }
403
404  /**
405   * Returns {@code true} if the provided keys are among the keys provided when the table was
406   * constructed.
407   */
408  @Override
409  public boolean contains(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
410    return containsRow(rowKey) && containsColumn(columnKey);
411  }
412
413  /**
414   * Returns {@code true} if the provided column key is among the column keys provided when the
415   * table was constructed.
416   */
417  @Override
418  public boolean containsColumn(@CheckForNull Object columnKey) {
419    return columnKeyToIndex.containsKey(columnKey);
420  }
421
422  /**
423   * Returns {@code true} if the provided row key is among the row keys provided when the table was
424   * constructed.
425   */
426  @Override
427  public boolean containsRow(@CheckForNull Object rowKey) {
428    return rowKeyToIndex.containsKey(rowKey);
429  }
430
431  @Override
432  public boolean containsValue(@CheckForNull Object value) {
433    for (@Nullable V[] row : array) {
434      for (V element : row) {
435        if (Objects.equal(value, element)) {
436          return true;
437        }
438      }
439    }
440    return false;
441  }
442
443  @Override
444  @CheckForNull
445  public V get(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
446    Integer rowIndex = rowKeyToIndex.get(rowKey);
447    Integer columnIndex = columnKeyToIndex.get(columnKey);
448    return (rowIndex == null || columnIndex == null) ? null : at(rowIndex, columnIndex);
449  }
450
451  /**
452   * Returns {@code true} if {@code rowKeyList().size == 0} or {@code columnKeyList().size() == 0}.
453   */
454  @Override
455  public boolean isEmpty() {
456    return rowList.isEmpty() || columnList.isEmpty();
457  }
458
459  /**
460   * {@inheritDoc}
461   *
462   * @throws IllegalArgumentException if {@code rowKey} is not in {@link #rowKeySet()} or {@code
463   *     columnKey} is not in {@link #columnKeySet()}.
464   */
465  @CanIgnoreReturnValue
466  @Override
467  @CheckForNull
468  public V put(R rowKey, C columnKey, @CheckForNull V value) {
469    checkNotNull(rowKey);
470    checkNotNull(columnKey);
471    Integer rowIndex = rowKeyToIndex.get(rowKey);
472    checkArgument(rowIndex != null, "Row %s not in %s", rowKey, rowList);
473    Integer columnIndex = columnKeyToIndex.get(columnKey);
474    checkArgument(columnIndex != null, "Column %s not in %s", columnKey, columnList);
475    return set(rowIndex, columnIndex, value);
476  }
477
478  /*
479   * TODO(jlevy): Consider creating a merge() method, similar to putAll() but
480   * copying non-null values only.
481   */
482
483  /**
484   * {@inheritDoc}
485   *
486   * <p>If {@code table} is an {@code ArrayTable}, its null values will be stored in this table,
487   * possibly replacing values that were previously non-null.
488   *
489   * @throws NullPointerException if {@code table} has a null key
490   * @throws IllegalArgumentException if any of the provided table's row keys or column keys is not
491   *     in {@link #rowKeySet()} or {@link #columnKeySet()}
492   */
493  @Override
494  public void putAll(Table<? extends R, ? extends C, ? extends @Nullable V> table) {
495    super.putAll(table);
496  }
497
498  /**
499   * Not supported. Use {@link #erase} instead.
500   *
501   * @throws UnsupportedOperationException always
502   * @deprecated Use {@link #erase}
503   */
504  @DoNotCall("Always throws UnsupportedOperationException")
505  @CanIgnoreReturnValue
506  @Override
507  @Deprecated
508  @CheckForNull
509  public V remove(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
510    throw new UnsupportedOperationException();
511  }
512
513  /**
514   * Associates the value {@code null} with the specified keys, assuming both keys are valid. If
515   * either key is null or isn't among the keys provided during construction, this method has no
516   * effect.
517   *
518   * <p>This method is equivalent to {@code put(rowKey, columnKey, null)} when both provided keys
519   * are valid.
520   *
521   * @param rowKey row key of mapping to be erased
522   * @param columnKey column key of mapping to be erased
523   * @return the value previously associated with the keys, or {@code null} if no mapping existed
524   *     for the keys
525   */
526  @CanIgnoreReturnValue
527  @CheckForNull
528  public V erase(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
529    Integer rowIndex = rowKeyToIndex.get(rowKey);
530    Integer columnIndex = columnKeyToIndex.get(columnKey);
531    if (rowIndex == null || columnIndex == null) {
532      return null;
533    }
534    return set(rowIndex, columnIndex, null);
535  }
536
537  // TODO(jlevy): Add eraseRow and eraseColumn methods?
538
539  @Override
540  public int size() {
541    return rowList.size() * columnList.size();
542  }
543
544  /**
545   * Returns an unmodifiable set of all row key / column key / value triplets. Changes to the table
546   * will update the returned set.
547   *
548   * <p>The returned set's iterator traverses the mappings with the first row key, the mappings with
549   * the second row key, and so on.
550   *
551   * <p>The value in the returned cells may change if the table subsequently changes.
552   *
553   * @return set of table cells consisting of row key / column key / value triplets
554   */
555  @Override
556  public Set<Cell<R, C, @Nullable V>> cellSet() {
557    return super.cellSet();
558  }
559
560  @Override
561  Iterator<Cell<R, C, @Nullable V>> cellIterator() {
562    return new AbstractIndexedListIterator<Cell<R, C, @Nullable V>>(size()) {
563      @Override
564      protected Cell<R, C, @Nullable V> get(final int index) {
565        return getCell(index);
566      }
567    };
568  }
569
570  @Override
571  Spliterator<Cell<R, C, @Nullable V>> cellSpliterator() {
572    return CollectSpliterators.<Cell<R, C, @Nullable V>>indexed(
573        size(), Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.DISTINCT, this::getCell);
574  }
575
576  private Cell<R, C, @Nullable V> getCell(final int index) {
577    return new Tables.AbstractCell<R, C, @Nullable V>() {
578      final int rowIndex = index / columnList.size();
579      final int columnIndex = index % columnList.size();
580
581      @Override
582      public R getRowKey() {
583        return rowList.get(rowIndex);
584      }
585
586      @Override
587      public C getColumnKey() {
588        return columnList.get(columnIndex);
589      }
590
591      @Override
592      @CheckForNull
593      public V getValue() {
594        return at(rowIndex, columnIndex);
595      }
596    };
597  }
598
599  @CheckForNull
600  private V getValue(int index) {
601    int rowIndex = index / columnList.size();
602    int columnIndex = index % columnList.size();
603    return at(rowIndex, columnIndex);
604  }
605
606  /**
607   * Returns a view of all mappings that have the given column key. If the column key isn't in
608   * {@link #columnKeySet()}, an empty immutable map is returned.
609   *
610   * <p>Otherwise, for each row key in {@link #rowKeySet()}, the returned map associates the row key
611   * with the corresponding value in the table. Changes to the returned map will update the
612   * underlying table, and vice versa.
613   *
614   * @param columnKey key of column to search for in the table
615   * @return the corresponding map from row keys to values
616   */
617  @Override
618  public Map<R, @Nullable V> column(C columnKey) {
619    checkNotNull(columnKey);
620    Integer columnIndex = columnKeyToIndex.get(columnKey);
621    if (columnIndex == null) {
622      return emptyMap();
623    } else {
624      return new Column(columnIndex);
625    }
626  }
627
628  private class Column extends ArrayMap<R, @Nullable V> {
629    final int columnIndex;
630
631    Column(int columnIndex) {
632      super(rowKeyToIndex);
633      this.columnIndex = columnIndex;
634    }
635
636    @Override
637    String getKeyRole() {
638      return "Row";
639    }
640
641    @Override
642    @CheckForNull
643    V getValue(int index) {
644      return at(index, columnIndex);
645    }
646
647    @Override
648    @CheckForNull
649    V setValue(int index, @CheckForNull V newValue) {
650      return set(index, columnIndex, newValue);
651    }
652  }
653
654  /**
655   * Returns an immutable set of the valid column keys, including those that are associated with
656   * null values only.
657   *
658   * @return immutable set of column keys
659   */
660  @Override
661  public ImmutableSet<C> columnKeySet() {
662    return columnKeyToIndex.keySet();
663  }
664
665  @CheckForNull private transient ColumnMap columnMap;
666
667  @Override
668  public Map<C, Map<R, @Nullable V>> columnMap() {
669    ColumnMap map = columnMap;
670    return (map == null) ? columnMap = new ColumnMap() : map;
671  }
672
673  @WeakOuter
674  private class ColumnMap extends ArrayMap<C, Map<R, @Nullable V>> {
675    private ColumnMap() {
676      super(columnKeyToIndex);
677    }
678
679    @Override
680    String getKeyRole() {
681      return "Column";
682    }
683
684    @Override
685    Map<R, @Nullable V> getValue(int index) {
686      return new Column(index);
687    }
688
689    @Override
690    Map<R, @Nullable V> setValue(int index, Map<R, @Nullable V> newValue) {
691      throw new UnsupportedOperationException();
692    }
693
694    @Override
695    @CheckForNull
696    public Map<R, @Nullable V> put(C key, Map<R, @Nullable V> value) {
697      throw new UnsupportedOperationException();
698    }
699  }
700
701  /**
702   * Returns a view of all mappings that have the given row key. If the row key isn't in {@link
703   * #rowKeySet()}, an empty immutable map is returned.
704   *
705   * <p>Otherwise, for each column key in {@link #columnKeySet()}, the returned map associates the
706   * column key with the corresponding value in the table. Changes to the returned map will update
707   * the underlying table, and vice versa.
708   *
709   * @param rowKey key of row to search for in the table
710   * @return the corresponding map from column keys to values
711   */
712  @Override
713  public Map<C, @Nullable V> row(R rowKey) {
714    checkNotNull(rowKey);
715    Integer rowIndex = rowKeyToIndex.get(rowKey);
716    if (rowIndex == null) {
717      return emptyMap();
718    } else {
719      return new Row(rowIndex);
720    }
721  }
722
723  private class Row extends ArrayMap<C, @Nullable V> {
724    final int rowIndex;
725
726    Row(int rowIndex) {
727      super(columnKeyToIndex);
728      this.rowIndex = rowIndex;
729    }
730
731    @Override
732    String getKeyRole() {
733      return "Column";
734    }
735
736    @Override
737    @CheckForNull
738    V getValue(int index) {
739      return at(rowIndex, index);
740    }
741
742    @Override
743    @CheckForNull
744    V setValue(int index, @CheckForNull V newValue) {
745      return set(rowIndex, index, newValue);
746    }
747  }
748
749  /**
750   * Returns an immutable set of the valid row keys, including those that are associated with null
751   * values only.
752   *
753   * @return immutable set of row keys
754   */
755  @Override
756  public ImmutableSet<R> rowKeySet() {
757    return rowKeyToIndex.keySet();
758  }
759
760  @CheckForNull private transient RowMap rowMap;
761
762  @Override
763  public Map<R, Map<C, @Nullable V>> rowMap() {
764    RowMap map = rowMap;
765    return (map == null) ? rowMap = new RowMap() : map;
766  }
767
768  @WeakOuter
769  private class RowMap extends ArrayMap<R, Map<C, @Nullable V>> {
770    private RowMap() {
771      super(rowKeyToIndex);
772    }
773
774    @Override
775    String getKeyRole() {
776      return "Row";
777    }
778
779    @Override
780    Map<C, @Nullable V> getValue(int index) {
781      return new Row(index);
782    }
783
784    @Override
785    Map<C, @Nullable V> setValue(int index, Map<C, @Nullable V> newValue) {
786      throw new UnsupportedOperationException();
787    }
788
789    @Override
790    @CheckForNull
791    public Map<C, @Nullable V> put(R key, Map<C, @Nullable V> value) {
792      throw new UnsupportedOperationException();
793    }
794  }
795
796  /**
797   * Returns an unmodifiable collection of all values, which may contain duplicates. Changes to the
798   * table will update the returned collection.
799   *
800   * <p>The returned collection's iterator traverses the values of the first row key, the values of
801   * the second row key, and so on.
802   *
803   * @return collection of values
804   */
805  @Override
806  public Collection<@Nullable V> values() {
807    return super.values();
808  }
809
810  @Override
811  Iterator<@Nullable V> valuesIterator() {
812    return new AbstractIndexedListIterator<@Nullable V>(size()) {
813      @Override
814      @CheckForNull
815      protected V get(int index) {
816        return getValue(index);
817      }
818    };
819  }
820
821  @Override
822  Spliterator<@Nullable V> valuesSpliterator() {
823    return CollectSpliterators.<@Nullable V>indexed(size(), Spliterator.ORDERED, this::getValue);
824  }
825
826  private static final long serialVersionUID = 0;
827}