1 /*
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27 import java.io.Serializable;
28 import java.io.ObjectOutputStream;
29 import java.io.IOException;
30 import java.lang.reflect.Array;
31 import java.util.function.BiConsumer;
32 import java.util.function.BiFunction;
33 import java.util.function.Consumer;
34 import java.util.function.Function;
35 import java.util.function.Predicate;
36 import java.util.function.UnaryOperator;
37
38 /**
39 * This class consists exclusively of static methods that operate on or return
40 * collections. It contains polymorphic algorithms that operate on
41 * collections, "wrappers", which return a new collection backed by a
42 * specified collection, and a few other odds and ends.
43 *
44 * <p>The methods of this class all throw a <tt>NullPointerException</tt>
45 * if the collections or class objects provided to them are null.
46 *
47 * <p>The documentation for the polymorphic algorithms contained in this class
48 * generally includes a brief description of the <i>implementation</i>. Such
49 * descriptions should be regarded as <i>implementation notes</i>, rather than
50 * parts of the <i>specification</i>. Implementors should feel free to
51 * substitute other algorithms, so long as the specification itself is adhered
52 * to. (For example, the algorithm used by <tt>sort</tt> does not have to be
53 * a mergesort, but it does have to be <i>stable</i>.)
54 *
55 * <p>The "destructive" algorithms contained in this class, that is, the
56 * algorithms that modify the collection on which they operate, are specified
57 * to throw <tt>UnsupportedOperationException</tt> if the collection does not
58 * support the appropriate mutation primitive(s), such as the <tt>set</tt>
59 * method. These algorithms may, but are not required to, throw this
60 * exception if an invocation would have no effect on the collection. For
61 * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
62 * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
63 *
64 * <p>This class is a member of the
65 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
66 * Java Collections Framework</a>.
67 *
68 * @author Josh Bloch
69 * @author Neal Gafter
70 * @see Collection
71 * @see Set
72 * @see List
73 * @see Map
74 * @since 1.2
75 */
76
77 public class Collections {
78 // Suppresses default constructor, ensuring non-instantiability.
79 private Collections() {
80 }
81
82 // Algorithms
83
84 /*
85 * Tuning parameters for algorithms - Many of the List algorithms have
86 * two implementations, one of which is appropriate for RandomAccess
87 * lists, the other for "sequential." Often, the random access variant
88 * yields better performance on small sequential access lists. The
89 * tuning parameters below determine the cutoff point for what constitutes
90 * a "small" sequential access list for each algorithm. The values below
91 * were empirically determined to work well for LinkedList. Hopefully
92 * they should be reasonable for other sequential access List
93 * implementations. Those doing performance work on this code would
94 * do well to validate the values of these parameters from time to time.
95 * (The first word of each tuning parameter name is the algorithm to which
96 * it applies.)
97 */
98 private static final int BINARYSEARCH_THRESHOLD = 5000;
99 private static final int REVERSE_THRESHOLD = 18;
100 private static final int SHUFFLE_THRESHOLD = 5;
101 private static final int FILL_THRESHOLD = 25;
102 private static final int ROTATE_THRESHOLD = 100;
103 private static final int COPY_THRESHOLD = 10;
104 private static final int REPLACEALL_THRESHOLD = 11;
105 private static final int INDEXOFSUBLIST_THRESHOLD = 35;
106
107 /**
108 * Sorts the specified list into ascending order, according to the
109 * {@linkplain Comparable natural ordering} of its elements.
110 * All elements in the list must implement the {@link Comparable}
111 * interface. Furthermore, all elements in the list must be
112 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)}
113 * must not throw a {@code ClassCastException} for any elements
114 * {@code e1} and {@code e2} in the list).
115 *
116 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
117 * not be reordered as a result of the sort.
118 *
119 * <p>The specified list must be modifiable, but need not be resizable.
120 *
121 * <p>Implementation note: This implementation is a stable, adaptive,
122 * iterative mergesort that requires far fewer than n lg(n) comparisons
123 * when the input array is partially sorted, while offering the
124 * performance of a traditional mergesort when the input array is
125 * randomly ordered. If the input array is nearly sorted, the
126 * implementation requires approximately n comparisons. Temporary
127 * storage requirements vary from a small constant for nearly sorted
128 * input arrays to n/2 object references for randomly ordered input
129 * arrays.
130 *
131 * <p>The implementation takes equal advantage of ascending and
132 * descending order in its input array, and can take advantage of
133 * ascending and descending order in different parts of the same
134 * input array. It is well-suited to merging two or more sorted arrays:
135 * simply concatenate the arrays and sort the resulting array.
136 *
137 * <p>The implementation was adapted from Tim Peters's list sort for Python
138 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
139 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
140 * Sorting and Information Theoretic Complexity", in Proceedings of the
141 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
142 * January 1993.
143 *
144 * <p>This implementation dumps the specified list into an array, sorts
145 * the array, and iterates over the list resetting each element
146 * from the corresponding position in the array. This avoids the
147 * n<sup>2</sup> log(n) performance that would result from attempting
148 * to sort a linked list in place.
149 *
150 * @param list the list to be sorted.
151 * @throws ClassCastException if the list contains elements that are not
152 * <i>mutually comparable</i> (for example, strings and integers).
153 * @throws UnsupportedOperationException if the specified list's
154 * list-iterator does not support the {@code set} operation.
155 * @throws IllegalArgumentException (optional) if the implementation
156 * detects that the natural ordering of the list elements is
157 * found to violate the {@link Comparable} contract
158 */
159 @SuppressWarnings("unchecked")
160 public static <T extends Comparable<? super T>> void sort(List<T> list) {
161 Object[] a = list.toArray();
162 Arrays.sort(a);
163 ListIterator<T> i = list.listIterator();
164 for (int j=0; j<a.length; j++) {
165 i.next();
166 i.set((T)a[j]);
167 }
168 }
169
170 /**
171 * Sorts the specified list according to the order induced by the
172 * specified comparator. All elements in the list must be <i>mutually
173 * comparable</i> using the specified comparator (that is,
174 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
175 * for any elements {@code e1} and {@code e2} in the list).
176 *
177 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
178 * not be reordered as a result of the sort.
179 *
180 * <p>The specified list must be modifiable, but need not be resizable.
181 *
182 * <p>Implementation note: This implementation is a stable, adaptive,
183 * iterative mergesort that requires far fewer than n lg(n) comparisons
184 * when the input array is partially sorted, while offering the
185 * performance of a traditional mergesort when the input array is
186 * randomly ordered. If the input array is nearly sorted, the
187 * implementation requires approximately n comparisons. Temporary
188 * storage requirements vary from a small constant for nearly sorted
189 * input arrays to n/2 object references for randomly ordered input
190 * arrays.
191 *
192 * <p>The implementation takes equal advantage of ascending and
193 * descending order in its input array, and can take advantage of
194 * ascending and descending order in different parts of the same
195 * input array. It is well-suited to merging two or more sorted arrays:
196 * simply concatenate the arrays and sort the resulting array.
197 *
198 * <p>The implementation was adapted from Tim Peters's list sort for Python
199 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
200 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
201 * Sorting and Information Theoretic Complexity", in Proceedings of the
202 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
203 * January 1993.
204 *
205 * <p>This implementation dumps the specified list into an array, sorts
206 * the array, and iterates over the list resetting each element
207 * from the corresponding position in the array. This avoids the
208 * n<sup>2</sup> log(n) performance that would result from attempting
209 * to sort a linked list in place.
210 *
211 * @param list the list to be sorted.
212 * @param c the comparator to determine the order of the list. A
213 * {@code null} value indicates that the elements' <i>natural
214 * ordering</i> should be used.
215 * @throws ClassCastException if the list contains elements that are not
216 * <i>mutually comparable</i> using the specified comparator.
217 * @throws UnsupportedOperationException if the specified list's
218 * list-iterator does not support the {@code set} operation.
219 * @throws IllegalArgumentException (optional) if the comparator is
220 * found to violate the {@link Comparator} contract
221 */
222 @SuppressWarnings({"unchecked", "rawtypes"})
223 public static <T> void sort(List<T> list, Comparator<? super T> c) {
224 Object[] a = list.toArray();
225 Arrays.sort(a, (Comparator)c);
226 ListIterator<T> i = list.listIterator();
227 for (int j=0; j<a.length; j++) {
228 i.next();
229 i.set((T)a[j]);
230 }
231 }
232
233
234 /**
235 * Searches the specified list for the specified object using the binary
236 * search algorithm. The list must be sorted into ascending order
237 * according to the {@linkplain Comparable natural ordering} of its
238 * elements (as by the {@link #sort(List)} method) prior to making this
239 * call. If it is not sorted, the results are undefined. If the list
240 * contains multiple elements equal to the specified object, there is no
241 * guarantee which one will be found.
242 *
243 * <p>This method runs in log(n) time for a "random access" list (which
244 * provides near-constant-time positional access). If the specified list
245 * does not implement the {@link RandomAccess} interface and is large,
246 * this method will do an iterator-based binary search that performs
247 * O(n) link traversals and O(log n) element comparisons.
248 *
249 * @param list the list to be searched.
250 * @param key the key to be searched for.
251 * @return the index of the search key, if it is contained in the list;
252 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
253 * <i>insertion point</i> is defined as the point at which the
254 * key would be inserted into the list: the index of the first
255 * element greater than the key, or <tt>list.size()</tt> if all
256 * elements in the list are less than the specified key. Note
257 * that this guarantees that the return value will be >= 0 if
258 * and only if the key is found.
259 * @throws ClassCastException if the list contains elements that are not
260 * <i>mutually comparable</i> (for example, strings and
261 * integers), or the search key is not mutually comparable
262 * with the elements of the list.
263 */
264 public static <T>
265 int binarySearch(List<? extends Comparable<? super T>> list, T key) {
266 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
267 return Collections.indexedBinarySearch(list, key);
268 else
269 return Collections.iteratorBinarySearch(list, key);
270 }
271
272 private static <T>
273 int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
274 int low = 0;
275 int high = list.size()-1;
276
277 while (low <= high) {
278 int mid = (low + high) >>> 1;
279 Comparable<? super T> midVal = list.get(mid);
280 int cmp = midVal.compareTo(key);
281
282 if (cmp < 0)
283 low = mid + 1;
284 else if (cmp > 0)
285 high = mid - 1;
286 else
287 return mid; // key found
288 }
289 return -(low + 1); // key not found
290 }
291
292 private static <T>
293 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
294 {
295 int low = 0;
296 int high = list.size()-1;
297 ListIterator<? extends Comparable<? super T>> i = list.listIterator();
298
299 while (low <= high) {
300 int mid = (low + high) >>> 1;
301 Comparable<? super T> midVal = get(i, mid);
302 int cmp = midVal.compareTo(key);
303
304 if (cmp < 0)
305 low = mid + 1;
306 else if (cmp > 0)
307 high = mid - 1;
308 else
309 return mid; // key found
310 }
311 return -(low + 1); // key not found
312 }
313
314 /**
315 * Gets the ith element from the given list by repositioning the specified
316 * list listIterator.
317 */
318 private static <T> T get(ListIterator<? extends T> i, int index) {
319 T obj = null;
320 int pos = i.nextIndex();
321 if (pos <= index) {
322 do {
323 obj = i.next();
324 } while (pos++ < index);
325 } else {
326 do {
327 obj = i.previous();
328 } while (--pos > index);
329 }
330 return obj;
331 }
332
333 /**
334 * Searches the specified list for the specified object using the binary
335 * search algorithm. The list must be sorted into ascending order
336 * according to the specified comparator (as by the
337 * {@link #sort(List, Comparator) sort(List, Comparator)}
338 * method), prior to making this call. If it is
339 * not sorted, the results are undefined. If the list contains multiple
340 * elements equal to the specified object, there is no guarantee which one
341 * will be found.
342 *
343 * <p>This method runs in log(n) time for a "random access" list (which
344 * provides near-constant-time positional access). If the specified list
345 * does not implement the {@link RandomAccess} interface and is large,
346 * this method will do an iterator-based binary search that performs
347 * O(n) link traversals and O(log n) element comparisons.
348 *
349 * @param list the list to be searched.
350 * @param key the key to be searched for.
351 * @param c the comparator by which the list is ordered.
352 * A <tt>null</tt> value indicates that the elements'
353 * {@linkplain Comparable natural ordering} should be used.
354 * @return the index of the search key, if it is contained in the list;
355 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
356 * <i>insertion point</i> is defined as the point at which the
357 * key would be inserted into the list: the index of the first
358 * element greater than the key, or <tt>list.size()</tt> if all
359 * elements in the list are less than the specified key. Note
360 * that this guarantees that the return value will be >= 0 if
361 * and only if the key is found.
362 * @throws ClassCastException if the list contains elements that are not
363 * <i>mutually comparable</i> using the specified comparator,
364 * or the search key is not mutually comparable with the
365 * elements of the list using this comparator.
366 */
367 @SuppressWarnings("unchecked")
368 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
369 if (c==null)
370 return binarySearch((List<? extends Comparable<? super T>>) list, key);
371
372 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
373 return Collections.indexedBinarySearch(list, key, c);
374 else
375 return Collections.iteratorBinarySearch(list, key, c);
376 }
377
378 private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
379 int low = 0;
380 int high = l.size()-1;
381
382 while (low <= high) {
383 int mid = (low + high) >>> 1;
384 T midVal = l.get(mid);
385 int cmp = c.compare(midVal, key);
386
387 if (cmp < 0)
388 low = mid + 1;
389 else if (cmp > 0)
390 high = mid - 1;
391 else
392 return mid; // key found
393 }
394 return -(low + 1); // key not found
395 }
396
397 private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
398 int low = 0;
399 int high = l.size()-1;
400 ListIterator<? extends T> i = l.listIterator();
401
402 while (low <= high) {
403 int mid = (low + high) >>> 1;
404 T midVal = get(i, mid);
405 int cmp = c.compare(midVal, key);
406
407 if (cmp < 0)
408 low = mid + 1;
409 else if (cmp > 0)
410 high = mid - 1;
411 else
412 return mid; // key found
413 }
414 return -(low + 1); // key not found
415 }
416
417 /**
418 * Reverses the order of the elements in the specified list.<p>
419 *
420 * This method runs in linear time.
421 *
422 * @param list the list whose elements are to be reversed.
423 * @throws UnsupportedOperationException if the specified list or
424 * its list-iterator does not support the <tt>set</tt> operation.
425 */
426 @SuppressWarnings({"rawtypes", "unchecked"})
427 public static void reverse(List<?> list) {
428 int size = list.size();
429 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
430 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
431 swap(list, i, j);
432 } else {
433 // instead of using a raw type here, it's possible to capture
434 // the wildcard but it will require a call to a supplementary
435 // private method
436 ListIterator fwd = list.listIterator();
437 ListIterator rev = list.listIterator(size);
438 for (int i=0, mid=list.size()>>1; i<mid; i++) {
439 Object tmp = fwd.next();
440 fwd.set(rev.previous());
441 rev.set(tmp);
442 }
443 }
444 }
445
446 /**
447 * Randomly permutes the specified list using a default source of
448 * randomness. All permutations occur with approximately equal
449 * likelihood.
450 *
451 * <p>The hedge "approximately" is used in the foregoing description because
452 * default source of randomness is only approximately an unbiased source
453 * of independently chosen bits. If it were a perfect source of randomly
454 * chosen bits, then the algorithm would choose permutations with perfect
455 * uniformity.
456 *
457 * <p>This implementation traverses the list backwards, from the last
458 * element up to the second, repeatedly swapping a randomly selected element
459 * into the "current position". Elements are randomly selected from the
460 * portion of the list that runs from the first element to the current
461 * position, inclusive.
462 *
463 * <p>This method runs in linear time. If the specified list does not
464 * implement the {@link RandomAccess} interface and is large, this
465 * implementation dumps the specified list into an array before shuffling
466 * it, and dumps the shuffled array back into the list. This avoids the
467 * quadratic behavior that would result from shuffling a "sequential
468 * access" list in place.
469 *
470 * @param list the list to be shuffled.
471 * @throws UnsupportedOperationException if the specified list or
472 * its list-iterator does not support the <tt>set</tt> operation.
473 */
474 public static void shuffle(List<?> list) {
475 Random rnd = r;
476 if (rnd == null)
477 r = rnd = new Random(); // harmless race.
478 shuffle(list, rnd);
479 }
480
481 private static Random r;
482
483 /**
484 * Randomly permute the specified list using the specified source of
485 * randomness. All permutations occur with equal likelihood
486 * assuming that the source of randomness is fair.<p>
487 *
488 * This implementation traverses the list backwards, from the last element
489 * up to the second, repeatedly swapping a randomly selected element into
490 * the "current position". Elements are randomly selected from the
491 * portion of the list that runs from the first element to the current
492 * position, inclusive.<p>
493 *
494 * This method runs in linear time. If the specified list does not
495 * implement the {@link RandomAccess} interface and is large, this
496 * implementation dumps the specified list into an array before shuffling
497 * it, and dumps the shuffled array back into the list. This avoids the
498 * quadratic behavior that would result from shuffling a "sequential
499 * access" list in place.
500 *
501 * @param list the list to be shuffled.
502 * @param rnd the source of randomness to use to shuffle the list.
503 * @throws UnsupportedOperationException if the specified list or its
504 * list-iterator does not support the <tt>set</tt> operation.
505 */
506 @SuppressWarnings({"rawtypes", "unchecked"})
507 public static void shuffle(List<?> list, Random rnd) {
508 int size = list.size();
509 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
510 for (int i=size; i>1; i--)
511 swap(list, i-1, rnd.nextInt(i));
512 } else {
513 Object arr[] = list.toArray();
514
515 // Shuffle array
516 for (int i=size; i>1; i--)
517 swap(arr, i-1, rnd.nextInt(i));
518
519 // Dump array back into list
520 // instead of using a raw type here, it's possible to capture
521 // the wildcard but it will require a call to a supplementary
522 // private method
523 ListIterator it = list.listIterator();
524 for (int i=0; i<arr.length; i++) {
525 it.next();
526 it.set(arr[i]);
527 }
528 }
529 }
530
531 /**
532 * Swaps the elements at the specified positions in the specified list.
533 * (If the specified positions are equal, invoking this method leaves
534 * the list unchanged.)
535 *
536 * @param list The list in which to swap elements.
537 * @param i the index of one element to be swapped.
538 * @param j the index of the other element to be swapped.
539 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
540 * is out of range (i < 0 || i >= list.size()
541 * || j < 0 || j >= list.size()).
542 * @since 1.4
543 */
544 @SuppressWarnings({"rawtypes", "unchecked"})
545 public static void swap(List<?> list, int i, int j) {
546 // instead of using a raw type here, it's possible to capture
547 // the wildcard but it will require a call to a supplementary
548 // private method
549 final List l = list;
550 l.set(i, l.set(j, l.get(i)));
551 }
552
553 /**
554 * Swaps the two specified elements in the specified array.
555 */
556 private static void swap(Object[] arr, int i, int j) {
557 Object tmp = arr[i];
558 arr[i] = arr[j];
559 arr[j] = tmp;
560 }
561
562 /**
563 * Replaces all of the elements of the specified list with the specified
564 * element. <p>
565 *
566 * This method runs in linear time.
567 *
568 * @param list the list to be filled with the specified element.
569 * @param obj The element with which to fill the specified list.
570 * @throws UnsupportedOperationException if the specified list or its
571 * list-iterator does not support the <tt>set</tt> operation.
572 */
573 public static <T> void fill(List<? super T> list, T obj) {
574 int size = list.size();
575
576 if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
577 for (int i=0; i<size; i++)
578 list.set(i, obj);
579 } else {
580 ListIterator<? super T> itr = list.listIterator();
581 for (int i=0; i<size; i++) {
582 itr.next();
583 itr.set(obj);
584 }
585 }
586 }
587
588 /**
589 * Copies all of the elements from one list into another. After the
590 * operation, the index of each copied element in the destination list
591 * will be identical to its index in the source list. The destination
592 * list must be at least as long as the source list. If it is longer, the
593 * remaining elements in the destination list are unaffected. <p>
594 *
595 * This method runs in linear time.
596 *
597 * @param dest The destination list.
598 * @param src The source list.
599 * @throws IndexOutOfBoundsException if the destination list is too small
600 * to contain the entire source List.
601 * @throws UnsupportedOperationException if the destination list's
602 * list-iterator does not support the <tt>set</tt> operation.
603 */
604 public static <T> void copy(List<? super T> dest, List<? extends T> src) {
605 int srcSize = src.size();
606 if (srcSize > dest.size())
607 throw new IndexOutOfBoundsException("Source does not fit in dest");
608
609 if (srcSize < COPY_THRESHOLD ||
610 (src instanceof RandomAccess && dest instanceof RandomAccess)) {
611 for (int i=0; i<srcSize; i++)
612 dest.set(i, src.get(i));
613 } else {
614 ListIterator<? super T> di=dest.listIterator();
615 ListIterator<? extends T> si=src.listIterator();
616 for (int i=0; i<srcSize; i++) {
617 di.next();
618 di.set(si.next());
619 }
620 }
621 }
622
623 /**
624 * Returns the minimum element of the given collection, according to the
625 * <i>natural ordering</i> of its elements. All elements in the
626 * collection must implement the <tt>Comparable</tt> interface.
627 * Furthermore, all elements in the collection must be <i>mutually
628 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
629 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
630 * <tt>e2</tt> in the collection).<p>
631 *
632 * This method iterates over the entire collection, hence it requires
633 * time proportional to the size of the collection.
634 *
635 * @param coll the collection whose minimum element is to be determined.
636 * @return the minimum element of the given collection, according
637 * to the <i>natural ordering</i> of its elements.
638 * @throws ClassCastException if the collection contains elements that are
639 * not <i>mutually comparable</i> (for example, strings and
640 * integers).
641 * @throws NoSuchElementException if the collection is empty.
642 * @see Comparable
643 */
644 public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
645 Iterator<? extends T> i = coll.iterator();
646 T candidate = i.next();
647
648 while (i.hasNext()) {
649 T next = i.next();
650 if (next.compareTo(candidate) < 0)
651 candidate = next;
652 }
653 return candidate;
654 }
655
656 /**
657 * Returns the minimum element of the given collection, according to the
658 * order induced by the specified comparator. All elements in the
659 * collection must be <i>mutually comparable</i> by the specified
660 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
661 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
662 * <tt>e2</tt> in the collection).<p>
663 *
664 * This method iterates over the entire collection, hence it requires
665 * time proportional to the size of the collection.
666 *
667 * @param coll the collection whose minimum element is to be determined.
668 * @param comp the comparator with which to determine the minimum element.
669 * A <tt>null</tt> value indicates that the elements' <i>natural
670 * ordering</i> should be used.
671 * @return the minimum element of the given collection, according
672 * to the specified comparator.
673 * @throws ClassCastException if the collection contains elements that are
674 * not <i>mutually comparable</i> using the specified comparator.
675 * @throws NoSuchElementException if the collection is empty.
676 * @see Comparable
677 */
678 @SuppressWarnings({"unchecked", "rawtypes"})
679 public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
680 if (comp==null)
681 return (T)min((Collection) coll);
682
683 Iterator<? extends T> i = coll.iterator();
684 T candidate = i.next();
685
686 while (i.hasNext()) {
687 T next = i.next();
688 if (comp.compare(next, candidate) < 0)
689 candidate = next;
690 }
691 return candidate;
692 }
693
694 /**
695 * Returns the maximum element of the given collection, according to the
696 * <i>natural ordering</i> of its elements. All elements in the
697 * collection must implement the <tt>Comparable</tt> interface.
698 * Furthermore, all elements in the collection must be <i>mutually
699 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
700 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
701 * <tt>e2</tt> in the collection).<p>
702 *
703 * This method iterates over the entire collection, hence it requires
704 * time proportional to the size of the collection.
705 *
706 * @param coll the collection whose maximum element is to be determined.
707 * @return the maximum element of the given collection, according
708 * to the <i>natural ordering</i> of its elements.
709 * @throws ClassCastException if the collection contains elements that are
710 * not <i>mutually comparable</i> (for example, strings and
711 * integers).
712 * @throws NoSuchElementException if the collection is empty.
713 * @see Comparable
714 */
715 public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
716 Iterator<? extends T> i = coll.iterator();
717 T candidate = i.next();
718
719 while (i.hasNext()) {
720 T next = i.next();
721 if (next.compareTo(candidate) > 0)
722 candidate = next;
723 }
724 return candidate;
725 }
726
727 /**
728 * Returns the maximum element of the given collection, according to the
729 * order induced by the specified comparator. All elements in the
730 * collection must be <i>mutually comparable</i> by the specified
731 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
732 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
733 * <tt>e2</tt> in the collection).<p>
734 *
735 * This method iterates over the entire collection, hence it requires
736 * time proportional to the size of the collection.
737 *
738 * @param coll the collection whose maximum element is to be determined.
739 * @param comp the comparator with which to determine the maximum element.
740 * A <tt>null</tt> value indicates that the elements' <i>natural
741 * ordering</i> should be used.
742 * @return the maximum element of the given collection, according
743 * to the specified comparator.
744 * @throws ClassCastException if the collection contains elements that are
745 * not <i>mutually comparable</i> using the specified comparator.
746 * @throws NoSuchElementException if the collection is empty.
747 * @see Comparable
748 */
749 @SuppressWarnings({"unchecked", "rawtypes"})
750 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
751 if (comp==null)
752 return (T)max((Collection) coll);
753
754 Iterator<? extends T> i = coll.iterator();
755 T candidate = i.next();
756
757 while (i.hasNext()) {
758 T next = i.next();
759 if (comp.compare(next, candidate) > 0)
760 candidate = next;
761 }
762 return candidate;
763 }
764
765 /**
766 * Rotates the elements in the specified list by the specified distance.
767 * After calling this method, the element at index <tt>i</tt> will be
768 * the element previously at index <tt>(i - distance)</tt> mod
769 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
770 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
771 * the size of the list.)
772 *
773 * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
774 * After invoking <tt>Collections.rotate(list, 1)</tt> (or
775 * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
776 * <tt>[s, t, a, n, k]</tt>.
777 *
778 * <p>Note that this method can usefully be applied to sublists to
779 * move one or more elements within a list while preserving the
780 * order of the remaining elements. For example, the following idiom
781 * moves the element at index <tt>j</tt> forward to position
782 * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
783 * <pre>
784 * Collections.rotate(list.subList(j, k+1), -1);
785 * </pre>
786 * To make this concrete, suppose <tt>list</tt> comprises
787 * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt>
788 * (<tt>b</tt>) forward two positions, perform the following invocation:
789 * <pre>
790 * Collections.rotate(l.subList(1, 4), -1);
791 * </pre>
792 * The resulting list is <tt>[a, c, d, b, e]</tt>.
793 *
794 * <p>To move more than one element forward, increase the absolute value
795 * of the rotation distance. To move elements backward, use a positive
796 * shift distance.
797 *
798 * <p>If the specified list is small or implements the {@link
799 * RandomAccess} interface, this implementation exchanges the first
800 * element into the location it should go, and then repeatedly exchanges
801 * the displaced element into the location it should go until a displaced
802 * element is swapped into the first element. If necessary, the process
803 * is repeated on the second and successive elements, until the rotation
804 * is complete. If the specified list is large and doesn't implement the
805 * <tt>RandomAccess</tt> interface, this implementation breaks the
806 * list into two sublist views around index <tt>-distance mod size</tt>.
807 * Then the {@link #reverse(List)} method is invoked on each sublist view,
808 * and finally it is invoked on the entire list. For a more complete
809 * description of both algorithms, see Section 2.3 of Jon Bentley's
810 * <i>Programming Pearls</i> (Addison-Wesley, 1986).
811 *
812 * @param list the list to be rotated.
813 * @param distance the distance to rotate the list. There are no
814 * constraints on this value; it may be zero, negative, or
815 * greater than <tt>list.size()</tt>.
816 * @throws UnsupportedOperationException if the specified list or
817 * its list-iterator does not support the <tt>set</tt> operation.
818 * @since 1.4
819 */
820 public static void rotate(List<?> list, int distance) {
821 if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
822 rotate1(list, distance);
823 else
824 rotate2(list, distance);
825 }
826
827 private static <T> void rotate1(List<T> list, int distance) {
828 int size = list.size();
829 if (size == 0)
830 return;
831 distance = distance % size;
832 if (distance < 0)
833 distance += size;
834 if (distance == 0)
835 return;
836
837 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
838 T displaced = list.get(cycleStart);
839 int i = cycleStart;
840 do {
841 i += distance;
842 if (i >= size)
843 i -= size;
844 displaced = list.set(i, displaced);
845 nMoved ++;
846 } while (i != cycleStart);
847 }
848 }
849
850 private static void rotate2(List<?> list, int distance) {
851 int size = list.size();
852 if (size == 0)
853 return;
854 int mid = -distance % size;
855 if (mid < 0)
856 mid += size;
857 if (mid == 0)
858 return;
859
860 reverse(list.subList(0, mid));
861 reverse(list.subList(mid, size));
862 reverse(list);
863 }
864
865 /**
866 * Replaces all occurrences of one specified value in a list with another.
867 * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
868 * in <tt>list</tt> such that
869 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
870 * (This method has no effect on the size of the list.)
871 *
872 * @param list the list in which replacement is to occur.
873 * @param oldVal the old value to be replaced.
874 * @param newVal the new value with which <tt>oldVal</tt> is to be
875 * replaced.
876 * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
877 * <tt>e</tt> such that
878 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
879 * @throws UnsupportedOperationException if the specified list or
880 * its list-iterator does not support the <tt>set</tt> operation.
881 * @since 1.4
882 */
883 public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
884 boolean result = false;
885 int size = list.size();
886 if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
887 if (oldVal==null) {
888 for (int i=0; i<size; i++) {
889 if (list.get(i)==null) {
890 list.set(i, newVal);
891 result = true;
892 }
893 }
894 } else {
895 for (int i=0; i<size; i++) {
896 if (oldVal.equals(list.get(i))) {
897 list.set(i, newVal);
898 result = true;
899 }
900 }
901 }
902 } else {
903 ListIterator<T> itr=list.listIterator();
904 if (oldVal==null) {
905 for (int i=0; i<size; i++) {
906 if (itr.next()==null) {
907 itr.set(newVal);
908 result = true;
909 }
910 }
911 } else {
912 for (int i=0; i<size; i++) {
913 if (oldVal.equals(itr.next())) {
914 itr.set(newVal);
915 result = true;
916 }
917 }
918 }
919 }
920 return result;
921 }
922
923 /**
924 * Returns the starting position of the first occurrence of the specified
925 * target list within the specified source list, or -1 if there is no
926 * such occurrence. More formally, returns the lowest index <tt>i</tt>
927 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
928 * or -1 if there is no such index. (Returns -1 if
929 * <tt>target.size() > source.size()</tt>.)
930 *
931 * <p>This implementation uses the "brute force" technique of scanning
932 * over the source list, looking for a match with the target at each
933 * location in turn.
934 *
935 * @param source the list in which to search for the first occurrence
936 * of <tt>target</tt>.
937 * @param target the list to search for as a subList of <tt>source</tt>.
938 * @return the starting position of the first occurrence of the specified
939 * target list within the specified source list, or -1 if there
940 * is no such occurrence.
941 * @since 1.4
942 */
943 public static int indexOfSubList(List<?> source, List<?> target) {
944 int sourceSize = source.size();
945 int targetSize = target.size();
946 int maxCandidate = sourceSize - targetSize;
947
948 if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
949 (source instanceof RandomAccess&&target instanceof RandomAccess)) {
950 nextCand:
951 for (int candidate = 0; candidate <= maxCandidate; candidate++) {
952 for (int i=0, j=candidate; i<targetSize; i++, j++)
953 if (!eq(target.get(i), source.get(j)))
954 continue nextCand; // Element mismatch, try next cand
955 return candidate; // All elements of candidate matched target
956 }
957 } else { // Iterator version of above algorithm
958 ListIterator<?> si = source.listIterator();
959 nextCand:
960 for (int candidate = 0; candidate <= maxCandidate; candidate++) {
961 ListIterator<?> ti = target.listIterator();
962 for (int i=0; i<targetSize; i++) {
963 if (!eq(ti.next(), si.next())) {
964 // Back up source iterator to next candidate
965 for (int j=0; j<i; j++)
966 si.previous();
967 continue nextCand;
968 }
969 }
970 return candidate;
971 }
972 }
973 return -1; // No candidate matched the target
974 }
975
976 /**
977 * Returns the starting position of the last occurrence of the specified
978 * target list within the specified source list, or -1 if there is no such
979 * occurrence. More formally, returns the highest index <tt>i</tt>
980 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
981 * or -1 if there is no such index. (Returns -1 if
982 * <tt>target.size() > source.size()</tt>.)
983 *
984 * <p>This implementation uses the "brute force" technique of iterating
985 * over the source list, looking for a match with the target at each
986 * location in turn.
987 *
988 * @param source the list in which to search for the last occurrence
989 * of <tt>target</tt>.
990 * @param target the list to search for as a subList of <tt>source</tt>.
991 * @return the starting position of the last occurrence of the specified
992 * target list within the specified source list, or -1 if there
993 * is no such occurrence.
994 * @since 1.4
995 */
996 public static int lastIndexOfSubList(List<?> source, List<?> target) {
997 int sourceSize = source.size();
998 int targetSize = target.size();
999 int maxCandidate = sourceSize - targetSize;
1000
1001 if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
1002 source instanceof RandomAccess) { // Index access version
1003 nextCand:
1004 for (int candidate = maxCandidate; candidate >= 0; candidate--) {
1005 for (int i=0, j=candidate; i<targetSize; i++, j++)
1006 if (!eq(target.get(i), source.get(j)))
1007 continue nextCand; // Element mismatch, try next cand
1008 return candidate; // All elements of candidate matched target
1009 }
1010 } else { // Iterator version of above algorithm
1011 if (maxCandidate < 0)
1012 return -1;
1013 ListIterator<?> si = source.listIterator(maxCandidate);
1014 nextCand:
1015 for (int candidate = maxCandidate; candidate >= 0; candidate--) {
1016 ListIterator<?> ti = target.listIterator();
1017 for (int i=0; i<targetSize; i++) {
1018 if (!eq(ti.next(), si.next())) {
1019 if (candidate != 0) {
1020 // Back up source iterator to next candidate
1021 for (int j=0; j<=i+1; j++)
1022 si.previous();
1023 }
1024 continue nextCand;
1025 }
1026 }
1027 return candidate;
1028 }
1029 }
1030 return -1; // No candidate matched the target
1031 }
1032
1033
1034 // Unmodifiable Wrappers
1035
1036 /**
1037 * Returns an unmodifiable view of the specified collection. This method
1038 * allows modules to provide users with "read-only" access to internal
1039 * collections. Query operations on the returned collection "read through"
1040 * to the specified collection, and attempts to modify the returned
1041 * collection, whether direct or via its iterator, result in an
1042 * <tt>UnsupportedOperationException</tt>.<p>
1043 *
1044 * The returned collection does <i>not</i> pass the hashCode and equals
1045 * operations through to the backing collection, but relies on
1046 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
1047 * is necessary to preserve the contracts of these operations in the case
1048 * that the backing collection is a set or a list.<p>
1049 *
1050 * The returned collection will be serializable if the specified collection
1051 * is serializable.
1052 *
1053 * @param c the collection for which an unmodifiable view is to be
1054 * returned.
1055 * @return an unmodifiable view of the specified collection.
1056 */
1057 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
1058 return new UnmodifiableCollection<>(c);
1059 }
1060
1061 /**
1062 * @serial include
1063 */
1064 static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
1065 private static final long serialVersionUID = 1820017752578914078L;
1066
1067 final Collection<? extends E> c;
1068
1069 UnmodifiableCollection(Collection<? extends E> c) {
1070 if (c==null)
1071 throw new NullPointerException();
1072 this.c = c;
1073 }
1074
1075 public int size() {return c.size();}
1076 public boolean isEmpty() {return c.isEmpty();}
1077 public boolean contains(Object o) {return c.contains(o);}
1078 public Object[] toArray() {return c.toArray();}
1079 public <T> T[] toArray(T[] a) {return c.toArray(a);}
1080 public String toString() {return c.toString();}
1081
1082 public Iterator<E> iterator() {
1083 return new Iterator<E>() {
1084 private final Iterator<? extends E> i = c.iterator();
1085
1086 public boolean hasNext() {return i.hasNext();}
1087 public E next() {return i.next();}
1088 public void remove() {
1089 throw new UnsupportedOperationException();
1090 }
1091 @Override
1092 public void forEachRemaining(Consumer<? super E> action) {
1093 // Use backing collection version
1094 i.forEachRemaining(action);
1095 }
1096 };
1097 }
1098
1099 public boolean add(E e) {
1100 throw new UnsupportedOperationException();
1101 }
1102 public boolean remove(Object o) {
1103 throw new UnsupportedOperationException();
1104 }
1105
1106 public boolean containsAll(Collection<?> coll) {
1107 return c.containsAll(coll);
1108 }
1109 public boolean addAll(Collection<? extends E> coll) {
1110 throw new UnsupportedOperationException();
1111 }
1112 public boolean removeAll(Collection<?> coll) {
1113 throw new UnsupportedOperationException();
1114 }
1115 public boolean retainAll(Collection<?> coll) {
1116 throw new UnsupportedOperationException();
1117 }
1118 public void clear() {
1119 throw new UnsupportedOperationException();
1120 }
1121
1122 // Override default methods in Collection
1123 @Override
1124 public void forEach(Consumer<? super E> action) {
1125 c.forEach(action);
1126 }
1127 @Override
1128 public boolean removeIf(Predicate<? super E> filter) {
1129 throw new UnsupportedOperationException();
1130 }
1131 @Override
1132 public Spliterator<E> spliterator() {
1133 return (Spliterator<E>)c.spliterator();
1134 }
1135
1136 }
1137
1138 /**
1139 * Returns an unmodifiable view of the specified set. This method allows
1140 * modules to provide users with "read-only" access to internal sets.
1141 * Query operations on the returned set "read through" to the specified
1142 * set, and attempts to modify the returned set, whether direct or via its
1143 * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1144 *
1145 * The returned set will be serializable if the specified set
1146 * is serializable.
1147 *
1148 * @param s the set for which an unmodifiable view is to be returned.
1149 * @return an unmodifiable view of the specified set.
1150 */
1151 public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1152 return new UnmodifiableSet<>(s);
1153 }
1154
1155 /**
1156 * @serial include
1157 */
1158 static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
1159 implements Set<E>, Serializable {
1160 private static final long serialVersionUID = -9215047833775013803L;
1161
1162 UnmodifiableSet(Set<? extends E> s) {super(s);}
1163 public boolean equals(Object o) {return o == this || c.equals(o);}
1164 public int hashCode() {return c.hashCode();}
1165 }
1166
1167 /**
1168 * Returns an unmodifiable view of the specified sorted set. This method
1169 * allows modules to provide users with "read-only" access to internal
1170 * sorted sets. Query operations on the returned sorted set "read
1171 * through" to the specified sorted set. Attempts to modify the returned
1172 * sorted set, whether direct, via its iterator, or via its
1173 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1174 * an <tt>UnsupportedOperationException</tt>.<p>
1175 *
1176 * The returned sorted set will be serializable if the specified sorted set
1177 * is serializable.
1178 *
1179 * @param s the sorted set for which an unmodifiable view is to be
1180 * returned.
1181 * @return an unmodifiable view of the specified sorted set.
1182 */
1183 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
1184 return new UnmodifiableSortedSet<>(s);
1185 }
1186
1187 /**
1188 * @serial include
1189 */
1190 static class UnmodifiableSortedSet<E>
1191 extends UnmodifiableSet<E>
1192 implements SortedSet<E>, Serializable {
1193 private static final long serialVersionUID = -4929149591599911165L;
1194 private final SortedSet<E> ss;
1195
1196 UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1197
1198 public Comparator<? super E> comparator() {return ss.comparator();}
1199
1200 public SortedSet<E> subSet(E fromElement, E toElement) {
1201 return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement));
1202 }
1203 public SortedSet<E> headSet(E toElement) {
1204 return new UnmodifiableSortedSet<>(ss.headSet(toElement));
1205 }
1206 public SortedSet<E> tailSet(E fromElement) {
1207 return new UnmodifiableSortedSet<>(ss.tailSet(fromElement));
1208 }
1209
1210 public E first() {return ss.first();}
1211 public E last() {return ss.last();}
1212 }
1213
1214 /**
1215 * Returns an unmodifiable view of the specified navigable set. This method
1216 * allows modules to provide users with "read-only" access to internal
1217 * navigable sets. Query operations on the returned navigable set "read
1218 * through" to the specified navigable set. Attempts to modify the returned
1219 * navigable set, whether direct, via its iterator, or via its
1220 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1221 * an <tt>UnsupportedOperationException</tt>.<p>
1222 *
1223 * The returned navigable set will be serializable if the specified sorted set
1224 * is serializable.
1225 *
1226 * @param s the navigable set for which an unmodifiable view is to be
1227 * returned
1228 * @return an unmodifiable view of the specified navigable set
1229 * @since 1.8
1230 */
1231 public static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s) {
1232 return new UnmodifiableNavigableSet<>(s);
1233 }
1234
1235 /**
1236 * @serial include
1237 */
1238 static class UnmodifiableNavigableSet<E>
1239 extends UnmodifiableSortedSet<E>
1240 implements NavigableSet<E>, Serializable {
1241
1242 private final NavigableSet<E> ns;
1243
1244 UnmodifiableNavigableSet(NavigableSet<E> s) {super(s); ns = s;}
1245
1246 @Override public E lower(E e) { return ns.lower(e); }
1247 @Override public E floor(E e) { return ns.floor(e); }
1248 @Override public E ceiling(E e) { return ns.ceiling(e); }
1249 @Override public E higher(E e) { return ns.higher(e); }
1250 @Override public E pollFirst() { throw new UnsupportedOperationException(); }
1251 @Override public E pollLast() { throw new UnsupportedOperationException(); }
1252 @Override
1253 public NavigableSet<E> descendingSet() {
1254 return new UnmodifiableNavigableSet<>(ns.descendingSet());
1255 }
1256
1257 @Override
1258 public Iterator<E> descendingIterator() {
1259 return descendingSet().iterator();
1260 }
1261
1262 @Override
1263 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
1264 return new UnmodifiableNavigableSet<>(ns.subSet(fromElement, fromInclusive, toElement, toInclusive));
1265 }
1266
1267 @Override
1268 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1269 return new UnmodifiableNavigableSet<>(ns.headSet(toElement, inclusive));
1270 }
1271
1272 @Override
1273 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1274 return new UnmodifiableNavigableSet<>(ns.tailSet(fromElement, inclusive));
1275 }
1276 }
1277
1278 /**
1279 * Returns an unmodifiable view of the specified list. This method allows
1280 * modules to provide users with "read-only" access to internal
1281 * lists. Query operations on the returned list "read through" to the
1282 * specified list, and attempts to modify the returned list, whether
1283 * direct or via its iterator, result in an
1284 * <tt>UnsupportedOperationException</tt>.<p>
1285 *
1286 * The returned list will be serializable if the specified list
1287 * is serializable. Similarly, the returned list will implement
1288 * {@link RandomAccess} if the specified list does.
1289 *
1290 * @param list the list for which an unmodifiable view is to be returned.
1291 * @return an unmodifiable view of the specified list.
1292 */
1293 public static <T> List<T> unmodifiableList(List<? extends T> list) {
1294 return (list instanceof RandomAccess ?
1295 new UnmodifiableRandomAccessList<>(list) :
1296 new UnmodifiableList<>(list));
1297 }
1298
1299 /**
1300 * @serial include
1301 */
1302 static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1303 implements List<E> {
1304 private static final long serialVersionUID = -283967356065247728L;
1305 final List<? extends E> list;
1306
1307 UnmodifiableList(List<? extends E> list) {
1308 super(list);
1309 this.list = list;
1310 }
1311
1312 public boolean equals(Object o) {return o == this || list.equals(o);}
1313 public int hashCode() {return list.hashCode();}
1314
1315 public E get(int index) {return list.get(index);}
1316 public E set(int index, E element) {
1317 throw new UnsupportedOperationException();
1318 }
1319 public void add(int index, E element) {
1320 throw new UnsupportedOperationException();
1321 }
1322 public E remove(int index) {
1323 throw new UnsupportedOperationException();
1324 }
1325 public int indexOf(Object o) {return list.indexOf(o);}
1326 public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1327 public boolean addAll(int index, Collection<? extends E> c) {
1328 throw new UnsupportedOperationException();
1329 }
1330
1331 @Override
1332 public void replaceAll(UnaryOperator<E> operator) {
1333 throw new UnsupportedOperationException();
1334 }
1335 @Override
1336 public void sort(Comparator<? super E> c) {
1337 throw new UnsupportedOperationException();
1338 }
1339
1340 public ListIterator<E> listIterator() {return listIterator(0);}
1341
1342 public ListIterator<E> listIterator(final int index) {
1343 return new ListIterator<E>() {
1344 private final ListIterator<? extends E> i
1345 = list.listIterator(index);
1346
1347 public boolean hasNext() {return i.hasNext();}
1348 public E next() {return i.next();}
1349 public boolean hasPrevious() {return i.hasPrevious();}
1350 public E previous() {return i.previous();}
1351 public int nextIndex() {return i.nextIndex();}
1352 public int previousIndex() {return i.previousIndex();}
1353
1354 public void remove() {
1355 throw new UnsupportedOperationException();
1356 }
1357 public void set(E e) {
1358 throw new UnsupportedOperationException();
1359 }
1360 public void add(E e) {
1361 throw new UnsupportedOperationException();
1362 }
1363
1364 @Override
1365 public void forEachRemaining(Consumer<? super E> action) {
1366 i.forEachRemaining(action);
1367 }
1368 };
1369 }
1370
1371 public List<E> subList(int fromIndex, int toIndex) {
1372 return new UnmodifiableList<>(list.subList(fromIndex, toIndex));
1373 }
1374
1375 /**
1376 * UnmodifiableRandomAccessList instances are serialized as
1377 * UnmodifiableList instances to allow them to be deserialized
1378 * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
1379 * This method inverts the transformation. As a beneficial
1380 * side-effect, it also grafts the RandomAccess marker onto
1381 * UnmodifiableList instances that were serialized in pre-1.4 JREs.
1382 *
1383 * Note: Unfortunately, UnmodifiableRandomAccessList instances
1384 * serialized in 1.4.1 and deserialized in 1.4 will become
1385 * UnmodifiableList instances, as this method was missing in 1.4.
1386 */
1387 private Object readResolve() {
1388 return (list instanceof RandomAccess
1389 ? new UnmodifiableRandomAccessList<>(list)
1390 : this);
1391 }
1392 }
1393
1394 /**
1395 * @serial include
1396 */
1397 static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E>
1398 implements RandomAccess
1399 {
1400 UnmodifiableRandomAccessList(List<? extends E> list) {
1401 super(list);
1402 }
1403
1404 public List<E> subList(int fromIndex, int toIndex) {
1405 return new UnmodifiableRandomAccessList<>(
1406 list.subList(fromIndex, toIndex));
1407 }
1408
1409 private static final long serialVersionUID = -2542308836966382001L;
1410
1411 /**
1412 * Allows instances to be deserialized in pre-1.4 JREs (which do
1413 * not have UnmodifiableRandomAccessList). UnmodifiableList has
1414 * a readResolve method that inverts this transformation upon
1415 * deserialization.
1416 */
1417 private Object writeReplace() {
1418 return new UnmodifiableList<>(list);
1419 }
1420 }
1421
1422 /**
1423 * Returns an unmodifiable view of the specified map. This method
1424 * allows modules to provide users with "read-only" access to internal
1425 * maps. Query operations on the returned map "read through"
1426 * to the specified map, and attempts to modify the returned
1427 * map, whether direct or via its collection views, result in an
1428 * <tt>UnsupportedOperationException</tt>.<p>
1429 *
1430 * The returned map will be serializable if the specified map
1431 * is serializable.
1432 *
1433 * @param m the map for which an unmodifiable view is to be returned.
1434 * @return an unmodifiable view of the specified map.
1435 */
1436 public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
1437 return new UnmodifiableMap<>(m);
1438 }
1439
1440 /**
1441 * @serial include
1442 */
1443 private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
1444 private static final long serialVersionUID = -1034234728574286014L;
1445
1446 private final Map<? extends K, ? extends V> m;
1447
1448 UnmodifiableMap(Map<? extends K, ? extends V> m) {
1449 if (m==null)
1450 throw new NullPointerException();
1451 this.m = m;
1452 }
1453
1454 public int size() {return m.size();}
1455 public boolean isEmpty() {return m.isEmpty();}
1456 public boolean containsKey(Object key) {return m.containsKey(key);}
1457 public boolean containsValue(Object val) {return m.containsValue(val);}
1458 public V get(Object key) {return m.get(key);}
1459
1460 public V put(K key, V value) {
1461 throw new UnsupportedOperationException();
1462 }
1463 public V remove(Object key) {
1464 throw new UnsupportedOperationException();
1465 }
1466 public void putAll(Map<? extends K, ? extends V> m) {
1467 throw new UnsupportedOperationException();
1468 }
1469 public void clear() {
1470 throw new UnsupportedOperationException();
1471 }
1472
1473 private transient Set<K> keySet = null;
1474 private transient Set<Map.Entry<K,V>> entrySet = null;
1475 private transient Collection<V> values = null;
1476
1477 public Set<K> keySet() {
1478 if (keySet==null)
1479 keySet = unmodifiableSet(m.keySet());
1480 return keySet;
1481 }
1482
1483 public Set<Map.Entry<K,V>> entrySet() {
1484 if (entrySet==null)
1485 entrySet = new UnmodifiableEntrySet<>(m.entrySet());
1486 return entrySet;
1487 }
1488
1489 public Collection<V> values() {
1490 if (values==null)
1491 values = unmodifiableCollection(m.values());
1492 return values;
1493 }
1494
1495 public boolean equals(Object o) {return o == this || m.equals(o);}
1496 public int hashCode() {return m.hashCode();}
1497 public String toString() {return m.toString();}
1498
1499 // Override default methods in Map
1500 @Override
1501 @SuppressWarnings("unchecked")
1502 public V getOrDefault(Object k, V defaultValue) {
1503 // Safe cast as we don't change the value
1504 return ((Map<K, V>)m).getOrDefault(k, defaultValue);
1505 }
1506
1507 @Override
1508 public void forEach(BiConsumer<? super K, ? super V> action) {
1509 m.forEach(action);
1510 }
1511
1512 @Override
1513 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1514 throw new UnsupportedOperationException();
1515 }
1516
1517 @Override
1518 public V putIfAbsent(K key, V value) {
1519 throw new UnsupportedOperationException();
1520 }
1521
1522 @Override
1523 public boolean remove(Object key, Object value) {
1524 throw new UnsupportedOperationException();
1525 }
1526
1527 @Override
1528 public boolean replace(K key, V oldValue, V newValue) {
1529 throw new UnsupportedOperationException();
1530 }
1531
1532 @Override
1533 public V replace(K key, V value) {
1534 throw new UnsupportedOperationException();
1535 }
1536
1537 @Override
1538 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1539 throw new UnsupportedOperationException();
1540 }
1541
1542 @Override
1543 public V computeIfPresent(K key,
1544 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1545 throw new UnsupportedOperationException();
1546 }
1547
1548 @Override
1549 public V compute(K key,
1550 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1551 throw new UnsupportedOperationException();
1552 }
1553
1554 @Override
1555 public V merge(K key, V value,
1556 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1557 throw new UnsupportedOperationException();
1558 }
1559
1560 /**
1561 * We need this class in addition to UnmodifiableSet as
1562 * Map.Entries themselves permit modification of the backing Map
1563 * via their setValue operation. This class is subtle: there are
1564 * many possible attacks that must be thwarted.
1565 *
1566 * @serial include
1567 */
1568 static class UnmodifiableEntrySet<K,V>
1569 extends UnmodifiableSet<Map.Entry<K,V>> {
1570 private static final long serialVersionUID = 7854390611657943733L;
1571
1572 @SuppressWarnings({"unchecked", "rawtypes"})
1573 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1574 // Need to cast to raw in order to work around a limitation in the type system
1575 super((Set)s);
1576 }
1577 public Iterator<Map.Entry<K,V>> iterator() {
1578 return new Iterator<Map.Entry<K,V>>() {
1579 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1580
1581 public boolean hasNext() {
1582 return i.hasNext();
1583 }
1584 public Map.Entry<K,V> next() {
1585 return new UnmodifiableEntry<>(i.next());
1586 }
1587 public void remove() {
1588 throw new UnsupportedOperationException();
1589 }
1590 };
1591 }
1592
1593 @SuppressWarnings("unchecked")
1594 public Object[] toArray() {
1595 Object[] a = c.toArray();
1596 for (int i=0; i<a.length; i++)
1597 a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]);
1598 return a;
1599 }
1600
1601 @SuppressWarnings("unchecked")
1602 public <T> T[] toArray(T[] a) {
1603 // We don't pass a to c.toArray, to avoid window of
1604 // vulnerability wherein an unscrupulous multithreaded client
1605 // could get his hands on raw (unwrapped) Entries from c.
1606 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1607
1608 for (int i=0; i<arr.length; i++)
1609 arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]);
1610
1611 if (arr.length > a.length)
1612 return (T[])arr;
1613
1614 System.arraycopy(arr, 0, a, 0, arr.length);
1615 if (a.length > arr.length)
1616 a[arr.length] = null;
1617 return a;
1618 }
1619
1620 /**
1621 * This method is overridden to protect the backing set against
1622 * an object with a nefarious equals function that senses
1623 * that the equality-candidate is Map.Entry and calls its
1624 * setValue method.
1625 */
1626 public boolean contains(Object o) {
1627 if (!(o instanceof Map.Entry))
1628 return false;
1629 return c.contains(
1630 new UnmodifiableEntry<>((Map.Entry<?,?>) o));
1631 }
1632
1633 /**
1634 * The next two methods are overridden to protect against
1635 * an unscrupulous List whose contains(Object o) method senses
1636 * when o is a Map.Entry, and calls o.setValue.
1637 */
1638 public boolean containsAll(Collection<?> coll) {
1639 for (Object e : coll) {
1640 if (!contains(e)) // Invokes safe contains() above
1641 return false;
1642 }
1643 return true;
1644 }
1645 public boolean equals(Object o) {
1646 if (o == this)
1647 return true;
1648
1649 if (!(o instanceof Set))
1650 return false;
1651 Set<?> s = (Set<?>) o;
1652 if (s.size() != c.size())
1653 return false;
1654 return containsAll(s); // Invokes safe containsAll() above
1655 }
1656
1657 /**
1658 * This "wrapper class" serves two purposes: it prevents
1659 * the client from modifying the backing Map, by short-circuiting
1660 * the setValue method, and it protects the backing Map against
1661 * an ill-behaved Map.Entry that attempts to modify another
1662 * Map Entry when asked to perform an equality check.
1663 */
1664 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
1665 private Map.Entry<? extends K, ? extends V> e;
1666
1667 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1668
1669 public K getKey() {return e.getKey();}
1670 public V getValue() {return e.getValue();}
1671 public V setValue(V value) {
1672 throw new UnsupportedOperationException();
1673 }
1674 public int hashCode() {return e.hashCode();}
1675 public boolean equals(Object o) {
1676 if (this == o)
1677 return true;
1678 if (!(o instanceof Map.Entry))
1679 return false;
1680 Map.Entry<?,?> t = (Map.Entry<?,?>)o;
1681 return eq(e.getKey(), t.getKey()) &&
1682 eq(e.getValue(), t.getValue());
1683 }
1684 public String toString() {return e.toString();}
1685 }
1686 }
1687 }
1688
1689 /**
1690 * Returns an unmodifiable view of the specified sorted map. This method
1691 * allows modules to provide users with "read-only" access to internal
1692 * sorted maps. Query operations on the returned sorted map "read through"
1693 * to the specified sorted map. Attempts to modify the returned
1694 * sorted map, whether direct, via its collection views, or via its
1695 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1696 * an <tt>UnsupportedOperationException</tt>.<p>
1697 *
1698 * The returned sorted map will be serializable if the specified sorted map
1699 * is serializable.
1700 *
1701 * @param m the sorted map for which an unmodifiable view is to be
1702 * returned.
1703 * @return an unmodifiable view of the specified sorted map.
1704 */
1705 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1706 return new UnmodifiableSortedMap<>(m);
1707 }
1708
1709 /**
1710 * @serial include
1711 */
1712 static class UnmodifiableSortedMap<K,V>
1713 extends UnmodifiableMap<K,V>
1714 implements SortedMap<K,V>, Serializable {
1715 private static final long serialVersionUID = -8806743815996713206L;
1716
1717 private final SortedMap<K, ? extends V> sm;
1718
1719 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1720
1721 public Comparator<? super K> comparator() {return sm.comparator();}
1722
1723 public SortedMap<K,V> subMap(K fromKey, K toKey) {
1724 return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey));
1725 }
1726 public SortedMap<K,V> headMap(K toKey) {
1727 return new UnmodifiableSortedMap<>(sm.headMap(toKey));
1728 }
1729 public SortedMap<K,V> tailMap(K fromKey) {
1730 return new UnmodifiableSortedMap<>(sm.tailMap(fromKey));
1731 }
1732
1733 public K firstKey() {return sm.firstKey();}
1734 public K lastKey() {return sm.lastKey();}
1735 }
1736
1737 /**
1738 * Returns an unmodifiable view of the specified navigable map. This method
1739 * allows modules to provide users with "read-only" access to internal
1740 * navigable maps. Query operations on the returned navigable map "read
1741 * through" to the specified navigable map. Attempts to modify the returned
1742 * navigable map, whether direct, via its collection views, or via its
1743 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1744 * an <tt>UnsupportedOperationException</tt>.<p>
1745 *
1746 * The returned navigable map will be serializable if the specified
1747 * navigable map is serializable.
1748 *
1749 * @param m the navigable map for which an unmodifiable view is to be
1750 * returned
1751 * @return an unmodifiable view of the specified navigable map
1752 * @since 1.8
1753 */
1754 public static <K,V> SortedMap<K,V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m) {
1755 return new UnmodifiableNavigableMap<>(m);
1756 }
1757
1758 /**
1759 * @serial include
1760 */
1761 static class UnmodifiableNavigableMap<K,V>
1762 extends UnmodifiableSortedMap<K,V>
1763 implements NavigableMap<K,V>, Serializable {
1764 // private static final long serialVersionUID = -8806743815996713206L;
1765
1766 private final NavigableMap<K, ? extends V> nm;
1767
1768 UnmodifiableNavigableMap(NavigableMap<K, ? extends V> m) {super(m); nm = m;}
1769
1770 @Override
1771 public Entry<K, V> lowerEntry(K key) {
1772 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.lowerEntry(key));
1773 }
1774
1775 @Override
1776 public K lowerKey(K key) {
1777 return nm.lowerKey(key);
1778 }
1779
1780 @Override
1781 public Entry<K, V> floorEntry(K key) {
1782 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.floorEntry(key));
1783 }
1784
1785 @Override
1786 public K floorKey(K key) {
1787 return nm.floorKey(key);
1788 }
1789
1790 @Override
1791 public Entry<K, V> ceilingEntry(K key) {
1792 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.ceilingEntry(key));
1793 }
1794
1795 @Override
1796 public K ceilingKey(K key) {
1797 return nm.ceilingKey(key);
1798 }
1799
1800 @Override
1801 public Entry<K, V> higherEntry(K key) {
1802 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.higherEntry(key));
1803 }
1804
1805 @Override
1806 public K higherKey(K key) {
1807 return nm.higherKey(key);
1808 }
1809
1810 @Override
1811 public Entry<K, V> firstEntry() {
1812 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.firstEntry());
1813 }
1814
1815 @Override
1816 public Entry<K, V> lastEntry() {
1817 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.lastEntry());
1818 }
1819
1820 @Override
1821 public Entry<K, V> pollFirstEntry() {
1822 Entry<K,V> entry = (Entry<K,V>) nm.pollFirstEntry();
1823 return (null == entry) ? null : new UnmodifiableEntrySet.UnmodifiableEntry(entry);
1824 }
1825
1826 @Override
1827 public Entry<K, V> pollLastEntry() {
1828 Entry<K,V> entry = (Entry<K,V>) nm.pollLastEntry();
1829 return (null == entry) ? null : new UnmodifiableEntrySet.UnmodifiableEntry(entry);
1830 }
1831
1832 @Override
1833 public NavigableMap<K, V> descendingMap() {
1834 return (NavigableMap<K,V>) unmodifiableNavigableMap(nm.descendingMap());
1835 }
1836
1837 @Override
1838 public NavigableSet<K> navigableKeySet() {
1839 return unmodifiableNavigableSet(nm.navigableKeySet());
1840 }
1841
1842 @Override
1843 public NavigableSet<K> descendingKeySet() {
1844 return unmodifiableNavigableSet(nm.descendingKeySet());
1845 }
1846
1847 @Override
1848 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1849 return (NavigableMap<K,V>) unmodifiableNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive));
1850 }
1851
1852 @Override
1853 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
1854 return (NavigableMap<K,V>) unmodifiableNavigableMap(nm.headMap(toKey, inclusive));
1855 }
1856
1857 @Override
1858 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
1859 return (NavigableMap<K,V>) unmodifiableNavigableMap(nm.tailMap(fromKey, inclusive));
1860 }
1861 }
1862
1863 // Synch Wrappers
1864
1865 /**
1866 * Returns a synchronized (thread-safe) collection backed by the specified
1867 * collection. In order to guarantee serial access, it is critical that
1868 * <strong>all</strong> access to the backing collection is accomplished
1869 * through the returned collection.<p>
1870 *
1871 * It is imperative that the user manually synchronize on the returned
1872 * collection when traversing it via {@link Iterator} or
1873 * {@link Spliterator}:
1874 * <pre>
1875 * Collection c = Collections.synchronizedCollection(myCollection);
1876 * ...
1877 * synchronized (c) {
1878 * Iterator i = c.iterator(); // Must be in the synchronized block
1879 * while (i.hasNext())
1880 * foo(i.next());
1881 * }
1882 * </pre>
1883 * Failure to follow this advice may result in non-deterministic behavior.
1884 *
1885 * <p>The returned collection does <i>not</i> pass the {@code hashCode}
1886 * and {@code equals} operations through to the backing collection, but
1887 * relies on {@code Object}'s equals and hashCode methods. This is
1888 * necessary to preserve the contracts of these operations in the case
1889 * that the backing collection is a set or a list.<p>
1890 *
1891 * The returned collection will be serializable if the specified collection
1892 * is serializable.
1893 *
1894 * @param c the collection to be "wrapped" in a synchronized collection.
1895 * @return a synchronized view of the specified collection.
1896 */
1897 public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1898 return new SynchronizedCollection<>(c);
1899 }
1900
1901 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1902 return new SynchronizedCollection<>(c, mutex);
1903 }
1904
1905 /**
1906 * @serial include
1907 */
1908 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1909 private static final long serialVersionUID = 3053995032091335093L;
1910
1911 final Collection<E> c; // Backing Collection
1912 final Object mutex; // Object on which to synchronize
1913
1914 SynchronizedCollection(Collection<E> c) {
1915 if (c==null)
1916 throw new NullPointerException();
1917 this.c = c;
1918 mutex = this;
1919 }
1920 SynchronizedCollection(Collection<E> c, Object mutex) {
1921 this.c = c;
1922 this.mutex = mutex;
1923 }
1924
1925 public int size() {
1926 synchronized (mutex) {return c.size();}
1927 }
1928 public boolean isEmpty() {
1929 synchronized (mutex) {return c.isEmpty();}
1930 }
1931 public boolean contains(Object o) {
1932 synchronized (mutex) {return c.contains(o);}
1933 }
1934 public Object[] toArray() {
1935 synchronized (mutex) {return c.toArray();}
1936 }
1937 public <T> T[] toArray(T[] a) {
1938 synchronized (mutex) {return c.toArray(a);}
1939 }
1940
1941 public Iterator<E> iterator() {
1942 return c.iterator(); // Must be manually synched by user!
1943 }
1944
1945 public boolean add(E e) {
1946 synchronized (mutex) {return c.add(e);}
1947 }
1948 public boolean remove(Object o) {
1949 synchronized (mutex) {return c.remove(o);}
1950 }
1951
1952 public boolean containsAll(Collection<?> coll) {
1953 synchronized (mutex) {return c.containsAll(coll);}
1954 }
1955 public boolean addAll(Collection<? extends E> coll) {
1956 synchronized (mutex) {return c.addAll(coll);}
1957 }
1958 public boolean removeAll(Collection<?> coll) {
1959 synchronized (mutex) {return c.removeAll(coll);}
1960 }
1961 public boolean retainAll(Collection<?> coll) {
1962 synchronized (mutex) {return c.retainAll(coll);}
1963 }
1964 public void clear() {
1965 synchronized (mutex) {c.clear();}
1966 }
1967 public String toString() {
1968 synchronized (mutex) {return c.toString();}
1969 }
1970 // Override default methods in Collection
1971 @Override
1972 public void forEach(Consumer<? super E> consumer) {
1973 synchronized (mutex) {c.forEach(consumer);}
1974 }
1975 @Override
1976 public boolean removeIf(Predicate<? super E> filter) {
1977 synchronized (mutex) {return c.removeIf(filter);}
1978 }
1979 @Override
1980 public Spliterator<E> spliterator() {
1981 return c.spliterator(); // Must be manually synched by user!
1982 }
1983 private void writeObject(ObjectOutputStream s) throws IOException {
1984 synchronized (mutex) {s.defaultWriteObject();}
1985 }
1986 }
1987
1988 /**
1989 * Returns a synchronized (thread-safe) set backed by the specified
1990 * set. In order to guarantee serial access, it is critical that
1991 * <strong>all</strong> access to the backing set is accomplished
1992 * through the returned set.<p>
1993 *
1994 * It is imperative that the user manually synchronize on the returned
1995 * set when iterating over it:
1996 * <pre>
1997 * Set s = Collections.synchronizedSet(new HashSet());
1998 * ...
1999 * synchronized (s) {
2000 * Iterator i = s.iterator(); // Must be in the synchronized block
2001 * while (i.hasNext())
2002 * foo(i.next());
2003 * }
2004 * </pre>
2005 * Failure to follow this advice may result in non-deterministic behavior.
2006 *
2007 * <p>The returned set will be serializable if the specified set is
2008 * serializable.
2009 *
2010 * @param s the set to be "wrapped" in a synchronized set.
2011 * @return a synchronized view of the specified set.
2012 */
2013 public static <T> Set<T> synchronizedSet(Set<T> s) {
2014 return new SynchronizedSet<>(s);
2015 }
2016
2017 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
2018 return new SynchronizedSet<>(s, mutex);
2019 }
2020
2021 /**
2022 * @serial include
2023 */
2024 static class SynchronizedSet<E>
2025 extends SynchronizedCollection<E>
2026 implements Set<E> {
2027 private static final long serialVersionUID = 487447009682186044L;
2028
2029 SynchronizedSet(Set<E> s) {
2030 super(s);
2031 }
2032 SynchronizedSet(Set<E> s, Object mutex) {
2033 super(s, mutex);
2034 }
2035
2036 public boolean equals(Object o) {
2037 if (this == o)
2038 return true;
2039 synchronized (mutex) {return c.equals(o);}
2040 }
2041 public int hashCode() {
2042 synchronized (mutex) {return c.hashCode();}
2043 }
2044 }
2045
2046 /**
2047 * Returns a synchronized (thread-safe) sorted set backed by the specified
2048 * sorted set. In order to guarantee serial access, it is critical that
2049 * <strong>all</strong> access to the backing sorted set is accomplished
2050 * through the returned sorted set (or its views).<p>
2051 *
2052 * It is imperative that the user manually synchronize on the returned
2053 * sorted set when iterating over it or any of its <tt>subSet</tt>,
2054 * <tt>headSet</tt>, or <tt>tailSet</tt> views.
2055 * <pre>
2056 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
2057 * ...
2058 * synchronized (s) {
2059 * Iterator i = s.iterator(); // Must be in the synchronized block
2060 * while (i.hasNext())
2061 * foo(i.next());
2062 * }
2063 * </pre>
2064 * or:
2065 * <pre>
2066 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
2067 * SortedSet s2 = s.headSet(foo);
2068 * ...
2069 * synchronized (s) { // Note: s, not s2!!!
2070 * Iterator i = s2.iterator(); // Must be in the synchronized block
2071 * while (i.hasNext())
2072 * foo(i.next());
2073 * }
2074 * </pre>
2075 * Failure to follow this advice may result in non-deterministic behavior.
2076 *
2077 * <p>The returned sorted set will be serializable if the specified
2078 * sorted set is serializable.
2079 *
2080 * @param s the sorted set to be "wrapped" in a synchronized sorted set.
2081 * @return a synchronized view of the specified sorted set.
2082 */
2083 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
2084 return new SynchronizedSortedSet<>(s);
2085 }
2086
2087 /**
2088 * @serial include
2089 */
2090 static class SynchronizedSortedSet<E>
2091 extends SynchronizedSet<E>
2092 implements SortedSet<E>
2093 {
2094 private static final long serialVersionUID = 8695801310862127406L;
2095
2096 private final SortedSet<E> ss;
2097
2098 SynchronizedSortedSet(SortedSet<E> s) {
2099 super(s);
2100 ss = s;
2101 }
2102 SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
2103 super(s, mutex);
2104 ss = s;
2105 }
2106
2107 public Comparator<? super E> comparator() {
2108 synchronized (mutex) {return ss.comparator();}
2109 }
2110
2111 public SortedSet<E> subSet(E fromElement, E toElement) {
2112 synchronized (mutex) {
2113 return new SynchronizedSortedSet<>(
2114 ss.subSet(fromElement, toElement), mutex);
2115 }
2116 }
2117 public SortedSet<E> headSet(E toElement) {
2118 synchronized (mutex) {
2119 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex);
2120 }
2121 }
2122 public SortedSet<E> tailSet(E fromElement) {
2123 synchronized (mutex) {
2124 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex);
2125 }
2126 }
2127
2128 public E first() {
2129 synchronized (mutex) {return ss.first();}
2130 }
2131 public E last() {
2132 synchronized (mutex) {return ss.last();}
2133 }
2134 }
2135
2136 /**
2137 * Returns a synchronized (thread-safe) sorted set backed by the specified
2138 * navigable set. In order to guarantee serial access, it is critical that
2139 * <strong>all</strong> access to the backing sorted set is accomplished
2140 * through the returned navigable set (or its views).<p>
2141 *
2142 * It is imperative that the user manually synchronize on the returned
2143 * navigable set when iterating over it or any of its <tt>subSet</tt>,
2144 * <tt>headSet</tt>, or <tt>tailSet</tt> views.
2145 * <pre>
2146 * SortedSet s = Collections.synchronizedNavigableSet(new TreeSet());
2147 * ...
2148 * synchronized (s) {
2149 * Iterator i = s.iterator(); // Must be in the synchronized block
2150 * while (i.hasNext())
2151 * foo(i.next());
2152 * }
2153 * </pre>
2154 * or:
2155 * <pre>
2156 * SortedSet s = Collections.synchronizedNavigableSet(new TreeSet());
2157 * SortedSet s2 = s.headSet(foo);
2158 * ...
2159 * synchronized (s) { // Note: s, not s2!!!
2160 * Iterator i = s2.iterator(); // Must be in the synchronized block
2161 * while (i.hasNext())
2162 * foo(i.next());
2163 * }
2164 * </pre>
2165 * Failure to follow this advice may result in non-deterministic behavior.
2166 *
2167 * <p>The returned navigable set will be serializable if the specified
2168 * navigable set is serializable.
2169 *
2170 * @param s the navigable set to be "wrapped" in a synchronized navigable
2171 * set
2172 * @return a synchronized view of the specified navigable set
2173 * @since 1.8
2174 */
2175 public static <T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s) {
2176 return new SynchronizedNavigableSet<>(s);
2177 }
2178
2179 /**
2180 * @serial include
2181 */
2182 static class SynchronizedNavigableSet<E>
2183 extends SynchronizedSortedSet<E>
2184 implements NavigableSet<E>
2185 {
2186 //private static final long serialVersionUID = 8695801310862127406L;
2187
2188 private final NavigableSet<E> ns;
2189
2190 SynchronizedNavigableSet(NavigableSet<E> s) {
2191 super(s);
2192 ns = s;
2193 }
2194 SynchronizedNavigableSet(NavigableSet<E> s, Object mutex) {
2195 super(s, mutex);
2196 ns = s;
2197 }
2198 @Override public E lower(E e) { synchronized (mutex) {return ns.lower(e);} }
2199 @Override public E floor(E e) { synchronized (mutex) {return ns.floor(e);} }
2200 @Override public E ceiling(E e) { synchronized (mutex) {return ns.ceiling(e);} }
2201 @Override public E higher(E e) { synchronized (mutex) {return ns.higher(e);} }
2202 @Override public E pollFirst() { synchronized (mutex) {return ns.pollFirst();} }
2203 @Override public E pollLast() { synchronized (mutex) {return ns.pollLast();} }
2204 @Override
2205 public NavigableSet<E> descendingSet() {
2206 synchronized (mutex) {
2207 return new SynchronizedNavigableSet<>(ns.descendingSet(), mutex);
2208 }
2209 }
2210
2211 @Override
2212 public Iterator<E> descendingIterator() {
2213 synchronized (mutex) {
2214 return descendingSet().iterator();
2215 }
2216 }
2217
2218 @Override
2219 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
2220 synchronized (mutex) {
2221 return new SynchronizedNavigableSet<>(ns.subSet(fromElement, fromInclusive, toElement, toInclusive), mutex);
2222 }
2223 }
2224
2225 @Override
2226 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
2227 synchronized (mutex) {
2228 return new SynchronizedNavigableSet<>(ns.headSet(toElement, inclusive), mutex);
2229 }
2230 }
2231
2232 @Override
2233 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
2234 synchronized (mutex) {
2235 return new SynchronizedNavigableSet<>(ns.tailSet(fromElement, inclusive));
2236 }
2237 }
2238 }
2239
2240 /**
2241 * Returns a synchronized (thread-safe) list backed by the specified
2242 * list. In order to guarantee serial access, it is critical that
2243 * <strong>all</strong> access to the backing list is accomplished
2244 * through the returned list.<p>
2245 *
2246 * It is imperative that the user manually synchronize on the returned
2247 * list when iterating over it:
2248 * <pre>
2249 * List list = Collections.synchronizedList(new ArrayList());
2250 * ...
2251 * synchronized (list) {
2252 * Iterator i = list.iterator(); // Must be in synchronized block
2253 * while (i.hasNext())
2254 * foo(i.next());
2255 * }
2256 * </pre>
2257 * Failure to follow this advice may result in non-deterministic behavior.
2258 *
2259 * <p>The returned list will be serializable if the specified list is
2260 * serializable.
2261 *
2262 * @param list the list to be "wrapped" in a synchronized list.
2263 * @return a synchronized view of the specified list.
2264 */
2265 public static <T> List<T> synchronizedList(List<T> list) {
2266 return (list instanceof RandomAccess ?
2267 new SynchronizedRandomAccessList<>(list) :
2268 new SynchronizedList<>(list));
2269 }
2270
2271 static <T> List<T> synchronizedList(List<T> list, Object mutex) {
2272 return (list instanceof RandomAccess ?
2273 new SynchronizedRandomAccessList<>(list, mutex) :
2274 new SynchronizedList<>(list, mutex));
2275 }
2276
2277 /**
2278 * @serial include
2279 */
2280 static class SynchronizedList<E>
2281 extends SynchronizedCollection<E>
2282 implements List<E> {
2283 private static final long serialVersionUID = -7754090372962971524L;
2284
2285 final List<E> list;
2286
2287 SynchronizedList(List<E> list) {
2288 super(list);
2289 this.list = list;
2290 }
2291 SynchronizedList(List<E> list, Object mutex) {
2292 super(list, mutex);
2293 this.list = list;
2294 }
2295
2296 public boolean equals(Object o) {
2297 if (this == o)
2298 return true;
2299 synchronized (mutex) {return list.equals(o);}
2300 }
2301 public int hashCode() {
2302 synchronized (mutex) {return list.hashCode();}
2303 }
2304
2305 public E get(int index) {
2306 synchronized (mutex) {return list.get(index);}
2307 }
2308 public E set(int index, E element) {
2309 synchronized (mutex) {return list.set(index, element);}
2310 }
2311 public void add(int index, E element) {
2312 synchronized (mutex) {list.add(index, element);}
2313 }
2314 public E remove(int index) {
2315 synchronized (mutex) {return list.remove(index);}
2316 }
2317
2318 public int indexOf(Object o) {
2319 synchronized (mutex) {return list.indexOf(o);}
2320 }
2321 public int lastIndexOf(Object o) {
2322 synchronized (mutex) {return list.lastIndexOf(o);}
2323 }
2324
2325 public boolean addAll(int index, Collection<? extends E> c) {
2326 synchronized (mutex) {return list.addAll(index, c);}
2327 }
2328
2329 public ListIterator<E> listIterator() {
2330 return list.listIterator(); // Must be manually synched by user
2331 }
2332
2333 public ListIterator<E> listIterator(int index) {
2334 return list.listIterator(index); // Must be manually synched by user
2335 }
2336
2337 public List<E> subList(int fromIndex, int toIndex) {
2338 synchronized (mutex) {
2339 return new SynchronizedList<>(list.subList(fromIndex, toIndex),
2340 mutex);
2341 }
2342 }
2343
2344 @Override
2345 public void replaceAll(UnaryOperator<E> operator) {
2346 synchronized (mutex) {list.replaceAll(operator);}
2347 }
2348 @Override
2349 public void sort(Comparator<? super E> c) {
2350 synchronized (mutex) {list.sort(c);}
2351 }
2352
2353 /**
2354 * SynchronizedRandomAccessList instances are serialized as
2355 * SynchronizedList instances to allow them to be deserialized
2356 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
2357 * This method inverts the transformation. As a beneficial
2358 * side-effect, it also grafts the RandomAccess marker onto
2359 * SynchronizedList instances that were serialized in pre-1.4 JREs.
2360 *
2361 * Note: Unfortunately, SynchronizedRandomAccessList instances
2362 * serialized in 1.4.1 and deserialized in 1.4 will become
2363 * SynchronizedList instances, as this method was missing in 1.4.
2364 */
2365 private Object readResolve() {
2366 return (list instanceof RandomAccess
2367 ? new SynchronizedRandomAccessList<>(list)
2368 : this);
2369 }
2370 }
2371
2372 /**
2373 * @serial include
2374 */
2375 static class SynchronizedRandomAccessList<E>
2376 extends SynchronizedList<E>
2377 implements RandomAccess {
2378
2379 SynchronizedRandomAccessList(List<E> list) {
2380 super(list);
2381 }
2382
2383 SynchronizedRandomAccessList(List<E> list, Object mutex) {
2384 super(list, mutex);
2385 }
2386
2387 public List<E> subList(int fromIndex, int toIndex) {
2388 synchronized (mutex) {
2389 return new SynchronizedRandomAccessList<>(
2390 list.subList(fromIndex, toIndex), mutex);
2391 }
2392 }
2393
2394 private static final long serialVersionUID = 1530674583602358482L;
2395
2396 /**
2397 * Allows instances to be deserialized in pre-1.4 JREs (which do
2398 * not have SynchronizedRandomAccessList). SynchronizedList has
2399 * a readResolve method that inverts this transformation upon
2400 * deserialization.
2401 */
2402 private Object writeReplace() {
2403 return new SynchronizedList<>(list);
2404 }
2405 }
2406
2407 /**
2408 * Returns a synchronized (thread-safe) map backed by the specified
2409 * map. In order to guarantee serial access, it is critical that
2410 * <strong>all</strong> access to the backing map is accomplished
2411 * through the returned map.<p>
2412 *
2413 * It is imperative that the user manually synchronize on the returned
2414 * map when iterating over any of its collection views:
2415 * <pre>
2416 * Map m = Collections.synchronizedMap(new HashMap());
2417 * ...
2418 * Set s = m.keySet(); // Needn't be in synchronized block
2419 * ...
2420 * synchronized (m) { // Synchronizing on m, not s!
2421 * Iterator i = s.iterator(); // Must be in synchronized block
2422 * while (i.hasNext())
2423 * foo(i.next());
2424 * }
2425 * </pre>
2426 * Failure to follow this advice may result in non-deterministic behavior.
2427 *
2428 * <p>The returned map will be serializable if the specified map is
2429 * serializable.
2430 *
2431 * @param m the map to be "wrapped" in a synchronized map.
2432 * @return a synchronized view of the specified map.
2433 */
2434 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
2435 return new SynchronizedMap<>(m);
2436 }
2437
2438 /**
2439 * @serial include
2440 */
2441 private static class SynchronizedMap<K,V>
2442 implements Map<K,V>, Serializable {
2443 private static final long serialVersionUID = 1978198479659022715L;
2444
2445 private final Map<K,V> m; // Backing Map
2446 final Object mutex; // Object on which to synchronize
2447
2448 SynchronizedMap(Map<K,V> m) {
2449 if (m==null)
2450 throw new NullPointerException();
2451 this.m = m;
2452 mutex = this;
2453 }
2454
2455 SynchronizedMap(Map<K,V> m, Object mutex) {
2456 this.m = m;
2457 this.mutex = mutex;
2458 }
2459
2460 public int size() {
2461 synchronized (mutex) {return m.size();}
2462 }
2463 public boolean isEmpty() {
2464 synchronized (mutex) {return m.isEmpty();}
2465 }
2466 public boolean containsKey(Object key) {
2467 synchronized (mutex) {return m.containsKey(key);}
2468 }
2469 public boolean containsValue(Object value) {
2470 synchronized (mutex) {return m.containsValue(value);}
2471 }
2472 public V get(Object key) {
2473 synchronized (mutex) {return m.get(key);}
2474 }
2475
2476 public V put(K key, V value) {
2477 synchronized (mutex) {return m.put(key, value);}
2478 }
2479 public V remove(Object key) {
2480 synchronized (mutex) {return m.remove(key);}
2481 }
2482 public void putAll(Map<? extends K, ? extends V> map) {
2483 synchronized (mutex) {m.putAll(map);}
2484 }
2485 public void clear() {
2486 synchronized (mutex) {m.clear();}
2487 }
2488
2489 private transient Set<K> keySet = null;
2490 private transient Set<Map.Entry<K,V>> entrySet = null;
2491 private transient Collection<V> values = null;
2492
2493 public Set<K> keySet() {
2494 synchronized (mutex) {
2495 if (keySet==null)
2496 keySet = new SynchronizedSet<>(m.keySet(), mutex);
2497 return keySet;
2498 }
2499 }
2500
2501 public Set<Map.Entry<K,V>> entrySet() {
2502 synchronized (mutex) {
2503 if (entrySet==null)
2504 entrySet = new SynchronizedSet<>(m.entrySet(), mutex);
2505 return entrySet;
2506 }
2507 }
2508
2509 public Collection<V> values() {
2510 synchronized (mutex) {
2511 if (values==null)
2512 values = new SynchronizedCollection<>(m.values(), mutex);
2513 return values;
2514 }
2515 }
2516
2517 public boolean equals(Object o) {
2518 if (this == o)
2519 return true;
2520 synchronized (mutex) {return m.equals(o);}
2521 }
2522 public int hashCode() {
2523 synchronized (mutex) {return m.hashCode();}
2524 }
2525 public String toString() {
2526 synchronized (mutex) {return m.toString();}
2527 }
2528
2529 // Override default methods in Map
2530 @Override
2531 public V getOrDefault(Object k, V defaultValue) {
2532 synchronized (mutex) {return m.getOrDefault(k, defaultValue);}
2533 }
2534 @Override
2535 public void forEach(BiConsumer<? super K, ? super V> action) {
2536 synchronized (mutex) {m.forEach(action);}
2537 }
2538 @Override
2539 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
2540 synchronized (mutex) {m.replaceAll(function);}
2541 }
2542 @Override
2543 public V putIfAbsent(K key, V value) {
2544 synchronized (mutex) {return m.putIfAbsent(key, value);}
2545 }
2546 @Override
2547 public boolean remove(Object key, Object value) {
2548 synchronized (mutex) {return m.remove(key, value);}
2549 }
2550 @Override
2551 public boolean replace(K key, V oldValue, V newValue) {
2552 synchronized (mutex) {return m.replace(key, oldValue, newValue);}
2553 }
2554 @Override
2555 public V replace(K key, V value) {
2556 synchronized (mutex) {return m.replace(key, value);}
2557 }
2558 @Override
2559 public V computeIfAbsent(K key,
2560 Function<? super K, ? extends V> mappingFunction) {
2561 synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);}
2562 }
2563 @Override
2564 public V computeIfPresent(K key,
2565 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2566 synchronized (mutex) {return m.computeIfPresent(key, remappingFunction);}
2567 }
2568 @Override
2569 public V compute(K key,
2570 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2571 synchronized (mutex) {return m.compute(key, remappingFunction);}
2572 }
2573 @Override
2574 public V merge(K key, V value,
2575 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2576 synchronized (mutex) {return m.merge(key, value, remappingFunction);}
2577 }
2578
2579 private void writeObject(ObjectOutputStream s) throws IOException {
2580 synchronized (mutex) {s.defaultWriteObject();}
2581 }
2582 }
2583
2584 /**
2585 * Returns a synchronized (thread-safe) sorted map backed by the specified
2586 * sorted map. In order to guarantee serial access, it is critical that
2587 * <strong>all</strong> access to the backing sorted map is accomplished
2588 * through the returned sorted map (or its views).<p>
2589 *
2590 * It is imperative that the user manually synchronize on the returned
2591 * sorted map when iterating over any of its collection views, or the
2592 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2593 * <tt>tailMap</tt> views.
2594 * <pre>
2595 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2596 * ...
2597 * Set s = m.keySet(); // Needn't be in synchronized block
2598 * ...
2599 * synchronized (m) { // Synchronizing on m, not s!
2600 * Iterator i = s.iterator(); // Must be in synchronized block
2601 * while (i.hasNext())
2602 * foo(i.next());
2603 * }
2604 * </pre>
2605 * or:
2606 * <pre>
2607 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2608 * SortedMap m2 = m.subMap(foo, bar);
2609 * ...
2610 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2611 * ...
2612 * synchronized (m) { // Synchronizing on m, not m2 or s2!
2613 * Iterator i = s.iterator(); // Must be in synchronized block
2614 * while (i.hasNext())
2615 * foo(i.next());
2616 * }
2617 * </pre>
2618 * Failure to follow this advice may result in non-deterministic behavior.
2619 *
2620 * <p>The returned sorted map will be serializable if the specified
2621 * sorted map is serializable.
2622 *
2623 * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2624 * @return a synchronized view of the specified sorted map.
2625 */
2626 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2627 return new SynchronizedSortedMap<>(m);
2628 }
2629
2630
2631 /**
2632 * @serial include
2633 */
2634 static class SynchronizedSortedMap<K,V>
2635 extends SynchronizedMap<K,V>
2636 implements SortedMap<K,V>
2637 {
2638 private static final long serialVersionUID = -8798146769416483793L;
2639
2640 private final SortedMap<K,V> sm;
2641
2642 SynchronizedSortedMap(SortedMap<K,V> m) {
2643 super(m);
2644 sm = m;
2645 }
2646 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2647 super(m, mutex);
2648 sm = m;
2649 }
2650
2651 public Comparator<? super K> comparator() {
2652 synchronized (mutex) {return sm.comparator();}
2653 }
2654
2655 public SortedMap<K,V> subMap(K fromKey, K toKey) {
2656 synchronized (mutex) {
2657 return new SynchronizedSortedMap<>(
2658 sm.subMap(fromKey, toKey), mutex);
2659 }
2660 }
2661 public SortedMap<K,V> headMap(K toKey) {
2662 synchronized (mutex) {
2663 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex);
2664 }
2665 }
2666 public SortedMap<K,V> tailMap(K fromKey) {
2667 synchronized (mutex) {
2668 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex);
2669 }
2670 }
2671
2672 public K firstKey() {
2673 synchronized (mutex) {return sm.firstKey();}
2674 }
2675 public K lastKey() {
2676 synchronized (mutex) {return sm.lastKey();}
2677 }
2678 }
2679
2680 /**
2681 * Returns a synchronized (thread-safe) navigable map backed by the
2682 * specified navigable map. In order to guarantee serial access, it is
2683 * critical that <strong>all</strong> access to the backing navigable map is
2684 * accomplished through the returned navigable map (or its views).<p>
2685 *
2686 * It is imperative that the user manually synchronize on the returned
2687 * navigable map when iterating over any of its collection views, or the
2688 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2689 * <tt>tailMap</tt> views.
2690 * <pre>
2691 * SortedMap m = Collections.synchronizedNavigableMap(new TreeMap());
2692 * ...
2693 * Set s = m.keySet(); // Needn't be in synchronized block
2694 * ...
2695 * synchronized (m) { // Synchronizing on m, not s!
2696 * Iterator i = s.iterator(); // Must be in synchronized block
2697 * while (i.hasNext())
2698 * foo(i.next());
2699 * }
2700 * </pre>
2701 * or:
2702 * <pre>
2703 * SortedMap m = Collections.synchronizedNavigableMap(new TreeMap());
2704 * SortedMap m2 = m.subMap(foo, bar);
2705 * ...
2706 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2707 * ...
2708 * synchronized (m) { // Synchronizing on m, not m2 or s2!
2709 * Iterator i = s.iterator(); // Must be in synchronized block
2710 * while (i.hasNext())
2711 * foo(i.next());
2712 * }
2713 * </pre>
2714 * Failure to follow this advice may result in non-deterministic behavior.
2715 *
2716 * <p>The returned navigable map will be serializable if the specified
2717 * navigable map is serializable.
2718 *
2719 * @param m the navigable map to be "wrapped" in a synchronized navigable
2720 * map
2721 * @return a synchronized view of the specified navigable map.
2722 * @since 1.8
2723 */
2724 public static <K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m) {
2725 return new SynchronizedNavigableMap<>(m);
2726 }
2727
2728
2729 /**
2730 * @serial include
2731 */
2732 static class SynchronizedNavigableMap<K,V>
2733 extends SynchronizedSortedMap<K,V>
2734 implements NavigableMap<K,V>
2735 {
2736 private static final long serialVersionUID = -8798146769416483793L;
2737
2738 private final NavigableMap<K,V> nm;
2739
2740 SynchronizedNavigableMap(NavigableMap<K,V> m) {
2741 super(m);
2742 nm = m;
2743 }
2744 SynchronizedNavigableMap(NavigableMap<K,V> m, Object mutex) {
2745 super(m, mutex);
2746 nm = m;
2747 }
2748
2749 @Override
2750 public Entry<K, V> lowerEntry(K key) {
2751 synchronized (mutex) { return nm.lowerEntry(key); }
2752 }
2753
2754 @Override
2755 public K lowerKey(K key) {
2756 synchronized (mutex) { return nm.lowerKey(key); }
2757 }
2758
2759 @Override
2760 public Entry<K, V> floorEntry(K key) {
2761 synchronized (mutex) { return nm.floorEntry(key); }
2762 }
2763
2764 @Override
2765 public K floorKey(K key) {
2766 synchronized (mutex) { return nm.floorKey(key); }
2767 }
2768
2769 @Override
2770 public Entry<K, V> ceilingEntry(K key) {
2771 synchronized (mutex) { return nm.ceilingEntry(key); }
2772 }
2773
2774 @Override
2775 public K ceilingKey(K key) {
2776 synchronized (mutex) { return nm.ceilingKey(key); }
2777 }
2778
2779 @Override
2780 public Entry<K, V> higherEntry(K key) {
2781 synchronized (mutex) { return nm.higherEntry(key); }
2782 }
2783
2784 @Override
2785 public K higherKey(K key) {
2786 synchronized (mutex) { return nm.higherKey(key); }
2787 }
2788
2789 @Override
2790 public Entry<K, V> firstEntry() {
2791 synchronized (mutex) { return nm.firstEntry(); }
2792 }
2793
2794 @Override
2795 public Entry<K, V> lastEntry() {
2796 synchronized (mutex) { return nm.lastEntry(); }
2797 }
2798
2799 @Override
2800 public Entry<K, V> pollFirstEntry() {
2801 synchronized (mutex) {
2802 Entry<K,V> entry = (Entry<K,V>) nm.pollFirstEntry();
2803 return (null == entry) ? null : entry;
2804 }
2805 }
2806
2807 @Override
2808 public Entry<K, V> pollLastEntry() {
2809 synchronized (mutex) {
2810 Entry<K,V> entry = (Entry<K,V>) nm.pollLastEntry();
2811 return (null == entry) ? null : entry;
2812 }
2813 }
2814
2815 @Override
2816 public NavigableMap<K, V> descendingMap() {
2817 synchronized (mutex) {
2818 return (NavigableMap<K,V>) new SynchronizedNavigableMap(nm.descendingMap(), mutex);
2819 }
2820 }
2821
2822 @Override
2823 public NavigableSet<K> navigableKeySet() {
2824 synchronized (mutex) {
2825 return new SynchronizedNavigableSet(nm.navigableKeySet(), mutex);
2826 }
2827 }
2828
2829 @Override
2830 public NavigableSet<K> descendingKeySet() {
2831 synchronized (mutex) {
2832 return new SynchronizedNavigableSet(nm.descendingKeySet(), mutex);
2833 }
2834 }
2835
2836 @Override
2837 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
2838 synchronized (mutex) {
2839 return (NavigableMap<K,V>) new SynchronizedNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive), mutex);
2840 }
2841 }
2842
2843 @Override
2844 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
2845 synchronized (mutex) {
2846 return (NavigableMap<K,V>) new SynchronizedNavigableMap(nm.headMap(toKey, inclusive), mutex);
2847 }
2848 }
2849
2850 @Override
2851 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
2852 synchronized (mutex) {
2853 return (NavigableMap<K,V>) new SynchronizedNavigableMap(nm.tailMap(fromKey, inclusive), mutex);
2854 }
2855 }
2856 }
2857
2858 // Dynamically typesafe collection wrappers
2859
2860 /**
2861 * Returns a dynamically typesafe view of the specified collection.
2862 * Any attempt to insert an element of the wrong type will result in an
2863 * immediate {@link ClassCastException}. Assuming a collection
2864 * contains no incorrectly typed elements prior to the time a
2865 * dynamically typesafe view is generated, and that all subsequent
2866 * access to the collection takes place through the view, it is
2867 * <i>guaranteed</i> that the collection cannot contain an incorrectly
2868 * typed element.
2869 *
2870 * <p>The generics mechanism in the language provides compile-time
2871 * (static) type checking, but it is possible to defeat this mechanism
2872 * with unchecked casts. Usually this is not a problem, as the compiler
2873 * issues warnings on all such unchecked operations. There are, however,
2874 * times when static type checking alone is not sufficient. For example,
2875 * suppose a collection is passed to a third-party library and it is
2876 * imperative that the library code not corrupt the collection by
2877 * inserting an element of the wrong type.
2878 *
2879 * <p>Another use of dynamically typesafe views is debugging. Suppose a
2880 * program fails with a {@code ClassCastException}, indicating that an
2881 * incorrectly typed element was put into a parameterized collection.
2882 * Unfortunately, the exception can occur at any time after the erroneous
2883 * element is inserted, so it typically provides little or no information
2884 * as to the real source of the problem. If the problem is reproducible,
2885 * one can quickly determine its source by temporarily modifying the
2886 * program to wrap the collection with a dynamically typesafe view.
2887 * For example, this declaration:
2888 * <pre> {@code
2889 * Collection<String> c = new HashSet<String>();
2890 * }</pre>
2891 * may be replaced temporarily by this one:
2892 * <pre> {@code
2893 * Collection<String> c = Collections.checkedCollection(
2894 * new HashSet<String>(), String.class);
2895 * }</pre>
2896 * Running the program again will cause it to fail at the point where
2897 * an incorrectly typed element is inserted into the collection, clearly
2898 * identifying the source of the problem. Once the problem is fixed, the
2899 * modified declaration may be reverted back to the original.
2900 *
2901 * <p>The returned collection does <i>not</i> pass the hashCode and equals
2902 * operations through to the backing collection, but relies on
2903 * {@code Object}'s {@code equals} and {@code hashCode} methods. This
2904 * is necessary to preserve the contracts of these operations in the case
2905 * that the backing collection is a set or a list.
2906 *
2907 * <p>The returned collection will be serializable if the specified
2908 * collection is serializable.
2909 *
2910 * <p>Since {@code null} is considered to be a value of any reference
2911 * type, the returned collection permits insertion of null elements
2912 * whenever the backing collection does.
2913 *
2914 * @param c the collection for which a dynamically typesafe view is to be
2915 * returned
2916 * @param type the type of element that {@code c} is permitted to hold
2917 * @return a dynamically typesafe view of the specified collection
2918 * @since 1.5
2919 */
2920 public static <E> Collection<E> checkedCollection(Collection<E> c,
2921 Class<E> type) {
2922 return new CheckedCollection<>(c, type);
2923 }
2924
2925 @SuppressWarnings("unchecked")
2926 static <T> T[] zeroLengthArray(Class<T> type) {
2927 return (T[]) Array.newInstance(type, 0);
2928 }
2929
2930 /**
2931 * @serial include
2932 */
2933 static class CheckedCollection<E> implements Collection<E>, Serializable {
2934 private static final long serialVersionUID = 1578914078182001775L;
2935
2936 final Collection<E> c;
2937 final Class<E> type;
2938
2939 void typeCheck(Object o) {
2940 if (o != null && !type.isInstance(o))
2941 throw new ClassCastException(badElementMsg(o));
2942 }
2943
2944 private String badElementMsg(Object o) {
2945 return "Attempt to insert " + o.getClass() +
2946 " element into collection with element type " + type;
2947 }
2948
2949 CheckedCollection(Collection<E> c, Class<E> type) {
2950 if (c==null || type == null)
2951 throw new NullPointerException();
2952 this.c = c;
2953 this.type = type;
2954 }
2955
2956 public int size() { return c.size(); }
2957 public boolean isEmpty() { return c.isEmpty(); }
2958 public boolean contains(Object o) { return c.contains(o); }
2959 public Object[] toArray() { return c.toArray(); }
2960 public <T> T[] toArray(T[] a) { return c.toArray(a); }
2961 public String toString() { return c.toString(); }
2962 public boolean remove(Object o) { return c.remove(o); }
2963 public void clear() { c.clear(); }
2964
2965 public boolean containsAll(Collection<?> coll) {
2966 return c.containsAll(coll);
2967 }
2968 public boolean removeAll(Collection<?> coll) {
2969 return c.removeAll(coll);
2970 }
2971 public boolean retainAll(Collection<?> coll) {
2972 return c.retainAll(coll);
2973 }
2974
2975 public Iterator<E> iterator() {
2976 // JDK-6363904 - unwrapped iterator could be typecast to
2977 // ListIterator with unsafe set()
2978 final Iterator<E> it = c.iterator();
2979 return new Iterator<E>() {
2980 public boolean hasNext() { return it.hasNext(); }
2981 public E next() { return it.next(); }
2982 public void remove() { it.remove(); }};
2983 }
2984
2985 public boolean add(E e) {
2986 typeCheck(e);
2987 return c.add(e);
2988 }
2989
2990 private E[] zeroLengthElementArray = null; // Lazily initialized
2991
2992 private E[] zeroLengthElementArray() {
2993 return zeroLengthElementArray != null ? zeroLengthElementArray :
2994 (zeroLengthElementArray = zeroLengthArray(type));
2995 }
2996
2997 @SuppressWarnings("unchecked")
2998 Collection<E> checkedCopyOf(Collection<? extends E> coll) {
2999 Object[] a = null;
3000 try {
3001 E[] z = zeroLengthElementArray();
3002 a = coll.toArray(z);
3003 // Defend against coll violating the toArray contract
3004 if (a.getClass() != z.getClass())
3005 a = Arrays.copyOf(a, a.length, z.getClass());
3006 } catch (ArrayStoreException ignore) {
3007 // To get better and consistent diagnostics,
3008 // we call typeCheck explicitly on each element.
3009 // We call clone() to defend against coll retaining a
3010 // reference to the returned array and storing a bad
3011 // element into it after it has been type checked.
3012 a = coll.toArray().clone();
3013 for (Object o : a)
3014 typeCheck(o);
3015 }
3016 // A slight abuse of the type system, but safe here.
3017 return (Collection<E>) Arrays.asList(a);
3018 }
3019
3020 public boolean addAll(Collection<? extends E> coll) {
3021 // Doing things this way insulates us from concurrent changes
3022 // in the contents of coll and provides all-or-nothing
3023 // semantics (which we wouldn't get if we type-checked each
3024 // element as we added it)
3025 return c.addAll(checkedCopyOf(coll));
3026 }
3027
3028 // Override default methods in Collection
3029 @Override
3030 public void forEach(Consumer<? super E> action) {c.forEach(action);}
3031 @Override
3032 public boolean removeIf(Predicate<? super E> filter) {
3033 return c.removeIf(filter);
3034 }
3035 @Override
3036 public Spliterator<E> spliterator() {return c.spliterator();}
3037 }
3038
3039 /**
3040 * Returns a dynamically typesafe view of the specified queue.
3041 * Any attempt to insert an element of the wrong type will result in
3042 * an immediate {@link ClassCastException}. Assuming a queue contains
3043 * no incorrectly typed elements prior to the time a dynamically typesafe
3044 * view is generated, and that all subsequent access to the queue
3045 * takes place through the view, it is <i>guaranteed</i> that the
3046 * queue cannot contain an incorrectly typed element.
3047 *
3048 * <p>A discussion of the use of dynamically typesafe views may be
3049 * found in the documentation for the {@link #checkedCollection
3050 * checkedCollection} method.
3051 *
3052 * <p>The returned queue will be serializable if the specified queue
3053 * is serializable.
3054 *
3055 * <p>Since {@code null} is considered to be a value of any reference
3056 * type, the returned queue permits insertion of {@code null} elements
3057 * whenever the backing queue does.
3058 *
3059 * @param queue the queue for which a dynamically typesafe view is to be
3060 * returned
3061 * @param type the type of element that {@code queue} is permitted to hold
3062 * @return a dynamically typesafe view of the specified queue
3063 * @since 1.8
3064 */
3065 public static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type) {
3066 return new CheckedQueue<>(queue, type);
3067 }
3068
3069 /**
3070 * @serial include
3071 */
3072 static class CheckedQueue<E>
3073 extends CheckedCollection<E>
3074 implements Queue<E>, Serializable
3075 {
3076 private static final long serialVersionUID = 1433151992604707767L;
3077 final Queue<E> queue;
3078
3079 CheckedQueue(Queue<E> queue, Class<E> elementType) {
3080 super(queue, elementType);
3081 this.queue = queue;
3082 }
3083
3084 public E element() {return queue.element();}
3085 public boolean equals(Object o) {return o == this || c.equals(o);}
3086 public int hashCode() {return c.hashCode();}
3087 public E peek() {return queue.peek();}
3088 public E poll() {return queue.poll();}
3089 public E remove() {return queue.remove();}
3090
3091 public boolean offer(E e) {
3092 typeCheck(e);
3093 return add(e);
3094 }
3095 }
3096
3097 /**
3098 * Returns a dynamically typesafe view of the specified set.
3099 * Any attempt to insert an element of the wrong type will result in
3100 * an immediate {@link ClassCastException}. Assuming a set contains
3101 * no incorrectly typed elements prior to the time a dynamically typesafe
3102 * view is generated, and that all subsequent access to the set
3103 * takes place through the view, it is <i>guaranteed</i> that the
3104 * set cannot contain an incorrectly typed element.
3105 *
3106 * <p>A discussion of the use of dynamically typesafe views may be
3107 * found in the documentation for the {@link #checkedCollection
3108 * checkedCollection} method.
3109 *
3110 * <p>The returned set will be serializable if the specified set is
3111 * serializable.
3112 *
3113 * <p>Since {@code null} is considered to be a value of any reference
3114 * type, the returned set permits insertion of null elements whenever
3115 * the backing set does.
3116 *
3117 * @param s the set for which a dynamically typesafe view is to be
3118 * returned
3119 * @param type the type of element that {@code s} is permitted to hold
3120 * @return a dynamically typesafe view of the specified set
3121 * @since 1.5
3122 */
3123 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
3124 return new CheckedSet<>(s, type);
3125 }
3126
3127 /**
3128 * @serial include
3129 */
3130 static class CheckedSet<E> extends CheckedCollection<E>
3131 implements Set<E>, Serializable
3132 {
3133 private static final long serialVersionUID = 4694047833775013803L;
3134
3135 CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
3136
3137 public boolean equals(Object o) { return o == this || c.equals(o); }
3138 public int hashCode() { return c.hashCode(); }
3139 }
3140
3141 /**
3142 * Returns a dynamically typesafe view of the specified sorted set.
3143 * Any attempt to insert an element of the wrong type will result in an
3144 * immediate {@link ClassCastException}. Assuming a sorted set
3145 * contains no incorrectly typed elements prior to the time a
3146 * dynamically typesafe view is generated, and that all subsequent
3147 * access to the sorted set takes place through the view, it is
3148 * <i>guaranteed</i> that the sorted set cannot contain an incorrectly
3149 * typed element.
3150 *
3151 * <p>A discussion of the use of dynamically typesafe views may be
3152 * found in the documentation for the {@link #checkedCollection
3153 * checkedCollection} method.
3154 *
3155 * <p>The returned sorted set will be serializable if the specified sorted
3156 * set is serializable.
3157 *
3158 * <p>Since {@code null} is considered to be a value of any reference
3159 * type, the returned sorted set permits insertion of null elements
3160 * whenever the backing sorted set does.
3161 *
3162 * @param s the sorted set for which a dynamically typesafe view is to be
3163 * returned
3164 * @param type the type of element that {@code s} is permitted to hold
3165 * @return a dynamically typesafe view of the specified sorted set
3166 * @since 1.5
3167 */
3168 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
3169 Class<E> type) {
3170 return new CheckedSortedSet<>(s, type);
3171 }
3172
3173 /**
3174 * @serial include
3175 */
3176 static class CheckedSortedSet<E> extends CheckedSet<E>
3177 implements SortedSet<E>, Serializable
3178 {
3179 private static final long serialVersionUID = 1599911165492914959L;
3180 private final SortedSet<E> ss;
3181
3182 CheckedSortedSet(SortedSet<E> s, Class<E> type) {
3183 super(s, type);
3184 ss = s;
3185 }
3186
3187 public Comparator<? super E> comparator() { return ss.comparator(); }
3188 public E first() { return ss.first(); }
3189 public E last() { return ss.last(); }
3190
3191 public SortedSet<E> subSet(E fromElement, E toElement) {
3192 return checkedSortedSet(ss.subSet(fromElement,toElement), type);
3193 }
3194 public SortedSet<E> headSet(E toElement) {
3195 return checkedSortedSet(ss.headSet(toElement), type);
3196 }
3197 public SortedSet<E> tailSet(E fromElement) {
3198 return checkedSortedSet(ss.tailSet(fromElement), type);
3199 }
3200 }
3201
3202 /**
3203 * Returns a dynamically typesafe view of the specified navigable set.
3204 * Any attempt to insert an element of the wrong type will result in an
3205 * immediate {@link ClassCastException}. Assuming a navigable set
3206 * contains no incorrectly typed elements prior to the time a
3207 * dynamically typesafe view is generated, and that all subsequent
3208 * access to the navigable set takes place through the view, it is
3209 * <em>guaranteed</em> that the navigable set cannot contain an incorrectly
3210 * typed element.
3211 *
3212 * <p>A discussion of the use of dynamically typesafe views may be
3213 * found in the documentation for the {@link #checkedCollection
3214 * checkedCollection} method.
3215 *
3216 * <p>The returned navigable set will be serializable if the specified
3217 * navigable set is serializable.
3218 *
3219 * <p>Since {@code null} is considered to be a value of any reference
3220 * type, the returned navigable set permits insertion of null elements
3221 * whenever the backing sorted set does.
3222 *
3223 * @param s the navigable set for which a dynamically typesafe view is to be
3224 * returned
3225 * @param type the type of element that {@code s} is permitted to hold
3226 * @return a dynamically typesafe view of the specified navigable set
3227 * @since 1.8
3228 */
3229 public static <E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s,
3230 Class<E> type) {
3231 return new CheckedNavigableSet<>(s, type);
3232 }
3233
3234 /**
3235 * @serial include
3236 */
3237 static class CheckedNavigableSet<E> extends CheckedSortedSet<E>
3238 implements NavigableSet<E>, Serializable
3239 {
3240 //private static final long serialVersionUID = 1599911165492914959L;
3241 private final NavigableSet<E> ns;
3242
3243 CheckedNavigableSet(NavigableSet<E> s, Class<E> type) {
3244 super(s, type);
3245 ns = s;
3246 }
3247
3248 @Override
3249 public E lower(E e) {
3250 return ns.lower(e);
3251 }
3252
3253 @Override
3254 public E floor(E e) {
3255 return ns.floor(e);
3256 }
3257
3258 @Override
3259 public E ceiling(E e) {
3260 return ns.ceiling(e);
3261 }
3262
3263 @Override
3264 public E higher(E e) {
3265 return ns.higher(e);
3266 }
3267
3268 @Override
3269 public E pollFirst() {
3270 return ns.pollFirst();
3271 }
3272
3273 @Override
3274 public E pollLast() {
3275 return ns.pollLast();
3276 }
3277
3278 @Override
3279 public NavigableSet<E> descendingSet() {
3280 return checkedNavigableSet(ns.descendingSet(), type);
3281 }
3282
3283 @Override
3284 public Iterator<E> descendingIterator() {
3285 return checkedNavigableSet(ns.descendingSet(), type).iterator();
3286 }
3287
3288 @Override
3289 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
3290 return checkedNavigableSet(ns.subSet(fromElement, fromInclusive, toElement, toInclusive), type);
3291 }
3292
3293 @Override
3294 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
3295 return checkedNavigableSet(ns.headSet(toElement, inclusive), type);
3296 }
3297
3298 @Override
3299 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
3300 return checkedNavigableSet(ns.tailSet(fromElement, inclusive), type);
3301 }
3302 }
3303
3304 /**
3305 * Returns a dynamically typesafe view of the specified list.
3306 * Any attempt to insert an element of the wrong type will result in
3307 * an immediate {@link ClassCastException}. Assuming a list contains
3308 * no incorrectly typed elements prior to the time a dynamically typesafe
3309 * view is generated, and that all subsequent access to the list
3310 * takes place through the view, it is <i>guaranteed</i> that the
3311 * list cannot contain an incorrectly typed element.
3312 *
3313 * <p>A discussion of the use of dynamically typesafe views may be
3314 * found in the documentation for the {@link #checkedCollection
3315 * checkedCollection} method.
3316 *
3317 * <p>The returned list will be serializable if the specified list
3318 * is serializable.
3319 *
3320 * <p>Since {@code null} is considered to be a value of any reference
3321 * type, the returned list permits insertion of null elements whenever
3322 * the backing list does.
3323 *
3324 * @param list the list for which a dynamically typesafe view is to be
3325 * returned
3326 * @param type the type of element that {@code list} is permitted to hold
3327 * @return a dynamically typesafe view of the specified list
3328 * @since 1.5
3329 */
3330 public static <E> List<E> checkedList(List<E> list, Class<E> type) {
3331 return (list instanceof RandomAccess ?
3332 new CheckedRandomAccessList<>(list, type) :
3333 new CheckedList<>(list, type));
3334 }
3335
3336 /**
3337 * @serial include
3338 */
3339 static class CheckedList<E>
3340 extends CheckedCollection<E>
3341 implements List<E>
3342 {
3343 private static final long serialVersionUID = 65247728283967356L;
3344 final List<E> list;
3345
3346 CheckedList(List<E> list, Class<E> type) {
3347 super(list, type);
3348 this.list = list;
3349 }
3350
3351 public boolean equals(Object o) { return o == this || list.equals(o); }
3352 public int hashCode() { return list.hashCode(); }
3353 public E get(int index) { return list.get(index); }
3354 public E remove(int index) { return list.remove(index); }
3355 public int indexOf(Object o) { return list.indexOf(o); }
3356 public int lastIndexOf(Object o) { return list.lastIndexOf(o); }
3357
3358 public E set(int index, E element) {
3359 typeCheck(element);
3360 return list.set(index, element);
3361 }
3362
3363 public void add(int index, E element) {
3364 typeCheck(element);
3365 list.add(index, element);
3366 }
3367
3368 public boolean addAll(int index, Collection<? extends E> c) {
3369 return list.addAll(index, checkedCopyOf(c));
3370 }
3371 public ListIterator<E> listIterator() { return listIterator(0); }
3372
3373 public ListIterator<E> listIterator(final int index) {
3374 final ListIterator<E> i = list.listIterator(index);
3375
3376 return new ListIterator<E>() {
3377 public boolean hasNext() { return i.hasNext(); }
3378 public E next() { return i.next(); }
3379 public boolean hasPrevious() { return i.hasPrevious(); }
3380 public E previous() { return i.previous(); }
3381 public int nextIndex() { return i.nextIndex(); }
3382 public int previousIndex() { return i.previousIndex(); }
3383 public void remove() { i.remove(); }
3384
3385 public void set(E e) {
3386 typeCheck(e);
3387 i.set(e);
3388 }
3389
3390 public void add(E e) {
3391 typeCheck(e);
3392 i.add(e);
3393 }
3394
3395 @Override
3396 public void forEachRemaining(Consumer<? super E> action) {
3397 i.forEachRemaining(action);
3398 }
3399 };
3400 }
3401
3402 public List<E> subList(int fromIndex, int toIndex) {
3403 return new CheckedList<>(list.subList(fromIndex, toIndex), type);
3404 }
3405
3406 @Override
3407 public void replaceAll(UnaryOperator<E> operator) {
3408 list.replaceAll(operator);
3409 }
3410 @Override
3411 public void sort(Comparator<? super E> c) {
3412 list.sort(c);
3413 }
3414 }
3415
3416 /**
3417 * @serial include
3418 */
3419 static class CheckedRandomAccessList<E> extends CheckedList<E>
3420 implements RandomAccess
3421 {
3422 private static final long serialVersionUID = 1638200125423088369L;
3423
3424 CheckedRandomAccessList(List<E> list, Class<E> type) {
3425 super(list, type);
3426 }
3427
3428 public List<E> subList(int fromIndex, int toIndex) {
3429 return new CheckedRandomAccessList<>(
3430 list.subList(fromIndex, toIndex), type);
3431 }
3432 }
3433
3434 /**
3435 * Returns a dynamically typesafe view of the specified map.
3436 * Any attempt to insert a mapping whose key or value have the wrong
3437 * type will result in an immediate {@link ClassCastException}.
3438 * Similarly, any attempt to modify the value currently associated with
3439 * a key will result in an immediate {@link ClassCastException},
3440 * whether the modification is attempted directly through the map
3441 * itself, or through a {@link Map.Entry} instance obtained from the
3442 * map's {@link Map#entrySet() entry set} view.
3443 *
3444 * <p>Assuming a map contains no incorrectly typed keys or values
3445 * prior to the time a dynamically typesafe view is generated, and
3446 * that all subsequent access to the map takes place through the view
3447 * (or one of its collection views), it is <i>guaranteed</i> that the
3448 * map cannot contain an incorrectly typed key or value.
3449 *
3450 * <p>A discussion of the use of dynamically typesafe views may be
3451 * found in the documentation for the {@link #checkedCollection
3452 * checkedCollection} method.
3453 *
3454 * <p>The returned map will be serializable if the specified map is
3455 * serializable.
3456 *
3457 * <p>Since {@code null} is considered to be a value of any reference
3458 * type, the returned map permits insertion of null keys or values
3459 * whenever the backing map does.
3460 *
3461 * @param m the map for which a dynamically typesafe view is to be
3462 * returned
3463 * @param keyType the type of key that {@code m} is permitted to hold
3464 * @param valueType the type of value that {@code m} is permitted to hold
3465 * @return a dynamically typesafe view of the specified map
3466 * @since 1.5
3467 */
3468 public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
3469 Class<K> keyType,
3470 Class<V> valueType) {
3471 return new CheckedMap<>(m, keyType, valueType);
3472 }
3473
3474
3475 /**
3476 * @serial include
3477 */
3478 private static class CheckedMap<K,V>
3479 implements Map<K,V>, Serializable
3480 {
3481 private static final long serialVersionUID = 5742860141034234728L;
3482
3483 private final Map<K, V> m;
3484 final Class<K> keyType;
3485 final Class<V> valueType;
3486
3487 private void typeCheck(Object key, Object value) {
3488 if (key != null && !keyType.isInstance(key))
3489 throw new ClassCastException(badKeyMsg(key));
3490
3491 if (value != null && !valueType.isInstance(value))
3492 throw new ClassCastException(badValueMsg(value));
3493 }
3494
3495 private BiFunction<? super K, ? super V, ? extends V> typeCheck(
3496 BiFunction<? super K, ? super V, ? extends V> func) {
3497 Objects.requireNonNull(func);
3498 return (k, v) -> {
3499 V newValue = func.apply(k, v);
3500 typeCheck(k, newValue);
3501 return newValue;
3502 };
3503 }
3504
3505 private String badKeyMsg(Object key) {
3506 return "Attempt to insert " + key.getClass() +
3507 " key into map with key type " + keyType;
3508 }
3509
3510 private String badValueMsg(Object value) {
3511 return "Attempt to insert " + value.getClass() +
3512 " value into map with value type " + valueType;
3513 }
3514
3515 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
3516 if (m == null || keyType == null || valueType == null)
3517 throw new NullPointerException();
3518 this.m = m;
3519 this.keyType = keyType;
3520 this.valueType = valueType;
3521 }
3522
3523 public int size() { return m.size(); }
3524 public boolean isEmpty() { return m.isEmpty(); }
3525 public boolean containsKey(Object key) { return m.containsKey(key); }
3526 public boolean containsValue(Object v) { return m.containsValue(v); }
3527 public V get(Object key) { return m.get(key); }
3528 public V remove(Object key) { return m.remove(key); }
3529 public void clear() { m.clear(); }
3530 public Set<K> keySet() { return m.keySet(); }
3531 public Collection<V> values() { return m.values(); }
3532 public boolean equals(Object o) { return o == this || m.equals(o); }
3533 public int hashCode() { return m.hashCode(); }
3534 public String toString() { return m.toString(); }
3535
3536 public V put(K key, V value) {
3537 typeCheck(key, value);
3538 return m.put(key, value);
3539 }
3540
3541 @SuppressWarnings("unchecked")
3542 public void putAll(Map<? extends K, ? extends V> t) {
3543 // Satisfy the following goals:
3544 // - good diagnostics in case of type mismatch
3545 // - all-or-nothing semantics
3546 // - protection from malicious t
3547 // - correct behavior if t is a concurrent map
3548 Object[] entries = t.entrySet().toArray();
3549 List<Map.Entry<K,V>> checked = new ArrayList<>(entries.length);
3550 for (Object o : entries) {
3551 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
3552 Object k = e.getKey();
3553 Object v = e.getValue();
3554 typeCheck(k, v);
3555 checked.add(
3556 new AbstractMap.SimpleImmutableEntry<>((K)k, (V)v));
3557 }
3558 for (Map.Entry<K,V> e : checked)
3559 m.put(e.getKey(), e.getValue());
3560 }
3561
3562 private transient Set<Map.Entry<K,V>> entrySet = null;
3563
3564 public Set<Map.Entry<K,V>> entrySet() {
3565 if (entrySet==null)
3566 entrySet = new CheckedEntrySet<>(m.entrySet(), valueType);
3567 return entrySet;
3568 }
3569
3570 // Override default methods in Map
3571 @Override
3572 public void forEach(BiConsumer<? super K, ? super V> action) {
3573 m.forEach(action);
3574 }
3575
3576 @Override
3577 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3578 m.replaceAll(typeCheck(function));
3579 }
3580
3581 @Override
3582 public V putIfAbsent(K key, V value) {
3583 typeCheck(key, value);
3584 return m.putIfAbsent(key, value);
3585 }
3586
3587 @Override
3588 public boolean remove(Object key, Object value) {
3589 return m.remove(key, value);
3590 }
3591
3592 @Override
3593 public boolean replace(K key, V oldValue, V newValue) {
3594 typeCheck(key, newValue);
3595 return m.replace(key, oldValue, newValue);
3596 }
3597
3598 @Override
3599 public V replace(K key, V value) {
3600 typeCheck(key, value);
3601 return m.replace(key, value);
3602 }
3603
3604 @Override
3605 public V computeIfAbsent(K key,
3606 Function<? super K, ? extends V> mappingFunction) {
3607 Objects.requireNonNull(mappingFunction);
3608 return m.computeIfAbsent(key, k -> {
3609 V value = mappingFunction.apply(k);
3610 typeCheck(k, value);
3611 return value;
3612 });
3613 }
3614
3615 @Override
3616 public V computeIfPresent(K key,
3617 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3618 return m.computeIfPresent(key, typeCheck(remappingFunction));
3619 }
3620
3621 @Override
3622 public V compute(K key,
3623 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3624 return m.compute(key, typeCheck(remappingFunction));
3625 }
3626
3627 @Override
3628 public V merge(K key, V value,
3629 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
3630 Objects.requireNonNull(remappingFunction);
3631 return m.merge(key, value, (v1, v2) -> {
3632 V newValue = remappingFunction.apply(v1, v2);
3633 typeCheck(null, newValue);
3634 return newValue;
3635 });
3636 }
3637
3638 /**
3639 * We need this class in addition to CheckedSet as Map.Entry permits
3640 * modification of the backing Map via the setValue operation. This
3641 * class is subtle: there are many possible attacks that must be
3642 * thwarted.
3643 *
3644 * @serial exclude
3645 */
3646 static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> {
3647 private final Set<Map.Entry<K,V>> s;
3648 private final Class<V> valueType;
3649
3650 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
3651 this.s = s;
3652 this.valueType = valueType;
3653 }
3654
3655 public int size() { return s.size(); }
3656 public boolean isEmpty() { return s.isEmpty(); }
3657 public String toString() { return s.toString(); }
3658 public int hashCode() { return s.hashCode(); }
3659 public void clear() { s.clear(); }
3660
3661 public boolean add(Map.Entry<K, V> e) {
3662 throw new UnsupportedOperationException();
3663 }
3664 public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
3665 throw new UnsupportedOperationException();
3666 }
3667
3668 public Iterator<Map.Entry<K,V>> iterator() {
3669 final Iterator<Map.Entry<K, V>> i = s.iterator();
3670 final Class<V> valueType = this.valueType;
3671
3672 return new Iterator<Map.Entry<K,V>>() {
3673 public boolean hasNext() { return i.hasNext(); }
3674 public void remove() { i.remove(); }
3675
3676 public Map.Entry<K,V> next() {
3677 return checkedEntry(i.next(), valueType);
3678 }
3679 };
3680 }
3681
3682 @SuppressWarnings("unchecked")
3683 public Object[] toArray() {
3684 Object[] source = s.toArray();
3685
3686 /*
3687 * Ensure that we don't get an ArrayStoreException even if
3688 * s.toArray returns an array of something other than Object
3689 */
3690 Object[] dest = (CheckedEntry.class.isInstance(
3691 source.getClass().getComponentType()) ? source :
3692 new Object[source.length]);
3693
3694 for (int i = 0; i < source.length; i++)
3695 dest[i] = checkedEntry((Map.Entry<K,V>)source[i],
3696 valueType);
3697 return dest;
3698 }
3699
3700 @SuppressWarnings("unchecked")
3701 public <T> T[] toArray(T[] a) {
3702 // We don't pass a to s.toArray, to avoid window of
3703 // vulnerability wherein an unscrupulous multithreaded client
3704 // could get his hands on raw (unwrapped) Entries from s.
3705 T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
3706
3707 for (int i=0; i<arr.length; i++)
3708 arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i],
3709 valueType);
3710 if (arr.length > a.length)
3711 return arr;
3712
3713 System.arraycopy(arr, 0, a, 0, arr.length);
3714 if (a.length > arr.length)
3715 a[arr.length] = null;
3716 return a;
3717 }
3718
3719 /**
3720 * This method is overridden to protect the backing set against
3721 * an object with a nefarious equals function that senses
3722 * that the equality-candidate is Map.Entry and calls its
3723 * setValue method.
3724 */
3725 public boolean contains(Object o) {
3726 if (!(o instanceof Map.Entry))
3727 return false;
3728 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
3729 return s.contains(
3730 (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
3731 }
3732
3733 /**
3734 * The bulk collection methods are overridden to protect
3735 * against an unscrupulous collection whose contains(Object o)
3736 * method senses when o is a Map.Entry, and calls o.setValue.
3737 */
3738 public boolean containsAll(Collection<?> c) {
3739 for (Object o : c)
3740 if (!contains(o)) // Invokes safe contains() above
3741 return false;
3742 return true;
3743 }
3744
3745 public boolean remove(Object o) {
3746 if (!(o instanceof Map.Entry))
3747 return false;
3748 return s.remove(new AbstractMap.SimpleImmutableEntry
3749 <>((Map.Entry<?,?>)o));
3750 }
3751
3752 public boolean removeAll(Collection<?> c) {
3753 return batchRemove(c, false);
3754 }
3755 public boolean retainAll(Collection<?> c) {
3756 return batchRemove(c, true);
3757 }
3758 private boolean batchRemove(Collection<?> c, boolean complement) {
3759 boolean modified = false;
3760 Iterator<Map.Entry<K,V>> it = iterator();
3761 while (it.hasNext()) {
3762 if (c.contains(it.next()) != complement) {
3763 it.remove();
3764 modified = true;
3765 }
3766 }
3767 return modified;
3768 }
3769
3770 public boolean equals(Object o) {
3771 if (o == this)
3772 return true;
3773 if (!(o instanceof Set))
3774 return false;
3775 Set<?> that = (Set<?>) o;
3776 return that.size() == s.size()
3777 && containsAll(that); // Invokes safe containsAll() above
3778 }
3779
3780 static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e,
3781 Class<T> valueType) {
3782 return new CheckedEntry<>(e, valueType);
3783 }
3784
3785 /**
3786 * This "wrapper class" serves two purposes: it prevents
3787 * the client from modifying the backing Map, by short-circuiting
3788 * the setValue method, and it protects the backing Map against
3789 * an ill-behaved Map.Entry that attempts to modify another
3790 * Map.Entry when asked to perform an equality check.
3791 */
3792 private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> {
3793 private final Map.Entry<K, V> e;
3794 private final Class<T> valueType;
3795
3796 CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) {
3797 this.e = e;
3798 this.valueType = valueType;
3799 }
3800
3801 public K getKey() { return e.getKey(); }
3802 public V getValue() { return e.getValue(); }
3803 public int hashCode() { return e.hashCode(); }
3804 public String toString() { return e.toString(); }
3805
3806 public V setValue(V value) {
3807 if (value != null && !valueType.isInstance(value))
3808 throw new ClassCastException(badValueMsg(value));
3809 return e.setValue(value);
3810 }
3811
3812 private String badValueMsg(Object value) {
3813 return "Attempt to insert " + value.getClass() +
3814 " value into map with value type " + valueType;
3815 }
3816
3817 public boolean equals(Object o) {
3818 if (o == this)
3819 return true;
3820 if (!(o instanceof Map.Entry))
3821 return false;
3822 return e.equals(new AbstractMap.SimpleImmutableEntry
3823 <>((Map.Entry<?,?>)o));
3824 }
3825 }
3826 }
3827 }
3828
3829 /**
3830 * Returns a dynamically typesafe view of the specified sorted map.
3831 * Any attempt to insert a mapping whose key or value have the wrong
3832 * type will result in an immediate {@link ClassCastException}.
3833 * Similarly, any attempt to modify the value currently associated with
3834 * a key will result in an immediate {@link ClassCastException},
3835 * whether the modification is attempted directly through the map
3836 * itself, or through a {@link Map.Entry} instance obtained from the
3837 * map's {@link Map#entrySet() entry set} view.
3838 *
3839 * <p>Assuming a map contains no incorrectly typed keys or values
3840 * prior to the time a dynamically typesafe view is generated, and
3841 * that all subsequent access to the map takes place through the view
3842 * (or one of its collection views), it is <i>guaranteed</i> that the
3843 * map cannot contain an incorrectly typed key or value.
3844 *
3845 * <p>A discussion of the use of dynamically typesafe views may be
3846 * found in the documentation for the {@link #checkedCollection
3847 * checkedCollection} method.
3848 *
3849 * <p>The returned map will be serializable if the specified map is
3850 * serializable.
3851 *
3852 * <p>Since {@code null} is considered to be a value of any reference
3853 * type, the returned map permits insertion of null keys or values
3854 * whenever the backing map does.
3855 *
3856 * @param m the map for which a dynamically typesafe view is to be
3857 * returned
3858 * @param keyType the type of key that {@code m} is permitted to hold
3859 * @param valueType the type of value that {@code m} is permitted to hold
3860 * @return a dynamically typesafe view of the specified map
3861 * @since 1.5
3862 */
3863 public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m,
3864 Class<K> keyType,
3865 Class<V> valueType) {
3866 return new CheckedSortedMap<>(m, keyType, valueType);
3867 }
3868
3869 /**
3870 * @serial include
3871 */
3872 static class CheckedSortedMap<K,V> extends CheckedMap<K,V>
3873 implements SortedMap<K,V>, Serializable
3874 {
3875 private static final long serialVersionUID = 1599671320688067438L;
3876
3877 private final SortedMap<K, V> sm;
3878
3879 CheckedSortedMap(SortedMap<K, V> m,
3880 Class<K> keyType, Class<V> valueType) {
3881 super(m, keyType, valueType);
3882 sm = m;
3883 }
3884
3885 public Comparator<? super K> comparator() { return sm.comparator(); }
3886 public K firstKey() { return sm.firstKey(); }
3887 public K lastKey() { return sm.lastKey(); }
3888
3889 public SortedMap<K,V> subMap(K fromKey, K toKey) {
3890 return checkedSortedMap(sm.subMap(fromKey, toKey),
3891 keyType, valueType);
3892 }
3893 public SortedMap<K,V> headMap(K toKey) {
3894 return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
3895 }
3896 public SortedMap<K,V> tailMap(K fromKey) {
3897 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
3898 }
3899 }
3900
3901 /**
3902 * Returns a dynamically typesafe view of the specified navigable map.
3903 * Any attempt to insert a mapping whose key or value have the wrong
3904 * type will result in an immediate {@link ClassCastException}.
3905 * Similarly, any attempt to modify the value currently associated with
3906 * a key will result in an immediate {@link ClassCastException},
3907 * whether the modification is attempted directly through the map
3908 * itself, or through a {@link Map.Entry} instance obtained from the
3909 * map's {@link Map#entrySet() entry set} view.
3910 *
3911 * <p>Assuming a map contains no incorrectly typed keys or values
3912 * prior to the time a dynamically typesafe view is generated, and
3913 * that all subsequent access to the map takes place through the view
3914 * (or one of its collection views), it is <em>guaranteed</em> that the
3915 * map cannot contain an incorrectly typed key or value.
3916 *
3917 * <p>A discussion of the use of dynamically typesafe views may be
3918 * found in the documentation for the {@link #checkedCollection
3919 * checkedCollection} method.
3920 *
3921 * <p>The returned map will be serializable if the specified map is
3922 * serializable.
3923 *
3924 * <p>Since {@code null} is considered to be a value of any reference
3925 * type, the returned map permits insertion of null keys or values
3926 * whenever the backing map does.
3927 *
3928 * @param m the map for which a dynamically typesafe view is to be
3929 * returned
3930 * @param keyType the type of key that {@code m} is permitted to hold
3931 * @param valueType the type of value that {@code m} is permitted to hold
3932 * @return a dynamically typesafe view of the specified map
3933 * @since 1.8
3934 */
3935 public static <K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K, V> m,
3936 Class<K> keyType,
3937 Class<V> valueType) {
3938 return new CheckedNavigableMap<>(m, keyType, valueType);
3939 }
3940
3941 /**
3942 * @serial include
3943 */
3944 static class CheckedNavigableMap<K,V> extends CheckedSortedMap<K,V>
3945 implements NavigableMap<K,V>, Serializable
3946 {
3947 //private static final long serialVersionUID = 1599671320688067438L;
3948
3949 private final NavigableMap<K, V> nm;
3950
3951 CheckedNavigableMap(NavigableMap<K, V> m,
3952 Class<K> keyType, Class<V> valueType) {
3953 super(m, keyType, valueType);
3954 nm = m;
3955 }
3956
3957 public Comparator<? super K> comparator() { return nm.comparator(); }
3958 public K firstKey() { return nm.firstKey(); }
3959 public K lastKey() { return nm.lastKey(); }
3960
3961 public NavigableMap<K,V> subMap(K fromKey, K toKey) {
3962 return checkedNavigableMap((NavigableMap<K,V>)nm.subMap(fromKey, toKey),
3963 keyType, valueType);
3964 }
3965 public NavigableMap<K,V> headMap(K toKey) {
3966 return checkedNavigableMap((NavigableMap<K,V>)nm.headMap(toKey), keyType, valueType);
3967 }
3968 public NavigableMap<K,V> tailMap(K fromKey) {
3969 return checkedNavigableMap((NavigableMap<K,V>)nm.tailMap(fromKey), keyType, valueType);
3970 }
3971
3972 @Override
3973 public Entry<K, V> lowerEntry(K key) {
3974 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lowerEntry(key), valueType);
3975 }
3976
3977 @Override
3978 public K lowerKey(K key) {
3979 return nm.lowerKey(key);
3980 }
3981
3982 @Override
3983 public Entry<K, V> floorEntry(K key) {
3984 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lowerEntry(key), valueType);
3985 }
3986
3987 @Override
3988 public K floorKey(K key) {
3989 return nm.floorKey(key);
3990 }
3991
3992 @Override
3993 public Entry<K, V> ceilingEntry(K key) {
3994 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.ceilingEntry(key), valueType);
3995 }
3996
3997 @Override
3998 public K ceilingKey(K key) {
3999 return nm.ceilingKey(key);
4000 }
4001
4002 @Override
4003 public Entry<K, V> higherEntry(K key) {
4004 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.higherEntry(key), valueType);
4005 }
4006
4007 @Override
4008 public K higherKey(K key) {
4009 return nm.higherKey(key);
4010 }
4011
4012 @Override
4013 public Entry<K, V> firstEntry() {
4014 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.firstEntry(), valueType);
4015 }
4016
4017 @Override
4018 public Entry<K, V> lastEntry() {
4019 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lastEntry(), valueType);
4020 }
4021
4022 @Override
4023 public Entry<K, V> pollFirstEntry() {
4024 Entry<K,V> entry = nm.pollFirstEntry();
4025 return (null == entry) ? null : new CheckedMap.CheckedEntrySet.CheckedEntry(entry, valueType);
4026 }
4027
4028 @Override
4029 public Entry<K, V> pollLastEntry() {
4030 Entry<K,V> entry = nm.pollLastEntry();
4031 return (null == entry) ? null : new CheckedMap.CheckedEntrySet.CheckedEntry(entry, valueType);
4032 }
4033
4034 @Override
4035 public NavigableMap<K, V> descendingMap() {
4036 return checkedNavigableMap(nm.descendingMap(), keyType, valueType);
4037 }
4038
4039 @Override
4040 public NavigableSet<K> navigableKeySet() {
4041 return checkedNavigableSet(nm.navigableKeySet(), keyType);
4042 }
4043
4044 @Override
4045 public NavigableSet<K> descendingKeySet() {
4046 return checkedNavigableSet(nm.descendingKeySet(), keyType);
4047 }
4048
4049 @Override
4050 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
4051 return checkedNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive), keyType, valueType);
4052 }
4053
4054 @Override
4055 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
4056 return checkedNavigableMap(nm.headMap(toKey, inclusive), keyType, valueType);
4057 }
4058
4059 @Override
4060 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
4061 return checkedNavigableMap(nm.tailMap(fromKey, inclusive), keyType, valueType);
4062 }
4063 }
4064
4065 // Empty collections
4066
4067 /**
4068 * Returns an iterator that has no elements. More precisely,
4069 *
4070 * <ul compact>
4071 *
4072 * <li>{@link Iterator#hasNext hasNext} always returns {@code
4073 * false}.
4074 *
4075 * <li>{@link Iterator#next next} always throws {@link
4076 * NoSuchElementException}.
4077 *
4078 * <li>{@link Iterator#remove remove} always throws {@link
4079 * IllegalStateException}.
4080 *
4081 * </ul>
4082 *
4083 * <p>Implementations of this method are permitted, but not
4084 * required, to return the same object from multiple invocations.
4085 *
4086 * @return an empty iterator
4087 * @since 1.7
4088 */
4089 @SuppressWarnings("unchecked")
4090 public static <T> Iterator<T> emptyIterator() {
4091 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
4092 }
4093
4094 private static class EmptyIterator<E> implements Iterator<E> {
4095 static final EmptyIterator<Object> EMPTY_ITERATOR
4096 = new EmptyIterator<>();
4097
4098 public boolean hasNext() { return false; }
4099 public E next() { throw new NoSuchElementException(); }
4100 public void remove() { throw new IllegalStateException(); }
4101 @Override
4102 public void forEachRemaining(Consumer<? super E> action) {
4103 Objects.requireNonNull(action);
4104 }
4105 }
4106
4107 /**
4108 * Returns a list iterator that has no elements. More precisely,
4109 *
4110 * <ul compact>
4111 *
4112 * <li>{@link Iterator#hasNext hasNext} and {@link
4113 * ListIterator#hasPrevious hasPrevious} always return {@code
4114 * false}.
4115 *
4116 * <li>{@link Iterator#next next} and {@link ListIterator#previous
4117 * previous} always throw {@link NoSuchElementException}.
4118 *
4119 * <li>{@link Iterator#remove remove} and {@link ListIterator#set
4120 * set} always throw {@link IllegalStateException}.
4121 *
4122 * <li>{@link ListIterator#add add} always throws {@link
4123 * UnsupportedOperationException}.
4124 *
4125 * <li>{@link ListIterator#nextIndex nextIndex} always returns
4126 * {@code 0} .
4127 *
4128 * <li>{@link ListIterator#previousIndex previousIndex} always
4129 * returns {@code -1}.
4130 *
4131 * </ul>
4132 *
4133 * <p>Implementations of this method are permitted, but not
4134 * required, to return the same object from multiple invocations.
4135 *
4136 * @return an empty list iterator
4137 * @since 1.7
4138 */
4139 @SuppressWarnings("unchecked")
4140 public static <T> ListIterator<T> emptyListIterator() {
4141 return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
4142 }
4143
4144 private static class EmptyListIterator<E>
4145 extends EmptyIterator<E>
4146 implements ListIterator<E>
4147 {
4148 static final EmptyListIterator<Object> EMPTY_ITERATOR
4149 = new EmptyListIterator<>();
4150
4151 public boolean hasPrevious() { return false; }
4152 public E previous() { throw new NoSuchElementException(); }
4153 public int nextIndex() { return 0; }
4154 public int previousIndex() { return -1; }
4155 public void set(E e) { throw new IllegalStateException(); }
4156 public void add(E e) { throw new UnsupportedOperationException(); }
4157 }
4158
4159 /**
4160 * Returns an enumeration that has no elements. More precisely,
4161 *
4162 * <ul compact>
4163 *
4164 * <li>{@link Enumeration#hasMoreElements hasMoreElements} always
4165 * returns {@code false}.
4166 *
4167 * <li> {@link Enumeration#nextElement nextElement} always throws
4168 * {@link NoSuchElementException}.
4169 *
4170 * </ul>
4171 *
4172 * <p>Implementations of this method are permitted, but not
4173 * required, to return the same object from multiple invocations.
4174 *
4175 * @return an empty enumeration
4176 * @since 1.7
4177 */
4178 @SuppressWarnings("unchecked")
4179 public static <T> Enumeration<T> emptyEnumeration() {
4180 return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
4181 }
4182
4183 private static class EmptyEnumeration<E> implements Enumeration<E> {
4184 static final EmptyEnumeration<Object> EMPTY_ENUMERATION
4185 = new EmptyEnumeration<>();
4186
4187 public boolean hasMoreElements() { return false; }
4188 public E nextElement() { throw new NoSuchElementException(); }
4189 }
4190
4191 /**
4192 * The empty set (immutable). This set is serializable.
4193 *
4194 * @see #emptySet()
4195 */
4196 @SuppressWarnings("rawtypes")
4197 public static final Set EMPTY_SET = new EmptySet<>();
4198
4199 /**
4200 * Returns the empty set (immutable). This set is serializable.
4201 * Unlike the like-named field, this method is parameterized.
4202 *
4203 * <p>This example illustrates the type-safe way to obtain an empty set:
4204 * <pre>
4205 * Set<String> s = Collections.emptySet();
4206 * </pre>
4207 * Implementation note: Implementations of this method need not
4208 * create a separate <tt>Set</tt> object for each call. Using this
4209 * method is likely to have comparable cost to using the like-named
4210 * field. (Unlike this method, the field does not provide type safety.)
4211 *
4212 * @see #EMPTY_SET
4213 * @since 1.5
4214 */
4215 @SuppressWarnings("unchecked")
4216 public static final <T> Set<T> emptySet() {
4217 return (Set<T>) EMPTY_SET;
4218 }
4219
4220 /**
4221 * @serial include
4222 */
4223 private static class EmptySet<E>
4224 extends AbstractSet<E>
4225 implements Serializable
4226 {
4227 private static final long serialVersionUID = 1582296315990362920L;
4228
4229 public Iterator<E> iterator() { return emptyIterator(); }
4230
4231 public int size() {return 0;}
4232 public boolean isEmpty() {return true;}
4233
4234 public boolean contains(Object obj) {return false;}
4235 public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
4236
4237 public Object[] toArray() { return new Object[0]; }
4238
4239 public <T> T[] toArray(T[] a) {
4240 if (a.length > 0)
4241 a[0] = null;
4242 return a;
4243 }
4244
4245 // Override default methods in Collection
4246 @Override
4247 public void forEach(Consumer<? super E> action) {
4248 Objects.requireNonNull(action);
4249 }
4250 @Override
4251 public boolean removeIf(Predicate<? super E> filter) {
4252 Objects.requireNonNull(filter);
4253 return false;
4254 }
4255 @Override
4256 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
4257
4258 // Preserves singleton property
4259 private Object readResolve() {
4260 return EMPTY_SET;
4261 }
4262 }
4263
4264 private static final EmptyNavigableSet<?> EMPTY_NAVIGABLE_SET =
4265 new EmptyNavigableSet<>();
4266
4267 /**
4268 * Returns the empty sorted set (immutable). This set is serializable.
4269 *
4270 * <p>This example illustrates the type-safe way to obtain an empty
4271 * sorted set:
4272 * <pre> {@code
4273 * SortedSet<String> s = Collections.emptySortedSet();
4274 * }</pre>
4275 *
4276 * @implNote Implementations of this method need not create a separate
4277 * {@code SortedSet} object for each call.
4278 *
4279 * @since 1.8
4280 */
4281 @SuppressWarnings("unchecked")
4282 public static <E> SortedSet<E> emptySortedSet() {
4283 return (SortedSet<E>) EMPTY_NAVIGABLE_SET;
4284 }
4285
4286 /**
4287 * Returns the empty navigable set (immutable). This set is serializable.
4288 *
4289 * <p>This example illustrates the type-safe way to obtain an empty
4290 * navigable set:
4291 * <pre> {@code
4292 * NavigableSet<String> s = Collections.emptyNavigableSet();
4293 * }</pre>
4294 *
4295 * @implNote Implementations of this method need not
4296 * create a separate {@code NavigableSet} object for each call.
4297 *
4298 * @since 1.8
4299 */
4300 @SuppressWarnings("unchecked")
4301 public static <E>NavigableSet<E> emptyNavigableSet() {
4302 return (NavigableSet<E>) EMPTY_NAVIGABLE_SET;
4303 }
4304
4305 /**
4306 * @serial include
4307 */
4308 private static class EmptyNavigableSet<E>
4309 extends EmptySet<E>
4310 implements NavigableSet<E>, Serializable
4311 {
4312 // private static final long serialVersionUID = 6316515401502265487L;
4313
4314 public boolean contains(Object obj) {
4315 Comparable<E> e = (Comparable<E>) obj;
4316 return obj != e;
4317 }
4318
4319 // Preserves singleton property
4320 private Object readResolve() {
4321 return Collections.emptyNavigableSet();
4322 }
4323
4324 @Override
4325 public Comparator<? super E> comparator() {
4326 return null;
4327 }
4328
4329 @Override
4330 @SuppressWarnings("unchecked")
4331 public SortedSet<E> subSet(E fromElement, E toElement) {
4332 return subSet(fromElement, true, toElement, false);
4333 }
4334
4335 @Override
4336 public SortedSet<E> headSet(E toElement) {
4337 return headSet(toElement, false);
4338 }
4339
4340 @Override
4341 public SortedSet<E> tailSet(E fromElement) {
4342 return tailSet(fromElement, true);
4343 }
4344
4345 @Override
4346 public E first() {
4347 throw new NoSuchElementException();
4348 }
4349
4350 @Override
4351 public E last() {
4352 throw new NoSuchElementException();
4353 }
4354
4355 @Override
4356 public E lower(E e) {
4357 Objects.requireNonNull(e);
4358 return null;
4359 }
4360
4361 @Override
4362 public E floor(E e) {
4363 Objects.requireNonNull(e);
4364 return null;
4365 }
4366
4367 @Override
4368 public E ceiling(E e) {
4369 Objects.requireNonNull(e);
4370 return null;
4371 }
4372
4373 @Override
4374 public E higher(E e) {
4375 Objects.requireNonNull(e);
4376 return null;
4377 }
4378
4379 @Override
4380 public E pollFirst() {
4381 return null;
4382 }
4383
4384 @Override
4385 public E pollLast() {
4386 return null;
4387 }
4388
4389 @Override
4390 public NavigableSet<E> descendingSet() {
4391 return new BoundedEmptyNavigableSet(null, true, null, true, true);
4392 }
4393
4394 @Override
4395 public Iterator<E> descendingIterator() { return emptyIterator(); }
4396
4397 @Override
4398 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
4399 return new BoundedEmptyNavigableSet(
4400 (Comparable<E>) Objects.requireNonNull(fromElement), fromInclusive,
4401 (Comparable<E>) Objects.requireNonNull(toElement), toInclusive,
4402 false);
4403 }
4404
4405 @Override
4406 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
4407 return new BoundedEmptyNavigableSet(
4408 null, true,
4409 (Comparable<E>) Objects.requireNonNull(toElement), inclusive,
4410 false);
4411 }
4412
4413 @Override
4414 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
4415 return new BoundedEmptyNavigableSet(
4416 (Comparable<E>) Objects.requireNonNull(fromElement), inclusive,
4417 null, true, false);
4418 }
4419
4420 // Override default methods in Collection
4421 @Override
4422 public void forEach(Consumer<? super E> action) {
4423 Objects.requireNonNull(action);
4424 }
4425
4426 @Override
4427 public boolean removeIf(Predicate<? super E> filter) {
4428 Objects.requireNonNull(filter);
4429 return false;
4430 }
4431
4432 @Override
4433 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
4434 }
4435
4436 /**
4437 * The empty list (immutable). This list is serializable.
4438 *
4439 * @see #emptyList()
4440 */
4441 @SuppressWarnings("rawtypes")
4442 public static final List EMPTY_LIST = new EmptyList<>();
4443
4444 /**
4445 * Returns the empty list (immutable). This list is serializable.
4446 *
4447 * <p>This example illustrates the type-safe way to obtain an empty list:
4448 * <pre>
4449 * List<String> s = Collections.emptyList();
4450 * </pre>
4451 * Implementation note: Implementations of this method need not
4452 * create a separate <tt>List</tt> object for each call. Using this
4453 * method is likely to have comparable cost to using the like-named
4454 * field. (Unlike this method, the field does not provide type safety.)
4455 *
4456 * @see #EMPTY_LIST
4457 * @since 1.5
4458 */
4459 @SuppressWarnings("unchecked")
4460 public static final <T> List<T> emptyList() {
4461 return (List<T>) EMPTY_LIST;
4462 }
4463
4464 /**
4465 * @serial include
4466 */
4467 private static class EmptyList<E>
4468 extends AbstractList<E>
4469 implements RandomAccess, Serializable {
4470 private static final long serialVersionUID = 8842843931221139166L;
4471
4472 public Iterator<E> iterator() {
4473 return emptyIterator();
4474 }
4475 public ListIterator<E> listIterator() {
4476 return emptyListIterator();
4477 }
4478
4479 public int size() {return 0;}
4480 public boolean isEmpty() {return true;}
4481
4482 public boolean contains(Object obj) {return false;}
4483 public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
4484
4485 public Object[] toArray() { return new Object[0]; }
4486
4487 public <T> T[] toArray(T[] a) {
4488 if (a.length > 0)
4489 a[0] = null;
4490 return a;
4491 }
4492
4493 public E get(int index) {
4494 throw new IndexOutOfBoundsException("Index: "+index);
4495 }
4496
4497 public boolean equals(Object o) {
4498 return (o instanceof List) && ((List<?>)o).isEmpty();
4499 }
4500
4501 public int hashCode() { return 1; }
4502
4503 @Override
4504 public boolean removeIf(Predicate<? super E> filter) {
4505 Objects.requireNonNull(filter);
4506 return false;
4507 }
4508 @Override
4509 public void replaceAll(UnaryOperator<E> operator) {
4510 Objects.requireNonNull(operator);
4511 }
4512 @Override
4513 public void sort(Comparator<? super E> c) {
4514 Objects.requireNonNull(c);
4515 }
4516
4517 // Override default methods in Collection
4518 @Override
4519 public void forEach(Consumer<? super E> action) {
4520 Objects.requireNonNull(action);
4521 }
4522
4523 @Override
4524 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
4525
4526 // Preserves singleton property
4527 private Object readResolve() {
4528 return EMPTY_LIST;
4529 }
4530 }
4531
4532 private static class BoundedEmptyNavigableSet<E> extends EmptyNavigableSet<E>
4533 implements Serializable {
4534
4535 final boolean descending;
4536 final boolean lowerInclusive;
4537 final boolean upperInclusive;
4538 final Comparable<E> lowerBound;
4539 final Comparable<E> upperBound;
4540
4541 public BoundedEmptyNavigableSet(
4542 Comparable<E> fromElement, boolean lowerInclusive,
4543 Comparable<E> toElement, boolean upperInclusive,
4544 boolean descending) {
4545 this.descending = descending;
4546
4547 if ((fromElement != null) && (toElement != null)) {
4548 int fromCompared = Integer.signum(fromElement.compareTo((E)toElement));
4549 int toCompared = Integer.signum(toElement.compareTo((E)fromElement));
4550
4551 if(fromCompared != -toCompared) {
4552 throw new IllegalArgumentException("inconsistent compareTo");
4553 }
4554
4555 if (!descending) {
4556 if (fromCompared > 0) {
4557 throw new IllegalArgumentException();
4558 }
4559 } else {
4560 if (fromCompared < 0) {
4561 throw new IllegalArgumentException();
4562 }
4563 }
4564 }
4565
4566 this.lowerBound = fromElement;
4567 this.lowerInclusive = lowerInclusive;
4568 this.upperBound = toElement;
4569 this.upperInclusive = upperInclusive;
4570 }
4571
4572 @Override
4573 public Comparator<E> comparator() {
4574 return descending ? Collections.reverseOrder() : null;
4575 }
4576
4577 public NavigableSet<E> descendingSet() {
4578 return new BoundedEmptyNavigableSet(upperBound, upperInclusive, lowerBound, lowerInclusive, !descending);
4579 }
4580
4581 @Override
4582 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
4583 return new BoundedEmptyNavigableSet(inBounds(fromElement), fromInclusive, inBounds(toElement), toInclusive, descending);
4584 }
4585
4586 @Override
4587 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
4588 return new BoundedEmptyNavigableSet(lowerBound, lowerInclusive, inBounds(toElement), inclusive, descending);
4589 }
4590
4591 @Override
4592 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
4593 return new BoundedEmptyNavigableSet(inBounds(fromElement), inclusive, upperBound, upperInclusive, descending);
4594 }
4595
4596 private Comparable<E> inBounds(E element) {
4597 if (!descending) {
4598 if (null != lowerBound) {
4599 if (lowerInclusive) {
4600 if (lowerBound.compareTo(element) > 0) {
4601 throw new IllegalArgumentException("out of bounds");
4602 }
4603 } else {
4604 if (lowerBound.compareTo(element) >= 0) {
4605 throw new IllegalArgumentException("out of bounds");
4606 }
4607 }
4608 }
4609
4610 if (null != upperBound) {
4611 if (upperInclusive) {
4612 if (upperBound.compareTo(element) < 0) {
4613 throw new IllegalArgumentException("out of bounds");
4614 }
4615 } else {
4616 if (upperBound.compareTo(element) <= 0) {
4617 throw new IllegalArgumentException("out of bounds");
4618 }
4619 }
4620 }
4621 } else {
4622 if (null != lowerBound) {
4623 if (lowerInclusive) {
4624 if (lowerBound.compareTo(element) < 0) {
4625 throw new IllegalArgumentException("out of bounds");
4626 }
4627 } else {
4628 if (lowerBound.compareTo(element) <= 0) {
4629 throw new IllegalArgumentException("out of bounds");
4630 }
4631 }
4632 }
4633
4634 if (null != upperBound) {
4635 if (upperInclusive) {
4636 if (upperBound.compareTo(element) > 0) {
4637 throw new IllegalArgumentException("out of bounds");
4638 }
4639 } else {
4640 if (upperBound.compareTo(element) >= 0) {
4641 throw new IllegalArgumentException("out of bounds");
4642 }
4643 }
4644 }
4645 }
4646
4647 return (Comparable<E>)Objects.requireNonNull(element);
4648 }
4649 }
4650
4651 private static class BoundedEmptyNavigableMap<K,V> extends EmptyNavigableMap<K,V>
4652 implements Serializable {
4653
4654 final boolean descending;
4655 final boolean lowerInclusive;
4656 final boolean upperInclusive;
4657 final Comparable<K> lowerBound;
4658 final Comparable<K> upperBound;
4659
4660 public BoundedEmptyNavigableMap(
4661 Comparable<K> fromElement, boolean lowerInclusive,
4662 Comparable<K> toElement, boolean upperInclusive,
4663 boolean descending) {
4664 this.descending = descending;
4665
4666 if ((fromElement != null) && (toElement != null)) {
4667 int fromCompared = Integer.signum(fromElement.compareTo((K)toElement));
4668 int toCompared = Integer.signum(toElement.compareTo((K)fromElement));
4669
4670 if(fromCompared != -toCompared) {
4671 throw new IllegalArgumentException("inconsistent compareTo");
4672 }
4673
4674 if (!descending) {
4675 if (fromCompared > 0) {
4676 throw new IllegalArgumentException();
4677 }
4678 } else {
4679 if (fromCompared < 0) {
4680 throw new IllegalArgumentException();
4681 }
4682 }
4683 }
4684
4685 this.lowerBound = fromElement;
4686 this.lowerInclusive = lowerInclusive;
4687 this.upperBound = toElement;
4688 this.upperInclusive = upperInclusive;
4689 }
4690
4691 @Override
4692 public Comparator<? super K> comparator() {
4693 return descending ? Collections.reverseOrder() : null;
4694 }
4695
4696 @Override
4697 public boolean containsKey(Object obj) {
4698 Comparable<K> e = (Comparable<K>) obj;
4699 return obj != e;
4700 }
4701
4702 private Comparable<K> inBounds(K element) {
4703 if (!descending) {
4704 if (null != lowerBound) {
4705 if (lowerInclusive) {
4706 if (lowerBound.compareTo(element) > 0) {
4707 throw new IllegalArgumentException("out of bounds");
4708 }
4709 } else {
4710 if (lowerBound.compareTo(element) >= 0) {
4711 throw new IllegalArgumentException("out of bounds");
4712 }
4713 }
4714 }
4715
4716 if (null != upperBound) {
4717 if (upperInclusive) {
4718 if (upperBound.compareTo(element) < 0) {
4719 throw new IllegalArgumentException("out of bounds");
4720 }
4721 } else {
4722 if (upperBound.compareTo(element) <= 0) {
4723 throw new IllegalArgumentException("out of bounds");
4724 }
4725 }
4726 }
4727 } else {
4728 if (null != lowerBound) {
4729 if (lowerInclusive) {
4730 if (lowerBound.compareTo(element) < 0) {
4731 throw new IllegalArgumentException("out of bounds");
4732 }
4733 } else {
4734 if (lowerBound.compareTo(element) <= 0) {
4735 throw new IllegalArgumentException("out of bounds");
4736 }
4737 }
4738 }
4739
4740 if (null != upperBound) {
4741 if (upperInclusive) {
4742 if (upperBound.compareTo(element) > 0) {
4743 throw new IllegalArgumentException("out of bounds");
4744 }
4745 } else {
4746 if (upperBound.compareTo(element) >= 0) {
4747 throw new IllegalArgumentException("out of bounds");
4748 }
4749 }
4750 }
4751 }
4752
4753 return (Comparable<K>)Objects.requireNonNull(element);
4754 }
4755
4756 @Override
4757 public NavigableMap<K, V> descendingMap() {
4758 if (upperBound == null && lowerBound == null && descending) {
4759 return Collections.emptyNavigableMap();
4760 }
4761 return new BoundedEmptyNavigableMap(upperBound, upperInclusive, lowerBound, lowerInclusive, !descending);
4762 }
4763
4764 @Override
4765 public NavigableSet<K> navigableKeySet() {
4766 if (upperBound == null && lowerBound == null && !descending) {
4767 return Collections.emptyNavigableSet();
4768 }
4769 return new BoundedEmptyNavigableSet(lowerBound, lowerInclusive, upperBound, upperInclusive, descending);
4770 }
4771
4772 @Override
4773 public NavigableSet<K> descendingKeySet() {
4774 if (upperBound == null && lowerBound == null && descending) {
4775 return Collections.emptyNavigableSet();
4776 }
4777 return new BoundedEmptyNavigableSet(upperBound, upperInclusive, lowerBound, lowerInclusive, !descending);
4778 }
4779
4780 @Override
4781 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
4782 return new BoundedEmptyNavigableMap(inBounds(fromKey), fromInclusive, inBounds(toKey), toInclusive, descending);
4783 }
4784
4785 @Override
4786 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
4787 return new BoundedEmptyNavigableMap(lowerBound, lowerInclusive, inBounds(toKey), inclusive, descending);
4788 }
4789
4790 @Override
4791 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
4792 return new BoundedEmptyNavigableMap(inBounds(fromKey), inclusive, upperBound, upperInclusive, descending);
4793 }
4794 }
4795
4796 /**
4797 * The empty map (immutable). This map is serializable.
4798 *
4799 * @see #emptyMap()
4800 * @since 1.3
4801 */
4802 @SuppressWarnings("rawtypes")
4803 public static final Map EMPTY_MAP = new EmptyMap<>();
4804
4805 /**
4806 * Returns the empty map (immutable). This map is serializable.
4807 *
4808 * <p>This example illustrates the type-safe way to obtain an empty map:
4809 * <pre>
4810 * Map<String, Date> s = Collections.emptyMap();
4811 * </pre>
4812 * Implementation note: Implementations of this method need not
4813 * create a separate <tt>Map</tt> object for each call. Using this
4814 * method is likely to have comparable cost to using the like-named
4815 * field. (Unlike this method, the field does not provide type safety.)
4816 *
4817 * @see #EMPTY_MAP
4818 * @since 1.5
4819 */
4820 @SuppressWarnings("unchecked")
4821 public static final <K,V> Map<K,V> emptyMap() {
4822 return (Map<K,V>) EMPTY_MAP;
4823 }
4824
4825 /**
4826 * Returns the empty sorted map (immutable). This map is serializable.
4827 *
4828 * <p>This example illustrates the type-safe way to obtain an empty map:
4829 * <pre> {@code
4830 * SortedMap<String, Date> s = Collections.emptySortedMap();
4831 * }</pre>
4832 *
4833 * @implNote Implementations of this method need not create a separate
4834 * {@code SortedMap} object for each call.
4835 *
4836 * @since 1.8
4837 */
4838 @SuppressWarnings("unchecked")
4839 public static final <K,V> SortedMap<K,V> emptySortedMap() {
4840 return (SortedMap<K,V>) EMPTY_NAVIGABLE_MAP;
4841 }
4842
4843 @SuppressWarnings("rawtypes")
4844 private static final NavigableMap EMPTY_NAVIGABLE_MAP =
4845 new EmptyNavigableMap();
4846
4847 /**
4848 * Returns the empty navigable map (immutable). This map is serializable.
4849 *
4850 * <p>This example illustrates the type-safe way to obtain an empty map:
4851 * <pre> {@code
4852 * NavigableMap<String, Date> s = Collections.emptyNavigableMap();
4853 * }</pre>
4854 *
4855 * @implNote Implementations of this method need not create a separate
4856 * {@code NavigableMap} object for each call.
4857 *
4858 * @since 1.8
4859 */
4860 @SuppressWarnings("unchecked")
4861 public static final <K,V> NavigableMap<K,V> emptyNavigableMap() {
4862 return (NavigableMap<K,V>) EMPTY_NAVIGABLE_MAP;
4863 }
4864
4865 /**
4866 * @serial include
4867 */
4868 private static class EmptyMap<K,V>
4869 extends AbstractMap<K,V>
4870 implements Serializable
4871 {
4872 private static final long serialVersionUID = 6428348081105594320L;
4873
4874 public int size() {return 0;}
4875 public boolean isEmpty() {return true;}
4876 public boolean containsKey(Object key) {return false;}
4877 public boolean containsValue(Object value) {return false;}
4878 public V get(Object key) {return null;}
4879 public Set<K> keySet() {return emptySet();}
4880 public Collection<V> values() {return emptySet();}
4881 public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
4882
4883 public boolean equals(Object o) {
4884 return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
4885 }
4886
4887 public int hashCode() {return 0;}
4888
4889 // Override default methods in Map
4890 @Override
4891 @SuppressWarnings("unchecked")
4892 public V getOrDefault(Object k, V defaultValue) {
4893 return defaultValue;
4894 }
4895
4896 @Override
4897 public void forEach(BiConsumer<? super K, ? super V> action) {
4898 Objects.requireNonNull(action);
4899 }
4900
4901 @Override
4902 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
4903 Objects.requireNonNull(function);
4904 }
4905
4906 @Override
4907 public V putIfAbsent(K key, V value) {
4908 throw new UnsupportedOperationException();
4909 }
4910
4911 @Override
4912 public boolean remove(Object key, Object value) {
4913 throw new UnsupportedOperationException();
4914 }
4915
4916 @Override
4917 public boolean replace(K key, V oldValue, V newValue) {
4918 throw new UnsupportedOperationException();
4919 }
4920
4921 @Override
4922 public V replace(K key, V value) {
4923 throw new UnsupportedOperationException();
4924 }
4925
4926 @Override
4927 public V computeIfAbsent(K key,
4928 Function<? super K, ? extends V> mappingFunction) {
4929 throw new UnsupportedOperationException();
4930 }
4931
4932 @Override
4933 public V computeIfPresent(K key,
4934 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
4935 throw new UnsupportedOperationException();
4936 }
4937
4938 @Override
4939 public V compute(K key,
4940 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
4941 throw new UnsupportedOperationException();
4942 }
4943
4944 @Override
4945 public V merge(K key, V value,
4946 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
4947 throw new UnsupportedOperationException();
4948 }
4949
4950 // Preserves singleton property
4951 private Object readResolve() {
4952 return EMPTY_MAP;
4953 }
4954 }
4955
4956 private static class EmptyNavigableMap<K,V> extends EmptyMap<K,V>
4957 implements NavigableMap<K,V>, Serializable {
4958
4959 EmptyNavigableMap() {
4960
4961 }
4962
4963 // Preserves singleton property
4964 private Object readResolve() {
4965 return Collections.emptyNavigableMap();
4966 }
4967
4968 @Override
4969 public Entry<K, V> lowerEntry(K key) {
4970 return null;
4971 }
4972
4973 @Override
4974 public K lowerKey(K key) {
4975 return null;
4976 }
4977
4978 @Override
4979 public Entry<K, V> floorEntry(K key) {
4980 return null;
4981 }
4982
4983 @Override
4984 public K floorKey(K key) {
4985 return null;
4986 }
4987
4988 @Override
4989 public Entry<K, V> ceilingEntry(K key) {
4990 return null;
4991 }
4992
4993 @Override
4994 public K ceilingKey(K key) {
4995 return null;
4996 }
4997
4998 @Override
4999 public Entry<K, V> higherEntry(K key) {
5000 return null;
5001 }
5002
5003 @Override
5004 public K higherKey(K key) {
5005 return null;
5006 }
5007
5008 @Override
5009 public Entry<K, V> firstEntry() {
5010 return null;
5011 }
5012
5013 @Override
5014 public Entry<K, V> lastEntry() {
5015 return null;
5016 }
5017
5018 @Override
5019 public Entry<K, V> pollFirstEntry() {
5020 throw new UnsupportedOperationException();
5021 }
5022
5023 @Override
5024 public Entry<K, V> pollLastEntry() {
5025 throw new UnsupportedOperationException();
5026 }
5027
5028 @Override
5029 public NavigableMap<K, V> descendingMap() {
5030 return new BoundedEmptyNavigableMap<>(null, true, null, true, true);
5031 }
5032
5033 @Override
5034 public NavigableSet<K> navigableKeySet() {
5035 return Collections.emptyNavigableSet();
5036 }
5037
5038 @Override
5039 public NavigableSet<K> descendingKeySet() {
5040 return Collections.<K>emptyNavigableSet().descendingSet();
5041 }
5042
5043 @Override
5044 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
5045 return new BoundedEmptyNavigableMap<>((Comparable<K>) fromKey, fromInclusive, (Comparable<K>) toKey, toInclusive, false);
5046 }
5047
5048 @Override
5049 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
5050 return new BoundedEmptyNavigableMap<>(null, false, (Comparable<K>) toKey, inclusive, false);
5051 }
5052
5053 @Override
5054 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
5055 return new BoundedEmptyNavigableMap<>((Comparable<K>) fromKey, inclusive, null, false, false);
5056 }
5057
5058 @Override
5059 public SortedMap<K, V> subMap(K fromKey, K toKey) {
5060 return subMap(fromKey, true, toKey, false);
5061 }
5062
5063 @Override
5064 public SortedMap<K, V> headMap(K toKey) {
5065 return headMap(toKey, false);
5066 }
5067
5068 @Override
5069 public SortedMap<K, V> tailMap(K fromKey) {
5070 return tailMap(fromKey, true);
5071 }
5072
5073 @Override
5074 public Comparator<? super K> comparator() {
5075 return null;
5076 }
5077
5078 @Override
5079 public K firstKey() {
5080 return null;
5081 }
5082
5083 @Override
5084 public K lastKey() {
5085 return null;
5086 }
5087 }
5088
5089 // Singleton collections
5090
5091 /**
5092 * Returns an immutable set containing only the specified object.
5093 * The returned set is serializable.
5094 *
5095 * @param o the sole object to be stored in the returned set.
5096 * @return an immutable set containing only the specified object.
5097 */
5098 public static <T> Set<T> singleton(T o) {
5099 return new SingletonSet<>(o);
5100 }
5101
5102 static <E> Iterator<E> singletonIterator(final E e) {
5103 return new Iterator<E>() {
5104 private boolean hasNext = true;
5105 public boolean hasNext() {
5106 return hasNext;
5107 }
5108 public E next() {
5109 if (hasNext) {
5110 hasNext = false;
5111 return e;
5112 }
5113 throw new NoSuchElementException();
5114 }
5115 public void remove() {
5116 throw new UnsupportedOperationException();
5117 }
5118 @Override
5119 public void forEachRemaining(Consumer<? super E> action) {
5120 Objects.requireNonNull(action);
5121 if (hasNext) {
5122 action.accept(e);
5123 hasNext = false;
5124 }
5125 }
5126 };
5127 }
5128
5129 /**
5130 * Creates a {@code Spliterator} with only the specified element
5131 *
5132 * @param <T> Type of elements
5133 * @return A singleton {@code Spliterator}
5134 */
5135 static <T> Spliterator<T> singletonSpliterator(final T element) {
5136 return new Spliterator<T>() {
5137 long est = 1;
5138
5139 @Override
5140 public Spliterator<T> trySplit() {
5141 return null;
5142 }
5143
5144 @Override
5145 public boolean tryAdvance(Consumer<? super T> consumer) {
5146 Objects.requireNonNull(consumer);
5147 if (est > 0) {
5148 est--;
5149 consumer.accept(element);
5150 return true;
5151 }
5152 return false;
5153 }
5154
5155 @Override
5156 public void forEachRemaining(Consumer<? super T> consumer) {
5157 tryAdvance(consumer);
5158 }
5159
5160 @Override
5161 public long estimateSize() {
5162 return est;
5163 }
5164
5165 @Override
5166 public int characteristics() {
5167 int value = (element != null) ? Spliterator.NONNULL : 0;
5168
5169 return value | Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE |
5170 Spliterator.DISTINCT | Spliterator.ORDERED;
5171 }
5172 };
5173 }
5174
5175 /**
5176 * @serial include
5177 */
5178 private static class SingletonSet<E>
5179 extends AbstractSet<E>
5180 implements Serializable
5181 {
5182 private static final long serialVersionUID = 3193687207550431679L;
5183
5184 private final E element;
5185
5186 SingletonSet(E e) {element = e;}
5187
5188 public Iterator<E> iterator() {
5189 return singletonIterator(element);
5190 }
5191
5192 public int size() {return 1;}
5193
5194 public boolean contains(Object o) {return eq(o, element);}
5195
5196 // Override default methods for Collection
5197 @Override
5198 public void forEach(Consumer<? super E> action) {
5199 action.accept(element);
5200 }
5201 @Override
5202 public Spliterator<E> spliterator() {
5203 return singletonSpliterator(element);
5204 }
5205 @Override
5206 public boolean removeIf(Predicate<? super E> filter) {
5207 throw new UnsupportedOperationException();
5208 }
5209 }
5210
5211 /**
5212 * Returns an immutable list containing only the specified object.
5213 * The returned list is serializable.
5214 *
5215 * @param o the sole object to be stored in the returned list.
5216 * @return an immutable list containing only the specified object.
5217 * @since 1.3
5218 */
5219 public static <T> List<T> singletonList(T o) {
5220 return new SingletonList<>(o);
5221 }
5222
5223 /**
5224 * @serial include
5225 */
5226 private static class SingletonList<E>
5227 extends AbstractList<E>
5228 implements RandomAccess, Serializable {
5229
5230 private static final long serialVersionUID = 3093736618740652951L;
5231
5232 private final E element;
5233
5234 SingletonList(E obj) {element = obj;}
5235
5236 public Iterator<E> iterator() {
5237 return singletonIterator(element);
5238 }
5239
5240 public int size() {return 1;}
5241
5242 public boolean contains(Object obj) {return eq(obj, element);}
5243
5244 public E get(int index) {
5245 if (index != 0)
5246 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
5247 return element;
5248 }
5249
5250 // Override default methods for Collection
5251 @Override
5252 public void forEach(Consumer<? super E> action) {
5253 action.accept(element);
5254 }
5255 @Override
5256 public boolean removeIf(Predicate<? super E> filter) {
5257 throw new UnsupportedOperationException();
5258 }
5259 @Override
5260 public void replaceAll(UnaryOperator<E> operator) {
5261 throw new UnsupportedOperationException();
5262 }
5263 @Override
5264 public void sort(Comparator<? super E> c) {
5265 }
5266 @Override
5267 public Spliterator<E> spliterator() {
5268 return singletonSpliterator(element);
5269 }
5270 }
5271
5272 /**
5273 * Returns an immutable map, mapping only the specified key to the
5274 * specified value. The returned map is serializable.
5275 *
5276 * @param key the sole key to be stored in the returned map.
5277 * @param value the value to which the returned map maps <tt>key</tt>.
5278 * @return an immutable map containing only the specified key-value
5279 * mapping.
5280 * @since 1.3
5281 */
5282 public static <K,V> Map<K,V> singletonMap(K key, V value) {
5283 return new SingletonMap<>(key, value);
5284 }
5285
5286 /**
5287 * @serial include
5288 */
5289 private static class SingletonMap<K,V>
5290 extends AbstractMap<K,V>
5291 implements Serializable {
5292 private static final long serialVersionUID = -6979724477215052911L;
5293
5294 private final K k;
5295 private final V v;
5296
5297 SingletonMap(K key, V value) {
5298 k = key;
5299 v = value;
5300 }
5301
5302 public int size() {return 1;}
5303
5304 public boolean isEmpty() {return false;}
5305
5306 public boolean containsKey(Object key) {return eq(key, k);}
5307
5308 public boolean containsValue(Object value) {return eq(value, v);}
5309
5310 public V get(Object key) {return (eq(key, k) ? v : null);}
5311
5312 private transient Set<K> keySet = null;
5313 private transient Set<Map.Entry<K,V>> entrySet = null;
5314 private transient Collection<V> values = null;
5315
5316 public Set<K> keySet() {
5317 if (keySet==null)
5318 keySet = singleton(k);
5319 return keySet;
5320 }
5321
5322 public Set<Map.Entry<K,V>> entrySet() {
5323 if (entrySet==null)
5324 entrySet = Collections.<Map.Entry<K,V>>singleton(
5325 new SimpleImmutableEntry<>(k, v));
5326 return entrySet;
5327 }
5328
5329 public Collection<V> values() {
5330 if (values==null)
5331 values = singleton(v);
5332 return values;
5333 }
5334
5335 // Override default methods in Map
5336 @Override
5337 public V getOrDefault(Object key, V defaultValue) {
5338 return eq(key, k) ? v : defaultValue;
5339 }
5340
5341 @Override
5342 public void forEach(BiConsumer<? super K, ? super V> action) {
5343 action.accept(k, v);
5344 }
5345
5346 @Override
5347 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
5348 throw new UnsupportedOperationException();
5349 }
5350
5351 @Override
5352 public V putIfAbsent(K key, V value) {
5353 throw new UnsupportedOperationException();
5354 }
5355
5356 @Override
5357 public boolean remove(Object key, Object value) {
5358 throw new UnsupportedOperationException();
5359 }
5360
5361 @Override
5362 public boolean replace(K key, V oldValue, V newValue) {
5363 throw new UnsupportedOperationException();
5364 }
5365
5366 @Override
5367 public V replace(K key, V value) {
5368 throw new UnsupportedOperationException();
5369 }
5370
5371 @Override
5372 public V computeIfAbsent(K key,
5373 Function<? super K, ? extends V> mappingFunction) {
5374 throw new UnsupportedOperationException();
5375 }
5376
5377 @Override
5378 public V computeIfPresent(K key,
5379 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
5380 throw new UnsupportedOperationException();
5381 }
5382
5383 @Override
5384 public V compute(K key,
5385 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
5386 throw new UnsupportedOperationException();
5387 }
5388
5389 @Override
5390 public V merge(K key, V value,
5391 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
5392 throw new UnsupportedOperationException();
5393 }
5394 }
5395
5396 // Miscellaneous
5397
5398 /**
5399 * Returns an immutable list consisting of <tt>n</tt> copies of the
5400 * specified object. The newly allocated data object is tiny (it contains
5401 * a single reference to the data object). This method is useful in
5402 * combination with the <tt>List.addAll</tt> method to grow lists.
5403 * The returned list is serializable.
5404 *
5405 * @param n the number of elements in the returned list.
5406 * @param o the element to appear repeatedly in the returned list.
5407 * @return an immutable list consisting of <tt>n</tt> copies of the
5408 * specified object.
5409 * @throws IllegalArgumentException if {@code n < 0}
5410 * @see List#addAll(Collection)
5411 * @see List#addAll(int, Collection)
5412 */
5413 public static <T> List<T> nCopies(int n, T o) {
5414 if (n < 0)
5415 throw new IllegalArgumentException("List length = " + n);
5416 return new CopiesList<>(n, o);
5417 }
5418
5419 /**
5420 * @serial include
5421 */
5422 private static class CopiesList<E>
5423 extends AbstractList<E>
5424 implements RandomAccess, Serializable
5425 {
5426 private static final long serialVersionUID = 2739099268398711800L;
5427
5428 final int n;
5429 final E element;
5430
5431 CopiesList(int n, E e) {
5432 assert n >= 0;
5433 this.n = n;
5434 element = e;
5435 }
5436
5437 public int size() {
5438 return n;
5439 }
5440
5441 public boolean contains(Object obj) {
5442 return n != 0 && eq(obj, element);
5443 }
5444
5445 public int indexOf(Object o) {
5446 return contains(o) ? 0 : -1;
5447 }
5448
5449 public int lastIndexOf(Object o) {
5450 return contains(o) ? n - 1 : -1;
5451 }
5452
5453 public E get(int index) {
5454 if (index < 0 || index >= n)
5455 throw new IndexOutOfBoundsException("Index: "+index+
5456 ", Size: "+n);
5457 return element;
5458 }
5459
5460 public Object[] toArray() {
5461 final Object[] a = new Object[n];
5462 if (element != null)
5463 Arrays.fill(a, 0, n, element);
5464 return a;
5465 }
5466
5467 @SuppressWarnings("unchecked")
5468 public <T> T[] toArray(T[] a) {
5469 final int n = this.n;
5470 if (a.length < n) {
5471 a = (T[])java.lang.reflect.Array
5472 .newInstance(a.getClass().getComponentType(), n);
5473 if (element != null)
5474 Arrays.fill(a, 0, n, element);
5475 } else {
5476 Arrays.fill(a, 0, n, element);
5477 if (a.length > n)
5478 a[n] = null;
5479 }
5480 return a;
5481 }
5482
5483 public List<E> subList(int fromIndex, int toIndex) {
5484 if (fromIndex < 0)
5485 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
5486 if (toIndex > n)
5487 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
5488 if (fromIndex > toIndex)
5489 throw new IllegalArgumentException("fromIndex(" + fromIndex +
5490 ") > toIndex(" + toIndex + ")");
5491 return new CopiesList<>(toIndex - fromIndex, element);
5492 }
5493 }
5494
5495 /**
5496 * Returns a comparator that imposes the reverse of the <em>natural
5497 * ordering</em> on a collection of objects that implement the
5498 * {@code Comparable} interface. (The natural ordering is the ordering
5499 * imposed by the objects' own {@code compareTo} method.) This enables a
5500 * simple idiom for sorting (or maintaining) collections (or arrays) of
5501 * objects that implement the {@code Comparable} interface in
5502 * reverse-natural-order. For example, suppose {@code a} is an array of
5503 * strings. Then: <pre>
5504 * Arrays.sort(a, Collections.reverseOrder());
5505 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
5506 *
5507 * The returned comparator is serializable.
5508 *
5509 * @return A comparator that imposes the reverse of the <i>natural
5510 * ordering</i> on a collection of objects that implement
5511 * the <tt>Comparable</tt> interface.
5512 * @see Comparable
5513 */
5514 @SuppressWarnings("unchecked")
5515 public static <T> Comparator<T> reverseOrder() {
5516 return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
5517 }
5518
5519 /**
5520 * @serial include
5521 */
5522 private static class ReverseComparator
5523 implements Comparator<Comparable<Object>>, Serializable {
5524
5525 private static final long serialVersionUID = 7207038068494060240L;
5526
5527 static final ReverseComparator REVERSE_ORDER
5528 = new ReverseComparator();
5529
5530 public int compare(Comparable<Object> c1, Comparable<Object> c2) {
5531 return c2.compareTo(c1);
5532 }
5533
5534 private Object readResolve() { return Collections.reverseOrder(); }
5535 }
5536
5537 /**
5538 * Returns a comparator that imposes the reverse ordering of the specified
5539 * comparator. If the specified comparator is {@code null}, this method is
5540 * equivalent to {@link #reverseOrder()} (in other words, it returns a
5541 * comparator that imposes the reverse of the <em>natural ordering</em> on
5542 * a collection of objects that implement the Comparable interface).
5543 *
5544 * <p>The returned comparator is serializable (assuming the specified
5545 * comparator is also serializable or {@code null}).
5546 *
5547 * @param cmp a comparator who's ordering is to be reversed by the returned
5548 * comparator or {@code null}
5549 * @return A comparator that imposes the reverse ordering of the
5550 * specified comparator.
5551 * @since 1.5
5552 */
5553 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
5554 if (cmp == null)
5555 return reverseOrder();
5556
5557 if (cmp instanceof ReverseComparator2)
5558 return ((ReverseComparator2<T>)cmp).cmp;
5559
5560 return new ReverseComparator2<>(cmp);
5561 }
5562
5563 /**
5564 * @serial include
5565 */
5566 private static class ReverseComparator2<T> implements Comparator<T>,
5567 Serializable
5568 {
5569 private static final long serialVersionUID = 4374092139857L;
5570
5571 /**
5572 * The comparator specified in the static factory. This will never
5573 * be null, as the static factory returns a ReverseComparator
5574 * instance if its argument is null.
5575 *
5576 * @serial
5577 */
5578 final Comparator<T> cmp;
5579
5580 ReverseComparator2(Comparator<T> cmp) {
5581 assert cmp != null;
5582 this.cmp = cmp;
5583 }
5584
5585 public int compare(T t1, T t2) {
5586 return cmp.compare(t2, t1);
5587 }
5588
5589 public boolean equals(Object o) {
5590 return (o == this) ||
5591 (o instanceof ReverseComparator2 &&
5592 cmp.equals(((ReverseComparator2)o).cmp));
5593 }
5594
5595 public int hashCode() {
5596 return cmp.hashCode() ^ Integer.MIN_VALUE;
5597 }
5598 }
5599
5600 /**
5601 * Returns an enumeration over the specified collection. This provides
5602 * interoperability with legacy APIs that require an enumeration
5603 * as input.
5604 *
5605 * @param c the collection for which an enumeration is to be returned.
5606 * @return an enumeration over the specified collection.
5607 * @see Enumeration
5608 */
5609 public static <T> Enumeration<T> enumeration(final Collection<T> c) {
5610 return new Enumeration<T>() {
5611 private final Iterator<T> i = c.iterator();
5612
5613 public boolean hasMoreElements() {
5614 return i.hasNext();
5615 }
5616
5617 public T nextElement() {
5618 return i.next();
5619 }
5620 };
5621 }
5622
5623 /**
5624 * Returns an array list containing the elements returned by the
5625 * specified enumeration in the order they are returned by the
5626 * enumeration. This method provides interoperability between
5627 * legacy APIs that return enumerations and new APIs that require
5628 * collections.
5629 *
5630 * @param e enumeration providing elements for the returned
5631 * array list
5632 * @return an array list containing the elements returned
5633 * by the specified enumeration.
5634 * @since 1.4
5635 * @see Enumeration
5636 * @see ArrayList
5637 */
5638 public static <T> ArrayList<T> list(Enumeration<T> e) {
5639 ArrayList<T> l = new ArrayList<>();
5640 while (e.hasMoreElements())
5641 l.add(e.nextElement());
5642 return l;
5643 }
5644
5645 /**
5646 * Returns true if the specified arguments are equal, or both null.
5647 */
5648 static boolean eq(Object o1, Object o2) {
5649 return o1==null ? o2==null : o1.equals(o2);
5650 }
5651
5652 /**
5653 * Returns the number of elements in the specified collection equal to the
5654 * specified object. More formally, returns the number of elements
5655 * <tt>e</tt> in the collection such that
5656 * <tt>(o == null ? e == null : o.equals(e))</tt>.
5657 *
5658 * @param c the collection in which to determine the frequency
5659 * of <tt>o</tt>
5660 * @param o the object whose frequency is to be determined
5661 * @throws NullPointerException if <tt>c</tt> is null
5662 * @since 1.5
5663 */
5664 public static int frequency(Collection<?> c, Object o) {
5665 int result = 0;
5666 if (o == null) {
5667 for (Object e : c)
5668 if (e == null)
5669 result++;
5670 } else {
5671 for (Object e : c)
5672 if (o.equals(e))
5673 result++;
5674 }
5675 return result;
5676 }
5677
5678 /**
5679 * Returns {@code true} if the two specified collections have no
5680 * elements in common.
5681 *
5682 * <p>Care must be exercised if this method is used on collections that
5683 * do not comply with the general contract for {@code Collection}.
5684 * Implementations may elect to iterate over either collection and test
5685 * for containment in the other collection (or to perform any equivalent
5686 * computation). If either collection uses a nonstandard equality test
5687 * (as does a {@link SortedSet} whose ordering is not <em>compatible with
5688 * equals</em>, or the key set of an {@link IdentityHashMap}), both
5689 * collections must use the same nonstandard equality test, or the
5690 * result of this method is undefined.
5691 *
5692 * <p>Care must also be exercised when using collections that have
5693 * restrictions on the elements that they may contain. Collection
5694 * implementations are allowed to throw exceptions for any operation
5695 * involving elements they deem ineligible. For absolute safety the
5696 * specified collections should contain only elements which are
5697 * eligible elements for both collections.
5698 *
5699 * <p>Note that it is permissible to pass the same collection in both
5700 * parameters, in which case the method will return {@code true} if and
5701 * only if the collection is empty.
5702 *
5703 * @param c1 a collection
5704 * @param c2 a collection
5705 * @return {@code true} if the two specified collections have no
5706 * elements in common.
5707 * @throws NullPointerException if either collection is {@code null}.
5708 * @throws NullPointerException if one collection contains a {@code null}
5709 * element and {@code null} is not an eligible element for the other collection.
5710 * (<a href="Collection.html#optional-restrictions">optional</a>)
5711 * @throws ClassCastException if one collection contains an element that is
5712 * of a type which is ineligible for the other collection.
5713 * (<a href="Collection.html#optional-restrictions">optional</a>)
5714 * @since 1.5
5715 */
5716 public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
5717 // The collection to be used for contains(). Preference is given to
5718 // the collection who's contains() has lower O() complexity.
5719 Collection<?> contains = c2;
5720 // The collection to be iterated. If the collections' contains() impl
5721 // are of different O() complexity, the collection with slower
5722 // contains() will be used for iteration. For collections who's
5723 // contains() are of the same complexity then best performance is
5724 // achieved by iterating the smaller collection.
5725 Collection<?> iterate = c1;
5726
5727 // Performance optimization cases. The heuristics:
5728 // 1. Generally iterate over c1.
5729 // 2. If c1 is a Set then iterate over c2.
5730 // 3. If either collection is empty then result is always true.
5731 // 4. Iterate over the smaller Collection.
5732 if (c1 instanceof Set) {
5733 // Use c1 for contains as a Set's contains() is expected to perform
5734 // better than O(N/2)
5735 iterate = c2;
5736 contains = c1;
5737 } else if (!(c2 instanceof Set)) {
5738 // Both are mere Collections. Iterate over smaller collection.
5739 // Example: If c1 contains 3 elements and c2 contains 50 elements and
5740 // assuming contains() requires ceiling(N/2) comparisons then
5741 // checking for all c1 elements in c2 would require 75 comparisons
5742 // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring
5743 // 100 comparisons (50 * ceiling(3/2)).
5744 int c1size = c1.size();
5745 int c2size = c2.size();
5746 if (c1size == 0 || c2size == 0) {
5747 // At least one collection is empty. Nothing will match.
5748 return true;
5749 }
5750
5751 if (c1size > c2size) {
5752 iterate = c2;
5753 contains = c1;
5754 }
5755 }
5756
5757 for (Object e : iterate) {
5758 if (contains.contains(e)) {
5759 // Found a common element. Collections are not disjoint.
5760 return false;
5761 }
5762 }
5763
5764 // No common elements were found.
5765 return true;
5766 }
5767
5768 /**
5769 * Adds all of the specified elements to the specified collection.
5770 * Elements to be added may be specified individually or as an array.
5771 * The behavior of this convenience method is identical to that of
5772 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely
5773 * to run significantly faster under most implementations.
5774 *
5775 * <p>When elements are specified individually, this method provides a
5776 * convenient way to add a few elements to an existing collection:
5777 * <pre>
5778 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
5779 * </pre>
5780 *
5781 * @param c the collection into which <tt>elements</tt> are to be inserted
5782 * @param elements the elements to insert into <tt>c</tt>
5783 * @return <tt>true</tt> if the collection changed as a result of the call
5784 * @throws UnsupportedOperationException if <tt>c</tt> does not support
5785 * the <tt>add</tt> operation
5786 * @throws NullPointerException if <tt>elements</tt> contains one or more
5787 * null values and <tt>c</tt> does not permit null elements, or
5788 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
5789 * @throws IllegalArgumentException if some property of a value in
5790 * <tt>elements</tt> prevents it from being added to <tt>c</tt>
5791 * @see Collection#addAll(Collection)
5792 * @since 1.5
5793 */
5794 @SafeVarargs
5795 public static <T> boolean addAll(Collection<? super T> c, T... elements) {
5796 boolean result = false;
5797 for (T element : elements)
5798 result |= c.add(element);
5799 return result;
5800 }
5801
5802 /**
5803 * Returns a set backed by the specified map. The resulting set displays
5804 * the same ordering, concurrency, and performance characteristics as the
5805 * backing map. In essence, this factory method provides a {@link Set}
5806 * implementation corresponding to any {@link Map} implementation. There
5807 * is no need to use this method on a {@link Map} implementation that
5808 * already has a corresponding {@link Set} implementation (such as {@link
5809 * HashMap} or {@link TreeMap}).
5810 *
5811 * <p>Each method invocation on the set returned by this method results in
5812 * exactly one method invocation on the backing map or its <tt>keySet</tt>
5813 * view, with one exception. The <tt>addAll</tt> method is implemented
5814 * as a sequence of <tt>put</tt> invocations on the backing map.
5815 *
5816 * <p>The specified map must be empty at the time this method is invoked,
5817 * and should not be accessed directly after this method returns. These
5818 * conditions are ensured if the map is created empty, passed directly
5819 * to this method, and no reference to the map is retained, as illustrated
5820 * in the following code fragment:
5821 * <pre>
5822 * Set<Object> weakHashSet = Collections.newSetFromMap(
5823 * new WeakHashMap<Object, Boolean>());
5824 * </pre>
5825 *
5826 * @param map the backing map
5827 * @return the set backed by the map
5828 * @throws IllegalArgumentException if <tt>map</tt> is not empty
5829 * @since 1.6
5830 */
5831 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
5832 return new SetFromMap<>(map);
5833 }
5834
5835 /**
5836 * @serial include
5837 */
5838 private static class SetFromMap<E> extends AbstractSet<E>
5839 implements Set<E>, Serializable
5840 {
5841 private final Map<E, Boolean> m; // The backing map
5842 private transient Set<E> s; // Its keySet
5843
5844 SetFromMap(Map<E, Boolean> map) {
5845 if (!map.isEmpty())
5846 throw new IllegalArgumentException("Map is non-empty");
5847 m = map;
5848 s = map.keySet();
5849 }
5850
5851 public void clear() { m.clear(); }
5852 public int size() { return m.size(); }
5853 public boolean isEmpty() { return m.isEmpty(); }
5854 public boolean contains(Object o) { return m.containsKey(o); }
5855 public boolean remove(Object o) { return m.remove(o) != null; }
5856 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
5857 public Iterator<E> iterator() { return s.iterator(); }
5858 public Object[] toArray() { return s.toArray(); }
5859 public <T> T[] toArray(T[] a) { return s.toArray(a); }
5860 public String toString() { return s.toString(); }
5861 public int hashCode() { return s.hashCode(); }
5862 public boolean equals(Object o) { return o == this || s.equals(o); }
5863 public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
5864 public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
5865 public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
5866 // addAll is the only inherited implementation
5867
5868 // Override default methods in Collection
5869 @Override
5870 public void forEach(Consumer<? super E> action) {
5871 s.forEach(action);
5872 }
5873 @Override
5874 public boolean removeIf(Predicate<? super E> filter) {
5875 return s.removeIf(filter);
5876 }
5877
5878 @Override
5879 public Spliterator<E> spliterator() {return s.spliterator();}
5880
5881 private static final long serialVersionUID = 2454657854757543876L;
5882
5883 private void readObject(java.io.ObjectInputStream stream)
5884 throws IOException, ClassNotFoundException
5885 {
5886 stream.defaultReadObject();
5887 s = m.keySet();
5888 }
5889 }
5890
5891 /**
5892 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
5893 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
5894 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
5895 * view can be useful when you would like to use a method
5896 * requiring a <tt>Queue</tt> but you need Lifo ordering.
5897 *
5898 * <p>Each method invocation on the queue returned by this method
5899 * results in exactly one method invocation on the backing deque, with
5900 * one exception. The {@link Queue#addAll addAll} method is
5901 * implemented as a sequence of {@link Deque#addFirst addFirst}
5902 * invocations on the backing deque.
5903 *
5904 * @param deque the deque
5905 * @return the queue
5906 * @since 1.6
5907 */
5908 public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
5909 return new AsLIFOQueue<>(deque);
5910 }
5911
5912 /**
5913 * @serial include
5914 */
5915 static class AsLIFOQueue<E> extends AbstractQueue<E>
5916 implements Queue<E>, Serializable {
5917 private static final long serialVersionUID = 1802017725587941708L;
5918 private final Deque<E> q;
5919 AsLIFOQueue(Deque<E> q) { this.q = q; }
5920 public boolean add(E e) { q.addFirst(e); return true; }
5921 public boolean offer(E e) { return q.offerFirst(e); }
5922 public E poll() { return q.pollFirst(); }
5923 public E remove() { return q.removeFirst(); }
5924 public E peek() { return q.peekFirst(); }
5925 public E element() { return q.getFirst(); }
5926 public void clear() { q.clear(); }
5927 public int size() { return q.size(); }
5928 public boolean isEmpty() { return q.isEmpty(); }
5929 public boolean contains(Object o) { return q.contains(o); }
5930 public boolean remove(Object o) { return q.remove(o); }
5931 public Iterator<E> iterator() { return q.iterator(); }
5932 public Object[] toArray() { return q.toArray(); }
5933 public <T> T[] toArray(T[] a) { return q.toArray(a); }
5934 public String toString() { return q.toString(); }
5935 public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
5936 public boolean removeAll(Collection<?> c) {return q.removeAll(c);}
5937 public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
5938 // We use inherited addAll; forwarding addAll would be wrong
5939
5940 // Override default methods in Collection
5941 @Override
5942 public void forEach(Consumer<? super E> action) {q.forEach(action);}
5943 @Override
5944 public Spliterator<E> spliterator() {return q.spliterator();}
5945 @Override
5946 public boolean removeIf(Predicate<? super E> filter) {
5947 return q.removeIf(filter);
5948 }
5949 }
5950 }