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