1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.collect.CollectPreconditions.checkRemove;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.collect.Maps.ImprovedAbstractMap;
25
26 import java.io.Serializable;
27 import java.util.AbstractCollection;
28 import java.util.Collection;
29 import java.util.Collections;
30 import java.util.Comparator;
31 import java.util.ConcurrentModificationException;
32 import java.util.Iterator;
33 import java.util.List;
34 import java.util.ListIterator;
35 import java.util.Map;
36 import java.util.Map.Entry;
37 import java.util.RandomAccess;
38 import java.util.Set;
39 import java.util.SortedMap;
40 import java.util.SortedSet;
41
42 import javax.annotation.Nullable;
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 @GwtCompatible(emulated = true)
88 abstract class AbstractMapBasedMultimap<K, V> extends AbstractMultimap<K, V>
89 implements Serializable {
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 private transient Map<K, Collection<V>> map;
110 private transient int totalSize;
111
112
113
114
115
116
117
118
119 protected AbstractMapBasedMultimap(Map<K, Collection<V>> map) {
120 checkArgument(map.isEmpty());
121 this.map = map;
122 }
123
124
125 final void setMap(Map<K, Collection<V>> map) {
126 this.map = map;
127 totalSize = 0;
128 for (Collection<V> values : map.values()) {
129 checkArgument(!values.isEmpty());
130 totalSize += values.size();
131 }
132 }
133
134
135
136
137
138
139 Collection<V> createUnmodifiableEmptyCollection() {
140 return unmodifiableCollectionSubclass(createCollection());
141 }
142
143
144
145
146
147
148
149
150
151
152
153
154 abstract Collection<V> createCollection();
155
156
157
158
159
160
161
162
163
164
165 Collection<V> createCollection(@Nullable K key) {
166 return createCollection();
167 }
168
169 Map<K, Collection<V>> backingMap() {
170 return map;
171 }
172
173
174
175 @Override
176 public int size() {
177 return totalSize;
178 }
179
180 @Override
181 public boolean containsKey(@Nullable Object key) {
182 return map.containsKey(key);
183 }
184
185
186
187 @Override
188 public boolean put(@Nullable K key, @Nullable V value) {
189 Collection<V> collection = map.get(key);
190 if (collection == null) {
191 collection = createCollection(key);
192 if (collection.add(value)) {
193 totalSize++;
194 map.put(key, collection);
195 return true;
196 } else {
197 throw new AssertionError("New Collection violated the Collection spec");
198 }
199 } else if (collection.add(value)) {
200 totalSize++;
201 return true;
202 } else {
203 return false;
204 }
205 }
206
207 private Collection<V> getOrCreateCollection(@Nullable K key) {
208 Collection<V> collection = map.get(key);
209 if (collection == null) {
210 collection = createCollection(key);
211 map.put(key, collection);
212 }
213 return collection;
214 }
215
216
217
218
219
220
221
222
223 @Override
224 public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
225 Iterator<? extends V> iterator = values.iterator();
226 if (!iterator.hasNext()) {
227 return removeAll(key);
228 }
229
230
231 Collection<V> collection = getOrCreateCollection(key);
232 Collection<V> oldValues = createCollection();
233 oldValues.addAll(collection);
234
235 totalSize -= collection.size();
236 collection.clear();
237
238 while (iterator.hasNext()) {
239 if (collection.add(iterator.next())) {
240 totalSize++;
241 }
242 }
243
244 return unmodifiableCollectionSubclass(oldValues);
245 }
246
247
248
249
250
251
252 @Override
253 public Collection<V> removeAll(@Nullable Object key) {
254 Collection<V> collection = map.remove(key);
255
256 if (collection == null) {
257 return createUnmodifiableEmptyCollection();
258 }
259
260 Collection<V> output = createCollection();
261 output.addAll(collection);
262 totalSize -= collection.size();
263 collection.clear();
264
265 return unmodifiableCollectionSubclass(output);
266 }
267
268 Collection<V> unmodifiableCollectionSubclass(Collection<V> collection) {
269
270
271 if (collection instanceof SortedSet) {
272 return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
273 } else if (collection instanceof Set) {
274 return Collections.unmodifiableSet((Set<V>) collection);
275 } else if (collection instanceof List) {
276 return Collections.unmodifiableList((List<V>) collection);
277 } else {
278 return Collections.unmodifiableCollection(collection);
279 }
280 }
281
282 @Override
283 public void clear() {
284
285 for (Collection<V> collection : map.values()) {
286 collection.clear();
287 }
288 map.clear();
289 totalSize = 0;
290 }
291
292
293
294
295
296
297
298
299 @Override
300 public Collection<V> get(@Nullable K key) {
301 Collection<V> collection = map.get(key);
302 if (collection == null) {
303 collection = createCollection(key);
304 }
305 return wrapCollection(key, collection);
306 }
307
308
309
310
311
312
313 Collection<V> wrapCollection(@Nullable K key, Collection<V> collection) {
314
315
316 if (collection instanceof SortedSet) {
317 return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
318 } else if (collection instanceof Set) {
319 return new WrappedSet(key, (Set<V>) collection);
320 } else if (collection instanceof List) {
321 return wrapList(key, (List<V>) collection, null);
322 } else {
323 return new WrappedCollection(key, collection, null);
324 }
325 }
326
327 private List<V> wrapList(
328 @Nullable K key, List<V> list, @Nullable WrappedCollection ancestor) {
329 return (list instanceof RandomAccess)
330 ? new RandomAccessWrappedList(key, list, ancestor)
331 : new WrappedList(key, list, ancestor);
332 }
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351 private class WrappedCollection extends AbstractCollection<V> {
352 final K key;
353 Collection<V> delegate;
354 final WrappedCollection ancestor;
355 final Collection<V> ancestorDelegate;
356
357 WrappedCollection(@Nullable K key, Collection<V> delegate,
358 @Nullable WrappedCollection ancestor) {
359 this.key = key;
360 this.delegate = delegate;
361 this.ancestor = ancestor;
362 this.ancestorDelegate
363 = (ancestor == null) ? null : ancestor.getDelegate();
364 }
365
366
367
368
369
370
371
372
373 void refreshIfEmpty() {
374 if (ancestor != null) {
375 ancestor.refreshIfEmpty();
376 if (ancestor.getDelegate() != ancestorDelegate) {
377 throw new ConcurrentModificationException();
378 }
379 } else if (delegate.isEmpty()) {
380 Collection<V> newDelegate = map.get(key);
381 if (newDelegate != null) {
382 delegate = newDelegate;
383 }
384 }
385 }
386
387
388
389
390
391 void removeIfEmpty() {
392 if (ancestor != null) {
393 ancestor.removeIfEmpty();
394 } else if (delegate.isEmpty()) {
395 map.remove(key);
396 }
397 }
398
399 K getKey() {
400 return key;
401 }
402
403
404
405
406
407
408
409
410 void addToMap() {
411 if (ancestor != null) {
412 ancestor.addToMap();
413 } else {
414 map.put(key, delegate);
415 }
416 }
417
418 @Override public int size() {
419 refreshIfEmpty();
420 return delegate.size();
421 }
422
423 @Override public boolean equals(@Nullable Object object) {
424 if (object == this) {
425 return true;
426 }
427 refreshIfEmpty();
428 return delegate.equals(object);
429 }
430
431 @Override public int hashCode() {
432 refreshIfEmpty();
433 return delegate.hashCode();
434 }
435
436 @Override public String toString() {
437 refreshIfEmpty();
438 return delegate.toString();
439 }
440
441 Collection<V> getDelegate() {
442 return delegate;
443 }
444
445 @Override public Iterator<V> iterator() {
446 refreshIfEmpty();
447 return new WrappedIterator();
448 }
449
450
451 class WrappedIterator implements Iterator<V> {
452 final Iterator<V> delegateIterator;
453 final Collection<V> originalDelegate = delegate;
454
455 WrappedIterator() {
456 delegateIterator = iteratorOrListIterator(delegate);
457 }
458
459 WrappedIterator(Iterator<V> delegateIterator) {
460 this.delegateIterator = delegateIterator;
461 }
462
463
464
465
466
467 void validateIterator() {
468 refreshIfEmpty();
469 if (delegate != originalDelegate) {
470 throw new ConcurrentModificationException();
471 }
472 }
473
474 @Override
475 public boolean hasNext() {
476 validateIterator();
477 return delegateIterator.hasNext();
478 }
479
480 @Override
481 public V next() {
482 validateIterator();
483 return delegateIterator.next();
484 }
485
486 @Override
487 public void remove() {
488 delegateIterator.remove();
489 totalSize--;
490 removeIfEmpty();
491 }
492
493 Iterator<V> getDelegateIterator() {
494 validateIterator();
495 return delegateIterator;
496 }
497 }
498
499 @Override public boolean add(V value) {
500 refreshIfEmpty();
501 boolean wasEmpty = delegate.isEmpty();
502 boolean changed = delegate.add(value);
503 if (changed) {
504 totalSize++;
505 if (wasEmpty) {
506 addToMap();
507 }
508 }
509 return changed;
510 }
511
512 WrappedCollection getAncestor() {
513 return ancestor;
514 }
515
516
517
518 @Override public boolean addAll(Collection<? extends V> collection) {
519 if (collection.isEmpty()) {
520 return false;
521 }
522 int oldSize = size();
523 boolean changed = delegate.addAll(collection);
524 if (changed) {
525 int newSize = delegate.size();
526 totalSize += (newSize - oldSize);
527 if (oldSize == 0) {
528 addToMap();
529 }
530 }
531 return changed;
532 }
533
534 @Override public boolean contains(Object o) {
535 refreshIfEmpty();
536 return delegate.contains(o);
537 }
538
539 @Override public boolean containsAll(Collection<?> c) {
540 refreshIfEmpty();
541 return delegate.containsAll(c);
542 }
543
544 @Override public void clear() {
545 int oldSize = size();
546 if (oldSize == 0) {
547 return;
548 }
549 delegate.clear();
550 totalSize -= oldSize;
551 removeIfEmpty();
552 }
553
554 @Override public boolean remove(Object o) {
555 refreshIfEmpty();
556 boolean changed = delegate.remove(o);
557 if (changed) {
558 totalSize--;
559 removeIfEmpty();
560 }
561 return changed;
562 }
563
564 @Override public boolean removeAll(Collection<?> c) {
565 if (c.isEmpty()) {
566 return false;
567 }
568 int oldSize = size();
569 boolean changed = delegate.removeAll(c);
570 if (changed) {
571 int newSize = delegate.size();
572 totalSize += (newSize - oldSize);
573 removeIfEmpty();
574 }
575 return changed;
576 }
577
578 @Override public boolean retainAll(Collection<?> c) {
579 checkNotNull(c);
580 int oldSize = size();
581 boolean changed = delegate.retainAll(c);
582 if (changed) {
583 int newSize = delegate.size();
584 totalSize += (newSize - oldSize);
585 removeIfEmpty();
586 }
587 return changed;
588 }
589 }
590
591 private Iterator<V> iteratorOrListIterator(Collection<V> collection) {
592 return (collection instanceof List)
593 ? ((List<V>) collection).listIterator()
594 : collection.iterator();
595 }
596
597
598 private class WrappedSet extends WrappedCollection implements Set<V> {
599 WrappedSet(@Nullable K key, Set<V> delegate) {
600 super(key, delegate, null);
601 }
602
603 @Override
604 public boolean removeAll(Collection<?> c) {
605 if (c.isEmpty()) {
606 return false;
607 }
608 int oldSize = size();
609
610
611
612
613 boolean changed = Sets.removeAllImpl((Set<V>) delegate, c);
614 if (changed) {
615 int newSize = delegate.size();
616 totalSize += (newSize - oldSize);
617 removeIfEmpty();
618 }
619 return changed;
620 }
621 }
622
623
624
625
626 private class WrappedSortedSet extends WrappedCollection
627 implements SortedSet<V> {
628 WrappedSortedSet(@Nullable K key, SortedSet<V> delegate,
629 @Nullable WrappedCollection ancestor) {
630 super(key, delegate, ancestor);
631 }
632
633 SortedSet<V> getSortedSetDelegate() {
634 return (SortedSet<V>) getDelegate();
635 }
636
637 @Override
638 public Comparator<? super V> comparator() {
639 return getSortedSetDelegate().comparator();
640 }
641
642 @Override
643 public V first() {
644 refreshIfEmpty();
645 return getSortedSetDelegate().first();
646 }
647
648 @Override
649 public V last() {
650 refreshIfEmpty();
651 return getSortedSetDelegate().last();
652 }
653
654 @Override
655 public SortedSet<V> headSet(V toElement) {
656 refreshIfEmpty();
657 return new WrappedSortedSet(
658 getKey(), getSortedSetDelegate().headSet(toElement),
659 (getAncestor() == null) ? this : getAncestor());
660 }
661
662 @Override
663 public SortedSet<V> subSet(V fromElement, V toElement) {
664 refreshIfEmpty();
665 return new WrappedSortedSet(
666 getKey(), getSortedSetDelegate().subSet(fromElement, toElement),
667 (getAncestor() == null) ? this : getAncestor());
668 }
669
670 @Override
671 public SortedSet<V> tailSet(V fromElement) {
672 refreshIfEmpty();
673 return new WrappedSortedSet(
674 getKey(), getSortedSetDelegate().tailSet(fromElement),
675 (getAncestor() == null) ? this : getAncestor());
676 }
677 }
678
679
680 private class WrappedList extends WrappedCollection implements List<V> {
681 WrappedList(@Nullable K key, List<V> delegate,
682 @Nullable WrappedCollection ancestor) {
683 super(key, delegate, ancestor);
684 }
685
686 List<V> getListDelegate() {
687 return (List<V>) getDelegate();
688 }
689
690 @Override
691 public boolean addAll(int index, Collection<? extends V> c) {
692 if (c.isEmpty()) {
693 return false;
694 }
695 int oldSize = size();
696 boolean changed = getListDelegate().addAll(index, c);
697 if (changed) {
698 int newSize = getDelegate().size();
699 totalSize += (newSize - oldSize);
700 if (oldSize == 0) {
701 addToMap();
702 }
703 }
704 return changed;
705 }
706
707 @Override
708 public V get(int index) {
709 refreshIfEmpty();
710 return getListDelegate().get(index);
711 }
712
713 @Override
714 public V set(int index, V element) {
715 refreshIfEmpty();
716 return getListDelegate().set(index, element);
717 }
718
719 @Override
720 public void add(int index, V element) {
721 refreshIfEmpty();
722 boolean wasEmpty = getDelegate().isEmpty();
723 getListDelegate().add(index, element);
724 totalSize++;
725 if (wasEmpty) {
726 addToMap();
727 }
728 }
729
730 @Override
731 public V remove(int index) {
732 refreshIfEmpty();
733 V value = getListDelegate().remove(index);
734 totalSize--;
735 removeIfEmpty();
736 return value;
737 }
738
739 @Override
740 public int indexOf(Object o) {
741 refreshIfEmpty();
742 return getListDelegate().indexOf(o);
743 }
744
745 @Override
746 public int lastIndexOf(Object o) {
747 refreshIfEmpty();
748 return getListDelegate().lastIndexOf(o);
749 }
750
751 @Override
752 public ListIterator<V> listIterator() {
753 refreshIfEmpty();
754 return new WrappedListIterator();
755 }
756
757 @Override
758 public ListIterator<V> listIterator(int index) {
759 refreshIfEmpty();
760 return new WrappedListIterator(index);
761 }
762
763 @Override
764 public List<V> subList(int fromIndex, int toIndex) {
765 refreshIfEmpty();
766 return wrapList(getKey(),
767 getListDelegate().subList(fromIndex, toIndex),
768 (getAncestor() == null) ? this : getAncestor());
769 }
770
771
772 private class WrappedListIterator extends WrappedIterator
773 implements ListIterator<V> {
774 WrappedListIterator() {}
775
776 public WrappedListIterator(int index) {
777 super(getListDelegate().listIterator(index));
778 }
779
780 private ListIterator<V> getDelegateListIterator() {
781 return (ListIterator<V>) getDelegateIterator();
782 }
783
784 @Override
785 public boolean hasPrevious() {
786 return getDelegateListIterator().hasPrevious();
787 }
788
789 @Override
790 public V previous() {
791 return getDelegateListIterator().previous();
792 }
793
794 @Override
795 public int nextIndex() {
796 return getDelegateListIterator().nextIndex();
797 }
798
799 @Override
800 public int previousIndex() {
801 return getDelegateListIterator().previousIndex();
802 }
803
804 @Override
805 public void set(V value) {
806 getDelegateListIterator().set(value);
807 }
808
809 @Override
810 public void add(V value) {
811 boolean wasEmpty = isEmpty();
812 getDelegateListIterator().add(value);
813 totalSize++;
814 if (wasEmpty) {
815 addToMap();
816 }
817 }
818 }
819 }
820
821
822
823
824
825 private class RandomAccessWrappedList extends WrappedList
826 implements RandomAccess {
827 RandomAccessWrappedList(@Nullable K key, List<V> delegate,
828 @Nullable WrappedCollection ancestor) {
829 super(key, delegate, ancestor);
830 }
831 }
832
833 @Override
834 Set<K> createKeySet() {
835
836
837 return (map instanceof SortedMap)
838 ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map);
839 }
840
841 private class KeySet extends Maps.KeySet<K, Collection<V>> {
842 KeySet(final Map<K, Collection<V>> subMap) {
843 super(subMap);
844 }
845
846 @Override public Iterator<K> iterator() {
847 final Iterator<Map.Entry<K, Collection<V>>> entryIterator
848 = map().entrySet().iterator();
849 return new Iterator<K>() {
850 Map.Entry<K, Collection<V>> entry;
851
852 @Override
853 public boolean hasNext() {
854 return entryIterator.hasNext();
855 }
856 @Override
857 public K next() {
858 entry = entryIterator.next();
859 return entry.getKey();
860 }
861 @Override
862 public void remove() {
863 checkRemove(entry != null);
864 Collection<V> collection = entry.getValue();
865 entryIterator.remove();
866 totalSize -= collection.size();
867 collection.clear();
868 }
869 };
870 }
871
872
873
874 @Override public boolean remove(Object key) {
875 int count = 0;
876 Collection<V> collection = map().remove(key);
877 if (collection != null) {
878 count = collection.size();
879 collection.clear();
880 totalSize -= count;
881 }
882 return count > 0;
883 }
884
885 @Override
886 public void clear() {
887 Iterators.clear(iterator());
888 }
889
890 @Override public boolean containsAll(Collection<?> c) {
891 return map().keySet().containsAll(c);
892 }
893
894 @Override public boolean equals(@Nullable Object object) {
895 return this == object || this.map().keySet().equals(object);
896 }
897
898 @Override public int hashCode() {
899 return map().keySet().hashCode();
900 }
901 }
902
903 private class SortedKeySet extends KeySet implements SortedSet<K> {
904
905 SortedKeySet(SortedMap<K, Collection<V>> subMap) {
906 super(subMap);
907 }
908
909 SortedMap<K, Collection<V>> sortedMap() {
910 return (SortedMap<K, Collection<V>>) super.map();
911 }
912
913 @Override
914 public Comparator<? super K> comparator() {
915 return sortedMap().comparator();
916 }
917
918 @Override
919 public K first() {
920 return sortedMap().firstKey();
921 }
922
923 @Override
924 public SortedSet<K> headSet(K toElement) {
925 return new SortedKeySet(sortedMap().headMap(toElement));
926 }
927
928 @Override
929 public K last() {
930 return sortedMap().lastKey();
931 }
932
933 @Override
934 public SortedSet<K> subSet(K fromElement, K toElement) {
935 return new SortedKeySet(sortedMap().subMap(fromElement, toElement));
936 }
937
938 @Override
939 public SortedSet<K> tailSet(K fromElement) {
940 return new SortedKeySet(sortedMap().tailMap(fromElement));
941 }
942 }
943
944
945
946
947
948 private int removeValuesForKey(Object key) {
949 Collection<V> collection = Maps.safeRemove(map, key);
950
951 int count = 0;
952 if (collection != null) {
953 count = collection.size();
954 collection.clear();
955 totalSize -= count;
956 }
957 return count;
958 }
959
960 private abstract class Itr<T> implements Iterator<T> {
961 final Iterator<Map.Entry<K, Collection<V>>> keyIterator;
962 K key;
963 Collection<V> collection;
964 Iterator<V> valueIterator;
965
966 Itr() {
967 keyIterator = map.entrySet().iterator();
968 key = null;
969 collection = null;
970 valueIterator = Iterators.emptyModifiableIterator();
971 }
972
973 abstract T output(K key, V value);
974
975 @Override
976 public boolean hasNext() {
977 return keyIterator.hasNext() || valueIterator.hasNext();
978 }
979
980 @Override
981 public T next() {
982 if (!valueIterator.hasNext()) {
983 Map.Entry<K, Collection<V>> mapEntry = keyIterator.next();
984 key = mapEntry.getKey();
985 collection = mapEntry.getValue();
986 valueIterator = collection.iterator();
987 }
988 return output(key, valueIterator.next());
989 }
990
991 @Override
992 public void remove() {
993 valueIterator.remove();
994 if (collection.isEmpty()) {
995 keyIterator.remove();
996 }
997 totalSize--;
998 }
999 }
1000
1001
1002
1003
1004
1005
1006
1007 @Override public Collection<V> values() {
1008 return super.values();
1009 }
1010
1011 @Override
1012 Iterator<V> valueIterator() {
1013 return new Itr<V>() {
1014 @Override
1015 V output(K key, V value) {
1016 return value;
1017 }
1018 };
1019 }
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037 @Override
1038 public Collection<Map.Entry<K, V>> entries() {
1039 return super.entries();
1040 }
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050 @Override
1051 Iterator<Map.Entry<K, V>> entryIterator() {
1052 return new Itr<Map.Entry<K, V>>() {
1053 @Override
1054 Entry<K, V> output(K key, V value) {
1055 return Maps.immutableEntry(key, value);
1056 }
1057 };
1058 }
1059
1060 @Override
1061 Map<K, Collection<V>> createAsMap() {
1062
1063
1064 return (map instanceof SortedMap)
1065 ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map);
1066 }
1067
1068 private class AsMap extends ImprovedAbstractMap<K, Collection<V>> {
1069
1070
1071
1072
1073 final transient Map<K, Collection<V>> submap;
1074
1075 AsMap(Map<K, Collection<V>> submap) {
1076 this.submap = submap;
1077 }
1078
1079 @Override
1080 protected Set<Entry<K, Collection<V>>> createEntrySet() {
1081 return new AsMapEntries();
1082 }
1083
1084
1085
1086 @Override public boolean containsKey(Object key) {
1087 return Maps.safeContainsKey(submap, key);
1088 }
1089
1090 @Override public Collection<V> get(Object key) {
1091 Collection<V> collection = Maps.safeGet(submap, key);
1092 if (collection == null) {
1093 return null;
1094 }
1095 @SuppressWarnings("unchecked")
1096 K k = (K) key;
1097 return wrapCollection(k, collection);
1098 }
1099
1100 @Override public Set<K> keySet() {
1101 return AbstractMapBasedMultimap.this.keySet();
1102 }
1103
1104 @Override
1105 public int size() {
1106 return submap.size();
1107 }
1108
1109 @Override public Collection<V> remove(Object key) {
1110 Collection<V> collection = submap.remove(key);
1111 if (collection == null) {
1112 return null;
1113 }
1114
1115 Collection<V> output = createCollection();
1116 output.addAll(collection);
1117 totalSize -= collection.size();
1118 collection.clear();
1119 return output;
1120 }
1121
1122 @Override public boolean equals(@Nullable Object object) {
1123 return this == object || submap.equals(object);
1124 }
1125
1126 @Override public int hashCode() {
1127 return submap.hashCode();
1128 }
1129
1130 @Override public String toString() {
1131 return submap.toString();
1132 }
1133
1134 @Override
1135 public void clear() {
1136 if (submap == map) {
1137 AbstractMapBasedMultimap.this.clear();
1138 } else {
1139 Iterators.clear(new AsMapIterator());
1140 }
1141 }
1142
1143 Entry<K, Collection<V>> wrapEntry(Entry<K, Collection<V>> entry) {
1144 K key = entry.getKey();
1145 return Maps.immutableEntry(key, wrapCollection(key, entry.getValue()));
1146 }
1147
1148 class AsMapEntries extends Maps.EntrySet<K, Collection<V>> {
1149 @Override
1150 Map<K, Collection<V>> map() {
1151 return AsMap.this;
1152 }
1153
1154 @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() {
1155 return new AsMapIterator();
1156 }
1157
1158
1159
1160 @Override public boolean contains(Object o) {
1161 return Collections2.safeContains(submap.entrySet(), o);
1162 }
1163
1164 @Override public boolean remove(Object o) {
1165 if (!contains(o)) {
1166 return false;
1167 }
1168 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1169 removeValuesForKey(entry.getKey());
1170 return true;
1171 }
1172 }
1173
1174
1175 class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> {
1176 final Iterator<Map.Entry<K, Collection<V>>> delegateIterator
1177 = submap.entrySet().iterator();
1178 Collection<V> collection;
1179
1180 @Override
1181 public boolean hasNext() {
1182 return delegateIterator.hasNext();
1183 }
1184
1185 @Override
1186 public Map.Entry<K, Collection<V>> next() {
1187 Map.Entry<K, Collection<V>> entry = delegateIterator.next();
1188 collection = entry.getValue();
1189 return wrapEntry(entry);
1190 }
1191
1192 @Override
1193 public void remove() {
1194 delegateIterator.remove();
1195 totalSize -= collection.size();
1196 collection.clear();
1197 }
1198 }
1199 }
1200
1201 private class SortedAsMap extends AsMap
1202 implements SortedMap<K, Collection<V>> {
1203 SortedAsMap(SortedMap<K, Collection<V>> submap) {
1204 super(submap);
1205 }
1206
1207 SortedMap<K, Collection<V>> sortedMap() {
1208 return (SortedMap<K, Collection<V>>) submap;
1209 }
1210
1211 @Override
1212 public Comparator<? super K> comparator() {
1213 return sortedMap().comparator();
1214 }
1215
1216 @Override
1217 public K firstKey() {
1218 return sortedMap().firstKey();
1219 }
1220
1221 @Override
1222 public K lastKey() {
1223 return sortedMap().lastKey();
1224 }
1225
1226 @Override
1227 public SortedMap<K, Collection<V>> headMap(K toKey) {
1228 return new SortedAsMap(sortedMap().headMap(toKey));
1229 }
1230
1231 @Override
1232 public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) {
1233 return new SortedAsMap(sortedMap().subMap(fromKey, toKey));
1234 }
1235
1236 @Override
1237 public SortedMap<K, Collection<V>> tailMap(K fromKey) {
1238 return new SortedAsMap(sortedMap().tailMap(fromKey));
1239 }
1240
1241 SortedSet<K> sortedKeySet;
1242
1243
1244
1245 @Override public SortedSet<K> keySet() {
1246 SortedSet<K> result = sortedKeySet;
1247 return (result == null) ? sortedKeySet = createKeySet() : result;
1248 }
1249
1250 @Override
1251 SortedSet<K> createKeySet() {
1252 return new SortedKeySet(sortedMap());
1253 }
1254 }
1255
1256 private static final long serialVersionUID = 2447537837011683357L;
1257 }