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