001/* 002 * Copyright (C) 2008 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.ObjectArrays.checkElementsNotNull; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.GwtIncompatible; 025import com.google.errorprone.annotations.CanIgnoreReturnValue; 026import com.google.errorprone.annotations.concurrent.LazyInit; 027import java.io.InvalidObjectException; 028import java.io.ObjectInputStream; 029import java.io.Serializable; 030import java.util.Arrays; 031import java.util.Collection; 032import java.util.Collections; 033import java.util.Comparator; 034import java.util.Iterator; 035import java.util.NavigableSet; 036import java.util.SortedSet; 037import java.util.Spliterator; 038import java.util.Spliterators; 039import java.util.function.Consumer; 040import java.util.stream.Collector; 041import org.checkerframework.checker.nullness.qual.Nullable; 042 043/** 044 * A {@link NavigableSet} 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 051 * collection will 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 NavigableSet} since 12.0) 059 */ 060// TODO(benyu): benchmark and optimize all creation paths, which are a mess now 061@GwtCompatible(serializable = true, emulated = true) 062@SuppressWarnings("serial") // we're overriding default serialization 063public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E> 064 implements NavigableSet<E>, SortedIterable<E> { 065 static final int SPLITERATOR_CHARACTERISTICS = 066 ImmutableSet.SPLITERATOR_CHARACTERISTICS | Spliterator.SORTED; 067 068 /** 069 * Returns a {@code Collector} that accumulates the input elements into a new {@code 070 * ImmutableSortedSet}, ordered by the specified comparator. 071 * 072 * <p>If the elements contain duplicates (according to the comparator), only the first duplicate 073 * in encounter order will appear in the result. 074 * 075 * @since 21.0 076 */ 077 public static <E> Collector<E, ?, ImmutableSortedSet<E>> toImmutableSortedSet( 078 Comparator<? super E> comparator) { 079 return CollectCollectors.toImmutableSortedSet(comparator); 080 } 081 082 static <E> RegularImmutableSortedSet<E> emptySet(Comparator<? super E> comparator) { 083 if (Ordering.natural().equals(comparator)) { 084 return (RegularImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET; 085 } else { 086 return new RegularImmutableSortedSet<E>(ImmutableList.<E>of(), comparator); 087 } 088 } 089 090 /** Returns the empty immutable sorted set. */ 091 public static <E> ImmutableSortedSet<E> of() { 092 return (ImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET; 093 } 094 095 /** Returns an immutable sorted set containing a single element. */ 096 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E element) { 097 return new RegularImmutableSortedSet<E>(ImmutableList.of(element), Ordering.natural()); 098 } 099 100 /** 101 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 102 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 103 * one specified is included. 104 * 105 * @throws NullPointerException if any element is null 106 */ 107 @SuppressWarnings("unchecked") 108 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2) { 109 return construct(Ordering.natural(), 2, e1, e2); 110 } 111 112 /** 113 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 114 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 115 * one specified is included. 116 * 117 * @throws NullPointerException if any element is null 118 */ 119 @SuppressWarnings("unchecked") 120 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3) { 121 return construct(Ordering.natural(), 3, e1, e2, e3); 122 } 123 124 /** 125 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 126 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 127 * one specified is included. 128 * 129 * @throws NullPointerException if any element is null 130 */ 131 @SuppressWarnings("unchecked") 132 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) { 133 return construct(Ordering.natural(), 4, e1, e2, e3, e4); 134 } 135 136 /** 137 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 138 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 139 * one specified is included. 140 * 141 * @throws NullPointerException if any element is null 142 */ 143 @SuppressWarnings("unchecked") 144 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 145 E e1, E e2, E e3, E e4, E e5) { 146 return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5); 147 } 148 149 /** 150 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 151 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 152 * one specified is included. 153 * 154 * @throws NullPointerException if any element is null 155 * @since 3.0 (source-compatible since 2.0) 156 */ 157 @SuppressWarnings("unchecked") 158 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 159 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) { 160 Comparable[] contents = new Comparable[6 + remaining.length]; 161 contents[0] = e1; 162 contents[1] = e2; 163 contents[2] = e3; 164 contents[3] = e4; 165 contents[4] = e5; 166 contents[5] = e6; 167 System.arraycopy(remaining, 0, contents, 6, remaining.length); 168 return construct(Ordering.natural(), contents.length, (E[]) contents); 169 } 170 171 // TODO(kevinb): Consider factory methods that reject duplicates 172 173 /** 174 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 175 * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first 176 * one specified is included. 177 * 178 * @throws NullPointerException if any of {@code elements} is null 179 * @since 3.0 180 */ 181 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(E[] elements) { 182 return construct(Ordering.natural(), elements.length, elements.clone()); 183 } 184 185 /** 186 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 187 * When multiple elements are equivalent according to {@code compareTo()}, only the first one 188 * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator, 189 * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once. 190 * 191 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)} 192 * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s}, 193 * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>} 194 * containing one element (the given set itself). 195 * 196 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 197 * safe to do so. The exact circumstances under which a copy will or will not be performed are 198 * undocumented and subject to change. 199 * 200 * <p>This method is not type-safe, as it may be called on elements that are not mutually 201 * comparable. 202 * 203 * @throws ClassCastException if the elements are not mutually comparable 204 * @throws NullPointerException if any of {@code elements} is null 205 */ 206 public static <E> ImmutableSortedSet<E> copyOf(Iterable<? extends E> elements) { 207 // Hack around E not being a subtype of Comparable. 208 // Unsafe, see ImmutableSortedSetFauxverideShim. 209 @SuppressWarnings("unchecked") 210 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 211 return copyOf(naturalOrder, elements); 212 } 213 214 /** 215 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 216 * When multiple elements are equivalent according to {@code compareTo()}, only the first one 217 * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator, 218 * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once. 219 * 220 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)} 221 * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s}, 222 * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>} 223 * containing one element (the given set itself). 224 * 225 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} is an {@code 226 * ImmutableSortedSet}, it may be returned instead of a copy. 227 * 228 * <p>This method is not type-safe, as it may be called on elements that are not mutually 229 * comparable. 230 * 231 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent 232 * collection that is currently being modified by another thread. 233 * 234 * @throws ClassCastException if the elements are not mutually comparable 235 * @throws NullPointerException if any of {@code elements} is null 236 * @since 7.0 (source-compatible since 2.0) 237 */ 238 public static <E> ImmutableSortedSet<E> copyOf(Collection<? extends E> elements) { 239 // Hack around E not being a subtype of Comparable. 240 // Unsafe, see ImmutableSortedSetFauxverideShim. 241 @SuppressWarnings("unchecked") 242 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 243 return copyOf(naturalOrder, elements); 244 } 245 246 /** 247 * Returns an immutable sorted set containing the given elements sorted by their natural ordering. 248 * When multiple elements are equivalent according to {@code compareTo()}, only the first one 249 * specified is included. 250 * 251 * <p>This method is not type-safe, as it may be called on elements that are not mutually 252 * comparable. 253 * 254 * @throws ClassCastException if the elements are not mutually comparable 255 * @throws NullPointerException if any of {@code elements} is null 256 */ 257 public static <E> ImmutableSortedSet<E> copyOf(Iterator<? extends E> elements) { 258 // Hack around E not being a subtype of Comparable. 259 // Unsafe, see ImmutableSortedSetFauxverideShim. 260 @SuppressWarnings("unchecked") 261 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural(); 262 return copyOf(naturalOrder, elements); 263 } 264 265 /** 266 * Returns an immutable sorted set containing the given elements sorted by the given {@code 267 * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the 268 * first one specified is included. 269 * 270 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 271 */ 272 public static <E> ImmutableSortedSet<E> copyOf( 273 Comparator<? super E> comparator, Iterator<? extends E> elements) { 274 return new Builder<E>(comparator).addAll(elements).build(); 275 } 276 277 /** 278 * Returns an immutable sorted set containing the given elements sorted by the given {@code 279 * Comparator}. When multiple elements are equivalent according to {@code compare()}, only the 280 * first one specified is included. This method iterates over {@code elements} at most once. 281 * 282 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 283 * safe to do so. The exact circumstances under which a copy will or will not be performed are 284 * undocumented and subject to change. 285 * 286 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 287 */ 288 public static <E> ImmutableSortedSet<E> copyOf( 289 Comparator<? super E> comparator, Iterable<? extends E> elements) { 290 checkNotNull(comparator); 291 boolean hasSameComparator = SortedIterables.hasSameComparator(comparator, elements); 292 293 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) { 294 @SuppressWarnings("unchecked") 295 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements; 296 if (!original.isPartialView()) { 297 return original; 298 } 299 } 300 @SuppressWarnings("unchecked") // elements only contains E's; it's safe. 301 E[] array = (E[]) Iterables.toArray(elements); 302 return construct(comparator, array.length, array); 303 } 304 305 /** 306 * Returns an immutable sorted set containing the given elements sorted by the given {@code 307 * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the 308 * first one specified is included. 309 * 310 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 311 * safe to do so. The exact circumstances under which a copy will or will not be performed are 312 * undocumented and subject to change. 313 * 314 * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent 315 * collection that is currently being modified by another thread. 316 * 317 * @throws NullPointerException if {@code comparator} or any of {@code elements} is null 318 * @since 7.0 (source-compatible since 2.0) 319 */ 320 public static <E> ImmutableSortedSet<E> copyOf( 321 Comparator<? super E> comparator, Collection<? extends E> elements) { 322 return copyOf(comparator, (Iterable<? extends E>) elements); 323 } 324 325 /** 326 * Returns an immutable sorted set containing the elements of a sorted set, sorted by the same 327 * {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always uses the 328 * natural ordering of the elements. 329 * 330 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 331 * safe to do so. The exact circumstances under which a copy will or will not be performed are 332 * undocumented and subject to change. 333 * 334 * <p>This method is safe to use even when {@code sortedSet} is a synchronized or concurrent 335 * collection that is currently being modified by another thread. 336 * 337 * @throws NullPointerException if {@code sortedSet} or any of its elements is null 338 */ 339 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) { 340 Comparator<? super E> comparator = SortedIterables.comparator(sortedSet); 341 ImmutableList<E> list = ImmutableList.copyOf(sortedSet); 342 if (list.isEmpty()) { 343 return emptySet(comparator); 344 } else { 345 return new RegularImmutableSortedSet<E>(list, comparator); 346 } 347 } 348 349 /** 350 * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of {@code contents}. 351 * If {@code k} is the size of the returned {@code ImmutableSortedSet}, then the sorted unique 352 * elements are in the first {@code k} positions of {@code contents}, and {@code contents[i] == 353 * null} for {@code k <= i < n}. 354 * 355 * <p>If {@code k == contents.length}, then {@code contents} may no longer be safe for 356 * modification. 357 * 358 * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is null 359 */ 360 static <E> ImmutableSortedSet<E> construct( 361 Comparator<? super E> comparator, int n, E... contents) { 362 if (n == 0) { 363 return emptySet(comparator); 364 } 365 checkElementsNotNull(contents, n); 366 Arrays.sort(contents, 0, n, comparator); 367 int uniques = 1; 368 for (int i = 1; i < n; i++) { 369 E cur = contents[i]; 370 E prev = contents[uniques - 1]; 371 if (comparator.compare(cur, prev) != 0) { 372 contents[uniques++] = cur; 373 } 374 } 375 Arrays.fill(contents, uniques, n, null); 376 return new RegularImmutableSortedSet<E>( 377 ImmutableList.<E>asImmutableList(contents, uniques), comparator); 378 } 379 380 /** 381 * Returns a builder that creates immutable sorted sets with an explicit comparator. If the 382 * comparator has a more general type than the set being generated, such as creating a {@code 383 * SortedSet<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor 384 * instead. 385 * 386 * @throws NullPointerException if {@code comparator} is null 387 */ 388 public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 389 return new Builder<E>(comparator); 390 } 391 392 /** 393 * Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse 394 * of their natural ordering. 395 */ 396 public static <E extends Comparable<?>> Builder<E> reverseOrder() { 397 return new Builder<E>(Collections.reverseOrder()); 398 } 399 400 /** 401 * Returns a builder that creates immutable sorted sets whose elements are ordered by their 402 * natural ordering. The sorted sets use {@link Ordering#natural()} as the comparator. This method 403 * provides more type-safety than {@link #builder}, as it can be called only for classes that 404 * implement {@link Comparable}. 405 */ 406 public static <E extends Comparable<?>> Builder<E> naturalOrder() { 407 return new Builder<E>(Ordering.natural()); 408 } 409 410 /** 411 * A builder for creating immutable sorted set instances, especially {@code public static final} 412 * sets ("constant sets"), with a given comparator. Example: 413 * 414 * <pre>{@code 415 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS = 416 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR) 417 * .addAll(SINGLE_DIGIT_PRIMES) 418 * .add(42) 419 * .build(); 420 * }</pre> 421 * 422 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build 423 * multiple sets in series. Each set is a superset of the set created before it. 424 * 425 * @since 2.0 426 */ 427 public static final class Builder<E> extends ImmutableSet.Builder<E> { 428 private final Comparator<? super E> comparator; 429 private E[] elements; 430 private int n; 431 432 /** 433 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 434 * ImmutableSortedSet#orderedBy}. 435 */ 436 public Builder(Comparator<? super E> comparator) { 437 super(true); // don't construct guts of hash-based set builder 438 this.comparator = checkNotNull(comparator); 439 this.elements = (E[]) new Object[ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY]; 440 this.n = 0; 441 } 442 443 @Override 444 void copy() { 445 elements = Arrays.copyOf(elements, elements.length); 446 } 447 448 private void sortAndDedup() { 449 if (n == 0) { 450 return; 451 } 452 Arrays.sort(elements, 0, n, comparator); 453 int unique = 1; 454 for (int i = 1; i < n; i++) { 455 int cmp = comparator.compare(elements[unique - 1], elements[i]); 456 if (cmp < 0) { 457 elements[unique++] = elements[i]; 458 } else if (cmp > 0) { 459 throw new AssertionError( 460 "Comparator " + comparator + " compare method violates its contract"); 461 } 462 } 463 Arrays.fill(elements, unique, n, null); 464 n = unique; 465 } 466 467 /** 468 * Adds {@code element} to the {@code ImmutableSortedSet}. If the {@code ImmutableSortedSet} 469 * already contains {@code element}, then {@code add} has no effect. (only the previously added 470 * element is retained). 471 * 472 * @param element the element to add 473 * @return this {@code Builder} object 474 * @throws NullPointerException if {@code element} is null 475 */ 476 @CanIgnoreReturnValue 477 @Override 478 public Builder<E> add(E element) { 479 checkNotNull(element); 480 copyIfNecessary(); 481 if (n == elements.length) { 482 sortAndDedup(); 483 /* 484 * Sorting operations can only be allowed to occur once every O(n) operations to keep 485 * amortized O(n log n) performance. Therefore, ensure there are at least O(n) *unused* 486 * spaces in the builder array. 487 */ 488 int newLength = ImmutableCollection.Builder.expandedCapacity(n, n + 1); 489 if (newLength > elements.length) { 490 elements = Arrays.copyOf(elements, newLength); 491 } 492 } 493 elements[n++] = element; 494 return this; 495 } 496 497 /** 498 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate 499 * elements (only the first duplicate element is added). 500 * 501 * @param elements the elements to add 502 * @return this {@code Builder} object 503 * @throws NullPointerException if {@code elements} contains a null element 504 */ 505 @CanIgnoreReturnValue 506 @Override 507 public Builder<E> add(E... elements) { 508 checkElementsNotNull(elements); 509 for (E e : elements) { 510 add(e); 511 } 512 return this; 513 } 514 515 /** 516 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate 517 * elements (only the first duplicate element is added). 518 * 519 * @param elements the elements to add to the {@code ImmutableSortedSet} 520 * @return this {@code Builder} object 521 * @throws NullPointerException if {@code elements} contains a null element 522 */ 523 @CanIgnoreReturnValue 524 @Override 525 public Builder<E> addAll(Iterable<? extends E> elements) { 526 super.addAll(elements); 527 return this; 528 } 529 530 /** 531 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate 532 * elements (only the first duplicate element is added). 533 * 534 * @param elements the elements to add to the {@code ImmutableSortedSet} 535 * @return this {@code Builder} object 536 * @throws NullPointerException if {@code elements} contains a null element 537 */ 538 @CanIgnoreReturnValue 539 @Override 540 public Builder<E> addAll(Iterator<? extends E> elements) { 541 super.addAll(elements); 542 return this; 543 } 544 545 @CanIgnoreReturnValue 546 @Override 547 Builder<E> combine(ImmutableSet.Builder<E> builder) { 548 copyIfNecessary(); 549 Builder<E> other = (Builder<E>) builder; 550 for (int i = 0; i < other.n; i++) { 551 add(other.elements[i]); 552 } 553 return this; 554 } 555 556 /** 557 * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code 558 * Builder} and its comparator. 559 */ 560 @Override 561 public ImmutableSortedSet<E> build() { 562 sortAndDedup(); 563 if (n == 0) { 564 return emptySet(comparator); 565 } else { 566 forceCopy = true; 567 return new RegularImmutableSortedSet<E>( 568 ImmutableList.asImmutableList(elements, n), comparator); 569 } 570 } 571 } 572 573 int unsafeCompare(Object a, Object b) { 574 return unsafeCompare(comparator, a, b); 575 } 576 577 static int unsafeCompare(Comparator<?> comparator, Object a, Object b) { 578 // Pretend the comparator can compare anything. If it turns out it can't 579 // compare a and b, we should get a CCE on the subsequent line. Only methods 580 // that are spec'd to throw CCE should call this. 581 @SuppressWarnings("unchecked") 582 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator; 583 return unsafeComparator.compare(a, b); 584 } 585 586 final transient Comparator<? super E> comparator; 587 588 ImmutableSortedSet(Comparator<? super E> comparator) { 589 this.comparator = comparator; 590 } 591 592 /** 593 * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the 594 * natural ordering of the elements is used. Note that its behavior is not consistent with {@link 595 * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering. 596 */ 597 @Override 598 public Comparator<? super E> comparator() { 599 return comparator; 600 } 601 602 @Override // needed to unify the iterator() methods in Collection and SortedIterable 603 public abstract UnmodifiableIterator<E> iterator(); 604 605 /** 606 * {@inheritDoc} 607 * 608 * <p>This method returns a serializable {@code ImmutableSortedSet}. 609 * 610 * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an 611 * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code 612 * toElement}. However, this method doesn't throw an exception in that situation, but instead 613 * keeps the original {@code toElement}. 614 */ 615 @Override 616 public ImmutableSortedSet<E> headSet(E toElement) { 617 return headSet(toElement, false); 618 } 619 620 /** @since 12.0 */ 621 @GwtIncompatible // NavigableSet 622 @Override 623 public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) { 624 return headSetImpl(checkNotNull(toElement), inclusive); 625 } 626 627 /** 628 * {@inheritDoc} 629 * 630 * <p>This method returns a serializable {@code ImmutableSortedSet}. 631 * 632 * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link 633 * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code 634 * fromElement}. However, this method doesn't throw an exception in that situation, but instead 635 * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code 636 * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an 637 * earlier {@code toElement}. 638 */ 639 @Override 640 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) { 641 return subSet(fromElement, true, toElement, false); 642 } 643 644 /** @since 12.0 */ 645 @GwtIncompatible // NavigableSet 646 @Override 647 public ImmutableSortedSet<E> subSet( 648 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 649 checkNotNull(fromElement); 650 checkNotNull(toElement); 651 checkArgument(comparator.compare(fromElement, toElement) <= 0); 652 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive); 653 } 654 655 /** 656 * {@inheritDoc} 657 * 658 * <p>This method returns a serializable {@code ImmutableSortedSet}. 659 * 660 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an 661 * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code 662 * fromElement}. However, this method doesn't throw an exception in that situation, but instead 663 * keeps the original {@code fromElement}. 664 */ 665 @Override 666 public ImmutableSortedSet<E> tailSet(E fromElement) { 667 return tailSet(fromElement, true); 668 } 669 670 /** @since 12.0 */ 671 @GwtIncompatible // NavigableSet 672 @Override 673 public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) { 674 return tailSetImpl(checkNotNull(fromElement), inclusive); 675 } 676 677 /* 678 * These methods perform most headSet, subSet, and tailSet logic, besides 679 * parameter validation. 680 */ 681 abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive); 682 683 abstract ImmutableSortedSet<E> subSetImpl( 684 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive); 685 686 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive); 687 688 /** @since 12.0 */ 689 @GwtIncompatible // NavigableSet 690 @Override 691 public E lower(E e) { 692 return Iterators.getNext(headSet(e, false).descendingIterator(), null); 693 } 694 695 /** @since 12.0 */ 696 @GwtIncompatible // NavigableSet 697 @Override 698 public E floor(E e) { 699 return Iterators.getNext(headSet(e, true).descendingIterator(), null); 700 } 701 702 /** @since 12.0 */ 703 @GwtIncompatible // NavigableSet 704 @Override 705 public E ceiling(E e) { 706 return Iterables.getFirst(tailSet(e, true), null); 707 } 708 709 /** @since 12.0 */ 710 @GwtIncompatible // NavigableSet 711 @Override 712 public E higher(E e) { 713 return Iterables.getFirst(tailSet(e, false), null); 714 } 715 716 @Override 717 public E first() { 718 return iterator().next(); 719 } 720 721 @Override 722 public E last() { 723 return descendingIterator().next(); 724 } 725 726 /** 727 * Guaranteed to throw an exception and leave the set unmodified. 728 * 729 * @since 12.0 730 * @throws UnsupportedOperationException always 731 * @deprecated Unsupported operation. 732 */ 733 @CanIgnoreReturnValue 734 @Deprecated 735 @GwtIncompatible // NavigableSet 736 @Override 737 public final E pollFirst() { 738 throw new UnsupportedOperationException(); 739 } 740 741 /** 742 * Guaranteed to throw an exception and leave the set unmodified. 743 * 744 * @since 12.0 745 * @throws UnsupportedOperationException always 746 * @deprecated Unsupported operation. 747 */ 748 @CanIgnoreReturnValue 749 @Deprecated 750 @GwtIncompatible // NavigableSet 751 @Override 752 public final E pollLast() { 753 throw new UnsupportedOperationException(); 754 } 755 756 @GwtIncompatible // NavigableSet 757 @LazyInit 758 transient ImmutableSortedSet<E> descendingSet; 759 760 /** @since 12.0 */ 761 @GwtIncompatible // NavigableSet 762 @Override 763 public ImmutableSortedSet<E> descendingSet() { 764 // racy single-check idiom 765 ImmutableSortedSet<E> result = descendingSet; 766 if (result == null) { 767 result = descendingSet = createDescendingSet(); 768 result.descendingSet = this; 769 } 770 return result; 771 } 772 773 // Most classes should implement this as new DescendingImmutableSortedSet<E>(this), 774 // but we push down that implementation because ProGuard can't eliminate it even when it's always 775 // overridden. 776 @GwtIncompatible // NavigableSet 777 abstract ImmutableSortedSet<E> createDescendingSet(); 778 779 @Override 780 public Spliterator<E> spliterator() { 781 return new Spliterators.AbstractSpliterator<E>( 782 size(), SPLITERATOR_CHARACTERISTICS | Spliterator.SIZED) { 783 final UnmodifiableIterator<E> iterator = iterator(); 784 785 @Override 786 public boolean tryAdvance(Consumer<? super E> action) { 787 if (iterator.hasNext()) { 788 action.accept(iterator.next()); 789 return true; 790 } else { 791 return false; 792 } 793 } 794 795 @Override 796 public Comparator<? super E> getComparator() { 797 return comparator; 798 } 799 }; 800 } 801 802 /** @since 12.0 */ 803 @GwtIncompatible // NavigableSet 804 @Override 805 public abstract UnmodifiableIterator<E> descendingIterator(); 806 807 /** Returns the position of an element within the set, or -1 if not present. */ 808 abstract int indexOf(@Nullable Object target); 809 810 /* 811 * This class is used to serialize all ImmutableSortedSet instances, 812 * regardless of implementation type. It captures their "logical contents" 813 * only. This is necessary to ensure that the existence of a particular 814 * implementation type is an implementation detail. 815 */ 816 private static class SerializedForm<E> implements Serializable { 817 final Comparator<? super E> comparator; 818 final Object[] elements; 819 820 public SerializedForm(Comparator<? super E> comparator, Object[] elements) { 821 this.comparator = comparator; 822 this.elements = elements; 823 } 824 825 @SuppressWarnings("unchecked") 826 Object readResolve() { 827 return new Builder<E>(comparator).add((E[]) elements).build(); 828 } 829 830 private static final long serialVersionUID = 0; 831 } 832 833 private void readObject(ObjectInputStream unused) throws InvalidObjectException { 834 throw new InvalidObjectException("Use SerializedForm"); 835 } 836 837 @Override 838 Object writeReplace() { 839 return new SerializedForm<E>(comparator, toArray()); 840 } 841}