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.checkNotNull;
20 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21 import static com.google.common.collect.CollectPreconditions.checkRemove;
22
23 import com.google.common.annotations.Beta;
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.annotations.GwtIncompatible;
26 import com.google.common.base.Function;
27 import com.google.common.base.Predicate;
28 import com.google.common.base.Predicates;
29 import com.google.common.base.Supplier;
30 import com.google.common.collect.Maps.EntryTransformer;
31
32 import java.io.IOException;
33 import java.io.ObjectInputStream;
34 import java.io.ObjectOutputStream;
35 import java.io.Serializable;
36 import java.util.AbstractCollection;
37 import java.util.Collection;
38 import java.util.Collections;
39 import java.util.Comparator;
40 import java.util.HashSet;
41 import java.util.Iterator;
42 import java.util.List;
43 import java.util.Map;
44 import java.util.Map.Entry;
45 import java.util.NoSuchElementException;
46 import java.util.Set;
47 import java.util.SortedSet;
48
49 import javax.annotation.Nullable;
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 @GwtCompatible(emulated = true)
65 public final class Multimaps {
66 private Multimaps() {}
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111 public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map,
112 final Supplier<? extends Collection<V>> factory) {
113 return new CustomMultimap<K, V>(map, factory);
114 }
115
116 private static class CustomMultimap<K, V> extends AbstractMapBasedMultimap<K, V> {
117 transient Supplier<? extends Collection<V>> factory;
118
119 CustomMultimap(Map<K, Collection<V>> map,
120 Supplier<? extends Collection<V>> factory) {
121 super(map);
122 this.factory = checkNotNull(factory);
123 }
124
125 @Override protected Collection<V> createCollection() {
126 return factory.get();
127 }
128
129
130
131
132
133 @GwtIncompatible("java.io.ObjectOutputStream")
134 private void writeObject(ObjectOutputStream stream) throws IOException {
135 stream.defaultWriteObject();
136 stream.writeObject(factory);
137 stream.writeObject(backingMap());
138 }
139
140 @GwtIncompatible("java.io.ObjectInputStream")
141 @SuppressWarnings("unchecked")
142 private void readObject(ObjectInputStream stream)
143 throws IOException, ClassNotFoundException {
144 stream.defaultReadObject();
145 factory = (Supplier<? extends Collection<V>>) stream.readObject();
146 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
147 setMap(map);
148 }
149
150 @GwtIncompatible("java serialization not supported")
151 private static final long serialVersionUID = 0;
152 }
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192 public static <K, V> ListMultimap<K, V> newListMultimap(
193 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
194 return new CustomListMultimap<K, V>(map, factory);
195 }
196
197 private static class CustomListMultimap<K, V>
198 extends AbstractListMultimap<K, V> {
199 transient Supplier<? extends List<V>> factory;
200
201 CustomListMultimap(Map<K, Collection<V>> map,
202 Supplier<? extends List<V>> factory) {
203 super(map);
204 this.factory = checkNotNull(factory);
205 }
206
207 @Override protected List<V> createCollection() {
208 return factory.get();
209 }
210
211
212 @GwtIncompatible("java.io.ObjectOutputStream")
213 private void writeObject(ObjectOutputStream stream) throws IOException {
214 stream.defaultWriteObject();
215 stream.writeObject(factory);
216 stream.writeObject(backingMap());
217 }
218
219 @GwtIncompatible("java.io.ObjectInputStream")
220 @SuppressWarnings("unchecked")
221 private void readObject(ObjectInputStream stream)
222 throws IOException, ClassNotFoundException {
223 stream.defaultReadObject();
224 factory = (Supplier<? extends List<V>>) stream.readObject();
225 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
226 setMap(map);
227 }
228
229 @GwtIncompatible("java serialization not supported")
230 private static final long serialVersionUID = 0;
231 }
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270 public static <K, V> SetMultimap<K, V> newSetMultimap(
271 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
272 return new CustomSetMultimap<K, V>(map, factory);
273 }
274
275 private static class CustomSetMultimap<K, V>
276 extends AbstractSetMultimap<K, V> {
277 transient Supplier<? extends Set<V>> factory;
278
279 CustomSetMultimap(Map<K, Collection<V>> map,
280 Supplier<? extends Set<V>> factory) {
281 super(map);
282 this.factory = checkNotNull(factory);
283 }
284
285 @Override protected Set<V> createCollection() {
286 return factory.get();
287 }
288
289
290 @GwtIncompatible("java.io.ObjectOutputStream")
291 private void writeObject(ObjectOutputStream stream) throws IOException {
292 stream.defaultWriteObject();
293 stream.writeObject(factory);
294 stream.writeObject(backingMap());
295 }
296
297 @GwtIncompatible("java.io.ObjectInputStream")
298 @SuppressWarnings("unchecked")
299 private void readObject(ObjectInputStream stream)
300 throws IOException, ClassNotFoundException {
301 stream.defaultReadObject();
302 factory = (Supplier<? extends Set<V>>) stream.readObject();
303 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
304 setMap(map);
305 }
306
307 @GwtIncompatible("not needed in emulated source")
308 private static final long serialVersionUID = 0;
309 }
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347 public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
348 Map<K, Collection<V>> map,
349 final Supplier<? extends SortedSet<V>> factory) {
350 return new CustomSortedSetMultimap<K, V>(map, factory);
351 }
352
353 private static class CustomSortedSetMultimap<K, V>
354 extends AbstractSortedSetMultimap<K, V> {
355 transient Supplier<? extends SortedSet<V>> factory;
356 transient Comparator<? super V> valueComparator;
357
358 CustomSortedSetMultimap(Map<K, Collection<V>> map,
359 Supplier<? extends SortedSet<V>> factory) {
360 super(map);
361 this.factory = checkNotNull(factory);
362 valueComparator = factory.get().comparator();
363 }
364
365 @Override protected SortedSet<V> createCollection() {
366 return factory.get();
367 }
368
369 @Override public Comparator<? super V> valueComparator() {
370 return valueComparator;
371 }
372
373
374 @GwtIncompatible("java.io.ObjectOutputStream")
375 private void writeObject(ObjectOutputStream stream) throws IOException {
376 stream.defaultWriteObject();
377 stream.writeObject(factory);
378 stream.writeObject(backingMap());
379 }
380
381 @GwtIncompatible("java.io.ObjectInputStream")
382 @SuppressWarnings("unchecked")
383 private void readObject(ObjectInputStream stream)
384 throws IOException, ClassNotFoundException {
385 stream.defaultReadObject();
386 factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
387 valueComparator = factory.get().comparator();
388 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
389 setMap(map);
390 }
391
392 @GwtIncompatible("not needed in emulated source")
393 private static final long serialVersionUID = 0;
394 }
395
396
397
398
399
400
401
402
403
404
405
406
407 public static <K, V, M extends Multimap<K, V>> M invertFrom(
408 Multimap<? extends V, ? extends K> source, M dest) {
409 checkNotNull(dest);
410 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
411 dest.put(entry.getValue(), entry.getKey());
412 }
413 return dest;
414 }
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449 public static <K, V> Multimap<K, V> synchronizedMultimap(
450 Multimap<K, V> multimap) {
451 return Synchronized.multimap(multimap, null);
452 }
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471 public static <K, V> Multimap<K, V> unmodifiableMultimap(
472 Multimap<K, V> delegate) {
473 if (delegate instanceof UnmodifiableMultimap ||
474 delegate instanceof ImmutableMultimap) {
475 return delegate;
476 }
477 return new UnmodifiableMultimap<K, V>(delegate);
478 }
479
480
481
482
483
484
485
486 @Deprecated public static <K, V> Multimap<K, V> unmodifiableMultimap(
487 ImmutableMultimap<K, V> delegate) {
488 return checkNotNull(delegate);
489 }
490
491 private static class UnmodifiableMultimap<K, V>
492 extends ForwardingMultimap<K, V> implements Serializable {
493 final Multimap<K, V> delegate;
494 transient Collection<Entry<K, V>> entries;
495 transient Multiset<K> keys;
496 transient Set<K> keySet;
497 transient Collection<V> values;
498 transient Map<K, Collection<V>> map;
499
500 UnmodifiableMultimap(final Multimap<K, V> delegate) {
501 this.delegate = checkNotNull(delegate);
502 }
503
504 @Override protected Multimap<K, V> delegate() {
505 return delegate;
506 }
507
508 @Override public void clear() {
509 throw new UnsupportedOperationException();
510 }
511
512 @Override public Map<K, Collection<V>> asMap() {
513 Map<K, Collection<V>> result = map;
514 if (result == null) {
515 result = map = Collections.unmodifiableMap(
516 Maps.transformValues(delegate.asMap(), new Function<Collection<V>, Collection<V>>() {
517 @Override
518 public Collection<V> apply(Collection<V> collection) {
519 return unmodifiableValueCollection(collection);
520 }
521 }));
522 }
523 return result;
524 }
525
526 @Override public Collection<Entry<K, V>> entries() {
527 Collection<Entry<K, V>> result = entries;
528 if (result == null) {
529 entries = result = unmodifiableEntries(delegate.entries());
530 }
531 return result;
532 }
533
534 @Override public Collection<V> get(K key) {
535 return unmodifiableValueCollection(delegate.get(key));
536 }
537
538 @Override public Multiset<K> keys() {
539 Multiset<K> result = keys;
540 if (result == null) {
541 keys = result = Multisets.unmodifiableMultiset(delegate.keys());
542 }
543 return result;
544 }
545
546 @Override public Set<K> keySet() {
547 Set<K> result = keySet;
548 if (result == null) {
549 keySet = result = Collections.unmodifiableSet(delegate.keySet());
550 }
551 return result;
552 }
553
554 @Override public boolean put(K key, V value) {
555 throw new UnsupportedOperationException();
556 }
557
558 @Override public boolean putAll(K key, Iterable<? extends V> values) {
559 throw new UnsupportedOperationException();
560 }
561
562 @Override
563 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
564 throw new UnsupportedOperationException();
565 }
566
567 @Override public boolean remove(Object key, Object value) {
568 throw new UnsupportedOperationException();
569 }
570
571 @Override public Collection<V> removeAll(Object key) {
572 throw new UnsupportedOperationException();
573 }
574
575 @Override public Collection<V> replaceValues(
576 K key, Iterable<? extends V> values) {
577 throw new UnsupportedOperationException();
578 }
579
580 @Override public Collection<V> values() {
581 Collection<V> result = values;
582 if (result == null) {
583 values = result = Collections.unmodifiableCollection(delegate.values());
584 }
585 return result;
586 }
587
588 private static final long serialVersionUID = 0;
589 }
590
591 private static class UnmodifiableListMultimap<K, V>
592 extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
593 UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
594 super(delegate);
595 }
596 @Override public ListMultimap<K, V> delegate() {
597 return (ListMultimap<K, V>) super.delegate();
598 }
599 @Override public List<V> get(K key) {
600 return Collections.unmodifiableList(delegate().get(key));
601 }
602 @Override public List<V> removeAll(Object key) {
603 throw new UnsupportedOperationException();
604 }
605 @Override public List<V> replaceValues(
606 K key, Iterable<? extends V> values) {
607 throw new UnsupportedOperationException();
608 }
609 private static final long serialVersionUID = 0;
610 }
611
612 private static class UnmodifiableSetMultimap<K, V>
613 extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
614 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
615 super(delegate);
616 }
617 @Override public SetMultimap<K, V> delegate() {
618 return (SetMultimap<K, V>) super.delegate();
619 }
620 @Override public Set<V> get(K key) {
621
622
623
624
625 return Collections.unmodifiableSet(delegate().get(key));
626 }
627 @Override public Set<Map.Entry<K, V>> entries() {
628 return Maps.unmodifiableEntrySet(delegate().entries());
629 }
630 @Override public Set<V> removeAll(Object key) {
631 throw new UnsupportedOperationException();
632 }
633 @Override public Set<V> replaceValues(
634 K key, Iterable<? extends V> values) {
635 throw new UnsupportedOperationException();
636 }
637 private static final long serialVersionUID = 0;
638 }
639
640 private static class UnmodifiableSortedSetMultimap<K, V>
641 extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
642 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
643 super(delegate);
644 }
645 @Override public SortedSetMultimap<K, V> delegate() {
646 return (SortedSetMultimap<K, V>) super.delegate();
647 }
648 @Override public SortedSet<V> get(K key) {
649 return Collections.unmodifiableSortedSet(delegate().get(key));
650 }
651 @Override public SortedSet<V> removeAll(Object key) {
652 throw new UnsupportedOperationException();
653 }
654 @Override public SortedSet<V> replaceValues(
655 K key, Iterable<? extends V> values) {
656 throw new UnsupportedOperationException();
657 }
658 @Override
659 public Comparator<? super V> valueComparator() {
660 return delegate().valueComparator();
661 }
662 private static final long serialVersionUID = 0;
663 }
664
665
666
667
668
669
670
671
672
673
674
675
676
677 public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(
678 SetMultimap<K, V> multimap) {
679 return Synchronized.setMultimap(multimap, null);
680 }
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
701 SetMultimap<K, V> delegate) {
702 if (delegate instanceof UnmodifiableSetMultimap ||
703 delegate instanceof ImmutableSetMultimap) {
704 return delegate;
705 }
706 return new UnmodifiableSetMultimap<K, V>(delegate);
707 }
708
709
710
711
712
713
714
715 @Deprecated public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
716 ImmutableSetMultimap<K, V> delegate) {
717 return checkNotNull(delegate);
718 }
719
720
721
722
723
724
725
726
727
728
729
730
731
732 public static <K, V> SortedSetMultimap<K, V>
733 synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) {
734 return Synchronized.sortedSetMultimap(multimap, null);
735 }
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755 public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
756 SortedSetMultimap<K, V> delegate) {
757 if (delegate instanceof UnmodifiableSortedSetMultimap) {
758 return delegate;
759 }
760 return new UnmodifiableSortedSetMultimap<K, V>(delegate);
761 }
762
763
764
765
766
767
768
769
770
771
772 public static <K, V> ListMultimap<K, V> synchronizedListMultimap(
773 ListMultimap<K, V> multimap) {
774 return Synchronized.listMultimap(multimap, null);
775 }
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
796 ListMultimap<K, V> delegate) {
797 if (delegate instanceof UnmodifiableListMultimap ||
798 delegate instanceof ImmutableListMultimap) {
799 return delegate;
800 }
801 return new UnmodifiableListMultimap<K, V>(delegate);
802 }
803
804
805
806
807
808
809
810 @Deprecated public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
811 ImmutableListMultimap<K, V> delegate) {
812 return checkNotNull(delegate);
813 }
814
815
816
817
818
819
820
821
822
823 private static <V> Collection<V> unmodifiableValueCollection(
824 Collection<V> collection) {
825 if (collection instanceof SortedSet) {
826 return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
827 } else if (collection instanceof Set) {
828 return Collections.unmodifiableSet((Set<V>) collection);
829 } else if (collection instanceof List) {
830 return Collections.unmodifiableList((List<V>) collection);
831 }
832 return Collections.unmodifiableCollection(collection);
833 }
834
835
836
837
838
839
840
841
842
843
844 private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
845 Collection<Entry<K, V>> entries) {
846 if (entries instanceof Set) {
847 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
848 }
849 return new Maps.UnmodifiableEntries<K, V>(
850 Collections.unmodifiableCollection(entries));
851 }
852
853
854
855
856
857
858
859 @Beta
860 @SuppressWarnings("unchecked")
861
862 public static <K, V> Map<K, List<V>> asMap(ListMultimap<K, V> multimap) {
863 return (Map<K, List<V>>) (Map<K, ?>) multimap.asMap();
864 }
865
866
867
868
869
870
871
872 @Beta
873 @SuppressWarnings("unchecked")
874
875 public static <K, V> Map<K, Set<V>> asMap(SetMultimap<K, V> multimap) {
876 return (Map<K, Set<V>>) (Map<K, ?>) multimap.asMap();
877 }
878
879
880
881
882
883
884
885
886 @Beta
887 @SuppressWarnings("unchecked")
888
889 public static <K, V> Map<K, SortedSet<V>> asMap(
890 SortedSetMultimap<K, V> multimap) {
891 return (Map<K, SortedSet<V>>) (Map<K, ?>) multimap.asMap();
892 }
893
894
895
896
897
898
899
900 @Beta
901 public static <K, V> Map<K, Collection<V>> asMap(Multimap<K, V> multimap) {
902 return multimap.asMap();
903 }
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922 public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
923 return new MapMultimap<K, V>(map);
924 }
925
926
927 private static class MapMultimap<K, V>
928 extends AbstractMultimap<K, V> implements SetMultimap<K, V>, Serializable {
929 final Map<K, V> map;
930
931 MapMultimap(Map<K, V> map) {
932 this.map = checkNotNull(map);
933 }
934
935 @Override
936 public int size() {
937 return map.size();
938 }
939
940 @Override
941 public boolean containsKey(Object key) {
942 return map.containsKey(key);
943 }
944
945 @Override
946 public boolean containsValue(Object value) {
947 return map.containsValue(value);
948 }
949
950 @Override
951 public boolean containsEntry(Object key, Object value) {
952 return map.entrySet().contains(Maps.immutableEntry(key, value));
953 }
954
955 @Override
956 public Set<V> get(final K key) {
957 return new Sets.ImprovedAbstractSet<V>() {
958 @Override public Iterator<V> iterator() {
959 return new Iterator<V>() {
960 int i;
961
962 @Override
963 public boolean hasNext() {
964 return (i == 0) && map.containsKey(key);
965 }
966
967 @Override
968 public V next() {
969 if (!hasNext()) {
970 throw new NoSuchElementException();
971 }
972 i++;
973 return map.get(key);
974 }
975
976 @Override
977 public void remove() {
978 checkRemove(i == 1);
979 i = -1;
980 map.remove(key);
981 }
982 };
983 }
984
985 @Override public int size() {
986 return map.containsKey(key) ? 1 : 0;
987 }
988 };
989 }
990
991 @Override
992 public boolean put(K key, V value) {
993 throw new UnsupportedOperationException();
994 }
995
996 @Override
997 public boolean putAll(K key, Iterable<? extends V> values) {
998 throw new UnsupportedOperationException();
999 }
1000
1001 @Override
1002 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1003 throw new UnsupportedOperationException();
1004 }
1005
1006 @Override
1007 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
1008 throw new UnsupportedOperationException();
1009 }
1010
1011 @Override
1012 public boolean remove(Object key, Object value) {
1013 return map.entrySet().remove(Maps.immutableEntry(key, value));
1014 }
1015
1016 @Override
1017 public Set<V> removeAll(Object key) {
1018 Set<V> values = new HashSet<V>(2);
1019 if (!map.containsKey(key)) {
1020 return values;
1021 }
1022 values.add(map.remove(key));
1023 return values;
1024 }
1025
1026 @Override
1027 public void clear() {
1028 map.clear();
1029 }
1030
1031 @Override
1032 public Set<K> keySet() {
1033 return map.keySet();
1034 }
1035
1036 @Override
1037 public Collection<V> values() {
1038 return map.values();
1039 }
1040
1041 @Override
1042 public Set<Entry<K, V>> entries() {
1043 return map.entrySet();
1044 }
1045
1046 @Override
1047 Iterator<Entry<K, V>> entryIterator() {
1048 return map.entrySet().iterator();
1049 }
1050
1051 @Override
1052 Map<K, Collection<V>> createAsMap() {
1053 return new AsMap<K, V>(this);
1054 }
1055
1056 @Override public int hashCode() {
1057 return map.hashCode();
1058 }
1059
1060 private static final long serialVersionUID = 7845222491160860175L;
1061 }
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107 public static <K, V1, V2> Multimap<K, V2> transformValues(
1108 Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1109 checkNotNull(function);
1110 EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function);
1111 return transformEntries(fromMultimap, transformer);
1112 }
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169 public static <K, V1, V2> Multimap<K, V2> transformEntries(
1170 Multimap<K, V1> fromMap,
1171 EntryTransformer<? super K, ? super V1, V2> transformer) {
1172 return new TransformedEntriesMultimap<K, V1, V2>(fromMap, transformer);
1173 }
1174
1175 private static class TransformedEntriesMultimap<K, V1, V2>
1176 extends AbstractMultimap<K, V2> {
1177 final Multimap<K, V1> fromMultimap;
1178 final EntryTransformer<? super K, ? super V1, V2> transformer;
1179
1180 TransformedEntriesMultimap(Multimap<K, V1> fromMultimap,
1181 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1182 this.fromMultimap = checkNotNull(fromMultimap);
1183 this.transformer = checkNotNull(transformer);
1184 }
1185
1186 Collection<V2> transform(K key, Collection<V1> values) {
1187 Function<? super V1, V2> function =
1188 Maps.asValueToValueFunction(transformer, key);
1189 if (values instanceof List) {
1190 return Lists.transform((List<V1>) values, function);
1191 } else {
1192 return Collections2.transform(values, function);
1193 }
1194 }
1195
1196 @Override
1197 Map<K, Collection<V2>> createAsMap() {
1198 return Maps.transformEntries(fromMultimap.asMap(),
1199 new EntryTransformer<K, Collection<V1>, Collection<V2>>() {
1200 @Override public Collection<V2> transformEntry(
1201 K key, Collection<V1> value) {
1202 return transform(key, value);
1203 }
1204 });
1205 }
1206
1207 @Override public void clear() {
1208 fromMultimap.clear();
1209 }
1210
1211 @Override public boolean containsKey(Object key) {
1212 return fromMultimap.containsKey(key);
1213 }
1214
1215 @Override
1216 Iterator<Entry<K, V2>> entryIterator() {
1217 return Iterators.transform(fromMultimap.entries().iterator(),
1218 Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
1219 }
1220
1221 @Override public Collection<V2> get(final K key) {
1222 return transform(key, fromMultimap.get(key));
1223 }
1224
1225 @Override public boolean isEmpty() {
1226 return fromMultimap.isEmpty();
1227 }
1228
1229 @Override public Set<K> keySet() {
1230 return fromMultimap.keySet();
1231 }
1232
1233 @Override public Multiset<K> keys() {
1234 return fromMultimap.keys();
1235 }
1236
1237 @Override public boolean put(K key, V2 value) {
1238 throw new UnsupportedOperationException();
1239 }
1240
1241 @Override public boolean putAll(K key, Iterable<? extends V2> values) {
1242 throw new UnsupportedOperationException();
1243 }
1244
1245 @Override public boolean putAll(
1246 Multimap<? extends K, ? extends V2> multimap) {
1247 throw new UnsupportedOperationException();
1248 }
1249
1250 @SuppressWarnings("unchecked")
1251 @Override public boolean remove(Object key, Object value) {
1252 return get((K) key).remove(value);
1253 }
1254
1255 @SuppressWarnings("unchecked")
1256 @Override public Collection<V2> removeAll(Object key) {
1257 return transform((K) key, fromMultimap.removeAll(key));
1258 }
1259
1260 @Override public Collection<V2> replaceValues(
1261 K key, Iterable<? extends V2> values) {
1262 throw new UnsupportedOperationException();
1263 }
1264
1265 @Override public int size() {
1266 return fromMultimap.size();
1267 }
1268
1269 @Override
1270 Collection<V2> createValues() {
1271 return Collections2.transform(
1272 fromMultimap.entries(), Maps.<K, V1, V2>asEntryToValueFunction(transformer));
1273 }
1274 }
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317 public static <K, V1, V2> ListMultimap<K, V2> transformValues(
1318 ListMultimap<K, V1> fromMultimap,
1319 final Function<? super V1, V2> function) {
1320 checkNotNull(function);
1321 EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function);
1322 return transformEntries(fromMultimap, transformer);
1323 }
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377 public static <K, V1, V2> ListMultimap<K, V2> transformEntries(
1378 ListMultimap<K, V1> fromMap,
1379 EntryTransformer<? super K, ? super V1, V2> transformer) {
1380 return new TransformedEntriesListMultimap<K, V1, V2>(fromMap, transformer);
1381 }
1382
1383 private static final class TransformedEntriesListMultimap<K, V1, V2>
1384 extends TransformedEntriesMultimap<K, V1, V2>
1385 implements ListMultimap<K, V2> {
1386
1387 TransformedEntriesListMultimap(ListMultimap<K, V1> fromMultimap,
1388 EntryTransformer<? super K, ? super V1, V2> transformer) {
1389 super(fromMultimap, transformer);
1390 }
1391
1392 @Override List<V2> transform(K key, Collection<V1> values) {
1393 return Lists.transform((List<V1>) values, Maps.asValueToValueFunction(transformer, key));
1394 }
1395
1396 @Override public List<V2> get(K key) {
1397 return transform(key, fromMultimap.get(key));
1398 }
1399
1400 @SuppressWarnings("unchecked")
1401 @Override public List<V2> removeAll(Object key) {
1402 return transform((K) key, fromMultimap.removeAll(key));
1403 }
1404
1405 @Override public List<V2> replaceValues(
1406 K key, Iterable<? extends V2> values) {
1407 throw new UnsupportedOperationException();
1408 }
1409 }
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453 public static <K, V> ImmutableListMultimap<K, V> index(
1454 Iterable<V> values, Function<? super V, K> keyFunction) {
1455 return index(values.iterator(), keyFunction);
1456 }
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501 public static <K, V> ImmutableListMultimap<K, V> index(
1502 Iterator<V> values, Function<? super V, K> keyFunction) {
1503 checkNotNull(keyFunction);
1504 ImmutableListMultimap.Builder<K, V> builder
1505 = ImmutableListMultimap.builder();
1506 while (values.hasNext()) {
1507 V value = values.next();
1508 checkNotNull(value, values);
1509 builder.put(keyFunction.apply(value), value);
1510 }
1511 return builder.build();
1512 }
1513
1514 static class Keys<K, V> extends AbstractMultiset<K> {
1515 final Multimap<K, V> multimap;
1516
1517 Keys(Multimap<K, V> multimap) {
1518 this.multimap = multimap;
1519 }
1520
1521 @Override Iterator<Multiset.Entry<K>> entryIterator() {
1522 return new TransformedIterator<Map.Entry<K, Collection<V>>, Multiset.Entry<K>>(
1523 multimap.asMap().entrySet().iterator()) {
1524 @Override
1525 Multiset.Entry<K> transform(
1526 final Map.Entry<K, Collection<V>> backingEntry) {
1527 return new Multisets.AbstractEntry<K>() {
1528 @Override
1529 public K getElement() {
1530 return backingEntry.getKey();
1531 }
1532
1533 @Override
1534 public int getCount() {
1535 return backingEntry.getValue().size();
1536 }
1537 };
1538 }
1539 };
1540 }
1541
1542 @Override int distinctElements() {
1543 return multimap.asMap().size();
1544 }
1545
1546 @Override Set<Multiset.Entry<K>> createEntrySet() {
1547 return new KeysEntrySet();
1548 }
1549
1550 class KeysEntrySet extends Multisets.EntrySet<K> {
1551 @Override Multiset<K> multiset() {
1552 return Keys.this;
1553 }
1554
1555 @Override public Iterator<Multiset.Entry<K>> iterator() {
1556 return entryIterator();
1557 }
1558
1559 @Override public int size() {
1560 return distinctElements();
1561 }
1562
1563 @Override public boolean isEmpty() {
1564 return multimap.isEmpty();
1565 }
1566
1567 @Override public boolean contains(@Nullable Object o) {
1568 if (o instanceof Multiset.Entry) {
1569 Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
1570 Collection<V> collection = multimap.asMap().get(entry.getElement());
1571 return collection != null && collection.size() == entry.getCount();
1572 }
1573 return false;
1574 }
1575
1576 @Override public boolean remove(@Nullable Object o) {
1577 if (o instanceof Multiset.Entry) {
1578 Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
1579 Collection<V> collection = multimap.asMap().get(entry.getElement());
1580 if (collection != null && collection.size() == entry.getCount()) {
1581 collection.clear();
1582 return true;
1583 }
1584 }
1585 return false;
1586 }
1587 }
1588
1589 @Override public boolean contains(@Nullable Object element) {
1590 return multimap.containsKey(element);
1591 }
1592
1593 @Override public Iterator<K> iterator() {
1594 return Maps.keyIterator(multimap.entries().iterator());
1595 }
1596
1597 @Override public int count(@Nullable Object element) {
1598 Collection<V> values = Maps.safeGet(multimap.asMap(), element);
1599 return (values == null) ? 0 : values.size();
1600 }
1601
1602 @Override public int remove(@Nullable Object element, int occurrences) {
1603 checkNonnegative(occurrences, "occurrences");
1604 if (occurrences == 0) {
1605 return count(element);
1606 }
1607
1608 Collection<V> values = Maps.safeGet(multimap.asMap(), element);
1609
1610 if (values == null) {
1611 return 0;
1612 }
1613
1614 int oldCount = values.size();
1615 if (occurrences >= oldCount) {
1616 values.clear();
1617 } else {
1618 Iterator<V> iterator = values.iterator();
1619 for (int i = 0; i < occurrences; i++) {
1620 iterator.next();
1621 iterator.remove();
1622 }
1623 }
1624 return oldCount;
1625 }
1626
1627 @Override public void clear() {
1628 multimap.clear();
1629 }
1630
1631 @Override public Set<K> elementSet() {
1632 return multimap.keySet();
1633 }
1634 }
1635
1636
1637
1638
1639 abstract static class Entries<K, V> extends
1640 AbstractCollection<Map.Entry<K, V>> {
1641 abstract Multimap<K, V> multimap();
1642
1643 @Override public int size() {
1644 return multimap().size();
1645 }
1646
1647 @Override public boolean contains(@Nullable Object o) {
1648 if (o instanceof Map.Entry) {
1649 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1650 return multimap().containsEntry(entry.getKey(), entry.getValue());
1651 }
1652 return false;
1653 }
1654
1655 @Override public boolean remove(@Nullable Object o) {
1656 if (o instanceof Map.Entry) {
1657 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1658 return multimap().remove(entry.getKey(), entry.getValue());
1659 }
1660 return false;
1661 }
1662
1663 @Override public void clear() {
1664 multimap().clear();
1665 }
1666 }
1667
1668
1669
1670
1671 static final class AsMap<K, V> extends
1672 Maps.ImprovedAbstractMap<K, Collection<V>> {
1673 private final Multimap<K, V> multimap;
1674
1675 AsMap(Multimap<K, V> multimap) {
1676 this.multimap = checkNotNull(multimap);
1677 }
1678
1679 @Override public int size() {
1680 return multimap.keySet().size();
1681 }
1682
1683 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
1684 return new EntrySet();
1685 }
1686
1687 void removeValuesForKey(Object key) {
1688 multimap.keySet().remove(key);
1689 }
1690
1691 class EntrySet extends Maps.EntrySet<K, Collection<V>> {
1692 @Override Map<K, Collection<V>> map() {
1693 return AsMap.this;
1694 }
1695
1696 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
1697 return Maps.asMapEntryIterator(multimap.keySet(), new Function<K, Collection<V>>() {
1698 @Override
1699 public Collection<V> apply(K key) {
1700 return multimap.get(key);
1701 }
1702 });
1703 }
1704
1705 @Override public boolean remove(Object o) {
1706 if (!contains(o)) {
1707 return false;
1708 }
1709 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1710 removeValuesForKey(entry.getKey());
1711 return true;
1712 }
1713 }
1714
1715 @SuppressWarnings("unchecked")
1716 @Override public Collection<V> get(Object key) {
1717 return containsKey(key) ? multimap.get((K) key) : null;
1718 }
1719
1720 @Override public Collection<V> remove(Object key) {
1721 return containsKey(key) ? multimap.removeAll(key) : null;
1722 }
1723
1724 @Override public Set<K> keySet() {
1725 return multimap.keySet();
1726 }
1727
1728 @Override public boolean isEmpty() {
1729 return multimap.isEmpty();
1730 }
1731
1732 @Override public boolean containsKey(Object key) {
1733 return multimap.containsKey(key);
1734 }
1735
1736 @Override public void clear() {
1737 multimap.clear();
1738 }
1739 }
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771 public static <K, V> Multimap<K, V> filterKeys(
1772 Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1773 if (unfiltered instanceof SetMultimap) {
1774 return filterKeys((SetMultimap<K, V>) unfiltered, keyPredicate);
1775 } else if (unfiltered instanceof ListMultimap) {
1776 return filterKeys((ListMultimap<K, V>) unfiltered, keyPredicate);
1777 } else if (unfiltered instanceof FilteredKeyMultimap) {
1778 FilteredKeyMultimap<K, V> prev = (FilteredKeyMultimap<K, V>) unfiltered;
1779 return new FilteredKeyMultimap<K, V>(prev.unfiltered,
1780 Predicates.and(prev.keyPredicate, keyPredicate));
1781 } else if (unfiltered instanceof FilteredMultimap) {
1782 FilteredMultimap<K, V> prev = (FilteredMultimap<K, V>) unfiltered;
1783 return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
1784 } else {
1785 return new FilteredKeyMultimap<K, V>(unfiltered, keyPredicate);
1786 }
1787 }
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819 public static <K, V> SetMultimap<K, V> filterKeys(
1820 SetMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1821 if (unfiltered instanceof FilteredKeySetMultimap) {
1822 FilteredKeySetMultimap<K, V> prev = (FilteredKeySetMultimap<K, V>) unfiltered;
1823 return new FilteredKeySetMultimap<K, V>(prev.unfiltered(),
1824 Predicates.and(prev.keyPredicate, keyPredicate));
1825 } else if (unfiltered instanceof FilteredSetMultimap) {
1826 FilteredSetMultimap<K, V> prev = (FilteredSetMultimap<K, V>) unfiltered;
1827 return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
1828 } else {
1829 return new FilteredKeySetMultimap<K, V>(unfiltered, keyPredicate);
1830 }
1831 }
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863 public static <K, V> ListMultimap<K, V> filterKeys(
1864 ListMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1865 if (unfiltered instanceof FilteredKeyListMultimap) {
1866 FilteredKeyListMultimap<K, V> prev = (FilteredKeyListMultimap<K, V>) unfiltered;
1867 return new FilteredKeyListMultimap<K, V>(prev.unfiltered(),
1868 Predicates.and(prev.keyPredicate, keyPredicate));
1869 } else {
1870 return new FilteredKeyListMultimap<K, V>(unfiltered, keyPredicate);
1871 }
1872 }
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904 public static <K, V> Multimap<K, V> filterValues(
1905 Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1906 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
1907 }
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939 public static <K, V> SetMultimap<K, V> filterValues(
1940 SetMultimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1941 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
1942 }
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972 public static <K, V> Multimap<K, V> filterEntries(
1973 Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1974 checkNotNull(entryPredicate);
1975 if (unfiltered instanceof SetMultimap) {
1976 return filterEntries((SetMultimap<K, V>) unfiltered, entryPredicate);
1977 }
1978 return (unfiltered instanceof FilteredMultimap)
1979 ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate)
1980 : new FilteredEntryMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
1981 }
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011 public static <K, V> SetMultimap<K, V> filterEntries(
2012 SetMultimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2013 checkNotNull(entryPredicate);
2014 return (unfiltered instanceof FilteredSetMultimap)
2015 ? filterFiltered((FilteredSetMultimap<K, V>) unfiltered, entryPredicate)
2016 : new FilteredEntrySetMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2017 }
2018
2019
2020
2021
2022
2023
2024
2025
2026 private static <K, V> Multimap<K, V> filterFiltered(FilteredMultimap<K, V> multimap,
2027 Predicate<? super Entry<K, V>> entryPredicate) {
2028 Predicate<Entry<K, V>> predicate
2029 = Predicates.and(multimap.entryPredicate(), entryPredicate);
2030 return new FilteredEntryMultimap<K, V>(multimap.unfiltered(), predicate);
2031 }
2032
2033
2034
2035
2036
2037
2038
2039 private static <K, V> SetMultimap<K, V> filterFiltered(
2040 FilteredSetMultimap<K, V> multimap,
2041 Predicate<? super Entry<K, V>> entryPredicate) {
2042 Predicate<Entry<K, V>> predicate
2043 = Predicates.and(multimap.entryPredicate(), entryPredicate);
2044 return new FilteredEntrySetMultimap<K, V>(multimap.unfiltered(), predicate);
2045 }
2046
2047 static boolean equalsImpl(Multimap<?, ?> multimap, @Nullable Object object) {
2048 if (object == multimap) {
2049 return true;
2050 }
2051 if (object instanceof Multimap) {
2052 Multimap<?, ?> that = (Multimap<?, ?>) object;
2053 return multimap.asMap().equals(that.asMap());
2054 }
2055 return false;
2056 }
2057
2058
2059 }