View Javadoc
1   /*
2    * Copyright (C) 2008 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  import static com.google.common.base.Predicates.alwaysTrue;
21  import static com.google.common.base.Predicates.equalTo;
22  import static com.google.common.base.Predicates.in;
23  import static com.google.common.base.Predicates.not;
24  import static com.google.common.collect.Maps.safeContainsKey;
25  import static com.google.common.collect.Maps.safeGet;
26  
27  import com.google.common.annotations.GwtCompatible;
28  import com.google.common.base.Function;
29  import com.google.common.base.Predicate;
30  import com.google.common.base.Supplier;
31  import com.google.common.collect.Maps.IteratorBasedAbstractMap;
32  import com.google.common.collect.Maps.ViewCachingAbstractMap;
33  import com.google.common.collect.Sets.ImprovedAbstractSet;
34  import com.google.errorprone.annotations.CanIgnoreReturnValue;
35  import com.google.j2objc.annotations.WeakOuter;
36  import java.io.Serializable;
37  import java.util.Collection;
38  import java.util.Iterator;
39  import java.util.LinkedHashMap;
40  import java.util.Map;
41  import java.util.Map.Entry;
42  import java.util.Set;
43  import java.util.Spliterator;
44  import java.util.Spliterators;
45  import javax.annotation.Nullable;
46  
47  /**
48   * {@link Table} implementation backed by a map that associates row keys with
49   * column key / value secondary maps. This class provides rapid access to
50   * records by the row key alone or by both keys, but not by just the column key.
51   *
52   * <p>The views returned by {@link #column}, {@link #columnKeySet()}, and {@link
53   * #columnMap()} have iterators that don't support {@code remove()}. Otherwise,
54   * all optional operations are supported. Null row keys, columns keys, and
55   * values are not supported.
56   *
57   * <p>Lookups by row key are often faster than lookups by column key, because
58   * the data is stored in a {@code Map<R, Map<C, V>>}. A method call like {@code
59   * column(columnKey).get(rowKey)} still runs quickly, since the row key is
60   * provided. However, {@code column(columnKey).size()} takes longer, since an
61   * iteration across all row keys occurs.
62   *
63   * <p>Note that this implementation is not synchronized. If multiple threads
64   * access this table concurrently and one of the threads modifies the table, it
65   * must be synchronized externally.
66   *
67   * @author Jared Levy
68   */
69  @GwtCompatible
70  class StandardTable<R, C, V> extends AbstractTable<R, C, V> implements Serializable {
71    @GwtTransient final Map<R, Map<C, V>> backingMap;
72    @GwtTransient final Supplier<? extends Map<C, V>> factory;
73  
74    StandardTable(Map<R, Map<C, V>> backingMap, Supplier<? extends Map<C, V>> factory) {
75      this.backingMap = backingMap;
76      this.factory = factory;
77    }
78  
79    // Accessors
80  
81    @Override
82    public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) {
83      return rowKey != null && columnKey != null && super.contains(rowKey, columnKey);
84    }
85  
86    @Override
87    public boolean containsColumn(@Nullable Object columnKey) {
88      if (columnKey == null) {
89        return false;
90      }
91      for (Map<C, V> map : backingMap.values()) {
92        if (safeContainsKey(map, columnKey)) {
93          return true;
94        }
95      }
96      return false;
97    }
98  
99    @Override
100   public boolean containsRow(@Nullable Object rowKey) {
101     return rowKey != null && safeContainsKey(backingMap, rowKey);
102   }
103 
104   @Override
105   public boolean containsValue(@Nullable Object value) {
106     return value != null && super.containsValue(value);
107   }
108 
109   @Override
110   public V get(@Nullable Object rowKey, @Nullable Object columnKey) {
111     return (rowKey == null || columnKey == null) ? null : super.get(rowKey, columnKey);
112   }
113 
114   @Override
115   public boolean isEmpty() {
116     return backingMap.isEmpty();
117   }
118 
119   @Override
120   public int size() {
121     int size = 0;
122     for (Map<C, V> map : backingMap.values()) {
123       size += map.size();
124     }
125     return size;
126   }
127 
128   // Mutators
129 
130   @Override
131   public void clear() {
132     backingMap.clear();
133   }
134 
135   private Map<C, V> getOrCreate(R rowKey) {
136     Map<C, V> map = backingMap.get(rowKey);
137     if (map == null) {
138       map = factory.get();
139       backingMap.put(rowKey, map);
140     }
141     return map;
142   }
143 
144   @CanIgnoreReturnValue
145   @Override
146   public V put(R rowKey, C columnKey, V value) {
147     checkNotNull(rowKey);
148     checkNotNull(columnKey);
149     checkNotNull(value);
150     return getOrCreate(rowKey).put(columnKey, value);
151   }
152 
153   @CanIgnoreReturnValue
154   @Override
155   public V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
156     if ((rowKey == null) || (columnKey == null)) {
157       return null;
158     }
159     Map<C, V> map = safeGet(backingMap, rowKey);
160     if (map == null) {
161       return null;
162     }
163     V value = map.remove(columnKey);
164     if (map.isEmpty()) {
165       backingMap.remove(rowKey);
166     }
167     return value;
168   }
169 
170   @CanIgnoreReturnValue
171   private Map<R, V> removeColumn(Object column) {
172     Map<R, V> output = new LinkedHashMap<>();
173     Iterator<Entry<R, Map<C, V>>> iterator = backingMap.entrySet().iterator();
174     while (iterator.hasNext()) {
175       Entry<R, Map<C, V>> entry = iterator.next();
176       V value = entry.getValue().remove(column);
177       if (value != null) {
178         output.put(entry.getKey(), value);
179         if (entry.getValue().isEmpty()) {
180           iterator.remove();
181         }
182       }
183     }
184     return output;
185   }
186 
187   private boolean containsMapping(Object rowKey, Object columnKey, Object value) {
188     return value != null && value.equals(get(rowKey, columnKey));
189   }
190 
191   /** Remove a row key / column key / value mapping, if present. */
192   private boolean removeMapping(Object rowKey, Object columnKey, Object value) {
193     if (containsMapping(rowKey, columnKey, value)) {
194       remove(rowKey, columnKey);
195       return true;
196     }
197     return false;
198   }
199 
200   // Views
201 
202   /**
203    * Abstract set whose {@code isEmpty()} returns whether the table is empty and
204    * whose {@code clear()} clears all table mappings.
205    */
206   @WeakOuter
207   private abstract class TableSet<T> extends ImprovedAbstractSet<T> {
208     @Override
209     public boolean isEmpty() {
210       return backingMap.isEmpty();
211     }
212 
213     @Override
214     public void clear() {
215       backingMap.clear();
216     }
217   }
218 
219   /**
220    * {@inheritDoc}
221    *
222    * <p>The set's iterator traverses the mappings for the first row, the
223    * mappings for the second row, and so on.
224    *
225    * <p>Each cell is an immutable snapshot of a row key / column key / value
226    * mapping, taken at the time the cell is returned by a method call to the
227    * set or its iterator.
228    */
229   @Override
230   public Set<Cell<R, C, V>> cellSet() {
231     return super.cellSet();
232   }
233 
234   @Override
235   Iterator<Cell<R, C, V>> cellIterator() {
236     return new CellIterator();
237   }
238 
239   private class CellIterator implements Iterator<Cell<R, C, V>> {
240     final Iterator<Entry<R, Map<C, V>>> rowIterator = backingMap.entrySet().iterator();
241     Entry<R, Map<C, V>> rowEntry;
242     Iterator<Entry<C, V>> columnIterator = Iterators.emptyModifiableIterator();
243 
244     @Override
245     public boolean hasNext() {
246       return rowIterator.hasNext() || columnIterator.hasNext();
247     }
248 
249     @Override
250     public Cell<R, C, V> next() {
251       if (!columnIterator.hasNext()) {
252         rowEntry = rowIterator.next();
253         columnIterator = rowEntry.getValue().entrySet().iterator();
254       }
255       Entry<C, V> columnEntry = columnIterator.next();
256       return Tables.immutableCell(rowEntry.getKey(), columnEntry.getKey(), columnEntry.getValue());
257     }
258 
259     @Override
260     public void remove() {
261       columnIterator.remove();
262       if (rowEntry.getValue().isEmpty()) {
263         rowIterator.remove();
264       }
265     }
266   }
267 
268   @Override
269   Spliterator<Cell<R, C, V>> cellSpliterator() {
270     return CollectSpliterators.flatMap(
271         backingMap.entrySet().spliterator(),
272         (Map.Entry<R, Map<C, V>> rowEntry) ->
273             CollectSpliterators.map(
274                 rowEntry.getValue().entrySet().spliterator(),
275                 (Map.Entry<C, V> columnEntry) ->
276                     Tables.immutableCell(
277                         rowEntry.getKey(), columnEntry.getKey(), columnEntry.getValue())),
278         Spliterator.DISTINCT | Spliterator.SIZED,
279         size());
280   }
281 
282   @Override
283   public Map<C, V> row(R rowKey) {
284     return new Row(rowKey);
285   }
286 
287   class Row extends IteratorBasedAbstractMap<C, V> {
288     final R rowKey;
289 
290     Row(R rowKey) {
291       this.rowKey = checkNotNull(rowKey);
292     }
293 
294     Map<C, V> backingRowMap;
295 
296     Map<C, V> backingRowMap() {
297       return (backingRowMap == null || (backingRowMap.isEmpty() && backingMap.containsKey(rowKey)))
298           ? backingRowMap = computeBackingRowMap()
299           : backingRowMap;
300     }
301 
302     Map<C, V> computeBackingRowMap() {
303       return backingMap.get(rowKey);
304     }
305 
306     // Call this every time we perform a removal.
307     void maintainEmptyInvariant() {
308       if (backingRowMap() != null && backingRowMap.isEmpty()) {
309         backingMap.remove(rowKey);
310         backingRowMap = null;
311       }
312     }
313 
314     @Override
315     public boolean containsKey(Object key) {
316       Map<C, V> backingRowMap = backingRowMap();
317       return (key != null && backingRowMap != null) && Maps.safeContainsKey(backingRowMap, key);
318     }
319 
320     @Override
321     public V get(Object key) {
322       Map<C, V> backingRowMap = backingRowMap();
323       return (key != null && backingRowMap != null) ? Maps.safeGet(backingRowMap, key) : null;
324     }
325 
326     @Override
327     public V put(C key, V value) {
328       checkNotNull(key);
329       checkNotNull(value);
330       if (backingRowMap != null && !backingRowMap.isEmpty()) {
331         return backingRowMap.put(key, value);
332       }
333       return StandardTable.this.put(rowKey, key, value);
334     }
335 
336     @Override
337     public V remove(Object key) {
338       Map<C, V> backingRowMap = backingRowMap();
339       if (backingRowMap == null) {
340         return null;
341       }
342       V result = Maps.safeRemove(backingRowMap, key);
343       maintainEmptyInvariant();
344       return result;
345     }
346 
347     @Override
348     public void clear() {
349       Map<C, V> backingRowMap = backingRowMap();
350       if (backingRowMap != null) {
351         backingRowMap.clear();
352       }
353       maintainEmptyInvariant();
354     }
355 
356     @Override
357     public int size() {
358       Map<C, V> map = backingRowMap();
359       return (map == null) ? 0 : map.size();
360     }
361 
362     @Override
363     Iterator<Entry<C, V>> entryIterator() {
364       final Map<C, V> map = backingRowMap();
365       if (map == null) {
366         return Iterators.emptyModifiableIterator();
367       }
368       final Iterator<Entry<C, V>> iterator = map.entrySet().iterator();
369       return new Iterator<Entry<C, V>>() {
370         @Override
371         public boolean hasNext() {
372           return iterator.hasNext();
373         }
374 
375         @Override
376         public Entry<C, V> next() {
377           return wrapEntry(iterator.next());
378         }
379 
380         @Override
381         public void remove() {
382           iterator.remove();
383           maintainEmptyInvariant();
384         }
385       };
386     }
387 
388     @Override
389     Spliterator<Entry<C, V>> entrySpliterator() {
390       Map<C, V> map = backingRowMap();
391       if (map == null) {
392         return Spliterators.emptySpliterator();
393       }
394       return CollectSpliterators.map(map.entrySet().spliterator(), this::wrapEntry);
395     }
396 
397     Entry<C, V> wrapEntry(final Entry<C, V> entry) {
398       return new ForwardingMapEntry<C, V>() {
399         @Override
400         protected Entry<C, V> delegate() {
401           return entry;
402         }
403 
404         @Override
405         public V setValue(V value) {
406           return super.setValue(checkNotNull(value));
407         }
408 
409         @Override
410         public boolean equals(Object object) {
411           // TODO(lowasser): identify why this affects GWT tests
412           return standardEquals(object);
413         }
414       };
415     }
416   }
417 
418   /**
419    * {@inheritDoc}
420    *
421    * <p>The returned map's views have iterators that don't support
422    * {@code remove()}.
423    */
424   @Override
425   public Map<R, V> column(C columnKey) {
426     return new Column(columnKey);
427   }
428 
429   private class Column extends ViewCachingAbstractMap<R, V> {
430     final C columnKey;
431 
432     Column(C columnKey) {
433       this.columnKey = checkNotNull(columnKey);
434     }
435 
436     @Override
437     public V put(R key, V value) {
438       return StandardTable.this.put(key, columnKey, value);
439     }
440 
441     @Override
442     public V get(Object key) {
443       return StandardTable.this.get(key, columnKey);
444     }
445 
446     @Override
447     public boolean containsKey(Object key) {
448       return StandardTable.this.contains(key, columnKey);
449     }
450 
451     @Override
452     public V remove(Object key) {
453       return StandardTable.this.remove(key, columnKey);
454     }
455 
456     /**
457      * Removes all {@code Column} mappings whose row key and value satisfy the
458      * given predicate.
459      */
460     @CanIgnoreReturnValue
461     boolean removeFromColumnIf(Predicate<? super Entry<R, V>> predicate) {
462       boolean changed = false;
463       Iterator<Entry<R, Map<C, V>>> iterator = backingMap.entrySet().iterator();
464       while (iterator.hasNext()) {
465         Entry<R, Map<C, V>> entry = iterator.next();
466         Map<C, V> map = entry.getValue();
467         V value = map.get(columnKey);
468         if (value != null && predicate.apply(Maps.immutableEntry(entry.getKey(), value))) {
469           map.remove(columnKey);
470           changed = true;
471           if (map.isEmpty()) {
472             iterator.remove();
473           }
474         }
475       }
476       return changed;
477     }
478 
479     @Override
480     Set<Entry<R, V>> createEntrySet() {
481       return new EntrySet();
482     }
483 
484     @WeakOuter
485     private class EntrySet extends ImprovedAbstractSet<Entry<R, V>> {
486       @Override
487       public Iterator<Entry<R, V>> iterator() {
488         return new EntrySetIterator();
489       }
490 
491       @Override
492       public int size() {
493         int size = 0;
494         for (Map<C, V> map : backingMap.values()) {
495           if (map.containsKey(columnKey)) {
496             size++;
497           }
498         }
499         return size;
500       }
501 
502       @Override
503       public boolean isEmpty() {
504         return !containsColumn(columnKey);
505       }
506 
507       @Override
508       public void clear() {
509         removeFromColumnIf(alwaysTrue());
510       }
511 
512       @Override
513       public boolean contains(Object o) {
514         if (o instanceof Entry) {
515           Entry<?, ?> entry = (Entry<?, ?>) o;
516           return containsMapping(entry.getKey(), columnKey, entry.getValue());
517         }
518         return false;
519       }
520 
521       @Override
522       public boolean remove(Object obj) {
523         if (obj instanceof Entry) {
524           Entry<?, ?> entry = (Entry<?, ?>) obj;
525           return removeMapping(entry.getKey(), columnKey, entry.getValue());
526         }
527         return false;
528       }
529 
530       @Override
531       public boolean retainAll(Collection<?> c) {
532         return removeFromColumnIf(not(in(c)));
533       }
534     }
535 
536     private class EntrySetIterator extends AbstractIterator<Entry<R, V>> {
537       final Iterator<Entry<R, Map<C, V>>> iterator = backingMap.entrySet().iterator();
538 
539       @Override
540       protected Entry<R, V> computeNext() {
541         while (iterator.hasNext()) {
542           final Entry<R, Map<C, V>> entry = iterator.next();
543           if (entry.getValue().containsKey(columnKey)) {
544             @WeakOuter
545             class EntryImpl extends AbstractMapEntry<R, V> {
546               @Override
547               public R getKey() {
548                 return entry.getKey();
549               }
550 
551               @Override
552               public V getValue() {
553                 return entry.getValue().get(columnKey);
554               }
555 
556               @Override
557               public V setValue(V value) {
558                 return entry.getValue().put(columnKey, checkNotNull(value));
559               }
560             }
561             return new EntryImpl();
562           }
563         }
564         return endOfData();
565       }
566     }
567 
568     @Override
569     Set<R> createKeySet() {
570       return new KeySet();
571     }
572 
573     @WeakOuter
574     private class KeySet extends Maps.KeySet<R, V> {
575       KeySet() {
576         super(Column.this);
577       }
578 
579       @Override
580       public boolean contains(Object obj) {
581         return StandardTable.this.contains(obj, columnKey);
582       }
583 
584       @Override
585       public boolean remove(Object obj) {
586         return StandardTable.this.remove(obj, columnKey) != null;
587       }
588 
589       @Override
590       public boolean retainAll(final Collection<?> c) {
591         return removeFromColumnIf(Maps.<R>keyPredicateOnEntries(not(in(c))));
592       }
593     }
594 
595     @Override
596     Collection<V> createValues() {
597       return new Values();
598     }
599 
600     @WeakOuter
601     private class Values extends Maps.Values<R, V> {
602       Values() {
603         super(Column.this);
604       }
605 
606       @Override
607       public boolean remove(Object obj) {
608         return obj != null && removeFromColumnIf(Maps.<V>valuePredicateOnEntries(equalTo(obj)));
609       }
610 
611       @Override
612       public boolean removeAll(final Collection<?> c) {
613         return removeFromColumnIf(Maps.<V>valuePredicateOnEntries(in(c)));
614       }
615 
616       @Override
617       public boolean retainAll(final Collection<?> c) {
618         return removeFromColumnIf(Maps.<V>valuePredicateOnEntries(not(in(c))));
619       }
620     }
621   }
622 
623   @Override
624   public Set<R> rowKeySet() {
625     return rowMap().keySet();
626   }
627 
628   private transient Set<C> columnKeySet;
629 
630   /**
631    * {@inheritDoc}
632    *
633    * <p>The returned set has an iterator that does not support {@code remove()}.
634    *
635    * <p>The set's iterator traverses the columns of the first row, the
636    * columns of the second row, etc., skipping any columns that have
637    * appeared previously.
638    */
639   @Override
640   public Set<C> columnKeySet() {
641     Set<C> result = columnKeySet;
642     return (result == null) ? columnKeySet = new ColumnKeySet() : result;
643   }
644 
645   @WeakOuter
646   private class ColumnKeySet extends TableSet<C> {
647     @Override
648     public Iterator<C> iterator() {
649       return createColumnKeyIterator();
650     }
651 
652     @Override
653     public int size() {
654       return Iterators.size(iterator());
655     }
656 
657     @Override
658     public boolean remove(Object obj) {
659       if (obj == null) {
660         return false;
661       }
662       boolean changed = false;
663       Iterator<Map<C, V>> iterator = backingMap.values().iterator();
664       while (iterator.hasNext()) {
665         Map<C, V> map = iterator.next();
666         if (map.keySet().remove(obj)) {
667           changed = true;
668           if (map.isEmpty()) {
669             iterator.remove();
670           }
671         }
672       }
673       return changed;
674     }
675 
676     @Override
677     public boolean removeAll(Collection<?> c) {
678       checkNotNull(c);
679       boolean changed = false;
680       Iterator<Map<C, V>> iterator = backingMap.values().iterator();
681       while (iterator.hasNext()) {
682         Map<C, V> map = iterator.next();
683         // map.keySet().removeAll(c) can throw a NPE when map is a TreeMap with
684         // natural ordering and c contains a null.
685         if (Iterators.removeAll(map.keySet().iterator(), c)) {
686           changed = true;
687           if (map.isEmpty()) {
688             iterator.remove();
689           }
690         }
691       }
692       return changed;
693     }
694 
695     @Override
696     public boolean retainAll(Collection<?> c) {
697       checkNotNull(c);
698       boolean changed = false;
699       Iterator<Map<C, V>> iterator = backingMap.values().iterator();
700       while (iterator.hasNext()) {
701         Map<C, V> map = iterator.next();
702         if (map.keySet().retainAll(c)) {
703           changed = true;
704           if (map.isEmpty()) {
705             iterator.remove();
706           }
707         }
708       }
709       return changed;
710     }
711 
712     @Override
713     public boolean contains(Object obj) {
714       return containsColumn(obj);
715     }
716   }
717 
718   /**
719    * Creates an iterator that returns each column value with duplicates
720    * omitted.
721    */
722   Iterator<C> createColumnKeyIterator() {
723     return new ColumnKeyIterator();
724   }
725 
726   private class ColumnKeyIterator extends AbstractIterator<C> {
727     // Use the same map type to support TreeMaps with comparators that aren't
728     // consistent with equals().
729     final Map<C, V> seen = factory.get();
730     final Iterator<Map<C, V>> mapIterator = backingMap.values().iterator();
731     Iterator<Entry<C, V>> entryIterator = Iterators.emptyIterator();
732 
733     @Override
734     protected C computeNext() {
735       while (true) {
736         if (entryIterator.hasNext()) {
737           Entry<C, V> entry = entryIterator.next();
738           if (!seen.containsKey(entry.getKey())) {
739             seen.put(entry.getKey(), entry.getValue());
740             return entry.getKey();
741           }
742         } else if (mapIterator.hasNext()) {
743           entryIterator = mapIterator.next().entrySet().iterator();
744         } else {
745           return endOfData();
746         }
747       }
748     }
749   }
750 
751   /**
752    * {@inheritDoc}
753    *
754    * <p>The collection's iterator traverses the values for the first row,
755    * the values for the second row, and so on.
756    */
757   @Override
758   public Collection<V> values() {
759     return super.values();
760   }
761 
762   private transient Map<R, Map<C, V>> rowMap;
763 
764   @Override
765   public Map<R, Map<C, V>> rowMap() {
766     Map<R, Map<C, V>> result = rowMap;
767     return (result == null) ? rowMap = createRowMap() : result;
768   }
769 
770   Map<R, Map<C, V>> createRowMap() {
771     return new RowMap();
772   }
773 
774   @WeakOuter
775   class RowMap extends ViewCachingAbstractMap<R, Map<C, V>> {
776     @Override
777     public boolean containsKey(Object key) {
778       return containsRow(key);
779     }
780 
781     // performing cast only when key is in backing map and has the correct type
782     @SuppressWarnings("unchecked")
783     @Override
784     public Map<C, V> get(Object key) {
785       return containsRow(key) ? row((R) key) : null;
786     }
787 
788     @Override
789     public Map<C, V> remove(Object key) {
790       return (key == null) ? null : backingMap.remove(key);
791     }
792 
793     @Override
794     protected Set<Entry<R, Map<C, V>>> createEntrySet() {
795       return new EntrySet();
796     }
797 
798     @WeakOuter
799     class EntrySet extends TableSet<Entry<R, Map<C, V>>> {
800       @Override
801       public Iterator<Entry<R, Map<C, V>>> iterator() {
802         return Maps.asMapEntryIterator(
803             backingMap.keySet(),
804             new Function<R, Map<C, V>>() {
805               @Override
806               public Map<C, V> apply(R rowKey) {
807                 return row(rowKey);
808               }
809             });
810       }
811 
812       @Override
813       public int size() {
814         return backingMap.size();
815       }
816 
817       @Override
818       public boolean contains(Object obj) {
819         if (obj instanceof Entry) {
820           Entry<?, ?> entry = (Entry<?, ?>) obj;
821           return entry.getKey() != null
822               && entry.getValue() instanceof Map
823               && Collections2.safeContains(backingMap.entrySet(), entry);
824         }
825         return false;
826       }
827 
828       @Override
829       public boolean remove(Object obj) {
830         if (obj instanceof Entry) {
831           Entry<?, ?> entry = (Entry<?, ?>) obj;
832           return entry.getKey() != null
833               && entry.getValue() instanceof Map
834               && backingMap.entrySet().remove(entry);
835         }
836         return false;
837       }
838     }
839   }
840 
841   private transient ColumnMap columnMap;
842 
843   @Override
844   public Map<C, Map<R, V>> columnMap() {
845     ColumnMap result = columnMap;
846     return (result == null) ? columnMap = new ColumnMap() : result;
847   }
848 
849   @WeakOuter
850   private class ColumnMap extends ViewCachingAbstractMap<C, Map<R, V>> {
851     // The cast to C occurs only when the key is in the map, implying that it
852     // has the correct type.
853     @SuppressWarnings("unchecked")
854     @Override
855     public Map<R, V> get(Object key) {
856       return containsColumn(key) ? column((C) key) : null;
857     }
858 
859     @Override
860     public boolean containsKey(Object key) {
861       return containsColumn(key);
862     }
863 
864     @Override
865     public Map<R, V> remove(Object key) {
866       return containsColumn(key) ? removeColumn(key) : null;
867     }
868 
869     @Override
870     public Set<Entry<C, Map<R, V>>> createEntrySet() {
871       return new ColumnMapEntrySet();
872     }
873 
874     @Override
875     public Set<C> keySet() {
876       return columnKeySet();
877     }
878 
879     @Override
880     Collection<Map<R, V>> createValues() {
881       return new ColumnMapValues();
882     }
883 
884     @WeakOuter
885     class ColumnMapEntrySet extends TableSet<Entry<C, Map<R, V>>> {
886       @Override
887       public Iterator<Entry<C, Map<R, V>>> iterator() {
888         return Maps.asMapEntryIterator(
889             columnKeySet(),
890             new Function<C, Map<R, V>>() {
891               @Override
892               public Map<R, V> apply(C columnKey) {
893                 return column(columnKey);
894               }
895             });
896       }
897 
898       @Override
899       public int size() {
900         return columnKeySet().size();
901       }
902 
903       @Override
904       public boolean contains(Object obj) {
905         if (obj instanceof Entry) {
906           Entry<?, ?> entry = (Entry<?, ?>) obj;
907           if (containsColumn(entry.getKey())) {
908             // The cast to C occurs only when the key is in the map, implying
909             // that it has the correct type.
910             @SuppressWarnings("unchecked")
911             C columnKey = (C) entry.getKey();
912             return get(columnKey).equals(entry.getValue());
913           }
914         }
915         return false;
916       }
917 
918       @Override
919       public boolean remove(Object obj) {
920         if (contains(obj)) {
921           Entry<?, ?> entry = (Entry<?, ?>) obj;
922           removeColumn(entry.getKey());
923           return true;
924         }
925         return false;
926       }
927 
928       @Override
929       public boolean removeAll(Collection<?> c) {
930         /*
931          * We can't inherit the normal implementation (which calls
932          * Sets.removeAllImpl(Set, *Collection*) because, under some
933          * circumstances, it attempts to call columnKeySet().iterator().remove,
934          * which is unsupported.
935          */
936         checkNotNull(c);
937         return Sets.removeAllImpl(this, c.iterator());
938       }
939 
940       @Override
941       public boolean retainAll(Collection<?> c) {
942         checkNotNull(c);
943         boolean changed = false;
944         for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
945           if (!c.contains(Maps.immutableEntry(columnKey, column(columnKey)))) {
946             removeColumn(columnKey);
947             changed = true;
948           }
949         }
950         return changed;
951       }
952     }
953 
954     @WeakOuter
955     private class ColumnMapValues extends Maps.Values<C, Map<R, V>> {
956       ColumnMapValues() {
957         super(ColumnMap.this);
958       }
959 
960       @Override
961       public boolean remove(Object obj) {
962         for (Entry<C, Map<R, V>> entry : ColumnMap.this.entrySet()) {
963           if (entry.getValue().equals(obj)) {
964             removeColumn(entry.getKey());
965             return true;
966           }
967         }
968         return false;
969       }
970 
971       @Override
972       public boolean removeAll(Collection<?> c) {
973         checkNotNull(c);
974         boolean changed = false;
975         for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
976           if (c.contains(column(columnKey))) {
977             removeColumn(columnKey);
978             changed = true;
979           }
980         }
981         return changed;
982       }
983 
984       @Override
985       public boolean retainAll(Collection<?> c) {
986         checkNotNull(c);
987         boolean changed = false;
988         for (C columnKey : Lists.newArrayList(columnKeySet().iterator())) {
989           if (!c.contains(column(columnKey))) {
990             removeColumn(columnKey);
991             changed = true;
992           }
993         }
994         return changed;
995       }
996     }
997   }
998 
999   private static final long serialVersionUID = 0;
1000 }