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