/*
 * 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.base.Predicates.alwaysTrue;
import static com.google.common.base.Predicates.equalTo;
import static com.google.common.base.Predicates.in;
import static com.google.common.base.Predicates.not;
import static com.google.common.collect.Maps.safeContainsKey;
import static com.google.common.collect.Maps.safeGet;

import java.io.Serializable;
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;

import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import com.google.common.base.Predicate;
import com.google.common.base.Supplier;
import com.google.common.collect.Maps.ImprovedAbstractMap;
import com.google.common.collect.Sets.ImprovedAbstractSet;

/**
 * {@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> extends AbstractTable<R, C, V> implements 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) {
		return rowKey != null && columnKey != null && super.contains(rowKey, 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) {
		return value != null && super.containsValue(value);
	}

	@Override
	public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
		return (rowKey == null || columnKey == null) ? null : super.get(rowKey, 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;
	}

	// 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 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 set whose {@code isEmpty()} returns whether the table is empty and
	 * whose {@code clear()} clears all table mappings.
	 */
	private abstract class TableSet<T> extends ImprovedAbstractSet<T> {
		@Override
		public boolean isEmpty() {
			return backingMap.isEmpty();
		}

		@Override
		public void clear() {
			backingMap.clear();
		}
	}

	/**
	 * {@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() {
		return super.cellSet();
	}

	@Override
	Iterator<Cell<R, C, V>> cellIterator() {
		return new CellIterator();
	}

	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 ImprovedAbstractMap<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) {
			Map<C, V> backingRowMap = backingRowMap();
			if (backingRowMap == null) {
				return null;
			}
			V result = Maps.safeRemove(backingRowMap, key);
			maintainEmptyInvariant();
			return result;
		}

		@Override
		public void clear() {
			Map<C, V> backingRowMap = backingRowMap();
			if (backingRowMap != null) {
				backingRowMap.clear();
			}
			maintainEmptyInvariant();
		}

		@Override
		protected Set<Entry<C, V>> createEntrySet() {
			return new RowEntrySet();
		}

		private final 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 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);
		}

		/**
		 * Removes all {@code Column} mappings whose row key and value satisfy the given
		 * predicate.
		 */
		boolean removeFromColumnIf(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(Maps.immutableEntry(entry.getKey(), value))) {
					map.remove(columnKey);
					changed = true;
					if (map.isEmpty()) {
						iterator.remove();
					}
				}
			}
			return changed;
		}

		@Override
		Set<Entry<R, V>> createEntrySet() {
			return new EntrySet();
		}

		private class EntrySet extends 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() {
				removeFromColumnIf(alwaysTrue());
			}

			@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 removeFromColumnIf(not(in(c)));
			}
		}

		private 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();
			}
		}

		@Override
		Set<R> createKeySet() {
			return new KeySet();
		}

		private class KeySet extends Maps.KeySet<R, V> {
			KeySet() {
				super(Column.this);
			}

			@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 boolean retainAll(final Collection<?> c) {
				return removeFromColumnIf(Maps.<R>keyPredicateOnEntries(not(in(c))));
			}
		}

		@Override
		Collection<V> createValues() {
			return new Values();
		}

		private class Values extends Maps.Values<R, V> {
			Values() {
				super(Column.this);
			}

			@Override
			public boolean remove(Object obj) {
				return obj != null && removeFromColumnIf(Maps.<V>valuePredicateOnEntries(equalTo(obj)));
			}

			@Override
			public boolean removeAll(final Collection<?> c) {
				return removeFromColumnIf(Maps.<V>valuePredicateOnEntries(in(c)));
			}

			@Override
			public boolean retainAll(final Collection<?> c) {
				return removeFromColumnIf(Maps.<V>valuePredicateOnEntries(not(in(c))));
			}
		}
	}

	@Override
	public Set<R> rowKeySet() {
		return rowMap().keySet();
	}

	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) {
			return containsColumn(obj);
		}
	}

	/**
	 * 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();
				}
			}
		}
	}

	/**
	 * {@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() {
		return super.values();
	}

	private transient Map<R, Map<C, V>> rowMap;

	@Override
	public Map<R, Map<C, V>> rowMap() {
		Map<R, Map<C, V>> result = rowMap;
		return (result == null) ? rowMap = createRowMap() : result;
	}

	Map<R, Map<C, V>> createRowMap() {
		return new RowMap();
	}

	class RowMap extends 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 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 Maps.asMapEntryIterator(backingMap.keySet(), new Function<R, Map<C, V>>() {
					@Override
					public Map<C, V> apply(R rowKey) {
						return 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 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();
		}

		@Override
		Collection<Map<R, V>> createValues() {
			return new ColumnMapValues();
		}

		class ColumnMapEntrySet extends TableSet<Entry<C, Map<R, V>>> {
			@Override
			public Iterator<Entry<C, Map<R, V>>> iterator() {
				return Maps.asMapEntryIterator(columnKeySet(), new Function<C, Map<R, V>>() {
					@Override
					public Map<R, V> apply(C columnKey) {
						return 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) {
				/*
				 * We can't inherit the normal implementation (which calls
				 * Sets.removeAllImpl(Set, *Collection*) because, under some circumstances, it
				 * attempts to call columnKeySet().iterator().remove, which is unsupported.
				 */
				checkNotNull(c);
				return Sets.removeAllImpl(this, c.iterator());
			}

			@Override
			public boolean retainAll(Collection<?> c) {
				checkNotNull(c);
				boolean changed = false;
				for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
					if (!c.contains(Maps.immutableEntry(columnKey, column(columnKey)))) {
						removeColumn(columnKey);
						changed = true;
					}
				}
				return changed;
			}
		}

		private class ColumnMapValues extends Maps.Values<C, Map<R, V>> {
			ColumnMapValues() {
				super(ColumnMap.this);
			}

			@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;
			}
		}
	}

	private static final long serialVersionUID = 0;
}
