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 * @deprecated use {@link #copyOf(Comparable[])}. <b>This method is scheduled
207 * for deletion in October 2011.</b>
208 * @since 2.0 (changed from varargs in 3.0)
209 */
210 @Deprecated
211 public
212 static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
213 E[] elements) {
214 return copyOf(elements);
215 }
216
217 /**
218 * Returns an immutable sorted set containing the given elements sorted by
219 * their natural ordering. When multiple elements are equivalent according to
220 * {@link Comparable#compareTo}, only the first one specified is included.
221 *
222 * @throws NullPointerException if any of {@code elements} is null
223 * @since 3.0
224 */
225 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
226 E[] elements) {
227 return copyOf(Ordering.natural(), Arrays.asList(elements));
228 }
229
230 /**
231 * Returns an immutable sorted set containing the given elements sorted by
232 * their natural ordering. When multiple elements are equivalent according to
233 * {@code compareTo()}, only the first one specified is included. To create a
234 * copy of a {@code SortedSet} that preserves the comparator, call {@link
235 * #copyOfSorted} instead. This method iterates over {@code elements} at most
236 * once.
237
238 *
239 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
240 * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>}
241 * containing each of the strings in {@code s}, while {@code
242 * ImmutableSortedSet.of(s)} returns an {@code
243 * ImmutableSortedSet<Set<String>>} containing one element (the given set
244 * itself).
245 *
246 * <p>Despite the method name, this method attempts to avoid actually copying
247 * the data when it is safe to do so. The exact circumstances under which a
248 * copy will or will not be performed are undocumented and subject to change.
249 *
250 * <p>This method is not type-safe, as it may be called on elements that are
251 * not mutually comparable.
252 *
253 * @throws ClassCastException if the elements are not mutually comparable
254 * @throws NullPointerException if any of {@code elements} is null
255 */
256 public static <E> ImmutableSortedSet<E> copyOf(
257 Iterable<? extends E> elements) {
258 // Hack around E not being a subtype of Comparable.
259 // Unsafe, see ImmutableSortedSetFauxverideShim.
260 @SuppressWarnings("unchecked")
261 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
262 return copyOf(naturalOrder, elements);
263 }
264
265 /**
266 * Returns an immutable sorted set containing the given elements sorted by
267 * their natural ordering. When multiple elements are equivalent according to
268 * {@code compareTo()}, only the first one specified is included. To create a
269 * copy of a {@code SortedSet} that preserves the comparator, call
270 * {@link #copyOfSorted} instead. This method iterates over {@code elements}
271 * at most once.
272 *
273 * <p>Note that if {@code s} is a {@code Set<String>}, then
274 * {@code ImmutableSortedSet.copyOf(s)} returns an
275 * {@code ImmutableSortedSet<String>} containing each of the strings in
276 * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
277 * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
278 * set itself).
279 *
280 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
281 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
282 *
283 * <p>This method is not type-safe, as it may be called on elements that are
284 * not mutually comparable.
285 *
286 * <p>This method is safe to use even when {@code elements} is a synchronized
287 * or concurrent collection that is currently being modified by another
288 * thread.
289 *
290 * @throws ClassCastException if the elements are not mutually comparable
291 * @throws NullPointerException if any of {@code elements} is null
292 * @since 7.0 (source-compatible since 2.0)
293 */
294 public static <E> ImmutableSortedSet<E> copyOf(
295 Collection<? extends E> elements) {
296 // Hack around E not being a subtype of Comparable.
297 // Unsafe, see ImmutableSortedSetFauxverideShim.
298 @SuppressWarnings("unchecked")
299 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
300 return copyOf(naturalOrder, elements);
301 }
302
303 /**
304 * Returns an immutable sorted set containing the given elements sorted by
305 * their natural ordering. When multiple elements are equivalent according to
306 * {@code compareTo()}, only the first one specified is included.
307 *
308 * <p>This method is not type-safe, as it may be called on elements that are
309 * not mutually comparable.
310 *
311 * @throws ClassCastException if the elements are not mutually comparable
312 * @throws NullPointerException if any of {@code elements} is null
313 */
314 public static <E> ImmutableSortedSet<E> copyOf(
315 Iterator<? extends E> elements) {
316 // Hack around E not being a subtype of Comparable.
317 // Unsafe, see ImmutableSortedSetFauxverideShim.
318 @SuppressWarnings("unchecked")
319 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
320 return copyOfInternal(naturalOrder, elements);
321 }
322
323 /**
324 * Returns an immutable sorted set containing the given elements sorted by
325 * the given {@code Comparator}. When multiple elements are equivalent
326 * according to {@code compareTo()}, only the first one specified is
327 * included.
328 *
329 * @throws NullPointerException if {@code comparator} or any of
330 * {@code elements} is null
331 */
332 public static <E> ImmutableSortedSet<E> copyOf(
333 Comparator<? super E> comparator, Iterator<? extends E> elements) {
334 checkNotNull(comparator);
335 return copyOfInternal(comparator, elements);
336 }
337
338 /**
339 * Returns an immutable sorted set containing the given elements sorted by
340 * the given {@code Comparator}. When multiple elements are equivalent
341 * according to {@code compare()}, only the first one specified is
342 * included. This method iterates over {@code elements} at most once.
343 *
344 * <p>Despite the method name, this method attempts to avoid actually copying
345 * the data when it is safe to do so. The exact circumstances under which a
346 * copy will or will not be performed are undocumented and subject to change.
347 *
348 * @throws NullPointerException if {@code comparator} or any of {@code
349 * elements} is null
350 */
351 public static <E> ImmutableSortedSet<E> copyOf(
352 Comparator<? super E> comparator, Iterable<? extends E> elements) {
353 checkNotNull(comparator);
354 return copyOfInternal(comparator, elements);
355 }
356
357 /**
358 * Returns an immutable sorted set containing the given elements sorted by
359 * the given {@code Comparator}. When multiple elements are equivalent
360 * according to {@code compareTo()}, only the first one specified is
361 * included.
362 *
363 * <p>Despite the method name, this method attempts to avoid actually copying
364 * the data when it is safe to do so. The exact circumstances under which a
365 * copy will or will not be performed are undocumented and subject to change.
366 *
367 * <p>This method is safe to use even when {@code elements} is a synchronized
368 * or concurrent collection that is currently being modified by another
369 * thread.
370 *
371 * @throws NullPointerException if {@code comparator} or any of
372 * {@code elements} is null
373 * @since 7.0 (source-compatible since 2.0)
374 */
375 public static <E> ImmutableSortedSet<E> copyOf(
376 Comparator<? super E> comparator, Collection<? extends E> elements) {
377 checkNotNull(comparator);
378 return copyOfInternal(comparator, elements);
379 }
380
381 /**
382 * Returns an immutable sorted set containing the elements of a sorted set,
383 * sorted by the same {@code Comparator}. That behavior differs from {@link
384 * #copyOf(Iterable)}, which always uses the natural ordering of the
385 * elements.
386 *
387 * <p>Despite the method name, this method attempts to avoid actually copying
388 * the data when it is safe to do so. The exact circumstances under which a
389 * copy will or will not be performed are undocumented and subject to change.
390 *
391 * <p>This method is safe to use even when {@code sortedSet} is a synchronized
392 * or concurrent collection that is currently being modified by another
393 * thread.
394 *
395 * @throws NullPointerException if {@code sortedSet} or any of its elements
396 * is null
397 */
398 @SuppressWarnings("unchecked")
399 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
400 Comparator<? super E> comparator = sortedSet.comparator();
401 if (comparator == null) {
402 comparator = (Comparator<? super E>) NATURAL_ORDER;
403 }
404 return copyOfInternal(comparator, sortedSet);
405 }
406
407 private static <E> ImmutableSortedSet<E> copyOfInternal(
408 Comparator<? super E> comparator, Iterable<? extends E> elements) {
409 boolean hasSameComparator =
410 SortedIterables.hasSameComparator(comparator, elements);
411
412 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
413 @SuppressWarnings("unchecked")
414 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
415 if (!original.isPartialView()) {
416 return original;
417 }
418 }
419 ImmutableList<E> list = ImmutableList.copyOf(
420 SortedIterables.sortedUnique(comparator, elements));
421 return list.isEmpty()
422 ? ImmutableSortedSet.<E>emptySet(comparator)
423 : new RegularImmutableSortedSet<E>(list, comparator);
424 }
425
426 private static <E> ImmutableSortedSet<E> copyOfInternal(
427 Comparator<? super E> comparator, Iterator<? extends E> elements) {
428 ImmutableList<E> list =
429 ImmutableList.copyOf(SortedIterables.sortedUnique(comparator, elements));
430 return list.isEmpty()
431 ? ImmutableSortedSet.<E>emptySet(comparator)
432 : new RegularImmutableSortedSet<E>(list, comparator);
433 }
434
435 /**
436 * Returns a builder that creates immutable sorted sets with an explicit
437 * comparator. If the comparator has a more general type than the set being
438 * generated, such as creating a {@code SortedSet<Integer>} with a
439 * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
440 *
441 * @throws NullPointerException if {@code comparator} is null
442 */
443 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
444 return new Builder<E>(comparator);
445 }
446
447 /**
448 * Returns a builder that creates immutable sorted sets whose elements are
449 * ordered by the reverse of their natural ordering.
450 *
451 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
452 * than {@code Comparable<? super E>} as a workaround for javac <a
453 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
454 * 6468354</a>.
455 */
456 public static <E extends Comparable<E>> Builder<E> reverseOrder() {
457 return new Builder<E>(Ordering.natural().reverse());
458 }
459
460 /**
461 * Returns a builder that creates immutable sorted sets whose elements are
462 * ordered by their natural ordering. The sorted sets use {@link
463 * Ordering#natural()} as the comparator. This method provides more
464 * type-safety than {@link #builder}, as it can be called only for classes
465 * that implement {@link Comparable}.
466 *
467 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
468 * than {@code Comparable<? super E>} as a workaround for javac <a
469 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
470 * 6468354</a>.
471 */
472 public static <E extends Comparable<E>> Builder<E> naturalOrder() {
473 return new Builder<E>(Ordering.natural());
474 }
475
476 /**
477 * A builder for creating immutable sorted set instances, especially {@code
478 * public static final} sets ("constant sets"), with a given comparator.
479 * Example: <pre> {@code
480 *
481 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
482 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
483 * .addAll(SINGLE_DIGIT_PRIMES)
484 * .add(42)
485 * .build();}</pre>
486 *
487 * Builder instances can be reused; it is safe to call {@link #build} multiple
488 * times to build multiple sets in series. Each set is a superset of the set
489 * created before it.
490 *
491 * @since 2.0 (imported from Google Collections Library)
492 */
493 public static final class Builder<E> extends ImmutableSet.Builder<E> {
494 private final Comparator<? super E> comparator;
495
496 /**
497 * Creates a new builder. The returned builder is equivalent to the builder
498 * generated by {@link ImmutableSortedSet#orderedBy}.
499 */
500 public Builder(Comparator<? super E> comparator) {
501 this.comparator = checkNotNull(comparator);
502 }
503
504 /**
505 * Adds {@code element} to the {@code ImmutableSortedSet}. If the
506 * {@code ImmutableSortedSet} already contains {@code element}, then
507 * {@code add} has no effect. (only the previously added element
508 * is retained).
509 *
510 * @param element the element to add
511 * @return this {@code Builder} object
512 * @throws NullPointerException if {@code element} is null
513 */
514 @Override public Builder<E> add(E element) {
515 super.add(element);
516 return this;
517 }
518
519 /**
520 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
521 * ignoring duplicate elements (only the first duplicate element is added).
522 *
523 * @param elements the elements to add
524 * @return this {@code Builder} object
525 * @throws NullPointerException if {@code elements} contains a null element
526 */
527 @Override public Builder<E> add(E... elements) {
528 super.add(elements);
529 return this;
530 }
531
532 /**
533 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
534 * ignoring duplicate elements (only the first duplicate element is added).
535 *
536 * @param elements the elements to add to the {@code ImmutableSortedSet}
537 * @return this {@code Builder} object
538 * @throws NullPointerException if {@code elements} contains a null element
539 */
540 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
541 super.addAll(elements);
542 return this;
543 }
544
545 /**
546 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
547 * ignoring duplicate elements (only the first duplicate element is added).
548 *
549 * @param elements the elements to add to the {@code ImmutableSortedSet}
550 * @return this {@code Builder} object
551 * @throws NullPointerException if {@code elements} contains a null element
552 */
553 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
554 super.addAll(elements);
555 return this;
556 }
557
558 /**
559 * Returns a newly-created {@code ImmutableSortedSet} based on the contents
560 * of the {@code Builder} and its comparator.
561 */
562 @Override public ImmutableSortedSet<E> build() {
563 return copyOfInternal(comparator, contents.iterator());
564 }
565 }
566
567 int unsafeCompare(Object a, Object b) {
568 return unsafeCompare(comparator, a, b);
569 }
570
571 static int unsafeCompare(
572 Comparator<?> comparator, Object a, Object b) {
573 // Pretend the comparator can compare anything. If it turns out it can't
574 // compare a and b, we should get a CCE on the subsequent line. Only methods
575 // that are spec'd to throw CCE should call this.
576 @SuppressWarnings("unchecked")
577 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
578 return unsafeComparator.compare(a, b);
579 }
580
581 final transient Comparator<? super E> comparator;
582
583 ImmutableSortedSet(Comparator<? super E> comparator) {
584 this.comparator = comparator;
585 }
586
587 /**
588 * Returns the comparator that orders the elements, which is
589 * {@link Ordering#natural()} when the natural ordering of the
590 * elements is used. Note that its behavior is not consistent with
591 * {@link SortedSet#comparator()}, which returns {@code null} to indicate
592 * natural ordering.
593 */
594 @Override
595 public Comparator<? super E> comparator() {
596 return comparator;
597 }
598
599 @Override // needed to unify the iterator() methods in Collection and SortedIterable
600 public abstract UnmodifiableIterator<E> iterator();
601
602 /**
603 * {@inheritDoc}
604 *
605 * <p>This method returns a serializable {@code ImmutableSortedSet}.
606 *
607 * <p>The {@link SortedSet#headSet} documentation states that a subset of a
608 * subset throws an {@link IllegalArgumentException} if passed a
609 * {@code toElement} greater than an earlier {@code toElement}. However, this
610 * method doesn't throw an exception in that situation, but instead keeps the
611 * original {@code toElement}.
612 */
613 @Override
614 public ImmutableSortedSet<E> headSet(E toElement) {
615 return headSet(toElement, false);
616 }
617
618 ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
619 return headSetImpl(checkNotNull(toElement), inclusive);
620 }
621
622 /**
623 * {@inheritDoc}
624 *
625 * <p>This method returns a serializable {@code ImmutableSortedSet}.
626 *
627 * <p>The {@link SortedSet#subSet} 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}. Similarly, this method keeps the
632 * original {@code toElement}, instead of throwing an exception, if passed a
633 * {@code toElement} greater than an earlier {@code toElement}.
634 */
635 @Override
636 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
637 return subSet(fromElement, true, toElement, false);
638 }
639
640 ImmutableSortedSet<E> subSet(
641 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
642 checkNotNull(fromElement);
643 checkNotNull(toElement);
644 checkArgument(comparator.compare(fromElement, toElement) <= 0);
645 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
646 }
647
648 /**
649 * {@inheritDoc}
650 *
651 * <p>This method returns a serializable {@code ImmutableSortedSet}.
652 *
653 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
654 * subset throws an {@link IllegalArgumentException} if passed a
655 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
656 * this method doesn't throw an exception in that situation, but instead keeps
657 * the original {@code fromElement}.
658 */
659 @Override
660 public ImmutableSortedSet<E> tailSet(E fromElement) {
661 return tailSet(fromElement, true);
662 }
663
664 ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
665 return tailSetImpl(checkNotNull(fromElement), inclusive);
666 }
667
668 /*
669 * These methods perform most headSet, subSet, and tailSet logic, besides
670 * parameter validation.
671 */
672 abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
673
674 abstract ImmutableSortedSet<E> subSetImpl(
675 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
676
677 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
678
679 /**
680 * Returns the position of an element within the set, or -1 if not present.
681 */
682 abstract int indexOf(@Nullable Object target);
683
684 /*
685 * This class is used to serialize all ImmutableSortedSet instances,
686 * regardless of implementation type. It captures their "logical contents"
687 * only. This is necessary to ensure that the existence of a particular
688 * implementation type is an implementation detail.
689 */
690 private static class SerializedForm<E> implements Serializable {
691 final Comparator<? super E> comparator;
692 final Object[] elements;
693
694 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
695 this.comparator = comparator;
696 this.elements = elements;
697 }
698
699 @SuppressWarnings("unchecked")
700 Object readResolve() {
701 return new Builder<E>(comparator).add((E[]) elements).build();
702 }
703
704 private static final long serialVersionUID = 0;
705 }
706
707 private void readObject(ObjectInputStream stream)
708 throws InvalidObjectException {
709 throw new InvalidObjectException("Use SerializedForm");
710 }
711
712 @Override Object writeReplace() {
713 return new SerializedForm<E>(comparator, toArray());
714 }
715 }