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    }