001 /*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Equivalence;
026 import com.google.common.base.Function;
027 import com.google.common.base.Joiner.MapJoiner;
028 import com.google.common.base.Objects;
029 import com.google.common.base.Preconditions;
030 import com.google.common.base.Predicate;
031 import com.google.common.base.Predicates;
032 import com.google.common.collect.MapDifference.ValueDifference;
033 import com.google.common.primitives.Ints;
034
035 import java.io.Serializable;
036 import java.util.AbstractCollection;
037 import java.util.AbstractMap;
038 import java.util.Collection;
039 import java.util.Collections;
040 import java.util.Comparator;
041 import java.util.EnumMap;
042 import java.util.Enumeration;
043 import java.util.HashMap;
044 import java.util.IdentityHashMap;
045 import java.util.Iterator;
046 import java.util.LinkedHashMap;
047 import java.util.Map;
048 import java.util.Map.Entry;
049 import java.util.NavigableMap;
050 import java.util.NavigableSet;
051 import java.util.Properties;
052 import java.util.Set;
053 import java.util.SortedMap;
054 import java.util.SortedSet;
055 import java.util.TreeMap;
056 import java.util.concurrent.ConcurrentMap;
057
058 import javax.annotation.Nullable;
059
060 /**
061 * Static utility methods pertaining to {@link Map} instances (including instances of
062 * {@link SortedMap}, {@link BiMap}, etc.). Also see this class's counterparts
063 * {@link Lists}, {@link Sets} and {@link Queues}.
064 *
065 * <p>See the Guava User Guide article on <a href=
066 * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Maps">
067 * {@code Maps}</a>.
068 *
069 * @author Kevin Bourrillion
070 * @author Mike Bostock
071 * @author Isaac Shum
072 * @author Louis Wasserman
073 * @since 2.0 (imported from Google Collections Library)
074 */
075 @GwtCompatible(emulated = true)
076 public final class Maps {
077 private Maps() {}
078
079 /**
080 * Creates a <i>mutable</i>, empty {@code HashMap} instance.
081 *
082 * <p><b>Note:</b> if mutability is not required, use {@link
083 * ImmutableMap#of()} instead.
084 *
085 * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
086 * #newEnumMap} instead.
087 *
088 * @return a new, empty {@code HashMap}
089 */
090 public static <K, V> HashMap<K, V> newHashMap() {
091 return new HashMap<K, V>();
092 }
093
094 /**
095 * Creates a {@code HashMap} instance, with a high enough "initial capacity"
096 * that it <i>should</i> hold {@code expectedSize} elements without growth.
097 * This behavior cannot be broadly guaranteed, but it is observed to be true
098 * for OpenJDK 1.6. It also can't be guaranteed that the method isn't
099 * inadvertently <i>oversizing</i> the returned map.
100 *
101 * @param expectedSize the number of elements you expect to add to the
102 * returned map
103 * @return a new, empty {@code HashMap} with enough capacity to hold {@code
104 * expectedSize} elements without resizing
105 * @throws IllegalArgumentException if {@code expectedSize} is negative
106 */
107 public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
108 int expectedSize) {
109 return new HashMap<K, V>(capacity(expectedSize));
110 }
111
112 /**
113 * Returns a capacity that is sufficient to keep the map from being resized as
114 * long as it grows no larger than expectedSize and the load factor is >= its
115 * default (0.75).
116 */
117 static int capacity(int expectedSize) {
118 if (expectedSize < 3) {
119 checkArgument(expectedSize >= 0);
120 return expectedSize + 1;
121 }
122 if (expectedSize < Ints.MAX_POWER_OF_TWO) {
123 return expectedSize + expectedSize / 3;
124 }
125 return Integer.MAX_VALUE; // any large value
126 }
127
128 /**
129 * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
130 * the specified map.
131 *
132 * <p><b>Note:</b> if mutability is not required, use {@link
133 * ImmutableMap#copyOf(Map)} instead.
134 *
135 * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
136 * #newEnumMap} instead.
137 *
138 * @param map the mappings to be placed in the new map
139 * @return a new {@code HashMap} initialized with the mappings from {@code
140 * map}
141 */
142 public static <K, V> HashMap<K, V> newHashMap(
143 Map<? extends K, ? extends V> map) {
144 return new HashMap<K, V>(map);
145 }
146
147 /**
148 * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
149 * instance.
150 *
151 * <p><b>Note:</b> if mutability is not required, use {@link
152 * ImmutableMap#of()} instead.
153 *
154 * @return a new, empty {@code LinkedHashMap}
155 */
156 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
157 return new LinkedHashMap<K, V>();
158 }
159
160 /**
161 * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
162 * with the same mappings as the specified map.
163 *
164 * <p><b>Note:</b> if mutability is not required, use {@link
165 * ImmutableMap#copyOf(Map)} instead.
166 *
167 * @param map the mappings to be placed in the new map
168 * @return a new, {@code LinkedHashMap} initialized with the mappings from
169 * {@code map}
170 */
171 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
172 Map<? extends K, ? extends V> map) {
173 return new LinkedHashMap<K, V>(map);
174 }
175
176 /**
177 * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
178 * all optional operations of the ConcurrentMap interface. It does not permit
179 * null keys or values. It is serializable.
180 *
181 * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
182 *
183 * <p>It is preferable to use {@code MapMaker} directly (rather than through
184 * this method), as it presents numerous useful configuration options,
185 * such as the concurrency level, load factor, key/value reference types,
186 * and value computation.
187 *
188 * @return a new, empty {@code ConcurrentMap}
189 * @since 3.0
190 */
191 public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
192 return new MapMaker().<K, V>makeMap();
193 }
194
195 /**
196 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
197 * ordering of its elements.
198 *
199 * <p><b>Note:</b> if mutability is not required, use {@link
200 * ImmutableSortedMap#of()} instead.
201 *
202 * @return a new, empty {@code TreeMap}
203 */
204 public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
205 return new TreeMap<K, V>();
206 }
207
208 /**
209 * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
210 * the specified map and using the same ordering as the specified map.
211 *
212 * <p><b>Note:</b> if mutability is not required, use {@link
213 * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
214 *
215 * @param map the sorted map whose mappings are to be placed in the new map
216 * and whose comparator is to be used to sort the new map
217 * @return a new {@code TreeMap} initialized with the mappings from {@code
218 * map} and using the comparator of {@code map}
219 */
220 public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
221 return new TreeMap<K, V>(map);
222 }
223
224 /**
225 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
226 * comparator.
227 *
228 * <p><b>Note:</b> if mutability is not required, use {@code
229 * ImmutableSortedMap.orderedBy(comparator).build()} instead.
230 *
231 * @param comparator the comparator to sort the keys with
232 * @return a new, empty {@code TreeMap}
233 */
234 public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
235 @Nullable Comparator<C> comparator) {
236 // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
237 // work-around of a compiler type inference quirk that prevents the
238 // following code from being compiled:
239 // Comparator<Class<?>> comparator = null;
240 // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
241 return new TreeMap<K, V>(comparator);
242 }
243
244 /**
245 * Creates an {@code EnumMap} instance.
246 *
247 * @param type the key type for this map
248 * @return a new, empty {@code EnumMap}
249 */
250 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
251 return new EnumMap<K, V>(checkNotNull(type));
252 }
253
254 /**
255 * Creates an {@code EnumMap} with the same mappings as the specified map.
256 *
257 * @param map the map from which to initialize this {@code EnumMap}
258 * @return a new {@code EnumMap} initialized with the mappings from {@code
259 * map}
260 * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
261 * instance and contains no mappings
262 */
263 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
264 Map<K, ? extends V> map) {
265 return new EnumMap<K, V>(map);
266 }
267
268 /**
269 * Creates an {@code IdentityHashMap} instance.
270 *
271 * @return a new, empty {@code IdentityHashMap}
272 */
273 public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
274 return new IdentityHashMap<K, V>();
275 }
276
277 /**
278 * Computes the difference between two maps. This difference is an immutable
279 * snapshot of the state of the maps at the time this method is called. It
280 * will never change, even if the maps change at a later time.
281 *
282 * <p>Since this method uses {@code HashMap} instances internally, the keys of
283 * the supplied maps must be well-behaved with respect to
284 * {@link Object#equals} and {@link Object#hashCode}.
285 *
286 * <p><b>Note:</b>If you only need to know whether two maps have the same
287 * mappings, call {@code left.equals(right)} instead of this method.
288 *
289 * @param left the map to treat as the "left" map for purposes of comparison
290 * @param right the map to treat as the "right" map for purposes of comparison
291 * @return the difference between the two maps
292 */
293 @SuppressWarnings("unchecked")
294 public static <K, V> MapDifference<K, V> difference(
295 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
296 if (left instanceof SortedMap) {
297 SortedMap<K, ? extends V> sortedLeft = (SortedMap<K, ? extends V>) left;
298 SortedMapDifference<K, V> result = difference(sortedLeft, right);
299 return result;
300 }
301 return difference(left, right, Equivalence.equals());
302 }
303
304 /**
305 * Computes the difference between two maps. This difference is an immutable
306 * snapshot of the state of the maps at the time this method is called. It
307 * will never change, even if the maps change at a later time.
308 *
309 * <p>Values are compared using a provided equivalence, in the case of
310 * equality, the value on the 'left' is returned in the difference.
311 *
312 * <p>Since this method uses {@code HashMap} instances internally, the keys of
313 * the supplied maps must be well-behaved with respect to
314 * {@link Object#equals} and {@link Object#hashCode}.
315 *
316 * @param left the map to treat as the "left" map for purposes of comparison
317 * @param right the map to treat as the "right" map for purposes of comparison
318 * @param valueEquivalence the equivalence relationship to use to compare
319 * values
320 * @return the difference between the two maps
321 * @since 10.0
322 */
323 @Beta
324 public static <K, V> MapDifference<K, V> difference(
325 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right,
326 Equivalence<? super V> valueEquivalence) {
327 Preconditions.checkNotNull(valueEquivalence);
328
329 Map<K, V> onlyOnLeft = newHashMap();
330 Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
331 Map<K, V> onBoth = newHashMap();
332 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
333 boolean eq = true;
334
335 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
336 K leftKey = entry.getKey();
337 V leftValue = entry.getValue();
338 if (right.containsKey(leftKey)) {
339 V rightValue = onlyOnRight.remove(leftKey);
340 if (valueEquivalence.equivalent(leftValue, rightValue)) {
341 onBoth.put(leftKey, leftValue);
342 } else {
343 eq = false;
344 differences.put(
345 leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
346 }
347 } else {
348 eq = false;
349 onlyOnLeft.put(leftKey, leftValue);
350 }
351 }
352
353 boolean areEqual = eq && onlyOnRight.isEmpty();
354 return mapDifference(
355 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
356 }
357
358 private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
359 Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
360 Map<K, ValueDifference<V>> differences) {
361 return new MapDifferenceImpl<K, V>(areEqual,
362 Collections.unmodifiableMap(onlyOnLeft),
363 Collections.unmodifiableMap(onlyOnRight),
364 Collections.unmodifiableMap(onBoth),
365 Collections.unmodifiableMap(differences));
366 }
367
368 static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
369 final boolean areEqual;
370 final Map<K, V> onlyOnLeft;
371 final Map<K, V> onlyOnRight;
372 final Map<K, V> onBoth;
373 final Map<K, ValueDifference<V>> differences;
374
375 MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
376 Map<K, V> onlyOnRight, Map<K, V> onBoth,
377 Map<K, ValueDifference<V>> differences) {
378 this.areEqual = areEqual;
379 this.onlyOnLeft = onlyOnLeft;
380 this.onlyOnRight = onlyOnRight;
381 this.onBoth = onBoth;
382 this.differences = differences;
383 }
384
385 @Override
386 public boolean areEqual() {
387 return areEqual;
388 }
389
390 @Override
391 public Map<K, V> entriesOnlyOnLeft() {
392 return onlyOnLeft;
393 }
394
395 @Override
396 public Map<K, V> entriesOnlyOnRight() {
397 return onlyOnRight;
398 }
399
400 @Override
401 public Map<K, V> entriesInCommon() {
402 return onBoth;
403 }
404
405 @Override
406 public Map<K, ValueDifference<V>> entriesDiffering() {
407 return differences;
408 }
409
410 @Override public boolean equals(Object object) {
411 if (object == this) {
412 return true;
413 }
414 if (object instanceof MapDifference) {
415 MapDifference<?, ?> other = (MapDifference<?, ?>) object;
416 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
417 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
418 && entriesInCommon().equals(other.entriesInCommon())
419 && entriesDiffering().equals(other.entriesDiffering());
420 }
421 return false;
422 }
423
424 @Override public int hashCode() {
425 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
426 entriesInCommon(), entriesDiffering());
427 }
428
429 @Override public String toString() {
430 if (areEqual) {
431 return "equal";
432 }
433
434 StringBuilder result = new StringBuilder("not equal");
435 if (!onlyOnLeft.isEmpty()) {
436 result.append(": only on left=").append(onlyOnLeft);
437 }
438 if (!onlyOnRight.isEmpty()) {
439 result.append(": only on right=").append(onlyOnRight);
440 }
441 if (!differences.isEmpty()) {
442 result.append(": value differences=").append(differences);
443 }
444 return result.toString();
445 }
446 }
447
448 static class ValueDifferenceImpl<V>
449 implements MapDifference.ValueDifference<V> {
450 private final V left;
451 private final V right;
452
453 static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) {
454 return new ValueDifferenceImpl<V>(left, right);
455 }
456
457 private ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
458 this.left = left;
459 this.right = right;
460 }
461
462 @Override
463 public V leftValue() {
464 return left;
465 }
466
467 @Override
468 public V rightValue() {
469 return right;
470 }
471
472 @Override public boolean equals(@Nullable Object object) {
473 if (object instanceof MapDifference.ValueDifference) {
474 MapDifference.ValueDifference<?> that =
475 (MapDifference.ValueDifference<?>) object;
476 return Objects.equal(this.left, that.leftValue())
477 && Objects.equal(this.right, that.rightValue());
478 }
479 return false;
480 }
481
482 @Override public int hashCode() {
483 return Objects.hashCode(left, right);
484 }
485
486 @Override public String toString() {
487 return "(" + left + ", " + right + ")";
488 }
489 }
490
491 /**
492 * Computes the difference between two sorted maps, using the comparator of
493 * the left map, or {@code Ordering.natural()} if the left map uses the
494 * natural ordering of its elements. This difference is an immutable snapshot
495 * of the state of the maps at the time this method is called. It will never
496 * change, even if the maps change at a later time.
497 *
498 * <p>Since this method uses {@code TreeMap} instances internally, the keys of
499 * the right map must all compare as distinct according to the comparator
500 * of the left map.
501 *
502 * <p><b>Note:</b>If you only need to know whether two sorted maps have the
503 * same mappings, call {@code left.equals(right)} instead of this method.
504 *
505 * @param left the map to treat as the "left" map for purposes of comparison
506 * @param right the map to treat as the "right" map for purposes of comparison
507 * @return the difference between the two maps
508 * @since 11.0
509 */
510 public static <K, V> SortedMapDifference<K, V> difference(
511 SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
512 checkNotNull(left);
513 checkNotNull(right);
514 Comparator<? super K> comparator = orNaturalOrder(left.comparator());
515 SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator);
516 SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator);
517 onlyOnRight.putAll(right); // will whittle it down
518 SortedMap<K, V> onBoth = Maps.newTreeMap(comparator);
519 SortedMap<K, MapDifference.ValueDifference<V>> differences =
520 Maps.newTreeMap(comparator);
521 boolean eq = true;
522
523 for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
524 K leftKey = entry.getKey();
525 V leftValue = entry.getValue();
526 if (right.containsKey(leftKey)) {
527 V rightValue = onlyOnRight.remove(leftKey);
528 if (Objects.equal(leftValue, rightValue)) {
529 onBoth.put(leftKey, leftValue);
530 } else {
531 eq = false;
532 differences.put(
533 leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
534 }
535 } else {
536 eq = false;
537 onlyOnLeft.put(leftKey, leftValue);
538 }
539 }
540
541 boolean areEqual = eq && onlyOnRight.isEmpty();
542 return sortedMapDifference(
543 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
544 }
545
546 private static <K, V> SortedMapDifference<K, V> sortedMapDifference(
547 boolean areEqual, SortedMap<K, V> onlyOnLeft, SortedMap<K, V> onlyOnRight,
548 SortedMap<K, V> onBoth, SortedMap<K, ValueDifference<V>> differences) {
549 return new SortedMapDifferenceImpl<K, V>(areEqual,
550 Collections.unmodifiableSortedMap(onlyOnLeft),
551 Collections.unmodifiableSortedMap(onlyOnRight),
552 Collections.unmodifiableSortedMap(onBoth),
553 Collections.unmodifiableSortedMap(differences));
554 }
555
556 static class SortedMapDifferenceImpl<K, V> extends MapDifferenceImpl<K, V>
557 implements SortedMapDifference<K, V> {
558 SortedMapDifferenceImpl(boolean areEqual, SortedMap<K, V> onlyOnLeft,
559 SortedMap<K, V> onlyOnRight, SortedMap<K, V> onBoth,
560 SortedMap<K, ValueDifference<V>> differences) {
561 super(areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
562 }
563
564 @Override public SortedMap<K, ValueDifference<V>> entriesDiffering() {
565 return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering();
566 }
567
568 @Override public SortedMap<K, V> entriesInCommon() {
569 return (SortedMap<K, V>) super.entriesInCommon();
570 }
571
572 @Override public SortedMap<K, V> entriesOnlyOnLeft() {
573 return (SortedMap<K, V>) super.entriesOnlyOnLeft();
574 }
575
576 @Override public SortedMap<K, V> entriesOnlyOnRight() {
577 return (SortedMap<K, V>) super.entriesOnlyOnRight();
578 }
579 }
580
581 /**
582 * Returns the specified comparator if not null; otherwise returns {@code
583 * Ordering.natural()}. This method is an abomination of generics; the only
584 * purpose of this method is to contain the ugly type-casting in one place.
585 */
586 @SuppressWarnings("unchecked")
587 static <E> Comparator<? super E> orNaturalOrder(
588 @Nullable Comparator<? super E> comparator) {
589 if (comparator != null) { // can't use ? : because of javac bug 5080917
590 return comparator;
591 }
592 return (Comparator<E>) Ordering.natural();
593 }
594
595 /**
596 * Returns a view of the set as a map, mapping keys from the set according to
597 * the specified function.
598 *
599 * <p>Specifically, for each {@code k} in the backing set, the returned map
600 * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code
601 * keySet}, {@code values}, and {@code entrySet} views of the returned map
602 * iterate in the same order as the backing set.
603 *
604 * <p>Modifications to the backing set are read through to the returned map.
605 * The returned map supports removal operations if the backing set does.
606 * Removal operations write through to the backing set. The returned map
607 * does not support put operations.
608 *
609 * <p><b>Warning</b>: If the function rejects {@code null}, caution is
610 * required to make sure the set does not contain {@code null}, because the
611 * view cannot stop {@code null} from being added to the set.
612 *
613 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
614 * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also
615 * of type {@code K}. Using a key type for which this may not hold, such as
616 * {@code ArrayList}, may risk a {@code ClassCastException} when calling
617 * methods on the resulting map view.
618 */
619 @Beta
620 static <K, V> Map<K, V> asMap(
621 Set<K> set, Function<? super K, V> function) {
622 if (set instanceof SortedSet) {
623 return asMap((SortedSet<K>) set, function);
624 } else {
625 return new AsMapView<K, V>(set, function);
626 }
627 }
628
629 /**
630 * Returns a view of the sorted set as a map, mapping keys from the set
631 * according to the specified function.
632 *
633 * <p>Specifically, for each {@code k} in the backing set, the returned map
634 * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code
635 * keySet}, {@code values}, and {@code entrySet} views of the returned map
636 * iterate in the same order as the backing set.
637 *
638 * <p>Modifications to the backing set are read through to the returned map.
639 * The returned map supports removal operations if the backing set does.
640 * Removal operations write through to the backing set. The returned map does
641 * not support put operations.
642 *
643 * <p><b>Warning</b>: If the function rejects {@code null}, caution is
644 * required to make sure the set does not contain {@code null}, because the
645 * view cannot stop {@code null} from being added to the set.
646 *
647 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
648 * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
649 * type {@code K}. Using a key type for which this may not hold, such as
650 * {@code ArrayList}, may risk a {@code ClassCastException} when calling
651 * methods on the resulting map view.
652 */
653 @Beta
654 static <K, V> SortedMap<K, V> asMap(
655 SortedSet<K> set, Function<? super K, V> function) {
656 // TODO: NavigableSet overloads
657 return new SortedAsMapView<K, V>(set, function);
658 }
659
660 private static class AsMapView<K, V> extends ImprovedAbstractMap<K, V> {
661
662 private final Set<K> set;
663 final Function<? super K, V> function;
664
665 Set<K> backingSet() {
666 return set;
667 }
668
669 AsMapView(Set<K> set, Function<? super K, V> function) {
670 this.set = checkNotNull(set);
671 this.function = checkNotNull(function);
672 }
673
674 @Override
675 public Set<K> keySet() {
676 // probably not worth caching
677 return new ForwardingSet<K>() {
678 @Override
679 protected Set<K> delegate() {
680 return set;
681 }
682
683 @Override
684 public boolean add(K element) {
685 throw new UnsupportedOperationException();
686 }
687
688 @Override
689 public boolean addAll(Collection<? extends K> collection) {
690 throw new UnsupportedOperationException();
691 }
692 };
693 }
694
695 @Override
696 public Collection<V> values() {
697 // probably not worth caching
698 return Collections2.transform(set, function);
699 }
700
701 @Override
702 public int size() {
703 return set.size();
704 }
705
706 @Override
707 public boolean containsKey(@Nullable Object key) {
708 return set.contains(key);
709 }
710
711 @Override
712 public V get(@Nullable Object key) {
713 if (set.contains(key)) {
714 @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
715 K k = (K) key;
716 return function.apply(k);
717 } else {
718 return null;
719 }
720 }
721
722 @Override
723 public V remove(@Nullable Object key) {
724 if (set.remove(key)) {
725 @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
726 K k = (K) key;
727 return function.apply(k);
728 } else {
729 return null;
730 }
731 }
732
733 @Override
734 public void clear() {
735 set.clear();
736 }
737
738 @Override
739 protected Set<Entry<K, V>> createEntrySet() {
740 return new EntrySet<K, V>() {
741 @Override
742 Map<K, V> map() {
743 return AsMapView.this;
744 }
745
746 @Override
747 public Iterator<Entry<K, V>> iterator() {
748 final Iterator<K> backingIterator = set.iterator();
749 return new Iterator<Entry<K, V>>() {
750 @Override
751 public boolean hasNext() {
752 return backingIterator.hasNext();
753 }
754
755 @Override
756 public Entry<K, V> next() {
757 K k = backingIterator.next();
758 return Maps.immutableEntry(k, function.apply(k));
759 }
760
761 @Override
762 public void remove() {
763 backingIterator.remove();
764 }
765 };
766 }
767 };
768 }
769 }
770
771 private static final class SortedAsMapView<K, V> extends AsMapView<K, V>
772 implements SortedMap<K, V> {
773
774 SortedAsMapView(SortedSet<K> set, Function<? super K, V> function) {
775 super(set, function);
776 }
777
778 @Override
779 public Comparator<? super K> comparator() {
780 return backingSet().comparator();
781 }
782
783 @Override
784 public SortedMap<K, V> subMap(K fromKey, K toKey) {
785 return asMap(backingSet().subSet(fromKey, toKey), function);
786 }
787
788 @Override
789 public SortedMap<K, V> headMap(K toKey) {
790 return asMap(backingSet().headSet(toKey), function);
791 }
792
793 @Override
794 public SortedMap<K, V> tailMap(K fromKey) {
795 return asMap(backingSet().tailSet(fromKey), function);
796 }
797
798 @Override
799 public K firstKey() {
800 return backingSet().first();
801 }
802
803 @Override
804 public K lastKey() {
805 return backingSet().last();
806 }
807
808 @Override
809 SortedSet<K> backingSet() {
810 return (SortedSet<K>) super.backingSet();
811 }
812 }
813
814 /**
815 * Returns an immutable map for which the {@link Map#values} are the given
816 * elements in the given order, and each key is the product of invoking a
817 * supplied function on its corresponding value.
818 *
819 * @param values the values to use when constructing the {@code Map}
820 * @param keyFunction the function used to produce the key for each value
821 * @return a map mapping the result of evaluating the function {@code
822 * keyFunction} on each value in the input collection to that value
823 * @throws IllegalArgumentException if {@code keyFunction} produces the same
824 * key for more than one value in the input collection
825 * @throws NullPointerException if any elements of {@code values} is null, or
826 * if {@code keyFunction} produces {@code null} for any value
827 */
828 public static <K, V> ImmutableMap<K, V> uniqueIndex(
829 Iterable<V> values, Function<? super V, K> keyFunction) {
830 return uniqueIndex(values.iterator(), keyFunction);
831 }
832
833 /**
834 * Returns an immutable map for which the {@link Map#values} are the given
835 * elements in the given order, and each key is the product of invoking a
836 * supplied function on its corresponding value.
837 *
838 * @param values the values to use when constructing the {@code Map}
839 * @param keyFunction the function used to produce the key for each value
840 * @return a map mapping the result of evaluating the function {@code
841 * keyFunction} on each value in the input collection to that value
842 * @throws IllegalArgumentException if {@code keyFunction} produces the same
843 * key for more than one value in the input collection
844 * @throws NullPointerException if any elements of {@code values} is null, or
845 * if {@code keyFunction} produces {@code null} for any value
846 * @since 10.0
847 */
848 public static <K, V> ImmutableMap<K, V> uniqueIndex(
849 Iterator<V> values, Function<? super V, K> keyFunction) {
850 checkNotNull(keyFunction);
851 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
852 while (values.hasNext()) {
853 V value = values.next();
854 builder.put(keyFunction.apply(value), value);
855 }
856 return builder.build();
857 }
858
859 /**
860 * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
861 * instance. Properties normally derive from {@code Map<Object, Object>}, but
862 * they typically contain strings, which is awkward. This method lets you get
863 * a plain-old-{@code Map} out of a {@code Properties}.
864 *
865 * @param properties a {@code Properties} object to be converted
866 * @return an immutable map containing all the entries in {@code properties}
867 * @throws ClassCastException if any key in {@code Properties} is not a {@code
868 * String}
869 * @throws NullPointerException if any key or value in {@code Properties} is
870 * null
871 */
872 @GwtIncompatible("java.util.Properties")
873 public static ImmutableMap<String, String> fromProperties(
874 Properties properties) {
875 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
876
877 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
878 String key = (String) e.nextElement();
879 builder.put(key, properties.getProperty(key));
880 }
881
882 return builder.build();
883 }
884
885 /**
886 * Returns an immutable map entry with the specified key and value. The {@link
887 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
888 *
889 * <p>The returned entry is serializable.
890 *
891 * @param key the key to be associated with the returned entry
892 * @param value the value to be associated with the returned entry
893 */
894 @GwtCompatible(serializable = true)
895 public static <K, V> Entry<K, V> immutableEntry(
896 @Nullable K key, @Nullable V value) {
897 return new ImmutableEntry<K, V>(key, value);
898 }
899
900 /**
901 * Returns an unmodifiable view of the specified set of entries. The {@link
902 * Entry#setValue} operation throws an {@link UnsupportedOperationException},
903 * as do any operations that would modify the returned set.
904 *
905 * @param entrySet the entries for which to return an unmodifiable view
906 * @return an unmodifiable view of the entries
907 */
908 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
909 Set<Entry<K, V>> entrySet) {
910 return new UnmodifiableEntrySet<K, V>(
911 Collections.unmodifiableSet(entrySet));
912 }
913
914 /**
915 * Returns an unmodifiable view of the specified map entry. The {@link
916 * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
917 * This also has the side-effect of redefining {@code equals} to comply with
918 * the Entry contract, to avoid a possible nefarious implementation of equals.
919 *
920 * @param entry the entry for which to return an unmodifiable view
921 * @return an unmodifiable view of the entry
922 */
923 static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
924 checkNotNull(entry);
925 return new AbstractMapEntry<K, V>() {
926 @Override public K getKey() {
927 return entry.getKey();
928 }
929
930 @Override public V getValue() {
931 return entry.getValue();
932 }
933 };
934 }
935
936 /** @see Multimaps#unmodifiableEntries */
937 static class UnmodifiableEntries<K, V>
938 extends ForwardingCollection<Entry<K, V>> {
939 private final Collection<Entry<K, V>> entries;
940
941 UnmodifiableEntries(Collection<Entry<K, V>> entries) {
942 this.entries = entries;
943 }
944
945 @Override protected Collection<Entry<K, V>> delegate() {
946 return entries;
947 }
948
949 @Override public Iterator<Entry<K, V>> iterator() {
950 final Iterator<Entry<K, V>> delegate = super.iterator();
951 return new ForwardingIterator<Entry<K, V>>() {
952 @Override public Entry<K, V> next() {
953 return unmodifiableEntry(super.next());
954 }
955
956 @Override public void remove() {
957 throw new UnsupportedOperationException();
958 }
959
960 @Override protected Iterator<Entry<K, V>> delegate() {
961 return delegate;
962 }
963 };
964 }
965
966 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
967
968 @Override public boolean add(Entry<K, V> element) {
969 throw new UnsupportedOperationException();
970 }
971
972 @Override public boolean addAll(
973 Collection<? extends Entry<K, V>> collection) {
974 throw new UnsupportedOperationException();
975 }
976
977 @Override public void clear() {
978 throw new UnsupportedOperationException();
979 }
980
981 @Override public boolean remove(Object object) {
982 throw new UnsupportedOperationException();
983 }
984
985 @Override public boolean removeAll(Collection<?> collection) {
986 throw new UnsupportedOperationException();
987 }
988
989 @Override public boolean retainAll(Collection<?> collection) {
990 throw new UnsupportedOperationException();
991 }
992
993 @Override public Object[] toArray() {
994 return standardToArray();
995 }
996
997 @Override public <T> T[] toArray(T[] array) {
998 return standardToArray(array);
999 }
1000 }
1001
1002 /** @see Maps#unmodifiableEntrySet(Set) */
1003 static class UnmodifiableEntrySet<K, V>
1004 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
1005 UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
1006 super(entries);
1007 }
1008
1009 // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
1010
1011 @Override public boolean equals(@Nullable Object object) {
1012 return Sets.equalsImpl(this, object);
1013 }
1014
1015 @Override public int hashCode() {
1016 return Sets.hashCodeImpl(this);
1017 }
1018 }
1019
1020 /**
1021 * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
1022 * In order to guarantee serial access, it is critical that <b>all</b> access
1023 * to the backing bimap is accomplished through the returned bimap.
1024 *
1025 * <p>It is imperative that the user manually synchronize on the returned map
1026 * when accessing any of its collection views: <pre> {@code
1027 *
1028 * BiMap<Long, String> map = Maps.synchronizedBiMap(
1029 * HashBiMap.<Long, String>create());
1030 * ...
1031 * Set<Long> set = map.keySet(); // Needn't be in synchronized block
1032 * ...
1033 * synchronized (map) { // Synchronizing on map, not set!
1034 * Iterator<Long> it = set.iterator(); // Must be in synchronized block
1035 * while (it.hasNext()) {
1036 * foo(it.next());
1037 * }
1038 * }}</pre>
1039 *
1040 * Failure to follow this advice may result in non-deterministic behavior.
1041 *
1042 * <p>The returned bimap will be serializable if the specified bimap is
1043 * serializable.
1044 *
1045 * @param bimap the bimap to be wrapped in a synchronized view
1046 * @return a sychronized view of the specified bimap
1047 */
1048 public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
1049 return Synchronized.biMap(bimap, null);
1050 }
1051
1052 /**
1053 * Returns an unmodifiable view of the specified bimap. This method allows
1054 * modules to provide users with "read-only" access to internal bimaps. Query
1055 * operations on the returned bimap "read through" to the specified bimap, and
1056 * attempts to modify the returned map, whether direct or via its collection
1057 * views, result in an {@code UnsupportedOperationException}.
1058 *
1059 * <p>The returned bimap will be serializable if the specified bimap is
1060 * serializable.
1061 *
1062 * @param bimap the bimap for which an unmodifiable view is to be returned
1063 * @return an unmodifiable view of the specified bimap
1064 */
1065 public static <K, V> BiMap<K, V> unmodifiableBiMap(
1066 BiMap<? extends K, ? extends V> bimap) {
1067 return new UnmodifiableBiMap<K, V>(bimap, null);
1068 }
1069
1070 /** @see Maps#unmodifiableBiMap(BiMap) */
1071 private static class UnmodifiableBiMap<K, V>
1072 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
1073 final Map<K, V> unmodifiableMap;
1074 final BiMap<? extends K, ? extends V> delegate;
1075 BiMap<V, K> inverse;
1076 transient Set<V> values;
1077
1078 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
1079 @Nullable BiMap<V, K> inverse) {
1080 unmodifiableMap = Collections.unmodifiableMap(delegate);
1081 this.delegate = delegate;
1082 this.inverse = inverse;
1083 }
1084
1085 @Override protected Map<K, V> delegate() {
1086 return unmodifiableMap;
1087 }
1088
1089 @Override
1090 public V forcePut(K key, V value) {
1091 throw new UnsupportedOperationException();
1092 }
1093
1094 @Override
1095 public BiMap<V, K> inverse() {
1096 BiMap<V, K> result = inverse;
1097 return (result == null)
1098 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
1099 : result;
1100 }
1101
1102 @Override public Set<V> values() {
1103 Set<V> result = values;
1104 return (result == null)
1105 ? values = Collections.unmodifiableSet(delegate.values())
1106 : result;
1107 }
1108
1109 private static final long serialVersionUID = 0;
1110 }
1111
1112 /**
1113 * Returns a view of a map where each value is transformed by a function. All
1114 * other properties of the map, such as iteration order, are left intact. For
1115 * example, the code: <pre> {@code
1116 *
1117 * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
1118 * Function<Integer, Double> sqrt =
1119 * new Function<Integer, Double>() {
1120 * public Double apply(Integer in) {
1121 * return Math.sqrt((int) in);
1122 * }
1123 * };
1124 * Map<String, Double> transformed = Maps.transformValues(map, sqrt);
1125 * System.out.println(transformed);}</pre>
1126 *
1127 * ... prints {@code {a=2.0, b=3.0}}.
1128 *
1129 * <p>Changes in the underlying map are reflected in this view. Conversely,
1130 * this view supports removal operations, and these are reflected in the
1131 * underlying map.
1132 *
1133 * <p>It's acceptable for the underlying map to contain null keys, and even
1134 * null values provided that the function is capable of accepting null input.
1135 * The transformed map might contain null values, if the function sometimes
1136 * gives a null result.
1137 *
1138 * <p>The returned map is not thread-safe or serializable, even if the
1139 * underlying map is.
1140 *
1141 * <p>The function is applied lazily, invoked when needed. This is necessary
1142 * for the returned map to be a view, but it means that the function will be
1143 * applied many times for bulk operations like {@link Map#containsValue} and
1144 * {@code Map.toString()}. For this to perform well, {@code function} should
1145 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
1146 * a view, copy the returned map into a new map of your choosing.
1147 */
1148 public static <K, V1, V2> Map<K, V2> transformValues(
1149 Map<K, V1> fromMap, Function<? super V1, V2> function) {
1150 return transformEntries(fromMap, asEntryTransformer(function));
1151 }
1152
1153 /**
1154 * Returns a view of a sorted map where each value is transformed by a
1155 * function. All other properties of the map, such as iteration order, are
1156 * left intact. For example, the code: <pre> {@code
1157 *
1158 * SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
1159 * Function<Integer, Double> sqrt =
1160 * new Function<Integer, Double>() {
1161 * public Double apply(Integer in) {
1162 * return Math.sqrt((int) in);
1163 * }
1164 * };
1165 * SortedMap<String, Double> transformed =
1166 * Maps.transformSortedValues(map, sqrt);
1167 * System.out.println(transformed);}</pre>
1168 *
1169 * ... prints {@code {a=2.0, b=3.0}}.
1170 *
1171 * <p>Changes in the underlying map are reflected in this view. Conversely,
1172 * this view supports removal operations, and these are reflected in the
1173 * underlying map.
1174 *
1175 * <p>It's acceptable for the underlying map to contain null keys, and even
1176 * null values provided that the function is capable of accepting null input.
1177 * The transformed map might contain null values, if the function sometimes
1178 * gives a null result.
1179 *
1180 * <p>The returned map is not thread-safe or serializable, even if the
1181 * underlying map is.
1182 *
1183 * <p>The function is applied lazily, invoked when needed. This is necessary
1184 * for the returned map to be a view, but it means that the function will be
1185 * applied many times for bulk operations like {@link Map#containsValue} and
1186 * {@code Map.toString()}. For this to perform well, {@code function} should
1187 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
1188 * a view, copy the returned map into a new map of your choosing.
1189 *
1190 * @since 11.0
1191 */
1192 @Beta
1193 public static <K, V1, V2> SortedMap<K, V2> transformValues(
1194 SortedMap<K, V1> fromMap, Function<? super V1, V2> function) {
1195 return transformEntries(fromMap, asEntryTransformer(function));
1196 }
1197
1198 /**
1199 * Returns a view of a navigable map where each value is transformed by a
1200 * function. All other properties of the map, such as iteration order, are
1201 * left intact. For example, the code: <pre> {@code
1202 *
1203 * NavigableMap<String, Integer> map = Maps.newTreeMap();
1204 * map.put("a", 4);
1205 * map.put("b", 9);
1206 * Function<Integer, Double> sqrt =
1207 * new Function<Integer, Double>() {
1208 * public Double apply(Integer in) {
1209 * return Math.sqrt((int) in);
1210 * }
1211 * };
1212 * NavigableMap<String, Double> transformed =
1213 * Maps.transformNavigableValues(map, sqrt);
1214 * System.out.println(transformed);}</pre>
1215 *
1216 * ... prints {@code {a=2.0, b=3.0}}.
1217 *
1218 * Changes in the underlying map are reflected in this view.
1219 * Conversely, this view supports removal operations, and these are reflected
1220 * in the underlying map.
1221 *
1222 * <p>It's acceptable for the underlying map to contain null keys, and even
1223 * null values provided that the function is capable of accepting null input.
1224 * The transformed map might contain null values, if the function sometimes
1225 * gives a null result.
1226 *
1227 * <p>The returned map is not thread-safe or serializable, even if the
1228 * underlying map is.
1229 *
1230 * <p>The function is applied lazily, invoked when needed. This is necessary
1231 * for the returned map to be a view, but it means that the function will be
1232 * applied many times for bulk operations like {@link Map#containsValue} and
1233 * {@code Map.toString()}. For this to perform well, {@code function} should
1234 * be fast. To avoid lazy evaluation when the returned map doesn't need to be
1235 * a view, copy the returned map into a new map of your choosing.
1236 *
1237 * @since 13.0
1238 */
1239 @Beta
1240 @GwtIncompatible("NavigableMap")
1241 public static <K, V1, V2> NavigableMap<K, V2> transformValues(
1242 NavigableMap<K, V1> fromMap, Function<? super V1, V2> function) {
1243 return transformEntries(fromMap, asEntryTransformer(function));
1244 }
1245
1246 private static <K, V1, V2> EntryTransformer<K, V1, V2>
1247 asEntryTransformer(final Function<? super V1, V2> function) {
1248 checkNotNull(function);
1249 return new EntryTransformer<K, V1, V2>() {
1250 @Override
1251 public V2 transformEntry(K key, V1 value) {
1252 return function.apply(value);
1253 }
1254 };
1255 }
1256
1257 /**
1258 * Returns a view of a map whose values are derived from the original map's
1259 * entries. In contrast to {@link #transformValues}, this method's
1260 * entry-transformation logic may depend on the key as well as the value.
1261 *
1262 * <p>All other properties of the transformed map, such as iteration order,
1263 * are left intact. For example, the code: <pre> {@code
1264 *
1265 * Map<String, Boolean> options =
1266 * ImmutableMap.of("verbose", true, "sort", false);
1267 * EntryTransformer<String, Boolean, String> flagPrefixer =
1268 * new EntryTransformer<String, Boolean, String>() {
1269 * public String transformEntry(String key, Boolean value) {
1270 * return value ? key : "no" + key;
1271 * }
1272 * };
1273 * Map<String, String> transformed =
1274 * Maps.transformEntries(options, flagPrefixer);
1275 * System.out.println(transformed);}</pre>
1276 *
1277 * ... prints {@code {verbose=verbose, sort=nosort}}.
1278 *
1279 * <p>Changes in the underlying map are reflected in this view. Conversely,
1280 * this view supports removal operations, and these are reflected in the
1281 * underlying map.
1282 *
1283 * <p>It's acceptable for the underlying map to contain null keys and null
1284 * values provided that the transformer is capable of accepting null inputs.
1285 * The transformed map might contain null values if the transformer sometimes
1286 * gives a null result.
1287 *
1288 * <p>The returned map is not thread-safe or serializable, even if the
1289 * underlying map is.
1290 *
1291 * <p>The transformer is applied lazily, invoked when needed. This is
1292 * necessary for the returned map to be a view, but it means that the
1293 * transformer will be applied many times for bulk operations like {@link
1294 * Map#containsValue} and {@link Object#toString}. For this to perform well,
1295 * {@code transformer} should be fast. To avoid lazy evaluation when the
1296 * returned map doesn't need to be a view, copy the returned map into a new
1297 * map of your choosing.
1298 *
1299 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1300 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1301 * that {@code k2} is also of type {@code K}. Using an {@code
1302 * EntryTransformer} key type for which this may not hold, such as {@code
1303 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1304 * the transformed map.
1305 *
1306 * @since 7.0
1307 */
1308 public static <K, V1, V2> Map<K, V2> transformEntries(
1309 Map<K, V1> fromMap,
1310 EntryTransformer<? super K, ? super V1, V2> transformer) {
1311 if (fromMap instanceof SortedMap) {
1312 return transformEntries((SortedMap<K, V1>) fromMap, transformer);
1313 }
1314 return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
1315 }
1316
1317 /**
1318 * Returns a view of a sorted map whose values are derived from the original
1319 * sorted map's entries. In contrast to {@link #transformValues}, this
1320 * method's entry-transformation logic may depend on the key as well as the
1321 * value.
1322 *
1323 * <p>All other properties of the transformed map, such as iteration order,
1324 * are left intact. For example, the code: <pre> {@code
1325 *
1326 * Map<String, Boolean> options =
1327 * ImmutableSortedMap.of("verbose", true, "sort", false);
1328 * EntryTransformer<String, Boolean, String> flagPrefixer =
1329 * new EntryTransformer<String, Boolean, String>() {
1330 * public String transformEntry(String key, Boolean value) {
1331 * return value ? key : "yes" + key;
1332 * }
1333 * };
1334 * SortedMap<String, String> transformed =
1335 * LabsMaps.transformSortedEntries(options, flagPrefixer);
1336 * System.out.println(transformed);}</pre>
1337 *
1338 * ... prints {@code {sort=yessort, verbose=verbose}}.
1339 *
1340 * <p>Changes in the underlying map are reflected in this view. Conversely,
1341 * this view supports removal operations, and these are reflected in the
1342 * underlying map.
1343 *
1344 * <p>It's acceptable for the underlying map to contain null keys and null
1345 * values provided that the transformer is capable of accepting null inputs.
1346 * The transformed map might contain null values if the transformer sometimes
1347 * gives a null result.
1348 *
1349 * <p>The returned map is not thread-safe or serializable, even if the
1350 * underlying map is.
1351 *
1352 * <p>The transformer is applied lazily, invoked when needed. This is
1353 * necessary for the returned map to be a view, but it means that the
1354 * transformer will be applied many times for bulk operations like {@link
1355 * Map#containsValue} and {@link Object#toString}. For this to perform well,
1356 * {@code transformer} should be fast. To avoid lazy evaluation when the
1357 * returned map doesn't need to be a view, copy the returned map into a new
1358 * map of your choosing.
1359 *
1360 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1361 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1362 * that {@code k2} is also of type {@code K}. Using an {@code
1363 * EntryTransformer} key type for which this may not hold, such as {@code
1364 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1365 * the transformed map.
1366 *
1367 * @since 11.0
1368 */
1369 @Beta
1370 public static <K, V1, V2> SortedMap<K, V2> transformEntries(
1371 SortedMap<K, V1> fromMap,
1372 EntryTransformer<? super K, ? super V1, V2> transformer) {
1373 return Platform.mapsTransformEntriesSortedMap(fromMap, transformer);
1374 }
1375
1376 /**
1377 * Returns a view of a navigable map whose values are derived from the
1378 * original navigable map's entries. In contrast to {@link
1379 * #transformValues}, this method's entry-transformation logic may
1380 * depend on the key as well as the value.
1381 *
1382 * <p>All other properties of the transformed map, such as iteration order,
1383 * are left intact. For example, the code: <pre> {@code
1384 *
1385 * NavigableMap<String, Boolean> options = Maps.newTreeMap();
1386 * options.put("verbose", false);
1387 * options.put("sort", true);
1388 * EntryTransformer<String, Boolean, String> flagPrefixer =
1389 * new EntryTransformer<String, Boolean, String>() {
1390 * public String transformEntry(String key, Boolean value) {
1391 * return value ? key : ("yes" + key);
1392 * }
1393 * };
1394 * NavigableMap<String, String> transformed =
1395 * LabsMaps.transformNavigableEntries(options, flagPrefixer);
1396 * System.out.println(transformed);}</pre>
1397 *
1398 * ... prints {@code {sort=yessort, verbose=verbose}}.
1399 *
1400 * <p>Changes in the underlying map are reflected in this view.
1401 * Conversely, this view supports removal operations, and these are reflected
1402 * in the underlying map.
1403 *
1404 * <p>It's acceptable for the underlying map to contain null keys and null
1405 * values provided that the transformer is capable of accepting null inputs.
1406 * The transformed map might contain null values if the transformer sometimes
1407 * gives a null result.
1408 *
1409 * <p>The returned map is not thread-safe or serializable, even if the
1410 * underlying map is.
1411 *
1412 * <p>The transformer is applied lazily, invoked when needed. This is
1413 * necessary for the returned map to be a view, but it means that the
1414 * transformer will be applied many times for bulk operations like {@link
1415 * Map#containsValue} and {@link Object#toString}. For this to perform well,
1416 * {@code transformer} should be fast. To avoid lazy evaluation when the
1417 * returned map doesn't need to be a view, copy the returned map into a new
1418 * map of your choosing.
1419 *
1420 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1421 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1422 * that {@code k2} is also of type {@code K}. Using an {@code
1423 * EntryTransformer} key type for which this may not hold, such as {@code
1424 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1425 * the transformed map.
1426 *
1427 * @since 13.0
1428 */
1429 @Beta
1430 @GwtIncompatible("NavigableMap")
1431 public static <K, V1, V2> NavigableMap<K, V2> transformEntries(
1432 final NavigableMap<K, V1> fromMap,
1433 EntryTransformer<? super K, ? super V1, V2> transformer) {
1434 return new TransformedEntriesNavigableMap<K, V1, V2>(fromMap, transformer);
1435 }
1436
1437 static <K, V1, V2> SortedMap<K, V2> transformEntriesIgnoreNavigable(
1438 SortedMap<K, V1> fromMap,
1439 EntryTransformer<? super K, ? super V1, V2> transformer) {
1440 return new TransformedEntriesSortedMap<K, V1, V2>(fromMap, transformer);
1441 }
1442
1443 /**
1444 * A transformation of the value of a key-value pair, using both key and value
1445 * as inputs. To apply the transformation to a map, use
1446 * {@link Maps#transformEntries(Map, EntryTransformer)}.
1447 *
1448 * @param <K> the key type of the input and output entries
1449 * @param <V1> the value type of the input entry
1450 * @param <V2> the value type of the output entry
1451 * @since 7.0
1452 */
1453 public interface EntryTransformer<K, V1, V2> {
1454 /**
1455 * Determines an output value based on a key-value pair. This method is
1456 * <i>generally expected</i>, but not absolutely required, to have the
1457 * following properties:
1458 *
1459 * <ul>
1460 * <li>Its execution does not cause any observable side effects.
1461 * <li>The computation is <i>consistent with equals</i>; that is,
1462 * {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
1463 * {@link Objects#equal}{@code (v1, v2)} implies that {@code
1464 * Objects.equal(transformer.transform(k1, v1),
1465 * transformer.transform(k2, v2))}.
1466 * </ul>
1467 *
1468 * @throws NullPointerException if the key or value is null and this
1469 * transformer does not accept null arguments
1470 */
1471 V2 transformEntry(@Nullable K key, @Nullable V1 value);
1472 }
1473
1474 static class TransformedEntriesMap<K, V1, V2>
1475 extends AbstractMap<K, V2> {
1476 final Map<K, V1> fromMap;
1477 final EntryTransformer<? super K, ? super V1, V2> transformer;
1478
1479 TransformedEntriesMap(
1480 Map<K, V1> fromMap,
1481 EntryTransformer<? super K, ? super V1, V2> transformer) {
1482 this.fromMap = checkNotNull(fromMap);
1483 this.transformer = checkNotNull(transformer);
1484 }
1485
1486 @Override public int size() {
1487 return fromMap.size();
1488 }
1489
1490 @Override public boolean containsKey(Object key) {
1491 return fromMap.containsKey(key);
1492 }
1493
1494 // safe as long as the user followed the <b>Warning</b> in the javadoc
1495 @SuppressWarnings("unchecked")
1496 @Override public V2 get(Object key) {
1497 V1 value = fromMap.get(key);
1498 return (value != null || fromMap.containsKey(key))
1499 ? transformer.transformEntry((K) key, value)
1500 : null;
1501 }
1502
1503 // safe as long as the user followed the <b>Warning</b> in the javadoc
1504 @SuppressWarnings("unchecked")
1505 @Override public V2 remove(Object key) {
1506 return fromMap.containsKey(key)
1507 ? transformer.transformEntry((K) key, fromMap.remove(key))
1508 : null;
1509 }
1510
1511 @Override public void clear() {
1512 fromMap.clear();
1513 }
1514
1515 @Override public Set<K> keySet() {
1516 return fromMap.keySet();
1517 }
1518
1519 Set<Entry<K, V2>> entrySet;
1520
1521 @Override public Set<Entry<K, V2>> entrySet() {
1522 Set<Entry<K, V2>> result = entrySet;
1523 if (result == null) {
1524 entrySet = result = new EntrySet<K, V2>() {
1525 @Override Map<K, V2> map() {
1526 return TransformedEntriesMap.this;
1527 }
1528
1529 @Override public Iterator<Entry<K, V2>> iterator() {
1530 return new TransformedIterator<Entry<K, V1>, Entry<K, V2>>(
1531 fromMap.entrySet().iterator()) {
1532 @Override
1533 Entry<K, V2> transform(final Entry<K, V1> entry) {
1534 return new AbstractMapEntry<K, V2>() {
1535 @Override
1536 public K getKey() {
1537 return entry.getKey();
1538 }
1539
1540 @Override
1541 public V2 getValue() {
1542 return transformer.transformEntry(entry.getKey(), entry.getValue());
1543 }
1544 };
1545 }
1546 };
1547 }
1548 };
1549 }
1550 return result;
1551 }
1552
1553 Collection<V2> values;
1554
1555 @Override public Collection<V2> values() {
1556 Collection<V2> result = values;
1557 if (result == null) {
1558 return values = new Values<K, V2>() {
1559 @Override Map<K, V2> map() {
1560 return TransformedEntriesMap.this;
1561 }
1562 };
1563 }
1564 return result;
1565 }
1566 }
1567
1568 static class TransformedEntriesSortedMap<K, V1, V2>
1569 extends TransformedEntriesMap<K, V1, V2> implements SortedMap<K, V2> {
1570
1571 protected SortedMap<K, V1> fromMap() {
1572 return (SortedMap<K, V1>) fromMap;
1573 }
1574
1575 TransformedEntriesSortedMap(SortedMap<K, V1> fromMap,
1576 EntryTransformer<? super K, ? super V1, V2> transformer) {
1577 super(fromMap, transformer);
1578 }
1579
1580 @Override public Comparator<? super K> comparator() {
1581 return fromMap().comparator();
1582 }
1583
1584 @Override public K firstKey() {
1585 return fromMap().firstKey();
1586 }
1587
1588 @Override public SortedMap<K, V2> headMap(K toKey) {
1589 return transformEntries(fromMap().headMap(toKey), transformer);
1590 }
1591
1592 @Override public K lastKey() {
1593 return fromMap().lastKey();
1594 }
1595
1596 @Override public SortedMap<K, V2> subMap(K fromKey, K toKey) {
1597 return transformEntries(
1598 fromMap().subMap(fromKey, toKey), transformer);
1599 }
1600
1601 @Override public SortedMap<K, V2> tailMap(K fromKey) {
1602 return transformEntries(fromMap().tailMap(fromKey), transformer);
1603 }
1604 }
1605
1606 @GwtIncompatible("NavigableMap")
1607 private static class TransformedEntriesNavigableMap<K, V1, V2>
1608 extends TransformedEntriesSortedMap<K, V1, V2>
1609 implements NavigableMap<K, V2> {
1610
1611 TransformedEntriesNavigableMap(NavigableMap<K, V1> fromMap,
1612 EntryTransformer<? super K, ? super V1, V2> transformer) {
1613 super(fromMap, transformer);
1614 }
1615
1616 @Override public Entry<K, V2> ceilingEntry(K key) {
1617 return transformEntry(fromMap().ceilingEntry(key));
1618 }
1619
1620 @Override public K ceilingKey(K key) {
1621 return fromMap().ceilingKey(key);
1622 }
1623
1624 @Override public NavigableSet<K> descendingKeySet() {
1625 return fromMap().descendingKeySet();
1626 }
1627
1628 @Override public NavigableMap<K, V2> descendingMap() {
1629 return transformEntries(fromMap().descendingMap(), transformer);
1630 }
1631
1632 @Override public Entry<K, V2> firstEntry() {
1633 return transformEntry(fromMap().firstEntry());
1634 }
1635 @Override public Entry<K, V2> floorEntry(K key) {
1636 return transformEntry(fromMap().floorEntry(key));
1637 }
1638
1639 @Override public K floorKey(K key) {
1640 return fromMap().floorKey(key);
1641 }
1642
1643 @Override public NavigableMap<K, V2> headMap(K toKey) {
1644 return headMap(toKey, false);
1645 }
1646
1647 @Override public NavigableMap<K, V2> headMap(K toKey, boolean inclusive) {
1648 return transformEntries(
1649 fromMap().headMap(toKey, inclusive), transformer);
1650 }
1651
1652 @Override public Entry<K, V2> higherEntry(K key) {
1653 return transformEntry(fromMap().higherEntry(key));
1654 }
1655
1656 @Override public K higherKey(K key) {
1657 return fromMap().higherKey(key);
1658 }
1659
1660 @Override public Entry<K, V2> lastEntry() {
1661 return transformEntry(fromMap().lastEntry());
1662 }
1663
1664 @Override public Entry<K, V2> lowerEntry(K key) {
1665 return transformEntry(fromMap().lowerEntry(key));
1666 }
1667
1668 @Override public K lowerKey(K key) {
1669 return fromMap().lowerKey(key);
1670 }
1671
1672 @Override public NavigableSet<K> navigableKeySet() {
1673 return fromMap().navigableKeySet();
1674 }
1675
1676 @Override public Entry<K, V2> pollFirstEntry() {
1677 return transformEntry(fromMap().pollFirstEntry());
1678 }
1679
1680 @Override public Entry<K, V2> pollLastEntry() {
1681 return transformEntry(fromMap().pollLastEntry());
1682 }
1683
1684 @Override public NavigableMap<K, V2> subMap(
1685 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1686 return transformEntries(
1687 fromMap().subMap(fromKey, fromInclusive, toKey, toInclusive),
1688 transformer);
1689 }
1690
1691 @Override public NavigableMap<K, V2> subMap(K fromKey, K toKey) {
1692 return subMap(fromKey, true, toKey, false);
1693 }
1694
1695 @Override public NavigableMap<K, V2> tailMap(K fromKey) {
1696 return tailMap(fromKey, true);
1697 }
1698
1699 @Override public NavigableMap<K, V2> tailMap(K fromKey, boolean inclusive) {
1700 return transformEntries(
1701 fromMap().tailMap(fromKey, inclusive), transformer);
1702 }
1703
1704 private Entry<K, V2> transformEntry(Entry<K, V1> entry) {
1705 if (entry == null) {
1706 return null;
1707 }
1708 K key = entry.getKey();
1709 V2 v2 = transformer.transformEntry(key, entry.getValue());
1710 return Maps.immutableEntry(key, v2);
1711 }
1712
1713 @Override protected NavigableMap<K, V1> fromMap() {
1714 return (NavigableMap<K, V1>) super.fromMap();
1715 }
1716 }
1717
1718 /**
1719 * Returns a map containing the mappings in {@code unfiltered} whose keys
1720 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1721 * changes to one affect the other.
1722 *
1723 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1724 * values()} views have iterators that don't support {@code remove()}, but all
1725 * other methods are supported by the map and its views. When given a key that
1726 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
1727 * methods throw an {@link IllegalArgumentException}.
1728 *
1729 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1730 * on the filtered map or its views, only mappings whose keys satisfy the
1731 * filter will be removed from the underlying map.
1732 *
1733 * <p>The returned map isn't threadsafe or serializable, even if {@code
1734 * unfiltered} is.
1735 *
1736 * <p>Many of the filtered map's methods, such as {@code size()},
1737 * iterate across every key/value mapping in the underlying map and determine
1738 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1739 * faster to copy the filtered map and use the copy.
1740 *
1741 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1742 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1743 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1744 * inconsistent with equals.
1745 */
1746 public static <K, V> Map<K, V> filterKeys(
1747 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1748 if (unfiltered instanceof SortedMap) {
1749 return filterKeys((SortedMap<K, V>) unfiltered, keyPredicate);
1750 }
1751 checkNotNull(keyPredicate);
1752 Predicate<Entry<K, V>> entryPredicate =
1753 new Predicate<Entry<K, V>>() {
1754 @Override
1755 public boolean apply(Entry<K, V> input) {
1756 return keyPredicate.apply(input.getKey());
1757 }
1758 };
1759 return (unfiltered instanceof AbstractFilteredMap)
1760 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1761 : new FilteredKeyMap<K, V>(
1762 checkNotNull(unfiltered), keyPredicate, entryPredicate);
1763 }
1764
1765 /**
1766 * Returns a sorted map containing the mappings in {@code unfiltered} whose
1767 * keys satisfy a predicate. The returned map is a live view of {@code
1768 * unfiltered}; changes to one affect the other.
1769 *
1770 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1771 * values()} views have iterators that don't support {@code remove()}, but all
1772 * other methods are supported by the map and its views. When given a key that
1773 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
1774 * methods throw an {@link IllegalArgumentException}.
1775 *
1776 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1777 * on the filtered map or its views, only mappings whose keys satisfy the
1778 * filter will be removed from the underlying map.
1779 *
1780 * <p>The returned map isn't threadsafe or serializable, even if {@code
1781 * unfiltered} is.
1782 *
1783 * <p>Many of the filtered map's methods, such as {@code size()},
1784 * iterate across every key/value mapping in the underlying map and determine
1785 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1786 * faster to copy the filtered map and use the copy.
1787 *
1788 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1789 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1790 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1791 * inconsistent with equals.
1792 *
1793 * @since 11.0
1794 */
1795 public static <K, V> SortedMap<K, V> filterKeys(
1796 SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1797 // TODO: Return a subclass of Maps.FilteredKeyMap for slightly better
1798 // performance.
1799 checkNotNull(keyPredicate);
1800 Predicate<Entry<K, V>> entryPredicate = new Predicate<Entry<K, V>>() {
1801 @Override
1802 public boolean apply(Entry<K, V> input) {
1803 return keyPredicate.apply(input.getKey());
1804 }
1805 };
1806 return filterEntries(unfiltered, entryPredicate);
1807 }
1808
1809 /**
1810 * Returns a map containing the mappings in {@code unfiltered} whose values
1811 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1812 * changes to one affect the other.
1813 *
1814 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1815 * values()} views have iterators that don't support {@code remove()}, but all
1816 * other methods are supported by the map and its views. When given a value
1817 * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1818 * putAll()}, and {@link Entry#setValue} methods throw an {@link
1819 * IllegalArgumentException}.
1820 *
1821 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1822 * on the filtered map or its views, only mappings whose values satisfy the
1823 * filter will be removed from the underlying map.
1824 *
1825 * <p>The returned map isn't threadsafe or serializable, even if {@code
1826 * unfiltered} is.
1827 *
1828 * <p>Many of the filtered map's methods, such as {@code size()},
1829 * iterate across every key/value mapping in the underlying map and determine
1830 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1831 * faster to copy the filtered map and use the copy.
1832 *
1833 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1834 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1835 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1836 * inconsistent with equals.
1837 */
1838 public static <K, V> Map<K, V> filterValues(
1839 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1840 if (unfiltered instanceof SortedMap) {
1841 return filterValues((SortedMap<K, V>) unfiltered, valuePredicate);
1842 }
1843 checkNotNull(valuePredicate);
1844 Predicate<Entry<K, V>> entryPredicate =
1845 new Predicate<Entry<K, V>>() {
1846 @Override
1847 public boolean apply(Entry<K, V> input) {
1848 return valuePredicate.apply(input.getValue());
1849 }
1850 };
1851 return filterEntries(unfiltered, entryPredicate);
1852 }
1853
1854 /**
1855 * Returns a sorted map containing the mappings in {@code unfiltered} whose
1856 * values satisfy a predicate. The returned map is a live view of {@code
1857 * unfiltered}; changes to one affect the other.
1858 *
1859 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1860 * values()} views have iterators that don't support {@code remove()}, but all
1861 * other methods are supported by the map and its views. When given a value
1862 * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1863 * putAll()}, and {@link Entry#setValue} methods throw an {@link
1864 * IllegalArgumentException}.
1865 *
1866 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1867 * on the filtered map or its views, only mappings whose values satisfy the
1868 * filter will be removed from the underlying map.
1869 *
1870 * <p>The returned map isn't threadsafe or serializable, even if {@code
1871 * unfiltered} is.
1872 *
1873 * <p>Many of the filtered map's methods, such as {@code size()},
1874 * iterate across every key/value mapping in the underlying map and determine
1875 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1876 * faster to copy the filtered map and use the copy.
1877 *
1878 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1879 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1880 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1881 * inconsistent with equals.
1882 *
1883 * @since 11.0
1884 */
1885 public static <K, V> SortedMap<K, V> filterValues(
1886 SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1887 checkNotNull(valuePredicate);
1888 Predicate<Entry<K, V>> entryPredicate =
1889 new Predicate<Entry<K, V>>() {
1890 @Override
1891 public boolean apply(Entry<K, V> input) {
1892 return valuePredicate.apply(input.getValue());
1893 }
1894 };
1895 return filterEntries(unfiltered, entryPredicate);
1896 }
1897
1898 /**
1899 * Returns a map containing the mappings in {@code unfiltered} that satisfy a
1900 * predicate. The returned map is a live view of {@code unfiltered}; changes
1901 * to one affect the other.
1902 *
1903 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1904 * values()} views have iterators that don't support {@code remove()}, but all
1905 * other methods are supported by the map and its views. When given a
1906 * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1907 * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1908 * Similarly, the map's entries have a {@link Entry#setValue} method that
1909 * throws an {@link IllegalArgumentException} when the existing key and the
1910 * provided value don't satisfy the predicate.
1911 *
1912 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1913 * on the filtered map or its views, only mappings that satisfy the filter
1914 * will be removed from the underlying map.
1915 *
1916 * <p>The returned map isn't threadsafe or serializable, even if {@code
1917 * unfiltered} is.
1918 *
1919 * <p>Many of the filtered map's methods, such as {@code size()},
1920 * iterate across every key/value mapping in the underlying map and determine
1921 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1922 * faster to copy the filtered map and use the copy.
1923 *
1924 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1925 * equals</i>, as documented at {@link Predicate#apply}.
1926 */
1927 public static <K, V> Map<K, V> filterEntries(
1928 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1929 if (unfiltered instanceof SortedMap) {
1930 return filterEntries((SortedMap<K, V>) unfiltered, entryPredicate);
1931 }
1932 checkNotNull(entryPredicate);
1933 return (unfiltered instanceof AbstractFilteredMap)
1934 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1935 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1936 }
1937
1938 /**
1939 * Returns a sorted map containing the mappings in {@code unfiltered} that
1940 * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1941 * changes to one affect the other.
1942 *
1943 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1944 * values()} views have iterators that don't support {@code remove()}, but all
1945 * other methods are supported by the map and its views. When given a
1946 * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1947 * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1948 * Similarly, the map's entries have a {@link Entry#setValue} method that
1949 * throws an {@link IllegalArgumentException} when the existing key and the
1950 * provided value don't satisfy the predicate.
1951 *
1952 * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1953 * on the filtered map or its views, only mappings that satisfy the filter
1954 * will be removed from the underlying map.
1955 *
1956 * <p>The returned map isn't threadsafe or serializable, even if {@code
1957 * unfiltered} is.
1958 *
1959 * <p>Many of the filtered map's methods, such as {@code size()},
1960 * iterate across every key/value mapping in the underlying map and determine
1961 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1962 * faster to copy the filtered map and use the copy.
1963 *
1964 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1965 * equals</i>, as documented at {@link Predicate#apply}.
1966 *
1967 * @since 11.0
1968 */
1969 public static <K, V> SortedMap<K, V> filterEntries(
1970 SortedMap<K, V> unfiltered,
1971 Predicate<? super Entry<K, V>> entryPredicate) {
1972 checkNotNull(entryPredicate);
1973 return (unfiltered instanceof FilteredEntrySortedMap)
1974 ? filterFiltered((FilteredEntrySortedMap<K, V>) unfiltered, entryPredicate)
1975 : new FilteredEntrySortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1976 }
1977
1978 /**
1979 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1980 * filtering a filtered map.
1981 */
1982 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
1983 Predicate<? super Entry<K, V>> entryPredicate) {
1984 Predicate<Entry<K, V>> predicate =
1985 Predicates.and(map.predicate, entryPredicate);
1986 return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
1987 }
1988
1989 private abstract static class AbstractFilteredMap<K, V>
1990 extends AbstractMap<K, V> {
1991 final Map<K, V> unfiltered;
1992 final Predicate<? super Entry<K, V>> predicate;
1993
1994 AbstractFilteredMap(
1995 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
1996 this.unfiltered = unfiltered;
1997 this.predicate = predicate;
1998 }
1999
2000 boolean apply(Object key, V value) {
2001 // This method is called only when the key is in the map, implying that
2002 // key is a K.
2003 @SuppressWarnings("unchecked")
2004 K k = (K) key;
2005 return predicate.apply(Maps.immutableEntry(k, value));
2006 }
2007
2008 @Override public V put(K key, V value) {
2009 checkArgument(apply(key, value));
2010 return unfiltered.put(key, value);
2011 }
2012
2013 @Override public void putAll(Map<? extends K, ? extends V> map) {
2014 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
2015 checkArgument(apply(entry.getKey(), entry.getValue()));
2016 }
2017 unfiltered.putAll(map);
2018 }
2019
2020 @Override public boolean containsKey(Object key) {
2021 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
2022 }
2023
2024 @Override public V get(Object key) {
2025 V value = unfiltered.get(key);
2026 return ((value != null) && apply(key, value)) ? value : null;
2027 }
2028
2029 @Override public boolean isEmpty() {
2030 return entrySet().isEmpty();
2031 }
2032
2033 @Override public V remove(Object key) {
2034 return containsKey(key) ? unfiltered.remove(key) : null;
2035 }
2036
2037 Collection<V> values;
2038
2039 @Override public Collection<V> values() {
2040 Collection<V> result = values;
2041 return (result == null) ? values = new Values() : result;
2042 }
2043
2044 class Values extends AbstractCollection<V> {
2045 @Override public Iterator<V> iterator() {
2046 final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
2047 return new UnmodifiableIterator<V>() {
2048 @Override
2049 public boolean hasNext() {
2050 return entryIterator.hasNext();
2051 }
2052
2053 @Override
2054 public V next() {
2055 return entryIterator.next().getValue();
2056 }
2057 };
2058 }
2059
2060 @Override public int size() {
2061 return entrySet().size();
2062 }
2063
2064 @Override public void clear() {
2065 entrySet().clear();
2066 }
2067
2068 @Override public boolean isEmpty() {
2069 return entrySet().isEmpty();
2070 }
2071
2072 @Override public boolean remove(Object o) {
2073 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
2074 while (iterator.hasNext()) {
2075 Entry<K, V> entry = iterator.next();
2076 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
2077 iterator.remove();
2078 return true;
2079 }
2080 }
2081 return false;
2082 }
2083
2084 @Override public boolean removeAll(Collection<?> collection) {
2085 checkNotNull(collection);
2086 boolean changed = false;
2087 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
2088 while (iterator.hasNext()) {
2089 Entry<K, V> entry = iterator.next();
2090 if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
2091 iterator.remove();
2092 changed = true;
2093 }
2094 }
2095 return changed;
2096 }
2097
2098 @Override public boolean retainAll(Collection<?> collection) {
2099 checkNotNull(collection);
2100 boolean changed = false;
2101 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
2102 while (iterator.hasNext()) {
2103 Entry<K, V> entry = iterator.next();
2104 if (!collection.contains(entry.getValue())
2105 && predicate.apply(entry)) {
2106 iterator.remove();
2107 changed = true;
2108 }
2109 }
2110 return changed;
2111 }
2112
2113 @Override public Object[] toArray() {
2114 // creating an ArrayList so filtering happens once
2115 return Lists.newArrayList(iterator()).toArray();
2116 }
2117
2118 @Override public <T> T[] toArray(T[] array) {
2119 return Lists.newArrayList(iterator()).toArray(array);
2120 }
2121 }
2122 }
2123 /**
2124 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
2125 * filtering a filtered sorted map.
2126 */
2127 private static <K, V> SortedMap<K, V> filterFiltered(
2128 FilteredEntrySortedMap<K, V> map,
2129 Predicate<? super Entry<K, V>> entryPredicate) {
2130 Predicate<Entry<K, V>> predicate
2131 = Predicates.and(map.predicate, entryPredicate);
2132 return new FilteredEntrySortedMap<K, V>(map.sortedMap(), predicate);
2133 }
2134
2135 private static class FilteredEntrySortedMap<K, V>
2136 extends FilteredEntryMap<K, V> implements SortedMap<K, V> {
2137
2138 FilteredEntrySortedMap(SortedMap<K, V> unfiltered,
2139 Predicate<? super Entry<K, V>> entryPredicate) {
2140 super(unfiltered, entryPredicate);
2141 }
2142
2143 SortedMap<K, V> sortedMap() {
2144 return (SortedMap<K, V>) unfiltered;
2145 }
2146
2147 @Override public Comparator<? super K> comparator() {
2148 return sortedMap().comparator();
2149 }
2150
2151 @Override public K firstKey() {
2152 // correctly throws NoSuchElementException when filtered map is empty.
2153 return keySet().iterator().next();
2154 }
2155
2156 @Override public K lastKey() {
2157 SortedMap<K, V> headMap = sortedMap();
2158 while (true) {
2159 // correctly throws NoSuchElementException when filtered map is empty.
2160 K key = headMap.lastKey();
2161 if (apply(key, unfiltered.get(key))) {
2162 return key;
2163 }
2164 headMap = sortedMap().headMap(key);
2165 }
2166 }
2167
2168 @Override public SortedMap<K, V> headMap(K toKey) {
2169 return new FilteredEntrySortedMap<K, V>(sortedMap().headMap(toKey), predicate);
2170 }
2171
2172 @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
2173 return new FilteredEntrySortedMap<K, V>(
2174 sortedMap().subMap(fromKey, toKey), predicate);
2175 }
2176
2177 @Override public SortedMap<K, V> tailMap(K fromKey) {
2178 return new FilteredEntrySortedMap<K, V>(
2179 sortedMap().tailMap(fromKey), predicate);
2180 }
2181 }
2182
2183 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
2184 Predicate<? super K> keyPredicate;
2185
2186 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
2187 Predicate<Entry<K, V>> entryPredicate) {
2188 super(unfiltered, entryPredicate);
2189 this.keyPredicate = keyPredicate;
2190 }
2191
2192 Set<Entry<K, V>> entrySet;
2193
2194 @Override public Set<Entry<K, V>> entrySet() {
2195 Set<Entry<K, V>> result = entrySet;
2196 return (result == null)
2197 ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
2198 : result;
2199 }
2200
2201 Set<K> keySet;
2202
2203 @Override public Set<K> keySet() {
2204 Set<K> result = keySet;
2205 return (result == null)
2206 ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
2207 : result;
2208 }
2209
2210 // The cast is called only when the key is in the unfiltered map, implying
2211 // that key is a K.
2212 @Override
2213 @SuppressWarnings("unchecked")
2214 public boolean containsKey(Object key) {
2215 return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
2216 }
2217 }
2218
2219 static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
2220 /**
2221 * Entries in this set satisfy the predicate, but they don't validate the
2222 * input to {@code Entry.setValue()}.
2223 */
2224 final Set<Entry<K, V>> filteredEntrySet;
2225
2226 FilteredEntryMap(
2227 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2228 super(unfiltered, entryPredicate);
2229 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
2230 }
2231
2232 Set<Entry<K, V>> entrySet;
2233
2234 @Override public Set<Entry<K, V>> entrySet() {
2235 Set<Entry<K, V>> result = entrySet;
2236 return (result == null) ? entrySet = new EntrySet() : result;
2237 }
2238
2239 private class EntrySet extends ForwardingSet<Entry<K, V>> {
2240 @Override protected Set<Entry<K, V>> delegate() {
2241 return filteredEntrySet;
2242 }
2243
2244 @Override public Iterator<Entry<K, V>> iterator() {
2245 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
2246 return new UnmodifiableIterator<Entry<K, V>>() {
2247 @Override
2248 public boolean hasNext() {
2249 return iterator.hasNext();
2250 }
2251
2252 @Override
2253 public Entry<K, V> next() {
2254 final Entry<K, V> entry = iterator.next();
2255 return new ForwardingMapEntry<K, V>() {
2256 @Override protected Entry<K, V> delegate() {
2257 return entry;
2258 }
2259
2260 @Override public V setValue(V value) {
2261 checkArgument(apply(entry.getKey(), value));
2262 return super.setValue(value);
2263 }
2264 };
2265 }
2266 };
2267 }
2268 }
2269
2270 Set<K> keySet;
2271
2272 @Override public Set<K> keySet() {
2273 Set<K> result = keySet;
2274 return (result == null) ? keySet = new KeySet() : result;
2275 }
2276
2277 private class KeySet extends Sets.ImprovedAbstractSet<K> {
2278 @Override public Iterator<K> iterator() {
2279 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
2280 return new UnmodifiableIterator<K>() {
2281 @Override
2282 public boolean hasNext() {
2283 return iterator.hasNext();
2284 }
2285
2286 @Override
2287 public K next() {
2288 return iterator.next().getKey();
2289 }
2290 };
2291 }
2292
2293 @Override public int size() {
2294 return filteredEntrySet.size();
2295 }
2296
2297 @Override public void clear() {
2298 filteredEntrySet.clear();
2299 }
2300
2301 @Override public boolean contains(Object o) {
2302 return containsKey(o);
2303 }
2304
2305 @Override public boolean remove(Object o) {
2306 if (containsKey(o)) {
2307 unfiltered.remove(o);
2308 return true;
2309 }
2310 return false;
2311 }
2312
2313 @Override public boolean retainAll(Collection<?> collection) {
2314 checkNotNull(collection); // for GWT
2315 boolean changed = false;
2316 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
2317 while (iterator.hasNext()) {
2318 Entry<K, V> entry = iterator.next();
2319 if (predicate.apply(entry) && !collection.contains(entry.getKey())) {
2320 iterator.remove();
2321 changed = true;
2322 }
2323 }
2324 return changed;
2325 }
2326
2327 @Override public Object[] toArray() {
2328 // creating an ArrayList so filtering happens once
2329 return Lists.newArrayList(iterator()).toArray();
2330 }
2331
2332 @Override public <T> T[] toArray(T[] array) {
2333 return Lists.newArrayList(iterator()).toArray(array);
2334 }
2335 }
2336 }
2337
2338 /**
2339 * Returns an unmodifiable view of the specified navigable map. Query operations on the returned
2340 * map read through to the specified map, and attempts to modify the returned map, whether direct
2341 * or via its views, result in an {@code UnsupportedOperationException}.
2342 *
2343 * <p>The returned navigable map will be serializable if the specified navigable map is
2344 * serializable.
2345 *
2346 * @param map the navigable map for which an unmodifiable view is to be returned
2347 * @return an unmodifiable view of the specified navigable map
2348 * @since 12.0
2349 */
2350 @GwtIncompatible("NavigableMap")
2351 public static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, V> map) {
2352 checkNotNull(map);
2353 if (map instanceof UnmodifiableNavigableMap) {
2354 return map;
2355 } else {
2356 return new UnmodifiableNavigableMap<K, V>(map);
2357 }
2358 }
2359
2360 @Nullable private static <K, V> Entry<K, V> unmodifiableOrNull(@Nullable Entry<K, V> entry) {
2361 return (entry == null) ? null : Maps.unmodifiableEntry(entry);
2362 }
2363
2364 @GwtIncompatible("NavigableMap")
2365 static class UnmodifiableNavigableMap<K, V>
2366 extends ForwardingSortedMap<K, V> implements NavigableMap<K, V>, Serializable {
2367 private final NavigableMap<K, V> delegate;
2368
2369 UnmodifiableNavigableMap(NavigableMap<K, V> delegate) {
2370 this.delegate = delegate;
2371 }
2372
2373 @Override
2374 protected SortedMap<K, V> delegate() {
2375 return Collections.unmodifiableSortedMap(delegate);
2376 }
2377
2378 @Override
2379 public Entry<K, V> lowerEntry(K key) {
2380 return unmodifiableOrNull(delegate.lowerEntry(key));
2381 }
2382
2383 @Override
2384 public K lowerKey(K key) {
2385 return delegate.lowerKey(key);
2386 }
2387
2388 @Override
2389 public Entry<K, V> floorEntry(K key) {
2390 return unmodifiableOrNull(delegate.floorEntry(key));
2391 }
2392
2393 @Override
2394 public K floorKey(K key) {
2395 return delegate.floorKey(key);
2396 }
2397
2398 @Override
2399 public Entry<K, V> ceilingEntry(K key) {
2400 return unmodifiableOrNull(delegate.ceilingEntry(key));
2401 }
2402
2403 @Override
2404 public K ceilingKey(K key) {
2405 return delegate.ceilingKey(key);
2406 }
2407
2408 @Override
2409 public Entry<K, V> higherEntry(K key) {
2410 return unmodifiableOrNull(delegate.higherEntry(key));
2411 }
2412
2413 @Override
2414 public K higherKey(K key) {
2415 return delegate.higherKey(key);
2416 }
2417
2418 @Override
2419 public Entry<K, V> firstEntry() {
2420 return unmodifiableOrNull(delegate.firstEntry());
2421 }
2422
2423 @Override
2424 public Entry<K, V> lastEntry() {
2425 return unmodifiableOrNull(delegate.lastEntry());
2426 }
2427
2428 @Override
2429 public final Entry<K, V> pollFirstEntry() {
2430 throw new UnsupportedOperationException();
2431 }
2432
2433 @Override
2434 public final Entry<K, V> pollLastEntry() {
2435 throw new UnsupportedOperationException();
2436 }
2437
2438 private transient UnmodifiableNavigableMap<K, V> descendingMap;
2439
2440 @Override
2441 public NavigableMap<K, V> descendingMap() {
2442 UnmodifiableNavigableMap<K, V> result = descendingMap;
2443 if (result == null) {
2444 descendingMap = result = new UnmodifiableNavigableMap<K, V>(delegate.descendingMap());
2445 result.descendingMap = this;
2446 }
2447 return result;
2448 }
2449
2450 @Override
2451 public Set<K> keySet() {
2452 return navigableKeySet();
2453 }
2454
2455 @Override
2456 public NavigableSet<K> navigableKeySet() {
2457 return Sets.unmodifiableNavigableSet(delegate.navigableKeySet());
2458 }
2459
2460 @Override
2461 public NavigableSet<K> descendingKeySet() {
2462 return Sets.unmodifiableNavigableSet(delegate.descendingKeySet());
2463 }
2464
2465 @Override
2466 public SortedMap<K, V> subMap(K fromKey, K toKey) {
2467 return subMap(fromKey, true, toKey, false);
2468 }
2469
2470 @Override
2471 public SortedMap<K, V> headMap(K toKey) {
2472 return headMap(toKey, false);
2473 }
2474
2475 @Override
2476 public SortedMap<K, V> tailMap(K fromKey) {
2477 return tailMap(fromKey, true);
2478 }
2479
2480 @Override
2481 public
2482 NavigableMap<K, V>
2483 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2484 return Maps.unmodifiableNavigableMap(delegate.subMap(
2485 fromKey,
2486 fromInclusive,
2487 toKey,
2488 toInclusive));
2489 }
2490
2491 @Override
2492 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
2493 return Maps.unmodifiableNavigableMap(delegate.headMap(toKey, inclusive));
2494 }
2495
2496 @Override
2497 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
2498 return Maps.unmodifiableNavigableMap(delegate.tailMap(fromKey, inclusive));
2499 }
2500 }
2501
2502 /**
2503 * Returns a synchronized (thread-safe) navigable map backed by the specified
2504 * navigable map. In order to guarantee serial access, it is critical that
2505 * <b>all</b> access to the backing navigable map is accomplished
2506 * through the returned navigable map (or its views).
2507 *
2508 * <p>It is imperative that the user manually synchronize on the returned
2509 * navigable map when iterating over any of its collection views, or the
2510 * collections views of any of its {@code descendingMap}, {@code subMap},
2511 * {@code headMap} or {@code tailMap} views. <pre> {@code
2512 *
2513 * NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>());
2514 *
2515 * // Needn't be in synchronized block
2516 * NavigableSet<K> set = map.navigableKeySet();
2517 *
2518 * synchronized (map) { // Synchronizing on map, not set!
2519 * Iterator<K> it = set.iterator(); // Must be in synchronized block
2520 * while (it.hasNext()){
2521 * foo(it.next());
2522 * }
2523 * }}</pre>
2524 *
2525 * or: <pre> {@code
2526 *
2527 * NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>());
2528 * NavigableMap<K, V> map2 = map.subMap(foo, false, bar, true);
2529 *
2530 * // Needn't be in synchronized block
2531 * NavigableSet<K> set2 = map2.descendingKeySet();
2532 *
2533 * synchronized (map) { // Synchronizing on map, not map2 or set2!
2534 * Iterator<K> it = set2.iterator(); // Must be in synchronized block
2535 * while (it.hasNext()){
2536 * foo(it.next());
2537 * }
2538 * }}</pre>
2539 *
2540 * Failure to follow this advice may result in non-deterministic behavior.
2541 *
2542 * <p>The returned navigable map will be serializable if the specified
2543 * navigable map is serializable.
2544 *
2545 * @param navigableMap the navigable map to be "wrapped" in a synchronized
2546 * navigable map.
2547 * @return a synchronized view of the specified navigable map.
2548 * @since 13.0
2549 */
2550 @Beta
2551 @GwtIncompatible("NavigableMap")
2552 public static <K, V> NavigableMap<K, V> synchronizedNavigableMap(
2553 NavigableMap<K, V> navigableMap) {
2554 return Synchronized.navigableMap(navigableMap);
2555 }
2556
2557 /**
2558 * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
2559 * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
2560 * implementations where {@code size()} is O(n), and it delegates the {@code
2561 * isEmpty()} methods of its key set and value collection to this
2562 * implementation.
2563 */
2564 @GwtCompatible
2565 abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
2566 /**
2567 * Creates the entry set to be returned by {@link #entrySet()}. This method
2568 * is invoked at most once on a given map, at the time when {@code entrySet}
2569 * is first called.
2570 */
2571 protected abstract Set<Entry<K, V>> createEntrySet();
2572
2573 private Set<Entry<K, V>> entrySet;
2574
2575 @Override public Set<Entry<K, V>> entrySet() {
2576 Set<Entry<K, V>> result = entrySet;
2577 if (result == null) {
2578 entrySet = result = createEntrySet();
2579 }
2580 return result;
2581 }
2582
2583 private Set<K> keySet;
2584
2585 @Override public Set<K> keySet() {
2586 Set<K> result = keySet;
2587 if (result == null) {
2588 return keySet = new KeySet<K, V>() {
2589 @Override Map<K, V> map() {
2590 return ImprovedAbstractMap.this;
2591 }
2592 };
2593 }
2594 return result;
2595 }
2596
2597 private Collection<V> values;
2598
2599 @Override public Collection<V> values() {
2600 Collection<V> result = values;
2601 if (result == null) {
2602 return values = new Values<K, V>() {
2603 @Override Map<K, V> map() {
2604 return ImprovedAbstractMap.this;
2605 }
2606 };
2607 }
2608 return result;
2609 }
2610 }
2611
2612 static final MapJoiner STANDARD_JOINER =
2613 Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
2614
2615 /**
2616 * Delegates to {@link Map#get}. Returns {@code null} on {@code
2617 * ClassCastException}.
2618 */
2619 static <V> V safeGet(Map<?, V> map, Object key) {
2620 try {
2621 return map.get(key);
2622 } catch (ClassCastException e) {
2623 return null;
2624 }
2625 }
2626
2627 /**
2628 * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
2629 * ClassCastException}
2630 */
2631 static boolean safeContainsKey(Map<?, ?> map, Object key) {
2632 try {
2633 return map.containsKey(key);
2634 } catch (ClassCastException e) {
2635 return false;
2636 }
2637 }
2638
2639 /**
2640 * Implements {@code Collection.contains} safely for forwarding collections of
2641 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
2642 * wrapped using {@link #unmodifiableEntry} to protect against a possible
2643 * nefarious equals method.
2644 *
2645 * <p>Note that {@code c} is the backing (delegate) collection, rather than
2646 * the forwarding collection.
2647 *
2648 * @param c the delegate (unwrapped) collection of map entries
2649 * @param o the object that might be contained in {@code c}
2650 * @return {@code true} if {@code c} contains {@code o}
2651 */
2652 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
2653 if (!(o instanceof Entry)) {
2654 return false;
2655 }
2656 return c.contains(unmodifiableEntry((Entry<?, ?>) o));
2657 }
2658
2659 /**
2660 * Implements {@code Collection.remove} safely for forwarding collections of
2661 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
2662 * wrapped using {@link #unmodifiableEntry} to protect against a possible
2663 * nefarious equals method.
2664 *
2665 * <p>Note that {@code c} is backing (delegate) collection, rather than the
2666 * forwarding collection.
2667 *
2668 * @param c the delegate (unwrapped) collection of map entries
2669 * @param o the object to remove from {@code c}
2670 * @return {@code true} if {@code c} was changed
2671 */
2672 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
2673 if (!(o instanceof Entry)) {
2674 return false;
2675 }
2676 return c.remove(unmodifiableEntry((Entry<?, ?>) o));
2677 }
2678
2679 /**
2680 * An implementation of {@link Map#equals}.
2681 */
2682 static boolean equalsImpl(Map<?, ?> map, Object object) {
2683 if (map == object) {
2684 return true;
2685 }
2686 if (object instanceof Map) {
2687 Map<?, ?> o = (Map<?, ?>) object;
2688 return map.entrySet().equals(o.entrySet());
2689 }
2690 return false;
2691 }
2692
2693 /**
2694 * An implementation of {@link Map#hashCode}.
2695 */
2696 static int hashCodeImpl(Map<?, ?> map) {
2697 return Sets.hashCodeImpl(map.entrySet());
2698 }
2699
2700 /**
2701 * An implementation of {@link Map#toString}.
2702 */
2703 static String toStringImpl(Map<?, ?> map) {
2704 StringBuilder sb
2705 = Collections2.newStringBuilderForCollection(map.size()).append('{');
2706 STANDARD_JOINER.appendTo(sb, map);
2707 return sb.append('}').toString();
2708 }
2709
2710 /**
2711 * An implementation of {@link Map#putAll}.
2712 */
2713 static <K, V> void putAllImpl(
2714 Map<K, V> self, Map<? extends K, ? extends V> map) {
2715 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
2716 self.put(entry.getKey(), entry.getValue());
2717 }
2718 }
2719
2720 /**
2721 * An admittedly inefficient implementation of {@link Map#containsKey}.
2722 */
2723 static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
2724 for (Entry<?, ?> entry : map.entrySet()) {
2725 if (Objects.equal(entry.getKey(), key)) {
2726 return true;
2727 }
2728 }
2729 return false;
2730 }
2731
2732 /**
2733 * An implementation of {@link Map#containsValue}.
2734 */
2735 static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
2736 for (Entry<?, ?> entry : map.entrySet()) {
2737 if (Objects.equal(entry.getValue(), value)) {
2738 return true;
2739 }
2740 }
2741 return false;
2742 }
2743
2744 static <K, V> Iterator<K> keyIterator(Iterator<Entry<K, V>> entryIterator) {
2745 return new TransformedIterator<Entry<K, V>, K>(entryIterator) {
2746 @Override
2747 K transform(Entry<K, V> entry) {
2748 return entry.getKey();
2749 }
2750 };
2751 }
2752
2753 abstract static class KeySet<K, V> extends Sets.ImprovedAbstractSet<K> {
2754 abstract Map<K, V> map();
2755
2756 @Override public Iterator<K> iterator() {
2757 return keyIterator(map().entrySet().iterator());
2758 }
2759
2760 @Override public int size() {
2761 return map().size();
2762 }
2763
2764 @Override public boolean isEmpty() {
2765 return map().isEmpty();
2766 }
2767
2768 @Override public boolean contains(Object o) {
2769 return map().containsKey(o);
2770 }
2771
2772 @Override public boolean remove(Object o) {
2773 if (contains(o)) {
2774 map().remove(o);
2775 return true;
2776 }
2777 return false;
2778 }
2779
2780 @Override public void clear() {
2781 map().clear();
2782 }
2783 }
2784
2785 @Nullable
2786 static <K> K keyOrNull(@Nullable Entry<K, ?> entry) {
2787 return (entry == null) ? null : entry.getKey();
2788 }
2789
2790 @GwtIncompatible("NavigableMap")
2791 abstract static class NavigableKeySet<K, V> extends KeySet<K, V> implements NavigableSet<K> {
2792 @Override
2793 abstract NavigableMap<K, V> map();
2794
2795 @Override
2796 public Comparator<? super K> comparator() {
2797 return map().comparator();
2798 }
2799
2800 @Override
2801 public K first() {
2802 return map().firstKey();
2803 }
2804
2805 @Override
2806 public K last() {
2807 return map().lastKey();
2808 }
2809
2810 @Override
2811 public K lower(K e) {
2812 return map().lowerKey(e);
2813 }
2814
2815 @Override
2816 public K floor(K e) {
2817 return map().floorKey(e);
2818 }
2819
2820 @Override
2821 public K ceiling(K e) {
2822 return map().ceilingKey(e);
2823 }
2824
2825 @Override
2826 public K higher(K e) {
2827 return map().higherKey(e);
2828 }
2829
2830 @Override
2831 public K pollFirst() {
2832 return keyOrNull(map().pollFirstEntry());
2833 }
2834
2835 @Override
2836 public K pollLast() {
2837 return keyOrNull(map().pollLastEntry());
2838 }
2839
2840 @Override
2841 public NavigableSet<K> descendingSet() {
2842 return map().descendingKeySet();
2843 }
2844
2845 @Override
2846 public Iterator<K> descendingIterator() {
2847 return descendingSet().iterator();
2848 }
2849
2850 @Override
2851 public NavigableSet<K> subSet(
2852 K fromElement,
2853 boolean fromInclusive,
2854 K toElement,
2855 boolean toInclusive) {
2856 return map().subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet();
2857 }
2858
2859 @Override
2860 public NavigableSet<K> headSet(K toElement, boolean inclusive) {
2861 return map().headMap(toElement, inclusive).navigableKeySet();
2862 }
2863
2864 @Override
2865 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
2866 return map().tailMap(fromElement, inclusive).navigableKeySet();
2867 }
2868
2869 @Override
2870 public SortedSet<K> subSet(K fromElement, K toElement) {
2871 return subSet(fromElement, true, toElement, false);
2872 }
2873
2874 @Override
2875 public SortedSet<K> headSet(K toElement) {
2876 return headSet(toElement, false);
2877 }
2878
2879 @Override
2880 public SortedSet<K> tailSet(K fromElement) {
2881 return tailSet(fromElement, true);
2882 }
2883 }
2884
2885 static <K, V> Iterator<V> valueIterator(Iterator<Entry<K, V>> entryIterator) {
2886 return new TransformedIterator<Entry<K, V>, V>(entryIterator) {
2887 @Override
2888 V transform(Entry<K, V> entry) {
2889 return entry.getValue();
2890 }
2891 };
2892 }
2893
2894 static <K, V> UnmodifiableIterator<V> valueIterator(
2895 final UnmodifiableIterator<Entry<K, V>> entryIterator) {
2896 return new UnmodifiableIterator<V>() {
2897 @Override
2898 public boolean hasNext() {
2899 return entryIterator.hasNext();
2900 }
2901
2902 @Override
2903 public V next() {
2904 return entryIterator.next().getValue();
2905 }
2906 };
2907 }
2908
2909 abstract static class Values<K, V> extends AbstractCollection<V> {
2910 abstract Map<K, V> map();
2911
2912 @Override public Iterator<V> iterator() {
2913 return valueIterator(map().entrySet().iterator());
2914 }
2915
2916 @Override public boolean remove(Object o) {
2917 try {
2918 return super.remove(o);
2919 } catch (UnsupportedOperationException e) {
2920 for (Entry<K, V> entry : map().entrySet()) {
2921 if (Objects.equal(o, entry.getValue())) {
2922 map().remove(entry.getKey());
2923 return true;
2924 }
2925 }
2926 return false;
2927 }
2928 }
2929
2930 @Override public boolean removeAll(Collection<?> c) {
2931 try {
2932 return super.removeAll(checkNotNull(c));
2933 } catch (UnsupportedOperationException e) {
2934 Set<K> toRemove = Sets.newHashSet();
2935 for (Entry<K, V> entry : map().entrySet()) {
2936 if (c.contains(entry.getValue())) {
2937 toRemove.add(entry.getKey());
2938 }
2939 }
2940 return map().keySet().removeAll(toRemove);
2941 }
2942 }
2943
2944 @Override public boolean retainAll(Collection<?> c) {
2945 try {
2946 return super.retainAll(checkNotNull(c));
2947 } catch (UnsupportedOperationException e) {
2948 Set<K> toRetain = Sets.newHashSet();
2949 for (Entry<K, V> entry : map().entrySet()) {
2950 if (c.contains(entry.getValue())) {
2951 toRetain.add(entry.getKey());
2952 }
2953 }
2954 return map().keySet().retainAll(toRetain);
2955 }
2956 }
2957
2958 @Override public int size() {
2959 return map().size();
2960 }
2961
2962 @Override public boolean isEmpty() {
2963 return map().isEmpty();
2964 }
2965
2966 @Override public boolean contains(@Nullable Object o) {
2967 return map().containsValue(o);
2968 }
2969
2970 @Override public void clear() {
2971 map().clear();
2972 }
2973 }
2974
2975 abstract static class EntrySet<K, V>
2976 extends Sets.ImprovedAbstractSet<Entry<K, V>> {
2977 abstract Map<K, V> map();
2978
2979 @Override public int size() {
2980 return map().size();
2981 }
2982
2983 @Override public void clear() {
2984 map().clear();
2985 }
2986
2987 @Override public boolean contains(Object o) {
2988 if (o instanceof Entry) {
2989 Entry<?, ?> entry = (Entry<?, ?>) o;
2990 Object key = entry.getKey();
2991 V value = map().get(key);
2992 return Objects.equal(value, entry.getValue())
2993 && (value != null || map().containsKey(key));
2994 }
2995 return false;
2996 }
2997
2998 @Override public boolean isEmpty() {
2999 return map().isEmpty();
3000 }
3001
3002 @Override public boolean remove(Object o) {
3003 if (contains(o)) {
3004 Entry<?, ?> entry = (Entry<?, ?>) o;
3005 return map().keySet().remove(entry.getKey());
3006 }
3007 return false;
3008 }
3009
3010 @Override public boolean removeAll(Collection<?> c) {
3011 try {
3012 return super.removeAll(checkNotNull(c));
3013 } catch (UnsupportedOperationException e) {
3014 // if the iterators don't support remove
3015 boolean changed = true;
3016 for (Object o : c) {
3017 changed |= remove(o);
3018 }
3019 return changed;
3020 }
3021 }
3022
3023 @Override public boolean retainAll(Collection<?> c) {
3024 try {
3025 return super.retainAll(checkNotNull(c));
3026 } catch (UnsupportedOperationException e) {
3027 // if the iterators don't support remove
3028 Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size());
3029 for (Object o : c) {
3030 if (contains(o)) {
3031 Entry<?, ?> entry = (Entry<?, ?>) o;
3032 keys.add(entry.getKey());
3033 }
3034 }
3035 return map().keySet().retainAll(keys);
3036 }
3037 }
3038 }
3039
3040 @GwtIncompatible("NavigableMap")
3041 abstract static class DescendingMap<K, V> extends ForwardingMap<K, V>
3042 implements NavigableMap<K, V> {
3043
3044 abstract NavigableMap<K, V> forward();
3045
3046 @Override
3047 protected final Map<K, V> delegate() {
3048 return forward();
3049 }
3050
3051 private transient Comparator<? super K> comparator;
3052
3053 @SuppressWarnings("unchecked")
3054 @Override
3055 public Comparator<? super K> comparator() {
3056 Comparator<? super K> result = comparator;
3057 if (result == null) {
3058 Comparator<? super K> forwardCmp = forward().comparator();
3059 if (forwardCmp == null) {
3060 forwardCmp = (Comparator) Ordering.natural();
3061 }
3062 result = comparator = reverse(forwardCmp);
3063 }
3064 return result;
3065 }
3066
3067 // If we inline this, we get a javac error.
3068 private static <T> Ordering<T> reverse(Comparator<T> forward) {
3069 return Ordering.from(forward).reverse();
3070 }
3071
3072 @Override
3073 public K firstKey() {
3074 return forward().lastKey();
3075 }
3076
3077 @Override
3078 public K lastKey() {
3079 return forward().firstKey();
3080 }
3081
3082 @Override
3083 public Entry<K, V> lowerEntry(K key) {
3084 return forward().higherEntry(key);
3085 }
3086
3087 @Override
3088 public K lowerKey(K key) {
3089 return forward().higherKey(key);
3090 }
3091
3092 @Override
3093 public Entry<K, V> floorEntry(K key) {
3094 return forward().ceilingEntry(key);
3095 }
3096
3097 @Override
3098 public K floorKey(K key) {
3099 return forward().ceilingKey(key);
3100 }
3101
3102 @Override
3103 public Entry<K, V> ceilingEntry(K key) {
3104 return forward().floorEntry(key);
3105 }
3106
3107 @Override
3108 public K ceilingKey(K key) {
3109 return forward().floorKey(key);
3110 }
3111
3112 @Override
3113 public Entry<K, V> higherEntry(K key) {
3114 return forward().lowerEntry(key);
3115 }
3116
3117 @Override
3118 public K higherKey(K key) {
3119 return forward().lowerKey(key);
3120 }
3121
3122 @Override
3123 public Entry<K, V> firstEntry() {
3124 return forward().lastEntry();
3125 }
3126
3127 @Override
3128 public Entry<K, V> lastEntry() {
3129 return forward().firstEntry();
3130 }
3131
3132 @Override
3133 public Entry<K, V> pollFirstEntry() {
3134 return forward().pollLastEntry();
3135 }
3136
3137 @Override
3138 public Entry<K, V> pollLastEntry() {
3139 return forward().pollFirstEntry();
3140 }
3141
3142 @Override
3143 public NavigableMap<K, V> descendingMap() {
3144 return forward();
3145 }
3146
3147 private transient Set<Entry<K, V>> entrySet;
3148
3149 @Override
3150 public Set<Entry<K, V>> entrySet() {
3151 Set<Entry<K, V>> result = entrySet;
3152 return (result == null) ? entrySet = createEntrySet() : result;
3153 }
3154
3155 abstract Iterator<Entry<K, V>> entryIterator();
3156
3157 Set<Entry<K, V>> createEntrySet() {
3158 return new EntrySet<K, V>() {
3159
3160 @Override
3161 Map<K, V> map() {
3162 return DescendingMap.this;
3163 }
3164
3165 @Override
3166 public Iterator<Entry<K, V>> iterator() {
3167 return entryIterator();
3168 }
3169 };
3170 }
3171
3172 @Override
3173 public Set<K> keySet() {
3174 return navigableKeySet();
3175 }
3176
3177 private transient NavigableSet<K> navigableKeySet;
3178
3179 @Override
3180 public NavigableSet<K> navigableKeySet() {
3181 NavigableSet<K> result = navigableKeySet;
3182 if (result == null) {
3183 result = navigableKeySet = new NavigableKeySet<K, V>() {
3184 @Override
3185 NavigableMap<K, V> map() {
3186 return DescendingMap.this;
3187 }
3188 };
3189 }
3190 return result;
3191 }
3192
3193 @Override
3194 public NavigableSet<K> descendingKeySet() {
3195 return forward().navigableKeySet();
3196 }
3197
3198 @Override
3199 public
3200 NavigableMap<K, V>
3201 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
3202 return forward().subMap(toKey, toInclusive, fromKey, fromInclusive).descendingMap();
3203 }
3204
3205 @Override
3206 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
3207 return forward().tailMap(toKey, inclusive).descendingMap();
3208 }
3209
3210 @Override
3211 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
3212 return forward().headMap(fromKey, inclusive).descendingMap();
3213 }
3214
3215 @Override
3216 public SortedMap<K, V> subMap(K fromKey, K toKey) {
3217 return subMap(fromKey, true, toKey, false);
3218 }
3219
3220 @Override
3221 public SortedMap<K, V> headMap(K toKey) {
3222 return headMap(toKey, false);
3223 }
3224
3225 @Override
3226 public SortedMap<K, V> tailMap(K fromKey) {
3227 return tailMap(fromKey, true);
3228 }
3229
3230 @Override
3231 public Collection<V> values() {
3232 return new Values<K, V>() {
3233 @Override
3234 Map<K, V> map() {
3235 return DescendingMap.this;
3236 }
3237 };
3238 }
3239 }
3240 }