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