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