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