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