/*

  * 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/

  */

 package java.util;

 /**

  * A {@link SortedSet} extended with navigation methods reporting

  * closest matches for given search targets. Methods {@code lower},

  * {@code floor}, {@code ceiling}, and {@code 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.  A {@code NavigableSet} may be accessed and

  * traversed in either ascending or descending order.  The {@code

  * 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

  * {@code pollFirst} and {@code pollLast} that return and remove the

  * lowest and highest element, if one exists, else returning {@code

  * null}.  Methods {@code subSet}, {@code headSet},

  * and {@code tailSet} 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}.

  *

  * <p>This interface is a member of the

  * <a href="{@docRoot}/../technotes/guides/collections/index.html">

  * Java Collections Framework</a>.

  *

  * @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

      * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.

      * 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}

 na     */

     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);

 }