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