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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.GwtCompatible;
023
024 import java.io.InvalidObjectException;
025 import java.io.ObjectInputStream;
026 import java.io.Serializable;
027 import java.util.ArrayList;
028 import java.util.Arrays;
029 import java.util.Collection;
030 import java.util.Collections;
031 import java.util.Comparator;
032 import java.util.Iterator;
033 import java.util.List;
034 import java.util.SortedSet;
035
036 import javax.annotation.Nullable;
037
038 /**
039 * An immutable {@code SortedSet} that stores its elements in a sorted array.
040 * Some instances are ordered by an explicit comparator, while others follow the
041 * natural sort ordering of their elements. Either way, null elements are not
042 * supported.
043 *
044 * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i>
045 * of a separate collection that can still change, an instance of {@code
046 * ImmutableSortedSet} contains its own private data and will <i>never</i>
047 * change. This class is convenient for {@code public static final} sets
048 * ("constant sets") and also lets you easily make a "defensive copy" of a set
049 * provided to your class by a caller.
050 *
051 * <p>The sets returned by the {@link #headSet}, {@link #tailSet}, and
052 * {@link #subSet} methods share the same array as the original set, preventing
053 * that array from being garbage collected. If this is a concern, the data may
054 * be copied into a correctly-sized array by calling {@link #copyOfSorted}.
055 *
056 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
057 * {@link #containsAll(Collection)}, and {@link #equals(Object)}
058 * implementations must check whether a provided object is equivalent to an
059 * element in the collection. Unlike most collections, an
060 * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if
061 * two elements are equivalent. Instead, with an explicit comparator, the
062 * following relation determines whether elements {@code x} and {@code y} are
063 * equivalent: <pre> {@code
064 *
065 * {(x, y) | comparator.compare(x, y) == 0}}</pre>
066 *
067 * With natural ordering of elements, the following relation determines whether
068 * two elements are equivalent: <pre> {@code
069 *
070 * {(x, y) | x.compareTo(y) == 0}}</pre>
071 *
072 * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not
073 * function correctly if an element is modified after being placed in the set.
074 * For this reason, and to avoid general confusion, it is strongly recommended
075 * to place only immutable objects into this collection.
076 *
077 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
078 * it has no public or protected constructors. Thus, instances of this type are
079 * guaranteed to be immutable.
080 *
081 * @see ImmutableSet
082 * @author Jared Levy
083 * @author Louis Wasserman
084 * @since 2.0 (imported from Google Collections Library)
085 */
086 // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
087 @GwtCompatible(serializable = true, emulated = true)
088 @SuppressWarnings("serial") // we're overriding default serialization
089 public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
090 implements SortedSet<E>, SortedIterable<E> {
091
092 private static final Comparator<Comparable> NATURAL_ORDER =
093 Ordering.natural();
094
095 private static final ImmutableSortedSet<Comparable> NATURAL_EMPTY_SET =
096 new EmptyImmutableSortedSet<Comparable>(NATURAL_ORDER);
097
098 @SuppressWarnings("unchecked")
099 private static <E> ImmutableSortedSet<E> emptySet() {
100 return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET;
101 }
102
103 static <E> ImmutableSortedSet<E> emptySet(
104 Comparator<? super E> comparator) {
105 if (NATURAL_ORDER.equals(comparator)) {
106 return emptySet();
107 } else {
108 return new EmptyImmutableSortedSet<E>(comparator);
109 }
110 }
111
112 /**
113 * Returns the empty immutable sorted set.
114 */
115 public static <E> ImmutableSortedSet<E> of() {
116 return emptySet();
117 }
118
119 /**
120 * Returns an immutable sorted set containing a single element.
121 */
122 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
123 E element) {
124 return new RegularImmutableSortedSet<E>(
125 ImmutableList.of(element), Ordering.natural());
126 }
127
128 /**
129 * Returns an immutable sorted set containing the given elements sorted by
130 * their natural ordering. When multiple elements are equivalent according to
131 * {@link Comparable#compareTo}, only the first one specified is included.
132 *
133 * @throws NullPointerException if any element is null
134 */
135 @SuppressWarnings("unchecked")
136 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
137 E e1, E e2) {
138 return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
139 }
140
141 /**
142 * Returns an immutable sorted set containing the given elements sorted by
143 * their natural ordering. When multiple elements are equivalent according to
144 * {@link Comparable#compareTo}, only the first one specified is included.
145 *
146 * @throws NullPointerException if any element is null
147 */
148 @SuppressWarnings("unchecked")
149 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
150 E e1, E e2, E e3) {
151 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
152 }
153
154 /**
155 * Returns an immutable sorted set containing the given elements sorted by
156 * their natural ordering. When multiple elements are equivalent according to
157 * {@link Comparable#compareTo}, only the first one specified is included.
158 *
159 * @throws NullPointerException if any element is null
160 */
161 @SuppressWarnings("unchecked")
162 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
163 E e1, E e2, E e3, E e4) {
164 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
165 }
166
167 /**
168 * Returns an immutable sorted set containing the given elements sorted by
169 * their natural ordering. When multiple elements are equivalent according to
170 * {@link Comparable#compareTo}, only the first one specified is included.
171 *
172 * @throws NullPointerException if any element is null
173 */
174 @SuppressWarnings("unchecked")
175 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
176 E e1, E e2, E e3, E e4, E e5) {
177 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
178 }
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 element is null
186 * @since 3.0 (source-compatible since 2.0)
187 */
188 @SuppressWarnings("unchecked")
189 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
190 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
191 int size = remaining.length + 6;
192 List<E> all = new ArrayList<E>(size);
193 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
194 Collections.addAll(all, remaining);
195 return copyOf(Ordering.natural(), all);
196 }
197
198 // TODO(kevinb): Consider factory methods that reject duplicates
199
200 /**
201 * Returns an immutable sorted set containing the given elements sorted by
202 * their natural ordering. When multiple elements are equivalent according to
203 * {@link Comparable#compareTo}, only the first one specified is included.
204 *
205 * @throws NullPointerException if any of {@code elements} is null
206 * @since 3.0
207 */
208 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
209 E[] elements) {
210 return copyOf(Ordering.natural(), Arrays.asList(elements));
211 }
212
213 /**
214 * Returns an immutable sorted set containing the given elements sorted by
215 * their natural ordering. When multiple elements are equivalent according to
216 * {@code compareTo()}, only the first one specified is included. To create a
217 * copy of a {@code SortedSet} that preserves the comparator, call {@link
218 * #copyOfSorted} instead. This method iterates over {@code elements} at most
219 * once.
220
221 *
222 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
223 * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>}
224 * containing each of the strings in {@code s}, while {@code
225 * ImmutableSortedSet.of(s)} returns an {@code
226 * ImmutableSortedSet<Set<String>>} containing one element (the given set
227 * itself).
228 *
229 * <p>Despite the method name, this method attempts to avoid actually copying
230 * the data when it is safe to do so. The exact circumstances under which a
231 * copy will or will not be performed are undocumented and subject to change.
232 *
233 * <p>This method is not type-safe, as it may be called on elements that are
234 * not mutually comparable.
235 *
236 * @throws ClassCastException if the elements are not mutually comparable
237 * @throws NullPointerException if any of {@code elements} is null
238 */
239 public static <E> ImmutableSortedSet<E> copyOf(
240 Iterable<? extends E> elements) {
241 // Hack around E not being a subtype of Comparable.
242 // Unsafe, see ImmutableSortedSetFauxverideShim.
243 @SuppressWarnings("unchecked")
244 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
245 return copyOf(naturalOrder, elements);
246 }
247
248 /**
249 * Returns an immutable sorted set containing the given elements sorted by
250 * their natural ordering. When multiple elements are equivalent according to
251 * {@code compareTo()}, only the first one specified is included. To create a
252 * copy of a {@code SortedSet} that preserves the comparator, call
253 * {@link #copyOfSorted} instead. This method iterates over {@code elements}
254 * at most once.
255 *
256 * <p>Note that if {@code s} is a {@code Set<String>}, then
257 * {@code ImmutableSortedSet.copyOf(s)} returns an
258 * {@code ImmutableSortedSet<String>} containing each of the strings in
259 * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
260 * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
261 * set itself).
262 *
263 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
264 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
265 *
266 * <p>This method is not type-safe, as it may be called on elements that are
267 * not mutually comparable.
268 *
269 * <p>This method is safe to use even when {@code elements} is a synchronized
270 * or concurrent collection that is currently being modified by another
271 * thread.
272 *
273 * @throws ClassCastException if the elements are not mutually comparable
274 * @throws NullPointerException if any of {@code elements} is null
275 * @since 7.0 (source-compatible since 2.0)
276 */
277 public static <E> ImmutableSortedSet<E> copyOf(
278 Collection<? extends E> elements) {
279 // Hack around E not being a subtype of Comparable.
280 // Unsafe, see ImmutableSortedSetFauxverideShim.
281 @SuppressWarnings("unchecked")
282 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
283 return copyOf(naturalOrder, elements);
284 }
285
286 /**
287 * Returns an immutable sorted set containing the given elements sorted by
288 * their natural ordering. When multiple elements are equivalent according to
289 * {@code compareTo()}, only the first one specified is included.
290 *
291 * <p>This method is not type-safe, as it may be called on elements that are
292 * not mutually comparable.
293 *
294 * @throws ClassCastException if the elements are not mutually comparable
295 * @throws NullPointerException if any of {@code elements} is null
296 */
297 public static <E> ImmutableSortedSet<E> copyOf(
298 Iterator<? extends E> elements) {
299 // Hack around E not being a subtype of Comparable.
300 // Unsafe, see ImmutableSortedSetFauxverideShim.
301 @SuppressWarnings("unchecked")
302 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
303 return copyOfInternal(naturalOrder, elements);
304 }
305
306 /**
307 * Returns an immutable sorted set containing the given elements sorted by
308 * the given {@code Comparator}. When multiple elements are equivalent
309 * according to {@code compareTo()}, only the first one specified is
310 * included.
311 *
312 * @throws NullPointerException if {@code comparator} or any of
313 * {@code elements} is null
314 */
315 public static <E> ImmutableSortedSet<E> copyOf(
316 Comparator<? super E> comparator, Iterator<? extends E> elements) {
317 checkNotNull(comparator);
318 return copyOfInternal(comparator, elements);
319 }
320
321 /**
322 * Returns an immutable sorted set containing the given elements sorted by
323 * the given {@code Comparator}. When multiple elements are equivalent
324 * according to {@code compare()}, only the first one specified is
325 * included. This method iterates over {@code elements} at most once.
326 *
327 * <p>Despite the method name, this method attempts to avoid actually copying
328 * the data when it is safe to do so. The exact circumstances under which a
329 * copy will or will not be performed are undocumented and subject to change.
330 *
331 * @throws NullPointerException if {@code comparator} or any of {@code
332 * elements} is null
333 */
334 public static <E> ImmutableSortedSet<E> copyOf(
335 Comparator<? super E> comparator, Iterable<? extends E> elements) {
336 checkNotNull(comparator);
337 return copyOfInternal(comparator, elements);
338 }
339
340 /**
341 * Returns an immutable sorted set containing the given elements sorted by
342 * the given {@code Comparator}. When multiple elements are equivalent
343 * according to {@code compareTo()}, only the first one specified is
344 * included.
345 *
346 * <p>Despite the method name, this method attempts to avoid actually copying
347 * the data when it is safe to do so. The exact circumstances under which a
348 * copy will or will not be performed are undocumented and subject to change.
349 *
350 * <p>This method is safe to use even when {@code elements} is a synchronized
351 * or concurrent collection that is currently being modified by another
352 * thread.
353 *
354 * @throws NullPointerException if {@code comparator} or any of
355 * {@code elements} is null
356 * @since 7.0 (source-compatible since 2.0)
357 */
358 public static <E> ImmutableSortedSet<E> copyOf(
359 Comparator<? super E> comparator, Collection<? extends E> elements) {
360 checkNotNull(comparator);
361 return copyOfInternal(comparator, elements);
362 }
363
364 /**
365 * Returns an immutable sorted set containing the elements of a sorted set,
366 * sorted by the same {@code Comparator}. That behavior differs from {@link
367 * #copyOf(Iterable)}, which always uses the natural ordering of the
368 * elements.
369 *
370 * <p>Despite the method name, this method attempts to avoid actually copying
371 * the data when it is safe to do so. The exact circumstances under which a
372 * copy will or will not be performed are undocumented and subject to change.
373 *
374 * <p>This method is safe to use even when {@code sortedSet} is a synchronized
375 * or concurrent collection that is currently being modified by another
376 * thread.
377 *
378 * @throws NullPointerException if {@code sortedSet} or any of its elements
379 * is null
380 */
381 @SuppressWarnings("unchecked")
382 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
383 Comparator<? super E> comparator = sortedSet.comparator();
384 if (comparator == null) {
385 comparator = (Comparator<? super E>) NATURAL_ORDER;
386 }
387 return copyOfInternal(comparator, sortedSet);
388 }
389
390 private static <E> ImmutableSortedSet<E> copyOfInternal(
391 Comparator<? super E> comparator, Iterable<? extends E> elements) {
392 boolean hasSameComparator =
393 SortedIterables.hasSameComparator(comparator, elements);
394
395 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
396 @SuppressWarnings("unchecked")
397 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
398 if (!original.isPartialView()) {
399 return original;
400 }
401 }
402 ImmutableList<E> list = ImmutableList.copyOf(
403 SortedIterables.sortedUnique(comparator, elements));
404 return list.isEmpty()
405 ? ImmutableSortedSet.<E>emptySet(comparator)
406 : new RegularImmutableSortedSet<E>(list, comparator);
407 }
408
409 private static <E> ImmutableSortedSet<E> copyOfInternal(
410 Comparator<? super E> comparator, Iterator<? extends E> elements) {
411 ImmutableList<E> list =
412 ImmutableList.copyOf(SortedIterables.sortedUnique(comparator, elements));
413 return list.isEmpty()
414 ? ImmutableSortedSet.<E>emptySet(comparator)
415 : new RegularImmutableSortedSet<E>(list, comparator);
416 }
417
418 /**
419 * Returns a builder that creates immutable sorted sets with an explicit
420 * comparator. If the comparator has a more general type than the set being
421 * generated, such as creating a {@code SortedSet<Integer>} with a
422 * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
423 *
424 * @throws NullPointerException if {@code comparator} is null
425 */
426 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
427 return new Builder<E>(comparator);
428 }
429
430 /**
431 * Returns a builder that creates immutable sorted sets whose elements are
432 * ordered by the reverse of their natural ordering.
433 *
434 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
435 * than {@code Comparable<? super E>} as a workaround for javac <a
436 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
437 * 6468354</a>.
438 */
439 public static <E extends Comparable<E>> Builder<E> reverseOrder() {
440 return new Builder<E>(Ordering.natural().reverse());
441 }
442
443 /**
444 * Returns a builder that creates immutable sorted sets whose elements are
445 * ordered by their natural ordering. The sorted sets use {@link
446 * Ordering#natural()} as the comparator. This method provides more
447 * type-safety than {@link #builder}, as it can be called only for classes
448 * that implement {@link Comparable}.
449 *
450 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
451 * than {@code Comparable<? super E>} as a workaround for javac <a
452 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
453 * 6468354</a>.
454 */
455 public static <E extends Comparable<E>> Builder<E> naturalOrder() {
456 return new Builder<E>(Ordering.natural());
457 }
458
459 /**
460 * A builder for creating immutable sorted set instances, especially {@code
461 * public static final} sets ("constant sets"), with a given comparator.
462 * Example: <pre> {@code
463 *
464 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
465 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
466 * .addAll(SINGLE_DIGIT_PRIMES)
467 * .add(42)
468 * .build();}</pre>
469 *
470 * Builder instances can be reused; it is safe to call {@link #build} multiple
471 * times to build multiple sets in series. Each set is a superset of the set
472 * created before it.
473 *
474 * @since 2.0 (imported from Google Collections Library)
475 */
476 public static final class Builder<E> extends ImmutableSet.Builder<E> {
477 private final Comparator<? super E> comparator;
478
479 /**
480 * Creates a new builder. The returned builder is equivalent to the builder
481 * generated by {@link ImmutableSortedSet#orderedBy}.
482 */
483 public Builder(Comparator<? super E> comparator) {
484 this.comparator = checkNotNull(comparator);
485 }
486
487 /**
488 * Adds {@code element} to the {@code ImmutableSortedSet}. If the
489 * {@code ImmutableSortedSet} already contains {@code element}, then
490 * {@code add} has no effect. (only the previously added element
491 * is retained).
492 *
493 * @param element the element to add
494 * @return this {@code Builder} object
495 * @throws NullPointerException if {@code element} is null
496 */
497 @Override public Builder<E> add(E element) {
498 super.add(element);
499 return this;
500 }
501
502 /**
503 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
504 * ignoring duplicate elements (only the first duplicate element is added).
505 *
506 * @param elements the elements to add
507 * @return this {@code Builder} object
508 * @throws NullPointerException if {@code elements} contains a null element
509 */
510 @Override public Builder<E> add(E... elements) {
511 super.add(elements);
512 return this;
513 }
514
515 /**
516 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
517 * ignoring duplicate 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 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
524 super.addAll(elements);
525 return this;
526 }
527
528 /**
529 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
530 * ignoring duplicate elements (only the first duplicate element is added).
531 *
532 * @param elements the elements to add to the {@code ImmutableSortedSet}
533 * @return this {@code Builder} object
534 * @throws NullPointerException if {@code elements} contains a null element
535 */
536 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
537 super.addAll(elements);
538 return this;
539 }
540
541 /**
542 * Returns a newly-created {@code ImmutableSortedSet} based on the contents
543 * of the {@code Builder} and its comparator.
544 */
545 @Override public ImmutableSortedSet<E> build() {
546 return copyOfInternal(comparator, contents.iterator());
547 }
548 }
549
550 int unsafeCompare(Object a, Object b) {
551 return unsafeCompare(comparator, a, b);
552 }
553
554 static int unsafeCompare(
555 Comparator<?> comparator, Object a, Object b) {
556 // Pretend the comparator can compare anything. If it turns out it can't
557 // compare a and b, we should get a CCE on the subsequent line. Only methods
558 // that are spec'd to throw CCE should call this.
559 @SuppressWarnings("unchecked")
560 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
561 return unsafeComparator.compare(a, b);
562 }
563
564 final transient Comparator<? super E> comparator;
565
566 ImmutableSortedSet(Comparator<? super E> comparator) {
567 this.comparator = comparator;
568 }
569
570 /**
571 * Returns the comparator that orders the elements, which is
572 * {@link Ordering#natural()} when the natural ordering of the
573 * elements is used. Note that its behavior is not consistent with
574 * {@link SortedSet#comparator()}, which returns {@code null} to indicate
575 * natural ordering.
576 */
577 @Override
578 public Comparator<? super E> comparator() {
579 return comparator;
580 }
581
582 @Override // needed to unify the iterator() methods in Collection and SortedIterable
583 public abstract UnmodifiableIterator<E> iterator();
584
585 /**
586 * {@inheritDoc}
587 *
588 * <p>This method returns a serializable {@code ImmutableSortedSet}.
589 *
590 * <p>The {@link SortedSet#headSet} documentation states that a subset of a
591 * subset throws an {@link IllegalArgumentException} if passed a
592 * {@code toElement} greater than an earlier {@code toElement}. However, this
593 * method doesn't throw an exception in that situation, but instead keeps the
594 * original {@code toElement}.
595 */
596 @Override
597 public ImmutableSortedSet<E> headSet(E toElement) {
598 return headSet(toElement, false);
599 }
600
601 ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
602 return headSetImpl(checkNotNull(toElement), inclusive);
603 }
604
605 /**
606 * {@inheritDoc}
607 *
608 * <p>This method returns a serializable {@code ImmutableSortedSet}.
609 *
610 * <p>The {@link SortedSet#subSet} documentation states that a subset of a
611 * subset throws an {@link IllegalArgumentException} if passed a
612 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
613 * this method doesn't throw an exception in that situation, but instead keeps
614 * the original {@code fromElement}. Similarly, this method keeps the
615 * original {@code toElement}, instead of throwing an exception, if passed a
616 * {@code toElement} greater than an earlier {@code toElement}.
617 */
618 @Override
619 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
620 return subSet(fromElement, true, toElement, false);
621 }
622
623 ImmutableSortedSet<E> subSet(
624 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
625 checkNotNull(fromElement);
626 checkNotNull(toElement);
627 checkArgument(comparator.compare(fromElement, toElement) <= 0);
628 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
629 }
630
631 /**
632 * {@inheritDoc}
633 *
634 * <p>This method returns a serializable {@code ImmutableSortedSet}.
635 *
636 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
637 * subset throws an {@link IllegalArgumentException} if passed a
638 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
639 * this method doesn't throw an exception in that situation, but instead keeps
640 * the original {@code fromElement}.
641 */
642 @Override
643 public ImmutableSortedSet<E> tailSet(E fromElement) {
644 return tailSet(fromElement, true);
645 }
646
647 ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
648 return tailSetImpl(checkNotNull(fromElement), inclusive);
649 }
650
651 /*
652 * These methods perform most headSet, subSet, and tailSet logic, besides
653 * parameter validation.
654 */
655 abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
656
657 abstract ImmutableSortedSet<E> subSetImpl(
658 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
659
660 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
661
662 /**
663 * Returns the position of an element within the set, or -1 if not present.
664 */
665 abstract int indexOf(@Nullable Object target);
666
667 /*
668 * This class is used to serialize all ImmutableSortedSet instances,
669 * regardless of implementation type. It captures their "logical contents"
670 * only. This is necessary to ensure that the existence of a particular
671 * implementation type is an implementation detail.
672 */
673 private static class SerializedForm<E> implements Serializable {
674 final Comparator<? super E> comparator;
675 final Object[] elements;
676
677 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
678 this.comparator = comparator;
679 this.elements = elements;
680 }
681
682 @SuppressWarnings("unchecked")
683 Object readResolve() {
684 return new Builder<E>(comparator).add((E[]) elements).build();
685 }
686
687 private static final long serialVersionUID = 0;
688 }
689
690 private void readObject(ObjectInputStream stream)
691 throws InvalidObjectException {
692 throw new InvalidObjectException("Use SerializedForm");
693 }
694
695 @Override Object writeReplace() {
696 return new SerializedForm<E>(comparator, toArray());
697 }
698 }
699