Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2008 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.collect.ObjectArrays.checkElementsNotNull;
 
 
 
 import  javax.annotation.Nullable;

An immutable SortedSet that stores its elements in a sorted array. Some instances are ordered by an explicit comparator, while others follow the natural sort ordering of their elements. Either way, null elements are not supported.

Unlike Collections.unmodifiableSortedSet, which is a view of a separate collection that can still change, an instance of ImmutableSortedSet contains its own private data and will never change. This class is convenient for public static final sets ("constant sets") and also lets you easily make a "defensive copy" of a set provided to your class by a caller.

The sets returned by the headSet, tailSet, and subSet methods share the same array as the original set, preventing that array from being garbage collected. If this is a concern, the data may be copied into a correctly-sized array by calling copyOfSorted.

Note on element equivalence: The contains(Object), containsAll(Collection), and equals(Object) implementations must check whether a provided object is equivalent to an element in the collection. Unlike most collections, an ImmutableSortedSet doesn't use Object.equals to determine if two elements are equivalent. Instead, with an explicit comparator, the following relation determines whether elements x and y are equivalent:

   {(x, y) | comparator.compare(x, y) == 0}

With natural ordering of elements, the following relation determines whether two elements are equivalent:

   {(x, y) | x.compareTo(y) == 0}
Warning: Like most sets, an ImmutableSortedSet will not function correctly if an element is modified after being placed in the set. For this reason, and to avoid general confusion, it is strongly recommended to place only immutable objects into this collection.

Note: Although this class is not final, it cannot be subclassed as it has no public or protected constructors. Thus, instances of this type are guaranteed to be immutable.

See the Guava User Guide article on immutable collections.

Author(s):
Jared Levy
Louis Wasserman
Since:
2.0 (imported from Google Collections Library; implements NavigableSet since 12.0)
See also:
ImmutableSet
 
 // TODO(benyu): benchmark and optimize all creation paths, which are a mess now
 @GwtCompatible(serializable = true, emulated = true)
 @SuppressWarnings("serial"// we're overriding default serialization
 public abstract class ImmutableSortedSet<E> extends ImmutableSortedSetFauxverideShim<E>
     implements NavigableSet<E>, SortedIterable<E> {
 
   private static final Comparator<ComparableNATURAL_ORDER =
       Ordering.natural();
 
  private static final ImmutableSortedSet<ComparableNATURAL_EMPTY_SET =
  @SuppressWarnings("unchecked")
  private static <E> ImmutableSortedSet<E> emptySet() {
  }
  static <E> ImmutableSortedSet<E> emptySet(
      Comparator<? super E> comparator) {
    if (.equals(comparator)) {
      return emptySet();
    } else {
      return new EmptyImmutableSortedSet<E>(comparator);
    }
  }

  
Returns the empty immutable sorted set.
  public static <E> ImmutableSortedSet<E> of() {
    return emptySet();
  }

  
Returns an immutable sorted set containing a single element.
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
      E element) {
    return new RegularImmutableSortedSet<E>(
        ImmutableList.of(element), Ordering.natural());
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to Comparable.compareTo, only the first one specified is included.

Throws:
NullPointerException if any element is null
  @SuppressWarnings("unchecked")
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
      E e1, E e2) {
    return construct(Ordering.natural(), 2, e1e2);
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to Comparable.compareTo, only the first one specified is included.

Throws:
NullPointerException if any element is null
  @SuppressWarnings("unchecked")
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
      E e1, E e2, E e3) {
    return construct(Ordering.natural(), 3, e1e2e3);
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to Comparable.compareTo, only the first one specified is included.

Throws:
NullPointerException if any element is null
  @SuppressWarnings("unchecked")
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
      E e1, E e2, E e3, E e4) {
    return construct(Ordering.natural(), 4, e1e2e3e4);
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to Comparable.compareTo, only the first one specified is included.

Throws:
NullPointerException if any element is null
  @SuppressWarnings("unchecked")
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
      E e1, E e2, E e3, E e4, E e5) {
    return construct(Ordering.natural(), 5, e1e2e3e4e5);
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to Comparable.compareTo, only the first one specified is included.

Throws:
NullPointerException if any element is null
Since:
3.0 (source-compatible since 2.0)
  @SuppressWarnings("unchecked")
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> of(
      E e1, E e2, E e3, E e4, E e5, E e6, E... remaining) {
    Comparable[] contents = new Comparable[6 + remaining.length];
    contents[0] = e1;
    contents[1] = e2;
    contents[2] = e3;
    contents[3] = e4;
    contents[4] = e5;
    contents[5] = e6;
    System.arraycopy(remaining, 0, contents, 6, remaining.length);
    return construct(Ordering.natural(), contents.length, (E[]) contents);
  }
  // TODO(kevinb): Consider factory methods that reject duplicates

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to Comparable.compareTo, only the first one specified is included.

Throws:
NullPointerException if any of elements is null
Since:
3.0
  public static <E extends Comparable<? super E>> ImmutableSortedSet<E> copyOf(
      E[] elements) {
    return construct(Ordering.natural(), elements.lengthelements.clone());
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to compareTo(), only the first one specified is included. To create a copy of a SortedSet that preserves the comparator, call copyOfSorted instead. This method iterates over elements at most once.

Note that if s is a Set<String>, then ImmutableSortedSet.copyOf(s) returns an ImmutableSortedSet<String> containing each of the strings in s, while ImmutableSortedSet.of(s) returns an ImmutableSortedSet<Set<String>> containing one element (the given set itself).

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

This method is not type-safe, as it may be called on elements that are not mutually comparable.

Throws:
ClassCastException if the elements are not mutually comparable
NullPointerException if any of elements is null
  public static <E> ImmutableSortedSet<E> copyOf(
      Iterable<? extends E> elements) {
    // Hack around E not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
    return copyOf(naturalOrderelements);
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to compareTo(), only the first one specified is included. To create a copy of a SortedSet that preserves the comparator, call copyOfSorted instead. This method iterates over elements at most once.

Note that if s is a Set<String>, then ImmutableSortedSet.copyOf(s) returns an ImmutableSortedSet<String> containing each of the strings in s, while ImmutableSortedSet.of(s) returns an ImmutableSortedSet<Set<String>> containing one element (the given set itself).

Note: Despite what the method name suggests, if elements is an ImmutableSortedSet, it may be returned instead of a copy.

This method is not type-safe, as it may be called on elements that are not mutually comparable.

This method is safe to use even when elements is a synchronized or concurrent collection that is currently being modified by another thread.

Throws:
ClassCastException if the elements are not mutually comparable
NullPointerException if any of elements is null
Since:
7.0 (source-compatible since 2.0)
  public static <E> ImmutableSortedSet<E> copyOf(
      Collection<? extends E> elements) {
    // Hack around E not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
    return copyOf(naturalOrderelements);
  }

  
Returns an immutable sorted set containing the given elements sorted by their natural ordering. When multiple elements are equivalent according to compareTo(), only the first one specified is included.

This method is not type-safe, as it may be called on elements that are not mutually comparable.

Throws:
ClassCastException if the elements are not mutually comparable
NullPointerException if any of elements is null
  public static <E> ImmutableSortedSet<E> copyOf(
      Iterator<? extends E> elements) {
    // Hack around E not being a subtype of Comparable.
    // Unsafe, see ImmutableSortedSetFauxverideShim.
    @SuppressWarnings("unchecked")
    Ordering<E> naturalOrder = (Ordering<E>) Ordering.<Comparable>natural();
    return copyOf(naturalOrderelements);
  }

  
Returns an immutable sorted set containing the given elements sorted by the given Comparator. When multiple elements are equivalent according to compareTo(), only the first one specified is included.

Throws:
NullPointerException if comparator or any of elements is null
  public static <E> ImmutableSortedSet<E> copyOf(
      Comparator<? super E> comparatorIterator<? extends E> elements) {
    return new Builder<E>(comparator).addAll(elements).build();
  }

  
Returns an immutable sorted set containing the given elements sorted by the given Comparator. When multiple elements are equivalent according to compare(), only the first one specified is included. This method iterates over elements at most once.

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

Throws:
NullPointerException if comparator or any of elements is null
  public static <E> ImmutableSortedSet<E> copyOf(
      Comparator<? super E> comparatorIterable<? extends E> elements) {
    checkNotNull(comparator);
    boolean hasSameComparator =
        SortedIterables.hasSameComparator(comparatorelements);
    if (hasSameComparator && (elements instanceof ImmutableSortedSet)) {
      @SuppressWarnings("unchecked")
      ImmutableSortedSet<E> original = (ImmutableSortedSet<E>) elements;
      if (!original.isPartialView()) {
        return original;
      }
    }
    @SuppressWarnings("unchecked"// elements only contains E's; it's safe.
    E[] array = (E[]) Iterables.toArray(elements);
    return construct(comparatorarray.lengtharray);
  }

  
Returns an immutable sorted set containing the given elements sorted by the given Comparator. When multiple elements are equivalent according to compareTo(), only the first one specified is included.

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

This method is safe to use even when elements is a synchronized or concurrent collection that is currently being modified by another thread.

Throws:
NullPointerException if comparator or any of elements is null
Since:
7.0 (source-compatible since 2.0)
  public static <E> ImmutableSortedSet<E> copyOf(
      Comparator<? super E> comparatorCollection<? extends E> elements) {
    return copyOf(comparator, (Iterable<? extends E>) elements);
  }

  
Returns an immutable sorted set containing the elements of a sorted set, sorted by the same Comparator. That behavior differs from copyOf(Iterable), which always uses the natural ordering of the elements.

Despite the method name, this method attempts to avoid actually copying the data when it is safe to do so. The exact circumstances under which a copy will or will not be performed are undocumented and subject to change.

This method is safe to use even when sortedSet is a synchronized or concurrent collection that is currently being modified by another thread.

Throws:
NullPointerException if sortedSet or any of its elements is null
  public static <E> ImmutableSortedSet<E> copyOfSorted(SortedSet<E> sortedSet) {
    Comparator<? super E> comparator = SortedIterables.comparator(sortedSet);
    ImmutableList<E> list = ImmutableList.copyOf(sortedSet);
    if (list.isEmpty()) {
      return emptySet(comparator);
    } else {
      return new RegularImmutableSortedSet<E>(listcomparator);
    }
  }

  
Constructs an ImmutableSortedSet from the first n elements of contents. If k is the size of the returned ImmutableSortedSet, then the sorted unique elements are in the first k positions of contents, and contents[i] == null for k <= i < n.

If k == contents.length, then contents may no longer be safe for modification.

Throws:
NullPointerException if any of the first n elements of contents is null
  static <E> ImmutableSortedSet<E> construct(
      Comparator<? super E> comparatorint n, E... contents) {
    if (n == 0) {
      return emptySet(comparator);
    }
    checkElementsNotNull(contentsn);
    Arrays.sort(contents, 0, ncomparator);
    int uniques = 1;
    for (int i = 1; i < ni++) {
      E cur = contents[i];
      E prev = contents[uniques - 1];
      if (comparator.compare(curprev) != 0) {
        contents[uniques++] = cur;
      }
    }
    Arrays.fill(contentsuniquesnnull);
    return new RegularImmutableSortedSet<E>(
        ImmutableList.<E>asImmutableList(contentsuniques), comparator);
  }

  
Returns a builder that creates immutable sorted sets with an explicit comparator. If the comparator has a more general type than the set being generated, such as creating a SortedSet<Integer> with a Comparator<Number>, use the Builder constructor instead.

Throws:
NullPointerException if comparator is null
  public static <E> Builder<E> orderedBy(Comparator<E> comparator) {
    return new Builder<E>(comparator);
  }

  
Returns a builder that creates immutable sorted sets whose elements are ordered by the reverse of their natural ordering.
  public static <E extends Comparable<?>> Builder<E> reverseOrder() {
    return new Builder<E>(Ordering.natural().reverse());
  }

  
Returns a builder that creates immutable sorted sets whose elements are ordered by their natural ordering. The sorted sets use Ordering.natural() as the comparator. This method provides more type-safety than builder, as it can be called only for classes that implement Comparable.
  public static <E extends Comparable<?>> Builder<E> naturalOrder() {
    return new Builder<E>(Ordering.natural());
  }

  
A builder for creating immutable sorted set instances, especially public static final sets ("constant sets"), with a given comparator. Example:
   public static final ImmutableSortedSet<Number> LUCKY_NUMBERS =
       new ImmutableSortedSet.Builder<Number>(ODDS_FIRST_COMPARATOR)
           .addAll(SINGLE_DIGIT_PRIMES)
           .add(42)
           .build();

Builder instances can be reused; it is safe to call build multiple times to build multiple sets in series. Each set is a superset of the set created before it.

Since:
2.0 (imported from Google Collections Library)
  public static final class Builder<E> extends ImmutableSet.Builder<E> {
    private final Comparator<? super E> comparator;

    
Creates a new builder. The returned builder is equivalent to the builder generated by ImmutableSortedSet.orderedBy.
    public Builder(Comparator<? super E> comparator) {
      this. = checkNotNull(comparator);
    }

    
Adds element to the ImmutableSortedSet. If the ImmutableSortedSet already contains element, then add has no effect. (only the previously added element is retained).

Parameters:
element the element to add
Returns:
this Builder object
Throws:
NullPointerException if element is null
    @Override public Builder<E> add(E element) {
      super.add(element);
      return this;
    }

    
Adds each element of elements to the ImmutableSortedSet, ignoring duplicate elements (only the first duplicate element is added).

Parameters:
elements the elements to add
Returns:
this Builder object
Throws:
NullPointerException if elements contains a null element
    @Override public Builder<E> add(E... elements) {
      super.add(elements);
      return this;
    }

    
Adds each element of elements to the ImmutableSortedSet, ignoring duplicate elements (only the first duplicate element is added).

Parameters:
elements the elements to add to the ImmutableSortedSet
Returns:
this Builder object
Throws:
NullPointerException if elements contains a null element
    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
      super.addAll(elements);
      return this;
    }

    
Adds each element of elements to the ImmutableSortedSet, ignoring duplicate elements (only the first duplicate element is added).

Parameters:
elements the elements to add to the ImmutableSortedSet
Returns:
this Builder object
Throws:
NullPointerException if elements contains a null element
    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
      super.addAll(elements);
      return this;
    }

    
Returns a newly-created ImmutableSortedSet based on the contents of the Builder and its comparator.
    @Override public ImmutableSortedSet<E> build() {
      @SuppressWarnings("unchecked"// we're careful to put only E's in here
      E[] contentsArray = (E[]) ;
      ImmutableSortedSet<E> result = construct(contentsArray);
      this. = result.size(); // we eliminated duplicates in-place in contentsArray
      return result;
    }
  }
  int unsafeCompare(Object aObject b) {
    return unsafeCompare(ab);
  }
  static int unsafeCompare(
      Comparator<?> comparatorObject aObject b) {
    // Pretend the comparator can compare anything. If it turns out it can't
    // compare a and b, we should get a CCE on the subsequent line. Only methods
    // that are spec'd to throw CCE should call this.
    @SuppressWarnings("unchecked")
    Comparator<ObjectunsafeComparator = (Comparator<Object>) comparator;
    return unsafeComparator.compare(ab);
  }
  final transient Comparator<? super E> comparator;
  ImmutableSortedSet(Comparator<? super E> comparator) {
    this. = comparator;
  }

  
Returns the comparator that orders the elements, which is Ordering.natural() when the natural ordering of the elements is used. Note that its behavior is not consistent with SortedSet.comparator(), which returns null to indicate natural ordering.
  public Comparator<? super E> comparator() {
    return ;
  }
  @Override // needed to unify the iterator() methods in Collection and SortedIterable
  public abstract UnmodifiableIterator<E> iterator();

  

This method returns a serializable ImmutableSortedSet.

The SortedSet.headSet documentation states that a subset of a subset throws an IllegalArgumentException if passed a toElement greater than an earlier toElement. However, this method doesn't throw an exception in that situation, but instead keeps the original toElement.

  public ImmutableSortedSet<E> headSet(E toElement) {
    return headSet(toElementfalse);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public ImmutableSortedSet<E> headSet(E toElementboolean inclusive) {
    return headSetImpl(checkNotNull(toElement), inclusive);
  }

  

This method returns a serializable ImmutableSortedSet.

The SortedSet.subSet documentation states that a subset of a subset throws an IllegalArgumentException if passed a fromElement smaller than an earlier fromElement. However, this method doesn't throw an exception in that situation, but instead keeps the original fromElement. Similarly, this method keeps the original toElement, instead of throwing an exception, if passed a toElement greater than an earlier toElement.

  public ImmutableSortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElementtruetoElementfalse);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public ImmutableSortedSet<E> subSet(
      E fromElementboolean fromInclusive, E toElementboolean toInclusive) {
    checkNotNull(fromElement);
    checkNotNull(toElement);
    checkArgument(.compare(fromElementtoElement) <= 0);
    return subSetImpl(fromElementfromInclusivetoElementtoInclusive);
  }

  

This method returns a serializable ImmutableSortedSet.

The SortedSet.tailSet documentation states that a subset of a subset throws an IllegalArgumentException if passed a fromElement smaller than an earlier fromElement. However, this method doesn't throw an exception in that situation, but instead keeps the original fromElement.

  public ImmutableSortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElementtrue);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public ImmutableSortedSet<E> tailSet(E fromElementboolean inclusive) {
    return tailSetImpl(checkNotNull(fromElement), inclusive);
  }
  /*
   * These methods perform most headSet, subSet, and tailSet logic, besides
   * parameter validation.
   */
  abstract ImmutableSortedSet<E> headSetImpl(E toElementboolean inclusive);
      E fromElementboolean fromInclusive, E toElementboolean toInclusive);
  abstract ImmutableSortedSet<E> tailSetImpl(E fromElementboolean inclusive);
  
  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public E lower(E e) {
    return Iterators.getNext(headSet(efalse).descendingIterator(), null);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public E floor(E e) {
    return Iterators.getNext(headSet(etrue).descendingIterator(), null);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public E ceiling(E e) {
    return Iterables.getFirst(tailSet(etrue), null);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public E higher(E e) {
    return Iterables.getFirst(tailSet(efalse), null);
  }
  public E first() {
    return iterator().next();
  }
  public E last() {
    return descendingIterator().next();
  }

  
Guaranteed to throw an exception and leave the set unmodified.

Deprecated:
Unsupported operation.
Throws:
UnsupportedOperationException always
Since:
12.0
  @GwtIncompatible("NavigableSet")
  public final E pollFirst() {
    throw new UnsupportedOperationException();
  }

  
Guaranteed to throw an exception and leave the set unmodified.

Deprecated:
Unsupported operation.
Throws:
UnsupportedOperationException always
Since:
12.0
  @GwtIncompatible("NavigableSet")
  public final E pollLast() {
    throw new UnsupportedOperationException();
  }
  @GwtIncompatible("NavigableSet")
  transient ImmutableSortedSet<E> descendingSet;

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
    // racy single-check idiom
    ImmutableSortedSet<E> result = ;
    if (result == null) {
      result =  = createDescendingSet();
      result.descendingSet = this;
    }
    return result;
  }
  @GwtIncompatible("NavigableSet")
    return new DescendingImmutableSortedSet<E>(this);
  }

  

Since:
12.0
  @GwtIncompatible("NavigableSet")
  public abstract UnmodifiableIterator<E> descendingIterator();

  
Returns the position of an element within the set, or -1 if not present.
  abstract int indexOf(@Nullable Object target);
  /*
   * This class is used to serialize all ImmutableSortedSet instances,
   * regardless of implementation type. It captures their "logical contents"
   * only. This is necessary to ensure that the existence of a particular
   * implementation type is an implementation detail.
   */
  private static class SerializedForm<E> implements Serializable {
    final Comparator<? super E> comparator;
    final Object[] elements;
    public SerializedForm(Comparator<? super E> comparatorObject[] elements) {
      this. = comparator;
      this. = elements;
    }
    @SuppressWarnings("unchecked")
    Object readResolve() {
      return new Builder<E>().add((E[]) ).build();
    }
    private static final long serialVersionUID = 0;
  }
  private void readObject(ObjectInputStream stream)
      throws InvalidObjectException {
    throw new InvalidObjectException("Use SerializedForm");
  }
    return new SerializedForm<E>(toArray());
  }
New to GrepCode? Check out our FAQ X