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/publicdomain/zero/1.0/ 5 */ 6 7package java.util; 8 9// BEGIN android-note 10// removed link to collections framework docs 11// END android-note 12 13/** 14 * A {@link SortedSet} extended with navigation methods reporting 15 * closest matches for given search targets. Methods {@code lower}, 16 * {@code floor}, {@code ceiling}, and {@code higher} return elements 17 * respectively less than, less than or equal, greater than or equal, 18 * and greater than a given element, returning {@code null} if there 19 * is no such element. A {@code NavigableSet} may be accessed and 20 * traversed in either ascending or descending order. The {@code 21 * descendingSet} method returns a view of the set with the senses of 22 * all relational and directional methods inverted. The performance of 23 * ascending operations and views is likely to be faster than that of 24 * descending ones. This interface additionally defines methods 25 * {@code pollFirst} and {@code pollLast} that return and remove the 26 * lowest and highest element, if one exists, else returning {@code 27 * null}. Methods {@code subSet}, {@code headSet}, 28 * and {@code tailSet} differ from the like-named {@code 29 * SortedSet} methods in accepting additional arguments describing 30 * whether lower and upper bounds are inclusive versus exclusive. 31 * Subsets of any {@code NavigableSet} must implement the {@code 32 * NavigableSet} interface. 33 * 34 * <p> The return values of navigation methods may be ambiguous in 35 * implementations that permit {@code null} elements. However, even 36 * in this case the result can be disambiguated by checking 37 * {@code contains(null)}. To avoid such issues, implementations of 38 * this interface are encouraged to <em>not</em> permit insertion of 39 * {@code null} elements. (Note that sorted sets of {@link 40 * Comparable} elements intrinsically do not permit {@code null}.) 41 * 42 * <p>Methods 43 * {@link #subSet(Object, Object) subSet(E, E)}, 44 * {@link #headSet(Object) headSet(E)}, and 45 * {@link #tailSet(Object) tailSet(E)} 46 * are specified to return {@code SortedSet} to allow existing 47 * implementations of {@code SortedSet} to be compatibly retrofitted to 48 * implement {@code NavigableSet}, but extensions and implementations 49 * of this interface are encouraged to override these methods to return 50 * {@code NavigableSet}. 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 */ 57public 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} 277na */ 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} 291