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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.common.annotations.J2ktIncompatible;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import com.google.errorprone.annotations.DoNotCall;
029import com.google.errorprone.annotations.concurrent.LazyInit;
030import java.io.InvalidObjectException;
031import java.io.ObjectInputStream;
032import java.io.Serializable;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.Collections;
036import java.util.Comparator;
037import java.util.Iterator;
038import java.util.NavigableSet;
039import java.util.SortedSet;
040import java.util.stream.Collector;
041import javax.annotation.CheckForNull;
042import org.checkerframework.checker.nullness.qual.Nullable;
043
044/**
045 * A {@link NavigableSet} whose contents will never change, with many other important properties
046 * detailed at {@link ImmutableCollection}.
047 *
048 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
049 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
050 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
051 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting
052 * collection will not correctly obey its specification.
053 *
054 * <p>See the Guava User Guide article on <a href=
055 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
056 *
057 * @author Jared Levy
058 * @author Louis Wasserman
059 * @since 2.0 (implements {@code NavigableSet} since 12.0)
060 */
061// TODO(benyu): benchmark and optimize all creation paths, which are a mess now
062@GwtCompatible(serializable = true, emulated = true)
063@SuppressWarnings("serial") // we're overriding default serialization
064@ElementTypesAreNonnullByDefault
065public abstract class ImmutableSortedSet<E> extends ImmutableSet<E>
066    implements NavigableSet<E>, SortedIterable<E> {
067  /**
068   * Returns a {@code Collector} that accumulates the input elements into a new {@code
069   * ImmutableSortedSet}, ordered by the specified comparator.
070   *
071   * <p>If the elements contain duplicates (according to the comparator), only the first duplicate
072   * in encounter order will appear in the result.
073   *
074   * @since 33.2.0 (available since 21.0 in guava-jre)
075   */
076  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
077  @IgnoreJRERequirement // Users will use this only if they're already using streams.
078  @Beta // TODO: b/288085449 - Remove.
079  public static <E> Collector<E, ?, ImmutableSortedSet<E>> toImmutableSortedSet(
080      Comparator<? super E> comparator) {
081    return CollectCollectors.toImmutableSortedSet(comparator);
082  }
083
084  static <E> RegularImmutableSortedSet<E> emptySet(Comparator<? super E> comparator) {
085    if (Ordering.natural().equals(comparator)) {
086      @SuppressWarnings("unchecked") // The natural-ordered empty set supports all types.
087      RegularImmutableSortedSet<E> result =
088          (RegularImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
089      return result;
090    } else {
091      return new RegularImmutableSortedSet<>(ImmutableList.of(), comparator);
092    }
093  }
094
095  /**
096   * Returns the empty immutable sorted set.
097   *
098   * <p><b>Performance note:</b> the instance returned is a singleton.
099   */
100  @SuppressWarnings("unchecked") // The natural-ordered empty set supports all types.
101  public static <E> ImmutableSortedSet<E> of() {
102    return (ImmutableSortedSet<E>) RegularImmutableSortedSet.NATURAL_EMPTY_SET;
103  }
104
105  /** Returns an immutable sorted set containing a single element. */
106  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E element) {
107    return new RegularImmutableSortedSet<>(ImmutableList.of(element), Ordering.natural());
108  }
109
110  /**
111   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
112   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
113   * one specified is included.
114   *
115   * @throws NullPointerException if any element is null
116   */
117  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2) {
118    return construct(Ordering.natural(), 2, e1, e2);
119  }
120
121  /**
122   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
123   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
124   * one specified is included.
125   *
126   * @throws NullPointerException if any element is null
127   */
128  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
129    return construct(Ordering.natural(), 3, e1, e2, e3);
130  }
131
132  /**
133   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
134   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
135   * one specified is included.
136   *
137   * @throws NullPointerException if any element is null
138   */
139  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) {
140    return construct(Ordering.natural(), 4, e1, e2, e3, e4);
141  }
142
143  /**
144   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
145   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
146   * one specified is included.
147   *
148   * @throws NullPointerException if any element is null
149   */
150  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
151      E e1, E e2, E e3, E e4, E e5) {
152    return construct(Ordering.natural(), 5, e1, e2, e3, e4, e5);
153  }
154
155  /**
156   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
157   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
158   * one specified is included.
159   *
160   * @throws NullPointerException if any element is null
161   * @since 3.0 (source-compatible since 2.0)
162   */
163  @SuppressWarnings("unchecked")
164  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
165      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
166    Comparable<?>[] contents = new Comparable<?>[6 + remaining.length];
167    contents[0] = e1;
168    contents[1] = e2;
169    contents[2] = e3;
170    contents[3] = e4;
171    contents[4] = e5;
172    contents[5] = e6;
173    System.arraycopy(remaining, 0, contents, 6, remaining.length);
174    return construct(Ordering.natural(), contents.length, (E[]) contents);
175  }
176
177  // TODO(kevinb): Consider factory methods that reject duplicates
178
179  /**
180   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
181   * When multiple elements are equivalent according to {@link Comparable#compareTo}, only the first
182   * one specified is included.
183   *
184   * @throws NullPointerException if any of {@code elements} is null
185   * @since 3.0
186   */
187  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(E[] elements) {
188    return construct(Ordering.natural(), elements.length, elements.clone());
189  }
190
191  /**
192   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
193   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
194   * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
195   * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
196   *
197   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
198   * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
199   * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
200   * containing one element (the given set itself).
201   *
202   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
203   * safe to do so. The exact circumstances under which a copy will or will not be performed are
204   * undocumented and subject to change.
205   *
206   * <p>This method is not type-safe, as it may be called on elements that are not mutually
207   * comparable.
208   *
209   * @throws ClassCastException if the elements are not mutually comparable
210   * @throws NullPointerException if any of {@code elements} is null
211   */
212  public static <E> ImmutableSortedSet<E> copyOf(Iterable<? extends E> elements) {
213    // Hack around E not being a subtype of Comparable.
214    // Unsafe, see ImmutableSortedSetFauxverideShim.
215    @SuppressWarnings("unchecked")
216    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
217    return copyOf(naturalOrder, elements);
218  }
219
220  /**
221   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
222   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
223   * specified is included. To create a copy of a {@code SortedSet} that preserves the comparator,
224   * call {@link #copyOfSorted} instead. This method iterates over {@code elements} at most once.
225   *
226   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code ImmutableSortedSet.copyOf(s)}
227   * returns an {@code ImmutableSortedSet<String>} containing each of the strings in {@code s},
228   * while {@code ImmutableSortedSet.of(s)} returns an {@code ImmutableSortedSet<Set<String>>}
229   * containing one element (the given set itself).
230   *
231   * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} is an {@code
232   * ImmutableSortedSet}, it may be returned instead of a copy.
233   *
234   * <p>This method is not type-safe, as it may be called on elements that are not mutually
235   * comparable.
236   *
237   * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
238   * collection that is currently being modified by another thread.
239   *
240   * @throws ClassCastException if the elements are not mutually comparable
241   * @throws NullPointerException if any of {@code elements} is null
242   * @since 7.0 (source-compatible since 2.0)
243   */
244  public static <E> ImmutableSortedSet<E> copyOf(Collection<? extends E> elements) {
245    // Hack around E not being a subtype of Comparable.
246    // Unsafe, see ImmutableSortedSetFauxverideShim.
247    @SuppressWarnings("unchecked")
248    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
249    return copyOf(naturalOrder, elements);
250  }
251
252  /**
253   * Returns an immutable sorted set containing the given elements sorted by their natural ordering.
254   * When multiple elements are equivalent according to {@code compareTo()}, only the first one
255   * specified is included.
256   *
257   * <p>This method is not type-safe, as it may be called on elements that are not mutually
258   * comparable.
259   *
260   * @throws ClassCastException if the elements are not mutually comparable
261   * @throws NullPointerException if any of {@code elements} is null
262   */
263  public static <E> ImmutableSortedSet<E> copyOf(Iterator<? extends E> elements) {
264    // Hack around E not being a subtype of Comparable.
265    // Unsafe, see ImmutableSortedSetFauxverideShim.
266    @SuppressWarnings("unchecked")
267    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable<?>>natural();
268    return copyOf(naturalOrder, elements);
269  }
270
271  /**
272   * Returns an immutable sorted set containing the given elements sorted by the given {@code
273   * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
274   * first one specified is included.
275   *
276   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
277   */
278  public static <E> ImmutableSortedSet<E> copyOf(
279      Comparator<? super E> comparator, Iterator<? extends E> elements) {
280    return new Builder<E>(comparator).addAll(elements).build();
281  }
282
283  /**
284   * Returns an immutable sorted set containing the given elements sorted by the given {@code
285   * Comparator}. When multiple elements are equivalent according to {@code compare()}, only the
286   * first one specified is included. This method iterates over {@code elements} at most once.
287   *
288   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
289   * safe to do so. The exact circumstances under which a copy will or will not be performed are
290   * undocumented and subject to change.
291   *
292   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
293   */
294  public static <E> ImmutableSortedSet<E> copyOf(
295      Comparator<? super E> comparator, Iterable<? extends E> elements) {
296    checkNotNull(comparator);
297    boolean hasSameComparator = SortedIterables.hasSameComparator(comparator, elements);
298
299    if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
300      @SuppressWarnings("unchecked")
301      ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
302      if (!original.isPartialView()) {
303        return original;
304      }
305    }
306    @SuppressWarnings("unchecked") // elements only contains E's; it's safe.
307    E[] array = (E[]) Iterables.toArray(elements);
308    return construct(comparator, array.length, array);
309  }
310
311  /**
312   * Returns an immutable sorted set containing the given elements sorted by the given {@code
313   * Comparator}. When multiple elements are equivalent according to {@code compareTo()}, only the
314   * first one specified is included.
315   *
316   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
317   * safe to do so. The exact circumstances under which a copy will or will not be performed are
318   * undocumented and subject to change.
319   *
320   * <p>This method is safe to use even when {@code elements} is a synchronized or concurrent
321   * collection that is currently being modified by another thread.
322   *
323   * @throws NullPointerException if {@code comparator} or any of {@code elements} is null
324   * @since 7.0 (source-compatible since 2.0)
325   */
326  public static <E> ImmutableSortedSet<E> copyOf(
327      Comparator<? super E> comparator, Collection<? extends E> elements) {
328    return copyOf(comparator, (Iterable<? extends E>) elements);
329  }
330
331  /**
332   * Returns an immutable sorted set containing the elements of a sorted set, sorted by the same
333   * {@code Comparator}. That behavior differs from {@link #copyOf(Iterable)}, which always uses the
334   * natural ordering of the elements.
335   *
336   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
337   * safe to do so. The exact circumstances under which a copy will or will not be performed are
338   * undocumented and subject to change.
339   *
340   * <p>This method is safe to use even when {@code sortedSet} is a synchronized or concurrent
341   * collection that is currently being modified by another thread.
342   *
343   * @throws NullPointerException if {@code sortedSet} or any of its elements is null
344   */
345  public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
346    Comparator<? super E> comparator = SortedIterables.comparator(sortedSet);
347    ImmutableList<E> list = ImmutableList.copyOf(sortedSet);
348    if (list.isEmpty()) {
349      return emptySet(comparator);
350    } else {
351      return new RegularImmutableSortedSet<>(list, comparator);
352    }
353  }
354
355  /**
356   * Constructs an {@code ImmutableSortedSet} from the first {@code n} elements of {@code contents}.
357   * If {@code k} is the size of the returned {@code ImmutableSortedSet}, then the sorted unique
358   * elements are in the first {@code k} positions of {@code contents}, and {@code contents[i] ==
359   * null} for {@code k <= i < n}.
360   *
361   * <p>This method takes ownership of {@code contents}; do not modify {@code contents} after this
362   * returns.
363   *
364   * @throws NullPointerException if any of the first {@code n} elements of {@code contents} is null
365   */
366  static <E> ImmutableSortedSet<E> construct(
367      Comparator<? super E> comparator, int n, E... contents) {
368    if (n == 0) {
369      return emptySet(comparator);
370    }
371    checkElementsNotNull(contents, n);
372    Arrays.sort(contents, 0, n, comparator);
373    int uniques = 1;
374    for (int i = 1; i < n; i++) {
375      E cur = contents[i];
376      E prev = contents[uniques - 1];
377      if (comparator.compare(cur, prev) != 0) {
378        contents[uniques++] = cur;
379      }
380    }
381    Arrays.fill(contents, uniques, n, null);
382    if (uniques < contents.length / 2) {
383      // Deduplication eliminated many of the elements.  We don't want to retain an arbitrarily
384      // large array relative to the number of elements, so we cap the ratio.
385      contents = Arrays.copyOf(contents, uniques);
386    }
387    return new RegularImmutableSortedSet<E>(
388        ImmutableList.<E>asImmutableList(contents, uniques), comparator);
389  }
390
391  /**
392   * Returns a builder that creates immutable sorted sets with an explicit comparator. If the
393   * comparator has a more general type than the set being generated, such as creating a {@code
394   * SortedSet<Integer>} with a {@code Comparator<Number>}, use the {@link Builder} constructor
395   * instead.
396   *
397   * @throws NullPointerException if {@code comparator} is null
398   */
399  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
400    return new Builder<>(comparator);
401  }
402
403  /**
404   * Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse
405   * of their natural ordering.
406   */
407  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
408    return new Builder<>(Collections.reverseOrder());
409  }
410
411  /**
412   * Returns a builder that creates immutable sorted sets whose elements are ordered by their
413   * natural ordering. The sorted sets use {@link Ordering#natural()} as the comparator. This method
414   * provides more type-safety than {@link #builder}, as it can be called only for classes that
415   * implement {@link Comparable}.
416   */
417  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
418    return new Builder<>(Ordering.natural());
419  }
420
421  /**
422   * A builder for creating immutable sorted set instances, especially {@code public static final}
423   * sets ("constant sets"), with a given comparator. Example:
424   *
425   * <pre>{@code
426   * public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
427   *     new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
428   *         .addAll(SINGLE_DIGIT_PRIMES)
429   *         .add(42)
430   *         .build();
431   * }</pre>
432   *
433   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
434   * multiple sets in series. Each set is a superset of the set created before it.
435   *
436   * @since 2.0
437   */
438  public static final class Builder<E> extends ImmutableSet.Builder<E> {
439    private final Comparator<? super E> comparator;
440
441    /**
442     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
443     * ImmutableSortedSet#orderedBy}.
444     */
445    /*
446     * TODO(cpovirk): use Object[] instead of E[] in the mainline? (The backport is different and
447     * doesn't need this suppression, but we keep it to minimize diffs.) Generally be more clear
448     * about when we have an Object[] vs. a Comparable[] or other array type in internalArray? If we
449     * used Object[], we might be able to optimize toArray() to use clone() sometimes. (See
450     * cl/592273615 and cl/592273683.)
451     */
452    @SuppressWarnings("unchecked")
453    public Builder(Comparator<? super E> comparator) {
454      this.comparator = checkNotNull(comparator);
455    }
456
457    /**
458     * Adds {@code element} to the {@code ImmutableSortedSet}. If the {@code ImmutableSortedSet}
459     * already contains {@code element}, then {@code add} has no effect. (only the previously added
460     * element is retained).
461     *
462     * @param element the element to add
463     * @return this {@code Builder} object
464     * @throws NullPointerException if {@code element} is null
465     */
466    @CanIgnoreReturnValue
467    @Override
468    public Builder<E> add(E element) {
469      super.add(element);
470      return this;
471    }
472
473    /**
474     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
475     * elements (only the first duplicate element is added).
476     *
477     * @param elements the elements to add
478     * @return this {@code Builder} object
479     * @throws NullPointerException if {@code elements} contains a null element
480     */
481    @CanIgnoreReturnValue
482    @Override
483    public Builder<E> add(E... elements) {
484      super.add(elements);
485      return this;
486    }
487
488    /**
489     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
490     * elements (only the first duplicate element is added).
491     *
492     * @param elements the elements to add to the {@code ImmutableSortedSet}
493     * @return this {@code Builder} object
494     * @throws NullPointerException if {@code elements} contains a null element
495     */
496    @CanIgnoreReturnValue
497    @Override
498    public Builder<E> addAll(Iterable<? extends E> elements) {
499      super.addAll(elements);
500      return this;
501    }
502
503    /**
504     * Adds each element of {@code elements} to the {@code ImmutableSortedSet}, ignoring duplicate
505     * elements (only the first duplicate element is added).
506     *
507     * @param elements the elements to add to the {@code ImmutableSortedSet}
508     * @return this {@code Builder} object
509     * @throws NullPointerException if {@code elements} contains a null element
510     */
511    @CanIgnoreReturnValue
512    @Override
513    public Builder<E> addAll(Iterator<? extends E> elements) {
514      super.addAll(elements);
515      return this;
516    }
517
518    @CanIgnoreReturnValue
519    @Override
520    Builder<E> combine(ImmutableSet.Builder<E> builder) {
521      super.combine(builder);
522      return this;
523    }
524
525    /**
526     * Returns a newly-created {@code ImmutableSortedSet} based on the contents of the {@code
527     * Builder} and its comparator.
528     */
529    @Override
530    public ImmutableSortedSet<E> build() {
531      @SuppressWarnings("unchecked") // we're careful to put only E's in here
532      E[] contentsArray = (E[]) contents;
533      ImmutableSortedSet<E> result = construct(comparator, size, contentsArray);
534      this.size = result.size(); // we eliminated duplicates in-place in contentsArray
535      this.forceCopy = true;
536      return result;
537    }
538  }
539
540  int unsafeCompare(Object a, @CheckForNull Object b) {
541    return unsafeCompare(comparator, a, b);
542  }
543
544  static int unsafeCompare(Comparator<?> comparator, Object a, @CheckForNull Object b) {
545    // Pretend the comparator can compare anything. If it turns out it can't
546    // compare a and b, we should get a CCE or NPE on the subsequent line. Only methods
547    // that are spec'd to throw CCE and NPE should call this.
548    @SuppressWarnings({"unchecked", "nullness"})
549    Comparator<@Nullable Object> unsafeComparator = (Comparator<@Nullable Object>) comparator;
550    return unsafeComparator.compare(a, b);
551  }
552
553  final transient Comparator<? super E> comparator;
554
555  ImmutableSortedSet(Comparator<? super E> comparator) {
556    this.comparator = comparator;
557  }
558
559  /**
560   * Returns the comparator that orders the elements, which is {@link Ordering#natural()} when the
561   * natural ordering of the elements is used. Note that its behavior is not consistent with {@link
562   * SortedSet#comparator()}, which returns {@code null} to indicate natural ordering.
563   */
564  @Override
565  public Comparator<? super E> comparator() {
566    return comparator;
567  }
568
569  @Override // needed to unify the iterator() methods in Collection and SortedIterable
570  public abstract UnmodifiableIterator<E> iterator();
571
572  /**
573   * {@inheritDoc}
574   *
575   * <p>This method returns a serializable {@code ImmutableSortedSet}.
576   *
577   * <p>The {@link SortedSet#headSet} documentation states that a subset of a subset throws an
578   * {@link IllegalArgumentException} if passed a {@code toElement} greater than an earlier {@code
579   * toElement}. However, this method doesn't throw an exception in that situation, but instead
580   * keeps the original {@code toElement}.
581   */
582  @Override
583  public ImmutableSortedSet<E> headSet(E toElement) {
584    return headSet(toElement, false);
585  }
586
587  /** @since 12.0 */
588  @Override
589  public ImmutableSortedSet<E> headSet(E toElement, boolean inclusive) {
590    return headSetImpl(checkNotNull(toElement), inclusive);
591  }
592
593  /**
594   * {@inheritDoc}
595   *
596   * <p>This method returns a serializable {@code ImmutableSortedSet}.
597   *
598   * <p>The {@link SortedSet#subSet} documentation states that a subset of a subset throws an {@link
599   * IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
600   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
601   * keeps the original {@code fromElement}. Similarly, this method keeps the original {@code
602   * toElement}, instead of throwing an exception, if passed a {@code toElement} greater than an
603   * earlier {@code toElement}.
604   */
605  @Override
606  public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
607    return subSet(fromElement, true, toElement, false);
608  }
609
610  /** @since 12.0 */
611  @GwtIncompatible // NavigableSet
612  @Override
613  public ImmutableSortedSet<E> subSet(
614      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
615    checkNotNull(fromElement);
616    checkNotNull(toElement);
617    checkArgument(comparator.compare(fromElement, toElement) <= 0);
618    return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
619  }
620
621  /**
622   * {@inheritDoc}
623   *
624   * <p>This method returns a serializable {@code ImmutableSortedSet}.
625   *
626   * <p>The {@link SortedSet#tailSet} documentation states that a subset of a subset throws an
627   * {@link IllegalArgumentException} if passed a {@code fromElement} smaller than an earlier {@code
628   * fromElement}. However, this method doesn't throw an exception in that situation, but instead
629   * keeps the original {@code fromElement}.
630   */
631  @Override
632  public ImmutableSortedSet<E> tailSet(E fromElement) {
633    return tailSet(fromElement, true);
634  }
635
636  /** @since 12.0 */
637  @Override
638  public ImmutableSortedSet<E> tailSet(E fromElement, boolean inclusive) {
639    return tailSetImpl(checkNotNull(fromElement), inclusive);
640  }
641
642  /*
643   * These methods perform most headSet, subSet, and tailSet logic, besides
644   * parameter validation.
645   */
646  abstract ImmutableSortedSet<E> headSetImpl(E toElement, boolean inclusive);
647
648  abstract ImmutableSortedSet<E> subSetImpl(
649      E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
650
651  abstract ImmutableSortedSet<E> tailSetImpl(E fromElement, boolean inclusive);
652
653  /** @since 12.0 */
654  @GwtIncompatible // NavigableSet
655  @Override
656  @CheckForNull
657  public E lower(E e) {
658    return Iterators.<@Nullable E>getNext(headSet(e, false).descendingIterator(), null);
659  }
660
661  /** @since 12.0 */
662  @Override
663  @CheckForNull
664  public E floor(E e) {
665    return Iterators.<@Nullable E>getNext(headSet(e, true).descendingIterator(), null);
666  }
667
668  /** @since 12.0 */
669  @Override
670  @CheckForNull
671  public E ceiling(E e) {
672    return Iterables.<@Nullable E>getFirst(tailSet(e, true), null);
673  }
674
675  /** @since 12.0 */
676  @GwtIncompatible // NavigableSet
677  @Override
678  @CheckForNull
679  public E higher(E e) {
680    return Iterables.<@Nullable E>getFirst(tailSet(e, false), null);
681  }
682
683  @Override
684  public E first() {
685    return iterator().next();
686  }
687
688  @Override
689  public E last() {
690    return descendingIterator().next();
691  }
692
693  /**
694   * Guaranteed to throw an exception and leave the set unmodified.
695   *
696   * @since 12.0
697   * @throws UnsupportedOperationException always
698   * @deprecated Unsupported operation.
699   */
700  @CanIgnoreReturnValue
701  @Deprecated
702  @GwtIncompatible // NavigableSet
703  @Override
704  @DoNotCall("Always throws UnsupportedOperationException")
705  @CheckForNull
706  public final E pollFirst() {
707    throw new UnsupportedOperationException();
708  }
709
710  /**
711   * Guaranteed to throw an exception and leave the set unmodified.
712   *
713   * @since 12.0
714   * @throws UnsupportedOperationException always
715   * @deprecated Unsupported operation.
716   */
717  @CanIgnoreReturnValue
718  @Deprecated
719  @GwtIncompatible // NavigableSet
720  @Override
721  @DoNotCall("Always throws UnsupportedOperationException")
722  @CheckForNull
723  public final E pollLast() {
724    throw new UnsupportedOperationException();
725  }
726
727  @GwtIncompatible // NavigableSet
728  @LazyInit
729  @CheckForNull
730  transient ImmutableSortedSet<E> descendingSet;
731
732  /** @since 12.0 */
733  @GwtIncompatible // NavigableSet
734  @Override
735  public ImmutableSortedSet<E> descendingSet() {
736    // racy single-check idiom
737    ImmutableSortedSet<E> result = descendingSet;
738    if (result == null) {
739      result = descendingSet = createDescendingSet();
740      result.descendingSet = this;
741    }
742    return result;
743  }
744
745  // Most classes should implement this as new DescendingImmutableSortedSet<E>(this),
746  // but we push down that implementation because ProGuard can't eliminate it even when it's always
747  // overridden.
748  @GwtIncompatible // NavigableSet
749  abstract ImmutableSortedSet<E> createDescendingSet();
750
751  /** @since 12.0 */
752  @GwtIncompatible // NavigableSet
753  @Override
754  public abstract UnmodifiableIterator<E> descendingIterator();
755
756  /** Returns the position of an element within the set, or -1 if not present. */
757  abstract int indexOf(@CheckForNull Object target);
758
759  /*
760   * This class is used to serialize all ImmutableSortedSet instances,
761   * regardless of implementation type. It captures their "logical contents"
762   * only. This is necessary to ensure that the existence of a particular
763   * implementation type is an implementation detail.
764   */
765  @J2ktIncompatible // serialization
766  private static class SerializedForm<E> implements Serializable {
767    final Comparator<? super E> comparator;
768    final Object[] elements;
769
770    public SerializedForm(Comparator<? super E> comparator, Object[] elements) {
771      this.comparator = comparator;
772      this.elements = elements;
773    }
774
775    @SuppressWarnings("unchecked")
776    Object readResolve() {
777      return new Builder<E>(comparator).add((E[]) elements).build();
778    }
779
780    private static final long serialVersionUID = 0;
781  }
782
783  @J2ktIncompatible // serialization
784  private void readObject(ObjectInputStream unused) throws InvalidObjectException {
785    throw new InvalidObjectException("Use SerializedForm");
786  }
787
788  @Override
789  @J2ktIncompatible // serialization
790  Object writeReplace() {
791    return new SerializedForm<E>(comparator, toArray());
792  }
793
794  /**
795   * Not supported. Use {@link #toImmutableSortedSet} instead. This method exists only to hide
796   * {@link ImmutableSet#toImmutableSet} from consumers of {@code ImmutableSortedSet}.
797   *
798   * @throws UnsupportedOperationException always
799   * @deprecated Use {@link ImmutableSortedSet#toImmutableSortedSet}.
800   * @since 33.2.0 (available since 21.0 in guava-jre)
801   */
802  @DoNotCall("Use toImmutableSortedSet")
803  @Deprecated
804  @SuppressWarnings({"AndroidJdkLibsChecker", "Java7ApiChecker"})
805  @IgnoreJRERequirement // Users will use this only if they're already using streams.
806  @Beta // TODO: b/288085449 - Remove.
807  public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
808    throw new UnsupportedOperationException();
809  }
810
811  /**
812   * Not supported. Use {@link #naturalOrder}, which offers better type-safety, instead. This method
813   * exists only to hide {@link ImmutableSet#builder} from consumers of {@code ImmutableSortedSet}.
814   *
815   * @throws UnsupportedOperationException always
816   * @deprecated Use {@link ImmutableSortedSet#naturalOrder}, which offers better type-safety.
817   */
818  @DoNotCall("Use naturalOrder")
819  @Deprecated
820  public static <E> ImmutableSortedSet.Builder<E> builder() {
821    throw new UnsupportedOperationException();
822  }
823
824  /**
825   * Not supported. This method exists only to hide {@link ImmutableSet#builderWithExpectedSize}
826   * from consumers of {@code ImmutableSortedSet}.
827   *
828   * @throws UnsupportedOperationException always
829   * @deprecated Not supported by ImmutableSortedSet.
830   */
831  @DoNotCall("Use naturalOrder (which does not accept an expected size)")
832  @Deprecated
833  public static <E> ImmutableSortedSet.Builder<E> builderWithExpectedSize(int expectedSize) {
834    throw new UnsupportedOperationException();
835  }
836
837  /**
838   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
839   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
840   * dummy version.
841   *
842   * @throws UnsupportedOperationException always
843   * @deprecated <b>Pass a parameter of type {@code Comparable} to use {@link
844   *     ImmutableSortedSet#of(Comparable)}.</b>
845   */
846  @DoNotCall("Pass a parameter of type Comparable")
847  @Deprecated
848  public static <E> ImmutableSortedSet<E> of(E element) {
849    throw new UnsupportedOperationException();
850  }
851
852  /**
853   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
854   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
855   * dummy version.
856   *
857   * @throws UnsupportedOperationException always
858   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
859   *     ImmutableSortedSet#of(Comparable, Comparable)}.</b>
860   */
861  @DoNotCall("Pass parameters of type Comparable")
862  @Deprecated
863  public static <E> ImmutableSortedSet<E> of(E e1, E e2) {
864    throw new UnsupportedOperationException();
865  }
866
867  /**
868   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
869   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
870   * dummy version.
871   *
872   * @throws UnsupportedOperationException always
873   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
874   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable)}.</b>
875   */
876  @DoNotCall("Pass parameters of type Comparable")
877  @Deprecated
878  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3) {
879    throw new UnsupportedOperationException();
880  }
881
882  /**
883   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
884   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
885   * dummy version.
886   *
887   * @throws UnsupportedOperationException always
888   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
889   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable)}. </b>
890   */
891  @DoNotCall("Pass parameters of type Comparable")
892  @Deprecated
893  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4) {
894    throw new UnsupportedOperationException();
895  }
896
897  /**
898   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
899   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
900   * dummy version.
901   *
902   * @throws UnsupportedOperationException always
903   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
904   *     ImmutableSortedSet#of( Comparable, Comparable, Comparable, Comparable, Comparable)}. </b>
905   */
906  @DoNotCall("Pass parameters of type Comparable")
907  @Deprecated
908  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5) {
909    throw new UnsupportedOperationException();
910  }
911
912  /**
913   * Not supported. <b>You are attempting to create a set that may contain a non-{@code Comparable}
914   * element.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
915   * dummy version.
916   *
917   * @throws UnsupportedOperationException always
918   * @deprecated <b>Pass the parameters of type {@code Comparable} to use {@link
919   *     ImmutableSortedSet#of(Comparable, Comparable, Comparable, Comparable, Comparable,
920   *     Comparable, Comparable...)}. </b>
921   */
922  @DoNotCall("Pass parameters of type Comparable")
923  @Deprecated
924  public static <E> ImmutableSortedSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
925    throw new UnsupportedOperationException();
926  }
927
928  /**
929   * Not supported. <b>You are attempting to create a set that may contain non-{@code Comparable}
930   * elements.</b> Proper calls will resolve to the version in {@code ImmutableSortedSet}, not this
931   * dummy version.
932   *
933   * @throws UnsupportedOperationException always
934   * @deprecated <b>Pass parameters of type {@code Comparable} to use {@link
935   *     ImmutableSortedSet#copyOf(Comparable[])}.</b>
936   */
937  @DoNotCall("Pass parameters of type Comparable")
938  @Deprecated
939  // The usage of "Z" here works around bugs in Javadoc (JDK-8318093) and JDiff.
940  public static <Z> ImmutableSortedSet<Z> copyOf(Z[] elements) {
941    throw new UnsupportedOperationException();
942  }
943
944  private static final long serialVersionUID = 0xdecaf;
945}