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