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