content: /*
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  /*
   * This file is available under and governed by the GNU General Public
   * License version 2 only, as published by the Free Software Foundation.
   * However, the following notice accompanied the original version of this
   * file:
   *
   * Written by Doug Lea and Josh Bloch with assistance from members of JCP
   * JSR-166 Expert Group and released to the public domain, as explained at
   * http://creativecommons.org/publicdomain/zero/1.0/
   */
  
  // BEGIN android-note
  // removed link to collections framework docs
  // END android-note
  
  package java.util;
  
  /**
   * A {@link SortedSet} extended with navigation methods reporting
   * closest matches for given search targets. Methods {@link #lower},
   * {@link #floor}, {@link #ceiling}, and {@link #higher} return elements
   * respectively less than, less than or equal, greater than or equal,
   * and greater than a given element, returning {@code null} if there
   * is no such element.
   *
   * <p>A {@code NavigableSet} may be accessed and traversed in either
   * ascending or descending order.  The {@link #descendingSet} method
   * returns a view of the set with the senses of all relational and
   * directional methods inverted. The performance of ascending
   * operations and views is likely to be faster than that of descending
   * ones.  This interface additionally defines methods {@link
   * #pollFirst} and {@link #pollLast} that return and remove the lowest
   * and highest element, if one exists, else returning {@code null}.
   * Methods
   * {@link #subSet(Object, boolean, Object, boolean) subSet(E, boolean, E, boolean)},
   * {@link #headSet(Object, boolean) headSet(E, boolean)}, and
   * {@link #tailSet(Object, boolean) tailSet(E, boolean)}
   * differ from the like-named {@code SortedSet} methods in accepting
   * additional arguments describing whether lower and upper bounds are
   * inclusive versus exclusive.  Subsets of any {@code NavigableSet}
   * must implement the {@code NavigableSet} interface.
   *
   * <p>The return values of navigation methods may be ambiguous in
   * implementations that permit {@code null} elements. However, even
   * in this case the result can be disambiguated by checking
   * {@code contains(null)}. To avoid such issues, implementations of
   * this interface are encouraged to <em>not</em> permit insertion of
   * {@code null} elements. (Note that sorted sets of {@link
   * Comparable} elements intrinsically do not permit {@code null}.)
   *
   * <p>Methods
   * {@link #subSet(Object, Object) subSet(E, E)},
   * {@link #headSet(Object) headSet(E)}, and
   * {@link #tailSet(Object) tailSet(E)}
   * are specified to return {@code SortedSet} to allow existing
   * implementations of {@code SortedSet} to be compatibly retrofitted to
   * implement {@code NavigableSet}, but extensions and implementations
   * of this interface are encouraged to override these methods to return
   * {@code NavigableSet}.
   *
   * @author Doug Lea
   * @author Josh Bloch
   * @param <E> the type of elements maintained by this set
   * @since 1.6
   */
  public interface NavigableSet<E> extends SortedSet<E> {
      /**
       * Returns the greatest element in this set strictly less than the
       * given element, or {@code null} if there is no such element.
       *
       * @param e the value to match
       * @return the greatest element less than {@code e},
       *         or {@code null} if there is no such element
       * @throws ClassCastException if the specified element cannot be
       *         compared with the elements currently in the set
       * @throws NullPointerException if the specified element is null
       *         and this set does not permit null elements
       */
      E lower(E e);
  
      /**
       * Returns the greatest element in this set less than or equal to
       * the given element, or {@code null} if there is no such element.
       *
       * @param e the value to match
       * @return the greatest element less than or equal to {@code e},
       *         or {@code null} if there is no such element
       * @throws ClassCastException if the specified element cannot be
       *         compared with the elements currently in the set
       * @throws NullPointerException if the specified element is null
       *         and this set does not permit null elements
       */
      E floor(E e);
  
      /**
       * Returns the least element in this set greater than or equal to
       * the given element, or {@code null} if there is no such element.
       *
       * @param e the value to match
       * @return the least element greater than or equal to {@code e},
       *         or {@code null} if there is no such element
       * @throws ClassCastException if the specified element cannot be
       *         compared with the elements currently in the set
       * @throws NullPointerException if the specified element is null
       *         and this set does not permit null elements
       */
      E ceiling(E e);
  
      /**
       * Returns the least element in this set strictly greater than the
       * given element, or {@code null} if there is no such element.
       *
       * @param e the value to match
       * @return the least element greater than {@code e},
       *         or {@code null} if there is no such element
       * @throws ClassCastException if the specified element cannot be
       *         compared with the elements currently in the set
       * @throws NullPointerException if the specified element is null
       *         and this set does not permit null elements
       */
      E higher(E e);
  
      /**
       * Retrieves and removes the first (lowest) element,
       * or returns {@code null} if this set is empty.
       *
       * @return the first element, or {@code null} if this set is empty
       */
      E pollFirst();
  
      /**
       * Retrieves and removes the last (highest) element,
       * or returns {@code null} if this set is empty.
       *
       * @return the last element, or {@code null} if this set is empty
       */
      E pollLast();
  
      /**
       * Returns an iterator over the elements in this set, in ascending order.
       *
       * @return an iterator over the elements in this set, in ascending order
       */
      Iterator<E> iterator();
  
      /**
       * Returns a reverse order view of the elements contained in this set.
       * The descending set is backed by this set, so changes to the set are
       * reflected in the descending set, and vice-versa.  If either set is
       * modified while an iteration over either set is in progress (except
       * through the iterator's own {@code remove} operation), the results of
       * the iteration are undefined.
       *
       * <p>The returned set has an ordering equivalent to
       * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
       * The expression {@code s.descendingSet().descendingSet()} returns a
       * view of {@code s} essentially equivalent to {@code s}.
       *
       * @return a reverse order view of this set
       */
      NavigableSet<E> descendingSet();
  
      /**
       * Returns an iterator over the elements in this set, in descending order.
       * Equivalent in effect to {@code descendingSet().iterator()}.
       *
       * @return an iterator over the elements in this set, in descending order
       */
      Iterator<E> descendingIterator();
  
      /**
       * Returns a view of the portion of this set whose elements range from
       * {@code fromElement} to {@code toElement}.  If {@code fromElement} and
       * {@code toElement} are equal, the returned set is empty unless {@code
       * fromInclusive} and {@code toInclusive} are both true.  The returned set
       * is backed by this set, so changes in the returned set are reflected in
       * this set, and vice-versa.  The returned set supports all optional set
       * operations that this set supports.
       *
       * <p>The returned set will throw an {@code IllegalArgumentException}
       * on an attempt to insert an element outside its range.
       *
       * @param fromElement low endpoint of the returned set
       * @param fromInclusive {@code true} if the low endpoint
       *        is to be included in the returned view
       * @param toElement high endpoint of the returned set
       * @param toInclusive {@code true} if the high endpoint
       *        is to be included in the returned view
       * @return a view of the portion of this set whose elements range from
       *         {@code fromElement}, inclusive, to {@code toElement}, exclusive
       * @throws ClassCastException if {@code fromElement} and
       *         {@code toElement} cannot be compared to one another using this
       *         set's comparator (or, if the set has no comparator, using
       *         natural ordering).  Implementations may, but are not required
       *         to, throw this exception if {@code fromElement} or
       *         {@code toElement} cannot be compared to elements currently in
       *         the set.
       * @throws NullPointerException if {@code fromElement} or
       *         {@code toElement} is null and this set does
       *         not permit null elements
       * @throws IllegalArgumentException if {@code fromElement} is
       *         greater than {@code toElement}; or if this set itself
       *         has a restricted range, and {@code fromElement} or
       *         {@code toElement} lies outside the bounds of the range.
       */
      NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                             E toElement,   boolean toInclusive);
  
      /**
       * Returns a view of the portion of this set whose elements are less than
       * (or equal to, if {@code inclusive} is true) {@code toElement}.  The
       * returned set is backed by this set, so changes in the returned set are
       * reflected in this set, and vice-versa.  The returned set supports all
       * optional set operations that this set supports.
       *
       * <p>The returned set will throw an {@code IllegalArgumentException}
       * on an attempt to insert an element outside its range.
       *
       * @param toElement high endpoint of the returned set
       * @param inclusive {@code true} if the high endpoint
       *        is to be included in the returned view
       * @return a view of the portion of this set whose elements are less than
       *         (or equal to, if {@code inclusive} is true) {@code toElement}
       * @throws ClassCastException if {@code toElement} is not compatible
       *         with this set's comparator (or, if the set has no comparator,
       *         if {@code toElement} does not implement {@link Comparable}).
       *         Implementations may, but are not required to, throw this
       *         exception if {@code toElement} cannot be compared to elements
       *         currently in the set.
       * @throws NullPointerException if {@code toElement} is null and
       *         this set does not permit null elements
       * @throws IllegalArgumentException if this set itself has a
       *         restricted range, and {@code toElement} lies outside the
       *         bounds of the range
       */
      NavigableSet<E> headSet(E toElement, boolean inclusive);
  
      /**
       * Returns a view of the portion of this set whose elements are greater
       * than (or equal to, if {@code inclusive} is true) {@code fromElement}.
       * The returned set is backed by this set, so changes in the returned set
       * are reflected in this set, and vice-versa.  The returned set supports
       * all optional set operations that this set supports.
       *
       * <p>The returned set will throw an {@code IllegalArgumentException}
       * on an attempt to insert an element outside its range.
       *
       * @param fromElement low endpoint of the returned set
       * @param inclusive {@code true} if the low endpoint
       *        is to be included in the returned view
       * @return a view of the portion of this set whose elements are greater
       *         than or equal to {@code fromElement}
       * @throws ClassCastException if {@code fromElement} is not compatible
       *         with this set's comparator (or, if the set has no comparator,
       *         if {@code fromElement} does not implement {@link Comparable}).
       *         Implementations may, but are not required to, throw this
       *         exception if {@code fromElement} cannot be compared to elements
       *         currently in the set.
       * @throws NullPointerException if {@code fromElement} is null
       *         and this set does not permit null elements
       * @throws IllegalArgumentException if this set itself has a
       *         restricted range, and {@code fromElement} lies outside the
       *         bounds of the range
       */
      NavigableSet<E> tailSet(E fromElement, boolean inclusive);
  
      /**
       * {@inheritDoc}
       *
       * <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}.
       *
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException     {@inheritDoc}
       * @throws IllegalArgumentException {@inheritDoc}
       */
      SortedSet<E> subSet(E fromElement, E toElement);
  
      /**
       * {@inheritDoc}
       *
       * <p>Equivalent to {@code headSet(toElement, false)}.
       *
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException     {@inheritDoc}
       * @throws IllegalArgumentException {@inheritDoc}
       */
      SortedSet<E> headSet(E toElement);
  
      /**
       * {@inheritDoc}
       *
       * <p>Equivalent to {@code tailSet(fromElement, true)}.
       *
       * @throws ClassCastException       {@inheritDoc}
       * @throws NullPointerException     {@inheritDoc}
       * @throws IllegalArgumentException {@inheritDoc}
       */
      SortedSet<E> tailSet(E fromElement);
  }
  