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