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