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