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 {@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 */ lower(E e)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 */ floor(E e)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 */ ceiling(E e)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 */ higher(E e)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 */ pollFirst()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 */ pollLast()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 */ iterator()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 */ descendingSet()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 */ descendingIterator()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 * fromInclusive} and {@code toInclusive} 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 */ subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)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 */ headSet(E toElement, boolean inclusive)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 */ tailSet(E fromElement, boolean inclusive)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 */ subSet(E fromElement, E toElement)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 */ headSet(E toElement)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 */ tailSet(E fromElement)318 SortedSet<E> tailSet(E fromElement); 319 } 320