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