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 {@code source.subList(i, i+target.size()).equals(target)},
928 * or -1 if there is no such index. (Returns -1 if
929 * {@code target.size() > source.size()})
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 {@code source.subList(i, i+target.size()).equals(target)},
981 * or -1 if there is no such index. (Returns -1 if
982 * {@code target.size() > source.size()})
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 list. This method allows
1216 * modules to provide users with "read-only" access to internal
1217 * lists. Query operations on the returned list "read through" to the
1218 * specified list, and attempts to modify the returned list, whether
1219 * direct or via its iterator, result in an
1220 * <tt>UnsupportedOperationException</tt>.<p>
1221 *
1222 * The returned list will be serializable if the specified list
1223 * is serializable. Similarly, the returned list will implement
1224 * {@link RandomAccess} if the specified list does.
1225 *
1226 * @param list the list for which an unmodifiable view is to be returned.
1227 * @return an unmodifiable view of the specified list.
1228 */
1229 public static <T> List<T> unmodifiableList(List<? extends T> list) {
1230 return (list instanceof RandomAccess ?
1231 new UnmodifiableRandomAccessList<>(list) :
1232 new UnmodifiableList<>(list));
1233 }
1234
1235 /**
1236 * @serial include
1237 */
1238 static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1239 implements List<E> {
1240 private static final long serialVersionUID = -283967356065247728L;
1241 final List<? extends E> list;
1242
1243 UnmodifiableList(List<? extends E> list) {
1244 super(list);
1245 this.list = list;
1246 }
1247
1248 public boolean equals(Object o) {return o == this || list.equals(o);}
1249 public int hashCode() {return list.hashCode();}
1250
1251 public E get(int index) {return list.get(index);}
1252 public E set(int index, E element) {
1253 throw new UnsupportedOperationException();
1254 }
1255 public void add(int index, E element) {
1256 throw new UnsupportedOperationException();
1257 }
1258 public E remove(int index) {
1259 throw new UnsupportedOperationException();
1260 }
1261 public int indexOf(Object o) {return list.indexOf(o);}
1262 public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1263 public boolean addAll(int index, Collection<? extends E> c) {
1264 throw new UnsupportedOperationException();
1265 }
1266
1267 @Override
1268 public void replaceAll(UnaryOperator<E> operator) {
1269 throw new UnsupportedOperationException();
1270 }
1271 @Override
1272 public void sort(Comparator<? super E> c) {
1273 throw new UnsupportedOperationException();
1274 }
1275
1276 public ListIterator<E> listIterator() {return listIterator(0);}
1277
1278 public ListIterator<E> listIterator(final int index) {
1279 return new ListIterator<E>() {
1280 private final ListIterator<? extends E> i
1281 = list.listIterator(index);
1282
1283 public boolean hasNext() {return i.hasNext();}
1284 public E next() {return i.next();}
1285 public boolean hasPrevious() {return i.hasPrevious();}
1286 public E previous() {return i.previous();}
1287 public int nextIndex() {return i.nextIndex();}
1288 public int previousIndex() {return i.previousIndex();}
1289
1290 public void remove() {
1291 throw new UnsupportedOperationException();
1292 }
1293 public void set(E e) {
1294 throw new UnsupportedOperationException();
1295 }
1296 public void add(E e) {
1297 throw new UnsupportedOperationException();
1298 }
1299
1300 @Override
1301 public void forEachRemaining(Consumer<? super E> action) {
1302 i.forEachRemaining(action);
1303 }
1304 };
1305 }
1306
1307 public List<E> subList(int fromIndex, int toIndex) {
1308 return new UnmodifiableList<>(list.subList(fromIndex, toIndex));
1309 }
1310
1311 /**
1312 * UnmodifiableRandomAccessList instances are serialized as
1313 * UnmodifiableList instances to allow them to be deserialized
1314 * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
1315 * This method inverts the transformation. As a beneficial
1316 * side-effect, it also grafts the RandomAccess marker onto
1317 * UnmodifiableList instances that were serialized in pre-1.4 JREs.
1318 *
1319 * Note: Unfortunately, UnmodifiableRandomAccessList instances
1320 * serialized in 1.4.1 and deserialized in 1.4 will become
1321 * UnmodifiableList instances, as this method was missing in 1.4.
1322 */
1323 private Object readResolve() {
1324 return (list instanceof RandomAccess
1325 ? new UnmodifiableRandomAccessList<>(list)
1326 : this);
1327 }
1328 }
1329
1330 /**
1331 * @serial include
1332 */
1333 static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E>
1334 implements RandomAccess
1335 {
1336 UnmodifiableRandomAccessList(List<? extends E> list) {
1337 super(list);
1338 }
1339
1340 public List<E> subList(int fromIndex, int toIndex) {
1341 return new UnmodifiableRandomAccessList<>(
1342 list.subList(fromIndex, toIndex));
1343 }
1344
1345 private static final long serialVersionUID = -2542308836966382001L;
1346
1347 /**
1348 * Allows instances to be deserialized in pre-1.4 JREs (which do
1349 * not have UnmodifiableRandomAccessList). UnmodifiableList has
1350 * a readResolve method that inverts this transformation upon
1351 * deserialization.
1352 */
1353 private Object writeReplace() {
1354 return new UnmodifiableList<>(list);
1355 }
1356 }
1357
1358 /**
1359 * Returns an unmodifiable view of the specified map. This method
1360 * allows modules to provide users with "read-only" access to internal
1361 * maps. Query operations on the returned map "read through"
1362 * to the specified map, and attempts to modify the returned
1363 * map, whether direct or via its collection views, result in an
1364 * <tt>UnsupportedOperationException</tt>.<p>
1365 *
1366 * The returned map will be serializable if the specified map
1367 * is serializable.
1368 *
1369 * @param m the map for which an unmodifiable view is to be returned.
1370 * @return an unmodifiable view of the specified map.
1371 */
1372 public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
1373 return new UnmodifiableMap<>(m);
1374 }
1375
1376 /**
1377 * @serial include
1378 */
1379 private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
1380 private static final long serialVersionUID = -1034234728574286014L;
1381
1382 private final Map<? extends K, ? extends V> m;
1383
1384 UnmodifiableMap(Map<? extends K, ? extends V> m) {
1385 if (m==null)
1386 throw new NullPointerException();
1387 this.m = m;
1388 }
1389
1390 public int size() {return m.size();}
1391 public boolean isEmpty() {return m.isEmpty();}
1392 public boolean containsKey(Object key) {return m.containsKey(key);}
1393 public boolean containsValue(Object val) {return m.containsValue(val);}
1394 public V get(Object key) {return m.get(key);}
1395
1396 public V put(K key, V value) {
1397 throw new UnsupportedOperationException();
1398 }
1399 public V remove(Object key) {
1400 throw new UnsupportedOperationException();
1401 }
1402 public void putAll(Map<? extends K, ? extends V> m) {
1403 throw new UnsupportedOperationException();
1404 }
1405 public void clear() {
1406 throw new UnsupportedOperationException();
1407 }
1408
1409 private transient Set<K> keySet = null;
1410 private transient Set<Map.Entry<K,V>> entrySet = null;
1411 private transient Collection<V> values = null;
1412
1413 public Set<K> keySet() {
1414 if (keySet==null)
1415 keySet = unmodifiableSet(m.keySet());
1416 return keySet;
1417 }
1418
1419 public Set<Map.Entry<K,V>> entrySet() {
1420 if (entrySet==null)
1421 entrySet = new UnmodifiableEntrySet<>(m.entrySet());
1422 return entrySet;
1423 }
1424
1425 public Collection<V> values() {
1426 if (values==null)
1427 values = unmodifiableCollection(m.values());
1428 return values;
1429 }
1430
1431 public boolean equals(Object o) {return o == this || m.equals(o);}
1432 public int hashCode() {return m.hashCode();}
1433 public String toString() {return m.toString();}
1434
1435 // Override default methods in Map
1436 @Override
1437 @SuppressWarnings("unchecked")
1438 public V getOrDefault(Object k, V defaultValue) {
1439 // Safe cast as we don't change the value
1440 return ((Map<K, V>)m).getOrDefault(k, defaultValue);
1441 }
1442
1443 @Override
1444 public void forEach(BiConsumer<? super K, ? super V> action) {
1445 m.forEach(action);
1446 }
1447
1448 @Override
1449 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1450 throw new UnsupportedOperationException();
1451 }
1452
1453 @Override
1454 public V putIfAbsent(K key, V value) {
1455 throw new UnsupportedOperationException();
1456 }
1457
1458 @Override
1459 public boolean remove(Object key, Object value) {
1460 throw new UnsupportedOperationException();
1461 }
1462
1463 @Override
1464 public boolean replace(K key, V oldValue, V newValue) {
1465 throw new UnsupportedOperationException();
1466 }
1467
1468 @Override
1469 public V replace(K key, V value) {
1470 throw new UnsupportedOperationException();
1471 }
1472
1473 @Override
1474 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1475 throw new UnsupportedOperationException();
1476 }
1477
1478 @Override
1479 public V computeIfPresent(K key,
1480 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1481 throw new UnsupportedOperationException();
1482 }
1483
1484 @Override
1485 public V compute(K key,
1486 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1487 throw new UnsupportedOperationException();
1488 }
1489
1490 @Override
1491 public V merge(K key, V value,
1492 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1493 throw new UnsupportedOperationException();
1494 }
1495
1496 /**
1497 * We need this class in addition to UnmodifiableSet as
1498 * Map.Entries themselves permit modification of the backing Map
1499 * via their setValue operation. This class is subtle: there are
1500 * many possible attacks that must be thwarted.
1501 *
1502 * @serial include
1503 */
1504 static class UnmodifiableEntrySet<K,V>
1505 extends UnmodifiableSet<Map.Entry<K,V>> {
1506 private static final long serialVersionUID = 7854390611657943733L;
1507
1508 @SuppressWarnings({"unchecked", "rawtypes"})
1509 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1510 // Need to cast to raw in order to work around a limitation in the type system
1511 super((Set)s);
1512 }
1513 public Iterator<Map.Entry<K,V>> iterator() {
1514 return new Iterator<Map.Entry<K,V>>() {
1515 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1516
1517 public boolean hasNext() {
1518 return i.hasNext();
1519 }
1520 public Map.Entry<K,V> next() {
1521 return new UnmodifiableEntry<>(i.next());
1522 }
1523 public void remove() {
1524 throw new UnsupportedOperationException();
1525 }
1526 };
1527 }
1528
1529 @SuppressWarnings("unchecked")
1530 public Object[] toArray() {
1531 Object[] a = c.toArray();
1532 for (int i=0; i<a.length; i++)
1533 a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]);
1534 return a;
1535 }
1536
1537 @SuppressWarnings("unchecked")
1538 public <T> T[] toArray(T[] a) {
1539 // We don't pass a to c.toArray, to avoid window of
1540 // vulnerability wherein an unscrupulous multithreaded client
1541 // could get his hands on raw (unwrapped) Entries from c.
1542 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1543
1544 for (int i=0; i<arr.length; i++)
1545 arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]);
1546
1547 if (arr.length > a.length)
1548 return (T[])arr;
1549
1550 System.arraycopy(arr, 0, a, 0, arr.length);
1551 if (a.length > arr.length)
1552 a[arr.length] = null;
1553 return a;
1554 }
1555
1556 /**
1557 * This method is overridden to protect the backing set against
1558 * an object with a nefarious equals function that senses
1559 * that the equality-candidate is Map.Entry and calls its
1560 * setValue method.
1561 */
1562 public boolean contains(Object o) {
1563 if (!(o instanceof Map.Entry))
1564 return false;
1565 return c.contains(
1566 new UnmodifiableEntry<>((Map.Entry<?,?>) o));
1567 }
1568
1569 /**
1570 * The next two methods are overridden to protect against
1571 * an unscrupulous List whose contains(Object o) method senses
1572 * when o is a Map.Entry, and calls o.setValue.
1573 */
1574 public boolean containsAll(Collection<?> coll) {
1575 for (Object e : coll) {
1576 if (!contains(e)) // Invokes safe contains() above
1577 return false;
1578 }
1579 return true;
1580 }
1581 public boolean equals(Object o) {
1582 if (o == this)
1583 return true;
1584
1585 if (!(o instanceof Set))
1586 return false;
1587 Set<?> s = (Set<?>) o;
1588 if (s.size() != c.size())
1589 return false;
1590 return containsAll(s); // Invokes safe containsAll() above
1591 }
1592
1593 /**
1594 * This "wrapper class" serves two purposes: it prevents
1595 * the client from modifying the backing Map, by short-circuiting
1596 * the setValue method, and it protects the backing Map against
1597 * an ill-behaved Map.Entry that attempts to modify another
1598 * Map Entry when asked to perform an equality check.
1599 */
1600 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
1601 private Map.Entry<? extends K, ? extends V> e;
1602
1603 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1604
1605 public K getKey() {return e.getKey();}
1606 public V getValue() {return e.getValue();}
1607 public V setValue(V value) {
1608 throw new UnsupportedOperationException();
1609 }
1610 public int hashCode() {return e.hashCode();}
1611 public boolean equals(Object o) {
1612 if (this == o)
1613 return true;
1614 if (!(o instanceof Map.Entry))
1615 return false;
1616 Map.Entry<?,?> t = (Map.Entry<?,?>)o;
1617 return eq(e.getKey(), t.getKey()) &&
1618 eq(e.getValue(), t.getValue());
1619 }
1620 public String toString() {return e.toString();}
1621 }
1622 }
1623 }
1624
1625 /**
1626 * Returns an unmodifiable view of the specified sorted map. This method
1627 * allows modules to provide users with "read-only" access to internal
1628 * sorted maps. Query operations on the returned sorted map "read through"
1629 * to the specified sorted map. Attempts to modify the returned
1630 * sorted map, whether direct, via its collection views, or via its
1631 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1632 * an <tt>UnsupportedOperationException</tt>.<p>
1633 *
1634 * The returned sorted map will be serializable if the specified sorted map
1635 * is serializable.
1636 *
1637 * @param m the sorted map for which an unmodifiable view is to be
1638 * returned.
1639 * @return an unmodifiable view of the specified sorted map.
1640 */
1641 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1642 return new UnmodifiableSortedMap<>(m);
1643 }
1644
1645 /**
1646 * @serial include
1647 */
1648 static class UnmodifiableSortedMap<K,V>
1649 extends UnmodifiableMap<K,V>
1650 implements SortedMap<K,V>, Serializable {
1651 private static final long serialVersionUID = -8806743815996713206L;
1652
1653 private final SortedMap<K, ? extends V> sm;
1654
1655 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1656
1657 public Comparator<? super K> comparator() {return sm.comparator();}
1658
1659 public SortedMap<K,V> subMap(K fromKey, K toKey) {
1660 return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey));
1661 }
1662 public SortedMap<K,V> headMap(K toKey) {
1663 return new UnmodifiableSortedMap<>(sm.headMap(toKey));
1664 }
1665 public SortedMap<K,V> tailMap(K fromKey) {
1666 return new UnmodifiableSortedMap<>(sm.tailMap(fromKey));
1667 }
1668
1669 public K firstKey() {return sm.firstKey();}
1670 public K lastKey() {return sm.lastKey();}
1671 }
1672
1673
1674 // Synch Wrappers
1675
1676 /**
1677 * Returns a synchronized (thread-safe) collection backed by the specified
1678 * collection. In order to guarantee serial access, it is critical that
1679 * <strong>all</strong> access to the backing collection is accomplished
1680 * through the returned collection.<p>
1681 *
1682 * It is imperative that the user manually synchronize on the returned
1683 * collection when traversing it via {@link Iterator} or
1684 * {@link Spliterator}:
1685 * <pre>
1686 * Collection c = Collections.synchronizedCollection(myCollection);
1687 * ...
1688 * synchronized (c) {
1689 * Iterator i = c.iterator(); // Must be in the synchronized block
1690 * while (i.hasNext())
1691 * foo(i.next());
1692 * }
1693 * </pre>
1694 * Failure to follow this advice may result in non-deterministic behavior.
1695 *
1696 * <p>The returned collection does <i>not</i> pass the {@code hashCode}
1697 * and {@code equals} operations through to the backing collection, but
1698 * relies on {@code Object}'s equals and hashCode methods. This is
1699 * necessary to preserve the contracts of these operations in the case
1700 * that the backing collection is a set or a list.<p>
1701 *
1702 * The returned collection will be serializable if the specified collection
1703 * is serializable.
1704 *
1705 * @param c the collection to be "wrapped" in a synchronized collection.
1706 * @return a synchronized view of the specified collection.
1707 */
1708 public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1709 return new SynchronizedCollection<>(c);
1710 }
1711
1712 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1713 return new SynchronizedCollection<>(c, mutex);
1714 }
1715
1716 /**
1717 * @serial include
1718 */
1719 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1720 private static final long serialVersionUID = 3053995032091335093L;
1721
1722 final Collection<E> c; // Backing Collection
1723 final Object mutex; // Object on which to synchronize
1724
1725 SynchronizedCollection(Collection<E> c) {
1726 if (c==null)
1727 throw new NullPointerException();
1728 this.c = c;
1729 mutex = this;
1730 }
1731 SynchronizedCollection(Collection<E> c, Object mutex) {
1732 this.c = c;
1733 this.mutex = mutex;
1734 }
1735
1736 public int size() {
1737 synchronized (mutex) {return c.size();}
1738 }
1739 public boolean isEmpty() {
1740 synchronized (mutex) {return c.isEmpty();}
1741 }
1742 public boolean contains(Object o) {
1743 synchronized (mutex) {return c.contains(o);}
1744 }
1745 public Object[] toArray() {
1746 synchronized (mutex) {return c.toArray();}
1747 }
1748 public <T> T[] toArray(T[] a) {
1749 synchronized (mutex) {return c.toArray(a);}
1750 }
1751
1752 public Iterator<E> iterator() {
1753 return c.iterator(); // Must be manually synched by user!
1754 }
1755
1756 public boolean add(E e) {
1757 synchronized (mutex) {return c.add(e);}
1758 }
1759 public boolean remove(Object o) {
1760 synchronized (mutex) {return c.remove(o);}
1761 }
1762
1763 public boolean containsAll(Collection<?> coll) {
1764 synchronized (mutex) {return c.containsAll(coll);}
1765 }
1766 public boolean addAll(Collection<? extends E> coll) {
1767 synchronized (mutex) {return c.addAll(coll);}
1768 }
1769 public boolean removeAll(Collection<?> coll) {
1770 synchronized (mutex) {return c.removeAll(coll);}
1771 }
1772 public boolean retainAll(Collection<?> coll) {
1773 synchronized (mutex) {return c.retainAll(coll);}
1774 }
1775 public void clear() {
1776 synchronized (mutex) {c.clear();}
1777 }
1778 public String toString() {
1779 synchronized (mutex) {return c.toString();}
1780 }
1781 // Override default methods in Collection
1782 @Override
1783 public void forEach(Consumer<? super E> consumer) {
1784 synchronized (mutex) {c.forEach(consumer);}
1785 }
1786 @Override
1787 public boolean removeIf(Predicate<? super E> filter) {
1788 synchronized (mutex) {return c.removeIf(filter);}
1789 }
1790 @Override
1791 public Spliterator<E> spliterator() {
1792 return c.spliterator(); // Must be manually synched by user!
1793 }
1794 private void writeObject(ObjectOutputStream s) throws IOException {
1795 synchronized (mutex) {s.defaultWriteObject();}
1796 }
1797 }
1798
1799 /**
1800 * Returns a synchronized (thread-safe) set backed by the specified
1801 * set. In order to guarantee serial access, it is critical that
1802 * <strong>all</strong> access to the backing set is accomplished
1803 * through the returned set.<p>
1804 *
1805 * It is imperative that the user manually synchronize on the returned
1806 * set when iterating over it:
1807 * <pre>
1808 * Set s = Collections.synchronizedSet(new HashSet());
1809 * ...
1810 * synchronized (s) {
1811 * Iterator i = s.iterator(); // Must be in the synchronized block
1812 * while (i.hasNext())
1813 * foo(i.next());
1814 * }
1815 * </pre>
1816 * Failure to follow this advice may result in non-deterministic behavior.
1817 *
1818 * <p>The returned set will be serializable if the specified set is
1819 * serializable.
1820 *
1821 * @param s the set to be "wrapped" in a synchronized set.
1822 * @return a synchronized view of the specified set.
1823 */
1824 public static <T> Set<T> synchronizedSet(Set<T> s) {
1825 return new SynchronizedSet<>(s);
1826 }
1827
1828 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1829 return new SynchronizedSet<>(s, mutex);
1830 }
1831
1832 /**
1833 * @serial include
1834 */
1835 static class SynchronizedSet<E>
1836 extends SynchronizedCollection<E>
1837 implements Set<E> {
1838 private static final long serialVersionUID = 487447009682186044L;
1839
1840 SynchronizedSet(Set<E> s) {
1841 super(s);
1842 }
1843 SynchronizedSet(Set<E> s, Object mutex) {
1844 super(s, mutex);
1845 }
1846
1847 public boolean equals(Object o) {
1848 if (this == o)
1849 return true;
1850 synchronized (mutex) {return c.equals(o);}
1851 }
1852 public int hashCode() {
1853 synchronized (mutex) {return c.hashCode();}
1854 }
1855 }
1856
1857 /**
1858 * Returns a synchronized (thread-safe) sorted set backed by the specified
1859 * sorted set. In order to guarantee serial access, it is critical that
1860 * <strong>all</strong> access to the backing sorted set is accomplished
1861 * through the returned sorted set (or its views).<p>
1862 *
1863 * It is imperative that the user manually synchronize on the returned
1864 * sorted set when iterating over it or any of its <tt>subSet</tt>,
1865 * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1866 * <pre>
1867 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1868 * ...
1869 * synchronized (s) {
1870 * Iterator i = s.iterator(); // Must be in the synchronized block
1871 * while (i.hasNext())
1872 * foo(i.next());
1873 * }
1874 * </pre>
1875 * or:
1876 * <pre>
1877 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1878 * SortedSet s2 = s.headSet(foo);
1879 * ...
1880 * synchronized (s) { // Note: s, not s2!!!
1881 * Iterator i = s2.iterator(); // Must be in the synchronized block
1882 * while (i.hasNext())
1883 * foo(i.next());
1884 * }
1885 * </pre>
1886 * Failure to follow this advice may result in non-deterministic behavior.
1887 *
1888 * <p>The returned sorted set will be serializable if the specified
1889 * sorted set is serializable.
1890 *
1891 * @param s the sorted set to be "wrapped" in a synchronized sorted set.
1892 * @return a synchronized view of the specified sorted set.
1893 */
1894 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1895 return new SynchronizedSortedSet<>(s);
1896 }
1897
1898 /**
1899 * @serial include
1900 */
1901 static class SynchronizedSortedSet<E>
1902 extends SynchronizedSet<E>
1903 implements SortedSet<E>
1904 {
1905 private static final long serialVersionUID = 8695801310862127406L;
1906
1907 private final SortedSet<E> ss;
1908
1909 SynchronizedSortedSet(SortedSet<E> s) {
1910 super(s);
1911 ss = s;
1912 }
1913 SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1914 super(s, mutex);
1915 ss = s;
1916 }
1917
1918 public Comparator<? super E> comparator() {
1919 synchronized (mutex) {return ss.comparator();}
1920 }
1921
1922 public SortedSet<E> subSet(E fromElement, E toElement) {
1923 synchronized (mutex) {
1924 return new SynchronizedSortedSet<>(
1925 ss.subSet(fromElement, toElement), mutex);
1926 }
1927 }
1928 public SortedSet<E> headSet(E toElement) {
1929 synchronized (mutex) {
1930 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex);
1931 }
1932 }
1933 public SortedSet<E> tailSet(E fromElement) {
1934 synchronized (mutex) {
1935 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex);
1936 }
1937 }
1938
1939 public E first() {
1940 synchronized (mutex) {return ss.first();}
1941 }
1942 public E last() {
1943 synchronized (mutex) {return ss.last();}
1944 }
1945 }
1946
1947 /**
1948 * Returns a synchronized (thread-safe) list backed by the specified
1949 * list. In order to guarantee serial access, it is critical that
1950 * <strong>all</strong> access to the backing list is accomplished
1951 * through the returned list.<p>
1952 *
1953 * It is imperative that the user manually synchronize on the returned
1954 * list when iterating over it:
1955 * <pre>
1956 * List list = Collections.synchronizedList(new ArrayList());
1957 * ...
1958 * synchronized (list) {
1959 * Iterator i = list.iterator(); // Must be in synchronized block
1960 * while (i.hasNext())
1961 * foo(i.next());
1962 * }
1963 * </pre>
1964 * Failure to follow this advice may result in non-deterministic behavior.
1965 *
1966 * <p>The returned list will be serializable if the specified list is
1967 * serializable.
1968 *
1969 * @param list the list to be "wrapped" in a synchronized list.
1970 * @return a synchronized view of the specified list.
1971 */
1972 public static <T> List<T> synchronizedList(List<T> list) {
1973 return (list instanceof RandomAccess ?
1974 new SynchronizedRandomAccessList<>(list) :
1975 new SynchronizedList<>(list));
1976 }
1977
1978 static <T> List<T> synchronizedList(List<T> list, Object mutex) {
1979 return (list instanceof RandomAccess ?
1980 new SynchronizedRandomAccessList<>(list, mutex) :
1981 new SynchronizedList<>(list, mutex));
1982 }
1983
1984 /**
1985 * @serial include
1986 */
1987 static class SynchronizedList<E>
1988 extends SynchronizedCollection<E>
1989 implements List<E> {
1990 private static final long serialVersionUID = -7754090372962971524L;
1991
1992 final List<E> list;
1993
1994 SynchronizedList(List<E> list) {
1995 super(list);
1996 this.list = list;
1997 }
1998 SynchronizedList(List<E> list, Object mutex) {
1999 super(list, mutex);
2000 this.list = list;
2001 }
2002
2003 public boolean equals(Object o) {
2004 if (this == o)
2005 return true;
2006 synchronized (mutex) {return list.equals(o);}
2007 }
2008 public int hashCode() {
2009 synchronized (mutex) {return list.hashCode();}
2010 }
2011
2012 public E get(int index) {
2013 synchronized (mutex) {return list.get(index);}
2014 }
2015 public E set(int index, E element) {
2016 synchronized (mutex) {return list.set(index, element);}
2017 }
2018 public void add(int index, E element) {
2019 synchronized (mutex) {list.add(index, element);}
2020 }
2021 public E remove(int index) {
2022 synchronized (mutex) {return list.remove(index);}
2023 }
2024
2025 public int indexOf(Object o) {
2026 synchronized (mutex) {return list.indexOf(o);}
2027 }
2028 public int lastIndexOf(Object o) {
2029 synchronized (mutex) {return list.lastIndexOf(o);}
2030 }
2031
2032 public boolean addAll(int index, Collection<? extends E> c) {
2033 synchronized (mutex) {return list.addAll(index, c);}
2034 }
2035
2036 public ListIterator<E> listIterator() {
2037 return list.listIterator(); // Must be manually synched by user
2038 }
2039
2040 public ListIterator<E> listIterator(int index) {
2041 return list.listIterator(index); // Must be manually synched by user
2042 }
2043
2044 public List<E> subList(int fromIndex, int toIndex) {
2045 synchronized (mutex) {
2046 return new SynchronizedList<>(list.subList(fromIndex, toIndex),
2047 mutex);
2048 }
2049 }
2050
2051 @Override
2052 public void replaceAll(UnaryOperator<E> operator) {
2053 synchronized (mutex) {list.replaceAll(operator);}
2054 }
2055 @Override
2056 public void sort(Comparator<? super E> c) {
2057 synchronized (mutex) {list.sort(c);}
2058 }
2059
2060 /**
2061 * SynchronizedRandomAccessList instances are serialized as
2062 * SynchronizedList instances to allow them to be deserialized
2063 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
2064 * This method inverts the transformation. As a beneficial
2065 * side-effect, it also grafts the RandomAccess marker onto
2066 * SynchronizedList instances that were serialized in pre-1.4 JREs.
2067 *
2068 * Note: Unfortunately, SynchronizedRandomAccessList instances
2069 * serialized in 1.4.1 and deserialized in 1.4 will become
2070 * SynchronizedList instances, as this method was missing in 1.4.
2071 */
2072 private Object readResolve() {
2073 return (list instanceof RandomAccess
2074 ? new SynchronizedRandomAccessList<>(list)
2075 : this);
2076 }
2077 }
2078
2079 /**
2080 * @serial include
2081 */
2082 static class SynchronizedRandomAccessList<E>
2083 extends SynchronizedList<E>
2084 implements RandomAccess {
2085
2086 SynchronizedRandomAccessList(List<E> list) {
2087 super(list);
2088 }
2089
2090 SynchronizedRandomAccessList(List<E> list, Object mutex) {
2091 super(list, mutex);
2092 }
2093
2094 public List<E> subList(int fromIndex, int toIndex) {
2095 synchronized (mutex) {
2096 return new SynchronizedRandomAccessList<>(
2097 list.subList(fromIndex, toIndex), mutex);
2098 }
2099 }
2100
2101 private static final long serialVersionUID = 1530674583602358482L;
2102
2103 /**
2104 * Allows instances to be deserialized in pre-1.4 JREs (which do
2105 * not have SynchronizedRandomAccessList). SynchronizedList has
2106 * a readResolve method that inverts this transformation upon
2107 * deserialization.
2108 */
2109 private Object writeReplace() {
2110 return new SynchronizedList<>(list);
2111 }
2112 }
2113
2114 /**
2115 * Returns a synchronized (thread-safe) map backed by the specified
2116 * map. In order to guarantee serial access, it is critical that
2117 * <strong>all</strong> access to the backing map is accomplished
2118 * through the returned map.<p>
2119 *
2120 * It is imperative that the user manually synchronize on the returned
2121 * map when iterating over any of its collection views:
2122 * <pre>
2123 * Map m = Collections.synchronizedMap(new HashMap());
2124 * ...
2125 * Set s = m.keySet(); // Needn't be in synchronized block
2126 * ...
2127 * synchronized (m) { // Synchronizing on m, not s!
2128 * Iterator i = s.iterator(); // Must be in synchronized block
2129 * while (i.hasNext())
2130 * foo(i.next());
2131 * }
2132 * </pre>
2133 * Failure to follow this advice may result in non-deterministic behavior.
2134 *
2135 * <p>The returned map will be serializable if the specified map is
2136 * serializable.
2137 *
2138 * @param m the map to be "wrapped" in a synchronized map.
2139 * @return a synchronized view of the specified map.
2140 */
2141 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
2142 return new SynchronizedMap<>(m);
2143 }
2144
2145 /**
2146 * @serial include
2147 */
2148 private static class SynchronizedMap<K,V>
2149 implements Map<K,V>, Serializable {
2150 private static final long serialVersionUID = 1978198479659022715L;
2151
2152 private final Map<K,V> m; // Backing Map
2153 final Object mutex; // Object on which to synchronize
2154
2155 SynchronizedMap(Map<K,V> m) {
2156 if (m==null)
2157 throw new NullPointerException();
2158 this.m = m;
2159 mutex = this;
2160 }
2161
2162 SynchronizedMap(Map<K,V> m, Object mutex) {
2163 this.m = m;
2164 this.mutex = mutex;
2165 }
2166
2167 public int size() {
2168 synchronized (mutex) {return m.size();}
2169 }
2170 public boolean isEmpty() {
2171 synchronized (mutex) {return m.isEmpty();}
2172 }
2173 public boolean containsKey(Object key) {
2174 synchronized (mutex) {return m.containsKey(key);}
2175 }
2176 public boolean containsValue(Object value) {
2177 synchronized (mutex) {return m.containsValue(value);}
2178 }
2179 public V get(Object key) {
2180 synchronized (mutex) {return m.get(key);}
2181 }
2182
2183 public V put(K key, V value) {
2184 synchronized (mutex) {return m.put(key, value);}
2185 }
2186 public V remove(Object key) {
2187 synchronized (mutex) {return m.remove(key);}
2188 }
2189 public void putAll(Map<? extends K, ? extends V> map) {
2190 synchronized (mutex) {m.putAll(map);}
2191 }
2192 public void clear() {
2193 synchronized (mutex) {m.clear();}
2194 }
2195
2196 private transient Set<K> keySet = null;
2197 private transient Set<Map.Entry<K,V>> entrySet = null;
2198 private transient Collection<V> values = null;
2199
2200 public Set<K> keySet() {
2201 synchronized (mutex) {
2202 if (keySet==null)
2203 keySet = new SynchronizedSet<>(m.keySet(), mutex);
2204 return keySet;
2205 }
2206 }
2207
2208 public Set<Map.Entry<K,V>> entrySet() {
2209 synchronized (mutex) {
2210 if (entrySet==null)
2211 entrySet = new SynchronizedSet<>(m.entrySet(), mutex);
2212 return entrySet;
2213 }
2214 }
2215
2216 public Collection<V> values() {
2217 synchronized (mutex) {
2218 if (values==null)
2219 values = new SynchronizedCollection<>(m.values(), mutex);
2220 return values;
2221 }
2222 }
2223
2224 public boolean equals(Object o) {
2225 if (this == o)
2226 return true;
2227 synchronized (mutex) {return m.equals(o);}
2228 }
2229 public int hashCode() {
2230 synchronized (mutex) {return m.hashCode();}
2231 }
2232 public String toString() {
2233 synchronized (mutex) {return m.toString();}
2234 }
2235
2236 // Override default methods in Map
2237 @Override
2238 public V getOrDefault(Object k, V defaultValue) {
2239 synchronized (mutex) {return m.getOrDefault(k, defaultValue);}
2240 }
2241 @Override
2242 public void forEach(BiConsumer<? super K, ? super V> action) {
2243 synchronized (mutex) {m.forEach(action);}
2244 }
2245 @Override
2246 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
2247 synchronized (mutex) {m.replaceAll(function);}
2248 }
2249 @Override
2250 public V putIfAbsent(K key, V value) {
2251 synchronized (mutex) {return m.putIfAbsent(key, value);}
2252 }
2253 @Override
2254 public boolean remove(Object key, Object value) {
2255 synchronized (mutex) {return m.remove(key, value);}
2256 }
2257 @Override
2258 public boolean replace(K key, V oldValue, V newValue) {
2259 synchronized (mutex) {return m.replace(key, oldValue, newValue);}
2260 }
2261 @Override
2262 public V replace(K key, V value) {
2263 synchronized (mutex) {return m.replace(key, value);}
2264 }
2265 @Override
2266 public V computeIfAbsent(K key,
2267 Function<? super K, ? extends V> mappingFunction) {
2268 synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);}
2269 }
2270 @Override
2271 public V computeIfPresent(K key,
2272 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2273 synchronized (mutex) {return m.computeIfPresent(key, remappingFunction);}
2274 }
2275 @Override
2276 public V compute(K key,
2277 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
2278 synchronized (mutex) {return m.compute(key, remappingFunction);}
2279 }
2280 @Override
2281 public V merge(K key, V value,
2282 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
2283 synchronized (mutex) {return m.merge(key, value, remappingFunction);}
2284 }
2285
2286 private void writeObject(ObjectOutputStream s) throws IOException {
2287 synchronized (mutex) {s.defaultWriteObject();}
2288 }
2289 }
2290
2291 /**
2292 * Returns a synchronized (thread-safe) sorted map backed by the specified
2293 * sorted map. In order to guarantee serial access, it is critical that
2294 * <strong>all</strong> access to the backing sorted map is accomplished
2295 * through the returned sorted map (or its views).<p>
2296 *
2297 * It is imperative that the user manually synchronize on the returned
2298 * sorted map when iterating over any of its collection views, or the
2299 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2300 * <tt>tailMap</tt> views.
2301 * <pre>
2302 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2303 * ...
2304 * Set s = m.keySet(); // Needn't be in synchronized block
2305 * ...
2306 * synchronized (m) { // Synchronizing on m, not s!
2307 * Iterator i = s.iterator(); // Must be in synchronized block
2308 * while (i.hasNext())
2309 * foo(i.next());
2310 * }
2311 * </pre>
2312 * or:
2313 * <pre>
2314 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2315 * SortedMap m2 = m.subMap(foo, bar);
2316 * ...
2317 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2318 * ...
2319 * synchronized (m) { // Synchronizing on m, not m2 or s2!
2320 * Iterator i = s.iterator(); // Must be in synchronized block
2321 * while (i.hasNext())
2322 * foo(i.next());
2323 * }
2324 * </pre>
2325 * Failure to follow this advice may result in non-deterministic behavior.
2326 *
2327 * <p>The returned sorted map will be serializable if the specified
2328 * sorted map is serializable.
2329 *
2330 * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2331 * @return a synchronized view of the specified sorted map.
2332 */
2333 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
2334 return new SynchronizedSortedMap<>(m);
2335 }
2336
2337
2338 /**
2339 * @serial include
2340 */
2341 static class SynchronizedSortedMap<K,V>
2342 extends SynchronizedMap<K,V>
2343 implements SortedMap<K,V>
2344 {
2345 private static final long serialVersionUID = -8798146769416483793L;
2346
2347 private final SortedMap<K,V> sm;
2348
2349 SynchronizedSortedMap(SortedMap<K,V> m) {
2350 super(m);
2351 sm = m;
2352 }
2353 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
2354 super(m, mutex);
2355 sm = m;
2356 }
2357
2358 public Comparator<? super K> comparator() {
2359 synchronized (mutex) {return sm.comparator();}
2360 }
2361
2362 public SortedMap<K,V> subMap(K fromKey, K toKey) {
2363 synchronized (mutex) {
2364 return new SynchronizedSortedMap<>(
2365 sm.subMap(fromKey, toKey), mutex);
2366 }
2367 }
2368 public SortedMap<K,V> headMap(K toKey) {
2369 synchronized (mutex) {
2370 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex);
2371 }
2372 }
2373 public SortedMap<K,V> tailMap(K fromKey) {
2374 synchronized (mutex) {
2375 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex);
2376 }
2377 }
2378
2379 public K firstKey() {
2380 synchronized (mutex) {return sm.firstKey();}
2381 }
2382 public K lastKey() {
2383 synchronized (mutex) {return sm.lastKey();}
2384 }
2385 }
2386
2387 // Dynamically typesafe collection wrappers
2388
2389 /**
2390 * Returns a dynamically typesafe view of the specified collection.
2391 * Any attempt to insert an element of the wrong type will result in an
2392 * immediate {@link ClassCastException}. Assuming a collection
2393 * contains no incorrectly typed elements prior to the time a
2394 * dynamically typesafe view is generated, and that all subsequent
2395 * access to the collection takes place through the view, it is
2396 * <i>guaranteed</i> that the collection cannot contain an incorrectly
2397 * typed element.
2398 *
2399 * <p>The generics mechanism in the language provides compile-time
2400 * (static) type checking, but it is possible to defeat this mechanism
2401 * with unchecked casts. Usually this is not a problem, as the compiler
2402 * issues warnings on all such unchecked operations. There are, however,
2403 * times when static type checking alone is not sufficient. For example,
2404 * suppose a collection is passed to a third-party library and it is
2405 * imperative that the library code not corrupt the collection by
2406 * inserting an element of the wrong type.
2407 *
2408 * <p>Another use of dynamically typesafe views is debugging. Suppose a
2409 * program fails with a {@code ClassCastException}, indicating that an
2410 * incorrectly typed element was put into a parameterized collection.
2411 * Unfortunately, the exception can occur at any time after the erroneous
2412 * element is inserted, so it typically provides little or no information
2413 * as to the real source of the problem. If the problem is reproducible,
2414 * one can quickly determine its source by temporarily modifying the
2415 * program to wrap the collection with a dynamically typesafe view.
2416 * For example, this declaration:
2417 * <pre> {@code
2418 * Collection<String> c = new HashSet<String>();
2419 * }</pre>
2420 * may be replaced temporarily by this one:
2421 * <pre> {@code
2422 * Collection<String> c = Collections.checkedCollection(
2423 * new HashSet<String>(), String.class);
2424 * }</pre>
2425 * Running the program again will cause it to fail at the point where
2426 * an incorrectly typed element is inserted into the collection, clearly
2427 * identifying the source of the problem. Once the problem is fixed, the
2428 * modified declaration may be reverted back to the original.
2429 *
2430 * <p>The returned collection does <i>not</i> pass the hashCode and equals
2431 * operations through to the backing collection, but relies on
2432 * {@code Object}'s {@code equals} and {@code hashCode} methods. This
2433 * is necessary to preserve the contracts of these operations in the case
2434 * that the backing collection is a set or a list.
2435 *
2436 * <p>The returned collection will be serializable if the specified
2437 * collection is serializable.
2438 *
2439 * <p>Since {@code null} is considered to be a value of any reference
2440 * type, the returned collection permits insertion of null elements
2441 * whenever the backing collection does.
2442 *
2443 * @param c the collection for which a dynamically typesafe view is to be
2444 * returned
2445 * @param type the type of element that {@code c} is permitted to hold
2446 * @return a dynamically typesafe view of the specified collection
2447 * @since 1.5
2448 */
2449 public static <E> Collection<E> checkedCollection(Collection<E> c,
2450 Class<E> type) {
2451 return new CheckedCollection<>(c, type);
2452 }
2453
2454 @SuppressWarnings("unchecked")
2455 static <T> T[] zeroLengthArray(Class<T> type) {
2456 return (T[]) Array.newInstance(type, 0);
2457 }
2458
2459 /**
2460 * @serial include
2461 */
2462 static class CheckedCollection<E> implements Collection<E>, Serializable {
2463 private static final long serialVersionUID = 1578914078182001775L;
2464
2465 final Collection<E> c;
2466 final Class<E> type;
2467
2468 void typeCheck(Object o) {
2469 if (o != null && !type.isInstance(o))
2470 throw new ClassCastException(badElementMsg(o));
2471 }
2472
2473 private String badElementMsg(Object o) {
2474 return "Attempt to insert " + o.getClass() +
2475 " element into collection with element type " + type;
2476 }
2477
2478 CheckedCollection(Collection<E> c, Class<E> type) {
2479 if (c==null || type == null)
2480 throw new NullPointerException();
2481 this.c = c;
2482 this.type = type;
2483 }
2484
2485 public int size() { return c.size(); }
2486 public boolean isEmpty() { return c.isEmpty(); }
2487 public boolean contains(Object o) { return c.contains(o); }
2488 public Object[] toArray() { return c.toArray(); }
2489 public <T> T[] toArray(T[] a) { return c.toArray(a); }
2490 public String toString() { return c.toString(); }
2491 public boolean remove(Object o) { return c.remove(o); }
2492 public void clear() { c.clear(); }
2493
2494 public boolean containsAll(Collection<?> coll) {
2495 return c.containsAll(coll);
2496 }
2497 public boolean removeAll(Collection<?> coll) {
2498 return c.removeAll(coll);
2499 }
2500 public boolean retainAll(Collection<?> coll) {
2501 return c.retainAll(coll);
2502 }
2503
2504 public Iterator<E> iterator() {
2505 // JDK-6363904 - unwrapped iterator could be typecast to
2506 // ListIterator with unsafe set()
2507 final Iterator<E> it = c.iterator();
2508 return new Iterator<E>() {
2509 public boolean hasNext() { return it.hasNext(); }
2510 public E next() { return it.next(); }
2511 public void remove() { it.remove(); }};
2512 }
2513
2514 public boolean add(E e) {
2515 typeCheck(e);
2516 return c.add(e);
2517 }
2518
2519 private E[] zeroLengthElementArray = null; // Lazily initialized
2520
2521 private E[] zeroLengthElementArray() {
2522 return zeroLengthElementArray != null ? zeroLengthElementArray :
2523 (zeroLengthElementArray = zeroLengthArray(type));
2524 }
2525
2526 @SuppressWarnings("unchecked")
2527 Collection<E> checkedCopyOf(Collection<? extends E> coll) {
2528 Object[] a = null;
2529 try {
2530 E[] z = zeroLengthElementArray();
2531 a = coll.toArray(z);
2532 // Defend against coll violating the toArray contract
2533 if (a.getClass() != z.getClass())
2534 a = Arrays.copyOf(a, a.length, z.getClass());
2535 } catch (ArrayStoreException ignore) {
2536 // To get better and consistent diagnostics,
2537 // we call typeCheck explicitly on each element.
2538 // We call clone() to defend against coll retaining a
2539 // reference to the returned array and storing a bad
2540 // element into it after it has been type checked.
2541 a = coll.toArray().clone();
2542 for (Object o : a)
2543 typeCheck(o);
2544 }
2545 // A slight abuse of the type system, but safe here.
2546 return (Collection<E>) Arrays.asList(a);
2547 }
2548
2549 public boolean addAll(Collection<? extends E> coll) {
2550 // Doing things this way insulates us from concurrent changes
2551 // in the contents of coll and provides all-or-nothing
2552 // semantics (which we wouldn't get if we type-checked each
2553 // element as we added it)
2554 return c.addAll(checkedCopyOf(coll));
2555 }
2556
2557 // Override default methods in Collection
2558 @Override
2559 public void forEach(Consumer<? super E> action) {c.forEach(action);}
2560 @Override
2561 public boolean removeIf(Predicate<? super E> filter) {
2562 return c.removeIf(filter);
2563 }
2564 @Override
2565 public Spliterator<E> spliterator() {return c.spliterator();}
2566 }
2567
2568 /**
2569 * Returns a dynamically typesafe view of the specified queue.
2570 * Any attempt to insert an element of the wrong type will result in
2571 * an immediate {@link ClassCastException}. Assuming a queue contains
2572 * no incorrectly typed elements prior to the time a dynamically typesafe
2573 * view is generated, and that all subsequent access to the queue
2574 * takes place through the view, it is <i>guaranteed</i> that the
2575 * queue cannot contain an incorrectly typed element.
2576 *
2577 * <p>A discussion of the use of dynamically typesafe views may be
2578 * found in the documentation for the {@link #checkedCollection
2579 * checkedCollection} method.
2580 *
2581 * <p>The returned queue will be serializable if the specified queue
2582 * is serializable.
2583 *
2584 * <p>Since {@code null} is considered to be a value of any reference
2585 * type, the returned queue permits insertion of {@code null} elements
2586 * whenever the backing queue does.
2587 *
2588 * @param queue the queue for which a dynamically typesafe view is to be
2589 * returned
2590 * @param type the type of element that {@code queue} is permitted to hold
2591 * @return a dynamically typesafe view of the specified queue
2592 * @since 1.8
2593 */
2594 public static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type) {
2595 return new CheckedQueue<>(queue, type);
2596 }
2597
2598 /**
2599 * @serial include
2600 */
2601 static class CheckedQueue<E>
2602 extends CheckedCollection<E>
2603 implements Queue<E>, Serializable
2604 {
2605 private static final long serialVersionUID = 1433151992604707767L;
2606 final Queue<E> queue;
2607
2608 CheckedQueue(Queue<E> queue, Class<E> elementType) {
2609 super(queue, elementType);
2610 this.queue = queue;
2611 }
2612
2613 public E element() {return queue.element();}
2614 public boolean equals(Object o) {return o == this || c.equals(o);}
2615 public int hashCode() {return c.hashCode();}
2616 public E peek() {return queue.peek();}
2617 public E poll() {return queue.poll();}
2618 public E remove() {return queue.remove();}
2619
2620 public boolean offer(E e) {
2621 typeCheck(e);
2622 return add(e);
2623 }
2624 }
2625
2626 /**
2627 * Returns a dynamically typesafe view of the specified set.
2628 * Any attempt to insert an element of the wrong type will result in
2629 * an immediate {@link ClassCastException}. Assuming a set contains
2630 * no incorrectly typed elements prior to the time a dynamically typesafe
2631 * view is generated, and that all subsequent access to the set
2632 * takes place through the view, it is <i>guaranteed</i> that the
2633 * set cannot contain an incorrectly typed element.
2634 *
2635 * <p>A discussion of the use of dynamically typesafe views may be
2636 * found in the documentation for the {@link #checkedCollection
2637 * checkedCollection} method.
2638 *
2639 * <p>The returned set will be serializable if the specified set is
2640 * serializable.
2641 *
2642 * <p>Since {@code null} is considered to be a value of any reference
2643 * type, the returned set permits insertion of null elements whenever
2644 * the backing set does.
2645 *
2646 * @param s the set for which a dynamically typesafe view is to be
2647 * returned
2648 * @param type the type of element that {@code s} is permitted to hold
2649 * @return a dynamically typesafe view of the specified set
2650 * @since 1.5
2651 */
2652 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2653 return new CheckedSet<>(s, type);
2654 }
2655
2656 /**
2657 * @serial include
2658 */
2659 static class CheckedSet<E> extends CheckedCollection<E>
2660 implements Set<E>, Serializable
2661 {
2662 private static final long serialVersionUID = 4694047833775013803L;
2663
2664 CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2665
2666 public boolean equals(Object o) { return o == this || c.equals(o); }
2667 public int hashCode() { return c.hashCode(); }
2668 }
2669
2670 /**
2671 * Returns a dynamically typesafe view of the specified sorted set.
2672 * Any attempt to insert an element of the wrong type will result in an
2673 * immediate {@link ClassCastException}. Assuming a sorted set
2674 * contains no incorrectly typed elements prior to the time a
2675 * dynamically typesafe view is generated, and that all subsequent
2676 * access to the sorted set takes place through the view, it is
2677 * <i>guaranteed</i> that the sorted set cannot contain an incorrectly
2678 * typed element.
2679 *
2680 * <p>A discussion of the use of dynamically typesafe views may be
2681 * found in the documentation for the {@link #checkedCollection
2682 * checkedCollection} method.
2683 *
2684 * <p>The returned sorted set will be serializable if the specified sorted
2685 * set is serializable.
2686 *
2687 * <p>Since {@code null} is considered to be a value of any reference
2688 * type, the returned sorted set permits insertion of null elements
2689 * whenever the backing sorted set does.
2690 *
2691 * @param s the sorted set for which a dynamically typesafe view is to be
2692 * returned
2693 * @param type the type of element that {@code s} is permitted to hold
2694 * @return a dynamically typesafe view of the specified sorted set
2695 * @since 1.5
2696 */
2697 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
2698 Class<E> type) {
2699 return new CheckedSortedSet<>(s, type);
2700 }
2701
2702 /**
2703 * @serial include
2704 */
2705 static class CheckedSortedSet<E> extends CheckedSet<E>
2706 implements SortedSet<E>, Serializable
2707 {
2708 private static final long serialVersionUID = 1599911165492914959L;
2709 private final SortedSet<E> ss;
2710
2711 CheckedSortedSet(SortedSet<E> s, Class<E> type) {
2712 super(s, type);
2713 ss = s;
2714 }
2715
2716 public Comparator<? super E> comparator() { return ss.comparator(); }
2717 public E first() { return ss.first(); }
2718 public E last() { return ss.last(); }
2719
2720 public SortedSet<E> subSet(E fromElement, E toElement) {
2721 return checkedSortedSet(ss.subSet(fromElement,toElement), type);
2722 }
2723 public SortedSet<E> headSet(E toElement) {
2724 return checkedSortedSet(ss.headSet(toElement), type);
2725 }
2726 public SortedSet<E> tailSet(E fromElement) {
2727 return checkedSortedSet(ss.tailSet(fromElement), type);
2728 }
2729 }
2730
2731 /**
2732 * Returns a dynamically typesafe view of the specified list.
2733 * Any attempt to insert an element of the wrong type will result in
2734 * an immediate {@link ClassCastException}. Assuming a list contains
2735 * no incorrectly typed elements prior to the time a dynamically typesafe
2736 * view is generated, and that all subsequent access to the list
2737 * takes place through the view, it is <i>guaranteed</i> that the
2738 * list cannot contain an incorrectly typed element.
2739 *
2740 * <p>A discussion of the use of dynamically typesafe views may be
2741 * found in the documentation for the {@link #checkedCollection
2742 * checkedCollection} method.
2743 *
2744 * <p>The returned list will be serializable if the specified list
2745 * is serializable.
2746 *
2747 * <p>Since {@code null} is considered to be a value of any reference
2748 * type, the returned list permits insertion of null elements whenever
2749 * the backing list does.
2750 *
2751 * @param list the list for which a dynamically typesafe view is to be
2752 * returned
2753 * @param type the type of element that {@code list} is permitted to hold
2754 * @return a dynamically typesafe view of the specified list
2755 * @since 1.5
2756 */
2757 public static <E> List<E> checkedList(List<E> list, Class<E> type) {
2758 return (list instanceof RandomAccess ?
2759 new CheckedRandomAccessList<>(list, type) :
2760 new CheckedList<>(list, type));
2761 }
2762
2763 /**
2764 * @serial include
2765 */
2766 static class CheckedList<E>
2767 extends CheckedCollection<E>
2768 implements List<E>
2769 {
2770 private static final long serialVersionUID = 65247728283967356L;
2771 final List<E> list;
2772
2773 CheckedList(List<E> list, Class<E> type) {
2774 super(list, type);
2775 this.list = list;
2776 }
2777
2778 public boolean equals(Object o) { return o == this || list.equals(o); }
2779 public int hashCode() { return list.hashCode(); }
2780 public E get(int index) { return list.get(index); }
2781 public E remove(int index) { return list.remove(index); }
2782 public int indexOf(Object o) { return list.indexOf(o); }
2783 public int lastIndexOf(Object o) { return list.lastIndexOf(o); }
2784
2785 public E set(int index, E element) {
2786 typeCheck(element);
2787 return list.set(index, element);
2788 }
2789
2790 public void add(int index, E element) {
2791 typeCheck(element);
2792 list.add(index, element);
2793 }
2794
2795 public boolean addAll(int index, Collection<? extends E> c) {
2796 return list.addAll(index, checkedCopyOf(c));
2797 }
2798 public ListIterator<E> listIterator() { return listIterator(0); }
2799
2800 public ListIterator<E> listIterator(final int index) {
2801 final ListIterator<E> i = list.listIterator(index);
2802
2803 return new ListIterator<E>() {
2804 public boolean hasNext() { return i.hasNext(); }
2805 public E next() { return i.next(); }
2806 public boolean hasPrevious() { return i.hasPrevious(); }
2807 public E previous() { return i.previous(); }
2808 public int nextIndex() { return i.nextIndex(); }
2809 public int previousIndex() { return i.previousIndex(); }
2810 public void remove() { i.remove(); }
2811
2812 public void set(E e) {
2813 typeCheck(e);
2814 i.set(e);
2815 }
2816
2817 public void add(E e) {
2818 typeCheck(e);
2819 i.add(e);
2820 }
2821
2822 @Override
2823 public void forEachRemaining(Consumer<? super E> action) {
2824 i.forEachRemaining(action);
2825 }
2826 };
2827 }
2828
2829 public List<E> subList(int fromIndex, int toIndex) {
2830 return new CheckedList<>(list.subList(fromIndex, toIndex), type);
2831 }
2832
2833 @Override
2834 public void replaceAll(UnaryOperator<E> operator) {
2835 list.replaceAll(operator);
2836 }
2837 @Override
2838 public void sort(Comparator<? super E> c) {
2839 list.sort(c);
2840 }
2841 }
2842
2843 /**
2844 * @serial include
2845 */
2846 static class CheckedRandomAccessList<E> extends CheckedList<E>
2847 implements RandomAccess
2848 {
2849 private static final long serialVersionUID = 1638200125423088369L;
2850
2851 CheckedRandomAccessList(List<E> list, Class<E> type) {
2852 super(list, type);
2853 }
2854
2855 public List<E> subList(int fromIndex, int toIndex) {
2856 return new CheckedRandomAccessList<>(
2857 list.subList(fromIndex, toIndex), type);
2858 }
2859 }
2860
2861 /**
2862 * Returns a dynamically typesafe view of the specified map.
2863 * Any attempt to insert a mapping whose key or value have the wrong
2864 * type will result in an immediate {@link ClassCastException}.
2865 * Similarly, any attempt to modify the value currently associated with
2866 * a key will result in an immediate {@link ClassCastException},
2867 * whether the modification is attempted directly through the map
2868 * itself, or through a {@link Map.Entry} instance obtained from the
2869 * map's {@link Map#entrySet() entry set} view.
2870 *
2871 * <p>Assuming a map contains no incorrectly typed keys or values
2872 * prior to the time a dynamically typesafe view is generated, and
2873 * that all subsequent access to the map takes place through the view
2874 * (or one of its collection views), it is <i>guaranteed</i> that the
2875 * map cannot contain an incorrectly typed key or value.
2876 *
2877 * <p>A discussion of the use of dynamically typesafe views may be
2878 * found in the documentation for the {@link #checkedCollection
2879 * checkedCollection} method.
2880 *
2881 * <p>The returned map will be serializable if the specified map is
2882 * serializable.
2883 *
2884 * <p>Since {@code null} is considered to be a value of any reference
2885 * type, the returned map permits insertion of null keys or values
2886 * whenever the backing map does.
2887 *
2888 * @param m the map for which a dynamically typesafe view is to be
2889 * returned
2890 * @param keyType the type of key that {@code m} is permitted to hold
2891 * @param valueType the type of value that {@code m} is permitted to hold
2892 * @return a dynamically typesafe view of the specified map
2893 * @since 1.5
2894 */
2895 public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
2896 Class<K> keyType,
2897 Class<V> valueType) {
2898 return new CheckedMap<>(m, keyType, valueType);
2899 }
2900
2901
2902 /**
2903 * @serial include
2904 */
2905 private static class CheckedMap<K,V>
2906 implements Map<K,V>, Serializable
2907 {
2908 private static final long serialVersionUID = 5742860141034234728L;
2909
2910 private final Map<K, V> m;
2911 final Class<K> keyType;
2912 final Class<V> valueType;
2913
2914 private void typeCheck(Object key, Object value) {
2915 if (key != null && !keyType.isInstance(key))
2916 throw new ClassCastException(badKeyMsg(key));
2917
2918 if (value != null && !valueType.isInstance(value))
2919 throw new ClassCastException(badValueMsg(value));
2920 }
2921
2922 private BiFunction<? super K, ? super V, ? extends V> typeCheck(
2923 BiFunction<? super K, ? super V, ? extends V> func) {
2924 Objects.requireNonNull(func);
2925 return (k, v) -> {
2926 V newValue = func.apply(k, v);
2927 typeCheck(k, newValue);
2928 return newValue;
2929 };
2930 }
2931
2932 private String badKeyMsg(Object key) {
2933 return "Attempt to insert " + key.getClass() +
2934 " key into map with key type " + keyType;
2935 }
2936
2937 private String badValueMsg(Object value) {
2938 return "Attempt to insert " + value.getClass() +
2939 " value into map with value type " + valueType;
2940 }
2941
2942 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
2943 if (m == null || keyType == null || valueType == null)
2944 throw new NullPointerException();
2945 this.m = m;
2946 this.keyType = keyType;
2947 this.valueType = valueType;
2948 }
2949
2950 public int size() { return m.size(); }
2951 public boolean isEmpty() { return m.isEmpty(); }
2952 public boolean containsKey(Object key) { return m.containsKey(key); }
2953 public boolean containsValue(Object v) { return m.containsValue(v); }
2954 public V get(Object key) { return m.get(key); }
2955 public V remove(Object key) { return m.remove(key); }
2956 public void clear() { m.clear(); }
2957 public Set<K> keySet() { return m.keySet(); }
2958 public Collection<V> values() { return m.values(); }
2959 public boolean equals(Object o) { return o == this || m.equals(o); }
2960 public int hashCode() { return m.hashCode(); }
2961 public String toString() { return m.toString(); }
2962
2963 public V put(K key, V value) {
2964 typeCheck(key, value);
2965 return m.put(key, value);
2966 }
2967
2968 @SuppressWarnings("unchecked")
2969 public void putAll(Map<? extends K, ? extends V> t) {
2970 // Satisfy the following goals:
2971 // - good diagnostics in case of type mismatch
2972 // - all-or-nothing semantics
2973 // - protection from malicious t
2974 // - correct behavior if t is a concurrent map
2975 Object[] entries = t.entrySet().toArray();
2976 List<Map.Entry<K,V>> checked = new ArrayList<>(entries.length);
2977 for (Object o : entries) {
2978 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2979 Object k = e.getKey();
2980 Object v = e.getValue();
2981 typeCheck(k, v);
2982 checked.add(
2983 new AbstractMap.SimpleImmutableEntry<>((K)k, (V)v));
2984 }
2985 for (Map.Entry<K,V> e : checked)
2986 m.put(e.getKey(), e.getValue());
2987 }
2988
2989 private transient Set<Map.Entry<K,V>> entrySet = null;
2990
2991 public Set<Map.Entry<K,V>> entrySet() {
2992 if (entrySet==null)
2993 entrySet = new CheckedEntrySet<>(m.entrySet(), valueType);
2994 return entrySet;
2995 }
2996
2997 // Override default methods in Map
2998 @Override
2999 public void forEach(BiConsumer<? super K, ? super V> action) {
3000 m.forEach(action);
3001 }
3002
3003 @Override
3004 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3005 m.replaceAll(typeCheck(function));
3006 }
3007
3008 @Override
3009 public V putIfAbsent(K key, V value) {
3010 typeCheck(key, value);
3011 return m.putIfAbsent(key, value);
3012 }
3013
3014 @Override
3015 public boolean remove(Object key, Object value) {
3016 return m.remove(key, value);
3017 }
3018
3019 @Override
3020 public boolean replace(K key, V oldValue, V newValue) {
3021 typeCheck(key, newValue);
3022 return m.replace(key, oldValue, newValue);
3023 }
3024
3025 @Override
3026 public V replace(K key, V value) {
3027 typeCheck(key, value);
3028 return m.replace(key, value);
3029 }
3030
3031 @Override
3032 public V computeIfAbsent(K key,
3033 Function<? super K, ? extends V> mappingFunction) {
3034 Objects.requireNonNull(mappingFunction);
3035 return m.computeIfAbsent(key, k -> {
3036 V value = mappingFunction.apply(k);
3037 typeCheck(k, value);
3038 return value;
3039 });
3040 }
3041
3042 @Override
3043 public V computeIfPresent(K key,
3044 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3045 return m.computeIfPresent(key, typeCheck(remappingFunction));
3046 }
3047
3048 @Override
3049 public V compute(K key,
3050 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3051 return m.compute(key, typeCheck(remappingFunction));
3052 }
3053
3054 @Override
3055 public V merge(K key, V value,
3056 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
3057 Objects.requireNonNull(remappingFunction);
3058 return m.merge(key, value, (v1, v2) -> {
3059 V newValue = remappingFunction.apply(v1, v2);
3060 typeCheck(null, newValue);
3061 return newValue;
3062 });
3063 }
3064
3065 /**
3066 * We need this class in addition to CheckedSet as Map.Entry permits
3067 * modification of the backing Map via the setValue operation. This
3068 * class is subtle: there are many possible attacks that must be
3069 * thwarted.
3070 *
3071 * @serial exclude
3072 */
3073 static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> {
3074 private final Set<Map.Entry<K,V>> s;
3075 private final Class<V> valueType;
3076
3077 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
3078 this.s = s;
3079 this.valueType = valueType;
3080 }
3081
3082 public int size() { return s.size(); }
3083 public boolean isEmpty() { return s.isEmpty(); }
3084 public String toString() { return s.toString(); }
3085 public int hashCode() { return s.hashCode(); }
3086 public void clear() { s.clear(); }
3087
3088 public boolean add(Map.Entry<K, V> e) {
3089 throw new UnsupportedOperationException();
3090 }
3091 public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
3092 throw new UnsupportedOperationException();
3093 }
3094
3095 public Iterator<Map.Entry<K,V>> iterator() {
3096 final Iterator<Map.Entry<K, V>> i = s.iterator();
3097 final Class<V> valueType = this.valueType;
3098
3099 return new Iterator<Map.Entry<K,V>>() {
3100 public boolean hasNext() { return i.hasNext(); }
3101 public void remove() { i.remove(); }
3102
3103 public Map.Entry<K,V> next() {
3104 return checkedEntry(i.next(), valueType);
3105 }
3106 };
3107 }
3108
3109 @SuppressWarnings("unchecked")
3110 public Object[] toArray() {
3111 Object[] source = s.toArray();
3112
3113 /*
3114 * Ensure that we don't get an ArrayStoreException even if
3115 * s.toArray returns an array of something other than Object
3116 */
3117 Object[] dest = (CheckedEntry.class.isInstance(
3118 source.getClass().getComponentType()) ? source :
3119 new Object[source.length]);
3120
3121 for (int i = 0; i < source.length; i++)
3122 dest[i] = checkedEntry((Map.Entry<K,V>)source[i],
3123 valueType);
3124 return dest;
3125 }
3126
3127 @SuppressWarnings("unchecked")
3128 public <T> T[] toArray(T[] a) {
3129 // We don't pass a to s.toArray, to avoid window of
3130 // vulnerability wherein an unscrupulous multithreaded client
3131 // could get his hands on raw (unwrapped) Entries from s.
3132 T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
3133
3134 for (int i=0; i<arr.length; i++)
3135 arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i],
3136 valueType);
3137 if (arr.length > a.length)
3138 return arr;
3139
3140 System.arraycopy(arr, 0, a, 0, arr.length);
3141 if (a.length > arr.length)
3142 a[arr.length] = null;
3143 return a;
3144 }
3145
3146 /**
3147 * This method is overridden to protect the backing set against
3148 * an object with a nefarious equals function that senses
3149 * that the equality-candidate is Map.Entry and calls its
3150 * setValue method.
3151 */
3152 public boolean contains(Object o) {
3153 if (!(o instanceof Map.Entry))
3154 return false;
3155 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
3156 return s.contains(
3157 (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
3158 }
3159
3160 /**
3161 * The bulk collection methods are overridden to protect
3162 * against an unscrupulous collection whose contains(Object o)
3163 * method senses when o is a Map.Entry, and calls o.setValue.
3164 */
3165 public boolean containsAll(Collection<?> c) {
3166 for (Object o : c)
3167 if (!contains(o)) // Invokes safe contains() above
3168 return false;
3169 return true;
3170 }
3171
3172 public boolean remove(Object o) {
3173 if (!(o instanceof Map.Entry))
3174 return false;
3175 return s.remove(new AbstractMap.SimpleImmutableEntry
3176 <>((Map.Entry<?,?>)o));
3177 }
3178
3179 public boolean removeAll(Collection<?> c) {
3180 return batchRemove(c, false);
3181 }
3182 public boolean retainAll(Collection<?> c) {
3183 return batchRemove(c, true);
3184 }
3185 private boolean batchRemove(Collection<?> c, boolean complement) {
3186 boolean modified = false;
3187 Iterator<Map.Entry<K,V>> it = iterator();
3188 while (it.hasNext()) {
3189 if (c.contains(it.next()) != complement) {
3190 it.remove();
3191 modified = true;
3192 }
3193 }
3194 return modified;
3195 }
3196
3197 public boolean equals(Object o) {
3198 if (o == this)
3199 return true;
3200 if (!(o instanceof Set))
3201 return false;
3202 Set<?> that = (Set<?>) o;
3203 return that.size() == s.size()
3204 && containsAll(that); // Invokes safe containsAll() above
3205 }
3206
3207 static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e,
3208 Class<T> valueType) {
3209 return new CheckedEntry<>(e, valueType);
3210 }
3211
3212 /**
3213 * This "wrapper class" serves two purposes: it prevents
3214 * the client from modifying the backing Map, by short-circuiting
3215 * the setValue method, and it protects the backing Map against
3216 * an ill-behaved Map.Entry that attempts to modify another
3217 * Map.Entry when asked to perform an equality check.
3218 */
3219 private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> {
3220 private final Map.Entry<K, V> e;
3221 private final Class<T> valueType;
3222
3223 CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) {
3224 this.e = e;
3225 this.valueType = valueType;
3226 }
3227
3228 public K getKey() { return e.getKey(); }
3229 public V getValue() { return e.getValue(); }
3230 public int hashCode() { return e.hashCode(); }
3231 public String toString() { return e.toString(); }
3232
3233 public V setValue(V value) {
3234 if (value != null && !valueType.isInstance(value))
3235 throw new ClassCastException(badValueMsg(value));
3236 return e.setValue(value);
3237 }
3238
3239 private String badValueMsg(Object value) {
3240 return "Attempt to insert " + value.getClass() +
3241 " value into map with value type " + valueType;
3242 }
3243
3244 public boolean equals(Object o) {
3245 if (o == this)
3246 return true;
3247 if (!(o instanceof Map.Entry))
3248 return false;
3249 return e.equals(new AbstractMap.SimpleImmutableEntry
3250 <>((Map.Entry<?,?>)o));
3251 }
3252 }
3253 }
3254 }
3255
3256 /**
3257 * Returns a dynamically typesafe view of the specified sorted map.
3258 * Any attempt to insert a mapping whose key or value have the wrong
3259 * type will result in an immediate {@link ClassCastException}.
3260 * Similarly, any attempt to modify the value currently associated with
3261 * a key will result in an immediate {@link ClassCastException},
3262 * whether the modification is attempted directly through the map
3263 * itself, or through a {@link Map.Entry} instance obtained from the
3264 * map's {@link Map#entrySet() entry set} view.
3265 *
3266 * <p>Assuming a map contains no incorrectly typed keys or values
3267 * prior to the time a dynamically typesafe view is generated, and
3268 * that all subsequent access to the map takes place through the view
3269 * (or one of its collection views), it is <i>guaranteed</i> that the
3270 * map cannot contain an incorrectly typed key or value.
3271 *
3272 * <p>A discussion of the use of dynamically typesafe views may be
3273 * found in the documentation for the {@link #checkedCollection
3274 * checkedCollection} method.
3275 *
3276 * <p>The returned map will be serializable if the specified map is
3277 * serializable.
3278 *
3279 * <p>Since {@code null} is considered to be a value of any reference
3280 * type, the returned map permits insertion of null keys or values
3281 * whenever the backing map does.
3282 *
3283 * @param m the map for which a dynamically typesafe view is to be
3284 * returned
3285 * @param keyType the type of key that {@code m} is permitted to hold
3286 * @param valueType the type of value that {@code m} is permitted to hold
3287 * @return a dynamically typesafe view of the specified map
3288 * @since 1.5
3289 */
3290 public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m,
3291 Class<K> keyType,
3292 Class<V> valueType) {
3293 return new CheckedSortedMap<>(m, keyType, valueType);
3294 }
3295
3296 /**
3297 * @serial include
3298 */
3299 static class CheckedSortedMap<K,V> extends CheckedMap<K,V>
3300 implements SortedMap<K,V>, Serializable
3301 {
3302 private static final long serialVersionUID = 1599671320688067438L;
3303
3304 private final SortedMap<K, V> sm;
3305
3306 CheckedSortedMap(SortedMap<K, V> m,
3307 Class<K> keyType, Class<V> valueType) {
3308 super(m, keyType, valueType);
3309 sm = m;
3310 }
3311
3312 public Comparator<? super K> comparator() { return sm.comparator(); }
3313 public K firstKey() { return sm.firstKey(); }
3314 public K lastKey() { return sm.lastKey(); }
3315
3316 public SortedMap<K,V> subMap(K fromKey, K toKey) {
3317 return checkedSortedMap(sm.subMap(fromKey, toKey),
3318 keyType, valueType);
3319 }
3320 public SortedMap<K,V> headMap(K toKey) {
3321 return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
3322 }
3323 public SortedMap<K,V> tailMap(K fromKey) {
3324 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
3325 }
3326 }
3327
3328 // Empty collections
3329
3330 /**
3331 * Returns an iterator that has no elements. More precisely,
3332 *
3333 * <ul compact>
3334 *
3335 * <li>{@link Iterator#hasNext hasNext} always returns {@code
3336 * false}.
3337 *
3338 * <li>{@link Iterator#next next} always throws {@link
3339 * NoSuchElementException}.
3340 *
3341 * <li>{@link Iterator#remove remove} always throws {@link
3342 * IllegalStateException}.
3343 *
3344 * </ul>
3345 *
3346 * <p>Implementations of this method are permitted, but not
3347 * required, to return the same object from multiple invocations.
3348 *
3349 * @return an empty iterator
3350 * @since 1.7
3351 */
3352 @SuppressWarnings("unchecked")
3353 public static <T> Iterator<T> emptyIterator() {
3354 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
3355 }
3356
3357 private static class EmptyIterator<E> implements Iterator<E> {
3358 static final EmptyIterator<Object> EMPTY_ITERATOR
3359 = new EmptyIterator<>();
3360
3361 public boolean hasNext() { return false; }
3362 public E next() { throw new NoSuchElementException(); }
3363 public void remove() { throw new IllegalStateException(); }
3364 @Override
3365 public void forEachRemaining(Consumer<? super E> action) {
3366 Objects.requireNonNull(action);
3367 }
3368 }
3369
3370 /**
3371 * Returns a list iterator that has no elements. More precisely,
3372 *
3373 * <ul compact>
3374 *
3375 * <li>{@link Iterator#hasNext hasNext} and {@link
3376 * ListIterator#hasPrevious hasPrevious} always return {@code
3377 * false}.
3378 *
3379 * <li>{@link Iterator#next next} and {@link ListIterator#previous
3380 * previous} always throw {@link NoSuchElementException}.
3381 *
3382 * <li>{@link Iterator#remove remove} and {@link ListIterator#set
3383 * set} always throw {@link IllegalStateException}.
3384 *
3385 * <li>{@link ListIterator#add add} always throws {@link
3386 * UnsupportedOperationException}.
3387 *
3388 * <li>{@link ListIterator#nextIndex nextIndex} always returns
3389 * {@code 0} .
3390 *
3391 * <li>{@link ListIterator#previousIndex previousIndex} always
3392 * returns {@code -1}.
3393 *
3394 * </ul>
3395 *
3396 * <p>Implementations of this method are permitted, but not
3397 * required, to return the same object from multiple invocations.
3398 *
3399 * @return an empty list iterator
3400 * @since 1.7
3401 */
3402 @SuppressWarnings("unchecked")
3403 public static <T> ListIterator<T> emptyListIterator() {
3404 return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
3405 }
3406
3407 private static class EmptyListIterator<E>
3408 extends EmptyIterator<E>
3409 implements ListIterator<E>
3410 {
3411 static final EmptyListIterator<Object> EMPTY_ITERATOR
3412 = new EmptyListIterator<>();
3413
3414 public boolean hasPrevious() { return false; }
3415 public E previous() { throw new NoSuchElementException(); }
3416 public int nextIndex() { return 0; }
3417 public int previousIndex() { return -1; }
3418 public void set(E e) { throw new IllegalStateException(); }
3419 public void add(E e) { throw new UnsupportedOperationException(); }
3420 }
3421
3422 /**
3423 * Returns an enumeration that has no elements. More precisely,
3424 *
3425 * <ul compact>
3426 *
3427 * <li>{@link Enumeration#hasMoreElements hasMoreElements} always
3428 * returns {@code false}.
3429 *
3430 * <li> {@link Enumeration#nextElement nextElement} always throws
3431 * {@link NoSuchElementException}.
3432 *
3433 * </ul>
3434 *
3435 * <p>Implementations of this method are permitted, but not
3436 * required, to return the same object from multiple invocations.
3437 *
3438 * @return an empty enumeration
3439 * @since 1.7
3440 */
3441 @SuppressWarnings("unchecked")
3442 public static <T> Enumeration<T> emptyEnumeration() {
3443 return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
3444 }
3445
3446 private static class EmptyEnumeration<E> implements Enumeration<E> {
3447 static final EmptyEnumeration<Object> EMPTY_ENUMERATION
3448 = new EmptyEnumeration<>();
3449
3450 public boolean hasMoreElements() { return false; }
3451 public E nextElement() { throw new NoSuchElementException(); }
3452 }
3453
3454 /**
3455 * The empty set (immutable). This set is serializable.
3456 *
3457 * @see #emptySet()
3458 */
3459 @SuppressWarnings("rawtypes")
3460 public static final Set EMPTY_SET = new EmptySet<>();
3461
3462 /**
3463 * Returns the empty set (immutable). This set is serializable.
3464 * Unlike the like-named field, this method is parameterized.
3465 *
3466 * <p>This example illustrates the type-safe way to obtain an empty set:
3467 * <pre>
3468 * Set<String> s = Collections.emptySet();
3469 * </pre>
3470 * Implementation note: Implementations of this method need not
3471 * create a separate <tt>Set</tt> object for each call. Using this
3472 * method is likely to have comparable cost to using the like-named
3473 * field. (Unlike this method, the field does not provide type safety.)
3474 *
3475 * @see #EMPTY_SET
3476 * @since 1.5
3477 */
3478 @SuppressWarnings("unchecked")
3479 public static final <T> Set<T> emptySet() {
3480 return (Set<T>) EMPTY_SET;
3481 }
3482
3483 /**
3484 * @serial include
3485 */
3486 private static class EmptySet<E>
3487 extends AbstractSet<E>
3488 implements Serializable
3489 {
3490 private static final long serialVersionUID = 1582296315990362920L;
3491
3492 public Iterator<E> iterator() { return emptyIterator(); }
3493
3494 public int size() {return 0;}
3495 public boolean isEmpty() {return true;}
3496
3497 public boolean contains(Object obj) {return false;}
3498 public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3499
3500 public Object[] toArray() { return new Object[0]; }
3501
3502 public <T> T[] toArray(T[] a) {
3503 if (a.length > 0)
3504 a[0] = null;
3505 return a;
3506 }
3507
3508 // Override default methods in Collection
3509 @Override
3510 public void forEach(Consumer<? super E> action) {
3511 Objects.requireNonNull(action);
3512 }
3513 @Override
3514 public boolean removeIf(Predicate<? super E> filter) {
3515 Objects.requireNonNull(filter);
3516 return false;
3517 }
3518 @Override
3519 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
3520
3521 // Preserves singleton property
3522 private Object readResolve() {
3523 return EMPTY_SET;
3524 }
3525 }
3526
3527 /**
3528 * Returns the empty sorted set (immutable). This set is serializable.
3529 *
3530 * <p>This example illustrates the type-safe way to obtain an empty sorted
3531 * set:
3532 * <pre>
3533 * SortedSet<String> s = Collections.emptySortedSet();
3534 * </pre>
3535 * Implementation note: Implementations of this method need not
3536 * create a separate <tt>SortedSet</tt> object for each call.
3537 *
3538 * @since 1.8
3539 */
3540 @SuppressWarnings("unchecked")
3541 public static final <E> SortedSet<E> emptySortedSet() {
3542 return (SortedSet<E>) new EmptySortedSet<>();
3543 }
3544
3545 /**
3546 * @serial include
3547 */
3548 private static class EmptySortedSet<E>
3549 extends AbstractSet<E>
3550 implements SortedSet<E>, Serializable
3551 {
3552 private static final long serialVersionUID = 6316515401502265487L;
3553 public Iterator<E> iterator() { return emptyIterator(); }
3554 public int size() {return 0;}
3555 public boolean isEmpty() {return true;}
3556 public boolean contains(Object obj) {return false;}
3557 public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3558 public Object[] toArray() { return new Object[0]; }
3559
3560 public <E> E[] toArray(E[] a) {
3561 if (a.length > 0)
3562 a[0] = null;
3563 return a;
3564 }
3565
3566 // Preserves singleton property
3567 private Object readResolve() {
3568 return new EmptySortedSet<>();
3569 }
3570
3571 @Override
3572 public Comparator<? super E> comparator() {
3573 return null;
3574 }
3575
3576 @Override
3577 @SuppressWarnings("unchecked")
3578 public SortedSet<E> subSet(Object fromElement, Object toElement) {
3579 Objects.requireNonNull(fromElement);
3580 Objects.requireNonNull(toElement);
3581
3582 if (!(fromElement instanceof Comparable) ||
3583 !(toElement instanceof Comparable))
3584 {
3585 throw new ClassCastException();
3586 }
3587
3588 if ((((Comparable)fromElement).compareTo(toElement) >= 0) ||
3589 (((Comparable)toElement).compareTo(fromElement) < 0))
3590 {
3591 throw new IllegalArgumentException();
3592 }
3593
3594 return emptySortedSet();
3595 }
3596
3597 @Override
3598 public SortedSet<E> headSet(Object toElement) {
3599 Objects.requireNonNull(toElement);
3600
3601 if (!(toElement instanceof Comparable)) {
3602 throw new ClassCastException();
3603 }
3604
3605 return emptySortedSet();
3606 }
3607
3608 @Override
3609 public SortedSet<E> tailSet(Object fromElement) {
3610 Objects.requireNonNull(fromElement);
3611
3612 if (!(fromElement instanceof Comparable)) {
3613 throw new ClassCastException();
3614 }
3615
3616 return emptySortedSet();
3617 }
3618
3619 @Override
3620 public E first() {
3621 throw new NoSuchElementException();
3622 }
3623
3624 @Override
3625 public E last() {
3626 throw new NoSuchElementException();
3627 }
3628
3629 // Override default methods in Collection
3630 @Override
3631 public void forEach(Consumer<? super E> action) {
3632 Objects.requireNonNull(action);
3633 }
3634
3635 @Override
3636 public boolean removeIf(Predicate<? super E> filter) {
3637 Objects.requireNonNull(filter);
3638 return false;
3639 }
3640
3641 @Override
3642 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
3643 }
3644
3645 /**
3646 * The empty list (immutable). This list is serializable.
3647 *
3648 * @see #emptyList()
3649 */
3650 @SuppressWarnings("rawtypes")
3651 public static final List EMPTY_LIST = new EmptyList<>();
3652
3653 /**
3654 * Returns the empty list (immutable). This list is serializable.
3655 *
3656 * <p>This example illustrates the type-safe way to obtain an empty list:
3657 * <pre>
3658 * List<String> s = Collections.emptyList();
3659 * </pre>
3660 * Implementation note: Implementations of this method need not
3661 * create a separate <tt>List</tt> object for each call. Using this
3662 * method is likely to have comparable cost to using the like-named
3663 * field. (Unlike this method, the field does not provide type safety.)
3664 *
3665 * @see #EMPTY_LIST
3666 * @since 1.5
3667 */
3668 @SuppressWarnings("unchecked")
3669 public static final <T> List<T> emptyList() {
3670 return (List<T>) EMPTY_LIST;
3671 }
3672
3673 /**
3674 * @serial include
3675 */
3676 private static class EmptyList<E>
3677 extends AbstractList<E>
3678 implements RandomAccess, Serializable {
3679 private static final long serialVersionUID = 8842843931221139166L;
3680
3681 public Iterator<E> iterator() {
3682 return emptyIterator();
3683 }
3684 public ListIterator<E> listIterator() {
3685 return emptyListIterator();
3686 }
3687
3688 public int size() {return 0;}
3689 public boolean isEmpty() {return true;}
3690
3691 public boolean contains(Object obj) {return false;}
3692 public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3693
3694 public Object[] toArray() { return new Object[0]; }
3695
3696 public <T> T[] toArray(T[] a) {
3697 if (a.length > 0)
3698 a[0] = null;
3699 return a;
3700 }
3701
3702 public E get(int index) {
3703 throw new IndexOutOfBoundsException("Index: "+index);
3704 }
3705
3706 public boolean equals(Object o) {
3707 return (o instanceof List) && ((List<?>)o).isEmpty();
3708 }
3709
3710 public int hashCode() { return 1; }
3711
3712 @Override
3713 public boolean removeIf(Predicate<? super E> filter) {
3714 Objects.requireNonNull(filter);
3715 return false;
3716 }
3717 @Override
3718 public void replaceAll(UnaryOperator<E> operator) {
3719 Objects.requireNonNull(operator);
3720 }
3721 @Override
3722 public void sort(Comparator<? super E> c) {
3723 Objects.requireNonNull(c);
3724 }
3725
3726 // Override default methods in Collection
3727 @Override
3728 public void forEach(Consumer<? super E> action) {
3729 Objects.requireNonNull(action);
3730 }
3731
3732 @Override
3733 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
3734
3735 // Preserves singleton property
3736 private Object readResolve() {
3737 return EMPTY_LIST;
3738 }
3739 }
3740
3741 /**
3742 * The empty map (immutable). This map is serializable.
3743 *
3744 * @see #emptyMap()
3745 * @since 1.3
3746 */
3747 @SuppressWarnings("rawtypes")
3748 public static final Map EMPTY_MAP = new EmptyMap<>();
3749
3750 /**
3751 * Returns the empty map (immutable). This map is serializable.
3752 *
3753 * <p>This example illustrates the type-safe way to obtain an empty set:
3754 * <pre>
3755 * Map<String, Date> s = Collections.emptyMap();
3756 * </pre>
3757 * Implementation note: Implementations of this method need not
3758 * create a separate <tt>Map</tt> object for each call. Using this
3759 * method is likely to have comparable cost to using the like-named
3760 * field. (Unlike this method, the field does not provide type safety.)
3761 *
3762 * @see #EMPTY_MAP
3763 * @since 1.5
3764 */
3765 @SuppressWarnings("unchecked")
3766 public static final <K,V> Map<K,V> emptyMap() {
3767 return (Map<K,V>) EMPTY_MAP;
3768 }
3769
3770 /**
3771 * @serial include
3772 */
3773 private static class EmptyMap<K,V>
3774 extends AbstractMap<K,V>
3775 implements Serializable
3776 {
3777 private static final long serialVersionUID = 6428348081105594320L;
3778
3779 public int size() {return 0;}
3780 public boolean isEmpty() {return true;}
3781 public boolean containsKey(Object key) {return false;}
3782 public boolean containsValue(Object value) {return false;}
3783 public V get(Object key) {return null;}
3784 public Set<K> keySet() {return emptySet();}
3785 public Collection<V> values() {return emptySet();}
3786 public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
3787
3788 public boolean equals(Object o) {
3789 return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
3790 }
3791
3792 public int hashCode() {return 0;}
3793
3794 // Override default methods in Map
3795 @Override
3796 @SuppressWarnings("unchecked")
3797 public V getOrDefault(Object k, V defaultValue) {
3798 return defaultValue;
3799 }
3800
3801 @Override
3802 public void forEach(BiConsumer<? super K, ? super V> action) {
3803 Objects.requireNonNull(action);
3804 }
3805
3806 @Override
3807 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
3808 Objects.requireNonNull(function);
3809 }
3810
3811 @Override
3812 public V putIfAbsent(K key, V value) {
3813 throw new UnsupportedOperationException();
3814 }
3815
3816 @Override
3817 public boolean remove(Object key, Object value) {
3818 throw new UnsupportedOperationException();
3819 }
3820
3821 @Override
3822 public boolean replace(K key, V oldValue, V newValue) {
3823 throw new UnsupportedOperationException();
3824 }
3825
3826 @Override
3827 public V replace(K key, V value) {
3828 throw new UnsupportedOperationException();
3829 }
3830
3831 @Override
3832 public V computeIfAbsent(K key,
3833 Function<? super K, ? extends V> mappingFunction) {
3834 throw new UnsupportedOperationException();
3835 }
3836
3837 @Override
3838 public V computeIfPresent(K key,
3839 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3840 throw new UnsupportedOperationException();
3841 }
3842
3843 @Override
3844 public V compute(K key,
3845 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
3846 throw new UnsupportedOperationException();
3847 }
3848
3849 @Override
3850 public V merge(K key, V value,
3851 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
3852 throw new UnsupportedOperationException();
3853 }
3854
3855 // Preserves singleton property
3856 private Object readResolve() {
3857 return EMPTY_MAP;
3858 }
3859 }
3860
3861 // Singleton collections
3862
3863 /**
3864 * Returns an immutable set containing only the specified object.
3865 * The returned set is serializable.
3866 *
3867 * @param o the sole object to be stored in the returned set.
3868 * @return an immutable set containing only the specified object.
3869 */
3870 public static <T> Set<T> singleton(T o) {
3871 return new SingletonSet<>(o);
3872 }
3873
3874 static <E> Iterator<E> singletonIterator(final E e) {
3875 return new Iterator<E>() {
3876 private boolean hasNext = true;
3877 public boolean hasNext() {
3878 return hasNext;
3879 }
3880 public E next() {
3881 if (hasNext) {
3882 hasNext = false;
3883 return e;
3884 }
3885 throw new NoSuchElementException();
3886 }
3887 public void remove() {
3888 throw new UnsupportedOperationException();
3889 }
3890 @Override
3891 public void forEachRemaining(Consumer<? super E> action) {
3892 Objects.requireNonNull(action);
3893 if (hasNext) {
3894 action.accept(e);
3895 hasNext = false;
3896 }
3897 }
3898 };
3899 }
3900
3901 /**
3902 * Creates a {@code Spliterator} with only the specified element
3903 *
3904 * @param <T> Type of elements
3905 * @return A singleton {@code Spliterator}
3906 */
3907 static <T> Spliterator<T> singletonSpliterator(final T element) {
3908 return new Spliterator<T>() {
3909 long est = 1;
3910
3911 @Override
3912 public Spliterator<T> trySplit() {
3913 return null;
3914 }
3915
3916 @Override
3917 public boolean tryAdvance(Consumer<? super T> consumer) {
3918 Objects.requireNonNull(consumer);
3919 if (est > 0) {
3920 est--;
3921 consumer.accept(element);
3922 return true;
3923 }
3924 return false;
3925 }
3926
3927 @Override
3928 public void forEachRemaining(Consumer<? super T> consumer) {
3929 tryAdvance(consumer);
3930 }
3931
3932 @Override
3933 public long estimateSize() {
3934 return est;
3935 }
3936
3937 @Override
3938 public int characteristics() {
3939 int value = (element != null) ? Spliterator.NONNULL : 0;
3940
3941 return value | Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE |
3942 Spliterator.DISTINCT | Spliterator.ORDERED;
3943 }
3944 };
3945 }
3946
3947 /**
3948 * @serial include
3949 */
3950 private static class SingletonSet<E>
3951 extends AbstractSet<E>
3952 implements Serializable
3953 {
3954 private static final long serialVersionUID = 3193687207550431679L;
3955
3956 private final E element;
3957
3958 SingletonSet(E e) {element = e;}
3959
3960 public Iterator<E> iterator() {
3961 return singletonIterator(element);
3962 }
3963
3964 public int size() {return 1;}
3965
3966 public boolean contains(Object o) {return eq(o, element);}
3967
3968 // Override default methods for Collection
3969 @Override
3970 public void forEach(Consumer<? super E> action) {
3971 action.accept(element);
3972 }
3973 @Override
3974 public Spliterator<E> spliterator() {
3975 return singletonSpliterator(element);
3976 }
3977 @Override
3978 public boolean removeIf(Predicate<? super E> filter) {
3979 throw new UnsupportedOperationException();
3980 }
3981 }
3982
3983 /**
3984 * Returns an immutable list containing only the specified object.
3985 * The returned list is serializable.
3986 *
3987 * @param o the sole object to be stored in the returned list.
3988 * @return an immutable list containing only the specified object.
3989 * @since 1.3
3990 */
3991 public static <T> List<T> singletonList(T o) {
3992 return new SingletonList<>(o);
3993 }
3994
3995 /**
3996 * @serial include
3997 */
3998 private static class SingletonList<E>
3999 extends AbstractList<E>
4000 implements RandomAccess, Serializable {
4001
4002 private static final long serialVersionUID = 3093736618740652951L;
4003
4004 private final E element;
4005
4006 SingletonList(E obj) {element = obj;}
4007
4008 public Iterator<E> iterator() {
4009 return singletonIterator(element);
4010 }
4011
4012 public int size() {return 1;}
4013
4014 public boolean contains(Object obj) {return eq(obj, element);}
4015
4016 public E get(int index) {
4017 if (index != 0)
4018 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
4019 return element;
4020 }
4021
4022 // Override default methods for Collection
4023 @Override
4024 public void forEach(Consumer<? super E> action) {
4025 action.accept(element);
4026 }
4027 @Override
4028 public boolean removeIf(Predicate<? super E> filter) {
4029 throw new UnsupportedOperationException();
4030 }
4031 @Override
4032 public void replaceAll(UnaryOperator<E> operator) {
4033 throw new UnsupportedOperationException();
4034 }
4035 @Override
4036 public void sort(Comparator<? super E> c) {
4037 }
4038 @Override
4039 public Spliterator<E> spliterator() {
4040 return singletonSpliterator(element);
4041 }
4042 }
4043
4044 /**
4045 * Returns an immutable map, mapping only the specified key to the
4046 * specified value. The returned map is serializable.
4047 *
4048 * @param key the sole key to be stored in the returned map.
4049 * @param value the value to which the returned map maps <tt>key</tt>.
4050 * @return an immutable map containing only the specified key-value
4051 * mapping.
4052 * @since 1.3
4053 */
4054 public static <K,V> Map<K,V> singletonMap(K key, V value) {
4055 return new SingletonMap<>(key, value);
4056 }
4057
4058 /**
4059 * @serial include
4060 */
4061 private static class SingletonMap<K,V>
4062 extends AbstractMap<K,V>
4063 implements Serializable {
4064 private static final long serialVersionUID = -6979724477215052911L;
4065
4066 private final K k;
4067 private final V v;
4068
4069 SingletonMap(K key, V value) {
4070 k = key;
4071 v = value;
4072 }
4073
4074 public int size() {return 1;}
4075
4076 public boolean isEmpty() {return false;}
4077
4078 public boolean containsKey(Object key) {return eq(key, k);}
4079
4080 public boolean containsValue(Object value) {return eq(value, v);}
4081
4082 public V get(Object key) {return (eq(key, k) ? v : null);}
4083
4084 private transient Set<K> keySet = null;
4085 private transient Set<Map.Entry<K,V>> entrySet = null;
4086 private transient Collection<V> values = null;
4087
4088 public Set<K> keySet() {
4089 if (keySet==null)
4090 keySet = singleton(k);
4091 return keySet;
4092 }
4093
4094 public Set<Map.Entry<K,V>> entrySet() {
4095 if (entrySet==null)
4096 entrySet = Collections.<Map.Entry<K,V>>singleton(
4097 new SimpleImmutableEntry<>(k, v));
4098 return entrySet;
4099 }
4100
4101 public Collection<V> values() {
4102 if (values==null)
4103 values = singleton(v);
4104 return values;
4105 }
4106
4107 // Override default methods in Map
4108 @Override
4109 public V getOrDefault(Object key, V defaultValue) {
4110 return eq(key, k) ? v : defaultValue;
4111 }
4112
4113 @Override
4114 public void forEach(BiConsumer<? super K, ? super V> action) {
4115 action.accept(k, v);
4116 }
4117
4118 @Override
4119 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
4120 throw new UnsupportedOperationException();
4121 }
4122
4123 @Override
4124 public V putIfAbsent(K key, V value) {
4125 throw new UnsupportedOperationException();
4126 }
4127
4128 @Override
4129 public boolean remove(Object key, Object value) {
4130 throw new UnsupportedOperationException();
4131 }
4132
4133 @Override
4134 public boolean replace(K key, V oldValue, V newValue) {
4135 throw new UnsupportedOperationException();
4136 }
4137
4138 @Override
4139 public V replace(K key, V value) {
4140 throw new UnsupportedOperationException();
4141 }
4142
4143 @Override
4144 public V computeIfAbsent(K key,
4145 Function<? super K, ? extends V> mappingFunction) {
4146 throw new UnsupportedOperationException();
4147 }
4148
4149 @Override
4150 public V computeIfPresent(K key,
4151 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
4152 throw new UnsupportedOperationException();
4153 }
4154
4155 @Override
4156 public V compute(K key,
4157 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
4158 throw new UnsupportedOperationException();
4159 }
4160
4161 @Override
4162 public V merge(K key, V value,
4163 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
4164 throw new UnsupportedOperationException();
4165 }
4166 }
4167
4168 // Miscellaneous
4169
4170 /**
4171 * Returns an immutable list consisting of <tt>n</tt> copies of the
4172 * specified object. The newly allocated data object is tiny (it contains
4173 * a single reference to the data object). This method is useful in
4174 * combination with the <tt>List.addAll</tt> method to grow lists.
4175 * The returned list is serializable.
4176 *
4177 * @param n the number of elements in the returned list.
4178 * @param o the element to appear repeatedly in the returned list.
4179 * @return an immutable list consisting of <tt>n</tt> copies of the
4180 * specified object.
4181 * @throws IllegalArgumentException if {@code n < 0}
4182 * @see List#addAll(Collection)
4183 * @see List#addAll(int, Collection)
4184 */
4185 public static <T> List<T> nCopies(int n, T o) {
4186 if (n < 0)
4187 throw new IllegalArgumentException("List length = " + n);
4188 return new CopiesList<>(n, o);
4189 }
4190
4191 /**
4192 * @serial include
4193 */
4194 private static class CopiesList<E>
4195 extends AbstractList<E>
4196 implements RandomAccess, Serializable
4197 {
4198 private static final long serialVersionUID = 2739099268398711800L;
4199
4200 final int n;
4201 final E element;
4202
4203 CopiesList(int n, E e) {
4204 assert n >= 0;
4205 this.n = n;
4206 element = e;
4207 }
4208
4209 public int size() {
4210 return n;
4211 }
4212
4213 public boolean contains(Object obj) {
4214 return n != 0 && eq(obj, element);
4215 }
4216
4217 public int indexOf(Object o) {
4218 return contains(o) ? 0 : -1;
4219 }
4220
4221 public int lastIndexOf(Object o) {
4222 return contains(o) ? n - 1 : -1;
4223 }
4224
4225 public E get(int index) {
4226 if (index < 0 || index >= n)
4227 throw new IndexOutOfBoundsException("Index: "+index+
4228 ", Size: "+n);
4229 return element;
4230 }
4231
4232 public Object[] toArray() {
4233 final Object[] a = new Object[n];
4234 if (element != null)
4235 Arrays.fill(a, 0, n, element);
4236 return a;
4237 }
4238
4239 @SuppressWarnings("unchecked")
4240 public <T> T[] toArray(T[] a) {
4241 final int n = this.n;
4242 if (a.length < n) {
4243 a = (T[])java.lang.reflect.Array
4244 .newInstance(a.getClass().getComponentType(), n);
4245 if (element != null)
4246 Arrays.fill(a, 0, n, element);
4247 } else {
4248 Arrays.fill(a, 0, n, element);
4249 if (a.length > n)
4250 a[n] = null;
4251 }
4252 return a;
4253 }
4254
4255 public List<E> subList(int fromIndex, int toIndex) {
4256 if (fromIndex < 0)
4257 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
4258 if (toIndex > n)
4259 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
4260 if (fromIndex > toIndex)
4261 throw new IllegalArgumentException("fromIndex(" + fromIndex +
4262 ") > toIndex(" + toIndex + ")");
4263 return new CopiesList<>(toIndex - fromIndex, element);
4264 }
4265 }
4266
4267 /**
4268 * Returns a comparator that imposes the reverse of the <em>natural
4269 * ordering</em> on a collection of objects that implement the
4270 * {@code Comparable} interface. (The natural ordering is the ordering
4271 * imposed by the objects' own {@code compareTo} method.) This enables a
4272 * simple idiom for sorting (or maintaining) collections (or arrays) of
4273 * objects that implement the {@code Comparable} interface in
4274 * reverse-natural-order. For example, suppose {@code a} is an array of
4275 * strings. Then: <pre>
4276 * Arrays.sort(a, Collections.reverseOrder());
4277 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
4278 *
4279 * The returned comparator is serializable.
4280 *
4281 * @return A comparator that imposes the reverse of the <i>natural
4282 * ordering</i> on a collection of objects that implement
4283 * the <tt>Comparable</tt> interface.
4284 * @see Comparable
4285 */
4286 @SuppressWarnings("unchecked")
4287 public static <T> Comparator<T> reverseOrder() {
4288 return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
4289 }
4290
4291 /**
4292 * @serial include
4293 */
4294 private static class ReverseComparator
4295 implements Comparator<Comparable<Object>>, Serializable {
4296
4297 private static final long serialVersionUID = 7207038068494060240L;
4298
4299 static final ReverseComparator REVERSE_ORDER
4300 = new ReverseComparator();
4301
4302 public int compare(Comparable<Object> c1, Comparable<Object> c2) {
4303 return c2.compareTo(c1);
4304 }
4305
4306 private Object readResolve() { return Collections.reverseOrder(); }
4307 }
4308
4309 /**
4310 * Returns a comparator that imposes the reverse ordering of the specified
4311 * comparator. If the specified comparator is {@code null}, this method is
4312 * equivalent to {@link #reverseOrder()} (in other words, it returns a
4313 * comparator that imposes the reverse of the <em>natural ordering</em> on
4314 * a collection of objects that implement the Comparable interface).
4315 *
4316 * <p>The returned comparator is serializable (assuming the specified
4317 * comparator is also serializable or {@code null}).
4318 *
4319 * @param cmp a comparator who's ordering is to be reversed by the returned
4320 * comparator or {@code null}
4321 * @return A comparator that imposes the reverse ordering of the
4322 * specified comparator.
4323 * @since 1.5
4324 */
4325 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
4326 if (cmp == null)
4327 return reverseOrder();
4328
4329 if (cmp instanceof ReverseComparator2)
4330 return ((ReverseComparator2<T>)cmp).cmp;
4331
4332 return new ReverseComparator2<>(cmp);
4333 }
4334
4335 /**
4336 * @serial include
4337 */
4338 private static class ReverseComparator2<T> implements Comparator<T>,
4339 Serializable
4340 {
4341 private static final long serialVersionUID = 4374092139857L;
4342
4343 /**
4344 * The comparator specified in the static factory. This will never
4345 * be null, as the static factory returns a ReverseComparator
4346 * instance if its argument is null.
4347 *
4348 * @serial
4349 */
4350 final Comparator<T> cmp;
4351
4352 ReverseComparator2(Comparator<T> cmp) {
4353 assert cmp != null;
4354 this.cmp = cmp;
4355 }
4356
4357 public int compare(T t1, T t2) {
4358 return cmp.compare(t2, t1);
4359 }
4360
4361 public boolean equals(Object o) {
4362 return (o == this) ||
4363 (o instanceof ReverseComparator2 &&
4364 cmp.equals(((ReverseComparator2)o).cmp));
4365 }
4366
4367 public int hashCode() {
4368 return cmp.hashCode() ^ Integer.MIN_VALUE;
4369 }
4370 }
4371
4372 /**
4373 * Returns an enumeration over the specified collection. This provides
4374 * interoperability with legacy APIs that require an enumeration
4375 * as input.
4376 *
4377 * @param c the collection for which an enumeration is to be returned.
4378 * @return an enumeration over the specified collection.
4379 * @see Enumeration
4380 */
4381 public static <T> Enumeration<T> enumeration(final Collection<T> c) {
4382 return new Enumeration<T>() {
4383 private final Iterator<T> i = c.iterator();
4384
4385 public boolean hasMoreElements() {
4386 return i.hasNext();
4387 }
4388
4389 public T nextElement() {
4390 return i.next();
4391 }
4392 };
4393 }
4394
4395 /**
4396 * Returns an array list containing the elements returned by the
4397 * specified enumeration in the order they are returned by the
4398 * enumeration. This method provides interoperability between
4399 * legacy APIs that return enumerations and new APIs that require
4400 * collections.
4401 *
4402 * @param e enumeration providing elements for the returned
4403 * array list
4404 * @return an array list containing the elements returned
4405 * by the specified enumeration.
4406 * @since 1.4
4407 * @see Enumeration
4408 * @see ArrayList
4409 */
4410 public static <T> ArrayList<T> list(Enumeration<T> e) {
4411 ArrayList<T> l = new ArrayList<>();
4412 while (e.hasMoreElements())
4413 l.add(e.nextElement());
4414 return l;
4415 }
4416
4417 /**
4418 * Returns true if the specified arguments are equal, or both null.
4419 */
4420 static boolean eq(Object o1, Object o2) {
4421 return o1==null ? o2==null : o1.equals(o2);
4422 }
4423
4424 /**
4425 * Returns the number of elements in the specified collection equal to the
4426 * specified object. More formally, returns the number of elements
4427 * <tt>e</tt> in the collection such that
4428 * <tt>(o == null ? e == null : o.equals(e))</tt>.
4429 *
4430 * @param c the collection in which to determine the frequency
4431 * of <tt>o</tt>
4432 * @param o the object whose frequency is to be determined
4433 * @throws NullPointerException if <tt>c</tt> is null
4434 * @since 1.5
4435 */
4436 public static int frequency(Collection<?> c, Object o) {
4437 int result = 0;
4438 if (o == null) {
4439 for (Object e : c)
4440 if (e == null)
4441 result++;
4442 } else {
4443 for (Object e : c)
4444 if (o.equals(e))
4445 result++;
4446 }
4447 return result;
4448 }
4449
4450 /**
4451 * Returns {@code true} if the two specified collections have no
4452 * elements in common.
4453 *
4454 * <p>Care must be exercised if this method is used on collections that
4455 * do not comply with the general contract for {@code Collection}.
4456 * Implementations may elect to iterate over either collection and test
4457 * for containment in the other collection (or to perform any equivalent
4458 * computation). If either collection uses a nonstandard equality test
4459 * (as does a {@link SortedSet} whose ordering is not <em>compatible with
4460 * equals</em>, or the key set of an {@link IdentityHashMap}), both
4461 * collections must use the same nonstandard equality test, or the
4462 * result of this method is undefined.
4463 *
4464 * <p>Care must also be exercised when using collections that have
4465 * restrictions on the elements that they may contain. Collection
4466 * implementations are allowed to throw exceptions for any operation
4467 * involving elements they deem ineligible. For absolute safety the
4468 * specified collections should contain only elements which are
4469 * eligible elements for both collections.
4470 *
4471 * <p>Note that it is permissible to pass the same collection in both
4472 * parameters, in which case the method will return {@code true} if and
4473 * only if the collection is empty.
4474 *
4475 * @param c1 a collection
4476 * @param c2 a collection
4477 * @return {@code true} if the two specified collections have no
4478 * elements in common.
4479 * @throws NullPointerException if either collection is {@code null}.
4480 * @throws NullPointerException if one collection contains a {@code null}
4481 * element and {@code null} is not an eligible element for the other collection.
4482 * (<a href="Collection.html#optional-restrictions">optional</a>)
4483 * @throws ClassCastException if one collection contains an element that is
4484 * of a type which is ineligible for the other collection.
4485 * (<a href="Collection.html#optional-restrictions">optional</a>)
4486 * @since 1.5
4487 */
4488 public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
4489 // The collection to be used for contains(). Preference is given to
4490 // the collection who's contains() has lower O() complexity.
4491 Collection<?> contains = c2;
4492 // The collection to be iterated. If the collections' contains() impl
4493 // are of different O() complexity, the collection with slower
4494 // contains() will be used for iteration. For collections who's
4495 // contains() are of the same complexity then best performance is
4496 // achieved by iterating the smaller collection.
4497 Collection<?> iterate = c1;
4498
4499 // Performance optimization cases. The heuristics:
4500 // 1. Generally iterate over c1.
4501 // 2. If c1 is a Set then iterate over c2.
4502 // 3. If either collection is empty then result is always true.
4503 // 4. Iterate over the smaller Collection.
4504 if (c1 instanceof Set) {
4505 // Use c1 for contains as a Set's contains() is expected to perform
4506 // better than O(N/2)
4507 iterate = c2;
4508 contains = c1;
4509 } else if (!(c2 instanceof Set)) {
4510 // Both are mere Collections. Iterate over smaller collection.
4511 // Example: If c1 contains 3 elements and c2 contains 50 elements and
4512 // assuming contains() requires ceiling(N/2) comparisons then
4513 // checking for all c1 elements in c2 would require 75 comparisons
4514 // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring
4515 // 100 comparisons (50 * ceiling(3/2)).
4516 int c1size = c1.size();
4517 int c2size = c2.size();
4518 if (c1size == 0 || c2size == 0) {
4519 // At least one collection is empty. Nothing will match.
4520 return true;
4521 }
4522
4523 if (c1size > c2size) {
4524 iterate = c2;
4525 contains = c1;
4526 }
4527 }
4528
4529 for (Object e : iterate) {
4530 if (contains.contains(e)) {
4531 // Found a common element. Collections are not disjoint.
4532 return false;
4533 }
4534 }
4535
4536 // No common elements were found.
4537 return true;
4538 }
4539
4540 /**
4541 * Adds all of the specified elements to the specified collection.
4542 * Elements to be added may be specified individually or as an array.
4543 * The behavior of this convenience method is identical to that of
4544 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely
4545 * to run significantly faster under most implementations.
4546 *
4547 * <p>When elements are specified individually, this method provides a
4548 * convenient way to add a few elements to an existing collection:
4549 * <pre>
4550 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
4551 * </pre>
4552 *
4553 * @param c the collection into which <tt>elements</tt> are to be inserted
4554 * @param elements the elements to insert into <tt>c</tt>
4555 * @return <tt>true</tt> if the collection changed as a result of the call
4556 * @throws UnsupportedOperationException if <tt>c</tt> does not support
4557 * the <tt>add</tt> operation
4558 * @throws NullPointerException if <tt>elements</tt> contains one or more
4559 * null values and <tt>c</tt> does not permit null elements, or
4560 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
4561 * @throws IllegalArgumentException if some property of a value in
4562 * <tt>elements</tt> prevents it from being added to <tt>c</tt>
4563 * @see Collection#addAll(Collection)
4564 * @since 1.5
4565 */
4566 @SafeVarargs
4567 public static <T> boolean addAll(Collection<? super T> c, T... elements) {
4568 boolean result = false;
4569 for (T element : elements)
4570 result |= c.add(element);
4571 return result;
4572 }
4573
4574 /**
4575 * Returns a set backed by the specified map. The resulting set displays
4576 * the same ordering, concurrency, and performance characteristics as the
4577 * backing map. In essence, this factory method provides a {@link Set}
4578 * implementation corresponding to any {@link Map} implementation. There
4579 * is no need to use this method on a {@link Map} implementation that
4580 * already has a corresponding {@link Set} implementation (such as {@link
4581 * HashMap} or {@link TreeMap}).
4582 *
4583 * <p>Each method invocation on the set returned by this method results in
4584 * exactly one method invocation on the backing map or its <tt>keySet</tt>
4585 * view, with one exception. The <tt>addAll</tt> method is implemented
4586 * as a sequence of <tt>put</tt> invocations on the backing map.
4587 *
4588 * <p>The specified map must be empty at the time this method is invoked,
4589 * and should not be accessed directly after this method returns. These
4590 * conditions are ensured if the map is created empty, passed directly
4591 * to this method, and no reference to the map is retained, as illustrated
4592 * in the following code fragment:
4593 * <pre>
4594 * Set<Object> weakHashSet = Collections.newSetFromMap(
4595 * new WeakHashMap<Object, Boolean>());
4596 * </pre>
4597 *
4598 * @param map the backing map
4599 * @return the set backed by the map
4600 * @throws IllegalArgumentException if <tt>map</tt> is not empty
4601 * @since 1.6
4602 */
4603 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
4604 return new SetFromMap<>(map);
4605 }
4606
4607 /**
4608 * @serial include
4609 */
4610 private static class SetFromMap<E> extends AbstractSet<E>
4611 implements Set<E>, Serializable
4612 {
4613 private final Map<E, Boolean> m; // The backing map
4614 private transient Set<E> s; // Its keySet
4615
4616 SetFromMap(Map<E, Boolean> map) {
4617 if (!map.isEmpty())
4618 throw new IllegalArgumentException("Map is non-empty");
4619 m = map;
4620 s = map.keySet();
4621 }
4622
4623 public void clear() { m.clear(); }
4624 public int size() { return m.size(); }
4625 public boolean isEmpty() { return m.isEmpty(); }
4626 public boolean contains(Object o) { return m.containsKey(o); }
4627 public boolean remove(Object o) { return m.remove(o) != null; }
4628 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
4629 public Iterator<E> iterator() { return s.iterator(); }
4630 public Object[] toArray() { return s.toArray(); }
4631 public <T> T[] toArray(T[] a) { return s.toArray(a); }
4632 public String toString() { return s.toString(); }
4633 public int hashCode() { return s.hashCode(); }
4634 public boolean equals(Object o) { return o == this || s.equals(o); }
4635 public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
4636 public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
4637 public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
4638 // addAll is the only inherited implementation
4639
4640 // Override default methods in Collection
4641 @Override
4642 public void forEach(Consumer<? super E> action) {
4643 s.forEach(action);
4644 }
4645 @Override
4646 public boolean removeIf(Predicate<? super E> filter) {
4647 return s.removeIf(filter);
4648 }
4649
4650 @Override
4651 public Spliterator<E> spliterator() {return s.spliterator();}
4652
4653 private static final long serialVersionUID = 2454657854757543876L;
4654
4655 private void readObject(java.io.ObjectInputStream stream)
4656 throws IOException, ClassNotFoundException
4657 {
4658 stream.defaultReadObject();
4659 s = m.keySet();
4660 }
4661 }
4662
4663 /**
4664 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
4665 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
4666 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
4667 * view can be useful when you would like to use a method
4668 * requiring a <tt>Queue</tt> but you need Lifo ordering.
4669 *
4670 * <p>Each method invocation on the queue returned by this method
4671 * results in exactly one method invocation on the backing deque, with
4672 * one exception. The {@link Queue#addAll addAll} method is
4673 * implemented as a sequence of {@link Deque#addFirst addFirst}
4674 * invocations on the backing deque.
4675 *
4676 * @param deque the deque
4677 * @return the queue
4678 * @since 1.6
4679 */
4680 public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
4681 return new AsLIFOQueue<>(deque);
4682 }
4683
4684 /**
4685 * @serial include
4686 */
4687 static class AsLIFOQueue<E> extends AbstractQueue<E>
4688 implements Queue<E>, Serializable {
4689 private static final long serialVersionUID = 1802017725587941708L;
4690 private final Deque<E> q;
4691 AsLIFOQueue(Deque<E> q) { this.q = q; }
4692 public boolean add(E e) { q.addFirst(e); return true; }
4693 public boolean offer(E e) { return q.offerFirst(e); }
4694 public E poll() { return q.pollFirst(); }
4695 public E remove() { return q.removeFirst(); }
4696 public E peek() { return q.peekFirst(); }
4697 public E element() { return q.getFirst(); }
4698 public void clear() { q.clear(); }
4699 public int size() { return q.size(); }
4700 public boolean isEmpty() { return q.isEmpty(); }
4701 public boolean contains(Object o) { return q.contains(o); }
4702 public boolean remove(Object o) { return q.remove(o); }
4703 public Iterator<E> iterator() { return q.iterator(); }
4704 public Object[] toArray() { return q.toArray(); }
4705 public <T> T[] toArray(T[] a) { return q.toArray(a); }
4706 public String toString() { return q.toString(); }
4707 public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
4708 public boolean removeAll(Collection<?> c) {return q.removeAll(c);}
4709 public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
4710 // We use inherited addAll; forwarding addAll would be wrong
4711
4712 // Override default methods in Collection
4713 @Override
4714 public void forEach(Consumer<? super E> action) {q.forEach(action);}
4715 @Override
4716 public Spliterator<E> spliterator() {return q.spliterator();}
4717 @Override
4718 public boolean removeIf(Predicate<? super E> filter) {
4719 return q.removeIf(filter);
4720 }
4721 }
4722 }