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