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