1 /* 2 * Copyright (C) 2008 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.base.Preconditions.checkArgument; 20 import static com.google.common.base.Preconditions.checkNotNull; 21 22 import com.google.common.annotations.GwtCompatible; 23 24 import java.io.InvalidObjectException; 25 import java.io.ObjectInputStream; 26 import java.io.Serializable; 27 import java.util.Arrays; 28 import java.util.Collection; 29 import java.util.Collections; 30 import java.util.Comparator; 31 import java.util.Iterator; 32 import java.util.List; 33 import java.util.SortedSet; 34 35 /** 36 * An immutable {@code SortedSet} that stores its elements in a sorted array. 37 * Some instances are ordered by an explicit comparator, while others follow the 38 * natural sort ordering of their elements. Either way, null elements are not 39 * supported. 40 * 41 * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i> 42 * of a separate collection that can still change, an instance of {@code 43 * ImmutableSortedSet} contains its own private data and will <i>never</i> 44 * change. This class is convenient for {@code public static final} sets 45 * ("constant sets") and also lets you easily make a "defensive copy" of a set 46 * provided to your class by a caller. 47 * 48 * <p>The sets returned by {@link #headSet}, {@link #tailSet}, and 49 * {@link #subSet} methods share the same array as the original set, preventing 50 * that array from being garbage collected. If this is a concern, the data may 51 * be copied into a correctly-sized array by calling {@link #copyOfSorted}. 52 * 53 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)}, 54 * {@link #containsAll(Collection)}, and {@link #equals(Object)} 55 * implementations must check whether a provided object is equivalent to an 56 * element in the collection. Unlike most collections, an 57 * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if 58 * two elements are equivalent. Instead, with an explicit comparator, the 59 * following relation determines whether elements {@code x} and {@code y} are 60 * equivalent: <pre> {@code 61 * 62 * {(x, y) | comparator.compare(x, y) == 0}}</pre> 63 * 64 * With natural ordering of elements, the following relation determines whether 65 * two elements are equivalent: <pre> {@code 66 * 67 * {(x, y) | x.compareTo(y) == 0}}</pre> 68 * 69 * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not 70 * function correctly if an element is modified after being placed in the set. 71 * For this reason, and to avoid general confusion, it is strongly recommended 72 * to place only immutable objects into this collection. 73 * 74 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as 75 * it has no public or protected constructors. Thus, instances of this type are 76 * guaranteed to be immutable. 77 * 78 * @see ImmutableSet 79 * @author Jared Levy 80 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library) 81 */ 82 @GwtCompatible(serializable = true) 83 @SuppressWarnings("serial") // we're overriding default serialization 84 public abstract class ImmutableSortedSet<E> 85 extends ImmutableSortedSetFauxverideShim<E> implements SortedSet<E> { 86 87 // TODO: Can we find a way to remove this @SuppressWarnings even for eclipse? 88 @SuppressWarnings("unchecked") 89 private static final Comparator NATURAL_ORDER = Ordering.natural(); 90 91 @SuppressWarnings("unchecked") 92 private static final ImmutableSortedSet<Object> NATURAL_EMPTY_SET = 93 new EmptyImmutableSortedSet<Object>(NATURAL_ORDER); 94 95 @SuppressWarnings("unchecked") 96 private static <E> ImmutableSortedSet<E> emptySet() { 97 return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET; 98 } 99 100 static <E> ImmutableSortedSet<E> emptySet( 101 Comparator<? super E> comparator) { 102 if (NATURAL_ORDER.equals(comparator)) { 103 return emptySet(); 104 } else { 105 return new EmptyImmutableSortedSet<E>(comparator); 106 } 107 } 108 109 /** 110 * Returns the empty immutable sorted set. 111 */ 112 public static <E> ImmutableSortedSet<E> of() { 113 return emptySet(); 114 } 115 116 /** 117 * Returns an immutable sorted set containing a single element. 118 */ 119 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 120 E element) { 121 Object[] array = { checkNotNull(element) }; 122 return new RegularImmutableSortedSet<E>(array, Ordering.natural()); 123 } 124 125 /** 126 * Returns an immutable sorted set containing the given elements sorted by 127 * their natural ordering. When multiple elements are equivalent according to 128 * {@link Comparable#compareTo}, only the first one specified is included. 129 * 130 * @throws NullPointerException if any element is null 131 */ 132 @SuppressWarnings("unchecked") 133 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 134 E e1, E e2) { 135 return ofInternal(Ordering.natural(), e1, e2); 136 } 137 138 /** 139 * Returns an immutable sorted set containing the given elements sorted by 140 * their natural ordering. When multiple elements are equivalent according to 141 * {@link Comparable#compareTo}, only the first one specified is included. 142 * 143 * @throws NullPointerException if any element is null 144 */ 145 @SuppressWarnings("unchecked") 146 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 147 E e1, E e2, E e3) { 148 return ofInternal(Ordering.natural(), e1, e2, e3); 149 } 150 151 /** 152 * Returns an immutable sorted set containing the given elements sorted by 153 * their natural ordering. When multiple elements are equivalent according to 154 * {@link Comparable#compareTo}, only the first one specified is included. 155 * 156 * @throws NullPointerException if any element is null 157 */ 158 @SuppressWarnings("unchecked") 159 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 160 E e1, E e2, E e3, E e4) { 161 return ofInternal(Ordering.natural(), e1, e2, e3, e4); 162 } 163 164 /** 165 * Returns an immutable sorted set containing the given elements sorted by 166 * their natural ordering. When multiple elements are equivalent according to 167 * {@link Comparable#compareTo}, only the first one specified is included. 168 * 169 * @throws NullPointerException if any element is null 170 */ 171 @SuppressWarnings("unchecked") 172 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 173 E e1, E e2, E e3, E e4, E e5) { 174 return ofInternal(Ordering.natural(), e1, e2, e3, e4, e5); 175 } 176 177 // TODO: Consider adding factory methods that throw an exception when given 178 // duplicate elements. 179 180 /** 181 * Returns an immutable sorted set containing the given elements sorted by 182 * their natural ordering. When multiple elements are equivalent according to 183 * {@link Comparable#compareTo}, only the first one specified is included. 184 * 185 * @throws NullPointerException if any of {@code elements} is null 186 */ 187 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of( 188 E... elements) { 189 return ofInternal(Ordering.natural(), elements); 190 } 191 192 private static <E> ImmutableSortedSet<E> ofInternal( 193 Comparator<? super E> comparator, E... elements) { 194 checkNotNull(elements); // for GWT 195 switch (elements.length) { 196 case 0: 197 return emptySet(comparator); 198 default: 199 /* 200 * We can't use Platform.clone() because of GWT bug 3621. See our GWT 201 * ImmutableSortedSetTest.testOf_gwtArraycopyBug() for details. We can't 202 * use System.arraycopy() here for the same reason. 203 */ 204 Object[] array = new Object[elements.length]; 205 for (int i = 0; i < elements.length; i++) { 206 array[i] = checkNotNull(elements[i]); 207 } 208 sort(array, comparator); 209 array = removeDupes(array, comparator); 210 return new RegularImmutableSortedSet<E>(array, comparator); 211 } 212 } 213 214 /** Sort the array, according to the comparator. */ 215 @SuppressWarnings("unchecked") // E comparator with Object array 216 private static <E> void sort( 217 Object[] array, Comparator<? super E> comparator) { 218 Arrays.sort(array, (Comparator<Object>) comparator); 219 } 220 221 /** 222 * Returns an array that removes duplicate consecutive elements, according to 223 * the provided comparator. Note that the input array is modified. This method 224 * does not support empty arrays. 225 */ 226 private static <E> Object[] removeDupes(Object[] array, 227 Comparator<? super E> comparator) { 228 int size = 1; 229 for (int i = 1; i < array.length; i++) { 230 Object element = array[i]; 231 if (unsafeCompare(comparator, array[size - 1], element) != 0) { 232 array[size] = element; 233 size++; 234 } 235 } 236 237 // TODO: Move to ObjectArrays? 238 if (size == array.length) { 239 return array; 240 } else { 241 Object[] copy = new Object[size]; 242 Platform.unsafeArrayCopy(array, 0, copy, 0, size); 243 return copy; 244 } 245 } 246 247 /** 248 * Returns an immutable sorted set containing the given elements sorted by 249 * their natural ordering. When multiple elements are equivalent according to 250 * {@code compareTo()}, only the first one specified is included. To create a 251 * copy of a {@code SortedSet} that preserves the comparator, call 252 * {@link #copyOfSorted} instead. This method iterates over {@code elements} 253 * at most once. 254 * 255 * <p>Note that if {@code s} is a {@code Set<String>}, then 256 * {@code ImmutableSortedSet.copyOf(s)} returns an 257 * {@code ImmutableSortedSet<String>} containing each of the strings in 258 * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an 259 * {@code ImmutableSortedSet<Set<String>>} containing one element (the given 260 * set itself). 261 * 262 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} 263 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy. 264 * 265 * <p>This method is not type-safe, as it may be called on elements that are 266 * not mutually comparable. 267 * 268 * @throws ClassCastException if the elements are not mutually comparable 269 * @throws NullPointerException if any of {@code elements} is null 270 */ 271 public static <E> ImmutableSortedSet<E> copyOf( 272 Iterable<? extends E> elements) { 273 // Hack around K not being a subtype of Comparable. 274 // Unsafe, see ImmutableSortedSetFauxverideShim. 275 @SuppressWarnings("unchecked") 276 Ordering<E> naturalOrder = (Ordering) Ordering.<Comparable>natural(); 277 return copyOfInternal(naturalOrder, elements, false); 278 } 279 280 /** 281 * Returns an immutable sorted set containing the given elements sorted by 282 * their natural ordering. When multiple elements are equivalent according to 283 * {@code compareTo()}, only the first one specified is included. 284 * 285 * <p>This method is not type-safe, as it may be called on elements that are 286 * not mutually comparable. 287 * 288 * @throws ClassCastException if the elements are not mutually comparable 289 * @throws NullPointerException if any of {@code elements} is null 290 */ 291 public static <E> ImmutableSortedSet<E> copyOf( 292 Iterator<? extends E> elements) { 293 // Hack around K not being a subtype of Comparable. 294 // Unsafe, see ImmutableSortedSetFauxverideShim. 295 @SuppressWarnings("unchecked") 296 Ordering<E> naturalOrder = (Ordering) Ordering.<Comparable>natural(); 297 return copyOfInternal(naturalOrder, elements); 298 } 299 300 /** 301 * Returns an immutable sorted set containing the given elements sorted by 302 * the given {@code Comparator}. When multiple elements are equivalent 303 * according to {@code compare()}, only the first one specified is 304 * included. This method iterates over {@code elements} at most once. 305 * 306 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} 307 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy. 308 * 309 * @throws NullPointerException if {@code comparator} or any of 310 * {@code elements} is null 311 */ 312 public static <E> ImmutableSortedSet<E> copyOf( 313 Comparator<? super E> comparator, Iterable<? extends E> elements) { 314 checkNotNull(comparator); 315 return copyOfInternal(comparator, elements, false); 316 } 317 318 /** 319 * Returns an immutable sorted set containing the given elements sorted by 320 * the given {@code Comparator}. When multiple elements are equivalent 321 * according to {@code compareTo()}, only the first one specified is 322 * included. 323 * 324 * @throws NullPointerException if {@code comparator} or any of 325 * {@code elements} is null 326 */ 327 public static <E> ImmutableSortedSet<E> copyOf( 328 Comparator<? super E> comparator, Iterator<? extends E> elements) { 329 checkNotNull(comparator); 330 return copyOfInternal(comparator, elements); 331 } 332 333 /** 334 * Returns an immutable sorted set containing the elements of a sorted set, 335 * sorted by the same {@code Comparator}. That behavior differs from 336 * {@link #copyOf(Iterable)}, which always uses the natural ordering of the 337 * elements. 338 * 339 * <p><b>Note:</b> Despite what the method name suggests, if {@code sortedSet} 340 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy. 341 * 342 * @throws NullPointerException if any of {@code elements} is null 343 */ 344 @SuppressWarnings("unchecked") 345 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) { 346 Comparator<? super E> comparator = sortedSet.comparator(); 347 if (comparator == null) { 348 comparator = NATURAL_ORDER; 349 } 350 return copyOfInternal(comparator, sortedSet, true); 351 } 352 353 private static <E> ImmutableSortedSet<E> copyOfInternal( 354 Comparator<? super E> comparator, Iterable<? extends E> elements, 355 boolean fromSortedSet) { 356 boolean hasSameComparator 357 = fromSortedSet || hasSameComparator(elements, comparator); 358 359 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) { 360 @SuppressWarnings("unchecked") 361 ImmutableSortedSet<E> result = (ImmutableSortedSet<E>) elements; 362 if (!result.hasPartialArray()) { 363 return result; 364 } 365 } 366 367 Object[] array = newObjectArray(elements); 368 if (array.length == 0) { 369 return emptySet(comparator); 370 } 371 372 for (Object e : array) { 373 checkNotNull(e); 374 } 375 if (!hasSameComparator) { 376 sort(array, comparator); 377 array = removeDupes(array, comparator); 378 } 379 return new RegularImmutableSortedSet<E>(array, comparator); 380 } 381 382 /** Simplified version of {@link Iterables#toArray} that is GWT safe. */ 383 private static <T> Object[] newObjectArray(Iterable<T> iterable) { 384 Collection<T> collection = (iterable instanceof Collection) 385 ? (Collection<T>) iterable : Lists.newArrayList(iterable); 386 Object[] array = new Object[collection.size()]; 387 return collection.toArray(array); 388 } 389 390 private static <E> ImmutableSortedSet<E> copyOfInternal( 391 Comparator<? super E> comparator, Iterator<? extends E> elements) { 392 if (!elements.hasNext()) { 393 return emptySet(comparator); 394 } 395 List<E> list = Lists.newArrayList(); 396 while (elements.hasNext()) { 397 list.add(checkNotNull(elements.next())); 398 } 399 Object[] array = list.toArray(); 400 sort(array, comparator); 401 array = removeDupes(array, comparator); 402 return new RegularImmutableSortedSet<E>(array, comparator); 403 } 404 405 /** 406 * Returns {@code true} if {@code elements} is a {@code SortedSet} that uses 407 * {@code comparator} to order its elements. Note that equivalent comparators 408 * may still return {@code false}, if {@code equals} doesn't consider them 409 * equal. If one comparator is {@code null} and the other is 410 * {@link Ordering#natural()}, this method returns {@code true}. 411 */ 412 static boolean hasSameComparator( 413 Iterable<?> elements, Comparator<?> comparator) { 414 if (elements instanceof SortedSet) { 415 SortedSet<?> sortedSet = (SortedSet<?>) elements; 416 Comparator<?> comparator2 = sortedSet.comparator(); 417 return (comparator2 == null) 418 ? comparator == Ordering.natural() 419 : comparator.equals(comparator2); 420 } 421 return false; 422 } 423 424 /** 425 * Returns a builder that creates immutable sorted sets with an explicit 426 * comparator. If the comparator has a more general type than the set being 427 * generated, such as creating a {@code SortedSet<Integer>} with a 428 * {@code Comparator<Number>}, use the {@link Builder} constructor instead. 429 * 430 * @throws NullPointerException if {@code comparator} is null 431 */ 432 public static <E> Builder<E> orderedBy(Comparator<E> comparator) { 433 return new Builder<E>(comparator); 434 } 435 436 /** 437 * Returns a builder that creates immutable sorted sets whose elements are 438 * ordered by the reverse of their natural ordering. 439 * 440 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather 441 * than {@code Comparable<? super E>} as a workaround for javac <a 442 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 443 * 6468354</a>. 444 */ 445 public static <E extends Comparable<E>> Builder<E> reverseOrder() { 446 return new Builder<E>(Ordering.natural().reverse()); 447 } 448 449 /** 450 * Returns a builder that creates immutable sorted sets whose elements are 451 * ordered by their natural ordering. The sorted sets use {@link 452 * Ordering#natural()} as the comparator. This method provides more 453 * type-safety than {@link #builder}, as it can be called only for classes 454 * that implement {@link Comparable}. 455 * 456 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather 457 * than {@code Comparable<? super E>} as a workaround for javac <a 458 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 459 * 6468354</a>. 460 */ 461 public static <E extends Comparable<E>> Builder<E> naturalOrder() { 462 return new Builder<E>(Ordering.natural()); 463 } 464 465 /** 466 * A builder for creating immutable sorted set instances, especially 467 * {@code public static final} sets ("constant sets"), with a given 468 * comparator. 469 * 470 * <p>Example: 471 * <pre>{@code 472 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS 473 * = new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR) 474 * .addAll(SINGLE_DIGIT_PRIMES) 475 * .add(42) 476 * .build();}</pre> 477 * 478 * <p>Builder instances can be reused - it is safe to call {@link #build} 479 * multiple times to build multiple sets in series. Each set 480 * is a superset of the set created before it. 481 */ 482 public static final class Builder<E> extends ImmutableSet.Builder<E> { 483 private final Comparator<? super E> comparator; 484 485 /** 486 * Creates a new builder. The returned builder is equivalent to the builder 487 * generated by {@link ImmutableSortedSet#orderedBy}. 488 */ 489 public Builder(Comparator<? super E> comparator) { 490 this.comparator = checkNotNull(comparator); 491 } 492 493 /** 494 * Adds {@code element} to the {@code ImmutableSortedSet}. If the 495 * {@code ImmutableSortedSet} already contains {@code element}, then 496 * {@code add} has no effect. (only the previously added element 497 * is retained). 498 * 499 * @param element the element to add 500 * @return this {@code Builder} object 501 * @throws NullPointerException if {@code element} is null 502 */ 503 @Override public Builder<E> add(E element) { 504 super.add(element); 505 return this; 506 } 507 508 /** 509 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, 510 * ignoring duplicate elements (only the first duplicate element is added). 511 * 512 * @param elements the elements to add 513 * @return this {@code Builder} object 514 * @throws NullPointerException if {@code elements} contains a null element 515 */ 516 @Override public Builder<E> add(E... elements) { 517 super.add(elements); 518 return this; 519 } 520 521 /** 522 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, 523 * ignoring duplicate elements (only the first duplicate element is added). 524 * 525 * @param elements the elements to add to the {@code ImmutableSortedSet} 526 * @return this {@code Builder} object 527 * @throws NullPointerException if {@code elements} contains a null element 528 */ 529 @Override public Builder<E> addAll(Iterable<? extends E> elements) { 530 super.addAll(elements); 531 return this; 532 } 533 534 /** 535 * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, 536 * ignoring duplicate elements (only the first duplicate element is added). 537 * 538 * @param elements the elements to add to the {@code ImmutableSortedSet} 539 * @return this {@code Builder} object 540 * @throws NullPointerException if {@code elements} contains a null element 541 */ 542 @Override public Builder<E> addAll(Iterator<? extends E> elements) { 543 super.addAll(elements); 544 return this; 545 } 546 547 /** 548 * Returns a newly-created {@code ImmutableSortedSet} based on the contents 549 * of the {@code Builder} and its comparator. 550 */ 551 @Override public ImmutableSortedSet<E> build() { 552 return copyOfInternal(comparator, contents.iterator()); 553 } 554 } 555 556 int unsafeCompare(Object a, Object b) { 557 return unsafeCompare(comparator, a, b); 558 } 559 560 static int unsafeCompare( 561 Comparator<?> comparator, Object a, Object b) { 562 // Pretend the comparator can compare anything. If it turns out it can't 563 // compare a and b, we should get a CCE on the subsequent line. Only methods 564 // that are spec'd to throw CCE should call this. 565 @SuppressWarnings("unchecked") 566 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator; 567 return unsafeComparator.compare(a, b); 568 } 569 570 final transient Comparator<? super E> comparator; 571 572 ImmutableSortedSet(Comparator<? super E> comparator) { 573 this.comparator = comparator; 574 } 575 576 /** 577 * Returns the comparator that orders the elements, which is 578 * {@link Ordering#natural()} when the natural ordering of the 579 * elements is used. Note that its behavior is not consistent with 580 * {@link SortedSet#comparator()}, which returns {@code null} to indicate 581 * natural ordering. 582 */ 583 public Comparator<? super E> comparator() { 584 return comparator; 585 } 586 587 /** 588 * {@inheritDoc} 589 * 590 * <p>This method returns a serializable {@code ImmutableSortedSet}. 591 * 592 * <p>The {@link SortedSet#headSet} documentation states that a subset of a 593 * subset throws an {@link IllegalArgumentException} if passed a 594 * {@code toElement} greater than an earlier {@code toElement}. However, this 595 * method doesn't throw an exception in that situation, but instead keeps the 596 * original {@code toElement}. 597 */ 598 public ImmutableSortedSet<E> headSet(E toElement) { 599 return headSetImpl(checkNotNull(toElement)); 600 } 601 602 /** 603 * {@inheritDoc} 604 * 605 * <p>This method returns a serializable {@code ImmutableSortedSet}. 606 * 607 * <p>The {@link SortedSet#subSet} documentation states that a subset of a 608 * subset throws an {@link IllegalArgumentException} if passed a 609 * {@code fromElement} smaller than an earlier {@code fromElement}. However, 610 * this method doesn't throw an exception in that situation, but instead keeps 611 * the original {@code fromElement}. Similarly, this method keeps the 612 * original {@code toElement}, instead of throwing an exception, if passed a 613 * {@code toElement} greater than an earlier {@code toElement}. 614 */ 615 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) { 616 checkNotNull(fromElement); 617 checkNotNull(toElement); 618 checkArgument(comparator.compare(fromElement, toElement) <= 0); 619 return subSetImpl(fromElement, toElement); 620 } 621 622 /** 623 * {@inheritDoc} 624 * 625 * <p>This method returns a serializable {@code ImmutableSortedSet}. 626 * 627 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a 628 * subset throws an {@link IllegalArgumentException} if passed a 629 * {@code fromElement} smaller than an earlier {@code fromElement}. However, 630 * this method doesn't throw an exception in that situation, but instead keeps 631 * the original {@code fromElement}. 632 */ 633 public ImmutableSortedSet<E> tailSet(E fromElement) { 634 return tailSetImpl(checkNotNull(fromElement)); 635 } 636 637 /* 638 * These methods perform most headSet, subSet, and tailSet logic, besides 639 * parameter validation. 640 */ 641 abstract ImmutableSortedSet<E> headSetImpl(E toElement); 642 abstract ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement); 643 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement); 644 645 /** Returns whether the elements are stored in a subset of a larger array. */ 646 abstract boolean hasPartialArray(); 647 648 /** 649 * Returns the position of an element within the set, or -1 if not present. 650 */ 651 abstract int indexOf(Object target); 652 653 /* 654 * This class is used to serialize all ImmutableSortedSet instances, 655 * regardless of implementation type. It captures their "logical contents" 656 * only. This is necessary to ensure that the existence of a particular 657 * implementation type is an implementation detail. 658 */ 659 private static class SerializedForm<E> implements Serializable { 660 final Comparator<? super E> comparator; 661 final Object[] elements; 662 663 public SerializedForm(Comparator<? super E> comparator, Object[] elements) { 664 this.comparator = comparator; 665 this.elements = elements; 666 } 667 668 @SuppressWarnings("unchecked") 669 Object readResolve() { 670 return new Builder<E>(comparator).add((E[]) elements).build(); 671 } 672 673 private static final long serialVersionUID = 0; 674 } 675 676 private void readObject(ObjectInputStream stream) 677 throws InvalidObjectException { 678 throw new InvalidObjectException("Use SerializedForm"); 679 } 680 681 @Override Object writeReplace() { 682 return new SerializedForm<E>(comparator, toArray()); 683 } 684 } 685