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