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