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