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