001 /*
002 * Copyright (C) 2008 Google Inc.
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.Beta;
023 import com.google.common.annotations.GwtCompatible;
024
025 import java.io.InvalidObjectException;
026 import java.io.ObjectInputStream;
027 import java.io.Serializable;
028 import java.util.ArrayList;
029 import java.util.Arrays;
030 import java.util.Collection;
031 import java.util.Collections;
032 import java.util.Comparator;
033 import java.util.Iterator;
034 import java.util.List;
035 import java.util.SortedSet;
036
037 /**
038 * An immutable {@code SortedSet} that stores its elements in a sorted array.
039 * Some instances are ordered by an explicit comparator, while others follow the
040 * natural sort ordering of their elements. Either way, null elements are not
041 * supported.
042 *
043 * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i>
044 * of a separate collection that can still change, an instance of {@code
045 * ImmutableSortedSet} contains its own private data and will <i>never</i>
046 * change. This class is convenient for {@code public static final} sets
047 * ("constant sets") and also lets you easily make a "defensive copy" of a set
048 * provided to your class by a caller.
049 *
050 * <p>The sets returned by {@link #headSet}, {@link #tailSet}, and
051 * {@link #subSet} methods share the same array as the original set, preventing
052 * that array from being garbage collected. If this is a concern, the data may
053 * be copied into a correctly-sized array by calling {@link #copyOfSorted}.
054 *
055 * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
056 * {@link #containsAll(Collection)}, and {@link #equals(Object)}
057 * implementations must check whether a provided object is equivalent to an
058 * element in the collection. Unlike most collections, an
059 * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if
060 * two elements are equivalent. Instead, with an explicit comparator, the
061 * following relation determines whether elements {@code x} and {@code y} are
062 * equivalent: <pre> {@code
063 *
064 * {(x, y) | comparator.compare(x, y) == 0}}</pre>
065 *
066 * With natural ordering of elements, the following relation determines whether
067 * two elements are equivalent: <pre> {@code
068 *
069 * {(x, y) | x.compareTo(y) == 0}}</pre>
070 *
071 * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not
072 * function correctly if an element is modified after being placed in the set.
073 * For this reason, and to avoid general confusion, it is strongly recommended
074 * to place only immutable objects into this collection.
075 *
076 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
077 * it has no public or protected constructors. Thus, instances of this type are
078 * guaranteed to be immutable.
079 *
080 * @see ImmutableSet
081 * @author Jared Levy
082 * @since 2 (imported from Google Collections Library)
083 */
084 // TODO: benchmark and optimize all creation paths, which are a mess right now
085 @GwtCompatible(serializable = true, emulated = true)
086 @SuppressWarnings("serial") // we're overriding default serialization
087 public abstract class ImmutableSortedSet<E>
088 extends ImmutableSortedSetFauxverideShim<E> implements SortedSet<E> {
089
090 // TODO: Can we find a way to remove this @SuppressWarnings even for eclipse?
091 @SuppressWarnings("unchecked")
092 private static final Comparator NATURAL_ORDER = Ordering.natural();
093
094 @SuppressWarnings("unchecked")
095 private static final ImmutableSortedSet<Object> NATURAL_EMPTY_SET =
096 new EmptyImmutableSortedSet<Object>(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 Object[] array = { checkNotNull(element) };
125 return new RegularImmutableSortedSet<E>(array, 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 ofInternal(Ordering.natural(), 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 ofInternal(Ordering.natural(), 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 ofInternal(Ordering.natural(), 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 ofInternal(Ordering.natural(), 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 (source-compatible since release 2)
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 // This is a mess (see TODO at top of file)
196 return ofInternal(Ordering.natural(),
197 (Object[]) all.toArray(new Comparable[0]));
198 }
199
200 // TODO: Consider adding factory methods that throw an exception when given
201 // duplicate elements.
202
203 /**
204 * Returns an immutable sorted set containing the given elements sorted by
205 * their natural ordering. When multiple elements are equivalent according to
206 * {@link Comparable#compareTo}, only the first one specified is included.
207 *
208 * @throws NullPointerException if any of {@code elements} is null
209 * @deprecated use {@link #copyOf(Comparable[])}.
210 * @since 2 (changed from varargs in release 3)
211 */
212 @Deprecated
213 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
214 E[] elements) {
215 return copyOf(elements);
216 }
217
218 /**
219 * Returns an immutable sorted set containing the given elements sorted by
220 * their natural ordering. When multiple elements are equivalent according to
221 * {@link Comparable#compareTo}, only the first one specified is included.
222 *
223 * @throws NullPointerException if any of {@code elements} is null
224 * @since 3
225 */
226 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
227 E[] elements) {
228 return ofInternal(Ordering.natural(), (Object[]) elements);
229 }
230
231 private static <E> ImmutableSortedSet<E> ofInternal(
232 Comparator<? super E> comparator, Object... elements) {
233 switch (elements.length) {
234 case 0:
235 return emptySet(comparator);
236 default:
237 /*
238 * We can't use Platform.clone() because of GWT bug 3621. See our GWT
239 * ImmutableSortedSetTest.testOf_gwtArraycopyBug() for details. We can't
240 * use System.arraycopy() here for the same reason.
241 */
242 Object[] array = new Object[elements.length];
243 for (int i = 0; i < elements.length; i++) {
244 array[i] = checkNotNull(elements[i]);
245 }
246 sort(array, comparator);
247 array = removeDupes(array, comparator);
248 return new RegularImmutableSortedSet<E>(array, comparator);
249 }
250 }
251
252 /** Sort the array, according to the comparator. */
253 @SuppressWarnings("unchecked") // E comparator with Object array
254 private static <E> void sort(
255 Object[] array, Comparator<? super E> comparator) {
256 Arrays.sort(array, (Comparator<Object>) comparator);
257 }
258
259 /**
260 * Returns an array that removes duplicate consecutive elements, according to
261 * the provided comparator. Note that the input array is modified. This method
262 * does not support empty arrays.
263 */
264 private static <E> Object[] removeDupes(Object[] array,
265 Comparator<? super E> comparator) {
266 int size = 1;
267 for (int i = 1; i < array.length; i++) {
268 Object element = array[i];
269 if (unsafeCompare(comparator, array[size - 1], element) != 0) {
270 array[size] = element;
271 size++;
272 }
273 }
274
275 // TODO: Move to ObjectArrays?
276 if (size == array.length) {
277 return array;
278 } else {
279 Object[] copy = new Object[size];
280 Platform.unsafeArrayCopy(array, 0, copy, 0, size);
281 return copy;
282 }
283 }
284
285 /**
286 * Returns an immutable sorted set containing the given elements sorted by
287 * their natural ordering. When multiple elements are equivalent according to
288 * {@code compareTo()}, only the first one specified is included. To create a
289 * copy of a {@code SortedSet} that preserves the comparator, call
290 * {@link #copyOfSorted} instead. This method iterates over {@code elements}
291 * at most once.
292 *
293 * <p>Note that if {@code s} is a {@code Set<String>}, then
294 * {@code ImmutableSortedSet.copyOf(s)} returns an
295 * {@code ImmutableSortedSet<String>} containing each of the strings in
296 * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
297 * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
298 * set itself).
299 *
300 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
301 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
302 *
303 * <p>This method is not type-safe, as it may be called on elements that are
304 * not mutually comparable.
305 *
306 * @throws ClassCastException if the elements are not mutually comparable
307 * @throws NullPointerException if any of {@code elements} is null
308 */
309 public static <E> ImmutableSortedSet<E> copyOf(
310 Iterable<? extends E> elements) {
311 // Hack around K not being a subtype of Comparable.
312 // Unsafe, see ImmutableSortedSetFauxverideShim.
313 @SuppressWarnings("unchecked")
314 Ordering<E> naturalOrder = (Ordering) Ordering.<Comparable>natural();
315 return copyOfInternal(naturalOrder, elements, false);
316 }
317
318 /**
319 * Returns an immutable sorted set containing the given elements sorted by
320 * their natural ordering. When multiple elements are equivalent according to
321 * {@code compareTo()}, only the first one specified is included.
322 *
323 * <p>This method is not type-safe, as it may be called on elements that are
324 * not mutually comparable.
325 *
326 * @throws ClassCastException if the elements are not mutually comparable
327 * @throws NullPointerException if any of {@code elements} is null
328 */
329 public static <E> ImmutableSortedSet<E> copyOf(
330 Iterator<? extends E> elements) {
331 // Hack around K not being a subtype of Comparable.
332 // Unsafe, see ImmutableSortedSetFauxverideShim.
333 @SuppressWarnings("unchecked")
334 Ordering<E> naturalOrder = (Ordering) Ordering.<Comparable>natural();
335 return copyOfInternal(naturalOrder, 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><b>Note:</b> Despite what the method name suggests, if {@code elements}
345 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
346 *
347 * @throws NullPointerException if {@code comparator} or any of
348 * {@code elements} is null
349 */
350 public static <E> ImmutableSortedSet<E> copyOf(
351 Comparator<? super E> comparator, Iterable<? extends E> elements) {
352 checkNotNull(comparator);
353 return copyOfInternal(comparator, elements, false);
354 }
355
356 /**
357 * Returns an immutable sorted set containing the given elements sorted by
358 * the given {@code Comparator}. When multiple elements are equivalent
359 * according to {@code compareTo()}, only the first one specified is
360 * included.
361 *
362 * @throws NullPointerException if {@code comparator} or any of
363 * {@code elements} is null
364 */
365 public static <E> ImmutableSortedSet<E> copyOf(
366 Comparator<? super E> comparator, Iterator<? extends E> elements) {
367 checkNotNull(comparator);
368 return copyOfInternal(comparator, elements);
369 }
370
371 /**
372 * Returns an immutable sorted set containing the elements of a sorted set,
373 * sorted by the same {@code Comparator}. That behavior differs from
374 * {@link #copyOf(Iterable)}, which always uses the natural ordering of the
375 * elements.
376 *
377 * <p><b>Note:</b> Despite what the method name suggests, if {@code sortedSet}
378 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
379 *
380 * @throws NullPointerException if {@code sortedSet} or any of its elements
381 * is null
382 */
383 @SuppressWarnings("unchecked")
384 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
385 Comparator<? super E> comparator = sortedSet.comparator();
386 if (comparator == null) {
387 comparator = NATURAL_ORDER;
388 }
389 return copyOfInternal(comparator, sortedSet, true);
390 }
391
392 private static <E> ImmutableSortedSet<E> copyOfInternal(
393 Comparator<? super E> comparator, Iterable<? extends E> elements,
394 boolean fromSortedSet) {
395 boolean hasSameComparator
396 = fromSortedSet || hasSameComparator(elements, comparator);
397
398 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
399 @SuppressWarnings("unchecked")
400 ImmutableSortedSet<E> result = (ImmutableSortedSet<E>) elements;
401 if (!result.hasPartialArray()) {
402 return result;
403 }
404 }
405
406 Object[] array = newObjectArray(elements);
407 if (array.length == 0) {
408 return emptySet(comparator);
409 }
410
411 for (Object e : array) {
412 checkNotNull(e);
413 }
414 if (!hasSameComparator) {
415 sort(array, comparator);
416 array = removeDupes(array, comparator);
417 }
418 return new RegularImmutableSortedSet<E>(array, comparator);
419 }
420
421 /** Simplified version of {@link Iterables#toArray} that is GWT safe. */
422 private static <T> Object[] newObjectArray(Iterable<T> iterable) {
423 Collection<T> collection = Collections2.toCollection(iterable);
424 Object[] array = new Object[collection.size()];
425 return collection.toArray(array);
426 }
427
428 private static <E> ImmutableSortedSet<E> copyOfInternal(
429 Comparator<? super E> comparator, Iterator<? extends E> elements) {
430 if (!elements.hasNext()) {
431 return emptySet(comparator);
432 }
433 List<E> list = Lists.newArrayList();
434 while (elements.hasNext()) {
435 list.add(checkNotNull(elements.next()));
436 }
437 Object[] array = list.toArray();
438 sort(array, comparator);
439 array = removeDupes(array, comparator);
440 return new RegularImmutableSortedSet<E>(array, comparator);
441 }
442
443 /**
444 * Returns {@code true} if {@code elements} is a {@code SortedSet} that uses
445 * {@code comparator} to order its elements. Note that equivalent comparators
446 * may still return {@code false}, if {@code equals} doesn't consider them
447 * equal. If one comparator is {@code null} and the other is
448 * {@link Ordering#natural()}, this method returns {@code true}.
449 */
450 static boolean hasSameComparator(
451 Iterable<?> elements, Comparator<?> comparator) {
452 if (elements instanceof SortedSet) {
453 SortedSet<?> sortedSet = (SortedSet<?>) elements;
454 Comparator<?> comparator2 = sortedSet.comparator();
455 return (comparator2 == null)
456 ? comparator == Ordering.natural()
457 : comparator.equals(comparator2);
458 }
459 return false;
460 }
461
462 /**
463 * Returns an immutable sorted set containing the elements in the given list
464 * in the same order. It is useful when the elements already have the desired
465 * order but constructing the appropriate comparator is difficult.
466 *
467 * @throws NullPointerException if any of the elements is null
468 * @throws IllegalArgumentException if {@code elements} contains any
469 * duplicate values (according to {@link Object#equals})
470 * @since 3
471 */
472 @Beta
473 public static <E> ImmutableSortedSet<E> withExplicitOrder(List<E> elements) {
474 return ExplicitOrderedImmutableSortedSet.create(elements);
475 }
476
477 /**
478 * Returns an immutable sorted set containing the provided elements in the
479 * same order. It is useful when the elements already have the desired order
480 * but constructing the appropriate comparator is difficult.
481 *
482 * @param firstElement the value which should appear first in the generated
483 * set
484 * @param remainingElementsInOrder the rest of the values in the generated
485 * set, in the order they should appear
486 * @throws NullPointerException if any of the elements is null
487 * @throws IllegalArgumentException if any duplicate values (according to
488 * {@link Object#equals(Object)}) are present among the method arguments
489 * @since 3
490 */
491 @Beta
492 public static <E> ImmutableSortedSet<E> withExplicitOrder(
493 E firstElement, E... remainingElementsInOrder) {
494 return withExplicitOrder(
495 Lists.asList(firstElement, remainingElementsInOrder));
496 }
497
498 /**
499 * Returns a builder that creates immutable sorted sets with an explicit
500 * comparator. If the comparator has a more general type than the set being
501 * generated, such as creating a {@code SortedSet<Integer>} with a
502 * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
503 *
504 * @throws NullPointerException if {@code comparator} is null
505 */
506 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
507 return new Builder<E>(comparator);
508 }
509
510 /**
511 * Returns a builder that creates immutable sorted sets whose elements are
512 * ordered by the reverse of their natural ordering.
513 *
514 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
515 * than {@code Comparable<? super E>} as a workaround for javac <a
516 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
517 * 6468354</a>.
518 */
519 public static <E extends Comparable<E>> Builder<E> reverseOrder() {
520 return new Builder<E>(Ordering.natural().reverse());
521 }
522
523 /**
524 * Returns a builder that creates immutable sorted sets whose elements are
525 * ordered by their natural ordering. The sorted sets use {@link
526 * Ordering#natural()} as the comparator. This method provides more
527 * type-safety than {@link #builder}, as it can be called only for classes
528 * that implement {@link Comparable}.
529 *
530 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
531 * than {@code Comparable<? super E>} as a workaround for javac <a
532 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
533 * 6468354</a>.
534 */
535 public static <E extends Comparable<E>> Builder<E> naturalOrder() {
536 return new Builder<E>(Ordering.natural());
537 }
538
539 /**
540 * A builder for creating immutable sorted set instances, especially
541 * {@code public static final} sets ("constant sets"), with a given
542 * comparator.
543 *
544 * <p>Example:
545 * <pre>{@code
546 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS
547 * = new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
548 * .addAll(SINGLE_DIGIT_PRIMES)
549 * .add(42)
550 * .build();}</pre>
551 *
552 * <p>Builder instances can be reused - it is safe to call {@link #build}
553 * multiple times to build multiple sets in series. Each set
554 * is a superset of the set created before it.
555 */
556 public static final class Builder<E> extends ImmutableSet.Builder<E> {
557 private final Comparator<? super E> comparator;
558
559 /**
560 * Creates a new builder. The returned builder is equivalent to the builder
561 * generated by {@link ImmutableSortedSet#orderedBy}.
562 */
563 public Builder(Comparator<? super E> comparator) {
564 this.comparator = checkNotNull(comparator);
565 }
566
567 /**
568 * Adds {@code element} to the {@code ImmutableSortedSet}. If the
569 * {@code ImmutableSortedSet} already contains {@code element}, then
570 * {@code add} has no effect. (only the previously added element
571 * is retained).
572 *
573 * @param element the element to add
574 * @return this {@code Builder} object
575 * @throws NullPointerException if {@code element} is null
576 */
577 @Override public Builder<E> add(E element) {
578 super.add(element);
579 return this;
580 }
581
582 /**
583 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
584 * ignoring duplicate elements (only the first duplicate element is added).
585 *
586 * @param elements the elements to add
587 * @return this {@code Builder} object
588 * @throws NullPointerException if {@code elements} contains a null element
589 */
590 @Override public Builder<E> add(E... elements) {
591 super.add(elements);
592 return this;
593 }
594
595 /**
596 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
597 * ignoring duplicate elements (only the first duplicate element is added).
598 *
599 * @param elements the elements to add to the {@code ImmutableSortedSet}
600 * @return this {@code Builder} object
601 * @throws NullPointerException if {@code elements} contains a null element
602 */
603 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
604 super.addAll(elements);
605 return this;
606 }
607
608 /**
609 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
610 * ignoring duplicate elements (only the first duplicate element is added).
611 *
612 * @param elements the elements to add to the {@code ImmutableSortedSet}
613 * @return this {@code Builder} object
614 * @throws NullPointerException if {@code elements} contains a null element
615 */
616 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
617 super.addAll(elements);
618 return this;
619 }
620
621 /**
622 * Returns a newly-created {@code ImmutableSortedSet} based on the contents
623 * of the {@code Builder} and its comparator.
624 */
625 @Override public ImmutableSortedSet<E> build() {
626 return copyOfInternal(comparator, contents.iterator());
627 }
628 }
629
630 int unsafeCompare(Object a, Object b) {
631 return unsafeCompare(comparator, a, b);
632 }
633
634 static int unsafeCompare(
635 Comparator<?> comparator, Object a, Object b) {
636 // Pretend the comparator can compare anything. If it turns out it can't
637 // compare a and b, we should get a CCE on the subsequent line. Only methods
638 // that are spec'd to throw CCE should call this.
639 @SuppressWarnings("unchecked")
640 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
641 return unsafeComparator.compare(a, b);
642 }
643
644 final transient Comparator<? super E> comparator;
645
646 ImmutableSortedSet(Comparator<? super E> comparator) {
647 this.comparator = comparator;
648 }
649
650 /**
651 * Returns the comparator that orders the elements, which is
652 * {@link Ordering#natural()} when the natural ordering of the
653 * elements is used. Note that its behavior is not consistent with
654 * {@link SortedSet#comparator()}, which returns {@code null} to indicate
655 * natural ordering.
656 */
657 public Comparator<? super E> comparator() {
658 return comparator;
659 }
660
661 /**
662 * {@inheritDoc}
663 *
664 * <p>This method returns a serializable {@code ImmutableSortedSet}.
665 *
666 * <p>The {@link SortedSet#headSet} documentation states that a subset of a
667 * subset throws an {@link IllegalArgumentException} if passed a
668 * {@code toElement} greater than an earlier {@code toElement}. However, this
669 * method doesn't throw an exception in that situation, but instead keeps the
670 * original {@code toElement}.
671 */
672 public ImmutableSortedSet<E> headSet(E toElement) {
673 return headSetImpl(checkNotNull(toElement));
674 }
675
676 /**
677 * {@inheritDoc}
678 *
679 * <p>This method returns a serializable {@code ImmutableSortedSet}.
680 *
681 * <p>The {@link SortedSet#subSet} documentation states that a subset of a
682 * subset throws an {@link IllegalArgumentException} if passed a
683 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
684 * this method doesn't throw an exception in that situation, but instead keeps
685 * the original {@code fromElement}. Similarly, this method keeps the
686 * original {@code toElement}, instead of throwing an exception, if passed a
687 * {@code toElement} greater than an earlier {@code toElement}.
688 */
689 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
690 checkNotNull(fromElement);
691 checkNotNull(toElement);
692 checkArgument(comparator.compare(fromElement, toElement) <= 0);
693 return subSetImpl(fromElement, toElement);
694 }
695
696 /**
697 * {@inheritDoc}
698 *
699 * <p>This method returns a serializable {@code ImmutableSortedSet}.
700 *
701 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
702 * subset throws an {@link IllegalArgumentException} if passed a
703 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
704 * this method doesn't throw an exception in that situation, but instead keeps
705 * the original {@code fromElement}.
706 */
707 public ImmutableSortedSet<E> tailSet(E fromElement) {
708 return tailSetImpl(checkNotNull(fromElement));
709 }
710
711 /*
712 * These methods perform most headSet, subSet, and tailSet logic, besides
713 * parameter validation.
714 */
715 abstract ImmutableSortedSet<E> headSetImpl(E toElement);
716 abstract ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement);
717 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement);
718
719 /** Returns whether the elements are stored in a subset of a larger array. */
720 abstract boolean hasPartialArray();
721
722 /**
723 * Returns the position of an element within the set, or -1 if not present.
724 */
725 abstract int indexOf(Object target);
726
727 /*
728 * This class is used to serialize all ImmutableSortedSet instances,
729 * regardless of implementation type. It captures their "logical contents"
730 * only. This is necessary to ensure that the existence of a particular
731 * implementation type is an implementation detail.
732 */
733 private static class SerializedForm<E> implements Serializable {
734 final Comparator<? super E> comparator;
735 final Object[] elements;
736
737 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
738 this.comparator = comparator;
739 this.elements = elements;
740 }
741
742 @SuppressWarnings("unchecked")
743 Object readResolve() {
744 return new Builder<E>(comparator).add((E[]) elements).build();
745 }
746
747 private static final long serialVersionUID = 0;
748 }
749
750 private void readObject(ObjectInputStream stream)
751 throws InvalidObjectException {
752 throw new InvalidObjectException("Use SerializedForm");
753 }
754
755 @Override Object writeReplace() {
756 return new SerializedForm<E>(comparator, toArray());
757 }
758 }