001/* 002 * Copyright (C) 2009 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.collect.CollectPreconditions.checkEntryNotNull; 022import static com.google.common.collect.Maps.keyOrNull; 023 024import com.google.common.annotations.Beta; 025import com.google.common.annotations.GwtCompatible; 026import com.google.errorprone.annotations.CanIgnoreReturnValue; 027import java.util.AbstractMap; 028import java.util.Arrays; 029import java.util.Comparator; 030import java.util.Map; 031import java.util.NavigableMap; 032import java.util.SortedMap; 033import java.util.Spliterator; 034import java.util.TreeMap; 035import java.util.function.BiConsumer; 036import java.util.function.BinaryOperator; 037import java.util.function.Consumer; 038import java.util.function.Function; 039import java.util.stream.Collector; 040import java.util.stream.Collectors; 041import org.checkerframework.checker.nullness.qual.Nullable; 042 043/** 044 * A {@link NavigableMap} whose contents will never change, with many other important properties 045 * detailed at {@link ImmutableCollection}. 046 * 047 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link 048 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with 049 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero 050 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will 051 * not correctly obey its specification. 052 * 053 * <p>See the Guava User Guide article on <a href= 054 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>. 055 * 056 * @author Jared Levy 057 * @author Louis Wasserman 058 * @since 2.0 (implements {@code NavigableMap} since 12.0) 059 */ 060@GwtCompatible(serializable = true, emulated = true) 061public final class ImmutableSortedMap<K, V> extends ImmutableSortedMapFauxverideShim<K, V> 062 implements NavigableMap<K, V> { 063 /** 064 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose 065 * keys and values are the result of applying the provided mapping functions to the input 066 * elements. The generated map is sorted by the specified comparator. 067 * 068 * <p>If the mapped keys contain duplicates (according to the specified comparator), an {@code 069 * IllegalArgumentException} is thrown when the collection operation is performed. (This differs 070 * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which 071 * throws an {@code IllegalStateException}.) 072 * 073 * @since 21.0 074 */ 075 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap( 076 Comparator<? super K> comparator, 077 Function<? super T, ? extends K> keyFunction, 078 Function<? super T, ? extends V> valueFunction) { 079 return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction); 080 } 081 082 /** 083 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose 084 * keys and values are the result of applying the provided mapping functions to the input 085 * elements. 086 * 087 * <p>If the mapped keys contain duplicates (according to the comparator), the the values are 088 * merged using the specified merging function. Entries will appear in the encounter order of the 089 * first occurrence of the key. 090 * 091 * @since 21.0 092 */ 093 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap( 094 Comparator<? super K> comparator, 095 Function<? super T, ? extends K> keyFunction, 096 Function<? super T, ? extends V> valueFunction, 097 BinaryOperator<V> mergeFunction) { 098 checkNotNull(comparator); 099 checkNotNull(keyFunction); 100 checkNotNull(valueFunction); 101 checkNotNull(mergeFunction); 102 return Collectors.collectingAndThen( 103 Collectors.toMap( 104 keyFunction, valueFunction, mergeFunction, () -> new TreeMap<K, V>(comparator)), 105 ImmutableSortedMap::copyOfSorted); 106 } 107 108 /* 109 * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and 110 * uses less memory than TreeMap; then say so in the class Javadoc. 111 */ 112 private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural(); 113 114 private static final ImmutableSortedMap<Comparable, Object> NATURAL_EMPTY_MAP = 115 new ImmutableSortedMap<>( 116 ImmutableSortedSet.emptySet(Ordering.natural()), ImmutableList.<Object>of()); 117 118 static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) { 119 if (Ordering.natural().equals(comparator)) { 120 return of(); 121 } else { 122 return new ImmutableSortedMap<>( 123 ImmutableSortedSet.emptySet(comparator), ImmutableList.<V>of()); 124 } 125 } 126 127 /** Returns the empty sorted map. */ 128 @SuppressWarnings("unchecked") 129 // unsafe, comparator() returns a comparator on the specified type 130 // TODO(kevinb): evaluate whether or not of().comparator() should return null 131 public static <K, V> ImmutableSortedMap<K, V> of() { 132 return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 133 } 134 135 /** Returns an immutable map containing a single entry. */ 136 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1) { 137 return of(Ordering.natural(), k1, v1); 138 } 139 140 /** Returns an immutable map containing a single entry. */ 141 private static <K, V> ImmutableSortedMap<K, V> of(Comparator<? super K> comparator, K k1, V v1) { 142 return new ImmutableSortedMap<>( 143 new RegularImmutableSortedSet<K>(ImmutableList.of(k1), checkNotNull(comparator)), 144 ImmutableList.of(v1)); 145 } 146 147 /** 148 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of 149 * their keys. 150 * 151 * @throws IllegalArgumentException if the two keys are equal according to their natural ordering 152 */ 153 @SuppressWarnings("unchecked") 154 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 155 K k1, V v1, K k2, V v2) { 156 return ofEntries(entryOf(k1, v1), entryOf(k2, v2)); 157 } 158 159 /** 160 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of 161 * their keys. 162 * 163 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering 164 */ 165 @SuppressWarnings("unchecked") 166 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 167 K k1, V v1, K k2, V v2, K k3, V v3) { 168 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3)); 169 } 170 171 /** 172 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of 173 * their keys. 174 * 175 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering 176 */ 177 @SuppressWarnings("unchecked") 178 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 179 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 180 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4)); 181 } 182 183 /** 184 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of 185 * their keys. 186 * 187 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering 188 */ 189 @SuppressWarnings("unchecked") 190 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 191 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 192 return ofEntries( 193 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5)); 194 } 195 196 private static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> ofEntries( 197 Entry<K, V>... entries) { 198 return fromEntries(Ordering.natural(), false, entries, entries.length); 199 } 200 201 /** 202 * Returns an immutable map containing the same entries as {@code map}, sorted by the natural 203 * ordering of the keys. 204 * 205 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 206 * safe to do so. The exact circumstances under which a copy will or will not be performed are 207 * undocumented and subject to change. 208 * 209 * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually 210 * comparable. 211 * 212 * @throws ClassCastException if the keys in {@code map} are not mutually comparable 213 * @throws NullPointerException if any key or value in {@code map} is null 214 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering 215 */ 216 public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 217 // Hack around K not being a subtype of Comparable. 218 // Unsafe, see ImmutableSortedSetFauxverideShim. 219 @SuppressWarnings("unchecked") 220 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER; 221 return copyOfInternal(map, naturalOrder); 222 } 223 224 /** 225 * Returns an immutable map containing the same entries as {@code map}, with keys sorted by the 226 * provided comparator. 227 * 228 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 229 * safe to do so. The exact circumstances under which a copy will or will not be performed are 230 * undocumented and subject to change. 231 * 232 * @throws NullPointerException if any key or value in {@code map} is null 233 * @throws IllegalArgumentException if any two keys are equal according to the comparator 234 */ 235 public static <K, V> ImmutableSortedMap<K, V> copyOf( 236 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 237 return copyOfInternal(map, checkNotNull(comparator)); 238 } 239 240 /** 241 * Returns an immutable map containing the given entries, with keys sorted by the provided 242 * comparator. 243 * 244 * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually 245 * comparable. 246 * 247 * @throws NullPointerException if any key or value in {@code map} is null 248 * @throws IllegalArgumentException if any two keys are equal according to the comparator 249 * @since 19.0 250 */ 251 @Beta 252 public static <K, V> ImmutableSortedMap<K, V> copyOf( 253 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 254 // Hack around K not being a subtype of Comparable. 255 // Unsafe, see ImmutableSortedSetFauxverideShim. 256 @SuppressWarnings("unchecked") 257 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER; 258 return copyOf(entries, naturalOrder); 259 } 260 261 /** 262 * Returns an immutable map containing the given entries, with keys sorted by the provided 263 * comparator. 264 * 265 * @throws NullPointerException if any key or value in {@code map} is null 266 * @throws IllegalArgumentException if any two keys are equal according to the comparator 267 * @since 19.0 268 */ 269 @Beta 270 public static <K, V> ImmutableSortedMap<K, V> copyOf( 271 Iterable<? extends Entry<? extends K, ? extends V>> entries, 272 Comparator<? super K> comparator) { 273 return fromEntries(checkNotNull(comparator), false, entries); 274 } 275 276 /** 277 * Returns an immutable map containing the same entries as the provided sorted map, with the same 278 * ordering. 279 * 280 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 281 * safe to do so. The exact circumstances under which a copy will or will not be performed are 282 * undocumented and subject to change. 283 * 284 * @throws NullPointerException if any key or value in {@code map} is null 285 */ 286 @SuppressWarnings("unchecked") 287 public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(SortedMap<K, ? extends V> map) { 288 Comparator<? super K> comparator = map.comparator(); 289 if (comparator == null) { 290 // If map has a null comparator, the keys should have a natural ordering, 291 // even though K doesn't explicitly implement Comparable. 292 comparator = (Comparator<? super K>) NATURAL_ORDER; 293 } 294 if (map instanceof ImmutableSortedMap) { 295 // TODO(kevinb): Prove that this cast is safe, even though 296 // Collections.unmodifiableSortedMap requires the same key type. 297 @SuppressWarnings("unchecked") 298 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 299 if (!kvMap.isPartialView()) { 300 return kvMap; 301 } 302 } 303 return fromEntries(comparator, true, map.entrySet()); 304 } 305 306 private static <K, V> ImmutableSortedMap<K, V> copyOfInternal( 307 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 308 boolean sameComparator = false; 309 if (map instanceof SortedMap) { 310 SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map; 311 Comparator<?> comparator2 = sortedMap.comparator(); 312 sameComparator = 313 (comparator2 == null) ? comparator == NATURAL_ORDER : comparator.equals(comparator2); 314 } 315 316 if (sameComparator && (map instanceof ImmutableSortedMap)) { 317 // TODO(kevinb): Prove that this cast is safe, even though 318 // Collections.unmodifiableSortedMap requires the same key type. 319 @SuppressWarnings("unchecked") 320 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 321 if (!kvMap.isPartialView()) { 322 return kvMap; 323 } 324 } 325 return fromEntries(comparator, sameComparator, map.entrySet()); 326 } 327 328 /** 329 * Accepts a collection of possibly-null entries. If {@code sameComparator}, then it is assumed 330 * that they do not need to be sorted or checked for dupes. 331 */ 332 private static <K, V> ImmutableSortedMap<K, V> fromEntries( 333 Comparator<? super K> comparator, 334 boolean sameComparator, 335 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 336 // "adding" type params to an array of a raw type should be safe as 337 // long as no one can ever cast that same array instance back to a 338 // raw type. 339 @SuppressWarnings("unchecked") 340 Entry<K, V>[] entryArray = (Entry[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 341 return fromEntries(comparator, sameComparator, entryArray, entryArray.length); 342 } 343 344 private static <K, V> ImmutableSortedMap<K, V> fromEntries( 345 final Comparator<? super K> comparator, 346 boolean sameComparator, 347 Entry<K, V>[] entryArray, 348 int size) { 349 switch (size) { 350 case 0: 351 return emptyMap(comparator); 352 case 1: 353 return ImmutableSortedMap.<K, V>of( 354 comparator, entryArray[0].getKey(), entryArray[0].getValue()); 355 default: 356 Object[] keys = new Object[size]; 357 Object[] values = new Object[size]; 358 if (sameComparator) { 359 // Need to check for nulls, but don't need to sort or validate. 360 for (int i = 0; i < size; i++) { 361 Object key = entryArray[i].getKey(); 362 Object value = entryArray[i].getValue(); 363 checkEntryNotNull(key, value); 364 keys[i] = key; 365 values[i] = value; 366 } 367 } else { 368 // Need to sort and check for nulls and dupes. 369 // Inline the Comparator implementation rather than transforming with a Function 370 // to save code size. 371 Arrays.sort( 372 entryArray, 373 0, 374 size, 375 new Comparator<Entry<K, V>>() { 376 @Override 377 public int compare(Entry<K, V> e1, Entry<K, V> e2) { 378 return comparator.compare(e1.getKey(), e2.getKey()); 379 } 380 }); 381 K prevKey = entryArray[0].getKey(); 382 keys[0] = prevKey; 383 values[0] = entryArray[0].getValue(); 384 checkEntryNotNull(keys[0], values[0]); 385 for (int i = 1; i < size; i++) { 386 K key = entryArray[i].getKey(); 387 V value = entryArray[i].getValue(); 388 checkEntryNotNull(key, value); 389 keys[i] = key; 390 values[i] = value; 391 checkNoConflict( 392 comparator.compare(prevKey, key) != 0, "key", entryArray[i - 1], entryArray[i]); 393 prevKey = key; 394 } 395 } 396 return new ImmutableSortedMap<>( 397 new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator), 398 new RegularImmutableList<V>(values)); 399 } 400 } 401 402 /** 403 * Returns a builder that creates immutable sorted maps whose keys are ordered by their natural 404 * ordering. The sorted maps use {@link Ordering#natural()} as the comparator. 405 */ 406 public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() { 407 return new Builder<>(Ordering.natural()); 408 } 409 410 /** 411 * Returns a builder that creates immutable sorted maps with an explicit comparator. If the 412 * comparator has a more general type than the map's keys, such as creating a {@code 413 * SortedMap<Integer, String>} with a {@code Comparator<Number>}, use the {@link Builder} 414 * constructor instead. 415 * 416 * @throws NullPointerException if {@code comparator} is null 417 */ 418 public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) { 419 return new Builder<>(comparator); 420 } 421 422 /** 423 * Returns a builder that creates immutable sorted maps whose keys are ordered by the reverse of 424 * their natural ordering. 425 */ 426 public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() { 427 return new Builder<>(Ordering.natural().reverse()); 428 } 429 430 /** 431 * A builder for creating immutable sorted map instances, especially {@code public static final} 432 * maps ("constant maps"). Example: 433 * 434 * <pre>{@code 435 * static final ImmutableSortedMap<Integer, String> INT_TO_WORD = 436 * new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural()) 437 * .put(1, "one") 438 * .put(2, "two") 439 * .put(3, "three") 440 * .build(); 441 * }</pre> 442 * 443 * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} methods are even 444 * more convenient. 445 * 446 * <p>Builder instances can be reused - it is safe to call {@link #build} multiple times to build 447 * multiple maps in series. Each map is a superset of the maps created before it. 448 * 449 * @since 2.0 450 */ 451 public static class Builder<K, V> extends ImmutableMap.Builder<K, V> { 452 private final Comparator<? super K> comparator; 453 454 /** 455 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 456 * ImmutableSortedMap#orderedBy}. 457 */ 458 @SuppressWarnings("unchecked") 459 public Builder(Comparator<? super K> comparator) { 460 this.comparator = checkNotNull(comparator); 461 } 462 463 /** 464 * Associates {@code key} with {@code value} in the built map. Duplicate keys, according to the 465 * comparator (which might be the keys' natural order), are not allowed, and will cause {@link 466 * #build} to fail. 467 */ 468 @CanIgnoreReturnValue 469 @Override 470 public Builder<K, V> put(K key, V value) { 471 super.put(key, value); 472 return this; 473 } 474 475 /** 476 * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys, 477 * according to the comparator (which might be the keys' natural order), are not allowed, and 478 * will cause {@link #build} to fail. 479 * 480 * @since 11.0 481 */ 482 @CanIgnoreReturnValue 483 @Override 484 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 485 super.put(entry); 486 return this; 487 } 488 489 /** 490 * Associates all of the given map's keys and values in the built map. Duplicate keys, according 491 * to the comparator (which might be the keys' natural order), are not allowed, and will cause 492 * {@link #build} to fail. 493 * 494 * @throws NullPointerException if any key or value in {@code map} is null 495 */ 496 @CanIgnoreReturnValue 497 @Override 498 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 499 super.putAll(map); 500 return this; 501 } 502 503 /** 504 * Adds all the given entries to the built map. Duplicate keys, according to the comparator 505 * (which might be the keys' natural order), are not allowed, and will cause {@link #build} to 506 * fail. 507 * 508 * @throws NullPointerException if any key, value, or entry is null 509 * @since 19.0 510 */ 511 @CanIgnoreReturnValue 512 @Beta 513 @Override 514 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 515 super.putAll(entries); 516 return this; 517 } 518 519 /** 520 * Throws an {@code UnsupportedOperationException}. 521 * 522 * @since 19.0 523 * @deprecated Unsupported by ImmutableSortedMap.Builder. 524 */ 525 @CanIgnoreReturnValue 526 @Beta 527 @Override 528 @Deprecated 529 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) { 530 throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder"); 531 } 532 533 @Override 534 Builder<K, V> combine(ImmutableMap.Builder<K, V> other) { 535 super.combine(other); 536 return this; 537 } 538 539 /** 540 * Returns a newly-created immutable sorted map. 541 * 542 * @throws IllegalArgumentException if any two keys are equal according to the comparator (which 543 * might be the keys' natural order) 544 */ 545 @Override 546 public ImmutableSortedMap<K, V> build() { 547 switch (size) { 548 case 0: 549 return emptyMap(comparator); 550 case 1: 551 return of(comparator, entries[0].getKey(), entries[0].getValue()); 552 default: 553 return fromEntries(comparator, false, entries, size); 554 } 555 } 556 } 557 558 private final transient RegularImmutableSortedSet<K> keySet; 559 private final transient ImmutableList<V> valueList; 560 private transient ImmutableSortedMap<K, V> descendingMap; 561 562 ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) { 563 this(keySet, valueList, null); 564 } 565 566 ImmutableSortedMap( 567 RegularImmutableSortedSet<K> keySet, 568 ImmutableList<V> valueList, 569 ImmutableSortedMap<K, V> descendingMap) { 570 this.keySet = keySet; 571 this.valueList = valueList; 572 this.descendingMap = descendingMap; 573 } 574 575 @Override 576 public int size() { 577 return valueList.size(); 578 } 579 580 @Override 581 public void forEach(BiConsumer<? super K, ? super V> action) { 582 checkNotNull(action); 583 ImmutableList<K> keyList = keySet.asList(); 584 for (int i = 0; i < size(); i++) { 585 action.accept(keyList.get(i), valueList.get(i)); 586 } 587 } 588 589 @Override 590 public V get(@Nullable Object key) { 591 int index = keySet.indexOf(key); 592 return (index == -1) ? null : valueList.get(index); 593 } 594 595 @Override 596 boolean isPartialView() { 597 return keySet.isPartialView() || valueList.isPartialView(); 598 } 599 600 /** Returns an immutable set of the mappings in this map, sorted by the key ordering. */ 601 @Override 602 public ImmutableSet<Entry<K, V>> entrySet() { 603 return super.entrySet(); 604 } 605 606 @Override 607 ImmutableSet<Entry<K, V>> createEntrySet() { 608 class EntrySet extends ImmutableMapEntrySet<K, V> { 609 @Override 610 public UnmodifiableIterator<Entry<K, V>> iterator() { 611 return asList().iterator(); 612 } 613 614 @Override 615 public Spliterator<Entry<K, V>> spliterator() { 616 return asList().spliterator(); 617 } 618 619 @Override 620 public void forEach(Consumer<? super Entry<K, V>> action) { 621 asList().forEach(action); 622 } 623 624 @Override 625 ImmutableList<Entry<K, V>> createAsList() { 626 return new ImmutableAsList<Entry<K, V>>() { 627 @Override 628 public Entry<K, V> get(int index) { 629 return new AbstractMap.SimpleImmutableEntry<>( 630 keySet.asList().get(index), valueList.get(index)); 631 } 632 633 @Override 634 public Spliterator<Entry<K, V>> spliterator() { 635 return CollectSpliterators.indexed( 636 size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get); 637 } 638 639 @Override 640 ImmutableCollection<Entry<K, V>> delegateCollection() { 641 return EntrySet.this; 642 } 643 }; 644 } 645 646 @Override 647 ImmutableMap<K, V> map() { 648 return ImmutableSortedMap.this; 649 } 650 } 651 return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet(); 652 } 653 654 /** Returns an immutable sorted set of the keys in this map. */ 655 @Override 656 public ImmutableSortedSet<K> keySet() { 657 return keySet; 658 } 659 660 @Override 661 ImmutableSet<K> createKeySet() { 662 throw new AssertionError("should never be called"); 663 } 664 665 /** 666 * Returns an immutable collection of the values in this map, sorted by the ordering of the 667 * corresponding keys. 668 */ 669 @Override 670 public ImmutableCollection<V> values() { 671 return valueList; 672 } 673 674 @Override 675 ImmutableCollection<V> createValues() { 676 throw new AssertionError("should never be called"); 677 } 678 679 /** 680 * Returns the comparator that orders the keys, which is {@link Ordering#natural()} when the 681 * natural ordering of the keys is used. Note that its behavior is not consistent with {@link 682 * TreeMap#comparator()}, which returns {@code null} to indicate natural ordering. 683 */ 684 @Override 685 public Comparator<? super K> comparator() { 686 return keySet().comparator(); 687 } 688 689 @Override 690 public K firstKey() { 691 return keySet().first(); 692 } 693 694 @Override 695 public K lastKey() { 696 return keySet().last(); 697 } 698 699 private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) { 700 if (fromIndex == 0 && toIndex == size()) { 701 return this; 702 } else if (fromIndex == toIndex) { 703 return emptyMap(comparator()); 704 } else { 705 return new ImmutableSortedMap<>( 706 keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex)); 707 } 708 } 709 710 /** 711 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less 712 * than {@code toKey}. 713 * 714 * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an 715 * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code 716 * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps 717 * the original {@code toKey}. 718 */ 719 @Override 720 public ImmutableSortedMap<K, V> headMap(K toKey) { 721 return headMap(toKey, false); 722 } 723 724 /** 725 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less 726 * than (or equal to, if {@code inclusive}) {@code toKey}. 727 * 728 * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an 729 * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code 730 * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps 731 * the original {@code toKey}. 732 * 733 * @since 12.0 734 */ 735 @Override 736 public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) { 737 return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive)); 738 } 739 740 /** 741 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges 742 * from {@code fromKey}, inclusive, to {@code toKey}, exclusive. 743 * 744 * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link 745 * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}. 746 * However, this method doesn't throw an exception in that situation, but instead keeps the 747 * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of 748 * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}. 749 */ 750 @Override 751 public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) { 752 return subMap(fromKey, true, toKey, false); 753 } 754 755 /** 756 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges 757 * from {@code fromKey} to {@code toKey}, inclusive or exclusive as indicated by the boolean 758 * flags. 759 * 760 * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link 761 * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}. 762 * However, this method doesn't throw an exception in that situation, but instead keeps the 763 * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of 764 * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}. 765 * 766 * @since 12.0 767 */ 768 @Override 769 public ImmutableSortedMap<K, V> subMap( 770 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 771 checkNotNull(fromKey); 772 checkNotNull(toKey); 773 checkArgument( 774 comparator().compare(fromKey, toKey) <= 0, 775 "expected fromKey <= toKey but %s > %s", 776 fromKey, 777 toKey); 778 return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive); 779 } 780 781 /** 782 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are 783 * greater than or equals to {@code fromKey}. 784 * 785 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an 786 * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code 787 * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps 788 * the original {@code fromKey}. 789 */ 790 @Override 791 public ImmutableSortedMap<K, V> tailMap(K fromKey) { 792 return tailMap(fromKey, true); 793 } 794 795 /** 796 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are 797 * greater than (or equal to, if {@code inclusive}) {@code fromKey}. 798 * 799 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an 800 * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code 801 * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps 802 * the original {@code fromKey}. 803 * 804 * @since 12.0 805 */ 806 @Override 807 public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) { 808 return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size()); 809 } 810 811 @Override 812 public Entry<K, V> lowerEntry(K key) { 813 return headMap(key, false).lastEntry(); 814 } 815 816 @Override 817 public K lowerKey(K key) { 818 return keyOrNull(lowerEntry(key)); 819 } 820 821 @Override 822 public Entry<K, V> floorEntry(K key) { 823 return headMap(key, true).lastEntry(); 824 } 825 826 @Override 827 public K floorKey(K key) { 828 return keyOrNull(floorEntry(key)); 829 } 830 831 @Override 832 public Entry<K, V> ceilingEntry(K key) { 833 return tailMap(key, true).firstEntry(); 834 } 835 836 @Override 837 public K ceilingKey(K key) { 838 return keyOrNull(ceilingEntry(key)); 839 } 840 841 @Override 842 public Entry<K, V> higherEntry(K key) { 843 return tailMap(key, false).firstEntry(); 844 } 845 846 @Override 847 public K higherKey(K key) { 848 return keyOrNull(higherEntry(key)); 849 } 850 851 @Override 852 public Entry<K, V> firstEntry() { 853 return isEmpty() ? null : entrySet().asList().get(0); 854 } 855 856 @Override 857 public Entry<K, V> lastEntry() { 858 return isEmpty() ? null : entrySet().asList().get(size() - 1); 859 } 860 861 /** 862 * Guaranteed to throw an exception and leave the map unmodified. 863 * 864 * @throws UnsupportedOperationException always 865 * @deprecated Unsupported operation. 866 */ 867 @CanIgnoreReturnValue 868 @Deprecated 869 @Override 870 public final Entry<K, V> pollFirstEntry() { 871 throw new UnsupportedOperationException(); 872 } 873 874 /** 875 * Guaranteed to throw an exception and leave the map unmodified. 876 * 877 * @throws UnsupportedOperationException always 878 * @deprecated Unsupported operation. 879 */ 880 @CanIgnoreReturnValue 881 @Deprecated 882 @Override 883 public final Entry<K, V> pollLastEntry() { 884 throw new UnsupportedOperationException(); 885 } 886 887 @Override 888 public ImmutableSortedMap<K, V> descendingMap() { 889 // TODO(kevinb): the descendingMap is never actually cached at all. Either it should be or the 890 // code below simplified. 891 ImmutableSortedMap<K, V> result = descendingMap; 892 if (result == null) { 893 if (isEmpty()) { 894 return result = emptyMap(Ordering.from(comparator()).reverse()); 895 } else { 896 return result = 897 new ImmutableSortedMap<>( 898 (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this); 899 } 900 } 901 return result; 902 } 903 904 @Override 905 public ImmutableSortedSet<K> navigableKeySet() { 906 return keySet; 907 } 908 909 @Override 910 public ImmutableSortedSet<K> descendingKeySet() { 911 return keySet.descendingSet(); 912 } 913 914 /** 915 * Serialized type for all ImmutableSortedMap instances. It captures the logical contents and they 916 * are reconstructed using public factory methods. This ensures that the implementation types 917 * remain as implementation details. 918 */ 919 private static class SerializedForm extends ImmutableMap.SerializedForm { 920 private final Comparator<Object> comparator; 921 922 @SuppressWarnings("unchecked") 923 SerializedForm(ImmutableSortedMap<?, ?> sortedMap) { 924 super(sortedMap); 925 comparator = (Comparator<Object>) sortedMap.comparator(); 926 } 927 928 @Override 929 Object readResolve() { 930 Builder<Object, Object> builder = new Builder<>(comparator); 931 return createMap(builder); 932 } 933 934 private static final long serialVersionUID = 0; 935 } 936 937 @Override 938 Object writeReplace() { 939 return new SerializedForm(this); 940 } 941 942 // This class is never actually serialized directly, but we have to make the 943 // warning go away (and suppressing would suppress for all nested classes too) 944 private static final long serialVersionUID = 0; 945}