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