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 * @author Louis Wasserman
083 * @since 2 (imported from Google Collections Library)
084 */
085 // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
086 @GwtCompatible(serializable = true, emulated = true)
087 @SuppressWarnings("serial") // we're overriding default serialization
088 public abstract class ImmutableSortedSet<E>
089 extends ImmutableSortedSetFauxverideShim<E> implements SortedSet<E> {
090
091 // TODO(cpovirk): find a way to remove this @SuppressWarnings even for eclipse?
092 @SuppressWarnings("unchecked")
093 private static final Comparator NATURAL_ORDER = Ordering.natural();
094
095 @SuppressWarnings("unchecked")
096 private static final ImmutableSortedSet<Object> NATURAL_EMPTY_SET =
097 new EmptyImmutableSortedSet<Object>(NATURAL_ORDER);
098
099 @SuppressWarnings("unchecked")
100 private static <E> ImmutableSortedSet<E> emptySet() {
101 return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET;
102 }
103
104 static <E> ImmutableSortedSet<E> emptySet(
105 Comparator<? super E> comparator) {
106 if (NATURAL_ORDER.equals(comparator)) {
107 return emptySet();
108 } else {
109 return new EmptyImmutableSortedSet<E>(comparator);
110 }
111 }
112
113 /**
114 * Returns the empty immutable sorted set.
115 */
116 public static <E> ImmutableSortedSet<E> of() {
117 return emptySet();
118 }
119
120 /**
121 * Returns an immutable sorted set containing a single element.
122 */
123 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
124 E element) {
125 return new RegularImmutableSortedSet<E>(
126 ImmutableList.of(element), Ordering.natural());
127 }
128
129 /**
130 * Returns an immutable sorted set containing the given elements sorted by
131 * their natural ordering. When multiple elements are equivalent according to
132 * {@link Comparable#compareTo}, only the first one specified is included.
133 *
134 * @throws NullPointerException if any element is null
135 */
136 @SuppressWarnings("unchecked")
137 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
138 E e1, E e2) {
139 return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
140 }
141
142 /**
143 * Returns an immutable sorted set containing the given elements sorted by
144 * their natural ordering. When multiple elements are equivalent according to
145 * {@link Comparable#compareTo}, only the first one specified is included.
146 *
147 * @throws NullPointerException if any element is null
148 */
149 @SuppressWarnings("unchecked")
150 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
151 E e1, E e2, E e3) {
152 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
153 }
154
155 /**
156 * Returns an immutable sorted set containing the given elements sorted by
157 * their natural ordering. When multiple elements are equivalent according to
158 * {@link Comparable#compareTo}, only the first one specified is included.
159 *
160 * @throws NullPointerException if any element is null
161 */
162 @SuppressWarnings("unchecked")
163 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
164 E e1, E e2, E e3, E e4) {
165 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
166 }
167
168 /**
169 * Returns an immutable sorted set containing the given elements sorted by
170 * their natural ordering. When multiple elements are equivalent according to
171 * {@link Comparable#compareTo}, only the first one specified is included.
172 *
173 * @throws NullPointerException if any element is null
174 */
175 @SuppressWarnings("unchecked")
176 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
177 E e1, E e2, E e3, E e4, E e5) {
178 return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
179 }
180
181 /**
182 * Returns an immutable sorted set containing the given elements sorted by
183 * their natural ordering. When multiple elements are equivalent according to
184 * {@link Comparable#compareTo}, only the first one specified is included.
185 *
186 * @throws NullPointerException if any element is null
187 * @since 3 (source-compatible since release 2)
188 */
189 @SuppressWarnings("unchecked")
190 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
191 E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
192 int size = remaining.length + 6;
193 List<E> all = new ArrayList<E>(size);
194 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
195 Collections.addAll(all, remaining);
196 return copyOf(Ordering.natural(), all);
197 }
198
199 // TODO(kevinb): Consider factory methods that reject duplicates
200
201 /**
202 * Returns an immutable sorted set containing the given elements sorted by
203 * their natural ordering. When multiple elements are equivalent according to
204 * {@link Comparable#compareTo}, only the first one specified is included.
205 *
206 * @throws NullPointerException if any of {@code elements} is null
207 * @deprecated use {@link #copyOf(Comparable[])}. <b>This method is scheduled
208 * for deletion in October 2011.</b>
209 * @since 2 (changed from varargs in release 3)
210 */
211 @Deprecated
212 public 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
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 K not being a subtype of Comparable.
259 // Unsafe, see ImmutableSortedSetFauxverideShim.
260 @SuppressWarnings("unchecked")
261 Ordering<E> naturalOrder = (Ordering) 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 (source-compatible since release 2)
293 */
294 public static <E> ImmutableSortedSet<E> copyOf(
295 Collection<? extends E> elements) {
296 // Hack around K not being a subtype of Comparable.
297 // Unsafe, see ImmutableSortedSetFauxverideShim.
298 @SuppressWarnings("unchecked")
299 Ordering<E> naturalOrder = (Ordering) 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 K not being a subtype of Comparable.
317 // Unsafe, see ImmutableSortedSetFauxverideShim.
318 @SuppressWarnings("unchecked")
319 Ordering<E> naturalOrder = (Ordering) 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, false);
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 (source-compatible since release 2)
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, false);
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 elements} 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 = NATURAL_ORDER;
403 }
404 return copyOfInternal(comparator, sortedSet, true);
405 }
406
407 private static <E> ImmutableSortedSet<E> copyOfInternal(
408 Comparator<? super E> comparator, Iterable<? extends E> elements,
409 boolean fromSortedSet) {
410 boolean hasSameComparator
411 = fromSortedSet || hasSameComparator(elements, comparator);
412
413 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
414 @SuppressWarnings("unchecked")
415 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
416 if (original.isEmpty()) {
417 return original;
418 }
419 ImmutableList<E> elementsList = original.asList();
420 ImmutableList<E> copiedElementsList = ImmutableList.copyOf(elements);
421 if (elementsList == copiedElementsList) {
422 return original;
423 }
424 return new RegularImmutableSortedSet<E>(copiedElementsList, comparator);
425 }
426
427 ImmutableList<E> list =
428 immutableSortedUniqueCopy(comparator, Lists.newArrayList(elements));
429 if (list.isEmpty()) {
430 return emptySet(comparator);
431 }
432 return new RegularImmutableSortedSet<E>(list, comparator);
433 }
434
435 private static <E> ImmutableSortedSet<E> copyOfInternal(
436 Comparator<? super E> comparator, Iterator<? extends E> elements) {
437 if (!elements.hasNext()) {
438 return emptySet(comparator);
439 }
440 ImmutableList<E> list =
441 immutableSortedUniqueCopy(comparator, Lists.newArrayList(elements));
442 return new RegularImmutableSortedSet<E>(list, comparator);
443 }
444
445 /**
446 * The list will get modified. Sorts the list, eliminates duplicate elements,
447 * returns an immutable copy.
448 */
449 private static <E> ImmutableList<E> immutableSortedUniqueCopy(
450 Comparator<? super E> comparator, List<E> list) {
451 if (list.isEmpty()) {
452 return ImmutableList.of();
453 }
454 Collections.sort(list, comparator);
455 int size = 1;
456 for (int i = 1; i < list.size(); i++) {
457 E elem = list.get(i);
458 if (comparator.compare(elem, list.get(size - 1)) != 0) {
459 list.set(size++, elem);
460 }
461 }
462 return ImmutableList.copyOf(list.subList(0, size));
463 }
464
465 /**
466 * Returns {@code true} if {@code elements} is a {@code SortedSet} that uses
467 * {@code comparator} to order its elements. Note that equivalent comparators
468 * may still return {@code false}, if {@code equals} doesn't consider them
469 * equal. If one comparator is {@code null} and the other is
470 * {@link Ordering#natural()}, this method returns {@code true}.
471 */
472 static boolean hasSameComparator(
473 Iterable<?> elements, Comparator<?> comparator) {
474 if (elements instanceof SortedSet) {
475 SortedSet<?> sortedSet = (SortedSet<?>) elements;
476 Comparator<?> comparator2 = sortedSet.comparator();
477 return (comparator2 == null)
478 ? comparator == Ordering.natural()
479 : comparator.equals(comparator2);
480 }
481 return false;
482 }
483
484 /**
485 * Returns an immutable sorted set containing the elements in the given list
486 * in the same order. It is useful when the elements already have the desired
487 * order but constructing the appropriate comparator is difficult.
488 *
489 * @throws NullPointerException if any of the elements is null
490 * @throws IllegalArgumentException if {@code elements} contains any
491 * duplicate values (according to {@link Object#equals})
492 * @since 3
493 */
494 @Beta
495 public static <E> ImmutableSortedSet<E> withExplicitOrder(List<E> elements) {
496 return ExplicitOrderedImmutableSortedSet.create(elements);
497 }
498
499 /**
500 * Returns an immutable sorted set containing the provided elements in the
501 * same order. It is useful when the elements already have the desired order
502 * but constructing the appropriate comparator is difficult.
503 *
504 * @param firstElement the value which should appear first in the generated
505 * set
506 * @param remainingElementsInOrder the rest of the values in the generated
507 * set, in the order they should appear
508 * @throws NullPointerException if any of the elements is null
509 * @throws IllegalArgumentException if any duplicate values (according to
510 * {@link Object#equals(Object)}) are present among the method arguments
511 * @since 3
512 */
513 @Beta
514 public static <E> ImmutableSortedSet<E> withExplicitOrder(
515 E firstElement, E... remainingElementsInOrder) {
516 return withExplicitOrder(
517 Lists.asList(firstElement, remainingElementsInOrder));
518 }
519
520 /**
521 * Returns a builder that creates immutable sorted sets with an explicit
522 * comparator. If the comparator has a more general type than the set being
523 * generated, such as creating a {@code SortedSet<Integer>} with a
524 * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
525 *
526 * @throws NullPointerException if {@code comparator} is null
527 */
528 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
529 return new Builder<E>(comparator);
530 }
531
532 /**
533 * Returns a builder that creates immutable sorted sets whose elements are
534 * ordered by the reverse of their natural ordering.
535 *
536 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
537 * than {@code Comparable<? super E>} as a workaround for javac <a
538 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
539 * 6468354</a>.
540 */
541 public static <E extends Comparable<E>> Builder<E> reverseOrder() {
542 return new Builder<E>(Ordering.natural().reverse());
543 }
544
545 /**
546 * Returns a builder that creates immutable sorted sets whose elements are
547 * ordered by their natural ordering. The sorted sets use {@link
548 * Ordering#natural()} as the comparator. This method provides more
549 * type-safety than {@link #builder}, as it can be called only for classes
550 * that implement {@link Comparable}.
551 *
552 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
553 * than {@code Comparable<? super E>} as a workaround for javac <a
554 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
555 * 6468354</a>.
556 */
557 public static <E extends Comparable<E>> Builder<E> naturalOrder() {
558 return new Builder<E>(Ordering.natural());
559 }
560
561 /**
562 * A builder for creating immutable sorted set instances, especially {@code
563 * public static final} sets ("constant sets"), with a given comparator.
564 * Example: <pre> {@code
565 *
566 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
567 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
568 * .addAll(SINGLE_DIGIT_PRIMES)
569 * .add(42)
570 * .build();}</pre>
571 *
572 * Builder instances can be reused; it is safe to call {@link #build} multiple
573 * times to build multiple sets in series. Each set is a superset of the set
574 * created before it.
575 *
576 * @since 2 (imported from Google Collections Library)
577 */
578 public static final class Builder<E> extends ImmutableSet.Builder<E> {
579 private final Comparator<? super E> comparator;
580
581 /**
582 * Creates a new builder. The returned builder is equivalent to the builder
583 * generated by {@link ImmutableSortedSet#orderedBy}.
584 */
585 public Builder(Comparator<? super E> comparator) {
586 this.comparator = checkNotNull(comparator);
587 }
588
589 /**
590 * Adds {@code element} to the {@code ImmutableSortedSet}. If the
591 * {@code ImmutableSortedSet} already contains {@code element}, then
592 * {@code add} has no effect. (only the previously added element
593 * is retained).
594 *
595 * @param element the element to add
596 * @return this {@code Builder} object
597 * @throws NullPointerException if {@code element} is null
598 */
599 @Override public Builder<E> add(E element) {
600 super.add(element);
601 return this;
602 }
603
604 /**
605 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
606 * ignoring duplicate elements (only the first duplicate element is added).
607 *
608 * @param elements the elements to add
609 * @return this {@code Builder} object
610 * @throws NullPointerException if {@code elements} contains a null element
611 */
612 @Override public Builder<E> add(E... elements) {
613 super.add(elements);
614 return this;
615 }
616
617 /**
618 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
619 * ignoring duplicate elements (only the first duplicate element is added).
620 *
621 * @param elements the elements to add to the {@code ImmutableSortedSet}
622 * @return this {@code Builder} object
623 * @throws NullPointerException if {@code elements} contains a null element
624 */
625 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
626 super.addAll(elements);
627 return this;
628 }
629
630 /**
631 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
632 * ignoring duplicate elements (only the first duplicate element is added).
633 *
634 * @param elements the elements to add to the {@code ImmutableSortedSet}
635 * @return this {@code Builder} object
636 * @throws NullPointerException if {@code elements} contains a null element
637 */
638 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
639 super.addAll(elements);
640 return this;
641 }
642
643 /**
644 * Returns a newly-created {@code ImmutableSortedSet} based on the contents
645 * of the {@code Builder} and its comparator.
646 */
647 @Override public ImmutableSortedSet<E> build() {
648 return copyOfInternal(comparator, contents.iterator());
649 }
650 }
651
652 int unsafeCompare(Object a, Object b) {
653 return unsafeCompare(comparator, a, b);
654 }
655
656 static int unsafeCompare(
657 Comparator<?> comparator, Object a, Object b) {
658 // Pretend the comparator can compare anything. If it turns out it can't
659 // compare a and b, we should get a CCE on the subsequent line. Only methods
660 // that are spec'd to throw CCE should call this.
661 @SuppressWarnings("unchecked")
662 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
663 return unsafeComparator.compare(a, b);
664 }
665
666 final transient Comparator<? super E> comparator;
667
668 ImmutableSortedSet(Comparator<? super E> comparator) {
669 this.comparator = comparator;
670 }
671
672 /**
673 * Returns the comparator that orders the elements, which is
674 * {@link Ordering#natural()} when the natural ordering of the
675 * elements is used. Note that its behavior is not consistent with
676 * {@link SortedSet#comparator()}, which returns {@code null} to indicate
677 * natural ordering.
678 */
679 public Comparator<? super E> comparator() {
680 return comparator;
681 }
682
683 /**
684 * {@inheritDoc}
685 *
686 * <p>This method returns a serializable {@code ImmutableSortedSet}.
687 *
688 * <p>The {@link SortedSet#headSet} documentation states that a subset of a
689 * subset throws an {@link IllegalArgumentException} if passed a
690 * {@code toElement} greater than an earlier {@code toElement}. However, this
691 * method doesn't throw an exception in that situation, but instead keeps the
692 * original {@code toElement}.
693 */
694 public ImmutableSortedSet<E> headSet(E toElement) {
695 return headSetImpl(checkNotNull(toElement));
696 }
697
698 /**
699 * {@inheritDoc}
700 *
701 * <p>This method returns a serializable {@code ImmutableSortedSet}.
702 *
703 * <p>The {@link SortedSet#subSet} documentation states that a subset of a
704 * subset throws an {@link IllegalArgumentException} if passed a
705 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
706 * this method doesn't throw an exception in that situation, but instead keeps
707 * the original {@code fromElement}. Similarly, this method keeps the
708 * original {@code toElement}, instead of throwing an exception, if passed a
709 * {@code toElement} greater than an earlier {@code toElement}.
710 */
711 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
712 checkNotNull(fromElement);
713 checkNotNull(toElement);
714 checkArgument(comparator.compare(fromElement, toElement) <= 0);
715 return subSetImpl(fromElement, toElement);
716 }
717
718 /**
719 * {@inheritDoc}
720 *
721 * <p>This method returns a serializable {@code ImmutableSortedSet}.
722 *
723 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
724 * subset throws an {@link IllegalArgumentException} if passed a
725 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
726 * this method doesn't throw an exception in that situation, but instead keeps
727 * the original {@code fromElement}.
728 */
729 public ImmutableSortedSet<E> tailSet(E fromElement) {
730 return tailSetImpl(checkNotNull(fromElement));
731 }
732
733 /*
734 * These methods perform most headSet, subSet, and tailSet logic, besides
735 * parameter validation.
736 */
737 abstract ImmutableSortedSet<E> headSetImpl(E toElement);
738 abstract ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement);
739 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement);
740
741 /**
742 * Returns the position of an element within the set, or -1 if not present.
743 */
744 abstract int indexOf(Object target);
745
746 /*
747 * This class is used to serialize all ImmutableSortedSet instances,
748 * regardless of implementation type. It captures their "logical contents"
749 * only. This is necessary to ensure that the existence of a particular
750 * implementation type is an implementation detail.
751 */
752 private static class SerializedForm<E> implements Serializable {
753 final Comparator<? super E> comparator;
754 final Object[] elements;
755
756 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
757 this.comparator = comparator;
758 this.elements = elements;
759 }
760
761 @SuppressWarnings("unchecked")
762 Object readResolve() {
763 return new Builder<E>(comparator).add((E[]) elements).build();
764 }
765
766 private static final long serialVersionUID = 0;
767 }
768
769 private void readObject(ObjectInputStream stream)
770 throws InvalidObjectException {
771 throw new InvalidObjectException("Use SerializedForm");
772 }
773
774 @Override Object writeReplace() {
775 return new SerializedForm<E>(comparator, toArray());
776 }
777 }