Initial Jack import.

Change-Id: I953cf0a520195a7187d791b2885848ad0d5a9b43

1 files changed, 1122 insertions, 0 deletions

diff --git a/guava/src/com/google/common/collect/StandardTable.java b/guava/src/com/google/common/collect/StandardTable.java
new file mode 100644
index 0000000..c7329c1
--- /dev/null
+++ b/guava/src/com/google/common/collect/StandardTable.java
@@ -0,0 +1,1122 @@
+/*
+ * Copyright (C) 2008 The Guava Authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.common.collect;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.collect.Maps.safeContainsKey;
+import static com.google.common.collect.Maps.safeGet;
+
+import com.google.common.annotations.GwtCompatible;
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
+import com.google.common.base.Supplier;
+
+import java.io.Serializable;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/**
+ * {@link Table} implementation backed by a map that associates row keys with
+ * column key / value secondary maps. This class provides rapid access to
+ * records by the row key alone or by both keys, but not by just the column key.
+ *
+ * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
+ * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
+ * all optional operations are supported. Null row keys, columns keys, and
+ * values are not supported.
+ *
+ * <p>Lookups by row key are often faster than lookups by column key, because
+ * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
+ * column(columnKey).get(rowKey)} still runs quickly, since the row key is
+ * provided. However, {@code column(columnKey).size()} takes longer, since an
+ * iteration across all row keys occurs.
+ *
+ * <p>Note that this implementation is not synchronized. If multiple threads
+ * access this table concurrently and one of the threads modifies the table, it
+ * must be synchronized externally.
+ *
+ * @author Jared Levy
+ */
+@GwtCompatible
+class StandardTable<R, C, V> implements Table<R, C, V>, Serializable {
+  @GwtTransient final Map<R, Map<C, V>> backingMap;
+  @GwtTransient final Supplier<? extends Map<C, V>> factory;
+
+  StandardTable(Map<R, Map<C, V>> backingMap,
+      Supplier<? extends Map<C, V>> factory) {
+    this.backingMap = backingMap;
+    this.factory = factory;
+  }
+
+  // Accessors
+
+  @Override public boolean contains(
+      @Nullable Object rowKey, @Nullable Object columnKey) {
+    if ((rowKey == null) || (columnKey == null)) {
+      return false;
+    }
+    Map<C, V> map = safeGet(backingMap, rowKey);
+    return map != null && safeContainsKey(map, columnKey);
+  }
+
+  @Override public boolean containsColumn(@Nullable Object columnKey) {
+    if (columnKey == null) {
+      return false;
+    }
+    for (Map<C, V> map : backingMap.values()) {
+      if (safeContainsKey(map, columnKey)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override public boolean containsRow(@Nullable Object rowKey) {
+    return rowKey != null && safeContainsKey(backingMap, rowKey);
+  }
+
+  @Override public boolean containsValue(@Nullable Object value) {
+    if (value == null) {
+      return false;
+    }
+    for (Map<C, V> map : backingMap.values()) {
+      if (map.containsValue(value)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  @Override public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
+    if ((rowKey == null) || (columnKey == null)) {
+      return null;
+    }
+    Map<C, V> map = safeGet(backingMap, rowKey);
+    return map == null ? null : safeGet(map, columnKey);
+  }
+
+  @Override public boolean isEmpty() {
+    return backingMap.isEmpty();
+  }
+
+  @Override public int size() {
+    int size = 0;
+    for (Map<C, V> map : backingMap.values()) {
+      size += map.size();
+    }
+    return size;
+  }
+
+  @Override public boolean equals(@Nullable Object obj) {
+    if (obj == this) {
+      return true;
+    }
+    if (obj instanceof Table) {
+      Table<?, ?, ?> other = (Table<?, ?, ?>) obj;
+      return cellSet().equals(other.cellSet());
+    }
+    return false;
+  }
+
+  @Override public int hashCode() {
+    return cellSet().hashCode();
+  }
+
+  /**
+   * Returns the string representation {@code rowMap().toString()}.
+   */
+  @Override public String toString() {
+    return rowMap().toString();
+  }
+
+  // Mutators
+
+  @Override public void clear() {
+    backingMap.clear();
+  }
+
+  private Map<C, V> getOrCreate(R rowKey) {
+    Map<C, V> map = backingMap.get(rowKey);
+    if (map == null) {
+      map = factory.get();
+      backingMap.put(rowKey, map);
+    }
+    return map;
+  }
+
+  @Override public V put(R rowKey, C columnKey, V value) {
+    checkNotNull(rowKey);
+    checkNotNull(columnKey);
+    checkNotNull(value);
+    return getOrCreate(rowKey).put(columnKey, value);
+  }
+
+  @Override public void putAll(
+      Table<? extends R, ? extends C, ? extends V> table) {
+    for (Cell<? extends R, ? extends C, ? extends V> cell : table.cellSet()) {
+      put(cell.getRowKey(), cell.getColumnKey(), cell.getValue());
+    }
+  }
+
+  @Override public V remove(
+      @Nullable Object rowKey, @Nullable Object columnKey) {
+    if ((rowKey == null) || (columnKey == null)) {
+      return null;
+    }
+    Map<C, V> map = safeGet(backingMap, rowKey);
+    if (map == null) {
+      return null;
+    }
+    V value = map.remove(columnKey);
+    if (map.isEmpty()) {
+      backingMap.remove(rowKey);
+    }
+    return value;
+  }
+
+  private Map<R, V> removeColumn(Object column) {
+    Map<R, V> output = new LinkedHashMap<R, V>();
+    Iterator<Entry<R, Map<C, V>>> iterator
+        = backingMap.entrySet().iterator();
+    while (iterator.hasNext()) {
+      Entry<R, Map<C, V>> entry = iterator.next();
+      V value = entry.getValue().remove(column);
+      if (value != null) {
+        output.put(entry.getKey(), value);
+        if (entry.getValue().isEmpty()) {
+          iterator.remove();
+        }
+      }
+    }
+    return output;
+  }
+
+  private boolean containsMapping(
+      Object rowKey, Object columnKey, Object value) {
+    return value != null && value.equals(get(rowKey, columnKey));
+  }
+
+  /** Remove a row key / column key / value mapping, if present. */
+  private boolean removeMapping(Object rowKey, Object columnKey, Object value) {
+    if (containsMapping(rowKey, columnKey, value)) {
+      remove(rowKey, columnKey);
+      return true;
+    }
+    return false;
+  }
+
+  // Views
+
+  /**
+   * Abstract collection whose {@code isEmpty()} returns whether the table is
+   * empty and whose {@code clear()} clears all table mappings.
+   */
+  private abstract class TableCollection<T> extends AbstractCollection<T> {
+    @Override public boolean isEmpty() {
+      return backingMap.isEmpty();
+    }
+
+    @Override public void clear() {
+      backingMap.clear();
+    }
+  }
+
+  /**
+   * Abstract set whose {@code isEmpty()} returns whether the table is empty and
+   * whose {@code clear()} clears all table mappings.
+   */
+  private abstract class TableSet<T> extends AbstractSet<T> {
+    @Override public boolean isEmpty() {
+      return backingMap.isEmpty();
+    }
+
+    @Override public void clear() {
+      backingMap.clear();
+    }
+  }
+
+  private transient CellSet cellSet;
+
+  /**
+   * {@inheritDoc}
+   *
+   * <p>The set's iterator traverses the mappings for the first row, the
+   * mappings for the second row, and so on.
+   *
+   * <p>Each cell is an immutable snapshot of a row key / column key / value
+   * mapping, taken at the time the cell is returned by a method call to the
+   * set or its iterator.
+   */
+  @Override public Set<Cell<R, C, V>> cellSet() {
+    CellSet result = cellSet;
+    return (result == null) ? cellSet = new CellSet() : result;
+  }
+
+  private class CellSet extends TableSet<Cell<R, C, V>> {
+    @Override public Iterator<Cell<R, C, V>> iterator() {
+      return new CellIterator();
+    }
+
+    @Override public int size() {
+      return StandardTable.this.size();
+    }
+
+    @Override public boolean contains(Object obj) {
+      if (obj instanceof Cell) {
+        Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
+        return containsMapping(
+            cell.getRowKey(), cell.getColumnKey(), cell.getValue());
+      }
+      return false;
+    }
+
+    @Override public boolean remove(Object obj) {
+      if (obj instanceof Cell) {
+        Cell<?, ?, ?> cell = (Cell<?, ?, ?>) obj;
+        return removeMapping(
+            cell.getRowKey(), cell.getColumnKey(), cell.getValue());
+      }
+      return false;
+    }
+  }
+
+  private class CellIterator implements Iterator<Cell<R, C, V>> {
+    final Iterator<Entry<R, Map<C, V>>> rowIterator
+        = backingMap.entrySet().iterator();
+    Entry<R, Map<C, V>> rowEntry;
+    Iterator<Entry<C, V>> columnIterator
+        = Iterators.emptyModifiableIterator();
+
+    @Override public boolean hasNext() {
+      return rowIterator.hasNext() || columnIterator.hasNext();
+    }
+
+    @Override public Cell<R, C, V> next() {
+      if (!columnIterator.hasNext()) {
+        rowEntry = rowIterator.next();
+        columnIterator = rowEntry.getValue().entrySet().iterator();
+      }
+      Entry<C, V> columnEntry = columnIterator.next();
+      return Tables.immutableCell(
+          rowEntry.getKey(), columnEntry.getKey(), columnEntry.getValue());
+    }
+
+    @Override public void remove() {
+      columnIterator.remove();
+      if (rowEntry.getValue().isEmpty()) {
+        rowIterator.remove();
+      }
+    }
+  }
+
+  @Override public Map<C, V> row(R rowKey) {
+    return new Row(rowKey);
+  }
+
+  class Row extends AbstractMap<C, V> {
+    final R rowKey;
+
+    Row(R rowKey) {
+      this.rowKey = checkNotNull(rowKey);
+    }
+
+    Map<C, V> backingRowMap;
+
+    Map<C, V> backingRowMap() {
+      return (backingRowMap == null
+              || (backingRowMap.isEmpty() && backingMap.containsKey(rowKey)))
+          ? backingRowMap = computeBackingRowMap()
+          : backingRowMap;
+    }
+
+    Map<C, V> computeBackingRowMap() {
+      return backingMap.get(rowKey);
+    }
+
+    // Call this every time we perform a removal.
+    void maintainEmptyInvariant() {
+      if (backingRowMap() != null && backingRowMap.isEmpty()) {
+        backingMap.remove(rowKey);
+        backingRowMap = null;
+      }
+    }
+
+    @Override
+    public boolean containsKey(Object key) {
+      Map<C, V> backingRowMap = backingRowMap();
+      return (key != null && backingRowMap != null)
+          && Maps.safeContainsKey(backingRowMap, key);
+    }
+
+    @Override
+    public V get(Object key) {
+      Map<C, V> backingRowMap = backingRowMap();
+      return (key != null && backingRowMap != null)
+          ? Maps.safeGet(backingRowMap, key)
+          : null;
+    }
+
+    @Override
+    public V put(C key, V value) {
+      checkNotNull(key);
+      checkNotNull(value);
+      if (backingRowMap != null && !backingRowMap.isEmpty()) {
+        return backingRowMap.put(key, value);
+      }
+      return StandardTable.this.put(rowKey, key, value);
+    }
+
+    @Override
+    public V remove(Object key) {
+      try {
+        Map<C, V> backingRowMap = backingRowMap();
+        if (backingRowMap == null) {
+          return null;
+        }
+        V result = backingRowMap.remove(key);
+        maintainEmptyInvariant();
+        return result;
+      } catch (ClassCastException e) {
+        return null;
+      }
+    }
+
+    @Override
+    public void clear() {
+      Map<C, V> backingRowMap = backingRowMap();
+      if (backingRowMap != null) {
+        backingRowMap.clear();
+      }
+      maintainEmptyInvariant();
+    }
+
+    Set<C> keySet;
+
+    @Override
+    public Set<C> keySet() {
+      Set<C> result = keySet;
+      if (result == null) {
+        return keySet = new Maps.KeySet<C, V>() {
+          @Override
+          Map<C, V> map() {
+            return Row.this;
+          }
+        };
+      }
+      return result;
+    }
+
+    Set<Entry<C, V>> entrySet;
+
+    @Override
+    public Set<Entry<C, V>> entrySet() {
+      Set<Entry<C, V>> result = entrySet;
+      if (result == null) {
+        return entrySet = new RowEntrySet();
+      }
+      return result;
+    }
+
+    private class RowEntrySet extends Maps.EntrySet<C, V> {
+      @Override
+      Map<C, V> map() {
+        return Row.this;
+      }
+
+      @Override
+      public int size() {
+        Map<C, V> map = backingRowMap();
+        return (map == null) ? 0 : map.size();
+      }
+
+      @Override
+      public Iterator<Entry<C, V>> iterator() {
+        final Map<C, V> map = backingRowMap();
+        if (map == null) {
+          return Iterators.emptyModifiableIterator();
+        }
+        final Iterator<Entry<C, V>> iterator = map.entrySet().iterator();
+        return new Iterator<Entry<C, V>>() {
+          @Override public boolean hasNext() {
+            return iterator.hasNext();
+          }
+          @Override public Entry<C, V> next() {
+            final Entry<C, V> entry = iterator.next();
+            return new ForwardingMapEntry<C, V>() {
+              @Override protected Entry<C, V> delegate() {
+                return entry;
+              }
+              @Override public V setValue(V value) {
+                return super.setValue(checkNotNull(value));
+              }
+              @Override
+              public boolean equals(Object object) {
+                // TODO(user): identify why this affects GWT tests
+                return standardEquals(object);
+              }
+            };
+          }
+
+          @Override
+          public void remove() {
+            iterator.remove();
+            maintainEmptyInvariant();
+          }
+        };
+      }
+    }
+  }
+
+  /**
+   * {@inheritDoc}
+   *
+   * <p>The returned map's views have iterators that don't support
+   * {@code remove()}.
+   */
+  @Override public Map<R, V> column(C columnKey) {
+    return new Column(columnKey);
+  }
+
+  private class Column extends Maps.ImprovedAbstractMap<R, V> {
+    final C columnKey;
+
+    Column(C columnKey) {
+      this.columnKey = checkNotNull(columnKey);
+    }
+
+    @Override public V put(R key, V value) {
+      return StandardTable.this.put(key, columnKey, value);
+    }
+
+    @Override public V get(Object key) {
+      return StandardTable.this.get(key, columnKey);
+    }
+
+    @Override public boolean containsKey(Object key) {
+      return StandardTable.this.contains(key, columnKey);
+    }
+
+    @Override public V remove(Object key) {
+      return StandardTable.this.remove(key, columnKey);
+    }
+
+    @Override public Set<Entry<R, V>> createEntrySet() {
+      return new EntrySet();
+    }
+
+    Values columnValues;
+
+    @Override public Collection<V> values() {
+      Values result = columnValues;
+      return (result == null) ? columnValues = new Values() : result;
+    }
+
+    /**
+     * Removes all {@code Column} mappings whose row key and value satisfy the
+     * given predicate.
+     */
+    boolean removePredicate(Predicate<? super Entry<R, V>> predicate) {
+      boolean changed = false;
+      Iterator<Entry<R, Map<C, V>>> iterator
+          = backingMap.entrySet().iterator();
+      while (iterator.hasNext()) {
+        Entry<R, Map<C, V>> entry = iterator.next();
+        Map<C, V> map = entry.getValue();
+        V value = map.get(columnKey);
+        if (value != null
+            && predicate.apply(
+                new ImmutableEntry<R, V>(entry.getKey(), value))) {
+          map.remove(columnKey);
+          changed = true;
+          if (map.isEmpty()) {
+            iterator.remove();
+          }
+        }
+      }
+      return changed;
+    }
+
+    class EntrySet extends Sets.ImprovedAbstractSet<Entry<R, V>> {
+      @Override public Iterator<Entry<R, V>> iterator() {
+        return new EntrySetIterator();
+      }
+
+      @Override public int size() {
+        int size = 0;
+        for (Map<C, V> map : backingMap.values()) {
+          if (map.containsKey(columnKey)) {
+            size++;
+          }
+        }
+        return size;
+      }
+
+      @Override public boolean isEmpty() {
+        return !containsColumn(columnKey);
+      }
+
+      @Override public void clear() {
+        Predicate<Entry<R, V>> predicate = Predicates.alwaysTrue();
+        removePredicate(predicate);
+      }
+
+      @Override public boolean contains(Object o) {
+        if (o instanceof Entry) {
+          Entry<?, ?> entry = (Entry<?, ?>) o;
+          return containsMapping(entry.getKey(), columnKey, entry.getValue());
+        }
+        return false;
+      }
+
+      @Override public boolean remove(Object obj) {
+        if (obj instanceof Entry) {
+          Entry<?, ?> entry = (Entry<?, ?>) obj;
+          return removeMapping(entry.getKey(), columnKey, entry.getValue());
+        }
+        return false;
+      }
+
+      @Override public boolean retainAll(Collection<?> c) {
+        return removePredicate(Predicates.not(Predicates.in(c)));
+      }
+    }
+
+    class EntrySetIterator extends AbstractIterator<Entry<R, V>> {
+      final Iterator<Entry<R, Map<C, V>>> iterator
+          = backingMap.entrySet().iterator();
+      @Override protected Entry<R, V> computeNext() {
+        while (iterator.hasNext()) {
+          final Entry<R, Map<C, V>> entry = iterator.next();
+          if (entry.getValue().containsKey(columnKey)) {
+            return new AbstractMapEntry<R, V>() {
+              @Override public R getKey() {
+                return entry.getKey();
+              }
+              @Override public V getValue() {
+                return entry.getValue().get(columnKey);
+              }
+              @Override public V setValue(V value) {
+                return entry.getValue().put(columnKey, checkNotNull(value));
+              }
+            };
+          }
+        }
+        return endOfData();
+      }
+    }
+
+    KeySet keySet;
+
+    @Override public Set<R> keySet() {
+      KeySet result = keySet;
+      return result == null ? keySet = new KeySet() : result;
+    }
+
+    class KeySet extends Sets.ImprovedAbstractSet<R> {
+      @Override public Iterator<R> iterator() {
+        return Maps.keyIterator(Column.this.entrySet().iterator());
+      }
+
+      @Override public int size() {
+        return entrySet().size();
+      }
+
+      @Override public boolean isEmpty() {
+        return !containsColumn(columnKey);
+      }
+
+      @Override public boolean contains(Object obj) {
+        return StandardTable.this.contains(obj, columnKey);
+      }
+
+      @Override public boolean remove(Object obj) {
+        return StandardTable.this.remove(obj, columnKey) != null;
+      }
+
+      @Override public void clear() {
+        entrySet().clear();
+      }
+
+      @Override public boolean retainAll(final Collection<?> c) {
+        checkNotNull(c);
+        Predicate<Entry<R, V>> predicate = new Predicate<Entry<R, V>>() {
+          @Override
+          public boolean apply(Entry<R, V> entry) {
+            return !c.contains(entry.getKey());
+          }
+        };
+        return removePredicate(predicate);
+      }
+    }
+
+    class Values extends AbstractCollection<V> {
+      @Override public Iterator<V> iterator() {
+        return Maps.valueIterator(Column.this.entrySet().iterator());
+      }
+
+      @Override public int size() {
+        return entrySet().size();
+      }
+
+      @Override public boolean isEmpty() {
+        return !containsColumn(columnKey);
+      }
+
+      @Override public void clear() {
+        entrySet().clear();
+      }
+
+      @Override public boolean remove(Object obj) {
+        if (obj == null) {
+          return false;
+        }
+        Iterator<Map<C, V>> iterator = backingMap.values().iterator();
+        while (iterator.hasNext()) {
+          Map<C, V> map = iterator.next();
+          if (map.entrySet().remove(
+              new ImmutableEntry<C, Object>(columnKey, obj))) {
+            if (map.isEmpty()) {
+              iterator.remove();
+            }
+            return true;
+          }
+        }
+        return false;
+      }
+
+      @Override public boolean removeAll(final Collection<?> c) {
+        checkNotNull(c);
+        Predicate<Entry<R, V>> predicate = new Predicate<Entry<R, V>>() {
+          @Override
+          public boolean apply(Entry<R, V> entry) {
+            return c.contains(entry.getValue());
+          }
+        };
+        return removePredicate(predicate);
+      }
+
+      @Override public boolean retainAll(final Collection<?> c) {
+        checkNotNull(c);
+        Predicate<Entry<R, V>> predicate = new Predicate<Entry<R, V>>() {
+          @Override
+          public boolean apply(Entry<R, V> entry) {
+            return !c.contains(entry.getValue());
+          }
+        };
+        return removePredicate(predicate);
+      }
+    }
+  }
+
+  private transient RowKeySet rowKeySet;
+
+  @Override public Set<R> rowKeySet() {
+    Set<R> result = rowKeySet;
+    return (result == null) ? rowKeySet = new RowKeySet() : result;
+  }
+
+  class RowKeySet extends TableSet<R> {
+    @Override public Iterator<R> iterator() {
+      return Maps.keyIterator(rowMap().entrySet().iterator());
+    }
+
+    @Override public int size() {
+      return backingMap.size();
+    }
+
+    @Override public boolean contains(Object obj) {
+      return containsRow(obj);
+    }
+
+    @Override public boolean remove(Object obj) {
+      return (obj != null) && backingMap.remove(obj) != null;
+    }
+  }
+
+  private transient Set<C> columnKeySet;
+
+  /**
+   * {@inheritDoc}
+   *
+   * <p>The returned set has an iterator that does not support {@code remove()}.
+   *
+   * <p>The set's iterator traverses the columns of the first row, the
+   * columns of the second row, etc., skipping any columns that have
+   * appeared previously.
+   */
+  @Override
+  public Set<C> columnKeySet() {
+    Set<C> result = columnKeySet;
+    return (result == null) ? columnKeySet = new ColumnKeySet() : result;
+  }
+
+  private class ColumnKeySet extends TableSet<C> {
+    @Override public Iterator<C> iterator() {
+      return createColumnKeyIterator();
+    }
+
+    @Override public int size() {
+      return Iterators.size(iterator());
+    }
+
+    @Override public boolean remove(Object obj) {
+      if (obj == null) {
+        return false;
+      }
+      boolean changed = false;
+      Iterator<Map<C, V>> iterator = backingMap.values().iterator();
+      while (iterator.hasNext()) {
+        Map<C, V> map = iterator.next();
+        if (map.keySet().remove(obj)) {
+          changed = true;
+          if (map.isEmpty()) {
+            iterator.remove();
+          }
+        }
+      }
+      return changed;
+    }
+
+    @Override public boolean removeAll(Collection<?> c) {
+      checkNotNull(c);
+      boolean changed = false;
+      Iterator<Map<C, V>> iterator = backingMap.values().iterator();
+      while (iterator.hasNext()) {
+        Map<C, V> map = iterator.next();
+        // map.keySet().removeAll(c) can throw a NPE when map is a TreeMap with
+        // natural ordering and c contains a null.
+        if (Iterators.removeAll(map.keySet().iterator(), c)) {
+          changed = true;
+          if (map.isEmpty()) {
+            iterator.remove();
+          }
+        }
+      }
+      return changed;
+    }
+
+    @Override public boolean retainAll(Collection<?> c) {
+      checkNotNull(c);
+      boolean changed = false;
+      Iterator<Map<C, V>> iterator = backingMap.values().iterator();
+      while (iterator.hasNext()) {
+        Map<C, V> map = iterator.next();
+        if (map.keySet().retainAll(c)) {
+          changed = true;
+          if (map.isEmpty()) {
+            iterator.remove();
+          }
+        }
+      }
+      return changed;
+    }
+
+    @Override public boolean contains(Object obj) {
+      if (obj == null) {
+        return false;
+      }
+      for (Map<C, V> map : backingMap.values()) {
+        if (map.containsKey(obj)) {
+          return true;
+        }
+      }
+      return false;
+    }
+  }
+
+  /**
+   * Creates an iterator that returns each column value with duplicates
+   * omitted.
+   */
+  Iterator<C> createColumnKeyIterator() {
+    return new ColumnKeyIterator();
+  }
+
+  private class ColumnKeyIterator extends AbstractIterator<C> {
+    // Use the same map type to support TreeMaps with comparators that aren't
+    // consistent with equals().
+    final Map<C, V> seen = factory.get();
+    final Iterator<Map<C, V>> mapIterator = backingMap.values().iterator();
+    Iterator<Entry<C, V>> entryIterator = Iterators.emptyIterator();
+
+    @Override protected C computeNext() {
+      while (true) {
+        if (entryIterator.hasNext()) {
+          Entry<C, V> entry = entryIterator.next();
+          if (!seen.containsKey(entry.getKey())) {
+            seen.put(entry.getKey(), entry.getValue());
+            return entry.getKey();
+          }
+        } else if (mapIterator.hasNext()) {
+          entryIterator = mapIterator.next().entrySet().iterator();
+        } else {
+          return endOfData();
+        }
+      }
+    }
+  }
+
+  private transient Values values;
+
+  /**
+   * {@inheritDoc}
+   *
+   * <p>The collection's iterator traverses the values for the first row,
+   * the values for the second row, and so on.
+   */
+  @Override public Collection<V> values() {
+    Values result = values;
+    return (result == null) ? values = new Values() : result;
+  }
+
+  private class Values extends TableCollection<V> {
+    @Override public Iterator<V> iterator() {
+      return new TransformedIterator<Cell<R, C, V>, V>(cellSet().iterator()) {
+        @Override
+        V transform(Cell<R, C, V> cell) {
+          return cell.getValue();
+        }
+      };
+    }
+
+    @Override public int size() {
+      return StandardTable.this.size();
+    }
+  }
+
+  private transient RowMap rowMap;
+
+  @Override public Map<R, Map<C, V>> rowMap() {
+    RowMap result = rowMap;
+    return (result == null) ? rowMap = new RowMap() : result;
+  }
+
+  class RowMap extends Maps.ImprovedAbstractMap<R, Map<C, V>> {
+    @Override public boolean containsKey(Object key) {
+      return containsRow(key);
+    }
+
+    // performing cast only when key is in backing map and has the correct type
+    @SuppressWarnings("unchecked")
+    @Override public Map<C, V> get(Object key) {
+      return containsRow(key) ? row((R) key) : null;
+    }
+
+    @Override public Set<R> keySet() {
+      return rowKeySet();
+    }
+
+    @Override public Map<C, V> remove(Object key) {
+      return (key == null) ? null : backingMap.remove(key);
+    }
+
+    @Override protected Set<Entry<R, Map<C, V>>> createEntrySet() {
+      return new EntrySet();
+    }
+
+    class EntrySet extends TableSet<Entry<R, Map<C, V>>> {
+      @Override public Iterator<Entry<R, Map<C, V>>> iterator() {
+        return new TransformedIterator<R, Entry<R, Map<C, V>>>(
+            backingMap.keySet().iterator()) {
+          @Override
+          Entry<R, Map<C, V>> transform(R rowKey) {
+            return new ImmutableEntry<R, Map<C, V>>(rowKey, row(rowKey));
+          }
+        };
+      }
+
+      @Override public int size() {
+        return backingMap.size();
+      }
+
+      @Override public boolean contains(Object obj) {
+        if (obj instanceof Entry) {
+          Entry<?, ?> entry = (Entry<?, ?>) obj;
+          return entry.getKey() != null
+              && entry.getValue() instanceof Map
+              && Collections2.safeContains(backingMap.entrySet(), entry);
+        }
+        return false;
+      }
+
+      @Override public boolean remove(Object obj) {
+        if (obj instanceof Entry) {
+          Entry<?, ?> entry = (Entry<?, ?>) obj;
+          return entry.getKey() != null
+              && entry.getValue() instanceof Map
+              && backingMap.entrySet().remove(entry);
+        }
+        return false;
+      }
+    }
+  }
+
+  private transient ColumnMap columnMap;
+
+  @Override public Map<C, Map<R, V>> columnMap() {
+    ColumnMap result = columnMap;
+    return (result == null) ? columnMap = new ColumnMap() : result;
+  }
+
+  private class ColumnMap extends Maps.ImprovedAbstractMap<C, Map<R, V>> {
+    // The cast to C occurs only when the key is in the map, implying that it
+    // has the correct type.
+    @SuppressWarnings("unchecked")
+    @Override public Map<R, V> get(Object key) {
+      return containsColumn(key) ? column((C) key) : null;
+    }
+
+    @Override public boolean containsKey(Object key) {
+      return containsColumn(key);
+    }
+
+    @Override public Map<R, V> remove(Object key) {
+      return containsColumn(key) ? removeColumn(key) : null;
+    }
+
+    @Override public Set<Entry<C, Map<R, V>>> createEntrySet() {
+      return new ColumnMapEntrySet();
+    }
+
+    @Override public Set<C> keySet() {
+      return columnKeySet();
+    }
+
+    ColumnMapValues columnMapValues;
+
+    @Override public Collection<Map<R, V>> values() {
+      ColumnMapValues result = columnMapValues;
+      return
+          (result == null) ? columnMapValues = new ColumnMapValues() : result;
+    }
+
+    class ColumnMapEntrySet extends TableSet<Entry<C, Map<R, V>>> {
+      @Override public Iterator<Entry<C, Map<R, V>>> iterator() {
+        return new TransformedIterator<C, Entry<C, Map<R, V>>>(
+            columnKeySet().iterator()) {
+          @Override
+          Entry<C, Map<R, V>> transform(C columnKey) {
+            return new ImmutableEntry<C, Map<R, V>>(
+                columnKey, column(columnKey));
+          }
+        };
+      }
+
+      @Override public int size() {
+        return columnKeySet().size();
+      }
+
+      @Override public boolean contains(Object obj) {
+        if (obj instanceof Entry) {
+          Entry<?, ?> entry = (Entry<?, ?>) obj;
+          if (containsColumn(entry.getKey())) {
+            // The cast to C occurs only when the key is in the map, implying
+            // that it has the correct type.
+            @SuppressWarnings("unchecked")
+            C columnKey = (C) entry.getKey();
+            return get(columnKey).equals(entry.getValue());
+          }
+        }
+        return false;
+      }
+
+      @Override public boolean remove(Object obj) {
+        if (contains(obj)) {
+          Entry<?, ?> entry = (Entry<?, ?>) obj;
+          removeColumn(entry.getKey());
+          return true;
+        }
+        return false;
+      }
+
+      @Override public boolean removeAll(Collection<?> c) {
+        boolean changed = false;
+        for (Object obj : c) {
+          changed |= remove(obj);
+        }
+        return changed;
+      }
+
+      @Override public boolean retainAll(Collection<?> c) {
+        boolean changed = false;
+        for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
+          if (!c.contains(new ImmutableEntry<C, Map<R, V>>(
+              columnKey, column(columnKey)))) {
+            removeColumn(columnKey);
+            changed = true;
+          }
+        }
+        return changed;
+      }
+    }
+
+    private class ColumnMapValues extends TableCollection<Map<R, V>> {
+      @Override public Iterator<Map<R, V>> iterator() {
+        return Maps.valueIterator(ColumnMap.this.entrySet().iterator());
+      }
+
+      @Override public boolean remove(Object obj) {
+        for (Entry<C, Map<R, V>> entry : ColumnMap.this.entrySet()) {
+          if (entry.getValue().equals(obj)) {
+            removeColumn(entry.getKey());
+            return true;
+          }
+        }
+        return false;
+      }
+
+      @Override public boolean removeAll(Collection<?> c) {
+        checkNotNull(c);
+        boolean changed = false;
+        for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
+          if (c.contains(column(columnKey))) {
+            removeColumn(columnKey);
+            changed = true;
+          }
+        }
+        return changed;
+      }
+
+      @Override public boolean retainAll(Collection<?> c) {
+        checkNotNull(c);
+        boolean changed = false;
+        for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
+          if (!c.contains(column(columnKey))) {
+            removeColumn(columnKey);
+            changed = true;
+          }
+        }
+        return changed;
+      }
+
+      @Override public int size() {
+        return columnKeySet().size();
+      }
+    }
+  }
+
+  private static final long serialVersionUID = 0;
+}