1 /*
2 * Copyright (C) 2008 The Guava Authors
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 import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25
26 import java.io.InvalidObjectException;
27 import java.io.ObjectInputStream;
28 import java.io.Serializable;
29 import java.util.Arrays;
30 import java.util.Collection;
31 import java.util.Collections;
32 import java.util.Comparator;
33 import java.util.Iterator;
34 import java.util.NavigableSet;
35 import java.util.SortedSet;
36
37 import javax.annotation.Nullable;
38
39 /**
40 * An immutable {@code SortedSet} that stores its elements in a sorted array.
41 * Some instances are ordered by an explicit comparator, while others follow the
42 * natural sort ordering of their elements. Either way, null elements are not
43 * supported.
44 *
45 * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i>
46 * of a separate collection that can still change, an instance of {@code
47 * ImmutableSortedSet} contains its own private data and will <i>never</i>
48 * change. This class is convenient for {@code public static final} sets
49 * ("constant sets") and also lets you easily make a "defensive copy" of a set
50 * provided to your class by a caller.
51 *
52 * <p>The sets returned by the {@link #headSet}, {@link #tailSet}, and
53 * {@link #subSet} methods share the same array as the original set, preventing
54 * that array from being garbage collected. If this is a concern, the data may
55 * be copied into a correctly-sized array by calling {@link #copyOfSorted}.
56 *
57 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
58 * {@link #containsAll(Collection)}, and {@link #equals(Object)}
59 * implementations must check whether a provided object is equivalent to an
60 * element in the collection. Unlike most collections, an
61 * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if
62 * two elements are equivalent. Instead, with an explicit comparator, the
63 * following relation determines whether elements {@code x} and {@code y} are
64 * equivalent: <pre> {@code
65 *
66 * {(x, y) | comparator.compare(x, y) == 0}}</pre>
67 *
68 * <p>With natural ordering of elements, the following relation determines whether
69 * two elements are equivalent: <pre> {@code
70 *
71 * {(x, y) | x.compareTo(y) == 0}}</pre>
72 *
73 * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not
74 * function correctly if an element is modified after being placed in the set.
75 * For this reason, and to avoid general confusion, it is strongly recommended
76 * to place only immutable objects into this collection.
77 *
78 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
79 * it has no public or protected constructors. Thus, instances of this type are
80 * guaranteed to be immutable.
81 *
82 * <p>See the Guava User Guide article on <a href=
83 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
84 * immutable collections</a>.
85 *
86 * @see ImmutableSet
87 * @author Jared Levy
88 * @author Louis Wasserman
89 * @since 2.0 (imported from Google Collections Library; implements {@code NavigableSet} since 12.0)
90 */
91 // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
92 @GwtCompatible(serializable = true, emulated = true)
93 @SuppressWarnings("serial") // we're overriding default serialization
94 public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
95 implements NavigableSet<E>, SortedIterable<E> {
96
97 private static final Comparator<Comparable> NATURAL_ORDER =
98 Ordering.natural();
99
100 private static final ImmutableSortedSet<Comparable> NATURAL_EMPTY_SET =
101 new EmptyImmutableSortedSet<Comparable>(NATURAL_ORDER);
102
103 @SuppressWarnings("unchecked")
104 private static <E> ImmutableSortedSet<E> emptySet() {
105 return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET;
106 }
107
108 static <E> ImmutableSortedSet<E> emptySet(
109 Comparator<? super E> comparator) {
110 if (NATURAL_ORDER.equals(comparator)) {
111 return emptySet();
112 } else {
113 return new EmptyImmutableSortedSet<E>(comparator);
114 }
115 }
116
117 /**
118 * Returns the empty immutable sorted set.
119 */
120 public static <E> ImmutableSortedSet<E> of() {
121 return emptySet();
122 }
123
124 /**
125 * Returns an immutable sorted set containing a single element.
126 */
127 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
128 E element) {
129 return new RegularImmutableSortedSet<E>(
130 ImmutableList.of(element), Ordering.natural());
131 }
132
133 /**
134 * Returns an immutable sorted set containing the given elements sorted by
135 * their natural ordering. When multiple elements are equivalent according to
136 * {@link Comparable#compareTo}, only the first one specified is included.
137 *
138 * @throws NullPointerException if any element is null
139 */
140 @SuppressWarnings("unchecked")
141 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
142 E e1, E e2) {
143 return construct(Ordering.natural(), 2, e1, e2);
144 }
145
146 /**
147 * Returns an immutable sorted set containing the given elements sorted by
148 * their natural ordering. When multiple elements are equivalent according to
149 * {@link Comparable#compareTo}, only the first one specified is included.
150 *
151 * @throws NullPointerException if any element is null
152 */
153 @SuppressWarnings("unchecked")
154 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
155 E e1, E e2, E e3) {
156 return construct(Ordering.natural(), 3, e1, e2, e3);
157 }
158
159 /**
160 * Returns an immutable sorted set containing the given elements sorted by
161 * their natural ordering. When multiple elements are equivalent according to
162 * {@link Comparable#compareTo}, only the first one specified is included.
163 *
164 * @throws NullPointerException if any element is null
165 */
166 @SuppressWarnings("unchecked")
167 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
168 E e1, E e2, E e3, E e4) {
169 return construct(Ordering.natural(), 4, e1, e2, e3, e4);
170 }
171
172 /**
173 * Returns an immutable sorted set containing the given elements sorted by
174 * their natural ordering. When multiple elements are equivalent according to
175 * {@link Comparable#compareTo}, only the first one specified is included.
176 *
177 * @throws NullPointerException if any element is null
178 */
179 @SuppressWarnings("unchecked")
180 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
181 E e1, E e2, E e3, E e4, E e5) {
182 return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5);
183 }
184
185 /**
186 * Returns an immutable sorted set containing the given elements sorted by
187 * their natural ordering. When multiple elements are equivalent according to
188 * {@link Comparable#compareTo}, only the first one specified is included.
189 *
190 * @throws NullPointerException if any element is null
191 * @since 3.0 (source-compatible since 2.0)
192 */
193 @SuppressWarnings("unchecked")
194 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
195 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
196 Comparable[] contents = new Comparable[6 + remaining.length];
197 contents[0] = e1;
198 contents[1] = e2;
199 contents[2] = e3;
200 contents[3] = e4;
201 contents[4] = e5;
202 contents[5] = e6;
203 System.arraycopy(remaining, 0, contents, 6, remaining.length);
204 return construct(Ordering.natural(), contents.length, (E[]) contents);
205 }
206
207 // TODO(kevinb): Consider factory methods that reject duplicates
208
209 /**
210 * Returns an immutable sorted set containing the given elements sorted by
211 * their natural ordering. When multiple elements are equivalent according to
212 * {@link Comparable#compareTo}, only the first one specified is included.
213 *
214 * @throws NullPointerException if any of {@code elements} is null
215 * @since 3.0
216 */
217 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
218 E[] elements) {
219 return construct(Ordering.natural(), elements.length, elements.clone());
220 }
221
222 /**
223 * Returns an immutable sorted set containing the given elements sorted by
224 * their natural ordering. When multiple elements are equivalent according to
225 * {@code compareTo()}, only the first one specified is included. To create a
226 * copy of a {@code SortedSet} that preserves the comparator, call {@link
227 * #copyOfSorted} instead. This method iterates over {@code elements} at most
228 * once.
229
230 *
231 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
232 * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>}
233 * containing each of the strings in {@code s}, while {@code
234 * ImmutableSortedSet.of(s)} returns an {@code
235 * ImmutableSortedSet<Set<String>>} containing one element (the given set
236 * itself).
237 *
238 * <p>Despite the method name, this method attempts to avoid actually copying
239 * the data when it is safe to do so. The exact circumstances under which a
240 * copy will or will not be performed are undocumented and subject to change.
241 *
242 * <p>This method is not type-safe, as it may be called on elements that are
243 * not mutually comparable.
244 *
245 * @throws ClassCastException if the elements are not mutually comparable
246 * @throws NullPointerException if any of {@code elements} is null
247 */
248 public static <E> ImmutableSortedSet<E> copyOf(
249 Iterable<? extends E> elements) {
250 // Hack around E not being a subtype of Comparable.
251 // Unsafe, see ImmutableSortedSetFauxverideShim.
252 @SuppressWarnings("unchecked")
253 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
254 return copyOf(naturalOrder, elements);
255 }
256
257 /**
258 * Returns an immutable sorted set containing the given elements sorted by
259 * their natural ordering. When multiple elements are equivalent according to
260 * {@code compareTo()}, only the first one specified is included. To create a
261 * copy of a {@code SortedSet} that preserves the comparator, call
262 * {@link #copyOfSorted} instead. This method iterates over {@code elements}
263 * at most once.
264 *
265 * <p>Note that if {@code s} is a {@code Set<String>}, then
266 * {@code ImmutableSortedSet.copyOf(s)} returns an
267 * {@code ImmutableSortedSet<String>} containing each of the strings in
268 * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
269 * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
270 * set itself).
271 *
272 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
273 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
274 *
275 * <p>This method is not type-safe, as it may be called on elements that are
276 * not mutually comparable.
277 *
278 * <p>This method is safe to use even when {@code elements} is a synchronized
279 * or concurrent collection that is currently being modified by another
280 * thread.
281 *
282 * @throws ClassCastException if the elements are not mutually comparable
283 * @throws NullPointerException if any of {@code elements} is null
284 * @since 7.0 (source-compatible since 2.0)
285 */
286 public static <E> ImmutableSortedSet<E> copyOf(
287 Collection<? extends E> elements) {
288 // Hack around E not being a subtype of Comparable.
289 // Unsafe, see ImmutableSortedSetFauxverideShim.
290 @SuppressWarnings("unchecked")
291 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
292 return copyOf(naturalOrder, elements);
293 }
294
295 /**
296 * Returns an immutable sorted set containing the given elements sorted by
297 * their natural ordering. When multiple elements are equivalent according to
298 * {@code compareTo()}, only the first one specified is included.
299 *
300 * <p>This method is not type-safe, as it may be called on elements that are
301 * not mutually comparable.
302 *
303 * @throws ClassCastException if the elements are not mutually comparable
304 * @throws NullPointerException if any of {@code elements} is null
305 */
306 public static <E> ImmutableSortedSet<E> copyOf(
307 Iterator<? extends E> elements) {
308 // Hack around E not being a subtype of Comparable.
309 // Unsafe, see ImmutableSortedSetFauxverideShim.
310 @SuppressWarnings("unchecked")
311 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
312 return copyOf(naturalOrder, elements);
313 }
314
315 /**
316 * Returns an immutable sorted set containing the given elements sorted by
317 * the given {@code Comparator}. When multiple elements are equivalent
318 * according to {@code compareTo()}, only the first one specified is
319 * included.
320 *
321 * @throws NullPointerException if {@code comparator} or any of
322 * {@code elements} is null
323 */
324 public static <E> ImmutableSortedSet<E> copyOf(
325 Comparator<? super E> comparator, Iterator<? extends E> elements) {
326 return new Builder<E>(comparator).addAll(elements).build();
327 }
328
329 /**
330 * Returns an immutable sorted set containing the given elements sorted by
331 * the given {@code Comparator}. When multiple elements are equivalent
332 * according to {@code compare()}, only the first one specified is
333 * included. This method iterates over {@code elements} at most once.
334 *
335 * <p>Despite the method name, this method attempts to avoid actually copying
336 * the data when it is safe to do so. The exact circumstances under which a
337 * copy will or will not be performed are undocumented and subject to change.
338 *
339 * @throws NullPointerException if {@code comparator} or any of {@code
340 * elements} is null
341 */
342 public static <E> ImmutableSortedSet<E> copyOf(
343 Comparator<? super E> comparator, Iterable<? extends E> elements) {
344 checkNotNull(comparator);
345 boolean hasSameComparator =
346 SortedIterables.hasSameComparator(comparator, elements);
347
348 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
349 @SuppressWarnings("unchecked")
350 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
351 if (!original.isPartialView()) {
352 return original;
353 }
354 }
355 @SuppressWarnings("unchecked") // elements only contains E's; it's safe.
356 E[] array = (E[]) Iterables.toArray(elements);
357 return construct(comparator, array.length, array);
358 }
359
360 /**
361 * Returns an immutable sorted set containing the given elements sorted by
362 * the given {@code Comparator}. When multiple elements are equivalent
363 * according to {@code compareTo()}, only the first one specified is
364 * included.
365 *
366 * <p>Despite the method name, this method attempts to avoid actually copying
367 * the data when it is safe to do so. The exact circumstances under which a
368 * copy will or will not be performed are undocumented and subject to change.
369 *
370 * <p>This method is safe to use even when {@code elements} is a synchronized
371 * or concurrent collection that is currently being modified by another
372 * thread.
373 *
374 * @throws NullPointerException if {@code comparator} or any of
375 * {@code elements} is null
376 * @since 7.0 (source-compatible since 2.0)
377 */
378 public static <E> ImmutableSortedSet<E> copyOf(
379 Comparator<? super E> comparator, Collection<? extends E> elements) {
380 return copyOf(comparator, (Iterable<? extends E>) elements);
381 }
382
383 /**
384 * Returns an immutable sorted set containing the elements of a sorted set,
385 * sorted by the same {@code Comparator}. That behavior differs from {@link
386 * #copyOf(Iterable)}, which always uses the natural ordering of the
387 * elements.
388 *
389 * <p>Despite the method name, this method attempts to avoid actually copying
390 * the data when it is safe to do so. The exact circumstances under which a
391 * copy will or will not be performed are undocumented and subject to change.
392 *
393 * <p>This method is safe to use even when {@code sortedSet} is a synchronized
394 * or concurrent collection that is currently being modified by another
395 * thread.
396 *
397 * @throws NullPointerException if {@code sortedSet} or any of its elements
398 * is null
399 */
400 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
401 Comparator<? super E> comparator = SortedIterables.comparator(sortedSet);
402 ImmutableList<E> list = ImmutableList.copyOf(sortedSet);
403 if (list.isEmpty()) {
404 return emptySet(comparator);
405 } else {
406 return new RegularImmutableSortedSet<E>(list, comparator);
407 }
408 }
409
410 /**
411 * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of
412 * {@code contents}. If {@code k} is the size of the returned {@code ImmutableSortedSet}, then
413 * the sorted unique elements are in the first {@code k} positions of {@code contents}, and
414 * {@code contents[i] == null} for {@code k <= i < n}.
415 *
416 * <p>If {@code k == contents.length}, then {@code contents} may no longer be safe for
417 * modification.
418 *
419 * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is
420 * null
421 */
422 static <E> ImmutableSortedSet<E> construct(
423 Comparator<? super E> comparator, int n, E... contents) {
424 if (n == 0) {
425 return emptySet(comparator);
426 }
427 checkElementsNotNull(contents, n);
428 Arrays.sort(contents, 0, n, comparator);
429 int uniques = 1;
430 for (int i = 1; i < n; i++) {
431 E cur = contents[i];
432 E prev = contents[uniques - 1];
433 if (comparator.compare(cur, prev) != 0) {
434 contents[uniques++] = cur;
435 }
436 }
437 Arrays.fill(contents, uniques, n, null);
438 return new RegularImmutableSortedSet<E>(
439 ImmutableList.<E>asImmutableList(contents, uniques), comparator);
440 }
441
442 /**
443 * Returns a builder that creates immutable sorted sets with an explicit
444 * comparator. If the comparator has a more general type than the set being
445 * generated, such as creating a {@code SortedSet<Integer>} with a
446 * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
447 *
448 * @throws NullPointerException if {@code comparator} is null
449 */
450 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
451 return new Builder<E>(comparator);
452 }
453
454 /**
455 * Returns a builder that creates immutable sorted sets whose elements are
456 * ordered by the reverse of their natural ordering.
457 */
458 public static <E extends Comparable<?>> Builder<E> reverseOrder() {
459 return new Builder<E>(Ordering.natural().reverse());
460 }
461
462 /**
463 * Returns a builder that creates immutable sorted sets whose elements are
464 * ordered by their natural ordering. The sorted sets use {@link
465 * Ordering#natural()} as the comparator. This method provides more
466 * type-safety than {@link #builder}, as it can be called only for classes
467 * that implement {@link Comparable}.
468 */
469 public static <E extends Comparable<?>> Builder<E> naturalOrder() {
470 return new Builder<E>(Ordering.natural());
471 }
472
473 /**
474 * A builder for creating immutable sorted set instances, especially {@code
475 * public static final} sets ("constant sets"), with a given comparator.
476 * Example: <pre> {@code
477 *
478 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
479 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
480 * .addAll(SINGLE_DIGIT_PRIMES)
481 * .add(42)
482 * .build();}</pre>
483 *
484 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
485 * times to build multiple sets in series. Each set is a superset of the set
486 * created before it.
487 *
488 * @since 2.0 (imported from Google Collections Library)
489 */
490 public static final class Builder<E> extends ImmutableSet.Builder<E> {
491 private final Comparator<? super E> comparator;
492
493 /**
494 * Creates a new builder. The returned builder is equivalent to the builder
495 * generated by {@link ImmutableSortedSet#orderedBy}.
496 */
497 public Builder(Comparator<? super E> comparator) {
498 this.comparator = checkNotNull(comparator);
499 }
500
501 /**
502 * Adds {@code element} to the {@code ImmutableSortedSet}. If the
503 * {@code ImmutableSortedSet} already contains {@code element}, then
504 * {@code add} has no effect. (only the previously added element
505 * is retained).
506 *
507 * @param element the element to add
508 * @return this {@code Builder} object
509 * @throws NullPointerException if {@code element} is null
510 */
511 @Override public Builder<E> add(E element) {
512 super.add(element);
513 return this;
514 }
515
516 /**
517 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
518 * ignoring duplicate elements (only the first duplicate element is added).
519 *
520 * @param elements the elements to add
521 * @return this {@code Builder} object
522 * @throws NullPointerException if {@code elements} contains a null element
523 */
524 @Override public Builder<E> add(E... elements) {
525 super.add(elements);
526 return this;
527 }
528
529 /**
530 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
531 * ignoring duplicate elements (only the first duplicate element is added).
532 *
533 * @param elements the elements to add to the {@code ImmutableSortedSet}
534 * @return this {@code Builder} object
535 * @throws NullPointerException if {@code elements} contains a null element
536 */
537 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
538 super.addAll(elements);
539 return this;
540 }
541
542 /**
543 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
544 * ignoring duplicate elements (only the first duplicate element is added).
545 *
546 * @param elements the elements to add to the {@code ImmutableSortedSet}
547 * @return this {@code Builder} object
548 * @throws NullPointerException if {@code elements} contains a null element
549 */
550 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
551 super.addAll(elements);
552 return this;
553 }
554
555 /**
556 * Returns a newly-created {@code ImmutableSortedSet} based on the contents
557 * of the {@code Builder} and its comparator.
558 */
559 @Override public ImmutableSortedSet<E> build() {
560 @SuppressWarnings("unchecked") // we're careful to put only E's in here
561 E[] contentsArray = (E[]) contents;
562 ImmutableSortedSet<E> result = construct(comparator, size, contentsArray);
563 this.size = result.size(); // we eliminated duplicates in-place in contentsArray
564 return result;
565 }
566 }
567
568 int unsafeCompare(Object a, Object b) {
569 return unsafeCompare(comparator, a, b);
570 }
571
572 static int unsafeCompare(
573 Comparator<?> comparator, Object a, Object b) {
574 // Pretend the comparator can compare anything. If it turns out it can't
575 // compare a and b, we should get a CCE on the subsequent line. Only methods
576 // that are spec'd to throw CCE should call this.
577 @SuppressWarnings("unchecked")
578 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
579 return unsafeComparator.compare(a, b);
580 }
581
582 final transient Comparator<? super E> comparator;
583
584 ImmutableSortedSet(Comparator<? super E> comparator) {
585 this.comparator = comparator;
586 }
587
588 /**
589 * Returns the comparator that orders the elements, which is
590 * {@link Ordering#natural()} when the natural ordering of the
591 * elements is used. Note that its behavior is not consistent with
592 * {@link SortedSet#comparator()}, which returns {@code null} to indicate
593 * natural ordering.
594 */
595 @Override
596 public Comparator<? super E> comparator() {
597 return comparator;
598 }
599
600 @Override // needed to unify the iterator() methods in Collection and SortedIterable
601 public abstract UnmodifiableIterator<E> iterator();
602
603 /**
604 * {@inheritDoc}
605 *
606 * <p>This method returns a serializable {@code ImmutableSortedSet}.
607 *
608 * <p>The {@link SortedSet#headSet} documentation states that a subset of a
609 * subset throws an {@link IllegalArgumentException} if passed a
610 * {@code toElement} greater than an earlier {@code toElement}. However, this
611 * method doesn't throw an exception in that situation, but instead keeps the
612 * original {@code toElement}.
613 */
614 @Override
615 public ImmutableSortedSet<E> headSet(E toElement) {
616 return headSet(toElement, false);
617 }
618
619 /**
620 * @since 12.0
621 */
622 @GwtIncompatible("NavigableSet")
623 @Override
624 public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
625 return headSetImpl(checkNotNull(toElement), inclusive);
626 }
627
628 /**
629 * {@inheritDoc}
630 *
631 * <p>This method returns a serializable {@code ImmutableSortedSet}.
632 *
633 * <p>The {@link SortedSet#subSet} documentation states that a subset of a
634 * subset throws an {@link IllegalArgumentException} if passed a
635 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
636 * this method doesn't throw an exception in that situation, but instead keeps
637 * the original {@code fromElement}. Similarly, this method keeps the
638 * original {@code toElement}, instead of throwing an exception, if passed a
639 * {@code toElement} greater than an earlier {@code toElement}.
640 */
641 @Override
642 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
643 return subSet(fromElement, true, toElement, false);
644 }
645
646 /**
647 * @since 12.0
648 */
649 @GwtIncompatible("NavigableSet")
650 @Override
651 public ImmutableSortedSet<E> subSet(
652 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
653 checkNotNull(fromElement);
654 checkNotNull(toElement);
655 checkArgument(comparator.compare(fromElement, toElement) <= 0);
656 return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
657 }
658
659 /**
660 * {@inheritDoc}
661 *
662 * <p>This method returns a serializable {@code ImmutableSortedSet}.
663 *
664 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
665 * subset throws an {@link IllegalArgumentException} if passed a
666 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
667 * this method doesn't throw an exception in that situation, but instead keeps
668 * the original {@code fromElement}.
669 */
670 @Override
671 public ImmutableSortedSet<E> tailSet(E fromElement) {
672 return tailSet(fromElement, true);
673 }
674
675 /**
676 * @since 12.0
677 */
678 @GwtIncompatible("NavigableSet")
679 @Override
680 public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
681 return tailSetImpl(checkNotNull(fromElement), inclusive);
682 }
683
684 /*
685 * These methods perform most headSet, subSet, and tailSet logic, besides
686 * parameter validation.
687 */
688 abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
689
690 abstract ImmutableSortedSet<E> subSetImpl(
691 E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
692
693 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
694
695 /**
696 * @since 12.0
697 */
698 @GwtIncompatible("NavigableSet")
699 @Override
700 public E lower(E e) {
701 return Iterators.getNext(headSet(e, false).descendingIterator(), null);
702 }
703
704 /**
705 * @since 12.0
706 */
707 @GwtIncompatible("NavigableSet")
708 @Override
709 public E floor(E e) {
710 return Iterators.getNext(headSet(e, true).descendingIterator(), null);
711 }
712
713 /**
714 * @since 12.0
715 */
716 @GwtIncompatible("NavigableSet")
717 @Override
718 public E ceiling(E e) {
719 return Iterables.getFirst(tailSet(e, true), null);
720 }
721
722 /**
723 * @since 12.0
724 */
725 @GwtIncompatible("NavigableSet")
726 @Override
727 public E higher(E e) {
728 return Iterables.getFirst(tailSet(e, false), null);
729 }
730
731 @Override
732 public E first() {
733 return iterator().next();
734 }
735
736 @Override
737 public E last() {
738 return descendingIterator().next();
739 }
740
741 /**
742 * Guaranteed to throw an exception and leave the set unmodified.
743 *
744 * @since 12.0
745 * @throws UnsupportedOperationException always
746 * @deprecated Unsupported operation.
747 */
748 @Deprecated
749 @GwtIncompatible("NavigableSet")
750 @Override
751 public final E pollFirst() {
752 throw new UnsupportedOperationException();
753 }
754
755 /**
756 * Guaranteed to throw an exception and leave the set unmodified.
757 *
758 * @since 12.0
759 * @throws UnsupportedOperationException always
760 * @deprecated Unsupported operation.
761 */
762 @Deprecated
763 @GwtIncompatible("NavigableSet")
764 @Override
765 public final E pollLast() {
766 throw new UnsupportedOperationException();
767 }
768
769 @GwtIncompatible("NavigableSet")
770 transient ImmutableSortedSet<E> descendingSet;
771
772 /**
773 * @since 12.0
774 */
775 @GwtIncompatible("NavigableSet")
776 @Override
777 public ImmutableSortedSet<E> descendingSet() {
778 // racy single-check idiom
779 ImmutableSortedSet<E> result = descendingSet;
780 if (result == null) {
781 result = descendingSet = createDescendingSet();
782 result.descendingSet = this;
783 }
784 return result;
785 }
786
787 @GwtIncompatible("NavigableSet")
788 ImmutableSortedSet<E> createDescendingSet() {
789 return new DescendingImmutableSortedSet<E>(this);
790 }
791
792 /**
793 * @since 12.0
794 */
795 @GwtIncompatible("NavigableSet")
796 @Override
797 public abstract UnmodifiableIterator<E> descendingIterator();
798
799 /**
800 * Returns the position of an element within the set, or -1 if not present.
801 */
802 abstract int indexOf(@Nullable Object target);
803
804 /*
805 * This class is used to serialize all ImmutableSortedSet instances,
806 * regardless of implementation type. It captures their "logical contents"
807 * only. This is necessary to ensure that the existence of a particular
808 * implementation type is an implementation detail.
809 */
810 private static class SerializedForm<E> implements Serializable {
811 final Comparator<? super E> comparator;
812 final Object[] elements;
813
814 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
815 this.comparator = comparator;
816 this.elements = elements;
817 }
818
819 @SuppressWarnings("unchecked")
820 Object readResolve() {
821 return new Builder<E>(comparator).add((E[]) elements).build();
822 }
823
824 private static final long serialVersionUID = 0;
825 }
826
827 private void readObject(ObjectInputStream stream)
828 throws InvalidObjectException {
829 throw new InvalidObjectException("Use SerializedForm");
830 }
831
832 @Override Object writeReplace() {
833 return new SerializedForm<E>(comparator, toArray());
834 }
835 }
836