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