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