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