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.base.Predicates.compose;
22 import static com.google.common.base.Predicates.equalTo;
23 import static com.google.common.base.Predicates.in;
24 import static com.google.common.base.Predicates.not;
25 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
26
27 import com.google.common.annotations.Beta;
28 import com.google.common.annotations.GwtCompatible;
29 import com.google.common.annotations.GwtIncompatible;
30 import com.google.common.base.Converter;
31 import com.google.common.base.Equivalence;
32 import com.google.common.base.Function;
33 import com.google.common.base.Joiner.MapJoiner;
34 import com.google.common.base.Objects;
35 import com.google.common.base.Preconditions;
36 import com.google.common.base.Predicate;
37 import com.google.common.base.Predicates;
38 import com.google.common.collect.MapDifference.ValueDifference;
39 import com.google.common.primitives.Ints;
40
41 import java.io.Serializable;
42 import java.util.AbstractCollection;
43 import java.util.AbstractMap;
44 import java.util.Collection;
45 import java.util.Collections;
46 import java.util.Comparator;
47 import java.util.EnumMap;
48 import java.util.Enumeration;
49 import java.util.HashMap;
50 import java.util.IdentityHashMap;
51 import java.util.Iterator;
52 import java.util.LinkedHashMap;
53 import java.util.Map;
54 import java.util.Map.Entry;
55 import java.util.NavigableMap;
56 import java.util.NavigableSet;
57 import java.util.Properties;
58 import java.util.Set;
59 import java.util.SortedMap;
60 import java.util.SortedSet;
61 import java.util.TreeMap;
62 import java.util.concurrent.ConcurrentMap;
63
64 import javax.annotation.Nullable;
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 @GwtCompatible(emulated = true)
82 public final class Maps {
83 private Maps() {}
84
85 private enum EntryFunction implements Function<Entry<?, ?>, Object> {
86 KEY {
87 @Override
88 @Nullable
89 public Object apply(Entry<?, ?> entry) {
90 return entry.getKey();
91 }
92 },
93 VALUE {
94 @Override
95 @Nullable
96 public Object apply(Entry<?, ?> entry) {
97 return entry.getValue();
98 }
99 };
100 }
101
102 @SuppressWarnings("unchecked")
103 static <K> Function<Entry<K, ?>, K> keyFunction() {
104 return (Function) EntryFunction.KEY;
105 }
106
107 @SuppressWarnings("unchecked")
108 static <V> Function<Entry<?, V>, V> valueFunction() {
109 return (Function) EntryFunction.VALUE;
110 }
111
112 static <K, V> Iterator<K> keyIterator(Iterator<Entry<K, V>> entryIterator) {
113 return Iterators.transform(entryIterator, Maps.<K>keyFunction());
114 }
115
116 static <K, V> Iterator<V> valueIterator(Iterator<Entry<K, V>> entryIterator) {
117 return Iterators.transform(entryIterator, Maps.<V>valueFunction());
118 }
119
120 static <K, V> UnmodifiableIterator<V> valueIterator(
121 final UnmodifiableIterator<Entry<K, V>> entryIterator) {
122 return new UnmodifiableIterator<V>() {
123 @Override
124 public boolean hasNext() {
125 return entryIterator.hasNext();
126 }
127
128 @Override
129 public V next() {
130 return entryIterator.next().getValue();
131 }
132 };
133 }
134
135
136
137
138
139
140
141
142
143
144
145
146 @GwtCompatible(serializable = true)
147 @Beta
148 public static <K extends Enum<K>, V> ImmutableMap<K, V> immutableEnumMap(
149 Map<K, ? extends V> map) {
150 if (map instanceof ImmutableEnumMap) {
151 @SuppressWarnings("unchecked")
152 ImmutableEnumMap<K, V> result = (ImmutableEnumMap<K, V>) map;
153 return result;
154 } else if (map.isEmpty()) {
155 return ImmutableMap.of();
156 } else {
157 for (Map.Entry<K, ? extends V> entry : map.entrySet()) {
158 checkNotNull(entry.getKey());
159 checkNotNull(entry.getValue());
160 }
161 return ImmutableEnumMap.asImmutable(new EnumMap<K, V>(map));
162 }
163 }
164
165
166
167
168
169
170
171
172
173
174
175
176 public static <K, V> HashMap<K, V> newHashMap() {
177 return new HashMap<K, V>();
178 }
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193 public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
194 int expectedSize) {
195 return new HashMap<K, V>(capacity(expectedSize));
196 }
197
198
199
200
201
202
203 static int capacity(int expectedSize) {
204 if (expectedSize < 3) {
205 checkNonnegative(expectedSize, "expectedSize");
206 return expectedSize + 1;
207 }
208 if (expectedSize < Ints.MAX_POWER_OF_TWO) {
209 return expectedSize + expectedSize / 3;
210 }
211 return Integer.MAX_VALUE;
212 }
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228 public static <K, V> HashMap<K, V> newHashMap(
229 Map<? extends K, ? extends V> map) {
230 return new HashMap<K, V>(map);
231 }
232
233
234
235
236
237
238
239
240
241
242 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
243 return new LinkedHashMap<K, V>();
244 }
245
246
247
248
249
250
251
252
253
254
255
256
257 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
258 Map<? extends K, ? extends V> map) {
259 return new LinkedHashMap<K, V>(map);
260 }
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277 public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
278 return new MapMaker().<K, V>makeMap();
279 }
280
281
282
283
284
285
286
287
288
289
290 public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
291 return new TreeMap<K, V>();
292 }
293
294
295
296
297
298
299
300
301
302
303
304
305
306 public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
307 return new TreeMap<K, V>(map);
308 }
309
310
311
312
313
314
315
316
317
318
319
320 public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
321 @Nullable Comparator<C> comparator) {
322
323
324
325
326
327 return new TreeMap<K, V>(comparator);
328 }
329
330
331
332
333
334
335
336 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
337 return new EnumMap<K, V>(checkNotNull(type));
338 }
339
340
341
342
343
344
345
346
347
348
349 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
350 Map<K, ? extends V> map) {
351 return new EnumMap<K, V>(map);
352 }
353
354
355
356
357
358
359 public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
360 return new IdentityHashMap<K, V>();
361 }
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379 @SuppressWarnings("unchecked")
380 public static <K, V> MapDifference<K, V> difference(
381 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
382 if (left instanceof SortedMap) {
383 SortedMap<K, ? extends V> sortedLeft = (SortedMap<K, ? extends V>) left;
384 SortedMapDifference<K, V> result = difference(sortedLeft, right);
385 return result;
386 }
387 return difference(left, right, Equivalence.equals());
388 }
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409 @Beta
410 public static <K, V> MapDifference<K, V> difference(
411 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right,
412 Equivalence<? super V> valueEquivalence) {
413 Preconditions.checkNotNull(valueEquivalence);
414
415 Map<K, V> onlyOnLeft = newHashMap();
416 Map<K, V> onlyOnRight = new HashMap<K, V>(right);
417 Map<K, V> onBoth = newHashMap();
418 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
419 doDifference(left, right, valueEquivalence, onlyOnLeft, onlyOnRight, onBoth, differences);
420 return new MapDifferenceImpl<K, V>(onlyOnLeft, onlyOnRight, onBoth, differences);
421 }
422
423 private static <K, V> void doDifference(
424 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right,
425 Equivalence<? super V> valueEquivalence,
426 Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
427 Map<K, MapDifference.ValueDifference<V>> differences) {
428 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
429 K leftKey = entry.getKey();
430 V leftValue = entry.getValue();
431 if (right.containsKey(leftKey)) {
432 V rightValue = onlyOnRight.remove(leftKey);
433 if (valueEquivalence.equivalent(leftValue, rightValue)) {
434 onBoth.put(leftKey, leftValue);
435 } else {
436 differences.put(
437 leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
438 }
439 } else {
440 onlyOnLeft.put(leftKey, leftValue);
441 }
442 }
443 }
444
445 private static <K, V> Map<K, V> unmodifiableMap(Map<K, V> map) {
446 if (map instanceof SortedMap) {
447 return Collections.unmodifiableSortedMap((SortedMap<K, ? extends V>) map);
448 } else {
449 return Collections.unmodifiableMap(map);
450 }
451 }
452
453 static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
454 final Map<K, V> onlyOnLeft;
455 final Map<K, V> onlyOnRight;
456 final Map<K, V> onBoth;
457 final Map<K, ValueDifference<V>> differences;
458
459 MapDifferenceImpl(Map<K, V> onlyOnLeft,
460 Map<K, V> onlyOnRight, Map<K, V> onBoth,
461 Map<K, ValueDifference<V>> differences) {
462 this.onlyOnLeft = unmodifiableMap(onlyOnLeft);
463 this.onlyOnRight = unmodifiableMap(onlyOnRight);
464 this.onBoth = unmodifiableMap(onBoth);
465 this.differences = unmodifiableMap(differences);
466 }
467
468 @Override
469 public boolean areEqual() {
470 return onlyOnLeft.isEmpty() && onlyOnRight.isEmpty() && differences.isEmpty();
471 }
472
473 @Override
474 public Map<K, V> entriesOnlyOnLeft() {
475 return onlyOnLeft;
476 }
477
478 @Override
479 public Map<K, V> entriesOnlyOnRight() {
480 return onlyOnRight;
481 }
482
483 @Override
484 public Map<K, V> entriesInCommon() {
485 return onBoth;
486 }
487
488 @Override
489 public Map<K, ValueDifference<V>> entriesDiffering() {
490 return differences;
491 }
492
493 @Override public boolean equals(Object object) {
494 if (object == this) {
495 return true;
496 }
497 if (object instanceof MapDifference) {
498 MapDifference<?, ?> other = (MapDifference<?, ?>) object;
499 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
500 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
501 && entriesInCommon().equals(other.entriesInCommon())
502 && entriesDiffering().equals(other.entriesDiffering());
503 }
504 return false;
505 }
506
507 @Override public int hashCode() {
508 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
509 entriesInCommon(), entriesDiffering());
510 }
511
512 @Override public String toString() {
513 if (areEqual()) {
514 return "equal";
515 }
516
517 StringBuilder result = new StringBuilder("not equal");
518 if (!onlyOnLeft.isEmpty()) {
519 result.append(": only on left=").append(onlyOnLeft);
520 }
521 if (!onlyOnRight.isEmpty()) {
522 result.append(": only on right=").append(onlyOnRight);
523 }
524 if (!differences.isEmpty()) {
525 result.append(": value differences=").append(differences);
526 }
527 return result.toString();
528 }
529 }
530
531 static class ValueDifferenceImpl<V>
532 implements MapDifference.ValueDifference<V> {
533 private final V left;
534 private final V right;
535
536 static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) {
537 return new ValueDifferenceImpl<V>(left, right);
538 }
539
540 private ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
541 this.left = left;
542 this.right = right;
543 }
544
545 @Override
546 public V leftValue() {
547 return left;
548 }
549
550 @Override
551 public V rightValue() {
552 return right;
553 }
554
555 @Override public boolean equals(@Nullable Object object) {
556 if (object instanceof MapDifference.ValueDifference) {
557 MapDifference.ValueDifference<?> that =
558 (MapDifference.ValueDifference<?>) object;
559 return Objects.equal(this.left, that.leftValue())
560 && Objects.equal(this.right, that.rightValue());
561 }
562 return false;
563 }
564
565 @Override public int hashCode() {
566 return Objects.hashCode(left, right);
567 }
568
569 @Override public String toString() {
570 return "(" + left + ", " + right + ")";
571 }
572 }
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593 public static <K, V> SortedMapDifference<K, V> difference(
594 SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
595 checkNotNull(left);
596 checkNotNull(right);
597 Comparator<? super K> comparator = orNaturalOrder(left.comparator());
598 SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator);
599 SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator);
600 onlyOnRight.putAll(right);
601 SortedMap<K, V> onBoth = Maps.newTreeMap(comparator);
602 SortedMap<K, MapDifference.ValueDifference<V>> differences =
603 Maps.newTreeMap(comparator);
604 doDifference(left, right, Equivalence.equals(), onlyOnLeft, onlyOnRight, onBoth, differences);
605 return new SortedMapDifferenceImpl<K, V>(onlyOnLeft, onlyOnRight, onBoth, differences);
606 }
607
608 static class SortedMapDifferenceImpl<K, V> extends MapDifferenceImpl<K, V>
609 implements SortedMapDifference<K, V> {
610 SortedMapDifferenceImpl(SortedMap<K, V> onlyOnLeft,
611 SortedMap<K, V> onlyOnRight, SortedMap<K, V> onBoth,
612 SortedMap<K, ValueDifference<V>> differences) {
613 super(onlyOnLeft, onlyOnRight, onBoth, differences);
614 }
615
616 @Override public SortedMap<K, ValueDifference<V>> entriesDiffering() {
617 return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering();
618 }
619
620 @Override public SortedMap<K, V> entriesInCommon() {
621 return (SortedMap<K, V>) super.entriesInCommon();
622 }
623
624 @Override public SortedMap<K, V> entriesOnlyOnLeft() {
625 return (SortedMap<K, V>) super.entriesOnlyOnLeft();
626 }
627
628 @Override public SortedMap<K, V> entriesOnlyOnRight() {
629 return (SortedMap<K, V>) super.entriesOnlyOnRight();
630 }
631 }
632
633
634
635
636
637
638 @SuppressWarnings("unchecked")
639 static <E> Comparator<? super E> orNaturalOrder(
640 @Nullable Comparator<? super E> comparator) {
641 if (comparator != null) {
642 return comparator;
643 }
644 return (Comparator<E>) Ordering.natural();
645 }
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674 @Beta
675 public static <K, V> Map<K, V> asMap(
676 Set<K> set, Function<? super K, V> function) {
677 if (set instanceof SortedSet) {
678 return asMap((SortedSet<K>) set, function);
679 } else {
680 return new AsMapView<K, V>(set, function);
681 }
682 }
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710 @Beta
711 public static <K, V> SortedMap<K, V> asMap(
712 SortedSet<K> set, Function<? super K, V> function) {
713 return Platform.mapsAsMapSortedSet(set, function);
714 }
715
716 static <K, V> SortedMap<K, V> asMapSortedIgnoreNavigable(SortedSet<K> set,
717 Function<? super K, V> function) {
718 return new SortedAsMapView<K, V>(set, function);
719 }
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747 @Beta
748 @GwtIncompatible("NavigableMap")
749 public static <K, V> NavigableMap<K, V> asMap(
750 NavigableSet<K> set, Function<? super K, V> function) {
751 return new NavigableAsMapView<K, V>(set, function);
752 }
753
754 private static class AsMapView<K, V> extends ImprovedAbstractMap<K, V> {
755
756 private final Set<K> set;
757 final Function<? super K, V> function;
758
759 Set<K> backingSet() {
760 return set;
761 }
762
763 AsMapView(Set<K> set, Function<? super K, V> function) {
764 this.set = checkNotNull(set);
765 this.function = checkNotNull(function);
766 }
767
768 @Override
769 public Set<K> createKeySet() {
770 return removeOnlySet(backingSet());
771 }
772
773 @Override
774 Collection<V> createValues() {
775 return Collections2.transform(set, function);
776 }
777
778 @Override
779 public int size() {
780 return backingSet().size();
781 }
782
783 @Override
784 public boolean containsKey(@Nullable Object key) {
785 return backingSet().contains(key);
786 }
787
788 @Override
789 public V get(@Nullable Object key) {
790 if (Collections2.safeContains(backingSet(), key)) {
791 @SuppressWarnings("unchecked")
792 K k = (K) key;
793 return function.apply(k);
794 } else {
795 return null;
796 }
797 }
798
799 @Override
800 public V remove(@Nullable Object key) {
801 if (backingSet().remove(key)) {
802 @SuppressWarnings("unchecked")
803 K k = (K) key;
804 return function.apply(k);
805 } else {
806 return null;
807 }
808 }
809
810 @Override
811 public void clear() {
812 backingSet().clear();
813 }
814
815 @Override
816 protected Set<Entry<K, V>> createEntrySet() {
817 return new EntrySet<K, V>() {
818 @Override
819 Map<K, V> map() {
820 return AsMapView.this;
821 }
822
823 @Override
824 public Iterator<Entry<K, V>> iterator() {
825 return asMapEntryIterator(backingSet(), function);
826 }
827 };
828 }
829 }
830
831 static <K, V> Iterator<Entry<K, V>> asMapEntryIterator(
832 Set<K> set, final Function<? super K, V> function) {
833 return new TransformedIterator<K, Entry<K,V>>(set.iterator()) {
834 @Override
835 Entry<K, V> transform(final K key) {
836 return immutableEntry(key, function.apply(key));
837 }
838 };
839 }
840
841 private static class SortedAsMapView<K, V> extends AsMapView<K, V>
842 implements SortedMap<K, V> {
843
844 SortedAsMapView(SortedSet<K> set, Function<? super K, V> function) {
845 super(set, function);
846 }
847
848 @Override
849 SortedSet<K> backingSet() {
850 return (SortedSet<K>) super.backingSet();
851 }
852
853 @Override
854 public Comparator<? super K> comparator() {
855 return backingSet().comparator();
856 }
857
858 @Override
859 public Set<K> keySet() {
860 return removeOnlySortedSet(backingSet());
861 }
862
863 @Override
864 public SortedMap<K, V> subMap(K fromKey, K toKey) {
865 return asMap(backingSet().subSet(fromKey, toKey), function);
866 }
867
868 @Override
869 public SortedMap<K, V> headMap(K toKey) {
870 return asMap(backingSet().headSet(toKey), function);
871 }
872
873 @Override
874 public SortedMap<K, V> tailMap(K fromKey) {
875 return asMap(backingSet().tailSet(fromKey), function);
876 }
877
878 @Override
879 public K firstKey() {
880 return backingSet().first();
881 }
882
883 @Override
884 public K lastKey() {
885 return backingSet().last();
886 }
887 }
888
889 @GwtIncompatible("NavigableMap")
890 private static final class NavigableAsMapView<K, V>
891 extends AbstractNavigableMap<K, V> {
892
893
894
895
896
897 private final NavigableSet<K> set;
898 private final Function<? super K, V> function;
899
900 NavigableAsMapView(NavigableSet<K> ks, Function<? super K, V> vFunction) {
901 this.set = checkNotNull(ks);
902 this.function = checkNotNull(vFunction);
903 }
904
905 @Override
906 public NavigableMap<K, V> subMap(
907 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
908 return asMap(set.subSet(fromKey, fromInclusive, toKey, toInclusive), function);
909 }
910
911 @Override
912 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
913 return asMap(set.headSet(toKey, inclusive), function);
914 }
915
916 @Override
917 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
918 return asMap(set.tailSet(fromKey, inclusive), function);
919 }
920
921 @Override
922 public Comparator<? super K> comparator() {
923 return set.comparator();
924 }
925
926 @Override
927 @Nullable
928 public V get(@Nullable Object key) {
929 if (Collections2.safeContains(set, key)) {
930 @SuppressWarnings("unchecked")
931 K k = (K) key;
932 return function.apply(k);
933 } else {
934 return null;
935 }
936 }
937
938 @Override
939 public void clear() {
940 set.clear();
941 }
942
943 @Override
944 Iterator<Entry<K, V>> entryIterator() {
945 return asMapEntryIterator(set, function);
946 }
947
948 @Override
949 Iterator<Entry<K, V>> descendingEntryIterator() {
950 return descendingMap().entrySet().iterator();
951 }
952
953 @Override
954 public NavigableSet<K> navigableKeySet() {
955 return removeOnlyNavigableSet(set);
956 }
957
958 @Override
959 public int size() {
960 return set.size();
961 }
962
963 @Override
964 public NavigableMap<K, V> descendingMap() {
965 return asMap(set.descendingSet(), function);
966 }
967 }
968
969 private static <E> Set<E> removeOnlySet(final Set<E> set) {
970 return new ForwardingSet<E>() {
971 @Override
972 protected Set<E> delegate() {
973 return set;
974 }
975
976 @Override
977 public boolean add(E element) {
978 throw new UnsupportedOperationException();
979 }
980
981 @Override
982 public boolean addAll(Collection<? extends E> es) {
983 throw new UnsupportedOperationException();
984 }
985 };
986 }
987
988 private static <E> SortedSet<E> removeOnlySortedSet(final SortedSet<E> set) {
989 return new ForwardingSortedSet<E>() {
990 @Override
991 protected SortedSet<E> delegate() {
992 return set;
993 }
994
995 @Override
996 public boolean add(E element) {
997 throw new UnsupportedOperationException();
998 }
999
1000 @Override
1001 public boolean addAll(Collection<? extends E> es) {
1002 throw new UnsupportedOperationException();
1003 }
1004
1005 @Override
1006 public SortedSet<E> headSet(E toElement) {
1007 return removeOnlySortedSet(super.headSet(toElement));
1008 }
1009
1010 @Override
1011 public SortedSet<E> subSet(E fromElement, E toElement) {
1012 return removeOnlySortedSet(super.subSet(fromElement, toElement));
1013 }
1014
1015 @Override
1016 public SortedSet<E> tailSet(E fromElement) {
1017 return removeOnlySortedSet(super.tailSet(fromElement));
1018 }
1019 };
1020 }
1021
1022 @GwtIncompatible("NavigableSet")
1023 private static <E> NavigableSet<E> removeOnlyNavigableSet(final NavigableSet<E> set) {
1024 return new ForwardingNavigableSet<E>() {
1025 @Override
1026 protected NavigableSet<E> delegate() {
1027 return set;
1028 }
1029
1030 @Override
1031 public boolean add(E element) {
1032 throw new UnsupportedOperationException();
1033 }
1034
1035 @Override
1036 public boolean addAll(Collection<? extends E> es) {
1037 throw new UnsupportedOperationException();
1038 }
1039
1040 @Override
1041 public SortedSet<E> headSet(E toElement) {
1042 return removeOnlySortedSet(super.headSet(toElement));
1043 }
1044
1045 @Override
1046 public SortedSet<E> subSet(E fromElement, E toElement) {
1047 return removeOnlySortedSet(
1048 super.subSet(fromElement, toElement));
1049 }
1050
1051 @Override
1052 public SortedSet<E> tailSet(E fromElement) {
1053 return removeOnlySortedSet(super.tailSet(fromElement));
1054 }
1055
1056 @Override
1057 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1058 return removeOnlyNavigableSet(super.headSet(toElement, inclusive));
1059 }
1060
1061 @Override
1062 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1063 return removeOnlyNavigableSet(super.tailSet(fromElement, inclusive));
1064 }
1065
1066 @Override
1067 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1068 E toElement, boolean toInclusive) {
1069 return removeOnlyNavigableSet(super.subSet(
1070 fromElement, fromInclusive, toElement, toInclusive));
1071 }
1072
1073 @Override
1074 public NavigableSet<E> descendingSet() {
1075 return removeOnlyNavigableSet(super.descendingSet());
1076 }
1077 };
1078 }
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094 @Beta
1095 public static <K, V> ImmutableMap<K, V> toMap(Iterable<K> keys,
1096 Function<? super K, V> valueFunction) {
1097 return toMap(keys.iterator(), valueFunction);
1098 }
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111 @Beta
1112 public static <K, V> ImmutableMap<K, V> toMap(Iterator<K> keys,
1113 Function<? super K, V> valueFunction) {
1114 checkNotNull(valueFunction);
1115
1116 Map<K, V> builder = newLinkedHashMap();
1117 while (keys.hasNext()) {
1118 K key = keys.next();
1119 builder.put(key, valueFunction.apply(key));
1120 }
1121 return ImmutableMap.copyOf(builder);
1122 }
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138 public static <K, V> ImmutableMap<K, V> uniqueIndex(
1139 Iterable<V> values, Function<? super V, K> keyFunction) {
1140 return uniqueIndex(values.iterator(), keyFunction);
1141 }
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158 public static <K, V> ImmutableMap<K, V> uniqueIndex(
1159 Iterator<V> values, Function<? super V, K> keyFunction) {
1160 checkNotNull(keyFunction);
1161 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
1162 while (values.hasNext()) {
1163 V value = values.next();
1164 builder.put(keyFunction.apply(value), value);
1165 }
1166 return builder.build();
1167 }
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182 @GwtIncompatible("java.util.Properties")
1183 public static ImmutableMap<String, String> fromProperties(
1184 Properties properties) {
1185 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
1186
1187 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
1188 String key = (String) e.nextElement();
1189 builder.put(key, properties.getProperty(key));
1190 }
1191
1192 return builder.build();
1193 }
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204 @GwtCompatible(serializable = true)
1205 public static <K, V> Entry<K, V> immutableEntry(
1206 @Nullable K key, @Nullable V value) {
1207 return new ImmutableEntry<K, V>(key, value);
1208 }
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
1219 Set<Entry<K, V>> entrySet) {
1220 return new UnmodifiableEntrySet<K, V>(
1221 Collections.unmodifiableSet(entrySet));
1222 }
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233 static <K, V> Entry<K, V> unmodifiableEntry(final Entry<? extends K, ? extends V> entry) {
1234 checkNotNull(entry);
1235 return new AbstractMapEntry<K, V>() {
1236 @Override public K getKey() {
1237 return entry.getKey();
1238 }
1239
1240 @Override public V getValue() {
1241 return entry.getValue();
1242 }
1243 };
1244 }
1245
1246
1247 static class UnmodifiableEntries<K, V>
1248 extends ForwardingCollection<Entry<K, V>> {
1249 private final Collection<Entry<K, V>> entries;
1250
1251 UnmodifiableEntries(Collection<Entry<K, V>> entries) {
1252 this.entries = entries;
1253 }
1254
1255 @Override protected Collection<Entry<K, V>> delegate() {
1256 return entries;
1257 }
1258
1259 @Override public Iterator<Entry<K, V>> iterator() {
1260 final Iterator<Entry<K, V>> delegate = super.iterator();
1261 return new UnmodifiableIterator<Entry<K, V>>() {
1262 @Override
1263 public boolean hasNext() {
1264 return delegate.hasNext();
1265 }
1266
1267 @Override public Entry<K, V> next() {
1268 return unmodifiableEntry(delegate.next());
1269 }
1270 };
1271 }
1272
1273
1274
1275 @Override public Object[] toArray() {
1276 return standardToArray();
1277 }
1278
1279 @Override public <T> T[] toArray(T[] array) {
1280 return standardToArray(array);
1281 }
1282 }
1283
1284
1285 static class UnmodifiableEntrySet<K, V>
1286 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
1287 UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
1288 super(entries);
1289 }
1290
1291
1292
1293 @Override public boolean equals(@Nullable Object object) {
1294 return Sets.equalsImpl(this, object);
1295 }
1296
1297 @Override public int hashCode() {
1298 return Sets.hashCodeImpl(this);
1299 }
1300 }
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313 @Beta
1314 public static <A, B> Converter<A, B> asConverter(final BiMap<A, B> bimap) {
1315 return new BiMapConverter<A, B>(bimap);
1316 }
1317
1318 private static final class BiMapConverter<A, B> extends Converter<A, B> implements Serializable {
1319 private final BiMap<A, B> bimap;
1320
1321 BiMapConverter(BiMap<A, B> bimap) {
1322 this.bimap = checkNotNull(bimap);
1323 }
1324
1325 @Override
1326 protected B doForward(A a) {
1327 return convert(bimap, a);
1328 }
1329
1330 @Override
1331 protected A doBackward(B b) {
1332 return convert(bimap.inverse(), b);
1333 }
1334
1335 private static <X, Y> Y convert(BiMap<X, Y> bimap, X input) {
1336 Y output = bimap.get(input);
1337 checkArgument(output != null, "No non-null mapping present for input: %s", input);
1338 return output;
1339 }
1340
1341 @Override
1342 public boolean equals(@Nullable Object object) {
1343 if (object instanceof BiMapConverter) {
1344 BiMapConverter<?, ?> that = (BiMapConverter<?, ?>) object;
1345 return this.bimap.equals(that.bimap);
1346 }
1347 return false;
1348 }
1349
1350 @Override
1351 public int hashCode() {
1352 return bimap.hashCode();
1353 }
1354
1355
1356 @Override
1357 public String toString() {
1358 return "Maps.asConverter(" + bimap + ")";
1359 }
1360
1361 private static final long serialVersionUID = 0L;
1362 }
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392 public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
1393 return Synchronized.biMap(bimap, null);
1394 }
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409 public static <K, V> BiMap<K, V> unmodifiableBiMap(
1410 BiMap<? extends K, ? extends V> bimap) {
1411 return new UnmodifiableBiMap<K, V>(bimap, null);
1412 }
1413
1414
1415 private static class UnmodifiableBiMap<K, V>
1416 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
1417 final Map<K, V> unmodifiableMap;
1418 final BiMap<? extends K, ? extends V> delegate;
1419 BiMap<V, K> inverse;
1420 transient Set<V> values;
1421
1422 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
1423 @Nullable BiMap<V, K> inverse) {
1424 unmodifiableMap = Collections.unmodifiableMap(delegate);
1425 this.delegate = delegate;
1426 this.inverse = inverse;
1427 }
1428
1429 @Override protected Map<K, V> delegate() {
1430 return unmodifiableMap;
1431 }
1432
1433 @Override
1434 public V forcePut(K key, V value) {
1435 throw new UnsupportedOperationException();
1436 }
1437
1438 @Override
1439 public BiMap<V, K> inverse() {
1440 BiMap<V, K> result = inverse;
1441 return (result == null)
1442 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
1443 : result;
1444 }
1445
1446 @Override public Set<V> values() {
1447 Set<V> result = values;
1448 return (result == null)
1449 ? values = Collections.unmodifiableSet(delegate.values())
1450 : result;
1451 }
1452
1453 private static final long serialVersionUID = 0;
1454 }
1455
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 public static <K, V1, V2> Map<K, V2> transformValues(
1493 Map<K, V1> fromMap, Function<? super V1, V2> function) {
1494 return transformEntries(fromMap, asEntryTransformer(function));
1495 }
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536 public static <K, V1, V2> SortedMap<K, V2> transformValues(
1537 SortedMap<K, V1> fromMap, Function<? super V1, V2> function) {
1538 return transformEntries(fromMap, asEntryTransformer(function));
1539 }
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582 @GwtIncompatible("NavigableMap")
1583 public static <K, V1, V2> NavigableMap<K, V2> transformValues(
1584 NavigableMap<K, V1> fromMap, Function<? super V1, V2> function) {
1585 return transformEntries(fromMap, asEntryTransformer(function));
1586 }
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639 public static <K, V1, V2> Map<K, V2> transformEntries(
1640 Map<K, V1> fromMap,
1641 EntryTransformer<? super K, ? super V1, V2> transformer) {
1642 if (fromMap instanceof SortedMap) {
1643 return transformEntries((SortedMap<K, V1>) fromMap, transformer);
1644 }
1645 return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
1646 }
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700 public static <K, V1, V2> SortedMap<K, V2> transformEntries(
1701 SortedMap<K, V1> fromMap,
1702 EntryTransformer<? super K, ? super V1, V2> transformer) {
1703 return Platform.mapsTransformEntriesSortedMap(fromMap, transformer);
1704 }
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759 @GwtIncompatible("NavigableMap")
1760 public static <K, V1, V2> NavigableMap<K, V2> transformEntries(
1761 final NavigableMap<K, V1> fromMap,
1762 EntryTransformer<? super K, ? super V1, V2> transformer) {
1763 return new TransformedEntriesNavigableMap<K, V1, V2>(fromMap, transformer);
1764 }
1765
1766 static <K, V1, V2> SortedMap<K, V2> transformEntriesIgnoreNavigable(
1767 SortedMap<K, V1> fromMap,
1768 EntryTransformer<? super K, ? super V1, V2> transformer) {
1769 return new TransformedEntriesSortedMap<K, V1, V2>(fromMap, transformer);
1770 }
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782 public interface EntryTransformer<K, V1, V2> {
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800 V2 transformEntry(@Nullable K key, @Nullable V1 value);
1801 }
1802
1803
1804
1805
1806 static <K, V1, V2> EntryTransformer<K, V1, V2>
1807 asEntryTransformer(final Function<? super V1, V2> function) {
1808 checkNotNull(function);
1809 return new EntryTransformer<K, V1, V2>() {
1810 @Override
1811 public V2 transformEntry(K key, V1 value) {
1812 return function.apply(value);
1813 }
1814 };
1815 }
1816
1817 static <K, V1, V2> Function<V1, V2> asValueToValueFunction(
1818 final EntryTransformer<? super K, V1, V2> transformer, final K key) {
1819 checkNotNull(transformer);
1820 return new Function<V1, V2>() {
1821 @Override
1822 public V2 apply(@Nullable V1 v1) {
1823 return transformer.transformEntry(key, v1);
1824 }
1825 };
1826 }
1827
1828
1829
1830
1831 static <K, V1, V2> Function<Entry<K, V1>, V2> asEntryToValueFunction(
1832 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1833 checkNotNull(transformer);
1834 return new Function<Entry<K, V1>, V2>() {
1835 @Override
1836 public V2 apply(Entry<K, V1> entry) {
1837 return transformer.transformEntry(entry.getKey(), entry.getValue());
1838 }
1839 };
1840 }
1841
1842
1843
1844
1845 static <V2, K, V1> Entry<K, V2> transformEntry(
1846 final EntryTransformer<? super K, ? super V1, V2> transformer, final Entry<K, V1> entry) {
1847 checkNotNull(transformer);
1848 checkNotNull(entry);
1849 return new AbstractMapEntry<K, V2>() {
1850 @Override
1851 public K getKey() {
1852 return entry.getKey();
1853 }
1854
1855 @Override
1856 public V2 getValue() {
1857 return transformer.transformEntry(entry.getKey(), entry.getValue());
1858 }
1859 };
1860 }
1861
1862
1863
1864
1865 static <K, V1, V2> Function<Entry<K, V1>, Entry<K, V2>> asEntryToEntryFunction(
1866 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1867 checkNotNull(transformer);
1868 return new Function<Entry<K, V1>, Entry<K, V2>>() {
1869 @Override
1870 public Entry<K, V2> apply(final Entry<K, V1> entry) {
1871 return transformEntry(transformer, entry);
1872 }
1873 };
1874 }
1875
1876 static class TransformedEntriesMap<K, V1, V2>
1877 extends ImprovedAbstractMap<K, V2> {
1878 final Map<K, V1> fromMap;
1879 final EntryTransformer<? super K, ? super V1, V2> transformer;
1880
1881 TransformedEntriesMap(
1882 Map<K, V1> fromMap,
1883 EntryTransformer<? super K, ? super V1, V2> transformer) {
1884 this.fromMap = checkNotNull(fromMap);
1885 this.transformer = checkNotNull(transformer);
1886 }
1887
1888 @Override public int size() {
1889 return fromMap.size();
1890 }
1891
1892 @Override public boolean containsKey(Object key) {
1893 return fromMap.containsKey(key);
1894 }
1895
1896
1897 @SuppressWarnings("unchecked")
1898 @Override public V2 get(Object key) {
1899 V1 value = fromMap.get(key);
1900 return (value != null || fromMap.containsKey(key))
1901 ? transformer.transformEntry((K) key, value)
1902 : null;
1903 }
1904
1905
1906 @SuppressWarnings("unchecked")
1907 @Override public V2 remove(Object key) {
1908 return fromMap.containsKey(key)
1909 ? transformer.transformEntry((K) key, fromMap.remove(key))
1910 : null;
1911 }
1912
1913 @Override public void clear() {
1914 fromMap.clear();
1915 }
1916
1917 @Override public Set<K> keySet() {
1918 return fromMap.keySet();
1919 }
1920
1921 @Override
1922 protected Set<Entry<K, V2>> createEntrySet() {
1923 return new EntrySet<K, V2>() {
1924 @Override Map<K, V2> map() {
1925 return TransformedEntriesMap.this;
1926 }
1927
1928 @Override public Iterator<Entry<K, V2>> iterator() {
1929 return Iterators.transform(fromMap.entrySet().iterator(),
1930 Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
1931 }
1932 };
1933 }
1934 }
1935
1936 static class TransformedEntriesSortedMap<K, V1, V2>
1937 extends TransformedEntriesMap<K, V1, V2> implements SortedMap<K, V2> {
1938
1939 protected SortedMap<K, V1> fromMap() {
1940 return (SortedMap<K, V1>) fromMap;
1941 }
1942
1943 TransformedEntriesSortedMap(SortedMap<K, V1> fromMap,
1944 EntryTransformer<? super K, ? super V1, V2> transformer) {
1945 super(fromMap, transformer);
1946 }
1947
1948 @Override public Comparator<? super K> comparator() {
1949 return fromMap().comparator();
1950 }
1951
1952 @Override public K firstKey() {
1953 return fromMap().firstKey();
1954 }
1955
1956 @Override public SortedMap<K, V2> headMap(K toKey) {
1957 return transformEntries(fromMap().headMap(toKey), transformer);
1958 }
1959
1960 @Override public K lastKey() {
1961 return fromMap().lastKey();
1962 }
1963
1964 @Override public SortedMap<K, V2> subMap(K fromKey, K toKey) {
1965 return transformEntries(
1966 fromMap().subMap(fromKey, toKey), transformer);
1967 }
1968
1969 @Override public SortedMap<K, V2> tailMap(K fromKey) {
1970 return transformEntries(fromMap().tailMap(fromKey), transformer);
1971 }
1972 }
1973
1974 @GwtIncompatible("NavigableMap")
1975 private static class TransformedEntriesNavigableMap<K, V1, V2>
1976 extends TransformedEntriesSortedMap<K, V1, V2>
1977 implements NavigableMap<K, V2> {
1978
1979 TransformedEntriesNavigableMap(NavigableMap<K, V1> fromMap,
1980 EntryTransformer<? super K, ? super V1, V2> transformer) {
1981 super(fromMap, transformer);
1982 }
1983
1984 @Override public Entry<K, V2> ceilingEntry(K key) {
1985 return transformEntry(fromMap().ceilingEntry(key));
1986 }
1987
1988 @Override public K ceilingKey(K key) {
1989 return fromMap().ceilingKey(key);
1990 }
1991
1992 @Override public NavigableSet<K> descendingKeySet() {
1993 return fromMap().descendingKeySet();
1994 }
1995
1996 @Override public NavigableMap<K, V2> descendingMap() {
1997 return transformEntries(fromMap().descendingMap(), transformer);
1998 }
1999
2000 @Override public Entry<K, V2> firstEntry() {
2001 return transformEntry(fromMap().firstEntry());
2002 }
2003 @Override public Entry<K, V2> floorEntry(K key) {
2004 return transformEntry(fromMap().floorEntry(key));
2005 }
2006
2007 @Override public K floorKey(K key) {
2008 return fromMap().floorKey(key);
2009 }
2010
2011 @Override public NavigableMap<K, V2> headMap(K toKey) {
2012 return headMap(toKey, false);
2013 }
2014
2015 @Override public NavigableMap<K, V2> headMap(K toKey, boolean inclusive) {
2016 return transformEntries(
2017 fromMap().headMap(toKey, inclusive), transformer);
2018 }
2019
2020 @Override public Entry<K, V2> higherEntry(K key) {
2021 return transformEntry(fromMap().higherEntry(key));
2022 }
2023
2024 @Override public K higherKey(K key) {
2025 return fromMap().higherKey(key);
2026 }
2027
2028 @Override public Entry<K, V2> lastEntry() {
2029 return transformEntry(fromMap().lastEntry());
2030 }
2031
2032 @Override public Entry<K, V2> lowerEntry(K key) {
2033 return transformEntry(fromMap().lowerEntry(key));
2034 }
2035
2036 @Override public K lowerKey(K key) {
2037 return fromMap().lowerKey(key);
2038 }
2039
2040 @Override public NavigableSet<K> navigableKeySet() {
2041 return fromMap().navigableKeySet();
2042 }
2043
2044 @Override public Entry<K, V2> pollFirstEntry() {
2045 return transformEntry(fromMap().pollFirstEntry());
2046 }
2047
2048 @Override public Entry<K, V2> pollLastEntry() {
2049 return transformEntry(fromMap().pollLastEntry());
2050 }
2051
2052 @Override public NavigableMap<K, V2> subMap(
2053 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2054 return transformEntries(
2055 fromMap().subMap(fromKey, fromInclusive, toKey, toInclusive),
2056 transformer);
2057 }
2058
2059 @Override public NavigableMap<K, V2> subMap(K fromKey, K toKey) {
2060 return subMap(fromKey, true, toKey, false);
2061 }
2062
2063 @Override public NavigableMap<K, V2> tailMap(K fromKey) {
2064 return tailMap(fromKey, true);
2065 }
2066
2067 @Override public NavigableMap<K, V2> tailMap(K fromKey, boolean inclusive) {
2068 return transformEntries(
2069 fromMap().tailMap(fromKey, inclusive), transformer);
2070 }
2071
2072 @Nullable
2073 private Entry<K, V2> transformEntry(@Nullable Entry<K, V1> entry) {
2074 return (entry == null) ? null : Maps.transformEntry(transformer, entry);
2075 }
2076
2077 @Override protected NavigableMap<K, V1> fromMap() {
2078 return (NavigableMap<K, V1>) super.fromMap();
2079 }
2080 }
2081
2082 static <K> Predicate<Entry<K, ?>> keyPredicateOnEntries(Predicate<? super K> keyPredicate) {
2083 return compose(keyPredicate, Maps.<K>keyFunction());
2084 }
2085
2086 static <V> Predicate<Entry<?, V>> valuePredicateOnEntries(Predicate<? super V> valuePredicate) {
2087 return compose(valuePredicate, Maps.<V>valueFunction());
2088 }
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118 public static <K, V> Map<K, V> filterKeys(
2119 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2120 if (unfiltered instanceof SortedMap) {
2121 return filterKeys((SortedMap<K, V>) unfiltered, keyPredicate);
2122 } else if (unfiltered instanceof BiMap) {
2123 return filterKeys((BiMap<K, V>) unfiltered, keyPredicate);
2124 }
2125 checkNotNull(keyPredicate);
2126 Predicate<Entry<K, ?>> entryPredicate = keyPredicateOnEntries(keyPredicate);
2127 return (unfiltered instanceof AbstractFilteredMap)
2128 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
2129 : new FilteredKeyMap<K, V>(
2130 checkNotNull(unfiltered), keyPredicate, entryPredicate);
2131 }
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163 public static <K, V> SortedMap<K, V> filterKeys(
2164 SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2165
2166
2167 return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2168 }
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200 @GwtIncompatible("NavigableMap")
2201 public static <K, V> NavigableMap<K, V> filterKeys(
2202 NavigableMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2203
2204
2205 return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2206 }
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233 public static <K, V> BiMap<K, V> filterKeys(
2234 BiMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2235 checkNotNull(keyPredicate);
2236 return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2237 }
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268 public static <K, V> Map<K, V> filterValues(
2269 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2270 if (unfiltered instanceof SortedMap) {
2271 return filterValues((SortedMap<K, V>) unfiltered, valuePredicate);
2272 } else if (unfiltered instanceof BiMap) {
2273 return filterValues((BiMap<K, V>) unfiltered, valuePredicate);
2274 }
2275 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2276 }
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309 public static <K, V> SortedMap<K, V> filterValues(
2310 SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2311 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2312 }
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345 @GwtIncompatible("NavigableMap")
2346 public static <K, V> NavigableMap<K, V> filterValues(
2347 NavigableMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2348 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2349 }
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379 public static <K, V> BiMap<K, V> filterValues(
2380 BiMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2381 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2382 }
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413 public static <K, V> Map<K, V> filterEntries(
2414 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2415 if (unfiltered instanceof SortedMap) {
2416 return filterEntries((SortedMap<K, V>) unfiltered, entryPredicate);
2417 } else if (unfiltered instanceof BiMap) {
2418 return filterEntries((BiMap<K, V>) unfiltered, entryPredicate);
2419 }
2420 checkNotNull(entryPredicate);
2421 return (unfiltered instanceof AbstractFilteredMap)
2422 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
2423 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2424 }
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457 public static <K, V> SortedMap<K, V> filterEntries(
2458 SortedMap<K, V> unfiltered,
2459 Predicate<? super Entry<K, V>> entryPredicate) {
2460 return Platform.mapsFilterSortedMap(unfiltered, entryPredicate);
2461 }
2462
2463 static <K, V> SortedMap<K, V> filterSortedIgnoreNavigable(
2464 SortedMap<K, V> unfiltered,
2465 Predicate<? super Entry<K, V>> entryPredicate) {
2466 checkNotNull(entryPredicate);
2467 return (unfiltered instanceof FilteredEntrySortedMap)
2468 ? filterFiltered((FilteredEntrySortedMap<K, V>) unfiltered, entryPredicate)
2469 : new FilteredEntrySortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2470 }
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503 @GwtIncompatible("NavigableMap")
2504 public static <K, V> NavigableMap<K, V> filterEntries(
2505 NavigableMap<K, V> unfiltered,
2506 Predicate<? super Entry<K, V>> entryPredicate) {
2507 checkNotNull(entryPredicate);
2508 return (unfiltered instanceof FilteredEntryNavigableMap)
2509 ? filterFiltered((FilteredEntryNavigableMap<K, V>) unfiltered, entryPredicate)
2510 : new FilteredEntryNavigableMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2511 }
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540 public static <K, V> BiMap<K, V> filterEntries(
2541 BiMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2542 checkNotNull(unfiltered);
2543 checkNotNull(entryPredicate);
2544 return (unfiltered instanceof FilteredEntryBiMap)
2545 ? filterFiltered((FilteredEntryBiMap<K, V>) unfiltered, entryPredicate)
2546 : new FilteredEntryBiMap<K, V>(unfiltered, entryPredicate);
2547 }
2548
2549
2550
2551
2552
2553 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
2554 Predicate<? super Entry<K, V>> entryPredicate) {
2555 return new FilteredEntryMap<K, V>(map.unfiltered,
2556 Predicates.<Entry<K, V>>and(map.predicate, entryPredicate));
2557 }
2558
2559 private abstract static class AbstractFilteredMap<K, V>
2560 extends ImprovedAbstractMap<K, V> {
2561 final Map<K, V> unfiltered;
2562 final Predicate<? super Entry<K, V>> predicate;
2563
2564 AbstractFilteredMap(
2565 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2566 this.unfiltered = unfiltered;
2567 this.predicate = predicate;
2568 }
2569
2570 boolean apply(@Nullable Object key, @Nullable V value) {
2571
2572
2573 @SuppressWarnings("unchecked")
2574 K k = (K) key;
2575 return predicate.apply(Maps.immutableEntry(k, value));
2576 }
2577
2578 @Override public V put(K key, V value) {
2579 checkArgument(apply(key, value));
2580 return unfiltered.put(key, value);
2581 }
2582
2583 @Override public void putAll(Map<? extends K, ? extends V> map) {
2584 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
2585 checkArgument(apply(entry.getKey(), entry.getValue()));
2586 }
2587 unfiltered.putAll(map);
2588 }
2589
2590 @Override public boolean containsKey(Object key) {
2591 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
2592 }
2593
2594 @Override public V get(Object key) {
2595 V value = unfiltered.get(key);
2596 return ((value != null) && apply(key, value)) ? value : null;
2597 }
2598
2599 @Override public boolean isEmpty() {
2600 return entrySet().isEmpty();
2601 }
2602
2603 @Override public V remove(Object key) {
2604 return containsKey(key) ? unfiltered.remove(key) : null;
2605 }
2606
2607 @Override
2608 Collection<V> createValues() {
2609 return new FilteredMapValues<K, V>(this, unfiltered, predicate);
2610 }
2611 }
2612
2613 private static final class FilteredMapValues<K, V> extends Maps.Values<K, V> {
2614 Map<K, V> unfiltered;
2615 Predicate<? super Entry<K, V>> predicate;
2616
2617 FilteredMapValues(Map<K, V> filteredMap, Map<K, V> unfiltered,
2618 Predicate<? super Entry<K, V>> predicate) {
2619 super(filteredMap);
2620 this.unfiltered = unfiltered;
2621 this.predicate = predicate;
2622 }
2623
2624 @Override public boolean remove(Object o) {
2625 return Iterables.removeFirstMatching(unfiltered.entrySet(),
2626 Predicates.<Entry<K, V>>and(predicate, Maps.<V>valuePredicateOnEntries(equalTo(o))))
2627 != null;
2628 }
2629
2630 private boolean removeIf(Predicate<? super V> valuePredicate) {
2631 return Iterables.removeIf(unfiltered.entrySet(), Predicates.<Entry<K, V>>and(
2632 predicate, Maps.<V>valuePredicateOnEntries(valuePredicate)));
2633 }
2634
2635 @Override public boolean removeAll(Collection<?> collection) {
2636 return removeIf(in(collection));
2637 }
2638
2639 @Override public boolean retainAll(Collection<?> collection) {
2640 return removeIf(not(in(collection)));
2641 }
2642
2643 @Override public Object[] toArray() {
2644
2645 return Lists.newArrayList(iterator()).toArray();
2646 }
2647
2648 @Override public <T> T[] toArray(T[] array) {
2649 return Lists.newArrayList(iterator()).toArray(array);
2650 }
2651 }
2652
2653 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
2654 Predicate<? super K> keyPredicate;
2655
2656 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
2657 Predicate<? super Entry<K, V>> entryPredicate) {
2658 super(unfiltered, entryPredicate);
2659 this.keyPredicate = keyPredicate;
2660 }
2661
2662 @Override
2663 protected Set<Entry<K, V>> createEntrySet() {
2664 return Sets.filter(unfiltered.entrySet(), predicate);
2665 }
2666
2667 @Override
2668 Set<K> createKeySet() {
2669 return Sets.filter(unfiltered.keySet(), keyPredicate);
2670 }
2671
2672
2673
2674 @Override
2675 @SuppressWarnings("unchecked")
2676 public boolean containsKey(Object key) {
2677 return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
2678 }
2679 }
2680
2681 static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
2682
2683
2684
2685
2686 final Set<Entry<K, V>> filteredEntrySet;
2687
2688 FilteredEntryMap(
2689 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2690 super(unfiltered, entryPredicate);
2691 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
2692 }
2693
2694 @Override
2695 protected Set<Entry<K, V>> createEntrySet() {
2696 return new EntrySet();
2697 }
2698
2699 private class EntrySet extends ForwardingSet<Entry<K, V>> {
2700 @Override protected Set<Entry<K, V>> delegate() {
2701 return filteredEntrySet;
2702 }
2703
2704 @Override public Iterator<Entry<K, V>> iterator() {
2705 return new TransformedIterator<Entry<K, V>, Entry<K, V>>(filteredEntrySet.iterator()) {
2706 @Override
2707 Entry<K, V> transform(final Entry<K, V> entry) {
2708 return new ForwardingMapEntry<K, V>() {
2709 @Override
2710 protected Entry<K, V> delegate() {
2711 return entry;
2712 }
2713
2714 @Override
2715 public V setValue(V newValue) {
2716 checkArgument(apply(getKey(), newValue));
2717 return super.setValue(newValue);
2718 }
2719 };
2720 }
2721 };
2722 }
2723 }
2724
2725 @Override
2726 Set<K> createKeySet() {
2727 return new KeySet();
2728 }
2729
2730 class KeySet extends Maps.KeySet<K, V> {
2731 KeySet() {
2732 super(FilteredEntryMap.this);
2733 }
2734
2735 @Override public boolean remove(Object o) {
2736 if (containsKey(o)) {
2737 unfiltered.remove(o);
2738 return true;
2739 }
2740 return false;
2741 }
2742
2743 private boolean removeIf(Predicate<? super K> keyPredicate) {
2744 return Iterables.removeIf(unfiltered.entrySet(), Predicates.<Entry<K, V>>and(
2745 predicate, Maps.<K>keyPredicateOnEntries(keyPredicate)));
2746 }
2747
2748 @Override
2749 public boolean removeAll(Collection<?> c) {
2750 return removeIf(in(c));
2751 }
2752
2753 @Override
2754 public boolean retainAll(Collection<?> c) {
2755 return removeIf(not(in(c)));
2756 }
2757
2758 @Override public Object[] toArray() {
2759
2760 return Lists.newArrayList(iterator()).toArray();
2761 }
2762
2763 @Override public <T> T[] toArray(T[] array) {
2764 return Lists.newArrayList(iterator()).toArray(array);
2765 }
2766 }
2767 }
2768
2769
2770
2771
2772
2773 private static <K, V> SortedMap<K, V> filterFiltered(
2774 FilteredEntrySortedMap<K, V> map,
2775 Predicate<? super Entry<K, V>> entryPredicate) {
2776 Predicate<Entry<K, V>> predicate
2777 = Predicates.and(map.predicate, entryPredicate);
2778 return new FilteredEntrySortedMap<K, V>(map.sortedMap(), predicate);
2779 }
2780
2781 private static class FilteredEntrySortedMap<K, V>
2782 extends FilteredEntryMap<K, V> implements SortedMap<K, V> {
2783
2784 FilteredEntrySortedMap(SortedMap<K, V> unfiltered,
2785 Predicate<? super Entry<K, V>> entryPredicate) {
2786 super(unfiltered, entryPredicate);
2787 }
2788
2789 SortedMap<K, V> sortedMap() {
2790 return (SortedMap<K, V>) unfiltered;
2791 }
2792
2793 @Override public SortedSet<K> keySet() {
2794 return (SortedSet<K>) super.keySet();
2795 }
2796
2797 @Override
2798 SortedSet<K> createKeySet() {
2799 return new SortedKeySet();
2800 }
2801
2802 class SortedKeySet extends KeySet implements SortedSet<K> {
2803 @Override
2804 public Comparator<? super K> comparator() {
2805 return sortedMap().comparator();
2806 }
2807
2808 @Override
2809 public SortedSet<K> subSet(K fromElement, K toElement) {
2810 return (SortedSet<K>) subMap(fromElement, toElement).keySet();
2811 }
2812
2813 @Override
2814 public SortedSet<K> headSet(K toElement) {
2815 return (SortedSet<K>) headMap(toElement).keySet();
2816 }
2817
2818 @Override
2819 public SortedSet<K> tailSet(K fromElement) {
2820 return (SortedSet<K>) tailMap(fromElement).keySet();
2821 }
2822
2823 @Override
2824 public K first() {
2825 return firstKey();
2826 }
2827
2828 @Override
2829 public K last() {
2830 return lastKey();
2831 }
2832 }
2833
2834 @Override public Comparator<? super K> comparator() {
2835 return sortedMap().comparator();
2836 }
2837
2838 @Override public K firstKey() {
2839
2840 return keySet().iterator().next();
2841 }
2842
2843 @Override public K lastKey() {
2844 SortedMap<K, V> headMap = sortedMap();
2845 while (true) {
2846
2847 K key = headMap.lastKey();
2848 if (apply(key, unfiltered.get(key))) {
2849 return key;
2850 }
2851 headMap = sortedMap().headMap(key);
2852 }
2853 }
2854
2855 @Override public SortedMap<K, V> headMap(K toKey) {
2856 return new FilteredEntrySortedMap<K, V>(sortedMap().headMap(toKey), predicate);
2857 }
2858
2859 @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
2860 return new FilteredEntrySortedMap<K, V>(
2861 sortedMap().subMap(fromKey, toKey), predicate);
2862 }
2863
2864 @Override public SortedMap<K, V> tailMap(K fromKey) {
2865 return new FilteredEntrySortedMap<K, V>(
2866 sortedMap().tailMap(fromKey), predicate);
2867 }
2868 }
2869
2870
2871
2872
2873
2874 @GwtIncompatible("NavigableMap")
2875 private static <K, V> NavigableMap<K, V> filterFiltered(
2876 FilteredEntryNavigableMap<K, V> map,
2877 Predicate<? super Entry<K, V>> entryPredicate) {
2878 Predicate<Entry<K, V>> predicate
2879 = Predicates.and(map.entryPredicate, entryPredicate);
2880 return new FilteredEntryNavigableMap<K, V>(map.unfiltered, predicate);
2881 }
2882
2883 @GwtIncompatible("NavigableMap")
2884 private static class FilteredEntryNavigableMap<K, V> extends AbstractNavigableMap<K, V> {
2885
2886
2887
2888
2889
2890
2891 private final NavigableMap<K, V> unfiltered;
2892 private final Predicate<? super Entry<K, V>> entryPredicate;
2893 private final Map<K, V> filteredDelegate;
2894
2895 FilteredEntryNavigableMap(
2896 NavigableMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2897 this.unfiltered = checkNotNull(unfiltered);
2898 this.entryPredicate = entryPredicate;
2899 this.filteredDelegate = new FilteredEntryMap<K, V>(unfiltered, entryPredicate);
2900 }
2901
2902 @Override
2903 public Comparator<? super K> comparator() {
2904 return unfiltered.comparator();
2905 }
2906
2907 @Override
2908 public NavigableSet<K> navigableKeySet() {
2909 return new Maps.NavigableKeySet<K, V>(this) {
2910 @Override
2911 public boolean removeAll(Collection<?> c) {
2912 return Iterators.removeIf(unfiltered.entrySet().iterator(),
2913 Predicates.<Entry<K, V>>and(entryPredicate, Maps.<K>keyPredicateOnEntries(in(c))));
2914 }
2915
2916 @Override
2917 public boolean retainAll(Collection<?> c) {
2918 return Iterators.removeIf(unfiltered.entrySet().iterator(), Predicates.<Entry<K, V>>and(
2919 entryPredicate, Maps.<K>keyPredicateOnEntries(not(in(c)))));
2920 }
2921 };
2922 }
2923
2924 @Override
2925 public Collection<V> values() {
2926 return new FilteredMapValues<K, V>(this, unfiltered, entryPredicate);
2927 }
2928
2929 @Override
2930 Iterator<Entry<K, V>> entryIterator() {
2931 return Iterators.filter(unfiltered.entrySet().iterator(), entryPredicate);
2932 }
2933
2934 @Override
2935 Iterator<Entry<K, V>> descendingEntryIterator() {
2936 return Iterators.filter(unfiltered.descendingMap().entrySet().iterator(), entryPredicate);
2937 }
2938
2939 @Override
2940 public int size() {
2941 return filteredDelegate.size();
2942 }
2943
2944 @Override
2945 public boolean isEmpty() {
2946 return !Iterables.any(unfiltered.entrySet(), entryPredicate);
2947 }
2948
2949 @Override
2950 @Nullable
2951 public V get(@Nullable Object key) {
2952 return filteredDelegate.get(key);
2953 }
2954
2955 @Override
2956 public boolean containsKey(@Nullable Object key) {
2957 return filteredDelegate.containsKey(key);
2958 }
2959
2960 @Override
2961 public V put(K key, V value) {
2962 return filteredDelegate.put(key, value);
2963 }
2964
2965 @Override
2966 public V remove(@Nullable Object key) {
2967 return filteredDelegate.remove(key);
2968 }
2969
2970 @Override
2971 public void putAll(Map<? extends K, ? extends V> m) {
2972 filteredDelegate.putAll(m);
2973 }
2974
2975 @Override
2976 public void clear() {
2977 filteredDelegate.clear();
2978 }
2979
2980 @Override
2981 public Set<Entry<K, V>> entrySet() {
2982 return filteredDelegate.entrySet();
2983 }
2984
2985 @Override
2986 public Entry<K, V> pollFirstEntry() {
2987 return Iterables.removeFirstMatching(unfiltered.entrySet(), entryPredicate);
2988 }
2989
2990 @Override
2991 public Entry<K, V> pollLastEntry() {
2992 return Iterables.removeFirstMatching(unfiltered.descendingMap().entrySet(), entryPredicate);
2993 }
2994
2995 @Override
2996 public NavigableMap<K, V> descendingMap() {
2997 return filterEntries(unfiltered.descendingMap(), entryPredicate);
2998 }
2999
3000 @Override
3001 public NavigableMap<K, V> subMap(
3002 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3003 return filterEntries(
3004 unfiltered.subMap(fromKey, fromInclusive, toKey, toInclusive), entryPredicate);
3005 }
3006
3007 @Override
3008 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3009 return filterEntries(unfiltered.headMap(toKey, inclusive), entryPredicate);
3010 }
3011
3012 @Override
3013 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3014 return filterEntries(unfiltered.tailMap(fromKey, inclusive), entryPredicate);
3015 }
3016 }
3017
3018
3019
3020
3021
3022 private static <K, V> BiMap<K, V> filterFiltered(
3023 FilteredEntryBiMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
3024 Predicate<Entry<K, V>> predicate = Predicates.and(map.predicate, entryPredicate);
3025 return new FilteredEntryBiMap<K, V>(map.unfiltered(), predicate);
3026 }
3027
3028 static final class FilteredEntryBiMap<K, V> extends FilteredEntryMap<K, V>
3029 implements BiMap<K, V> {
3030 private final BiMap<V, K> inverse;
3031
3032 private static <K, V> Predicate<Entry<V, K>> inversePredicate(
3033 final Predicate<? super Entry<K, V>> forwardPredicate) {
3034 return new Predicate<Entry<V, K>>() {
3035 @Override
3036 public boolean apply(Entry<V, K> input) {
3037 return forwardPredicate.apply(
3038 Maps.immutableEntry(input.getValue(), input.getKey()));
3039 }
3040 };
3041 }
3042
3043 FilteredEntryBiMap(BiMap<K, V> delegate,
3044 Predicate<? super Entry<K, V>> predicate) {
3045 super(delegate, predicate);
3046 this.inverse = new FilteredEntryBiMap<V, K>(
3047 delegate.inverse(), inversePredicate(predicate), this);
3048 }
3049
3050 private FilteredEntryBiMap(
3051 BiMap<K, V> delegate, Predicate<? super Entry<K, V>> predicate,
3052 BiMap<V, K> inverse) {
3053 super(delegate, predicate);
3054 this.inverse = inverse;
3055 }
3056
3057 BiMap<K, V> unfiltered() {
3058 return (BiMap<K, V>) unfiltered;
3059 }
3060
3061 @Override
3062 public V forcePut(@Nullable K key, @Nullable V value) {
3063 checkArgument(apply(key, value));
3064 return unfiltered().forcePut(key, value);
3065 }
3066
3067 @Override
3068 public BiMap<V, K> inverse() {
3069 return inverse;
3070 }
3071
3072 @Override
3073 public Set<V> values() {
3074 return inverse.keySet();
3075 }
3076 }
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090 @GwtIncompatible("NavigableMap")
3091 public static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, V> map) {
3092 checkNotNull(map);
3093 if (map instanceof UnmodifiableNavigableMap) {
3094 return map;
3095 } else {
3096 return new UnmodifiableNavigableMap<K, V>(map);
3097 }
3098 }
3099
3100 @Nullable private static <K, V> Entry<K, V> unmodifiableOrNull(@Nullable Entry<K, V> entry) {
3101 return (entry == null) ? null : Maps.unmodifiableEntry(entry);
3102 }
3103
3104 @GwtIncompatible("NavigableMap")
3105 static class UnmodifiableNavigableMap<K, V>
3106 extends ForwardingSortedMap<K, V> implements NavigableMap<K, V>, Serializable {
3107 private final NavigableMap<K, V> delegate;
3108
3109 UnmodifiableNavigableMap(NavigableMap<K, V> delegate) {
3110 this.delegate = delegate;
3111 }
3112
3113 UnmodifiableNavigableMap(
3114 NavigableMap<K, V> delegate, UnmodifiableNavigableMap<K, V> descendingMap) {
3115 this.delegate = delegate;
3116 this.descendingMap = descendingMap;
3117 }
3118
3119 @Override
3120 protected SortedMap<K, V> delegate() {
3121 return Collections.unmodifiableSortedMap(delegate);
3122 }
3123
3124 @Override
3125 public Entry<K, V> lowerEntry(K key) {
3126 return unmodifiableOrNull(delegate.lowerEntry(key));
3127 }
3128
3129 @Override
3130 public K lowerKey(K key) {
3131 return delegate.lowerKey(key);
3132 }
3133
3134 @Override
3135 public Entry<K, V> floorEntry(K key) {
3136 return unmodifiableOrNull(delegate.floorEntry(key));
3137 }
3138
3139 @Override
3140 public K floorKey(K key) {
3141 return delegate.floorKey(key);
3142 }
3143
3144 @Override
3145 public Entry<K, V> ceilingEntry(K key) {
3146 return unmodifiableOrNull(delegate.ceilingEntry(key));
3147 }
3148
3149 @Override
3150 public K ceilingKey(K key) {
3151 return delegate.ceilingKey(key);
3152 }
3153
3154 @Override
3155 public Entry<K, V> higherEntry(K key) {
3156 return unmodifiableOrNull(delegate.higherEntry(key));
3157 }
3158
3159 @Override
3160 public K higherKey(K key) {
3161 return delegate.higherKey(key);
3162 }
3163
3164 @Override
3165 public Entry<K, V> firstEntry() {
3166 return unmodifiableOrNull(delegate.firstEntry());
3167 }
3168
3169 @Override
3170 public Entry<K, V> lastEntry() {
3171 return unmodifiableOrNull(delegate.lastEntry());
3172 }
3173
3174 @Override
3175 public final Entry<K, V> pollFirstEntry() {
3176 throw new UnsupportedOperationException();
3177 }
3178
3179 @Override
3180 public final Entry<K, V> pollLastEntry() {
3181 throw new UnsupportedOperationException();
3182 }
3183
3184 private transient UnmodifiableNavigableMap<K, V> descendingMap;
3185
3186 @Override
3187 public NavigableMap<K, V> descendingMap() {
3188 UnmodifiableNavigableMap<K, V> result = descendingMap;
3189 return (result == null)
3190 ? descendingMap = new UnmodifiableNavigableMap<K, V>(delegate.descendingMap(), this)
3191 : result;
3192 }
3193
3194 @Override
3195 public Set<K> keySet() {
3196 return navigableKeySet();
3197 }
3198
3199 @Override
3200 public NavigableSet<K> navigableKeySet() {
3201 return Sets.unmodifiableNavigableSet(delegate.navigableKeySet());
3202 }
3203
3204 @Override
3205 public NavigableSet<K> descendingKeySet() {
3206 return Sets.unmodifiableNavigableSet(delegate.descendingKeySet());
3207 }
3208
3209 @Override
3210 public SortedMap<K, V> subMap(K fromKey, K toKey) {
3211 return subMap(fromKey, true, toKey, false);
3212 }
3213
3214 @Override
3215 public SortedMap<K, V> headMap(K toKey) {
3216 return headMap(toKey, false);
3217 }
3218
3219 @Override
3220 public SortedMap<K, V> tailMap(K fromKey) {
3221 return tailMap(fromKey, true);
3222 }
3223
3224 @Override
3225 public
3226 NavigableMap<K, V>
3227 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3228 return Maps.unmodifiableNavigableMap(delegate.subMap(
3229 fromKey,
3230 fromInclusive,
3231 toKey,
3232 toInclusive));
3233 }
3234
3235 @Override
3236 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3237 return Maps.unmodifiableNavigableMap(delegate.headMap(toKey, inclusive));
3238 }
3239
3240 @Override
3241 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3242 return Maps.unmodifiableNavigableMap(delegate.tailMap(fromKey, inclusive));
3243 }
3244 }
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294 @GwtIncompatible("NavigableMap")
3295 public static <K, V> NavigableMap<K, V> synchronizedNavigableMap(
3296 NavigableMap<K, V> navigableMap) {
3297 return Synchronized.navigableMap(navigableMap);
3298 }
3299
3300
3301
3302
3303
3304
3305
3306
3307 @GwtCompatible
3308 abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
3309
3310
3311
3312
3313
3314 abstract Set<Entry<K, V>> createEntrySet();
3315
3316 private transient Set<Entry<K, V>> entrySet;
3317
3318 @Override public Set<Entry<K, V>> entrySet() {
3319 Set<Entry<K, V>> result = entrySet;
3320 return (result == null) ? entrySet = createEntrySet() : result;
3321 }
3322
3323 private transient Set<K> keySet;
3324
3325 @Override public Set<K> keySet() {
3326 Set<K> result = keySet;
3327 return (result == null) ? keySet = createKeySet() : result;
3328 }
3329
3330 Set<K> createKeySet() {
3331 return new KeySet<K, V>(this);
3332 }
3333
3334 private transient Collection<V> values;
3335
3336 @Override public Collection<V> values() {
3337 Collection<V> result = values;
3338 return (result == null) ? values = createValues() : result;
3339 }
3340
3341 Collection<V> createValues() {
3342 return new Values<K, V>(this);
3343 }
3344 }
3345
3346
3347
3348
3349
3350 static <V> V safeGet(Map<?, V> map, @Nullable Object key) {
3351 checkNotNull(map);
3352 try {
3353 return map.get(key);
3354 } catch (ClassCastException e) {
3355 return null;
3356 } catch (NullPointerException e) {
3357 return null;
3358 }
3359 }
3360
3361
3362
3363
3364
3365 static boolean safeContainsKey(Map<?, ?> map, Object key) {
3366 checkNotNull(map);
3367 try {
3368 return map.containsKey(key);
3369 } catch (ClassCastException e) {
3370 return false;
3371 } catch (NullPointerException e) {
3372 return false;
3373 }
3374 }
3375
3376
3377
3378
3379
3380 static <V> V safeRemove(Map<?, V> map, Object key) {
3381 checkNotNull(map);
3382 try {
3383 return map.remove(key);
3384 } catch (ClassCastException e) {
3385 return null;
3386 } catch (NullPointerException e) {
3387 return null;
3388 }
3389 }
3390
3391
3392
3393
3394 static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
3395 return Iterators.contains(keyIterator(map.entrySet().iterator()), key);
3396 }
3397
3398
3399
3400
3401 static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
3402 return Iterators.contains(valueIterator(map.entrySet().iterator()), value);
3403 }
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
3419 if (!(o instanceof Entry)) {
3420 return false;
3421 }
3422 return c.contains(unmodifiableEntry((Entry<?, ?>) o));
3423 }
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
3439 if (!(o instanceof Entry)) {
3440 return false;
3441 }
3442 return c.remove(unmodifiableEntry((Entry<?, ?>) o));
3443 }
3444
3445
3446
3447
3448 static boolean equalsImpl(Map<?, ?> map, Object object) {
3449 if (map == object) {
3450 return true;
3451 } else if (object instanceof Map) {
3452 Map<?, ?> o = (Map<?, ?>) object;
3453 return map.entrySet().equals(o.entrySet());
3454 }
3455 return false;
3456 }
3457
3458 static final MapJoiner STANDARD_JOINER =
3459 Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
3460
3461
3462
3463
3464 static String toStringImpl(Map<?, ?> map) {
3465 StringBuilder sb
3466 = Collections2.newStringBuilderForCollection(map.size()).append('{');
3467 STANDARD_JOINER.appendTo(sb, map);
3468 return sb.append('}').toString();
3469 }
3470
3471
3472
3473
3474 static <K, V> void putAllImpl(
3475 Map<K, V> self, Map<? extends K, ? extends V> map) {
3476 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
3477 self.put(entry.getKey(), entry.getValue());
3478 }
3479 }
3480
3481 static class KeySet<K, V> extends Sets.ImprovedAbstractSet<K> {
3482 final Map<K, V> map;
3483
3484 KeySet(Map<K, V> map) {
3485 this.map = checkNotNull(map);
3486 }
3487
3488 Map<K, V> map() {
3489 return map;
3490 }
3491
3492 @Override public Iterator<K> iterator() {
3493 return keyIterator(map().entrySet().iterator());
3494 }
3495
3496 @Override public int size() {
3497 return map().size();
3498 }
3499
3500 @Override public boolean isEmpty() {
3501 return map().isEmpty();
3502 }
3503
3504 @Override public boolean contains(Object o) {
3505 return map().containsKey(o);
3506 }
3507
3508 @Override public boolean remove(Object o) {
3509 if (contains(o)) {
3510 map().remove(o);
3511 return true;
3512 }
3513 return false;
3514 }
3515
3516 @Override public void clear() {
3517 map().clear();
3518 }
3519 }
3520
3521 @Nullable
3522 static <K> K keyOrNull(@Nullable Entry<K, ?> entry) {
3523 return (entry == null) ? null : entry.getKey();
3524 }
3525
3526 @Nullable
3527 static <V> V valueOrNull(@Nullable Entry<?, V> entry) {
3528 return (entry == null) ? null : entry.getValue();
3529 }
3530
3531 static class SortedKeySet<K, V> extends KeySet<K, V> implements SortedSet<K> {
3532 SortedKeySet(SortedMap<K, V> map) {
3533 super(map);
3534 }
3535
3536 @Override
3537 SortedMap<K, V> map() {
3538 return (SortedMap<K, V>) super.map();
3539 }
3540
3541 @Override
3542 public Comparator<? super K> comparator() {
3543 return map().comparator();
3544 }
3545
3546 @Override
3547 public SortedSet<K> subSet(K fromElement, K toElement) {
3548 return new SortedKeySet<K, V>(map().subMap(fromElement, toElement));
3549 }
3550
3551 @Override
3552 public SortedSet<K> headSet(K toElement) {
3553 return new SortedKeySet<K, V>(map().headMap(toElement));
3554 }
3555
3556 @Override
3557 public SortedSet<K> tailSet(K fromElement) {
3558 return new SortedKeySet<K, V>(map().tailMap(fromElement));
3559 }
3560
3561 @Override
3562 public K first() {
3563 return map().firstKey();
3564 }
3565
3566 @Override
3567 public K last() {
3568 return map().lastKey();
3569 }
3570 }
3571
3572 @GwtIncompatible("NavigableMap")
3573 static class NavigableKeySet<K, V> extends SortedKeySet<K, V> implements NavigableSet<K> {
3574 NavigableKeySet(NavigableMap<K, V> map) {
3575 super(map);
3576 }
3577
3578 @Override
3579 NavigableMap<K, V> map() {
3580 return (NavigableMap<K, V>) map;
3581 }
3582
3583 @Override
3584 public K lower(K e) {
3585 return map().lowerKey(e);
3586 }
3587
3588 @Override
3589 public K floor(K e) {
3590 return map().floorKey(e);
3591 }
3592
3593 @Override
3594 public K ceiling(K e) {
3595 return map().ceilingKey(e);
3596 }
3597
3598 @Override
3599 public K higher(K e) {
3600 return map().higherKey(e);
3601 }
3602
3603 @Override
3604 public K pollFirst() {
3605 return keyOrNull(map().pollFirstEntry());
3606 }
3607
3608 @Override
3609 public K pollLast() {
3610 return keyOrNull(map().pollLastEntry());
3611 }
3612
3613 @Override
3614 public NavigableSet<K> descendingSet() {
3615 return map().descendingKeySet();
3616 }
3617
3618 @Override
3619 public Iterator<K> descendingIterator() {
3620 return descendingSet().iterator();
3621 }
3622
3623 @Override
3624 public NavigableSet<K> subSet(
3625 K fromElement,
3626 boolean fromInclusive,
3627 K toElement,
3628 boolean toInclusive) {
3629 return map().subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet();
3630 }
3631
3632 @Override
3633 public NavigableSet<K> headSet(K toElement, boolean inclusive) {
3634 return map().headMap(toElement, inclusive).navigableKeySet();
3635 }
3636
3637 @Override
3638 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
3639 return map().tailMap(fromElement, inclusive).navigableKeySet();
3640 }
3641
3642 @Override
3643 public SortedSet<K> subSet(K fromElement, K toElement) {
3644 return subSet(fromElement, true, toElement, false);
3645 }
3646
3647 @Override
3648 public SortedSet<K> headSet(K toElement) {
3649 return headSet(toElement, false);
3650 }
3651
3652 @Override
3653 public SortedSet<K> tailSet(K fromElement) {
3654 return tailSet(fromElement, true);
3655 }
3656 }
3657
3658 static class Values<K, V> extends AbstractCollection<V> {
3659 final Map<K, V> map;
3660
3661 Values(Map<K, V> map) {
3662 this.map = checkNotNull(map);
3663 }
3664
3665 final Map<K, V> map() {
3666 return map;
3667 }
3668
3669 @Override public Iterator<V> iterator() {
3670 return valueIterator(map().entrySet().iterator());
3671 }
3672
3673 @Override public boolean remove(Object o) {
3674 try {
3675 return super.remove(o);
3676 } catch (UnsupportedOperationException e) {
3677 for (Entry<K, V> entry : map().entrySet()) {
3678 if (Objects.equal(o, entry.getValue())) {
3679 map().remove(entry.getKey());
3680 return true;
3681 }
3682 }
3683 return false;
3684 }
3685 }
3686
3687 @Override public boolean removeAll(Collection<?> c) {
3688 try {
3689 return super.removeAll(checkNotNull(c));
3690 } catch (UnsupportedOperationException e) {
3691 Set<K> toRemove = Sets.newHashSet();
3692 for (Entry<K, V> entry : map().entrySet()) {
3693 if (c.contains(entry.getValue())) {
3694 toRemove.add(entry.getKey());
3695 }
3696 }
3697 return map().keySet().removeAll(toRemove);
3698 }
3699 }
3700
3701 @Override public boolean retainAll(Collection<?> c) {
3702 try {
3703 return super.retainAll(checkNotNull(c));
3704 } catch (UnsupportedOperationException e) {
3705 Set<K> toRetain = Sets.newHashSet();
3706 for (Entry<K, V> entry : map().entrySet()) {
3707 if (c.contains(entry.getValue())) {
3708 toRetain.add(entry.getKey());
3709 }
3710 }
3711 return map().keySet().retainAll(toRetain);
3712 }
3713 }
3714
3715 @Override public int size() {
3716 return map().size();
3717 }
3718
3719 @Override public boolean isEmpty() {
3720 return map().isEmpty();
3721 }
3722
3723 @Override public boolean contains(@Nullable Object o) {
3724 return map().containsValue(o);
3725 }
3726
3727 @Override public void clear() {
3728 map().clear();
3729 }
3730 }
3731
3732 abstract static class EntrySet<K, V>
3733 extends Sets.ImprovedAbstractSet<Entry<K, V>> {
3734 abstract Map<K, V> map();
3735
3736 @Override public int size() {
3737 return map().size();
3738 }
3739
3740 @Override public void clear() {
3741 map().clear();
3742 }
3743
3744 @Override public boolean contains(Object o) {
3745 if (o instanceof Entry) {
3746 Entry<?, ?> entry = (Entry<?, ?>) o;
3747 Object key = entry.getKey();
3748 V value = Maps.safeGet(map(), key);
3749 return Objects.equal(value, entry.getValue())
3750 && (value != null || map().containsKey(key));
3751 }
3752 return false;
3753 }
3754
3755 @Override public boolean isEmpty() {
3756 return map().isEmpty();
3757 }
3758
3759 @Override public boolean remove(Object o) {
3760 if (contains(o)) {
3761 Entry<?, ?> entry = (Entry<?, ?>) o;
3762 return map().keySet().remove(entry.getKey());
3763 }
3764 return false;
3765 }
3766
3767 @Override public boolean removeAll(Collection<?> c) {
3768 try {
3769 return super.removeAll(checkNotNull(c));
3770 } catch (UnsupportedOperationException e) {
3771
3772 return Sets.removeAllImpl(this, c.iterator());
3773 }
3774 }
3775
3776 @Override public boolean retainAll(Collection<?> c) {
3777 try {
3778 return super.retainAll(checkNotNull(c));
3779 } catch (UnsupportedOperationException e) {
3780
3781 Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size());
3782 for (Object o : c) {
3783 if (contains(o)) {
3784 Entry<?, ?> entry = (Entry<?, ?>) o;
3785 keys.add(entry.getKey());
3786 }
3787 }
3788 return map().keySet().retainAll(keys);
3789 }
3790 }
3791 }
3792
3793 @GwtIncompatible("NavigableMap")
3794 abstract static class DescendingMap<K, V> extends ForwardingMap<K, V>
3795 implements NavigableMap<K, V> {
3796
3797 abstract NavigableMap<K, V> forward();
3798
3799 @Override
3800 protected final Map<K, V> delegate() {
3801 return forward();
3802 }
3803
3804 private transient Comparator<? super K> comparator;
3805
3806 @SuppressWarnings("unchecked")
3807 @Override
3808 public Comparator<? super K> comparator() {
3809 Comparator<? super K> result = comparator;
3810 if (result == null) {
3811 Comparator<? super K> forwardCmp = forward().comparator();
3812 if (forwardCmp == null) {
3813 forwardCmp = (Comparator) Ordering.natural();
3814 }
3815 result = comparator = reverse(forwardCmp);
3816 }
3817 return result;
3818 }
3819
3820
3821 private static <T> Ordering<T> reverse(Comparator<T> forward) {
3822 return Ordering.from(forward).reverse();
3823 }
3824
3825 @Override
3826 public K firstKey() {
3827 return forward().lastKey();
3828 }
3829
3830 @Override
3831 public K lastKey() {
3832 return forward().firstKey();
3833 }
3834
3835 @Override
3836 public Entry<K, V> lowerEntry(K key) {
3837 return forward().higherEntry(key);
3838 }
3839
3840 @Override
3841 public K lowerKey(K key) {
3842 return forward().higherKey(key);
3843 }
3844
3845 @Override
3846 public Entry<K, V> floorEntry(K key) {
3847 return forward().ceilingEntry(key);
3848 }
3849
3850 @Override
3851 public K floorKey(K key) {
3852 return forward().ceilingKey(key);
3853 }
3854
3855 @Override
3856 public Entry<K, V> ceilingEntry(K key) {
3857 return forward().floorEntry(key);
3858 }
3859
3860 @Override
3861 public K ceilingKey(K key) {
3862 return forward().floorKey(key);
3863 }
3864
3865 @Override
3866 public Entry<K, V> higherEntry(K key) {
3867 return forward().lowerEntry(key);
3868 }
3869
3870 @Override
3871 public K higherKey(K key) {
3872 return forward().lowerKey(key);
3873 }
3874
3875 @Override
3876 public Entry<K, V> firstEntry() {
3877 return forward().lastEntry();
3878 }
3879
3880 @Override
3881 public Entry<K, V> lastEntry() {
3882 return forward().firstEntry();
3883 }
3884
3885 @Override
3886 public Entry<K, V> pollFirstEntry() {
3887 return forward().pollLastEntry();
3888 }
3889
3890 @Override
3891 public Entry<K, V> pollLastEntry() {
3892 return forward().pollFirstEntry();
3893 }
3894
3895 @Override
3896 public NavigableMap<K, V> descendingMap() {
3897 return forward();
3898 }
3899
3900 private transient Set<Entry<K, V>> entrySet;
3901
3902 @Override
3903 public Set<Entry<K, V>> entrySet() {
3904 Set<Entry<K, V>> result = entrySet;
3905 return (result == null) ? entrySet = createEntrySet() : result;
3906 }
3907
3908 abstract Iterator<Entry<K, V>> entryIterator();
3909
3910 Set<Entry<K, V>> createEntrySet() {
3911 return new EntrySet<K, V>() {
3912 @Override
3913 Map<K, V> map() {
3914 return DescendingMap.this;
3915 }
3916
3917 @Override
3918 public Iterator<Entry<K, V>> iterator() {
3919 return entryIterator();
3920 }
3921 };
3922 }
3923
3924 @Override
3925 public Set<K> keySet() {
3926 return navigableKeySet();
3927 }
3928
3929 private transient NavigableSet<K> navigableKeySet;
3930
3931 @Override
3932 public NavigableSet<K> navigableKeySet() {
3933 NavigableSet<K> result = navigableKeySet;
3934 return (result == null) ? navigableKeySet = new NavigableKeySet<K, V>(this) : result;
3935 }
3936
3937 @Override
3938 public NavigableSet<K> descendingKeySet() {
3939 return forward().navigableKeySet();
3940 }
3941
3942 @Override
3943 public
3944 NavigableMap<K, V>
3945 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3946 return forward().subMap(toKey, toInclusive, fromKey, fromInclusive).descendingMap();
3947 }
3948
3949 @Override
3950 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3951 return forward().tailMap(toKey, inclusive).descendingMap();
3952 }
3953
3954 @Override
3955 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3956 return forward().headMap(fromKey, inclusive).descendingMap();
3957 }
3958
3959 @Override
3960 public SortedMap<K, V> subMap(K fromKey, K toKey) {
3961 return subMap(fromKey, true, toKey, false);
3962 }
3963
3964 @Override
3965 public SortedMap<K, V> headMap(K toKey) {
3966 return headMap(toKey, false);
3967 }
3968
3969 @Override
3970 public SortedMap<K, V> tailMap(K fromKey) {
3971 return tailMap(fromKey, true);
3972 }
3973
3974 @Override
3975 public Collection<V> values() {
3976 return new Values<K, V>(this);
3977 }
3978
3979 @Override
3980 public String toString() {
3981 return standardToString();
3982 }
3983 }
3984 }