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