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