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