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