Source for java.util.NavigableSet

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