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