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    import com.google.common.annotations.GwtIncompatible;
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.NavigableSet;
036    import java.util.SortedSet;
037    
038    import javax.annotation.Nullable;
039    
040    /**
041     * An immutable {@code SortedSet} that stores its elements in a sorted array.
042     * Some instances are ordered by an explicit comparator, while others follow the
043     * natural sort ordering of their elements. Either way, null elements are not
044     * supported.
045     *
046     * <p>Unlike {@link Collections#unmodifiableSortedSet}, which is a <i>view</i>
047     * of a separate collection that can still change, an instance of {@code
048     * ImmutableSortedSet} contains its own private data and will <i>never</i>
049     * change. This class is convenient for {@code public static final} sets
050     * ("constant sets") and also lets you easily make a "defensive copy" of a set
051     * provided to your class by a caller.
052     *
053     * <p>The sets returned by the {@link #headSet}, {@link #tailSet}, and
054     * {@link #subSet} methods share the same array as the original set, preventing
055     * that array from being garbage collected. If this is a concern, the data may
056     * be copied into a correctly-sized array by calling {@link #copyOfSorted}.
057     *
058     * <p><b>Note on element equivalence:</b> The {@link #contains(Object)},
059     * {@link #containsAll(Collection)}, and {@link #equals(Object)}
060     * implementations must check whether a provided object is equivalent to an
061     * element in the collection. Unlike most collections, an
062     * {@code ImmutableSortedSet} doesn't use {@link Object#equals} to determine if
063     * two elements are equivalent. Instead, with an explicit comparator, the
064     * following relation determines whether elements {@code x} and {@code y} are
065     * equivalent: <pre>   {@code
066     *
067     *   {(x, y) | comparator.compare(x, y) == 0}}</pre>
068     *
069     * With natural ordering of elements, the following relation determines whether
070     * two elements are equivalent: <pre>   {@code
071     *
072     *   {(x, y) | x.compareTo(y) == 0}}</pre>
073     *
074     * <b>Warning:</b> Like most sets, an {@code ImmutableSortedSet} will not
075     * function correctly if an element is modified after being placed in the set.
076     * For this reason, and to avoid general confusion, it is strongly recommended
077     * to place only immutable objects into this collection.
078     *
079     * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
080     * it has no public or protected constructors. Thus, instances of this type are
081     * guaranteed to be immutable.
082     *
083     * <p>See the Guava User Guide article on <a href=
084     * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
085     * immutable collections</a>.
086     *
087     * @see ImmutableSet
088     * @author Jared Levy
089     * @author Louis Wasserman
090     * @since 2.0 (imported from Google Collections Library; implements {@code NavigableSet} since 12.0)
091     */
092    // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
093    @GwtCompatible(serializable = true, emulated = true)
094    @SuppressWarnings("serial") // we're overriding default serialization
095    public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
096        implements NavigableSet<E>, SortedIterable<E> {
097    
098      private static final Comparator<Comparable> NATURAL_ORDER =
099          Ordering.natural();
100    
101      private static final ImmutableSortedSet<Comparable> NATURAL_EMPTY_SET =
102          new EmptyImmutableSortedSet<Comparable>(NATURAL_ORDER);
103    
104      @SuppressWarnings("unchecked")
105      private static <E> ImmutableSortedSet<E> emptySet() {
106        return (ImmutableSortedSet<E>) NATURAL_EMPTY_SET;
107      }
108    
109      static <E> ImmutableSortedSet<E> emptySet(
110          Comparator<? super E> comparator) {
111        if (NATURAL_ORDER.equals(comparator)) {
112          return emptySet();
113        } else {
114          return new EmptyImmutableSortedSet<E>(comparator);
115        }
116      }
117    
118      /**
119       * Returns the empty immutable sorted set.
120       */
121      public static <E> ImmutableSortedSet<E> of() {
122        return emptySet();
123      }
124    
125      /**
126       * Returns an immutable sorted set containing a single element.
127       */
128      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
129          E element) {
130        return new RegularImmutableSortedSet<E>(
131            ImmutableList.of(element), Ordering.natural());
132      }
133    
134      /**
135       * Returns an immutable sorted set containing the given elements sorted by
136       * their natural ordering. When multiple elements are equivalent according to
137       * {@link Comparable#compareTo}, only the first one specified is included.
138       *
139       * @throws NullPointerException if any element is null
140       */
141      @SuppressWarnings("unchecked")
142      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
143          E e1, E e2) {
144        return copyOf(Ordering.natural(), Arrays.asList(e1, e2));
145      }
146    
147      /**
148       * Returns an immutable sorted set containing the given elements sorted by
149       * their natural ordering. When multiple elements are equivalent according to
150       * {@link Comparable#compareTo}, only the first one specified is included.
151       *
152       * @throws NullPointerException if any element is null
153       */
154      @SuppressWarnings("unchecked")
155      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
156          E e1, E e2, E e3) {
157        return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3));
158      }
159    
160      /**
161       * Returns an immutable sorted set containing the given elements sorted by
162       * their natural ordering. When multiple elements are equivalent according to
163       * {@link Comparable#compareTo}, only the first one specified is included.
164       *
165       * @throws NullPointerException if any element is null
166       */
167      @SuppressWarnings("unchecked")
168      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
169          E e1, E e2, E e3, E e4) {
170        return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4));
171      }
172    
173      /**
174       * Returns an immutable sorted set containing the given elements sorted by
175       * their natural ordering. When multiple elements are equivalent according to
176       * {@link Comparable#compareTo}, only the first one specified is included.
177       *
178       * @throws NullPointerException if any element is null
179       */
180      @SuppressWarnings("unchecked")
181      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
182          E e1, E e2, E e3, E e4, E e5) {
183        return copyOf(Ordering.natural(), Arrays.asList(e1, e2, e3, e4, e5));
184      }
185    
186      /**
187       * Returns an immutable sorted set containing the given elements sorted by
188       * their natural ordering. When multiple elements are equivalent according to
189       * {@link Comparable#compareTo}, only the first one specified is included.
190       *
191       * @throws NullPointerException if any element is null
192       * @since 3.0 (source-compatible since 2.0)
193       */
194      @SuppressWarnings("unchecked")
195      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
196          E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
197        int size = remaining.length + 6;
198        List<E> all = new ArrayList<E>(size);
199        Collections.addAll(all, e1, e2, e3, e4, e5, e6);
200        Collections.addAll(all, remaining);
201        return copyOf(Ordering.natural(), all);
202      }
203    
204      // TODO(kevinb): Consider factory methods that reject duplicates
205    
206      /**
207       * Returns an immutable sorted set containing the given elements sorted by
208       * their natural ordering. When multiple elements are equivalent according to
209       * {@link Comparable#compareTo}, only the first one specified is included.
210       *
211       * @throws NullPointerException if any of {@code elements} is null
212       * @since 3.0
213       */
214      public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
215          E[] elements) {
216        return copyOf(Ordering.natural(), Arrays.asList(elements));
217      }
218    
219      /**
220       * Returns an immutable sorted set containing the given elements sorted by
221       * their natural ordering. When multiple elements are equivalent according to
222       * {@code compareTo()}, only the first one specified is included. To create a
223       * copy of a {@code SortedSet} that preserves the comparator, call {@link
224       * #copyOfSorted} instead. This method iterates over {@code elements} at most
225       * once.
226    
227       *
228       * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
229       * ImmutableSortedSet.copyOf(s)} returns an {@code ImmutableSortedSet<String>}
230       * containing each of the strings in {@code s}, while {@code
231       * ImmutableSortedSet.of(s)} returns an {@code
232       * ImmutableSortedSet<Set<String>>} containing one element (the given set
233       * itself).
234       *
235       * <p>Despite the method name, this method attempts to avoid actually copying
236       * the data when it is safe to do so. The exact circumstances under which a
237       * copy will or will not be performed are undocumented and subject to change.
238       *
239       * <p>This method is not type-safe, as it may be called on elements that are
240       * not mutually comparable.
241       *
242       * @throws ClassCastException if the elements are not mutually comparable
243       * @throws NullPointerException if any of {@code elements} is null
244       */
245      public static <E> ImmutableSortedSet<E> copyOf(
246          Iterable<? extends E> elements) {
247        // Hack around E not being a subtype of Comparable.
248        // Unsafe, see ImmutableSortedSetFauxverideShim.
249        @SuppressWarnings("unchecked")
250        Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
251        return copyOf(naturalOrder, elements);
252      }
253    
254      /**
255       * Returns an immutable sorted set containing the given elements sorted by
256       * their natural ordering. When multiple elements are equivalent according to
257       * {@code compareTo()}, only the first one specified is included. To create a
258       * copy of a {@code SortedSet} that preserves the comparator, call
259       * {@link #copyOfSorted} instead. This method iterates over {@code elements}
260       * at most once.
261       *
262       * <p>Note that if {@code s} is a {@code Set<String>}, then
263       * {@code ImmutableSortedSet.copyOf(s)} returns an
264       * {@code ImmutableSortedSet<String>} containing each of the strings in
265       * {@code s}, while {@code ImmutableSortedSet.of(s)} returns an
266       * {@code ImmutableSortedSet<Set<String>>} containing one element (the given
267       * set itself).
268       *
269       * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
270       * is an {@code ImmutableSortedSet}, it may be returned instead of a copy.
271       *
272       * <p>This method is not type-safe, as it may be called on elements that are
273       * not mutually comparable.
274       *
275       * <p>This method is safe to use even when {@code elements} is a synchronized
276       * or concurrent collection that is currently being modified by another
277       * thread.
278       *
279       * @throws ClassCastException if the elements are not mutually comparable
280       * @throws NullPointerException if any of {@code elements} is null
281       * @since 7.0 (source-compatible since 2.0)
282       */
283      public static <E> ImmutableSortedSet<E> copyOf(
284          Collection<? extends E> elements) {
285        // Hack around E not being a subtype of Comparable.
286        // Unsafe, see ImmutableSortedSetFauxverideShim.
287        @SuppressWarnings("unchecked")
288        Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
289        return copyOf(naturalOrder, elements);
290      }
291    
292      /**
293       * Returns an immutable sorted set containing the given elements sorted by
294       * their natural ordering. When multiple elements are equivalent according to
295       * {@code compareTo()}, only the first one specified is included.
296       *
297       * <p>This method is not type-safe, as it may be called on elements that are
298       * not mutually comparable.
299       *
300       * @throws ClassCastException if the elements are not mutually comparable
301       * @throws NullPointerException if any of {@code elements} is null
302       */
303      public static <E> ImmutableSortedSet<E> copyOf(
304          Iterator<? extends E> elements) {
305        // Hack around E not being a subtype of Comparable.
306        // Unsafe, see ImmutableSortedSetFauxverideShim.
307        @SuppressWarnings("unchecked")
308        Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
309        return copyOfInternal(naturalOrder, elements);
310      }
311    
312      /**
313       * Returns an immutable sorted set containing the given elements sorted by
314       * the given {@code Comparator}. When multiple elements are equivalent
315       * according to {@code compareTo()}, only the first one specified is
316       * included.
317       *
318       * @throws NullPointerException if {@code comparator} or any of
319       *     {@code elements} is null
320       */
321      public static <E> ImmutableSortedSet<E> copyOf(
322          Comparator<? super E> comparator, Iterator<? extends E> elements) {
323        checkNotNull(comparator);
324        return copyOfInternal(comparator, elements);
325      }
326    
327      /**
328       * Returns an immutable sorted set containing the given elements sorted by
329       * the given {@code Comparator}. When multiple elements are equivalent
330       * according to {@code compare()}, only the first one specified is
331       * included. This method iterates over {@code elements} at most once.
332       *
333       * <p>Despite the method name, this method attempts to avoid actually copying
334       * the data when it is safe to do so. The exact circumstances under which a
335       * copy will or will not be performed are undocumented and subject to change.
336       *
337       * @throws NullPointerException if {@code comparator} or any of {@code
338       *         elements} is null
339       */
340      public static <E> ImmutableSortedSet<E> copyOf(
341          Comparator<? super E> comparator, Iterable<? extends E> elements) {
342        checkNotNull(comparator);
343        return copyOfInternal(comparator, elements);
344      }
345    
346      /**
347       * Returns an immutable sorted set containing the given elements sorted by
348       * the given {@code Comparator}. When multiple elements are equivalent
349       * according to {@code compareTo()}, only the first one specified is
350       * included.
351       *
352       * <p>Despite the method name, this method attempts to avoid actually copying
353       * the data when it is safe to do so. The exact circumstances under which a
354       * copy will or will not be performed are undocumented and subject to change.
355       *
356       * <p>This method is safe to use even when {@code elements} is a synchronized
357       * or concurrent collection that is currently being modified by another
358       * thread.
359       *
360       * @throws NullPointerException if {@code comparator} or any of
361       *     {@code elements} is null
362       * @since 7.0 (source-compatible since 2.0)
363       */
364      public static <E> ImmutableSortedSet<E> copyOf(
365          Comparator<? super E> comparator, Collection<? extends E> elements) {
366        checkNotNull(comparator);
367        return copyOfInternal(comparator, elements);
368      }
369    
370      /**
371       * Returns an immutable sorted set containing the elements of a sorted set,
372       * sorted by the same {@code Comparator}. That behavior differs from {@link
373       * #copyOf(Iterable)}, which always uses the natural ordering of the
374       * elements.
375       *
376       * <p>Despite the method name, this method attempts to avoid actually copying
377       * the data when it is safe to do so. The exact circumstances under which a
378       * copy will or will not be performed are undocumented and subject to change.
379       *
380       * <p>This method is safe to use even when {@code sortedSet} is a synchronized
381       * or concurrent collection that is currently being modified by another
382       * thread.
383       *
384       * @throws NullPointerException if {@code sortedSet} or any of its elements
385       *     is null
386       */
387      @SuppressWarnings("unchecked")
388      public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
389        Comparator<? super E> comparator = sortedSet.comparator();
390        if (comparator == null) {
391          comparator = (Comparator<? super E>) NATURAL_ORDER;
392        }
393        return copyOfInternal(comparator, sortedSet);
394      }
395    
396      private static <E> ImmutableSortedSet<E> copyOfInternal(
397          Comparator<? super E> comparator, Iterable<? extends E> elements) {
398        boolean hasSameComparator =
399            SortedIterables.hasSameComparator(comparator, elements);
400    
401        if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
402          @SuppressWarnings("unchecked")
403          ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
404          if (!original.isPartialView()) {
405            return original;
406          }
407        }
408        ImmutableList<E> list = ImmutableList.copyOf(
409            SortedIterables.sortedUnique(comparator, elements));
410        return list.isEmpty()
411            ? ImmutableSortedSet.<E>emptySet(comparator)
412            : new RegularImmutableSortedSet<E>(list, comparator);
413      }
414    
415      private static <E> ImmutableSortedSet<E> copyOfInternal(
416          Comparator<? super E> comparator, Iterator<? extends E> elements) {
417        ImmutableList<E> list =
418            ImmutableList.copyOf(SortedIterables.sortedUnique(comparator, elements));
419        return list.isEmpty()
420            ? ImmutableSortedSet.<E>emptySet(comparator)
421            : new RegularImmutableSortedSet<E>(list, comparator);
422      }
423    
424      /**
425       * Returns a builder that creates immutable sorted sets with an explicit
426       * comparator. If the comparator has a more general type than the set being
427       * generated, such as creating a {@code SortedSet<Integer>} with a
428       * {@code Comparator<Number>}, use the {@link Builder} constructor instead.
429       *
430       * @throws NullPointerException if {@code comparator} is null
431       */
432      public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
433        return new Builder<E>(comparator);
434      }
435    
436      /**
437       * Returns a builder that creates immutable sorted sets whose elements are
438       * ordered by the reverse of their natural ordering.
439       *
440       * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
441       * than {@code Comparable<? super E>} as a workaround for javac <a
442       * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
443       * 6468354</a>.
444       */
445      public static <E extends Comparable<E>> Builder<E> reverseOrder() {
446        return new Builder<E>(Ordering.natural().reverse());
447      }
448    
449      /**
450       * Returns a builder that creates immutable sorted sets whose elements are
451       * ordered by their natural ordering. The sorted sets use {@link
452       * Ordering#natural()} as the comparator. This method provides more
453       * type-safety than {@link #builder}, as it can be called only for classes
454       * that implement {@link Comparable}.
455       *
456       * <p>Note: the type parameter {@code E} extends {@code Comparable<E>} rather
457       * than {@code Comparable<? super E>} as a workaround for javac <a
458       * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
459       * 6468354</a>.
460       */
461      public static <E extends Comparable<E>> Builder<E> naturalOrder() {
462        return new Builder<E>(Ordering.natural());
463      }
464    
465      /**
466       * A builder for creating immutable sorted set instances, especially {@code
467       * public static final} sets ("constant sets"), with a given comparator.
468       * Example: <pre>   {@code
469       *
470       *   public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
471       *       new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
472       *           .addAll(SINGLE_DIGIT_PRIMES)
473       *           .add(42)
474       *           .build();}</pre>
475       *
476       * Builder instances can be reused; it is safe to call {@link #build} multiple
477       * times to build multiple sets in series. Each set is a superset of the set
478       * created before it.
479       *
480       * @since 2.0 (imported from Google Collections Library)
481       */
482      public static final class Builder<E> extends ImmutableSet.Builder<E> {
483        private final Comparator<? super E> comparator;
484    
485        /**
486         * Creates a new builder. The returned builder is equivalent to the builder
487         * generated by {@link ImmutableSortedSet#orderedBy}.
488         */
489        public Builder(Comparator<? super E> comparator) {
490          this.comparator = checkNotNull(comparator);
491        }
492    
493        /**
494         * Adds {@code element} to the {@code ImmutableSortedSet}.  If the
495         * {@code ImmutableSortedSet} already contains {@code element}, then
496         * {@code add} has no effect. (only the previously added element
497         * is retained).
498         *
499         * @param element the element to add
500         * @return this {@code Builder} object
501         * @throws NullPointerException if {@code element} is null
502         */
503        @Override public Builder<E> add(E element) {
504          super.add(element);
505          return this;
506        }
507    
508        /**
509         * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
510         * ignoring duplicate elements (only the first duplicate element is added).
511         *
512         * @param elements the elements to add
513         * @return this {@code Builder} object
514         * @throws NullPointerException if {@code elements} contains a null element
515         */
516        @Override public Builder<E> add(E... elements) {
517          super.add(elements);
518          return this;
519        }
520    
521        /**
522         * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
523         * ignoring duplicate elements (only the first duplicate element is added).
524         *
525         * @param elements the elements to add to the {@code ImmutableSortedSet}
526         * @return this {@code Builder} object
527         * @throws NullPointerException if {@code elements} contains a null element
528         */
529        @Override public Builder<E> addAll(Iterable<? extends E> elements) {
530          super.addAll(elements);
531          return this;
532        }
533    
534        /**
535         * Adds each element of {@code elements} to the {@code ImmutableSortedSet},
536         * ignoring duplicate elements (only the first duplicate element is added).
537         *
538         * @param elements the elements to add to the {@code ImmutableSortedSet}
539         * @return this {@code Builder} object
540         * @throws NullPointerException if {@code elements} contains a null element
541         */
542        @Override public Builder<E> addAll(Iterator<? extends E> elements) {
543          super.addAll(elements);
544          return this;
545        }
546    
547        /**
548         * Returns a newly-created {@code ImmutableSortedSet} based on the contents
549         * of the {@code Builder} and its comparator.
550         */
551        @Override public ImmutableSortedSet<E> build() {
552          return copyOfInternal(comparator, contents.iterator());
553        }
554      }
555    
556      int unsafeCompare(Object a, Object b) {
557        return unsafeCompare(comparator, a, b);
558      }
559    
560      static int unsafeCompare(
561          Comparator<?> comparator, Object a, Object b) {
562        // Pretend the comparator can compare anything. If it turns out it can't
563        // compare a and b, we should get a CCE on the subsequent line. Only methods
564        // that are spec'd to throw CCE should call this.
565        @SuppressWarnings("unchecked")
566        Comparator<Object> unsafeComparator = (Comparator<Object>) comparator;
567        return unsafeComparator.compare(a, b);
568      }
569    
570      final transient Comparator<? super E> comparator;
571    
572      ImmutableSortedSet(Comparator<? super E> comparator) {
573        this.comparator = comparator;
574      }
575    
576      /**
577       * Returns the comparator that orders the elements, which is
578       * {@link Ordering#natural()} when the natural ordering of the
579       * elements is used. Note that its behavior is not consistent with
580       * {@link SortedSet#comparator()}, which returns {@code null} to indicate
581       * natural ordering.
582       */
583      @Override
584      public Comparator<? super E> comparator() {
585        return comparator;
586      }
587    
588      @Override // needed to unify the iterator() methods in Collection and SortedIterable
589      public abstract UnmodifiableIterator<E> iterator();
590    
591      /**
592       * {@inheritDoc}
593       *
594       * <p>This method returns a serializable {@code ImmutableSortedSet}.
595       *
596       * <p>The {@link SortedSet#headSet} documentation states that a subset of a
597       * subset throws an {@link IllegalArgumentException} if passed a
598       * {@code toElement} greater than an earlier {@code toElement}. However, this
599       * method doesn't throw an exception in that situation, but instead keeps the
600       * original {@code toElement}.
601       */
602      @Override
603      public ImmutableSortedSet<E> headSet(E toElement) {
604        return headSet(toElement, false);
605      }
606    
607      /**
608       * @since 12.0
609       */
610      @GwtIncompatible("NavigableSet")
611      @Override
612      public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
613        return headSetImpl(checkNotNull(toElement), inclusive);
614      }
615    
616      /**
617       * {@inheritDoc}
618       *
619       * <p>This method returns a serializable {@code ImmutableSortedSet}.
620       *
621       * <p>The {@link SortedSet#subSet} documentation states that a subset of a
622       * subset throws an {@link IllegalArgumentException} if passed a
623       * {@code fromElement} smaller than an earlier {@code fromElement}. However,
624       * this method doesn't throw an exception in that situation, but instead keeps
625       * the original {@code fromElement}. Similarly, this method keeps the
626       * original {@code toElement}, instead of throwing an exception, if passed a
627       * {@code toElement} greater than an earlier {@code toElement}.
628       */
629      @Override
630      public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
631        return subSet(fromElement, true, toElement, false);
632      }
633    
634      /**
635       * @since 12.0
636       */
637      @GwtIncompatible("NavigableSet")
638      @Override
639      public ImmutableSortedSet<E> subSet(
640          E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
641        checkNotNull(fromElement);
642        checkNotNull(toElement);
643        checkArgument(comparator.compare(fromElement, toElement) <= 0);
644        return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
645      }
646    
647      /**
648       * {@inheritDoc}
649       *
650       * <p>This method returns a serializable {@code ImmutableSortedSet}.
651       *
652       * <p>The {@link SortedSet#tailSet} documentation states that a subset of a
653       * subset throws an {@link IllegalArgumentException} if passed a
654       * {@code fromElement} smaller than an earlier {@code fromElement}. However,
655       * this method doesn't throw an exception in that situation, but instead keeps
656       * the original {@code fromElement}.
657       */
658      @Override
659      public ImmutableSortedSet<E> tailSet(E fromElement) {
660        return tailSet(fromElement, true);
661      }
662    
663      /**
664       * @since 12.0
665       */
666      @GwtIncompatible("NavigableSet")
667      @Override
668      public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
669        return tailSetImpl(checkNotNull(fromElement), inclusive);
670      }
671    
672      /*
673       * These methods perform most headSet, subSet, and tailSet logic, besides
674       * parameter validation.
675       */
676      abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
677    
678      abstract ImmutableSortedSet<E> subSetImpl(
679          E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
680    
681      abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
682    
683      /**
684       * @since 12.0
685       */
686      @GwtIncompatible("NavigableSet")
687      @Override
688      public E lower(E e) {
689        return Iterables.getFirst(headSet(e, false).descendingSet(), null);
690      }
691    
692      /**
693       * @since 12.0
694       */
695      @GwtIncompatible("NavigableSet")
696      @Override
697      public E floor(E e) {
698        return Iterables.getFirst(headSet(e, true).descendingSet(), null);
699      }
700    
701      /**
702       * @since 12.0
703       */
704      @GwtIncompatible("NavigableSet")
705      @Override
706      public E ceiling(E e) {
707        return Iterables.getFirst(tailSet(e, true), null);
708      }
709    
710      /**
711       * @since 12.0
712       */
713      @GwtIncompatible("NavigableSet")
714      @Override
715      public E higher(E e) {
716        return Iterables.getFirst(tailSet(e, false), null);
717      }
718    
719      /**
720       * @since 12.0
721       */
722      @GwtIncompatible("NavigableSet")
723      @Override
724      public final E pollFirst() {
725        throw new UnsupportedOperationException();
726      }
727    
728      /**
729       * @since 12.0
730       */
731      @GwtIncompatible("NavigableSet")
732      @Override
733      public final E pollLast() {
734        throw new UnsupportedOperationException();
735      }
736    
737      @GwtIncompatible("NavigableSet")
738      transient ImmutableSortedSet<E> descendingSet;
739    
740      /**
741       * @since 12.0
742       */
743      @GwtIncompatible("NavigableSet")
744      @Override
745      public ImmutableSortedSet<E> descendingSet() {
746        ImmutableSortedSet<E> result = descendingSet;
747        if (result == null) {
748          result = descendingSet = createDescendingSet();
749          result.descendingSet = this;
750        }
751        return result;
752      }
753    
754      @GwtIncompatible("NavigableSet")
755      abstract ImmutableSortedSet<E> createDescendingSet();
756    
757      /**
758       * @since 12.0
759       */
760      @GwtIncompatible("NavigableSet")
761      @Override
762      public UnmodifiableIterator<E> descendingIterator() {
763        return descendingSet().iterator();
764      }
765    
766      /**
767       * Returns the position of an element within the set, or -1 if not present.
768       */
769      abstract int indexOf(@Nullable 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    }
803