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.  Sun designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  21  * CA 95054 USA or visit www.sun.com if you need additional information or
  22  * have any 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/licenses/publicdomain
  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 {@code lower},
  41  * {@code floor}, {@code ceiling}, and {@code 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.  A {@code NavigableSet} may be accessed and
  45  * traversed in either ascending or descending order.  The {@code
  46  * descendingSet} method returns a view of the set with the senses of
  47  * all relational and directional methods inverted. The performance of
  48  * ascending operations and views is likely to be faster than that of
  49  * descending ones.  This interface additionally defines methods
  50  * {@code pollFirst} and {@code pollLast} that return and remove the
  51  * lowest and highest element, if one exists, else returning {@code
  52  * null}.  Methods {@code subSet}, {@code headSet},
  53  * and {@code tailSet} differ from the like-named {@code
  54  * SortedSet} methods in accepting additional arguments describing
  55  * whether lower and upper bounds are inclusive versus exclusive.
  56  * Subsets of any {@code NavigableSet} must implement the {@code
  57  * NavigableSet} interface.
  58  *
  59  * <p> The return values of navigation methods may be ambiguous in
  60  * implementations that permit {@code null} elements. However, even
  61  * in this case the result can be disambiguated by checking
  62  * {@code contains(null)}. To avoid such issues, implementations of
  63  * this interface are encouraged to <em>not</em> permit insertion of
  64  * {@code null} elements. (Note that sorted sets of {@link
  65  * Comparable} elements intrinsically do not permit {@code null}.)
  66  *
  67  * <p>Methods
  68  * {@link #subSet(Object, Object) subSet(E, E)},
  69  * {@link #headSet(Object) headSet(E)}, and
  70  * {@link #tailSet(Object) tailSet(E)}
  71  * are specified to return {@code SortedSet} to allow existing
  72  * implementations of {@code SortedSet} to be compatibly retrofitted to
  73  * implement {@code NavigableSet}, but extensions and implementations
  74  * of this interface are encouraged to override these methods to return
  75  * {@code NavigableSet}.
  76  *
  77  * <p>This interface is a member of the
  78  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  79  * Java Collections Framework</a>.
  80  *
  81  * @author Doug Lea
  82  * @author Josh Bloch
  83  * @param <E> the type of elements maintained by this set
  84  * @since 1.6
  85  */
  86 public interface NavigableSet<E> extends SortedSet<E> {
  87     /**
  88      * Returns the greatest element in this set strictly less than the
  89      * given element, or {@code null} if there is no such element.
  90      *
  91      * @param e the value to match
  92      * @return the greatest element less than {@code e},
  93      *         or {@code null} if there is no such element
  94      * @throws ClassCastException if the specified element cannot be
  95      *         compared with the elements currently in the set
  96      * @throws NullPointerException if the specified element is null
  97      *         and this set does not permit null elements
  98      */
  99     E lower(E e);
 100 
 101     /**
 102      * Returns the greatest element in this set less than or equal to
 103      * the given element, or {@code null} if there is no such element.
 104      *
 105      * @param e the value to match
 106      * @return the greatest element less than or equal to {@code e},
 107      *         or {@code null} if there is no such element
 108      * @throws ClassCastException if the specified element cannot be
 109      *         compared with the elements currently in the set
 110      * @throws NullPointerException if the specified element is null
 111      *         and this set does not permit null elements
 112      */
 113     E floor(E e);
 114 
 115     /**
 116      * Returns the least element in this set greater than or equal to
 117      * the given element, or {@code null} if there is no such element.
 118      *
 119      * @param e the value to match
 120      * @return the least element greater than or equal to {@code e},
 121      *         or {@code null} if there is no such element
 122      * @throws ClassCastException if the specified element cannot be
 123      *         compared with the elements currently in the set
 124      * @throws NullPointerException if the specified element is null
 125      *         and this set does not permit null elements
 126      */
 127     E ceiling(E e);
 128 
 129     /**
 130      * Returns the least element in this set strictly greater than the
 131      * given element, or {@code null} if there is no such element.
 132      *
 133      * @param e the value to match
 134      * @return the least element greater than {@code e},
 135      *         or {@code null} if there is no such element
 136      * @throws ClassCastException if the specified element cannot be
 137      *         compared with the elements currently in the set
 138      * @throws NullPointerException if the specified element is null
 139      *         and this set does not permit null elements
 140      */
 141     E higher(E e);
 142 
 143     /**
 144      * Retrieves and removes the first (lowest) element,
 145      * or returns {@code null} if this set is empty.
 146      *
 147      * @return the first element, or {@code null} if this set is empty
 148      */
 149     E pollFirst();
 150 
 151     /**
 152      * Retrieves and removes the last (highest) element,
 153      * or returns {@code null} if this set is empty.
 154      *
 155      * @return the last element, or {@code null} if this set is empty
 156      */
 157     E pollLast();
 158 
 159     /**
 160      * Returns an iterator over the elements in this set, in ascending order.
 161      *
 162      * @return an iterator over the elements in this set, in ascending order
 163      */
 164     Iterator<E> iterator();
 165 
 166     /**
 167      * Returns a reverse order view of the elements contained in this set.
 168      * The descending set is backed by this set, so changes to the set are
 169      * reflected in the descending set, and vice-versa.  If either set is
 170      * modified while an iteration over either set is in progress (except
 171      * through the iterator's own {@code remove} operation), the results of
 172      * the iteration are undefined.
 173      *
 174      * <p>The returned set has an ordering equivalent to
 175      * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
 176      * The expression {@code s.descendingSet().descendingSet()} returns a
 177      * view of {@code s} essentially equivalent to {@code s}.
 178      *
 179      * @return a reverse order view of this set
 180      */
 181     NavigableSet<E> descendingSet();
 182 
 183     /**
 184      * Returns an iterator over the elements in this set, in descending order.
 185      * Equivalent in effect to {@code descendingSet().iterator()}.
 186      *
 187      * @return an iterator over the elements in this set, in descending order
 188      */
 189     Iterator<E> descendingIterator();
 190 
 191     /**
 192      * Returns a view of the portion of this set whose elements range from
 193      * {@code fromElement} to {@code toElement}.  If {@code fromElement} and
 194      * {@code toElement} are equal, the returned set is empty unless {@code
 195      * fromExclusive} and {@code toExclusive} are both true.  The returned set
 196      * is backed by this set, so changes in the returned set are reflected in
 197      * this set, and vice-versa.  The returned set supports all optional set
 198      * operations that this set supports.
 199      *
 200      * <p>The returned set will throw an {@code IllegalArgumentException}
 201      * on an attempt to insert an element outside its range.
 202      *
 203      * @param fromElement low endpoint of the returned set
 204      * @param fromInclusive {@code true} if the low endpoint
 205      *        is to be included in the returned view
 206      * @param toElement high endpoint of the returned set
 207      * @param toInclusive {@code true} if the high endpoint
 208      *        is to be included in the returned view
 209      * @return a view of the portion of this set whose elements range from
 210      *         {@code fromElement}, inclusive, to {@code toElement}, exclusive
 211      * @throws ClassCastException if {@code fromElement} and
 212      *         {@code toElement} cannot be compared to one another using this
 213      *         set's comparator (or, if the set has no comparator, using
 214      *         natural ordering).  Implementations may, but are not required
 215      *         to, throw this exception if {@code fromElement} or
 216      *         {@code toElement} cannot be compared to elements currently in
 217      *         the set.
 218      * @throws NullPointerException if {@code fromElement} or
 219      *         {@code toElement} is null and this set does
 220      *         not permit null elements
 221      * @throws IllegalArgumentException if {@code fromElement} is
 222      *         greater than {@code toElement}; or if this set itself
 223      *         has a restricted range, and {@code fromElement} or
 224      *         {@code toElement} lies outside the bounds of the range.
 225      */
 226     NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
 227                            E toElement,   boolean toInclusive);
 228 
 229     /**
 230      * Returns a view of the portion of this set whose elements are less than
 231      * (or equal to, if {@code inclusive} is true) {@code toElement}.  The
 232      * returned set is backed by this set, so changes in the returned set are
 233      * reflected in this set, and vice-versa.  The returned set supports all
 234      * optional set operations that this set supports.
 235      *
 236      * <p>The returned set will throw an {@code IllegalArgumentException}
 237      * on an attempt to insert an element outside its range.
 238      *
 239      * @param toElement high endpoint of the returned set
 240      * @param inclusive {@code true} if the high endpoint
 241      *        is to be included in the returned view
 242      * @return a view of the portion of this set whose elements are less than
 243      *         (or equal to, if {@code inclusive} is true) {@code toElement}
 244      * @throws ClassCastException if {@code toElement} is not compatible
 245      *         with this set's comparator (or, if the set has no comparator,
 246      *         if {@code toElement} does not implement {@link Comparable}).
 247      *         Implementations may, but are not required to, throw this
 248      *         exception if {@code toElement} cannot be compared to elements
 249      *         currently in the set.
 250      * @throws NullPointerException if {@code toElement} is null and
 251      *         this set does not permit null elements
 252      * @throws IllegalArgumentException if this set itself has a
 253      *         restricted range, and {@code toElement} lies outside the
 254      *         bounds of the range
 255      */
 256     NavigableSet<E> headSet(E toElement, boolean inclusive);
 257 
 258     /**
 259      * Returns a view of the portion of this set whose elements are greater
 260      * than (or equal to, if {@code inclusive} is true) {@code fromElement}.
 261      * The returned set is backed by this set, so changes in the returned set
 262      * are reflected in this set, and vice-versa.  The returned set supports
 263      * all optional set operations that this set supports.
 264      *
 265      * <p>The returned set will throw an {@code IllegalArgumentException}
 266      * on an attempt to insert an element outside its range.
 267      *
 268      * @param fromElement low endpoint of the returned set
 269      * @param inclusive {@code true} if the low endpoint
 270      *        is to be included in the returned view
 271      * @return a view of the portion of this set whose elements are greater
 272      *         than or equal to {@code fromElement}
 273      * @throws ClassCastException if {@code fromElement} is not compatible
 274      *         with this set's comparator (or, if the set has no comparator,
 275      *         if {@code fromElement} does not implement {@link Comparable}).
 276      *         Implementations may, but are not required to, throw this
 277      *         exception if {@code fromElement} cannot be compared to elements
 278      *         currently in the set.
 279      * @throws NullPointerException if {@code fromElement} is null
 280      *         and this set does not permit null elements
 281      * @throws IllegalArgumentException if this set itself has a
 282      *         restricted range, and {@code fromElement} lies outside the
 283      *         bounds of the range
 284      */
 285     NavigableSet<E> tailSet(E fromElement, boolean inclusive);
 286 
 287     /**
 288      * {@inheritDoc}
 289      *
 290      * <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}.
 291      *
 292      * @throws ClassCastException       {@inheritDoc}
 293      * @throws NullPointerException     {@inheritDoc}
 294      * @throws IllegalArgumentException {@inheritDoc}
 295      */
 296     SortedSet<E> subSet(E fromElement, E toElement);
 297 
 298     /**
 299      * {@inheritDoc}
 300      *
 301      * <p>Equivalent to {@code headSet(toElement, false)}.
 302      *
 303      * @throws ClassCastException       {@inheritDoc}
 304      * @throws NullPointerException     {@inheritDoc}
 305      * @throws IllegalArgumentException {@inheritDoc}
 306 na     */
 307     SortedSet<E> headSet(E toElement);
 308 
 309     /**
 310      * {@inheritDoc}
 311      *
 312      * <p>Equivalent to {@code tailSet(fromElement, true)}.
 313      *
 314      * @throws ClassCastException       {@inheritDoc}
 315      * @throws NullPointerException     {@inheritDoc}
 316      * @throws IllegalArgumentException {@inheritDoc}
 317      */
 318     SortedSet<E> tailSet(E fromElement);
 319 }