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