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