lib/classpath/external/jsr166/java/util/NavigableSet.java

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