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