1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /*

    26  * This file is available under and governed by the GNU General Public

    27  * License version 2 only, as published by the Free Software Foundation.

    28  * However, the following notice accompanied the original version of this

    29  * file:

    30  *

    31  * Written by Doug Lea and Josh Bloch with assistance from members of JCP

    32  * JSR-166 Expert Group and released to the public domain, as explained at

    33  * http://creativecommons.org/publicdomain/zero/1.0/

    34  */

    35 

    36 package java.util;

    37 

    38 /**

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

    40  * closest matches for given search targets. Methods {@link #lower},

    41  * {@link #floor}, {@link #ceiling}, and {@link #higher} return elements

    42  * respectively less than, less than or equal, greater than or equal,

    43  * and greater than a given element, returning {@code null} if there

    44  * is no such element.

    45  *

    46  * <p>A {@code NavigableSet} may be accessed and traversed in either

    47  * ascending or descending order.  The {@link #descendingSet} method

    48  * returns a view of the set with the senses of all relational and

    49  * directional methods inverted. The performance of ascending

    50  * operations and views is likely to be faster than that of descending

    51  * ones.  This interface additionally defines methods {@link

    52  * #pollFirst} and {@link #pollLast} that return and remove the lowest

    53  * and highest element, if one exists, else returning {@code null}.

    54  * Methods

    55  * {@link #subSet(Object, boolean, Object, boolean) subSet(E, boolean, E, boolean)},

    56  * {@link #headSet(Object, boolean) headSet(E, boolean)}, and

    57  * {@link #tailSet(Object, boolean) tailSet(E, boolean)}

    58  * differ from the like-named {@code SortedSet} methods in accepting

    59  * additional arguments describing whether lower and upper bounds are

    60  * inclusive versus exclusive.  Subsets of any {@code NavigableSet}

    61  * must implement the {@code NavigableSet} interface.

    62  *

    63  * <p>The return values of navigation methods may be ambiguous in

    64  * implementations that permit {@code null} elements. However, even

    65  * in this case the result can be disambiguated by checking

    66  * {@code contains(null)}. To avoid such issues, implementations of

    67  * this interface are encouraged to <em>not</em> permit insertion of

    68  * {@code null} elements. (Note that sorted sets of {@link

    69  * Comparable} elements intrinsically do not permit {@code null}.)

    70  *

    71  * <p>Methods

    72  * {@link #subSet(Object, Object) subSet(E, E)},

    73  * {@link #headSet(Object) headSet(E)}, and

    74  * {@link #tailSet(Object) tailSet(E)}

    75  * are specified to return {@code SortedSet} to allow existing

    76  * implementations of {@code SortedSet} to be compatibly retrofitted to

    77  * implement {@code NavigableSet}, but extensions and implementations

    78  * of this interface are encouraged to override these methods to return

    79  * {@code NavigableSet}.

    80  *

    81  * <p>This interface is a member of the

    82  * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">

    83  * Java Collections Framework</a>.

    84  *

    85  * @author Doug Lea

    86  * @author Josh Bloch

    87  * @param <E> the type of elements maintained by this set

    88  * @since 1.6

    89  */

    90 public interface NavigableSet<E> extends SortedSet<E> {

    91     /**

    92      * Returns the greatest element in this set strictly less than the

    93      * given element, or {@code null} if there is no such element.

    94      *

    95      * @param e the value to match

    96      * @return the greatest element less than {@code e},

    97      *         or {@code null} if there is no such element

    98      * @throws ClassCastException if the specified element cannot be

    99      *         compared with the elements currently in the set

   100      * @throws NullPointerException if the specified element is null

   101      *         and this set does not permit null elements

   102      */

   103     E lower(E e);

   104 

   105     /**

   106      * Returns the greatest element in this set less than or equal to

   107      * the given element, or {@code null} if there is no such element.

   108      *

   109      * @param e the value to match

   110      * @return the greatest element less than or equal to {@code e},

   111      *         or {@code null} if there is no such element

   112      * @throws ClassCastException if the specified element cannot be

   113      *         compared with the elements currently in the set

   114      * @throws NullPointerException if the specified element is null

   115      *         and this set does not permit null elements

   116      */

   117     E floor(E e);

   118 

   119     /**

   120      * Returns the least element in this set greater than or equal to

   121      * the given element, or {@code null} if there is no such element.

   122      *

   123      * @param e the value to match

   124      * @return the least element greater than or equal to {@code e},

   125      *         or {@code null} if there is no such element

   126      * @throws ClassCastException if the specified element cannot be

   127      *         compared with the elements currently in the set

   128      * @throws NullPointerException if the specified element is null

   129      *         and this set does not permit null elements

   130      */

   131     E ceiling(E e);

   132 

   133     /**

   134      * Returns the least element in this set strictly greater than the

   135      * given element, or {@code null} if there is no such element.

   136      *

   137      * @param e the value to match

   138      * @return the least element greater than {@code e},

   139      *         or {@code null} if there is no such element

   140      * @throws ClassCastException if the specified element cannot be

   141      *         compared with the elements currently in the set

   142      * @throws NullPointerException if the specified element is null

   143      *         and this set does not permit null elements

   144      */

   145     E higher(E e);

   146 

   147     /**

   148      * Retrieves and removes the first (lowest) element,

   149      * or returns {@code null} if this set is empty.

   150      *

   151      * @return the first element, or {@code null} if this set is empty

   152      */

   153     E pollFirst();

   154 

   155     /**

   156      * Retrieves and removes the last (highest) element,

   157      * or returns {@code null} if this set is empty.

   158      *

   159      * @return the last element, or {@code null} if this set is empty

   160      */

   161     E pollLast();

   162 

   163     /**

   164      * Returns an iterator over the elements in this set, in ascending order.

   165      *

   166      * @return an iterator over the elements in this set, in ascending order

   167      */

   168     Iterator<E> iterator();

   169 

   170     /**

   171      * Returns a reverse order view of the elements contained in this set.

   172      * The descending set is backed by this set, so changes to the set are

   173      * reflected in the descending set, and vice-versa.  If either set is

   174      * modified while an iteration over either set is in progress (except

   175      * through the iterator's own {@code remove} operation), the results of

   176      * the iteration are undefined.

   177      *

   178      * <p>The returned set has an ordering equivalent to

   179      * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.

   180      * The expression {@code s.descendingSet().descendingSet()} returns a

   181      * view of {@code s} essentially equivalent to {@code s}.

   182      *

   183      * @return a reverse order view of this set

   184      */

   185     NavigableSet<E> descendingSet();

   186 

   187     /**

   188      * Returns an iterator over the elements in this set, in descending order.

   189      * Equivalent in effect to {@code descendingSet().iterator()}.

   190      *

   191      * @return an iterator over the elements in this set, in descending order

   192      */

   193     Iterator<E> descendingIterator();

   194 

   195     /**

   196      * Returns a view of the portion of this set whose elements range from

   197      * {@code fromElement} to {@code toElement}.  If {@code fromElement} and

   198      * {@code toElement} are equal, the returned set is empty unless {@code

   199      * fromInclusive} and {@code toInclusive} are both true.  The returned set

   200      * is backed by this set, so changes in the returned set are reflected in

   201      * this set, and vice-versa.  The returned set supports all optional set

   202      * operations that this set supports.

   203      *

   204      * <p>The returned set will throw an {@code IllegalArgumentException}

   205      * on an attempt to insert an element outside its range.

   206      *

   207      * @param fromElement low endpoint of the returned set

   208      * @param fromInclusive {@code true} if the low endpoint

   209      *        is to be included in the returned view

   210      * @param toElement high endpoint of the returned set

   211      * @param toInclusive {@code true} if the high endpoint

   212      *        is to be included in the returned view

   213      * @return a view of the portion of this set whose elements range from

   214      *         {@code fromElement}, inclusive, to {@code toElement}, exclusive

   215      * @throws ClassCastException if {@code fromElement} and

   216      *         {@code toElement} cannot be compared to one another using this

   217      *         set's comparator (or, if the set has no comparator, using

   218      *         natural ordering).  Implementations may, but are not required

   219      *         to, throw this exception if {@code fromElement} or

   220      *         {@code toElement} cannot be compared to elements currently in

   221      *         the set.

   222      * @throws NullPointerException if {@code fromElement} or

   223      *         {@code toElement} is null and this set does

   224      *         not permit null elements

   225      * @throws IllegalArgumentException if {@code fromElement} is

   226      *         greater than {@code toElement}; or if this set itself

   227      *         has a restricted range, and {@code fromElement} or

   228      *         {@code toElement} lies outside the bounds of the range.

   229      */

   230     NavigableSet<E> subSet(E fromElement, boolean fromInclusive,

   231                            E toElement,   boolean toInclusive);

   232 

   233     /**

   234      * Returns a view of the portion of this set whose elements are less than

   235      * (or equal to, if {@code inclusive} is true) {@code toElement}.  The

   236      * returned set is backed by this set, so changes in the returned set are

   237      * reflected in this set, and vice-versa.  The returned set supports all

   238      * optional set operations that this set supports.

   239      *

   240      * <p>The returned set will throw an {@code IllegalArgumentException}

   241      * on an attempt to insert an element outside its range.

   242      *

   243      * @param toElement high endpoint of the returned set

   244      * @param inclusive {@code true} if the high endpoint

   245      *        is to be included in the returned view

   246      * @return a view of the portion of this set whose elements are less than

   247      *         (or equal to, if {@code inclusive} is true) {@code toElement}

   248      * @throws ClassCastException if {@code toElement} is not compatible

   249      *         with this set's comparator (or, if the set has no comparator,

   250      *         if {@code toElement} does not implement {@link Comparable}).

   251      *         Implementations may, but are not required to, throw this

   252      *         exception if {@code toElement} cannot be compared to elements

   253      *         currently in the set.

   254      * @throws NullPointerException if {@code toElement} is null and

   255      *         this set does not permit null elements

   256      * @throws IllegalArgumentException if this set itself has a

   257      *         restricted range, and {@code toElement} lies outside the

   258      *         bounds of the range

   259      */

   260     NavigableSet<E> headSet(E toElement, boolean inclusive);

   261 

   262     /**

   263      * Returns a view of the portion of this set whose elements are greater

   264      * than (or equal to, if {@code inclusive} is true) {@code fromElement}.

   265      * The returned set is backed by this set, so changes in the returned set

   266      * are reflected in this set, and vice-versa.  The returned set supports

   267      * all optional set operations that this set supports.

   268      *

   269      * <p>The returned set will throw an {@code IllegalArgumentException}

   270      * on an attempt to insert an element outside its range.

   271      *

   272      * @param fromElement low endpoint of the returned set

   273      * @param inclusive {@code true} if the low endpoint

   274      *        is to be included in the returned view

   275      * @return a view of the portion of this set whose elements are greater

   276      *         than or equal to {@code fromElement}

   277      * @throws ClassCastException if {@code fromElement} is not compatible

   278      *         with this set's comparator (or, if the set has no comparator,

   279      *         if {@code fromElement} does not implement {@link Comparable}).

   280      *         Implementations may, but are not required to, throw this

   281      *         exception if {@code fromElement} cannot be compared to elements

   282      *         currently in the set.

   283      * @throws NullPointerException if {@code fromElement} is null

   284      *         and this set does not permit null elements

   285      * @throws IllegalArgumentException if this set itself has a

   286      *         restricted range, and {@code fromElement} lies outside the

   287      *         bounds of the range

   288      */

   289     NavigableSet<E> tailSet(E fromElement, boolean inclusive);

   290 

   291     /**

   292      * {@inheritDoc}

   293      *

   294      * <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}.

   295      *

   296      * @throws ClassCastException       {@inheritDoc}

   297      * @throws NullPointerException     {@inheritDoc}

   298      * @throws IllegalArgumentException {@inheritDoc}

   299      */

   300     SortedSet<E> subSet(E fromElement, E toElement);

   301 

   302     /**

   303      * {@inheritDoc}

   304      *

   305      * <p>Equivalent to {@code headSet(toElement, false)}.

   306      *

   307      * @throws ClassCastException       {@inheritDoc}

   308      * @throws NullPointerException     {@inheritDoc}

   309      * @throws IllegalArgumentException {@inheritDoc}

   310      */

   311     SortedSet<E> headSet(E toElement);

   312 

   313     /**

   314      * {@inheritDoc}

   315      *

   316      * <p>Equivalent to {@code tailSet(fromElement, true)}.

   317      *

   318      * @throws ClassCastException       {@inheritDoc}

   319      * @throws NullPointerException     {@inheritDoc}

   320      * @throws IllegalArgumentException {@inheritDoc}

   321      */

   322     SortedSet<E> tailSet(E fromElement);

   323 }