001 /*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.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 /*
092 * TODO(cpovirk): find a way to remove this @SuppressWarnings even for
093 * eclipse?
094 */
095 @SuppressWarnings("unchecked")
096 private static final Comparator<Comparable> NATURAL_ORDER =
097 Ordering.natural();
098
099 @SuppressWarnings("unchecked")
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 copyOf(Ordering.natural(), Arrays.asList(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 copyOf(Ordering.natural(), Arrays.asList(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 copyOf(Ordering.natural(), Arrays.asList(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 copyOf(Ordering.natural(), Arrays.asList(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 (source-compatible since release 2)
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 int size = remaining.length + 6;
197 List<E> all = new ArrayList<E>(size);
198 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
199 Collections.addAll(all, remaining);
200 return copyOf(Ordering.natural(), all);
201 }
202
203 // TODO(kevinb): Consider factory methods that reject duplicates
204
205 /**
206 * Returns an immutable sorted set containing the given elements sorted by
207 * their natural ordering. When multiple elements are equivalent according to
208 * {@link Comparable#compareTo}, only the first one specified is included.
209 *
210 * @throws NullPointerException if any of {@code elements} is null
211 * @deprecated use {@link #copyOf(Comparable[])}. <b>This method is scheduled
212 * for deletion in October 2011.</b>
213 * @since 2 (changed from varargs in release 3)
214 */
215 @Deprecated
216 public
217 static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
218 E[] elements) {
219 return copyOf(elements);
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 * {@link Comparable#compareTo}, only the first one specified is included.
226 *
227 * @throws NullPointerException if any of {@code elements} is null
228 * @since 3
229 */
230 public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
231 E[] elements) {
232 return copyOf(Ordering.natural(), Arrays.asList(elements));
233 }
234
235 /**
236 * Returns an immutable sorted set containing the given elements sorted by
237 * their natural ordering. When multiple elements are equivalent according to
238 * {@code compareTo()}, only the first one specified is included. To create a
239 * copy of a {@code SortedSet} that preserves the comparator, call {@link
240 * #copyOfSorted} instead. This method iterates over {@code elements} at most
241 * once.
242
243 *
244 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
245 * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>}
246 * containing each of the strings in {@code s}, while {@code
247 * ImmutableSortedSet.of(s)} returns an {@code
248 * ImmutableSortedSet<Set<String>>} containing one element (the given set
249 * itself).
250 *
251 * <p>Despite the method name, this method attempts to avoid actually copying
252 * the data when it is safe to do so. The exact circumstances under which a
253 * copy will or will not be performed are undocumented and subject to change.
254 *
255 * <p>This method is not type-safe, as it may be called on elements that are
256 * not mutually comparable.
257 *
258 * @throws ClassCastException if the elements are not mutually comparable
259 * @throws NullPointerException if any of {@code elements} is null
260 */
261 public static <E> ImmutableSortedSet<E> copyOf(
262 Iterable<? extends E> elements) {
263 // Hack around K not being a subtype of Comparable.
264 // Unsafe, see ImmutableSortedSetFauxverideShim.
265 @SuppressWarnings("unchecked")
266 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
267 return copyOf(naturalOrder, elements);
268 }
269
270 /**
271 * Returns an immutable sorted set containing the given elements sorted by
272 * their natural ordering. When multiple elements are equivalent according to
273 * {@code compareTo()}, only the first one specified is included. To create a
274 * copy of a {@code SortedSet} that preserves the comparator, call
275 * {@link #copyOfSorted} instead. This method iterates over {@code elements}
276 * at most once.
277 *
278 * <p>Note that if {@code s} is a {@code Set<String>}, then
279 * {@code ImmutableSortedSet.copyOf(s)} returns an
280 * {@code ImmutableSortedSet<String>} containing each of the strings in
281 * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
282 * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
283 * set itself).
284 *
285 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
286 * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
287 *
288 * <p>This method is not type-safe, as it may be called on elements that are
289 * not mutually comparable.
290 *
291 * <p>This method is safe to use even when {@code elements} is a synchronized
292 * or concurrent collection that is currently being modified by another
293 * thread.
294 *
295 * @throws ClassCastException if the elements are not mutually comparable
296 * @throws NullPointerException if any of {@code elements} is null
297 * @since 7 (source-compatible since release 2)
298 */
299 public static <E> ImmutableSortedSet<E> copyOf(
300 Collection<? extends E> elements) {
301 // Hack around K not being a subtype of Comparable.
302 // Unsafe, see ImmutableSortedSetFauxverideShim.
303 @SuppressWarnings("unchecked")
304 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
305 return copyOf(naturalOrder, elements);
306 }
307
308 /**
309 * Returns an immutable sorted set containing the given elements sorted by
310 * their natural ordering. When multiple elements are equivalent according to
311 * {@code compareTo()}, only the first one specified is included.
312 *
313 * <p>This method is not type-safe, as it may be called on elements that are
314 * not mutually comparable.
315 *
316 * @throws ClassCastException if the elements are not mutually comparable
317 * @throws NullPointerException if any of {@code elements} is null
318 */
319 public static <E> ImmutableSortedSet<E> copyOf(
320 Iterator<? extends E> elements) {
321 // Hack around K not being a subtype of Comparable.
322 // Unsafe, see ImmutableSortedSetFauxverideShim.
323 @SuppressWarnings("unchecked")
324 Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
325 return copyOfInternal(naturalOrder, elements);
326 }
327
328 /**
329 * Returns an immutable sorted set containing the given elements sorted by
330 * the given {@code Comparator}. When multiple elements are equivalent
331 * according to {@code compareTo()}, only the first one specified is
332 * included.
333 *
334 * @throws NullPointerException if {@code comparator} or any of
335 * {@code elements} is null
336 */
337 public static <E> ImmutableSortedSet<E> copyOf(
338 Comparator<? super E> comparator, Iterator<? extends E> elements) {
339 checkNotNull(comparator);
340 return copyOfInternal(comparator, elements);
341 }
342
343 /**
344 * Returns an immutable sorted set containing the given elements sorted by
345 * the given {@code Comparator}. When multiple elements are equivalent
346 * according to {@code compare()}, only the first one specified is
347 * included. This method iterates over {@code elements} at most once.
348 *
349 * <p>Despite the method name, this method attempts to avoid actually copying
350 * the data when it is safe to do so. The exact circumstances under which a
351 * copy will or will not be performed are undocumented and subject to change.
352 *
353 * @throws NullPointerException if {@code comparator} or any of {@code
354 * elements} is null
355 */
356 public static <E> ImmutableSortedSet<E> copyOf(
357 Comparator<? super E> comparator, Iterable<? extends E> elements) {
358 checkNotNull(comparator);
359 return copyOfInternal(comparator, elements, false);
360 }
361
362 /**
363 * Returns an immutable sorted set containing the given elements sorted by
364 * the given {@code Comparator}. When multiple elements are equivalent
365 * according to {@code compareTo()}, only the first one specified is
366 * included.
367 *
368 * <p>Despite the method name, this method attempts to avoid actually copying
369 * the data when it is safe to do so. The exact circumstances under which a
370 * copy will or will not be performed are undocumented and subject to change.
371 *
372 * <p>This method is safe to use even when {@code elements} is a synchronized
373 * or concurrent collection that is currently being modified by another
374 * thread.
375 *
376 * @throws NullPointerException if {@code comparator} or any of
377 * {@code elements} is null
378 * @since 7 (source-compatible since release 2)
379 */
380 public static <E> ImmutableSortedSet<E> copyOf(
381 Comparator<? super E> comparator, Collection<? extends E> elements) {
382 checkNotNull(comparator);
383 return copyOfInternal(comparator, elements, false);
384 }
385
386 /**
387 * Returns an immutable sorted set containing the elements of a sorted set,
388 * sorted by the same {@code Comparator}. That behavior differs from {@link
389 * #copyOf(Iterable)}, which always uses the natural ordering of the
390 * elements.
391 *
392 * <p>Despite the method name, this method attempts to avoid actually copying
393 * the data when it is safe to do so. The exact circumstances under which a
394 * copy will or will not be performed are undocumented and subject to change.
395 *
396 * <p>This method is safe to use even when {@code elements} is a synchronized
397 * or concurrent collection that is currently being modified by another
398 * thread.
399 *
400 * @throws NullPointerException if {@code sortedSet} or any of its elements
401 * is null
402 */
403 @SuppressWarnings("unchecked")
404 public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
405 Comparator<? super E> comparator = sortedSet.comparator();
406 if (comparator == null) {
407 comparator = (Comparator<? super E>) NATURAL_ORDER;
408 }
409 return copyOfInternal(comparator, sortedSet, true);
410 }
411
412 private static <E> ImmutableSortedSet<E> copyOfInternal(
413 Comparator<? super E> comparator, Iterable<? extends E> elements,
414 boolean fromSortedSet) {
415 boolean hasSameComparator
416 = fromSortedSet || hasSameComparator(elements, comparator);
417
418 if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
419 @SuppressWarnings("unchecked")
420 ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
421 if (original.isEmpty()) {
422 return original;
423 }
424 ImmutableList<E> elementsList = original.asList();
425 ImmutableList<E> copiedElementsList = ImmutableList.copyOf(elements);
426 if (elementsList == copiedElementsList) {
427 return original;
428 }
429 return new RegularImmutableSortedSet<E>(copiedElementsList, comparator);
430 }
431
432 ImmutableList<E> list =
433 immutableSortedUniqueCopy(comparator, Lists.newArrayList(elements));
434 if (list.isEmpty()) {
435 return emptySet(comparator);
436 }
437 return new RegularImmutableSortedSet<E>(list, comparator);
438 }
439
440 private static <E> ImmutableSortedSet<E> copyOfInternal(
441 Comparator<? super E> comparator, Iterator<? extends E> elements) {
442 if (!elements.hasNext()) {
443 return emptySet(comparator);
444 }
445 ImmutableList<E> list =
446 immutableSortedUniqueCopy(comparator, Lists.newArrayList(elements));
447 return new RegularImmutableSortedSet<E>(list, comparator);
448 }
449
450 /**
451 * The list will get modified. Sorts the list, eliminates duplicate elements,
452 * returns an immutable copy.
453 */
454 private static <E> ImmutableList<E> immutableSortedUniqueCopy(
455 Comparator<? super E> comparator, List<E> list) {
456 if (list.isEmpty()) {
457 return ImmutableList.of();
458 }
459 Collections.sort(list, comparator);
460 int size = 1;
461 for (int i = 1; i < list.size(); i++) {
462 E elem = list.get(i);
463 if (comparator.compare(elem, list.get(size - 1)) != 0) {
464 list.set(size++, elem);
465 }
466 }
467 return ImmutableList.copyOf(list.subList(0, size));
468 }
469
470 /**
471 * Returns {@code true} if {@code elements} is a {@code SortedSet} that uses
472 * {@code comparator} to order its elements. Note that equivalent comparators
473 * may still return {@code false}, if {@code equals} doesn't consider them
474 * equal. If one comparator is {@code null} and the other is
475 * {@link Ordering#natural()}, this method returns {@code true}.
476 */
477 static boolean hasSameComparator(
478 Iterable<?> elements, Comparator<?> comparator) {
479 if (elements instanceof SortedSet) {
480 SortedSet<?> sortedSet = (SortedSet<?>) elements;
481 Comparator<?> comparator2 = sortedSet.comparator();
482 return (comparator2 == null)
483 ? comparator == Ordering.natural()
484 : comparator.equals(comparator2);
485 }
486 return false;
487 }
488
489 /**
490 * Returns an immutable sorted set containing the elements in the given list
491 * in the same order. It is useful when the elements already have the desired
492 * order but constructing the appropriate comparator is difficult.
493 *
494 * @throws NullPointerException if any of the elements is null
495 * @throws IllegalArgumentException if {@code elements} contains any
496 * duplicate values (according to {@link Object#equals})
497 * @since 3
498 * @deprecated If the provided elements are already in their natural order,
499 * {@link #copyOf(Iterable)} will produce a set with the same elements in
500 * the same order. If the elements are arranged according to another
501 * {@code Comparator}, use {@link #orderedBy(Comparator)}. Otherwise, use
502 * {@link ImmutableSet}, which maintains insertion order for inputs that
503 * are ordered but not sorted. This method is scheduled for deletion in
504 * Guava release 10.
505 */
506 @Beta
507 @Deprecated
508 public static <E> ImmutableSortedSet<E> withExplicitOrder(List<E> elements) {
509 return ExplicitOrderedImmutableSortedSet.create(elements);
510 }
511
512 /**
513 * Returns an immutable sorted set containing the provided elements in the
514 * same order. It is useful when the elements already have the desired order
515 * but constructing the appropriate comparator is difficult.
516 *
517 * @param firstElement the value which should appear first in the generated
518 * set
519 * @param remainingElementsInOrder the rest of the values in the generated
520 * set, in the order they should appear
521 * @throws NullPointerException if any of the elements is null
522 * @throws IllegalArgumentException if any duplicate values (according to
523 * {@link Object#equals(Object)}) are present among the method arguments
524 * @since 3
525 * @deprecated If the provided elements are already in their natural order,
526 * {@link #of()} will produce a set with the same elements in the same
527 * order. If the elements are arranged according to another {@code
528 * Comparator}, use {@link #orderedBy(Comparator)}. Otherwise, use {@link
529 * ImmutableSet}, which maintains insertion order for inputs that are
530 * ordered but not sorted. This method is scheduled for deletion in Guava
531 * release 10.
532 */
533 @Beta
534 @Deprecated
535 public static <E> ImmutableSortedSet<E> withExplicitOrder(
536 E firstElement, E... remainingElementsInOrder) {
537 return withExplicitOrder(
538 Lists.asList(firstElement, remainingElementsInOrder));
539 }
540
541 /**
542 * Returns a builder that creates immutable sorted sets with an explicit
543 * comparator. If the comparator has a more general type than the set being
544 * generated, such as creating a {@code SortedSet<Integer>} with a
545 * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
546 *
547 * @throws NullPointerException if {@code comparator} is null
548 */
549 public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
550 return new Builder<E>(comparator);
551 }
552
553 /**
554 * Returns a builder that creates immutable sorted sets whose elements are
555 * ordered by the reverse of their natural ordering.
556 *
557 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
558 * than {@code Comparable<? super E>} as a workaround for javac <a
559 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
560 * 6468354</a>.
561 */
562 public static <E extends Comparable<E>> Builder<E> reverseOrder() {
563 return new Builder<E>(Ordering.natural().reverse());
564 }
565
566 /**
567 * Returns a builder that creates immutable sorted sets whose elements are
568 * ordered by their natural ordering. The sorted sets use {@link
569 * Ordering#natural()} as the comparator. This method provides more
570 * type-safety than {@link #builder}, as it can be called only for classes
571 * that implement {@link Comparable}.
572 *
573 * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
574 * than {@code Comparable<? super E>} as a workaround for javac <a
575 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
576 * 6468354</a>.
577 */
578 public static <E extends Comparable<E>> Builder<E> naturalOrder() {
579 return new Builder<E>(Ordering.natural());
580 }
581
582 /**
583 * A builder for creating immutable sorted set instances, especially {@code
584 * public static final} sets ("constant sets"), with a given comparator.
585 * Example: <pre> {@code
586 *
587 * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
588 * new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
589 * .addAll(SINGLE_DIGIT_PRIMES)
590 * .add(42)
591 * .build();}</pre>
592 *
593 * Builder instances can be reused; it is safe to call {@link #build} multiple
594 * times to build multiple sets in series. Each set is a superset of the set
595 * created before it.
596 *
597 * @since 2 (imported from Google Collections Library)
598 */
599 public static final class Builder<E> extends ImmutableSet.Builder<E> {
600 private final Comparator<? super E> comparator;
601
602 /**
603 * Creates a new builder. The returned builder is equivalent to the builder
604 * generated by {@link ImmutableSortedSet#orderedBy}.
605 */
606 public Builder(Comparator<? super E> comparator) {
607 this.comparator = checkNotNull(comparator);
608 }
609
610 /**
611 * Adds {@code element} to the {@code ImmutableSortedSet}. If the
612 * {@code ImmutableSortedSet} already contains {@code element}, then
613 * {@code add} has no effect. (only the previously added element
614 * is retained).
615 *
616 * @param element the element to add
617 * @return this {@code Builder} object
618 * @throws NullPointerException if {@code element} is null
619 */
620 @Override public Builder<E> add(E element) {
621 super.add(element);
622 return this;
623 }
624
625 /**
626 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
627 * ignoring duplicate elements (only the first duplicate element is added).
628 *
629 * @param elements the elements to add
630 * @return this {@code Builder} object
631 * @throws NullPointerException if {@code elements} contains a null element
632 */
633 @Override public Builder<E> add(E... elements) {
634 super.add(elements);
635 return this;
636 }
637
638 /**
639 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
640 * ignoring duplicate elements (only the first duplicate element is added).
641 *
642 * @param elements the elements to add to the {@code ImmutableSortedSet}
643 * @return this {@code Builder} object
644 * @throws NullPointerException if {@code elements} contains a null element
645 */
646 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
647 super.addAll(elements);
648 return this;
649 }
650
651 /**
652 * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
653 * ignoring duplicate elements (only the first duplicate element is added).
654 *
655 * @param elements the elements to add to the {@code ImmutableSortedSet}
656 * @return this {@code Builder} object
657 * @throws NullPointerException if {@code elements} contains a null element
658 */
659 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
660 super.addAll(elements);
661 return this;
662 }
663
664 /**
665 * Returns a newly-created {@code ImmutableSortedSet} based on the contents
666 * of the {@code Builder} and its comparator.
667 */
668 @Override public ImmutableSortedSet<E> build() {
669 return copyOfInternal(comparator, contents.iterator());
670 }
671 }
672
673 int unsafeCompare(Object a, Object b) {
674 return unsafeCompare(comparator, a, b);
675 }
676
677 static int unsafeCompare(
678 Comparator<?> comparator, Object a, Object b) {
679 // Pretend the comparator can compare anything. If it turns out it can't
680 // compare a and b, we should get a CCE on the subsequent line. Only methods
681 // that are spec'd to throw CCE should call this.
682 @SuppressWarnings("unchecked")
683 Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
684 return unsafeComparator.compare(a, b);
685 }
686
687 final transient Comparator<? super E> comparator;
688
689 ImmutableSortedSet(Comparator<? super E> comparator) {
690 this.comparator = comparator;
691 }
692
693 /**
694 * Returns the comparator that orders the elements, which is
695 * {@link Ordering#natural()} when the natural ordering of the
696 * elements is used. Note that its behavior is not consistent with
697 * {@link SortedSet#comparator()}, which returns {@code null} to indicate
698 * natural ordering.
699 */
700 @Override
701 public Comparator<? super E> comparator() {
702 return comparator;
703 }
704
705 /**
706 * {@inheritDoc}
707 *
708 * <p>This method returns a serializable {@code ImmutableSortedSet}.
709 *
710 * <p>The {@link SortedSet#headSet} documentation states that a subset of a
711 * subset throws an {@link IllegalArgumentException} if passed a
712 * {@code toElement} greater than an earlier {@code toElement}. However, this
713 * method doesn't throw an exception in that situation, but instead keeps the
714 * original {@code toElement}.
715 */
716 @Override
717 public ImmutableSortedSet<E> headSet(E toElement) {
718 return headSetImpl(checkNotNull(toElement));
719 }
720
721 /**
722 * {@inheritDoc}
723 *
724 * <p>This method returns a serializable {@code ImmutableSortedSet}.
725 *
726 * <p>The {@link SortedSet#subSet} documentation states that a subset of a
727 * subset throws an {@link IllegalArgumentException} if passed a
728 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
729 * this method doesn't throw an exception in that situation, but instead keeps
730 * the original {@code fromElement}. Similarly, this method keeps the
731 * original {@code toElement}, instead of throwing an exception, if passed a
732 * {@code toElement} greater than an earlier {@code toElement}.
733 */
734 @Override
735 public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
736 checkNotNull(fromElement);
737 checkNotNull(toElement);
738 checkArgument(comparator.compare(fromElement, toElement) <= 0);
739 return subSetImpl(fromElement, toElement);
740 }
741
742 /**
743 * {@inheritDoc}
744 *
745 * <p>This method returns a serializable {@code ImmutableSortedSet}.
746 *
747 * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
748 * subset throws an {@link IllegalArgumentException} if passed a
749 * {@code fromElement} smaller than an earlier {@code fromElement}. However,
750 * this method doesn't throw an exception in that situation, but instead keeps
751 * the original {@code fromElement}.
752 */
753 @Override
754 public ImmutableSortedSet<E> tailSet(E fromElement) {
755 return tailSetImpl(checkNotNull(fromElement));
756 }
757
758 /*
759 * These methods perform most headSet, subSet, and tailSet logic, besides
760 * parameter validation.
761 */
762 abstract ImmutableSortedSet<E> headSetImpl(E toElement);
763 abstract ImmutableSortedSet<E> subSetImpl(E fromElement, E toElement);
764 abstract ImmutableSortedSet<E> tailSetImpl(E fromElement);
765
766 /**
767 * Returns the position of an element within the set, or -1 if not present.
768 */
769 abstract int indexOf(Object target);
770
771 /*
772 * This class is used to serialize all ImmutableSortedSet instances,
773 * regardless of implementation type. It captures their "logical contents"
774 * only. This is necessary to ensure that the existence of a particular
775 * implementation type is an implementation detail.
776 */
777 private static class SerializedForm<E> implements Serializable {
778 final Comparator<? super E> comparator;
779 final Object[] elements;
780
781 public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
782 this.comparator = comparator;
783 this.elements = elements;
784 }
785
786 @SuppressWarnings("unchecked")
787 Object readResolve() {
788 return new Builder<E>(comparator).add((E[]) elements).build();
789 }
790
791 private static final long serialVersionUID = 0;
792 }
793
794 private void readObject(ObjectInputStream stream)
795 throws InvalidObjectException {
796 throw new InvalidObjectException("Use SerializedForm");
797 }
798
799 @Override Object writeReplace() {
800 return new SerializedForm<E>(comparator, toArray());
801 }
802 }