Repository navigation
Expand file tree
/
Copy pathNavigableSet.java
More file actions
383 lines (363 loc) · 16.3 KB
/
Copy pathNavigableSet.java
File metadata and controls
383 lines (363 loc) · 16.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
/*
* This file is available under and governed by the GNU General Public
* License version 2 only, as published by the Free Software Foundation.
* However, the following notice accompanied the original version of this
* file:
*
* Written by Doug Lea and Josh Bloch with assistance from members of JCP
* JSR-166 Expert Group and released to the public domain, as explained at
* http://creativecommons.org/publicdomain/zero/1.0/
*/
package java.util;
/**
* A {@link SortedSet} extended with navigation methods reporting
* closest matches for given search targets. Methods {@link #lower},
* {@link #floor}, {@link #ceiling}, and {@link #higher} return elements
* respectively less than, less than or equal, greater than or equal,
* and greater than a given element, returning {@code null} if there
* is no such element.
*
* <p>A {@code NavigableSet} may be accessed and traversed in either
* ascending or descending order. The {@link #descendingSet} method
* returns a view of the set with the senses of all relational and
* directional methods inverted. The performance of ascending
* operations and views is likely to be faster than that of descending
* ones. This interface additionally defines methods {@link
* #pollFirst} and {@link #pollLast} that return and remove the lowest
* and highest element, if one exists, else returning {@code null}.
* Methods
* {@link #subSet(Object, boolean, Object, boolean) subSet(E, boolean, E, boolean)},
* {@link #headSet(Object, boolean) headSet(E, boolean)}, and
* {@link #tailSet(Object, boolean) tailSet(E, boolean)}
* differ from the like-named {@code SortedSet} methods in accepting
* additional arguments describing whether lower and upper bounds are
* inclusive versus exclusive. Subsets of any {@code NavigableSet}
* must implement the {@code NavigableSet} interface.
*
* <p>The return values of navigation methods may be ambiguous in
* implementations that permit {@code null} elements. However, even
* in this case the result can be disambiguated by checking
* {@code contains(null)}. To avoid such issues, implementations of
* this interface are encouraged to <em>not</em> permit insertion of
* {@code null} elements. (Note that sorted sets of {@link
* Comparable} elements intrinsically do not permit {@code null}.)
*
* <p>Methods
* {@link #subSet(Object, Object) subSet(E, E)},
* {@link #headSet(Object) headSet(E)}, and
* {@link #tailSet(Object) tailSet(E)}
* are specified to return {@code SortedSet} to allow existing
* implementations of {@code SortedSet} to be compatibly retrofitted to
* implement {@code NavigableSet}, but extensions and implementations
* of this interface are encouraged to override these methods to return
* {@code NavigableSet}.
*
* <p>This interface is a member of the
* <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
* Java Collections Framework</a>.
*
* @author Doug Lea
* @author Josh Bloch
* @param <E> the type of elements maintained by this set
* @since 1.6
*/
public interface NavigableSet<E> extends SortedSet<E> {
/**
* Returns the greatest element in this set strictly less than the
* given element, or {@code null} if there is no such element.
*
* @param e the value to match
* @return the greatest element less than {@code e},
* or {@code null} if there is no such element
* @throws ClassCastException if the specified element cannot be
* compared with the elements currently in the set
* @throws NullPointerException if the specified element is null
* and this set does not permit null elements
*/
E lower(E e);
/**
* Returns the greatest element in this set less than or equal to
* the given element, or {@code null} if there is no such element.
*
* @param e the value to match
* @return the greatest element less than or equal to {@code e},
* or {@code null} if there is no such element
* @throws ClassCastException if the specified element cannot be
* compared with the elements currently in the set
* @throws NullPointerException if the specified element is null
* and this set does not permit null elements
*/
E floor(E e);
/**
* Returns the least element in this set greater than or equal to
* the given element, or {@code null} if there is no such element.
*
* @param e the value to match
* @return the least element greater than or equal to {@code e},
* or {@code null} if there is no such element
* @throws ClassCastException if the specified element cannot be
* compared with the elements currently in the set
* @throws NullPointerException if the specified element is null
* and this set does not permit null elements
*/
E ceiling(E e);
/**
* Returns the least element in this set strictly greater than the
* given element, or {@code null} if there is no such element.
*
* @param e the value to match
* @return the least element greater than {@code e},
* or {@code null} if there is no such element
* @throws ClassCastException if the specified element cannot be
* compared with the elements currently in the set
* @throws NullPointerException if the specified element is null
* and this set does not permit null elements
*/
E higher(E e);
/**
* Retrieves and removes the first (lowest) element,
* or returns {@code null} if this set is empty (optional operation).
*
* @return the first element, or {@code null} if this set is empty
*
* @throws UnsupportedOperationException if the {@code pollFirst}
* operation is not supported by this collection
*/
E pollFirst();
/**
* Retrieves and removes the last (highest) element,
* or returns {@code null} if this set is empty (optional operation).
*
* @return the last element, or {@code null} if this set is empty
*
* @throws UnsupportedOperationException if the {@code pollLast}
* operation is not supported by this collection
*/
E pollLast();
/**
* Returns an iterator over the elements in this set, in ascending order.
*
* @return an iterator over the elements in this set, in ascending order
*/
Iterator<E> iterator();
/**
* Returns a reverse order view of the elements contained in this set.
* The descending set is backed by this set, so changes to the set are
* reflected in the descending set, and vice-versa. If either set is
* modified while an iteration over either set is in progress (except
* through the iterator's own {@code remove} operation), the results of
* the iteration are undefined.
*
* <p>The returned set has an ordering equivalent to
* {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
* The expression {@code s.descendingSet().descendingSet()} returns a
* view of {@code s} essentially equivalent to {@code s}.
*
* @return a reverse order view of this set
*/
NavigableSet<E> descendingSet();
/**
* Returns an iterator over the elements in this set, in descending order.
* Equivalent in effect to {@code descendingSet().iterator()}.
*
* @return an iterator over the elements in this set, in descending order
*/
Iterator<E> descendingIterator();
/**
* Returns a view of the portion of this set whose elements range from
* {@code fromElement} to {@code toElement}. If {@code fromElement} and
* {@code toElement} are equal, the returned set is empty unless {@code
* fromInclusive} and {@code toInclusive} are both true. The returned set
* is backed by this set, so changes in the returned set are reflected in
* this set, and vice-versa. The returned set supports all optional set
* operations that this set supports.
*
* <p>The returned set will throw an {@code IllegalArgumentException}
* on an attempt to insert an element outside its range.
*
* @param fromElement low endpoint of the returned set
* @param fromInclusive {@code true} if the low endpoint
* is to be included in the returned view
* @param toElement high endpoint of the returned set
* @param toInclusive {@code true} if the high endpoint
* is to be included in the returned view
* @return a view of the portion of this set whose elements range from
* {@code fromElement}, inclusive, to {@code toElement}, exclusive
* @throws ClassCastException if {@code fromElement} and
* {@code toElement} cannot be compared to one another using this
* set's comparator (or, if the set has no comparator, using
* natural ordering). Implementations may, but are not required
* to, throw this exception if {@code fromElement} or
* {@code toElement} cannot be compared to elements currently in
* the set.
* @throws NullPointerException if {@code fromElement} or
* {@code toElement} is null and this set does
* not permit null elements
* @throws IllegalArgumentException if {@code fromElement} is
* greater than {@code toElement}; or if this set itself
* has a restricted range, and {@code fromElement} or
* {@code toElement} lies outside the bounds of the range.
*/
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive);
/**
* Returns a view of the portion of this set whose elements are less than
* (or equal to, if {@code inclusive} is true) {@code toElement}. The
* returned set is backed by this set, so changes in the returned set are
* reflected in this set, and vice-versa. The returned set supports all
* optional set operations that this set supports.
*
* <p>The returned set will throw an {@code IllegalArgumentException}
* on an attempt to insert an element outside its range.
*
* @param toElement high endpoint of the returned set
* @param inclusive {@code true} if the high endpoint
* is to be included in the returned view
* @return a view of the portion of this set whose elements are less than
* (or equal to, if {@code inclusive} is true) {@code toElement}
* @throws ClassCastException if {@code toElement} is not compatible
* with this set's comparator (or, if the set has no comparator,
* if {@code toElement} does not implement {@link Comparable}).
* Implementations may, but are not required to, throw this
* exception if {@code toElement} cannot be compared to elements
* currently in the set.
* @throws NullPointerException if {@code toElement} is null and
* this set does not permit null elements
* @throws IllegalArgumentException if this set itself has a
* restricted range, and {@code toElement} lies outside the
* bounds of the range
*/
NavigableSet<E> headSet(E toElement, boolean inclusive);
/**
* Returns a view of the portion of this set whose elements are greater
* than (or equal to, if {@code inclusive} is true) {@code fromElement}.
* The returned set is backed by this set, so changes in the returned set
* are reflected in this set, and vice-versa. The returned set supports
* all optional set operations that this set supports.
*
* <p>The returned set will throw an {@code IllegalArgumentException}
* on an attempt to insert an element outside its range.
*
* @param fromElement low endpoint of the returned set
* @param inclusive {@code true} if the low endpoint
* is to be included in the returned view
* @return a view of the portion of this set whose elements are greater
* than or equal to {@code fromElement}
* @throws ClassCastException if {@code fromElement} is not compatible
* with this set's comparator (or, if the set has no comparator,
* if {@code fromElement} does not implement {@link Comparable}).
* Implementations may, but are not required to, throw this
* exception if {@code fromElement} cannot be compared to elements
* currently in the set.
* @throws NullPointerException if {@code fromElement} is null
* and this set does not permit null elements
* @throws IllegalArgumentException if this set itself has a
* restricted range, and {@code fromElement} lies outside the
* bounds of the range
*/
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
/**
* {@inheritDoc}
*
* <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
SortedSet<E> subSet(E fromElement, E toElement);
/**
* {@inheritDoc}
*
* <p>Equivalent to {@code headSet(toElement, false)}.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
SortedSet<E> headSet(E toElement);
/**
* {@inheritDoc}
*
* <p>Equivalent to {@code tailSet(fromElement, true)}.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
SortedSet<E> tailSet(E fromElement);
/**
* {@inheritDoc}
*
* @implSpec
* If this set is not empty, the implementation in this interface returns the result of calling
* the {@code pollFirst} method. Otherwise, it throws {@code NoSuchElementException}.
*
* @throws NoSuchElementException {@inheritDoc}
* @throws UnsupportedOperationException {@inheritDoc}
* @since 21
*/
default E removeFirst() {
if (this.isEmpty()) {
throw new NoSuchElementException();
} else {
return this.pollFirst();
}
}
/**
* {@inheritDoc}
*
* @implSpec
* If this set is not empty, the implementation in this interface returns the result of calling
* the {@code pollLast} method. Otherwise, it throws {@code NoSuchElementException}.
*
* @throws NoSuchElementException {@inheritDoc}
* @throws UnsupportedOperationException {@inheritDoc}
* @since 21
*/
default E removeLast() {
if (this.isEmpty()) {
throw new NoSuchElementException();
} else {
return this.pollLast();
}
}
/**
* {@inheritDoc}
* <p>
* This method is equivalent to {@link #descendingSet descendingSet}.
*
* @implSpec
* The implementation in this interface returns the result of calling the
* {@code descendingSet} method.
*
* @return a reverse-ordered view of this collection, as a {@code NavigableSet}
* @since 21
*/
default NavigableSet<E> reversed() {
return this.descendingSet();
}
}