    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.GwtCompatible;
    023
    024    import java.io.InvalidObjectException;
    025    import java.io.ObjectInputStream;
    026    import java.io.Serializable;
    027    import java.util.ArrayList;
    028    import java.util.Arrays;
    029    import java.util.Collection;
    030    import java.util.Collections;
    031    import java.util.Comparator;
    032    import java.util.Iterator;
    033    import java.util.List;
    034    import java.util.SortedSet;
    035
    036    import javax.annotation.Nullable;
    037
    038    /**
    039     * An immutable {@code SortedSet} that stores its elements in a sorted array.
    040     * Some instances are ordered by an explicit comparator, while others follow the
    041     * natural sort ordering of their elements. Either way, null elements are not
    042     * supported.
    043     *
    044     * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i>
    045     * of a separate collection that can still change, an instance of {@code
    046     * ImmutableSortedSet} contains its own private data and will <i>never</i>
    047     * change. This class is convenient for {@code public static final} sets
    048     * ("constant sets") and also lets you easily make a "defensive copy" of a set
    049     * provided to your class by a caller.
    050     *
    051     * <p>The sets returned by the {@link #headSet}, {@link #tailSet}, and
    052     * {@link #subSet} methods share the same array as the original set, preventing
    053     * that array from being garbage collected. If this is a concern, the data may
    054     * be copied into a correctly-sized array by calling {@link #copyOfSorted}.
    055     *
    056     * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
    057     * {@link #containsAll(Collection)}, and {@link #equals(Object)}
    058     * implementations must check whether a provided object is equivalent to an
    059     * element in the collection. Unlike most collections, an
    060     * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if
    061     * two elements are equivalent. Instead, with an explicit comparator, the
    062     * following relation determines whether elements {@code x} and {@code y} are
    063     * equivalent: <pre>   {@code
    064     *
    065     *   {(x, y) | comparator.compare(x, y) == 0}}</pre>
    066     *
    067     * With natural ordering of elements, the following relation determines whether
    068     * two elements are equivalent: <pre>   {@code
    069     *
    070     *   {(x, y) | x.compareTo(y) == 0}}</pre>
    071     *
    072     * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not
    073     * function correctly if an element is modified after being placed in the set.
    074     * For this reason, and to avoid general confusion, it is strongly recommended
    075     * to place only immutable objects into this collection.
    076     *
    077     * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
    078     * it has no public or protected constructors. Thus, instances of this type are
    079     * guaranteed to be immutable.
    080     *
    081     * @see ImmutableSet
    082     * @author Jared Levy
    083     * @author Louis Wasserman
    084     * @since 2.0 (imported from Google Collections Library)
    085     */
    086    // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
    087    @GwtCompatible(serializable = true, emulated = true)
    088    @SuppressWarnings("serial") // we're overriding default serialization
    089    public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
    090        implements SortedSet<E>, SortedIterable<E> {
    091
    092      private static final Comparator<Comparable> NATURAL_ORDER =
    093          Ordering.natural();
    094
    095      private static final ImmutableSortedSet<Comparable> NATURAL_EMPTY_SET =
    096          new EmptyImmutableSortedSet<Comparable>(NATURAL_ORDER);
    097
    098      @SuppressWarnings("unchecked")
    099      private static <E> ImmutableSortedSet<E> emptySet() {
    100        return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET;
    101      }
    102
    103      static <E> ImmutableSortedSet<E> emptySet(
    104          Comparator<? super E> comparator) {
    105        if (NATURAL_ORDER.equals(comparator)) {
    106          return emptySet();
    107        } else {
    108          return new EmptyImmutableSortedSet<E>(comparator);
    109        }
    110      }
    111
    112      /**
    113       * Returns the empty immutable sorted set.
    114       */
    115      public static <E> ImmutableSortedSet<E> of() {
    116        return emptySet();
    117      }
    118
    119      /**
    120       * Returns an immutable sorted set containing a single element.
    121       */
    122      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
    123          E element) {
    124        return new RegularImmutableSortedSet<E>(
    125            ImmutableList.of(element), Ordering.natural());
    126      }
    127
    128      /**
    129       * Returns an immutable sorted set containing the given elements sorted by
    130       * their natural ordering. When multiple elements are equivalent according to
    131       * {@link Comparable#compareTo}, only the first one specified is included.
    132       *
    133       * @throws NullPointerException if any element is null
    134       */
    135      @SuppressWarnings("unchecked")
    136      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
    137          E e1, E e2) {
    138        return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
    139      }
    140
    141      /**
    142       * Returns an immutable sorted set containing the given elements sorted by
    143       * their natural ordering. When multiple elements are equivalent according to
    144       * {@link Comparable#compareTo}, only the first one specified is included.
    145       *
    146       * @throws NullPointerException if any element is null
    147       */
    148      @SuppressWarnings("unchecked")
    149      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
    150          E e1, E e2, E e3) {
    151        return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
    152      }
    153
    154      /**
    155       * Returns an immutable sorted set containing the given elements sorted by
    156       * their natural ordering. When multiple elements are equivalent according to
    157       * {@link Comparable#compareTo}, only the first one specified is included.
    158       *
    159       * @throws NullPointerException if any element is null
    160       */
    161      @SuppressWarnings("unchecked")
    162      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
    163          E e1, E e2, E e3, E e4) {
    164        return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
    165      }
    166
    167      /**
    168       * Returns an immutable sorted set containing the given elements sorted by
    169       * their natural ordering. When multiple elements are equivalent according to
    170       * {@link Comparable#compareTo}, only the first one specified is included.
    171       *
    172       * @throws NullPointerException if any element is null
    173       */
    174      @SuppressWarnings("unchecked")
    175      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
    176          E e1, E e2, E e3, E e4, E e5) {
    177        return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
    178      }
    179
    180      /**
    181       * Returns an immutable sorted set containing the given elements sorted by
    182       * their natural ordering. When multiple elements are equivalent according to
    183       * {@link Comparable#compareTo}, only the first one specified is included.
    184       *
    185       * @throws NullPointerException if any element is null
    186       * @since 3.0 (source-compatible since 2.0)
    187       */
    188      @SuppressWarnings("unchecked")
    189      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
    190          E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
    191        int size = remaining.length + 6;
    192        List<E> all = new ArrayList<E>(size);
    193        Collections.addAll(all, e1, e2, e3, e4, e5, e6);
    194        Collections.addAll(all, remaining);
    195        return copyOf(Ordering.natural(), all);
    196      }
    197
    198      // TODO(kevinb): Consider factory methods that reject duplicates
    199
    200      /**
    201       * Returns an immutable sorted set containing the given elements sorted by
    202       * their natural ordering. When multiple elements are equivalent according to
    203       * {@link Comparable#compareTo}, only the first one specified is included.
    204       *
    205       * @throws NullPointerException if any of {@code elements} is null
    206       * @deprecated use {@link #copyOf(Comparable[])}. <b>This method is scheduled
    207       *     for deletion in October 2011.</b>
    208       * @since 2.0 (changed from varargs in 3.0)
    209       */
    210      @Deprecated
    211      public
    212      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.0
    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 E not being a subtype of Comparable.
    259        // Unsafe, see ImmutableSortedSetFauxverideShim.
    260        @SuppressWarnings("unchecked")
    261        Ordering<E> naturalOrder = (Ordering<E>) 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.0 (source-compatible since 2.0)
    293       */
    294      public static <E> ImmutableSortedSet<E> copyOf(
    295          Collection<? extends E> elements) {
    296        // Hack around E not being a subtype of Comparable.
    297        // Unsafe, see ImmutableSortedSetFauxverideShim.
    298        @SuppressWarnings("unchecked")
    299        Ordering<E> naturalOrder = (Ordering<E>) 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 E not being a subtype of Comparable.
    317        // Unsafe, see ImmutableSortedSetFauxverideShim.
    318        @SuppressWarnings("unchecked")
    319        Ordering<E> naturalOrder = (Ordering<E>) 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);
    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.0 (source-compatible since 2.0)
    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);
    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 sortedSet} 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 = (Comparator<? super E>) NATURAL_ORDER;
    403        }
    404        return copyOfInternal(comparator, sortedSet);
    405      }
    406
    407      private static <E> ImmutableSortedSet<E> copyOfInternal(
    408          Comparator<? super E> comparator, Iterable<? extends E> elements) {
    409        boolean hasSameComparator =
    410            SortedIterables.hasSameComparator(comparator, elements);
    411
    412        if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
    413          @SuppressWarnings("unchecked")
    414          ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
    415          if (!original.isPartialView()) {
    416            return original;
    417          }
    418        }
    419        ImmutableList<E> list = ImmutableList.copyOf(
    420            SortedIterables.sortedUnique(comparator, elements));
    421        return list.isEmpty()
    422            ? ImmutableSortedSet.<E>emptySet(comparator)
    423            : new RegularImmutableSortedSet<E>(list, comparator);
    424      }
    425
    426      private static <E> ImmutableSortedSet<E> copyOfInternal(
    427          Comparator<? super E> comparator, Iterator<? extends E> elements) {
    428        ImmutableList<E> list =
    429            ImmutableList.copyOf(SortedIterables.sortedUnique(comparator, elements));
    430        return list.isEmpty()
    431            ? ImmutableSortedSet.<E>emptySet(comparator)
    432            : new RegularImmutableSortedSet<E>(list, comparator);
    433      }
    434
    435      /**
    436       * Returns a builder that creates immutable sorted sets with an explicit
    437       * comparator. If the comparator has a more general type than the set being
    438       * generated, such as creating a {@code SortedSet<Integer>} with a
    439       * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
    440       *
    441       * @throws NullPointerException if {@code comparator} is null
    442       */
    443      public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
    444        return new Builder<E>(comparator);
    445      }
    446
    447      /**
    448       * Returns a builder that creates immutable sorted sets whose elements are
    449       * ordered by the reverse of their natural ordering.
    450       *
    451       * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
    452       * than {@code Comparable<? super E>} as a workaround for javac <a
    453       * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
    454       * 6468354</a>.
    455       */
    456      public static <E extends Comparable<E>> Builder<E> reverseOrder() {
    457        return new Builder<E>(Ordering.natural().reverse());
    458      }
    459
    460      /**
    461       * Returns a builder that creates immutable sorted sets whose elements are
    462       * ordered by their natural ordering. The sorted sets use {@link
    463       * Ordering#natural()} as the comparator. This method provides more
    464       * type-safety than {@link #builder}, as it can be called only for classes
    465       * that implement {@link Comparable}.
    466       *
    467       * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
    468       * than {@code Comparable<? super E>} as a workaround for javac <a
    469       * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
    470       * 6468354</a>.
    471       */
    472      public static <E extends Comparable<E>> Builder<E> naturalOrder() {
    473        return new Builder<E>(Ordering.natural());
    474      }
    475
    476      /**
    477       * A builder for creating immutable sorted set instances, especially {@code
    478       * public static final} sets ("constant sets"), with a given comparator.
    479       * Example: <pre>   {@code
    480       *
    481       *   public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
    482       *       new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
    483       *           .addAll(SINGLE_DIGIT_PRIMES)
    484       *           .add(42)
    485       *           .build();}</pre>
    486       *
    487       * Builder instances can be reused; it is safe to call {@link #build} multiple
    488       * times to build multiple sets in series. Each set is a superset of the set
    489       * created before it.
    490       *
    491       * @since 2.0 (imported from Google Collections Library)
    492       */
    493      public static final class Builder<E> extends ImmutableSet.Builder<E> {
    494        private final Comparator<? super E> comparator;
    495
    496        /**
    497         * Creates a new builder. The returned builder is equivalent to the builder
    498         * generated by {@link ImmutableSortedSet#orderedBy}.
    499         */
    500        public Builder(Comparator<? super E> comparator) {
    501          this.comparator = checkNotNull(comparator);
    502        }
    503
    504        /**
    505         * Adds {@code element} to the {@code ImmutableSortedSet}.  If the
    506         * {@code ImmutableSortedSet} already contains {@code element}, then
    507         * {@code add} has no effect. (only the previously added element
    508         * is retained).
    509         *
    510         * @param element the element to add
    511         * @return this {@code Builder} object
    512         * @throws NullPointerException if {@code element} is null
    513         */
    514        @Override public Builder<E> add(E element) {
    515          super.add(element);
    516          return this;
    517        }
    518
    519        /**
    520         * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
    521         * ignoring duplicate elements (only the first duplicate element is added).
    522         *
    523         * @param elements the elements to add
    524         * @return this {@code Builder} object
    525         * @throws NullPointerException if {@code elements} contains a null element
    526         */
    527        @Override public Builder<E> add(E... elements) {
    528          super.add(elements);
    529          return this;
    530        }
    531
    532        /**
    533         * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
    534         * ignoring duplicate elements (only the first duplicate element is added).
    535         *
    536         * @param elements the elements to add to the {@code ImmutableSortedSet}
    537         * @return this {@code Builder} object
    538         * @throws NullPointerException if {@code elements} contains a null element
    539         */
    540        @Override public Builder<E> addAll(Iterable<? extends E> elements) {
    541          super.addAll(elements);
    542          return this;
    543        }
    544
    545        /**
    546         * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
    547         * ignoring duplicate elements (only the first duplicate element is added).
    548         *
    549         * @param elements the elements to add to the {@code ImmutableSortedSet}
    550         * @return this {@code Builder} object
    551         * @throws NullPointerException if {@code elements} contains a null element
    552         */
    553        @Override public Builder<E> addAll(Iterator<? extends E> elements) {
    554          super.addAll(elements);
    555          return this;
    556        }
    557
    558        /**
    559         * Returns a newly-created {@code ImmutableSortedSet} based on the contents
    560         * of the {@code Builder} and its comparator.
    561         */
    562        @Override public ImmutableSortedSet<E> build() {
    563          return copyOfInternal(comparator, contents.iterator());
    564        }
    565      }
    566
    567      int unsafeCompare(Object a, Object b) {
    568        return unsafeCompare(comparator, a, b);
    569      }
    570
    571      static int unsafeCompare(
    572          Comparator<?> comparator, Object a, Object b) {
    573        // Pretend the comparator can compare anything. If it turns out it can't
    574        // compare a and b, we should get a CCE on the subsequent line. Only methods
    575        // that are spec'd to throw CCE should call this.
    576        @SuppressWarnings("unchecked")
    577        Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
    578        return unsafeComparator.compare(a, b);
    579      }
    580
    581      final transient Comparator<? super E> comparator;
    582
    583      ImmutableSortedSet(Comparator<? super E> comparator) {
    584        this.comparator = comparator;
    585      }
    586
    587      /**
    588       * Returns the comparator that orders the elements, which is
    589       * {@link Ordering#natural()} when the natural ordering of the
    590       * elements is used. Note that its behavior is not consistent with
    591       * {@link SortedSet#comparator()}, which returns {@code null} to indicate
    592       * natural ordering.
    593       */
    594      @Override
    595      public Comparator<? super E> comparator() {
    596        return comparator;
    597      }
    598
    599      @Override // needed to unify the iterator() methods in Collection and SortedIterable
    600      public abstract UnmodifiableIterator<E> iterator();
    601
    602      /**
    603       * {@inheritDoc}
    604       *
    605       * <p>This method returns a serializable {@code ImmutableSortedSet}.
    606       *
    607       * <p>The {@link SortedSet#headSet} documentation states that a subset of a
    608       * subset throws an {@link IllegalArgumentException} if passed a
    609       * {@code toElement} greater than an earlier {@code toElement}. However, this
    610       * method doesn't throw an exception in that situation, but instead keeps the
    611       * original {@code toElement}.
    612       */
    613      @Override
    614      public ImmutableSortedSet<E> headSet(E toElement) {
    615        return headSet(toElement, false);
    616      }
    617
    618      ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
    619        return headSetImpl(checkNotNull(toElement), inclusive);
    620      }
    621
    622      /**
    623       * {@inheritDoc}
    624       *
    625       * <p>This method returns a serializable {@code ImmutableSortedSet}.
    626       *
    627       * <p>The {@link SortedSet#subSet} documentation states that a subset of a
    628       * subset throws an {@link IllegalArgumentException} if passed a
    629       * {@code fromElement} smaller than an earlier {@code fromElement}. However,
    630       * this method doesn't throw an exception in that situation, but instead keeps
    631       * the original {@code fromElement}. Similarly, this method keeps the
    632       * original {@code toElement}, instead of throwing an exception, if passed a
    633       * {@code toElement} greater than an earlier {@code toElement}.
    634       */
    635      @Override
    636      public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
    637        return subSet(fromElement, true, toElement, false);
    638      }
    639
    640      ImmutableSortedSet<E> subSet(
    641          E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
    642        checkNotNull(fromElement);
    643        checkNotNull(toElement);
    644        checkArgument(comparator.compare(fromElement, toElement) <= 0);
    645        return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
    646      }
    647
    648      /**
    649       * {@inheritDoc}
    650       *
    651       * <p>This method returns a serializable {@code ImmutableSortedSet}.
    652       *
    653       * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
    654       * subset throws an {@link IllegalArgumentException} if passed a
    655       * {@code fromElement} smaller than an earlier {@code fromElement}. However,
    656       * this method doesn't throw an exception in that situation, but instead keeps
    657       * the original {@code fromElement}.
    658       */
    659      @Override
    660      public ImmutableSortedSet<E> tailSet(E fromElement) {
    661        return tailSet(fromElement, true);
    662      }
    663
    664      ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
    665        return tailSetImpl(checkNotNull(fromElement), inclusive);
    666      }
    667
    668      /*
    669       * These methods perform most headSet, subSet, and tailSet logic, besides
    670       * parameter validation.
    671       */
    672      abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
    673
    674      abstract ImmutableSortedSet<E> subSetImpl(
    675          E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
    676
    677      abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
    678
    679      /**
    680       * Returns the position of an element within the set, or -1 if not present.
    681       */
    682      abstract int indexOf(@Nullable Object target);
    683
    684      /*
    685       * This class is used to serialize all ImmutableSortedSet instances,
    686       * regardless of implementation type. It captures their "logical contents"
    687       * only. This is necessary to ensure that the existence of a particular
    688       * implementation type is an implementation detail.
    689       */
    690      private static class SerializedForm<E> implements Serializable {
    691        final Comparator<? super E> comparator;
    692        final Object[] elements;
    693
    694        public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
    695          this.comparator = comparator;
    696          this.elements = elements;
    697        }
    698
    699        @SuppressWarnings("unchecked")
    700        Object readResolve() {
    701          return new Builder<E>(comparator).add((E[]) elements).build();
    702        }
    703
    704        private static final long serialVersionUID = 0;
    705      }
    706
    707      private void readObject(ObjectInputStream stream)
    708          throws InvalidObjectException {
    709        throw new InvalidObjectException("Use SerializedForm");
    710      }
    711
    712      @Override Object writeReplace() {
    713        return new SerializedForm<E>(comparator, toArray());
    714      }
    715    }