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