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