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.errorprone.annotations.concurrent.LazyInit;
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 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    // TODO(lowasser): consider an optimized values() implementation
257
258    @Override
259    public boolean containsKey(@CheckForNull Object key) {
260      return keyIndex.containsKey(key);
261    }
262
263    @CheckForNull
264    @Override
265    public V get(@CheckForNull Object key) {
266      Integer index = keyIndex.get(key);
267      if (index == null) {
268        return null;
269      } else {
270        return getValue(index);
271      }
272    }
273
274    @Override
275    @CheckForNull
276    public V put(K key, @ParametricNullness V value) {
277      Integer index = keyIndex.get(key);
278      if (index == null) {
279        throw new IllegalArgumentException(
280            getKeyRole() + " " + key + " not in " + keyIndex.keySet());
281      }
282      return setValue(index, value);
283    }
284
285    @Override
286    @CheckForNull
287    public V remove(@CheckForNull Object key) {
288      throw new UnsupportedOperationException();
289    }
290
291    @Override
292    public void clear() {
293      throw new UnsupportedOperationException();
294    }
295  }
296
297  /**
298   * Returns, as an immutable list, the row keys provided when the table was constructed, including
299   * those that are mapped to null values only.
300   */
301  public ImmutableList<R> rowKeyList() {
302    return rowList;
303  }
304
305  /**
306   * Returns, as an immutable list, the column keys provided when the table was constructed,
307   * including those that are mapped to null values only.
308   */
309  public ImmutableList<C> columnKeyList() {
310    return columnList;
311  }
312
313  /**
314   * Returns the value corresponding to the specified row and column indices. The same value is
315   * returned by {@code get(rowKeyList().get(rowIndex), columnKeyList().get(columnIndex))}, but this
316   * method runs more quickly.
317   *
318   * @param rowIndex position of the row key in {@link #rowKeyList()}
319   * @param columnIndex position of the row key in {@link #columnKeyList()}
320   * @return the value with the specified row and column
321   * @throws IndexOutOfBoundsException if either index is negative, {@code rowIndex} is greater than
322   *     or equal to the number of allowed row keys, or {@code columnIndex} is greater than or equal
323   *     to the number of allowed column keys
324   */
325  @CheckForNull
326  public V at(int rowIndex, int columnIndex) {
327    // In GWT array access never throws IndexOutOfBoundsException.
328    checkElementIndex(rowIndex, rowList.size());
329    checkElementIndex(columnIndex, columnList.size());
330    return array[rowIndex][columnIndex];
331  }
332
333  /**
334   * Associates {@code value} with the specified row and column indices. The logic {@code
335   * put(rowKeyList().get(rowIndex), columnKeyList().get(columnIndex), value)} has the same
336   * behavior, but this method runs more quickly.
337   *
338   * @param rowIndex position of the row key in {@link #rowKeyList()}
339   * @param columnIndex position of the row key in {@link #columnKeyList()}
340   * @param value value to store in the table
341   * @return the previous value with the specified row and column
342   * @throws IndexOutOfBoundsException if either index is negative, {@code rowIndex} is greater than
343   *     or equal to the number of allowed row keys, or {@code columnIndex} is greater than or equal
344   *     to the number of allowed column keys
345   */
346  @CanIgnoreReturnValue
347  @CheckForNull
348  public V set(int rowIndex, int columnIndex, @CheckForNull V value) {
349    // In GWT array access never throws IndexOutOfBoundsException.
350    checkElementIndex(rowIndex, rowList.size());
351    checkElementIndex(columnIndex, columnList.size());
352    V oldValue = array[rowIndex][columnIndex];
353    array[rowIndex][columnIndex] = value;
354    return oldValue;
355  }
356
357  /**
358   * Returns a two-dimensional array with the table contents. The row and column indices correspond
359   * to the positions of the row and column in the iterables provided during table construction. If
360   * the table lacks a mapping for a given row and column, the corresponding array element is null.
361   *
362   * <p>Subsequent table changes will not modify the array, and vice versa.
363   *
364   * @param valueClass class of values stored in the returned array
365   */
366  @GwtIncompatible // reflection
367  public @Nullable V[][] toArray(Class<V> valueClass) {
368    @SuppressWarnings("unchecked") // TODO: safe?
369    @Nullable
370    V[][] copy = (@Nullable V[][]) Array.newInstance(valueClass, rowList.size(), columnList.size());
371    for (int i = 0; i < rowList.size(); i++) {
372      System.arraycopy(array[i], 0, copy[i], 0, array[i].length);
373    }
374    return copy;
375  }
376
377  /**
378   * Not supported. Use {@link #eraseAll} instead.
379   *
380   * @throws UnsupportedOperationException always
381   * @deprecated Use {@link #eraseAll}
382   */
383  @DoNotCall("Always throws UnsupportedOperationException")
384  @Override
385  @Deprecated
386  public void clear() {
387    throw new UnsupportedOperationException();
388  }
389
390  /** Associates the value {@code null} with every pair of allowed row and column keys. */
391  public void eraseAll() {
392    for (@Nullable V[] row : array) {
393      Arrays.fill(row, null);
394    }
395  }
396
397  /**
398   * Returns {@code true} if the provided keys are among the keys provided when the table was
399   * constructed.
400   */
401  @Override
402  public boolean contains(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
403    return containsRow(rowKey) && containsColumn(columnKey);
404  }
405
406  /**
407   * Returns {@code true} if the provided column key is among the column keys provided when the
408   * table was constructed.
409   */
410  @Override
411  public boolean containsColumn(@CheckForNull Object columnKey) {
412    return columnKeyToIndex.containsKey(columnKey);
413  }
414
415  /**
416   * Returns {@code true} if the provided row key is among the row keys provided when the table was
417   * constructed.
418   */
419  @Override
420  public boolean containsRow(@CheckForNull Object rowKey) {
421    return rowKeyToIndex.containsKey(rowKey);
422  }
423
424  @Override
425  public boolean containsValue(@CheckForNull Object value) {
426    for (@Nullable V[] row : array) {
427      for (V element : row) {
428        if (Objects.equal(value, element)) {
429          return true;
430        }
431      }
432    }
433    return false;
434  }
435
436  @Override
437  @CheckForNull
438  public V get(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
439    Integer rowIndex = rowKeyToIndex.get(rowKey);
440    Integer columnIndex = columnKeyToIndex.get(columnKey);
441    return (rowIndex == null || columnIndex == null) ? null : at(rowIndex, columnIndex);
442  }
443
444  /**
445   * Returns {@code true} if {@code rowKeyList().size == 0} or {@code columnKeyList().size() == 0}.
446   */
447  @Override
448  public boolean isEmpty() {
449    return rowList.isEmpty() || columnList.isEmpty();
450  }
451
452  /**
453   * {@inheritDoc}
454   *
455   * @throws IllegalArgumentException if {@code rowKey} is not in {@link #rowKeySet()} or {@code
456   *     columnKey} is not in {@link #columnKeySet()}.
457   */
458  @CanIgnoreReturnValue
459  @Override
460  @CheckForNull
461  public V put(R rowKey, C columnKey, @CheckForNull V value) {
462    checkNotNull(rowKey);
463    checkNotNull(columnKey);
464    Integer rowIndex = rowKeyToIndex.get(rowKey);
465    checkArgument(rowIndex != null, "Row %s not in %s", rowKey, rowList);
466    Integer columnIndex = columnKeyToIndex.get(columnKey);
467    checkArgument(columnIndex != null, "Column %s not in %s", columnKey, columnList);
468    return set(rowIndex, columnIndex, value);
469  }
470
471  /*
472   * TODO(jlevy): Consider creating a merge() method, similar to putAll() but
473   * copying non-null values only.
474   */
475
476  /**
477   * {@inheritDoc}
478   *
479   * <p>If {@code table} is an {@code ArrayTable}, its null values will be stored in this table,
480   * possibly replacing values that were previously non-null.
481   *
482   * @throws NullPointerException if {@code table} has a null key
483   * @throws IllegalArgumentException if any of the provided table's row keys or column keys is not
484   *     in {@link #rowKeySet()} or {@link #columnKeySet()}
485   */
486  @Override
487  public void putAll(Table<? extends R, ? extends C, ? extends @Nullable V> table) {
488    super.putAll(table);
489  }
490
491  /**
492   * Not supported. Use {@link #erase} instead.
493   *
494   * @throws UnsupportedOperationException always
495   * @deprecated Use {@link #erase}
496   */
497  @DoNotCall("Always throws UnsupportedOperationException")
498  @CanIgnoreReturnValue
499  @Override
500  @Deprecated
501  @CheckForNull
502  public V remove(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
503    throw new UnsupportedOperationException();
504  }
505
506  /**
507   * Associates the value {@code null} with the specified keys, assuming both keys are valid. If
508   * either key is null or isn't among the keys provided during construction, this method has no
509   * effect.
510   *
511   * <p>This method is equivalent to {@code put(rowKey, columnKey, null)} when both provided keys
512   * are valid.
513   *
514   * @param rowKey row key of mapping to be erased
515   * @param columnKey column key of mapping to be erased
516   * @return the value previously associated with the keys, or {@code null} if no mapping existed
517   *     for the keys
518   */
519  @CanIgnoreReturnValue
520  @CheckForNull
521  public V erase(@CheckForNull Object rowKey, @CheckForNull Object columnKey) {
522    Integer rowIndex = rowKeyToIndex.get(rowKey);
523    Integer columnIndex = columnKeyToIndex.get(columnKey);
524    if (rowIndex == null || columnIndex == null) {
525      return null;
526    }
527    return set(rowIndex, columnIndex, null);
528  }
529
530  // TODO(jlevy): Add eraseRow and eraseColumn methods?
531
532  @Override
533  public int size() {
534    return rowList.size() * columnList.size();
535  }
536
537  /**
538   * Returns an unmodifiable set of all row key / column key / value triplets. Changes to the table
539   * will update the returned set.
540   *
541   * <p>The returned set's iterator traverses the mappings with the first row key, the mappings with
542   * the second row key, and so on.
543   *
544   * <p>The value in the returned cells may change if the table subsequently changes.
545   *
546   * @return set of table cells consisting of row key / column key / value triplets
547   */
548  @Override
549  public Set<Cell<R, C, @Nullable V>> cellSet() {
550    return super.cellSet();
551  }
552
553  @Override
554  Iterator<Cell<R, C, @Nullable V>> cellIterator() {
555    return new AbstractIndexedListIterator<Cell<R, C, @Nullable V>>(size()) {
556      @Override
557      protected Cell<R, C, @Nullable V> get(final int index) {
558        return getCell(index);
559      }
560    };
561  }
562
563  private Cell<R, C, @Nullable V> getCell(final int index) {
564    return new Tables.AbstractCell<R, C, @Nullable V>() {
565      final int rowIndex = index / columnList.size();
566      final int columnIndex = index % columnList.size();
567
568      @Override
569      public R getRowKey() {
570        return rowList.get(rowIndex);
571      }
572
573      @Override
574      public C getColumnKey() {
575        return columnList.get(columnIndex);
576      }
577
578      @Override
579      @CheckForNull
580      public V getValue() {
581        return at(rowIndex, columnIndex);
582      }
583    };
584  }
585
586  @CheckForNull
587  private V getValue(int index) {
588    int rowIndex = index / columnList.size();
589    int columnIndex = index % columnList.size();
590    return at(rowIndex, columnIndex);
591  }
592
593  /**
594   * Returns a view of all mappings that have the given column key. If the column key isn't in
595   * {@link #columnKeySet()}, an empty immutable map is returned.
596   *
597   * <p>Otherwise, for each row key in {@link #rowKeySet()}, the returned map associates the row key
598   * with the corresponding value in the table. Changes to the returned map will update the
599   * underlying table, and vice versa.
600   *
601   * @param columnKey key of column to search for in the table
602   * @return the corresponding map from row keys to values
603   */
604  @Override
605  public Map<R, @Nullable V> column(C columnKey) {
606    checkNotNull(columnKey);
607    Integer columnIndex = columnKeyToIndex.get(columnKey);
608    if (columnIndex == null) {
609      return emptyMap();
610    } else {
611      return new Column(columnIndex);
612    }
613  }
614
615  private class Column extends ArrayMap<R, @Nullable V> {
616    final int columnIndex;
617
618    Column(int columnIndex) {
619      super(rowKeyToIndex);
620      this.columnIndex = columnIndex;
621    }
622
623    @Override
624    String getKeyRole() {
625      return "Row";
626    }
627
628    @Override
629    @CheckForNull
630    V getValue(int index) {
631      return at(index, columnIndex);
632    }
633
634    @Override
635    @CheckForNull
636    V setValue(int index, @CheckForNull V newValue) {
637      return set(index, columnIndex, newValue);
638    }
639  }
640
641  /**
642   * Returns an immutable set of the valid column keys, including those that are associated with
643   * null values only.
644   *
645   * @return immutable set of column keys
646   */
647  @Override
648  public ImmutableSet<C> columnKeySet() {
649    return columnKeyToIndex.keySet();
650  }
651
652  @LazyInit @CheckForNull private transient ColumnMap columnMap;
653
654  @Override
655  public Map<C, Map<R, @Nullable V>> columnMap() {
656    ColumnMap map = columnMap;
657    return (map == null) ? columnMap = new ColumnMap() : map;
658  }
659
660  @WeakOuter
661  private class ColumnMap extends ArrayMap<C, Map<R, @Nullable V>> {
662    private ColumnMap() {
663      super(columnKeyToIndex);
664    }
665
666    @Override
667    String getKeyRole() {
668      return "Column";
669    }
670
671    @Override
672    Map<R, @Nullable V> getValue(int index) {
673      return new Column(index);
674    }
675
676    @Override
677    Map<R, @Nullable V> setValue(int index, Map<R, @Nullable V> newValue) {
678      throw new UnsupportedOperationException();
679    }
680
681    @Override
682    @CheckForNull
683    public Map<R, @Nullable V> put(C key, Map<R, @Nullable V> value) {
684      throw new UnsupportedOperationException();
685    }
686  }
687
688  /**
689   * Returns a view of all mappings that have the given row key. If the row key isn't in {@link
690   * #rowKeySet()}, an empty immutable map is returned.
691   *
692   * <p>Otherwise, for each column key in {@link #columnKeySet()}, the returned map associates the
693   * column key with the corresponding value in the table. Changes to the returned map will update
694   * the underlying table, and vice versa.
695   *
696   * @param rowKey key of row to search for in the table
697   * @return the corresponding map from column keys to values
698   */
699  @Override
700  public Map<C, @Nullable V> row(R rowKey) {
701    checkNotNull(rowKey);
702    Integer rowIndex = rowKeyToIndex.get(rowKey);
703    if (rowIndex == null) {
704      return emptyMap();
705    } else {
706      return new Row(rowIndex);
707    }
708  }
709
710  private class Row extends ArrayMap<C, @Nullable V> {
711    final int rowIndex;
712
713    Row(int rowIndex) {
714      super(columnKeyToIndex);
715      this.rowIndex = rowIndex;
716    }
717
718    @Override
719    String getKeyRole() {
720      return "Column";
721    }
722
723    @Override
724    @CheckForNull
725    V getValue(int index) {
726      return at(rowIndex, index);
727    }
728
729    @Override
730    @CheckForNull
731    V setValue(int index, @CheckForNull V newValue) {
732      return set(rowIndex, index, newValue);
733    }
734  }
735
736  /**
737   * Returns an immutable set of the valid row keys, including those that are associated with null
738   * values only.
739   *
740   * @return immutable set of row keys
741   */
742  @Override
743  public ImmutableSet<R> rowKeySet() {
744    return rowKeyToIndex.keySet();
745  }
746
747  @LazyInit @CheckForNull private transient RowMap rowMap;
748
749  @Override
750  public Map<R, Map<C, @Nullable V>> rowMap() {
751    RowMap map = rowMap;
752    return (map == null) ? rowMap = new RowMap() : map;
753  }
754
755  @WeakOuter
756  private class RowMap extends ArrayMap<R, Map<C, @Nullable V>> {
757    private RowMap() {
758      super(rowKeyToIndex);
759    }
760
761    @Override
762    String getKeyRole() {
763      return "Row";
764    }
765
766    @Override
767    Map<C, @Nullable V> getValue(int index) {
768      return new Row(index);
769    }
770
771    @Override
772    Map<C, @Nullable V> setValue(int index, Map<C, @Nullable V> newValue) {
773      throw new UnsupportedOperationException();
774    }
775
776    @Override
777    @CheckForNull
778    public Map<C, @Nullable V> put(R key, Map<C, @Nullable V> value) {
779      throw new UnsupportedOperationException();
780    }
781  }
782
783  /**
784   * Returns an unmodifiable collection of all values, which may contain duplicates. Changes to the
785   * table will update the returned collection.
786   *
787   * <p>The returned collection's iterator traverses the values of the first row key, the values of
788   * the second row key, and so on.
789   *
790   * @return collection of values
791   */
792  @Override
793  public Collection<@Nullable V> values() {
794    return super.values();
795  }
796
797  @Override
798  Iterator<@Nullable V> valuesIterator() {
799    return new AbstractIndexedListIterator<@Nullable V>(size()) {
800      @Override
801      @CheckForNull
802      protected V get(int index) {
803        return getValue(index);
804      }
805    };
806  }
807
808  private static final long serialVersionUID = 0;
809}