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