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