    rev 48045 : 8177290: add copy factory methods for unmodifiable List, Set, Map
    8184690: add Collectors for collecting into unmodifiable List, Set, and Map
    Reviewed-by: alanb, briangoetz, dholmes, jrose, rriggs, scolebourne

       1 /*
       2  * Copyright (c) 1997, 2017, 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 {@code NullPointerException}
      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 {@code sort} 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 {@code UnsupportedOperationException} if the collection does not
      61  * support the appropriate mutation primitive(s), such as the {@code set}
      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 {@code sort} method on an unmodifiable list that is
      65  * already sorted may or may not throw {@code UnsupportedOperationException}.
      66  *
      67  * <p>This class is a member of the
      68  * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
      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      * @implNote
     125      * This implementation defers to the {@link List#sort(Comparator)}
     126      * method using the specified list and a {@code null} comparator.
     127      *
     128      * @param  <T> the class of the objects in the list
     129      * @param  list the list to be sorted.
     130      * @throws ClassCastException if the list contains elements that are not
     131      *         <i>mutually comparable</i> (for example, strings and integers).
     132      * @throws UnsupportedOperationException if the specified list's
     133      *         list-iterator does not support the {@code set} operation.
     134      * @throws IllegalArgumentException (optional) if the implementation
     135      *         detects that the natural ordering of the list elements is
     136      *         found to violate the {@link Comparable} contract
     137      * @see List#sort(Comparator)
     138      */
     139     @SuppressWarnings("unchecked")
     140     public static <T extends Comparable<? super T>> void sort(List<T> list) {
     141         list.sort(null);
     142     }
     143
     144     /**
     145      * Sorts the specified list according to the order induced by the
     146      * specified comparator.  All elements in the list must be <i>mutually
     147      * comparable</i> using the specified comparator (that is,
     148      * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
     149      * for any elements {@code e1} and {@code e2} in the list).
     150      *
     151      * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
     152      * not be reordered as a result of the sort.
     153      *
     154      * <p>The specified list must be modifiable, but need not be resizable.
     155      *
     156      * @implNote
     157      * This implementation defers to the {@link List#sort(Comparator)}
     158      * method using the specified list and comparator.
     159      *
     160      * @param  <T> the class of the objects in the list
     161      * @param  list the list to be sorted.
     162      * @param  c the comparator to determine the order of the list.  A
     163      *        {@code null} value indicates that the elements' <i>natural
     164      *        ordering</i> should be used.
     165      * @throws ClassCastException if the list contains elements that are not
     166      *         <i>mutually comparable</i> using the specified comparator.
     167      * @throws UnsupportedOperationException if the specified list's
     168      *         list-iterator does not support the {@code set} operation.
     169      * @throws IllegalArgumentException (optional) if the comparator is
     170      *         found to violate the {@link Comparator} contract
     171      * @see List#sort(Comparator)
     172      */
     173     @SuppressWarnings({"unchecked", "rawtypes"})
     174     public static <T> void sort(List<T> list, Comparator<? super T> c) {
     175         list.sort(c);
     176     }
     177
     178
     179     /**
     180      * Searches the specified list for the specified object using the binary
     181      * search algorithm.  The list must be sorted into ascending order
     182      * according to the {@linkplain Comparable natural ordering} of its
     183      * elements (as by the {@link #sort(List)} method) prior to making this
     184      * call.  If it is not sorted, the results are undefined.  If the list
     185      * contains multiple elements equal to the specified object, there is no
     186      * guarantee which one will be found.
     187      *
     188      * <p>This method runs in log(n) time for a "random access" list (which
     189      * provides near-constant-time positional access).  If the specified list
     190      * does not implement the {@link RandomAccess} interface and is large,
     191      * this method will do an iterator-based binary search that performs
     192      * O(n) link traversals and O(log n) element comparisons.
     193      *
     194      * @param  <T> the class of the objects in the list
     195      * @param  list the list to be searched.
     196      * @param  key the key to be searched for.
     197      * @return the index of the search key, if it is contained in the list;
     198      *         otherwise, <code>(-(<i>insertion point</i>) - 1)</code>.  The
     199      *         <i>insertion point</i> is defined as the point at which the
     200      *         key would be inserted into the list: the index of the first
     201      *         element greater than the key, or {@code list.size()} if all
     202      *         elements in the list are less than the specified key.  Note
     203      *         that this guarantees that the return value will be &gt;= 0 if
     204      *         and only if the key is found.
     205      * @throws ClassCastException if the list contains elements that are not
     206      *         <i>mutually comparable</i> (for example, strings and
     207      *         integers), or the search key is not mutually comparable
     208      *         with the elements of the list.
     209      */
     210     public static <T>
     211     int binarySearch(List<? extends Comparable<? super T>> list, T key) {
     212         if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
     213             return Collections.indexedBinarySearch(list, key);
     214         else
     215             return Collections.iteratorBinarySearch(list, key);
     216     }
     217
     218     private static <T>
     219     int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
     220         int low = 0;
     221         int high = list.size()-1;
     222
     223         while (low <= high) {
     224             int mid = (low + high) >>> 1;
     225             Comparable<? super T> midVal = list.get(mid);
     226             int cmp = midVal.compareTo(key);
     227
     228             if (cmp < 0)
     229                 low = mid + 1;
     230             else if (cmp > 0)
     231                 high = mid - 1;
     232             else
     233                 return mid; // key found
     234         }
     235         return -(low + 1);  // key not found
     236     }
     237
     238     private static <T>
     239     int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
     240     {
     241         int low = 0;
     242         int high = list.size()-1;
     243         ListIterator<? extends Comparable<? super T>> i = list.listIterator();
     244
     245         while (low <= high) {
     246             int mid = (low + high) >>> 1;
     247             Comparable<? super T> midVal = get(i, mid);
     248             int cmp = midVal.compareTo(key);
     249
     250             if (cmp < 0)
     251                 low = mid + 1;
     252             else if (cmp > 0)
     253                 high = mid - 1;
     254             else
     255                 return mid; // key found
     256         }
     257         return -(low + 1);  // key not found
     258     }
     259
     260     /**
     261      * Gets the ith element from the given list by repositioning the specified
     262      * list listIterator.
     263      */
     264     private static <T> T get(ListIterator<? extends T> i, int index) {
     265         T obj = null;
     266         int pos = i.nextIndex();
     267         if (pos <= index) {
     268             do {
     269                 obj = i.next();
     270             } while (pos++ < index);
     271         } else {
     272             do {
     273                 obj = i.previous();
     274             } while (--pos > index);
     275         }
     276         return obj;
     277     }
     278
     279     /**
     280      * Searches the specified list for the specified object using the binary
     281      * search algorithm.  The list must be sorted into ascending order
     282      * according to the specified comparator (as by the
     283      * {@link #sort(List, Comparator) sort(List, Comparator)}
     284      * method), prior to making this call.  If it is
     285      * not sorted, the results are undefined.  If the list contains multiple
     286      * elements equal to the specified object, there is no guarantee which one
     287      * will be found.
     288      *
     289      * <p>This method runs in log(n) time for a "random access" list (which
     290      * provides near-constant-time positional access).  If the specified list
     291      * does not implement the {@link RandomAccess} interface and is large,
     292      * this method will do an iterator-based binary search that performs
     293      * O(n) link traversals and O(log n) element comparisons.
     294      *
     295      * @param  <T> the class of the objects in the list
     296      * @param  list the list to be searched.
     297      * @param  key the key to be searched for.
     298      * @param  c the comparator by which the list is ordered.
     299      *         A {@code null} value indicates that the elements'
     300      *         {@linkplain Comparable natural ordering} should be used.
     301      * @return the index of the search key, if it is contained in the list;
     302      *         otherwise, <code>(-(<i>insertion point</i>) - 1)</code>.  The
     303      *         <i>insertion point</i> is defined as the point at which the
     304      *         key would be inserted into the list: the index of the first
     305      *         element greater than the key, or {@code list.size()} if all
     306      *         elements in the list are less than the specified key.  Note
     307      *         that this guarantees that the return value will be &gt;= 0 if
     308      *         and only if the key is found.
     309      * @throws ClassCastException if the list contains elements that are not
     310      *         <i>mutually comparable</i> using the specified comparator,
     311      *         or the search key is not mutually comparable with the
     312      *         elements of the list using this comparator.
     313      */
     314     @SuppressWarnings("unchecked")
     315     public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
     316         if (c==null)
     317             return binarySearch((List<? extends Comparable<? super T>>) list, key);
     318
     319         if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
     320             return Collections.indexedBinarySearch(list, key, c);
     321         else
     322             return Collections.iteratorBinarySearch(list, key, c);
     323     }
     324
     325     private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
     326         int low = 0;
     327         int high = l.size()-1;
     328
     329         while (low <= high) {
     330             int mid = (low + high) >>> 1;
     331             T midVal = l.get(mid);
     332             int cmp = c.compare(midVal, key);
     333
     334             if (cmp < 0)
     335                 low = mid + 1;
     336             else if (cmp > 0)
     337                 high = mid - 1;
     338             else
     339                 return mid; // key found
     340         }
     341         return -(low + 1);  // key not found
     342     }
     343
     344     private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
     345         int low = 0;
     346         int high = l.size()-1;
     347         ListIterator<? extends T> i = l.listIterator();
     348
     349         while (low <= high) {
     350             int mid = (low + high) >>> 1;
     351             T midVal = get(i, mid);
     352             int cmp = c.compare(midVal, key);
     353
     354             if (cmp < 0)
     355                 low = mid + 1;
     356             else if (cmp > 0)
     357                 high = mid - 1;
     358             else
     359                 return mid; // key found
     360         }
     361         return -(low + 1);  // key not found
     362     }
     363
     364     /**
     365      * Reverses the order of the elements in the specified list.<p>
     366      *
     367      * This method runs in linear time.
     368      *
     369      * @param  list the list whose elements are to be reversed.
     370      * @throws UnsupportedOperationException if the specified list or
     371      *         its list-iterator does not support the {@code set} operation.
     372      */
     373     @SuppressWarnings({"rawtypes", "unchecked"})
     374     public static void reverse(List<?> list) {
     375         int size = list.size();
     376         if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
     377             for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
     378                 swap(list, i, j);
     379         } else {
     380             // instead of using a raw type here, it's possible to capture
     381             // the wildcard but it will require a call to a supplementary
     382             // private method
     383             ListIterator fwd = list.listIterator();
     384             ListIterator rev = list.listIterator(size);
     385             for (int i=0, mid=list.size()>>1; i<mid; i++) {
     386                 Object tmp = fwd.next();
     387                 fwd.set(rev.previous());
     388                 rev.set(tmp);
     389             }
     390         }
     391     }
     392
     393     /**
     394      * Randomly permutes the specified list using a default source of
     395      * randomness.  All permutations occur with approximately equal
     396      * likelihood.
     397      *
     398      * <p>The hedge "approximately" is used in the foregoing description because
     399      * default source of randomness is only approximately an unbiased source
     400      * of independently chosen bits. If it were a perfect source of randomly
     401      * chosen bits, then the algorithm would choose permutations with perfect
     402      * uniformity.
     403      *
     404      * <p>This implementation traverses the list backwards, from the last
     405      * element up to the second, repeatedly swapping a randomly selected element
     406      * into the "current position".  Elements are randomly selected from the
     407      * portion of the list that runs from the first element to the current
     408      * position, inclusive.
     409      *
     410      * <p>This method runs in linear time.  If the specified list does not
     411      * implement the {@link RandomAccess} interface and is large, this
     412      * implementation dumps the specified list into an array before shuffling
     413      * it, and dumps the shuffled array back into the list.  This avoids the
     414      * quadratic behavior that would result from shuffling a "sequential
     415      * access" list in place.
     416      *
     417      * @param  list the list to be shuffled.
     418      * @throws UnsupportedOperationException if the specified list or
     419      *         its list-iterator does not support the {@code set} operation.
     420      */
     421     public static void shuffle(List<?> list) {
     422         Random rnd = r;
     423         if (rnd == null)
     424             r = rnd = new Random(); // harmless race.
     425         shuffle(list, rnd);
     426     }
     427
     428     private static Random r;
     429
     430     /**
     431      * Randomly permute the specified list using the specified source of
     432      * randomness.  All permutations occur with equal likelihood
     433      * assuming that the source of randomness is fair.<p>
     434      *
     435      * This implementation traverses the list backwards, from the last element
     436      * up to the second, repeatedly swapping a randomly selected element into
     437      * the "current position".  Elements are randomly selected from the
     438      * portion of the list that runs from the first element to the current
     439      * position, inclusive.<p>
     440      *
     441      * This method runs in linear time.  If the specified list does not
     442      * implement the {@link RandomAccess} interface and is large, this
     443      * implementation dumps the specified list into an array before shuffling
     444      * it, and dumps the shuffled array back into the list.  This avoids the
     445      * quadratic behavior that would result from shuffling a "sequential
     446      * access" list in place.
     447      *
     448      * @param  list the list to be shuffled.
     449      * @param  rnd the source of randomness to use to shuffle the list.
     450      * @throws UnsupportedOperationException if the specified list or its
     451      *         list-iterator does not support the {@code set} operation.
     452      */
     453     @SuppressWarnings({"rawtypes", "unchecked"})
     454     public static void shuffle(List<?> list, Random rnd) {
     455         int size = list.size();
     456         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
     457             for (int i=size; i>1; i--)
     458                 swap(list, i-1, rnd.nextInt(i));
     459         } else {
     460             Object arr[] = list.toArray();
     461
     462             // Shuffle array
     463             for (int i=size; i>1; i--)
     464                 swap(arr, i-1, rnd.nextInt(i));
     465
     466             // Dump array back into list
     467             // instead of using a raw type here, it's possible to capture
     468             // the wildcard but it will require a call to a supplementary
     469             // private method
     470             ListIterator it = list.listIterator();
     471             for (Object e : arr) {
     472                 it.next();
     473                 it.set(e);
     474             }
     475         }
     476     }
     477
     478     /**
     479      * Swaps the elements at the specified positions in the specified list.
     480      * (If the specified positions are equal, invoking this method leaves
     481      * the list unchanged.)
     482      *
     483      * @param list The list in which to swap elements.
     484      * @param i the index of one element to be swapped.
     485      * @param j the index of the other element to be swapped.
     486      * @throws IndexOutOfBoundsException if either {@code i} or {@code j}
     487      *         is out of range (i &lt; 0 || i &gt;= list.size()
     488      *         || j &lt; 0 || j &gt;= list.size()).
     489      * @since 1.4
     490      */
     491     @SuppressWarnings({"rawtypes", "unchecked"})
     492     public static void swap(List<?> list, int i, int j) {
     493         // instead of using a raw type here, it's possible to capture
     494         // the wildcard but it will require a call to a supplementary
     495         // private method
     496         final List l = list;
     497         l.set(i, l.set(j, l.get(i)));
     498     }
     499
     500     /**
     501      * Swaps the two specified elements in the specified array.
     502      */
     503     private static void swap(Object[] arr, int i, int j) {
     504         Object tmp = arr[i];
     505         arr[i] = arr[j];
     506         arr[j] = tmp;
     507     }
     508
     509     /**
     510      * Replaces all of the elements of the specified list with the specified
     511      * element. <p>
     512      *
     513      * This method runs in linear time.
     514      *
     515      * @param  <T> the class of the objects in the list
     516      * @param  list the list to be filled with the specified element.
     517      * @param  obj The element with which to fill the specified list.
     518      * @throws UnsupportedOperationException if the specified list or its
     519      *         list-iterator does not support the {@code set} operation.
     520      */
     521     public static <T> void fill(List<? super T> list, T obj) {
     522         int size = list.size();
     523
     524         if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
     525             for (int i=0; i<size; i++)
     526                 list.set(i, obj);
     527         } else {
     528             ListIterator<? super T> itr = list.listIterator();
     529             for (int i=0; i<size; i++) {
     530                 itr.next();
     531                 itr.set(obj);
     532             }
     533         }
     534     }
     535
     536     /**
     537      * Copies all of the elements from one list into another.  After the
     538      * operation, the index of each copied element in the destination list
     539      * will be identical to its index in the source list.  The destination
     540      * list's size must be greater than or equal to the source list's size.
     541      * If it is greater, the remaining elements in the destination list are
     542      * unaffected. <p>
     543      *
     544      * This method runs in linear time.
     545      *
     546      * @param  <T> the class of the objects in the lists
     547      * @param  dest The destination list.
     548      * @param  src The source list.
     549      * @throws IndexOutOfBoundsException if the destination list is too small
     550      *         to contain the entire source List.
     551      * @throws UnsupportedOperationException if the destination list's
     552      *         list-iterator does not support the {@code set} operation.
     553      */
     554     public static <T> void copy(List<? super T> dest, List<? extends T> src) {
     555         int srcSize = src.size();
     556         if (srcSize > dest.size())
     557             throw new IndexOutOfBoundsException("Source does not fit in dest");
     558
     559         if (srcSize < COPY_THRESHOLD ||
     560             (src instanceof RandomAccess && dest instanceof RandomAccess)) {
     561             for (int i=0; i<srcSize; i++)
     562                 dest.set(i, src.get(i));
     563         } else {
     564             ListIterator<? super T> di=dest.listIterator();
     565             ListIterator<? extends T> si=src.listIterator();
     566             for (int i=0; i<srcSize; i++) {
     567                 di.next();
     568                 di.set(si.next());
     569             }
     570         }
     571     }
     572
     573     /**
     574      * Returns the minimum element of the given collection, according to the
     575      * <i>natural ordering</i> of its elements.  All elements in the
     576      * collection must implement the {@code Comparable} interface.
     577      * Furthermore, all elements in the collection must be <i>mutually
     578      * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
     579      * {@code ClassCastException} for any elements {@code e1} and
     580      * {@code e2} in the collection).<p>
     581      *
     582      * This method iterates over the entire collection, hence it requires
     583      * time proportional to the size of the collection.
     584      *
     585      * @param  <T> the class of the objects in the collection
     586      * @param  coll the collection whose minimum element is to be determined.
     587      * @return the minimum element of the given collection, according
     588      *         to the <i>natural ordering</i> of its elements.
     589      * @throws ClassCastException if the collection contains elements that are
     590      *         not <i>mutually comparable</i> (for example, strings and
     591      *         integers).
     592      * @throws NoSuchElementException if the collection is empty.
     593      * @see Comparable
     594      */
     595     public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
     596         Iterator<? extends T> i = coll.iterator();
     597         T candidate = i.next();
     598
     599         while (i.hasNext()) {
     600             T next = i.next();
     601             if (next.compareTo(candidate) < 0)
     602                 candidate = next;
     603         }
     604         return candidate;
     605     }
     606
     607     /**
     608      * Returns the minimum element of the given collection, according to the
     609      * order induced by the specified comparator.  All elements in the
     610      * collection must be <i>mutually comparable</i> by the specified
     611      * comparator (that is, {@code comp.compare(e1, e2)} must not throw a
     612      * {@code ClassCastException} for any elements {@code e1} and
     613      * {@code e2} in the collection).<p>
     614      *
     615      * This method iterates over the entire collection, hence it requires
     616      * time proportional to the size of the collection.
     617      *
     618      * @param  <T> the class of the objects in the collection
     619      * @param  coll the collection whose minimum element is to be determined.
     620      * @param  comp the comparator with which to determine the minimum element.
     621      *         A {@code null} value indicates that the elements' <i>natural
     622      *         ordering</i> should be used.
     623      * @return the minimum element of the given collection, according
     624      *         to the specified comparator.
     625      * @throws ClassCastException if the collection contains elements that are
     626      *         not <i>mutually comparable</i> using the specified comparator.
     627      * @throws NoSuchElementException if the collection is empty.
     628      * @see Comparable
     629      */
     630     @SuppressWarnings({"unchecked", "rawtypes"})
     631     public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
     632         if (comp==null)
     633             return (T)min((Collection) coll);
     634
     635         Iterator<? extends T> i = coll.iterator();
     636         T candidate = i.next();
     637
     638         while (i.hasNext()) {
     639             T next = i.next();
     640             if (comp.compare(next, candidate) < 0)
     641                 candidate = next;
     642         }
     643         return candidate;
     644     }
     645
     646     /**
     647      * Returns the maximum element of the given collection, according to the
     648      * <i>natural ordering</i> of its elements.  All elements in the
     649      * collection must implement the {@code Comparable} interface.
     650      * Furthermore, all elements in the collection must be <i>mutually
     651      * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
     652      * {@code ClassCastException} for any elements {@code e1} and
     653      * {@code e2} in the collection).<p>
     654      *
     655      * This method iterates over the entire collection, hence it requires
     656      * time proportional to the size of the collection.
     657      *
     658      * @param  <T> the class of the objects in the collection
     659      * @param  coll the collection whose maximum element is to be determined.
     660      * @return the maximum element of the given collection, according
     661      *         to the <i>natural ordering</i> of its elements.
     662      * @throws ClassCastException if the collection contains elements that are
     663      *         not <i>mutually comparable</i> (for example, strings and
     664      *         integers).
     665      * @throws NoSuchElementException if the collection is empty.
     666      * @see Comparable
     667      */
     668     public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
     669         Iterator<? extends T> i = coll.iterator();
     670         T candidate = i.next();
     671
     672         while (i.hasNext()) {
     673             T next = i.next();
     674             if (next.compareTo(candidate) > 0)
     675                 candidate = next;
     676         }
     677         return candidate;
     678     }
     679
     680     /**
     681      * Returns the maximum element of the given collection, according to the
     682      * order induced by the specified comparator.  All elements in the
     683      * collection must be <i>mutually comparable</i> by the specified
     684      * comparator (that is, {@code comp.compare(e1, e2)} must not throw a
     685      * {@code ClassCastException} for any elements {@code e1} and
     686      * {@code e2} in the collection).<p>
     687      *
     688      * This method iterates over the entire collection, hence it requires
     689      * time proportional to the size of the collection.
     690      *
     691      * @param  <T> the class of the objects in the collection
     692      * @param  coll the collection whose maximum element is to be determined.
     693      * @param  comp the comparator with which to determine the maximum element.
     694      *         A {@code null} value indicates that the elements' <i>natural
     695      *        ordering</i> should be used.
     696      * @return the maximum element of the given collection, according
     697      *         to the specified comparator.
     698      * @throws ClassCastException if the collection contains elements that are
     699      *         not <i>mutually comparable</i> using the specified comparator.
     700      * @throws NoSuchElementException if the collection is empty.
     701      * @see Comparable
     702      */
     703     @SuppressWarnings({"unchecked", "rawtypes"})
     704     public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
     705         if (comp==null)
     706             return (T)max((Collection) coll);
     707
     708         Iterator<? extends T> i = coll.iterator();
     709         T candidate = i.next();
     710
     711         while (i.hasNext()) {
     712             T next = i.next();
     713             if (comp.compare(next, candidate) > 0)
     714                 candidate = next;
     715         }
     716         return candidate;
     717     }
     718
     719     /**
     720      * Rotates the elements in the specified list by the specified distance.
     721      * After calling this method, the element at index {@code i} will be
     722      * the element previously at index {@code (i - distance)} mod
     723      * {@code list.size()}, for all values of {@code i} between {@code 0}
     724      * and {@code list.size()-1}, inclusive.  (This method has no effect on
     725      * the size of the list.)
     726      *
     727      * <p>For example, suppose {@code list} comprises{@code  [t, a, n, k, s]}.
     728      * After invoking {@code Collections.rotate(list, 1)} (or
     729      * {@code Collections.rotate(list, -4)}), {@code list} will comprise
     730      * {@code [s, t, a, n, k]}.
     731      *
     732      * <p>Note that this method can usefully be applied to sublists to
     733      * move one or more elements within a list while preserving the
     734      * order of the remaining elements.  For example, the following idiom
     735      * moves the element at index {@code j} forward to position
     736      * {@code k} (which must be greater than or equal to {@code j}):
     737      * <pre>
     738      *     Collections.rotate(list.subList(j, k+1), -1);
     739      * </pre>
     740      * To make this concrete, suppose {@code list} comprises
     741      * {@code [a, b, c, d, e]}.  To move the element at index {@code 1}
     742      * ({@code b}) forward two positions, perform the following invocation:
     743      * <pre>
     744      *     Collections.rotate(l.subList(1, 4), -1);
     745      * </pre>
     746      * The resulting list is {@code [a, c, d, b, e]}.
     747      *
     748      * <p>To move more than one element forward, increase the absolute value
     749      * of the rotation distance.  To move elements backward, use a positive
     750      * shift distance.
     751      *
     752      * <p>If the specified list is small or implements the {@link
     753      * RandomAccess} interface, this implementation exchanges the first
     754      * element into the location it should go, and then repeatedly exchanges
     755      * the displaced element into the location it should go until a displaced
     756      * element is swapped into the first element.  If necessary, the process
     757      * is repeated on the second and successive elements, until the rotation
     758      * is complete.  If the specified list is large and doesn't implement the
     759      * {@code RandomAccess} interface, this implementation breaks the
     760      * list into two sublist views around index {@code -distance mod size}.
     761      * Then the {@link #reverse(List)} method is invoked on each sublist view,
     762      * and finally it is invoked on the entire list.  For a more complete
     763      * description of both algorithms, see Section 2.3 of Jon Bentley's
     764      * <i>Programming Pearls</i> (Addison-Wesley, 1986).
     765      *
     766      * @param list the list to be rotated.
     767      * @param distance the distance to rotate the list.  There are no
     768      *        constraints on this value; it may be zero, negative, or
     769      *        greater than {@code list.size()}.
     770      * @throws UnsupportedOperationException if the specified list or
     771      *         its list-iterator does not support the {@code set} operation.
     772      * @since 1.4
     773      */
     774     public static void rotate(List<?> list, int distance) {
     775         if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
     776             rotate1(list, distance);
     777         else
     778             rotate2(list, distance);
     779     }
     780
     781     private static <T> void rotate1(List<T> list, int distance) {
     782         int size = list.size();
     783         if (size == 0)
     784             return;
     785         distance = distance % size;
     786         if (distance < 0)
     787             distance += size;
     788         if (distance == 0)
     789             return;
     790
     791         for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
     792             T displaced = list.get(cycleStart);
     793             int i = cycleStart;
     794             do {
     795                 i += distance;
     796                 if (i >= size)
     797                     i -= size;
     798                 displaced = list.set(i, displaced);
     799                 nMoved ++;
     800             } while (i != cycleStart);
     801         }
     802     }
     803
     804     private static void rotate2(List<?> list, int distance) {
     805         int size = list.size();
     806         if (size == 0)
     807             return;
     808         int mid =  -distance % size;
     809         if (mid < 0)
     810             mid += size;
     811         if (mid == 0)
     812             return;
     813
     814         reverse(list.subList(0, mid));
     815         reverse(list.subList(mid, size));
     816         reverse(list);
     817     }
     818
     819     /**
     820      * Replaces all occurrences of one specified value in a list with another.
     821      * More formally, replaces with {@code newVal} each element {@code e}
     822      * in {@code list} such that
     823      * {@code (oldVal==null ? e==null : oldVal.equals(e))}.
     824      * (This method has no effect on the size of the list.)
     825      *
     826      * @param  <T> the class of the objects in the list
     827      * @param list the list in which replacement is to occur.
     828      * @param oldVal the old value to be replaced.
     829      * @param newVal the new value with which {@code oldVal} is to be
     830      *        replaced.
     831      * @return {@code true} if {@code list} contained one or more elements
     832      *         {@code e} such that
     833      *         {@code (oldVal==null ?  e==null : oldVal.equals(e))}.
     834      * @throws UnsupportedOperationException if the specified list or
     835      *         its list-iterator does not support the {@code set} operation.
     836      * @since  1.4
     837      */
     838     public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
     839         boolean result = false;
     840         int size = list.size();
     841         if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
     842             if (oldVal==null) {
     843                 for (int i=0; i<size; i++) {
     844                     if (list.get(i)==null) {
     845                         list.set(i, newVal);
     846                         result = true;
     847                     }
     848                 }
     849             } else {
     850                 for (int i=0; i<size; i++) {
     851                     if (oldVal.equals(list.get(i))) {
     852                         list.set(i, newVal);
     853                         result = true;
     854                     }
     855                 }
     856             }
     857         } else {
     858             ListIterator<T> itr=list.listIterator();
     859             if (oldVal==null) {
     860                 for (int i=0; i<size; i++) {
     861                     if (itr.next()==null) {
     862                         itr.set(newVal);
     863                         result = true;
     864                     }
     865                 }
     866             } else {
     867                 for (int i=0; i<size; i++) {
     868                     if (oldVal.equals(itr.next())) {
     869                         itr.set(newVal);
     870                         result = true;
     871                     }
     872                 }
     873             }
     874         }
     875         return result;
     876     }
     877
     878     /**
     879      * Returns the starting position of the first occurrence of the specified
     880      * target list within the specified source list, or -1 if there is no
     881      * such occurrence.  More formally, returns the lowest index {@code i}
     882      * such that {@code source.subList(i, i+target.size()).equals(target)},
     883      * or -1 if there is no such index.  (Returns -1 if
     884      * {@code target.size() > source.size()})
     885      *
     886      * <p>This implementation uses the "brute force" technique of scanning
     887      * over the source list, looking for a match with the target at each
     888      * location in turn.
     889      *
     890      * @param source the list in which to search for the first occurrence
     891      *        of {@code target}.
     892      * @param target the list to search for as a subList of {@code source}.
     893      * @return the starting position of the first occurrence of the specified
     894      *         target list within the specified source list, or -1 if there
     895      *         is no such occurrence.
     896      * @since  1.4
     897      */
     898     public static int indexOfSubList(List<?> source, List<?> target) {
     899         int sourceSize = source.size();
     900         int targetSize = target.size();
     901         int maxCandidate = sourceSize - targetSize;
     902
     903         if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
     904             (source instanceof RandomAccess&&target instanceof RandomAccess)) {
     905         nextCand:
     906             for (int candidate = 0; candidate <= maxCandidate; candidate++) {
     907                 for (int i=0, j=candidate; i<targetSize; i++, j++)
     908                     if (!eq(target.get(i), source.get(j)))
     909                         continue nextCand;  // Element mismatch, try next cand
     910                 return candidate;  // All elements of candidate matched target
     911             }
     912         } else {  // Iterator version of above algorithm
     913             ListIterator<?> si = source.listIterator();
     914         nextCand:
     915             for (int candidate = 0; candidate <= maxCandidate; candidate++) {
     916                 ListIterator<?> ti = target.listIterator();
     917                 for (int i=0; i<targetSize; i++) {
     918                     if (!eq(ti.next(), si.next())) {
     919                         // Back up source iterator to next candidate
     920                         for (int j=0; j<i; j++)
     921                             si.previous();
     922                         continue nextCand;
     923                     }
     924                 }
     925                 return candidate;
     926             }
     927         }
     928         return -1;  // No candidate matched the target
     929     }
     930
     931     /**
     932      * Returns the starting position of the last occurrence of the specified
     933      * target list within the specified source list, or -1 if there is no such
     934      * occurrence.  More formally, returns the highest index {@code i}
     935      * such that {@code source.subList(i, i+target.size()).equals(target)},
     936      * or -1 if there is no such index.  (Returns -1 if
     937      * {@code target.size() > source.size()})
     938      *
     939      * <p>This implementation uses the "brute force" technique of iterating
     940      * over the source list, looking for a match with the target at each
     941      * location in turn.
     942      *
     943      * @param source the list in which to search for the last occurrence
     944      *        of {@code target}.
     945      * @param target the list to search for as a subList of {@code source}.
     946      * @return the starting position of the last occurrence of the specified
     947      *         target list within the specified source list, or -1 if there
     948      *         is no such occurrence.
     949      * @since  1.4
     950      */
     951     public static int lastIndexOfSubList(List<?> source, List<?> target) {
     952         int sourceSize = source.size();
     953         int targetSize = target.size();
     954         int maxCandidate = sourceSize - targetSize;
     955
     956         if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
     957             source instanceof RandomAccess) {   // Index access version
     958         nextCand:
     959             for (int candidate = maxCandidate; candidate >= 0; candidate--) {
     960                 for (int i=0, j=candidate; i<targetSize; i++, j++)
     961                     if (!eq(target.get(i), source.get(j)))
     962                         continue nextCand;  // Element mismatch, try next cand
     963                 return candidate;  // All elements of candidate matched target
     964             }
     965         } else {  // Iterator version of above algorithm
     966             if (maxCandidate < 0)
     967                 return -1;
     968             ListIterator<?> si = source.listIterator(maxCandidate);
     969         nextCand:
     970             for (int candidate = maxCandidate; candidate >= 0; candidate--) {
     971                 ListIterator<?> ti = target.listIterator();
     972                 for (int i=0; i<targetSize; i++) {
     973                     if (!eq(ti.next(), si.next())) {
     974                         if (candidate != 0) {
     975                             // Back up source iterator to next candidate
     976                             for (int j=0; j<=i+1; j++)
     977                                 si.previous();
     978                         }
     979                         continue nextCand;
     980                     }
     981                 }
     982                 return candidate;
     983             }
     984         }
     985         return -1;  // No candidate matched the target
     986     }
     987
     988
     989     // Unmodifiable Wrappers
     990
     991     /**
     992      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
     993      * specified collection. Query operations on the returned collection "read through"

     994      * to the specified collection, and attempts to modify the returned
     995      * collection, whether direct or via its iterator, result in an
     996      * {@code UnsupportedOperationException}.<p>
     997      *
     998      * The returned collection does <i>not</i> pass the hashCode and equals
     999      * operations through to the backing collection, but relies on
    1000      * {@code Object}'s {@code equals} and {@code hashCode} methods.  This
    1001      * is necessary to preserve the contracts of these operations in the case
    1002      * that the backing collection is a set or a list.<p>
    1003      *
    1004      * The returned collection will be serializable if the specified collection
    1005      * is serializable.
    1006      *
    1007      * @param  <T> the class of the objects in the collection
    1008      * @param  c the collection for which an unmodifiable view is to be
    1009      *         returned.
    1010      * @return an unmodifiable view of the specified collection.
    1011      */
    1012     public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
    1013         return new UnmodifiableCollection<>(c);
    1014     }
    1015
    1016     /**
    1017      * @serial include
    1018      */
    1019     static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
    1020         private static final long serialVersionUID = 1820017752578914078L;
    1021
    1022         final Collection<? extends E> c;
    1023
    1024         UnmodifiableCollection(Collection<? extends E> c) {
    1025             if (c==null)
    1026                 throw new NullPointerException();
    1027             this.c = c;
    1028         }
    1029
    1030         public int size()                   {return c.size();}
    1031         public boolean isEmpty()            {return c.isEmpty();}
    1032         public boolean contains(Object o)   {return c.contains(o);}
    1033         public Object[] toArray()           {return c.toArray();}
    1034         public <T> T[] toArray(T[] a)       {return c.toArray(a);}
    1035         public String toString()            {return c.toString();}
    1036
    1037         public Iterator<E> iterator() {
    1038             return new Iterator<E>() {
    1039                 private final Iterator<? extends E> i = c.iterator();
    1040
    1041                 public boolean hasNext() {return i.hasNext();}
    1042                 public E next()          {return i.next();}
    1043                 public void remove() {
    1044                     throw new UnsupportedOperationException();
    1045                 }
    1046                 @Override
    1047                 public void forEachRemaining(Consumer<? super E> action) {
    1048                     // Use backing collection version
    1049                     i.forEachRemaining(action);
    1050                 }
    1051             };
    1052         }
    1053
    1054         public boolean add(E e) {
    1055             throw new UnsupportedOperationException();
    1056         }
    1057         public boolean remove(Object o) {
    1058             throw new UnsupportedOperationException();
    1059         }
    1060
    1061         public boolean containsAll(Collection<?> coll) {
    1062             return c.containsAll(coll);
    1063         }
    1064         public boolean addAll(Collection<? extends E> coll) {
    1065             throw new UnsupportedOperationException();
    1066         }
    1067         public boolean removeAll(Collection<?> coll) {
    1068             throw new UnsupportedOperationException();
    1069         }
    1070         public boolean retainAll(Collection<?> coll) {
    1071             throw new UnsupportedOperationException();
    1072         }
    1073         public void clear() {
    1074             throw new UnsupportedOperationException();
    1075         }
    1076
    1077         // Override default methods in Collection
    1078         @Override
    1079         public void forEach(Consumer<? super E> action) {
    1080             c.forEach(action);
    1081         }
    1082         @Override
    1083         public boolean removeIf(Predicate<? super E> filter) {
    1084             throw new UnsupportedOperationException();
    1085         }
    1086         @SuppressWarnings("unchecked")
    1087         @Override
    1088         public Spliterator<E> spliterator() {
    1089             return (Spliterator<E>)c.spliterator();
    1090         }
    1091         @SuppressWarnings("unchecked")
    1092         @Override
    1093         public Stream<E> stream() {
    1094             return (Stream<E>)c.stream();
    1095         }
    1096         @SuppressWarnings("unchecked")
    1097         @Override
    1098         public Stream<E> parallelStream() {
    1099             return (Stream<E>)c.parallelStream();
    1100         }
    1101     }
    1102
    1103     /**
    1104      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1105      * specified set. Query operations on the returned set "read through" to the specified

    1106      * set, and attempts to modify the returned set, whether direct or via its
    1107      * iterator, result in an {@code UnsupportedOperationException}.<p>
    1108      *
    1109      * The returned set will be serializable if the specified set
    1110      * is serializable.
    1111      *
    1112      * @param  <T> the class of the objects in the set
    1113      * @param  s the set for which an unmodifiable view is to be returned.
    1114      * @return an unmodifiable view of the specified set.
    1115      */
    1116     public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
    1117         return new UnmodifiableSet<>(s);
    1118     }
    1119
    1120     /**
    1121      * @serial include
    1122      */
    1123     static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
    1124                                  implements Set<E>, Serializable {
    1125         private static final long serialVersionUID = -9215047833775013803L;
    1126
    1127         UnmodifiableSet(Set<? extends E> s)     {super(s);}
    1128         public boolean equals(Object o) {return o == this || c.equals(o);}
    1129         public int hashCode()           {return c.hashCode();}
    1130     }
    1131
    1132     /**
    1133      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1134      * specified sorted set. Query operations on the returned sorted set "read

    1135      * through" to the specified sorted set.  Attempts to modify the returned
    1136      * sorted set, whether direct, via its iterator, or via its
    1137      * {@code subSet}, {@code headSet}, or {@code tailSet} views, result in
    1138      * an {@code UnsupportedOperationException}.<p>
    1139      *
    1140      * The returned sorted set will be serializable if the specified sorted set
    1141      * is serializable.
    1142      *
    1143      * @param  <T> the class of the objects in the set
    1144      * @param s the sorted set for which an unmodifiable view is to be
    1145      *        returned.
    1146      * @return an unmodifiable view of the specified sorted set.
    1147      */
    1148     public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
    1149         return new UnmodifiableSortedSet<>(s);
    1150     }
    1151
    1152     /**
    1153      * @serial include
    1154      */
    1155     static class UnmodifiableSortedSet<E>
    1156                              extends UnmodifiableSet<E>
    1157                              implements SortedSet<E>, Serializable {
    1158         private static final long serialVersionUID = -4929149591599911165L;
    1159         private final SortedSet<E> ss;
    1160
    1161         UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
    1162
    1163         public Comparator<? super E> comparator() {return ss.comparator();}
    1164
    1165         public SortedSet<E> subSet(E fromElement, E toElement) {
    1166             return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement));
    1167         }
    1168         public SortedSet<E> headSet(E toElement) {
    1169             return new UnmodifiableSortedSet<>(ss.headSet(toElement));
    1170         }
    1171         public SortedSet<E> tailSet(E fromElement) {
    1172             return new UnmodifiableSortedSet<>(ss.tailSet(fromElement));
    1173         }
    1174
    1175         public E first()                   {return ss.first();}
    1176         public E last()                    {return ss.last();}
    1177     }
    1178
    1179     /**
    1180      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1181      * specified navigable set. Query operations on the returned navigable set "read

    1182      * through" to the specified navigable set.  Attempts to modify the returned
    1183      * navigable set, whether direct, via its iterator, or via its
    1184      * {@code subSet}, {@code headSet}, or {@code tailSet} views, result in
    1185      * an {@code UnsupportedOperationException}.<p>
    1186      *
    1187      * The returned navigable set will be serializable if the specified
    1188      * navigable set is serializable.
    1189      *
    1190      * @param  <T> the class of the objects in the set
    1191      * @param s the navigable set for which an unmodifiable view is to be
    1192      *        returned
    1193      * @return an unmodifiable view of the specified navigable set
    1194      * @since 1.8
    1195      */
    1196     public static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s) {
    1197         return new UnmodifiableNavigableSet<>(s);
    1198     }
    1199
    1200     /**
    1201      * Wraps a navigable set and disables all of the mutative operations.
    1202      *
    1203      * @param <E> type of elements
    1204      * @serial include
    1205      */
    1206     static class UnmodifiableNavigableSet<E>
    1207                              extends UnmodifiableSortedSet<E>
    1208                              implements NavigableSet<E>, Serializable {
    1209
    1210         private static final long serialVersionUID = -6027448201786391929L;
    1211
    1212         /**
    1213          * A singleton empty unmodifiable navigable set used for
    1214          * {@link #emptyNavigableSet()}.
    1215          *
    1216          * @param <E> type of elements, if there were any, and bounds
    1217          */
    1218         private static class EmptyNavigableSet<E> extends UnmodifiableNavigableSet<E>
    1219             implements Serializable {
    1220             private static final long serialVersionUID = -6291252904449939134L;
    1221
    1222             public EmptyNavigableSet() {
    1223                 super(new TreeSet<>());
    1224             }
    1225
    1226             private Object readResolve()        { return EMPTY_NAVIGABLE_SET; }
    1227         }
    1228
    1229         @SuppressWarnings("rawtypes")
    1230         private static final NavigableSet<?> EMPTY_NAVIGABLE_SET =
    1231                 new EmptyNavigableSet<>();
    1232
    1233         /**
    1234          * The instance we are protecting.
    1235          */
    1236         private final NavigableSet<E> ns;
    1237
    1238         UnmodifiableNavigableSet(NavigableSet<E> s)         {super(s); ns = s;}
    1239
    1240         public E lower(E e)                             { return ns.lower(e); }
    1241         public E floor(E e)                             { return ns.floor(e); }
    1242         public E ceiling(E e)                         { return ns.ceiling(e); }
    1243         public E higher(E e)                           { return ns.higher(e); }
    1244         public E pollFirst()     { throw new UnsupportedOperationException(); }
    1245         public E pollLast()      { throw new UnsupportedOperationException(); }
    1246         public NavigableSet<E> descendingSet()
    1247                  { return new UnmodifiableNavigableSet<>(ns.descendingSet()); }
    1248         public Iterator<E> descendingIterator()
    1249                                          { return descendingSet().iterator(); }
    1250
    1251         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
    1252             return new UnmodifiableNavigableSet<>(
    1253                 ns.subSet(fromElement, fromInclusive, toElement, toInclusive));
    1254         }
    1255
    1256         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    1257             return new UnmodifiableNavigableSet<>(
    1258                 ns.headSet(toElement, inclusive));
    1259         }
    1260
    1261         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    1262             return new UnmodifiableNavigableSet<>(
    1263                 ns.tailSet(fromElement, inclusive));
    1264         }
    1265     }
    1266
    1267     /**
    1268      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1269      * specified list. Query operations on the returned list "read through" to the

    1270      * specified list, and attempts to modify the returned list, whether
    1271      * direct or via its iterator, result in an
    1272      * {@code UnsupportedOperationException}.<p>
    1273      *
    1274      * The returned list will be serializable if the specified list
    1275      * is serializable. Similarly, the returned list will implement
    1276      * {@link RandomAccess} if the specified list does.
    1277      *
    1278      * @param  <T> the class of the objects in the list
    1279      * @param  list the list for which an unmodifiable view is to be returned.
    1280      * @return an unmodifiable view of the specified list.
    1281      */
    1282     public static <T> List<T> unmodifiableList(List<? extends T> list) {
    1283         return (list instanceof RandomAccess ?
    1284                 new UnmodifiableRandomAccessList<>(list) :
    1285                 new UnmodifiableList<>(list));
    1286     }
    1287
    1288     /**
    1289      * @serial include
    1290      */
    1291     static class UnmodifiableList<E> extends UnmodifiableCollection<E>
    1292                                   implements List<E> {
    1293         private static final long serialVersionUID = -283967356065247728L;
    1294
    1295         final List<? extends E> list;
    1296
    1297         UnmodifiableList(List<? extends E> list) {
    1298             super(list);
    1299             this.list = list;
    1300         }
    1301
    1302         public boolean equals(Object o) {return o == this || list.equals(o);}
    1303         public int hashCode()           {return list.hashCode();}
    1304
    1305         public E get(int index) {return list.get(index);}
    1306         public E set(int index, E element) {
    1307             throw new UnsupportedOperationException();
    1308         }
    1309         public void add(int index, E element) {
    1310             throw new UnsupportedOperationException();
    1311         }
    1312         public E remove(int index) {
    1313             throw new UnsupportedOperationException();
    1314         }
    1315         public int indexOf(Object o)            {return list.indexOf(o);}
    1316         public int lastIndexOf(Object o)        {return list.lastIndexOf(o);}
    1317         public boolean addAll(int index, Collection<? extends E> c) {
    1318             throw new UnsupportedOperationException();
    1319         }
    1320
    1321         @Override
    1322         public void replaceAll(UnaryOperator<E> operator) {
    1323             throw new UnsupportedOperationException();
    1324         }
    1325         @Override
    1326         public void sort(Comparator<? super E> c) {
    1327             throw new UnsupportedOperationException();
    1328         }
    1329
    1330         public ListIterator<E> listIterator()   {return listIterator(0);}
    1331
    1332         public ListIterator<E> listIterator(final int index) {
    1333             return new ListIterator<E>() {
    1334                 private final ListIterator<? extends E> i
    1335                     = list.listIterator(index);
    1336
    1337                 public boolean hasNext()     {return i.hasNext();}
    1338                 public E next()              {return i.next();}
    1339                 public boolean hasPrevious() {return i.hasPrevious();}
    1340                 public E previous()          {return i.previous();}
    1341                 public int nextIndex()       {return i.nextIndex();}
    1342                 public int previousIndex()   {return i.previousIndex();}
    1343
    1344                 public void remove() {
    1345                     throw new UnsupportedOperationException();
    1346                 }
    1347                 public void set(E e) {
    1348                     throw new UnsupportedOperationException();
    1349                 }
    1350                 public void add(E e) {
    1351                     throw new UnsupportedOperationException();
    1352                 }
    1353
    1354                 @Override
    1355                 public void forEachRemaining(Consumer<? super E> action) {
    1356                     i.forEachRemaining(action);
    1357                 }
    1358             };
    1359         }
    1360
    1361         public List<E> subList(int fromIndex, int toIndex) {
    1362             return new UnmodifiableList<>(list.subList(fromIndex, toIndex));
    1363         }
    1364
    1365         /**
    1366          * UnmodifiableRandomAccessList instances are serialized as
    1367          * UnmodifiableList instances to allow them to be deserialized
    1368          * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
    1369          * This method inverts the transformation.  As a beneficial
    1370          * side-effect, it also grafts the RandomAccess marker onto
    1371          * UnmodifiableList instances that were serialized in pre-1.4 JREs.
    1372          *
    1373          * Note: Unfortunately, UnmodifiableRandomAccessList instances
    1374          * serialized in 1.4.1 and deserialized in 1.4 will become
    1375          * UnmodifiableList instances, as this method was missing in 1.4.
    1376          */
    1377         private Object readResolve() {
    1378             return (list instanceof RandomAccess
    1379                     ? new UnmodifiableRandomAccessList<>(list)
    1380                     : this);
    1381         }
    1382     }
    1383
    1384     /**
    1385      * @serial include
    1386      */
    1387     static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E>
    1388                                               implements RandomAccess
    1389     {
    1390         UnmodifiableRandomAccessList(List<? extends E> list) {
    1391             super(list);
    1392         }
    1393
    1394         public List<E> subList(int fromIndex, int toIndex) {
    1395             return new UnmodifiableRandomAccessList<>(
    1396                 list.subList(fromIndex, toIndex));
    1397         }
    1398
    1399         private static final long serialVersionUID = -2542308836966382001L;
    1400
    1401         /**
    1402          * Allows instances to be deserialized in pre-1.4 JREs (which do
    1403          * not have UnmodifiableRandomAccessList).  UnmodifiableList has
    1404          * a readResolve method that inverts this transformation upon
    1405          * deserialization.
    1406          */
    1407         private Object writeReplace() {
    1408             return new UnmodifiableList<>(list);
    1409         }
    1410     }
    1411
    1412     /**
    1413      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1414      * specified map. Query operations on the returned map "read through"

    1415      * to the specified map, and attempts to modify the returned
    1416      * map, whether direct or via its collection views, result in an
    1417      * {@code UnsupportedOperationException}.<p>
    1418      *
    1419      * The returned map will be serializable if the specified map
    1420      * is serializable.
    1421      *
    1422      * @param <K> the class of the map keys
    1423      * @param <V> the class of the map values
    1424      * @param  m the map for which an unmodifiable view is to be returned.
    1425      * @return an unmodifiable view of the specified map.
    1426      */
    1427     public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
    1428         return new UnmodifiableMap<>(m);
    1429     }
    1430
    1431     /**
    1432      * @serial include
    1433      */
    1434     private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
    1435         private static final long serialVersionUID = -1034234728574286014L;
    1436
    1437         private final Map<? extends K, ? extends V> m;
    1438
    1439         UnmodifiableMap(Map<? extends K, ? extends V> m) {
    1440             if (m==null)
    1441                 throw new NullPointerException();
    1442             this.m = m;
    1443         }
    1444
    1445         public int size()                        {return m.size();}
    1446         public boolean isEmpty()                 {return m.isEmpty();}
    1447         public boolean containsKey(Object key)   {return m.containsKey(key);}
    1448         public boolean containsValue(Object val) {return m.containsValue(val);}
    1449         public V get(Object key)                 {return m.get(key);}
    1450
    1451         public V put(K key, V value) {
    1452             throw new UnsupportedOperationException();
    1453         }
    1454         public V remove(Object key) {
    1455             throw new UnsupportedOperationException();
    1456         }
    1457         public void putAll(Map<? extends K, ? extends V> m) {
    1458             throw new UnsupportedOperationException();
    1459         }
    1460         public void clear() {
    1461             throw new UnsupportedOperationException();
    1462         }
    1463
    1464         private transient Set<K> keySet;
    1465         private transient Set<Map.Entry<K,V>> entrySet;
    1466         private transient Collection<V> values;
    1467
    1468         public Set<K> keySet() {
    1469             if (keySet==null)
    1470                 keySet = unmodifiableSet(m.keySet());
    1471             return keySet;
    1472         }
    1473
    1474         public Set<Map.Entry<K,V>> entrySet() {
    1475             if (entrySet==null)
    1476                 entrySet = new UnmodifiableEntrySet<>(m.entrySet());
    1477             return entrySet;
    1478         }
    1479
    1480         public Collection<V> values() {
    1481             if (values==null)
    1482                 values = unmodifiableCollection(m.values());
    1483             return values;
    1484         }
    1485
    1486         public boolean equals(Object o) {return o == this || m.equals(o);}
    1487         public int hashCode()           {return m.hashCode();}
    1488         public String toString()        {return m.toString();}
    1489
    1490         // Override default methods in Map
    1491         @Override
    1492         @SuppressWarnings("unchecked")
    1493         public V getOrDefault(Object k, V defaultValue) {
    1494             // Safe cast as we don't change the value
    1495             return ((Map<K, V>)m).getOrDefault(k, defaultValue);
    1496         }
    1497
    1498         @Override
    1499         public void forEach(BiConsumer<? super K, ? super V> action) {
    1500             m.forEach(action);
    1501         }
    1502
    1503         @Override
    1504         public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    1505             throw new UnsupportedOperationException();
    1506         }
    1507
    1508         @Override
    1509         public V putIfAbsent(K key, V value) {
    1510             throw new UnsupportedOperationException();
    1511         }
    1512
    1513         @Override
    1514         public boolean remove(Object key, Object value) {
    1515             throw new UnsupportedOperationException();
    1516         }
    1517
    1518         @Override
    1519         public boolean replace(K key, V oldValue, V newValue) {
    1520             throw new UnsupportedOperationException();
    1521         }
    1522
    1523         @Override
    1524         public V replace(K key, V value) {
    1525             throw new UnsupportedOperationException();
    1526         }
    1527
    1528         @Override
    1529         public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    1530             throw new UnsupportedOperationException();
    1531         }
    1532
    1533         @Override
    1534         public V computeIfPresent(K key,
    1535                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    1536             throw new UnsupportedOperationException();
    1537         }
    1538
    1539         @Override
    1540         public V compute(K key,
    1541                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    1542             throw new UnsupportedOperationException();
    1543         }
    1544
    1545         @Override
    1546         public V merge(K key, V value,
    1547                 BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    1548             throw new UnsupportedOperationException();
    1549         }
    1550
    1551         /**
    1552          * We need this class in addition to UnmodifiableSet as
    1553          * Map.Entries themselves permit modification of the backing Map
    1554          * via their setValue operation.  This class is subtle: there are
    1555          * many possible attacks that must be thwarted.
    1556          *
    1557          * @serial include
    1558          */
    1559         static class UnmodifiableEntrySet<K,V>
    1560             extends UnmodifiableSet<Map.Entry<K,V>> {
    1561             private static final long serialVersionUID = 7854390611657943733L;
    1562
    1563             @SuppressWarnings({"unchecked", "rawtypes"})
    1564             UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
    1565                 // Need to cast to raw in order to work around a limitation in the type system
    1566                 super((Set)s);
    1567             }
    1568
    1569             static <K, V> Consumer<Map.Entry<K, V>> entryConsumer(Consumer<? super Entry<K, V>> action) {
    1570                 return e -> action.accept(new UnmodifiableEntry<>(e));
    1571             }
    1572
    1573             public void forEach(Consumer<? super Entry<K, V>> action) {
    1574                 Objects.requireNonNull(action);
    1575                 c.forEach(entryConsumer(action));
    1576             }
    1577
    1578             static final class UnmodifiableEntrySetSpliterator<K, V>
    1579                     implements Spliterator<Entry<K,V>> {
    1580                 final Spliterator<Map.Entry<K, V>> s;
    1581
    1582                 UnmodifiableEntrySetSpliterator(Spliterator<Entry<K, V>> s) {
    1583                     this.s = s;
    1584                 }
    1585
    1586                 @Override
    1587                 public boolean tryAdvance(Consumer<? super Entry<K, V>> action) {
    1588                     Objects.requireNonNull(action);
    1589                     return s.tryAdvance(entryConsumer(action));
    1590                 }
    1591
    1592                 @Override
    1593                 public void forEachRemaining(Consumer<? super Entry<K, V>> action) {
    1594                     Objects.requireNonNull(action);
    1595                     s.forEachRemaining(entryConsumer(action));
    1596                 }
    1597
    1598                 @Override
    1599                 public Spliterator<Entry<K, V>> trySplit() {
    1600                     Spliterator<Entry<K, V>> split = s.trySplit();
    1601                     return split == null
    1602                            ? null
    1603                            : new UnmodifiableEntrySetSpliterator<>(split);
    1604                 }
    1605
    1606                 @Override
    1607                 public long estimateSize() {
    1608                     return s.estimateSize();
    1609                 }
    1610
    1611                 @Override
    1612                 public long getExactSizeIfKnown() {
    1613                     return s.getExactSizeIfKnown();
    1614                 }
    1615
    1616                 @Override
    1617                 public int characteristics() {
    1618                     return s.characteristics();
    1619                 }
    1620
    1621                 @Override
    1622                 public boolean hasCharacteristics(int characteristics) {
    1623                     return s.hasCharacteristics(characteristics);
    1624                 }
    1625
    1626                 @Override
    1627                 public Comparator<? super Entry<K, V>> getComparator() {
    1628                     return s.getComparator();
    1629                 }
    1630             }
    1631
    1632             @SuppressWarnings("unchecked")
    1633             public Spliterator<Entry<K,V>> spliterator() {
    1634                 return new UnmodifiableEntrySetSpliterator<>(
    1635                         (Spliterator<Map.Entry<K, V>>) c.spliterator());
    1636             }
    1637
    1638             @Override
    1639             public Stream<Entry<K,V>> stream() {
    1640                 return StreamSupport.stream(spliterator(), false);
    1641             }
    1642
    1643             @Override
    1644             public Stream<Entry<K,V>> parallelStream() {
    1645                 return StreamSupport.stream(spliterator(), true);
    1646             }
    1647
    1648             public Iterator<Map.Entry<K,V>> iterator() {
    1649                 return new Iterator<Map.Entry<K,V>>() {
    1650                     private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
    1651
    1652                     public boolean hasNext() {
    1653                         return i.hasNext();
    1654                     }
    1655                     public Map.Entry<K,V> next() {
    1656                         return new UnmodifiableEntry<>(i.next());
    1657                     }
    1658                     public void remove() {
    1659                         throw new UnsupportedOperationException();
    1660                     }
    1661                 };
    1662             }
    1663
    1664             @SuppressWarnings("unchecked")
    1665             public Object[] toArray() {
    1666                 Object[] a = c.toArray();
    1667                 for (int i=0; i<a.length; i++)
    1668                     a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]);
    1669                 return a;
    1670             }
    1671
    1672             @SuppressWarnings("unchecked")
    1673             public <T> T[] toArray(T[] a) {
    1674                 // We don't pass a to c.toArray, to avoid window of
    1675                 // vulnerability wherein an unscrupulous multithreaded client
    1676                 // could get his hands on raw (unwrapped) Entries from c.
    1677                 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
    1678
    1679                 for (int i=0; i<arr.length; i++)
    1680                     arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]);
    1681
    1682                 if (arr.length > a.length)
    1683                     return (T[])arr;
    1684
    1685                 System.arraycopy(arr, 0, a, 0, arr.length);
    1686                 if (a.length > arr.length)
    1687                     a[arr.length] = null;
    1688                 return a;
    1689             }
    1690
    1691             /**
    1692              * This method is overridden to protect the backing set against
    1693              * an object with a nefarious equals function that senses
    1694              * that the equality-candidate is Map.Entry and calls its
    1695              * setValue method.
    1696              */
    1697             public boolean contains(Object o) {
    1698                 if (!(o instanceof Map.Entry))
    1699                     return false;
    1700                 return c.contains(
    1701                     new UnmodifiableEntry<>((Map.Entry<?,?>) o));
    1702             }
    1703
    1704             /**
    1705              * The next two methods are overridden to protect against
    1706              * an unscrupulous List whose contains(Object o) method senses
    1707              * when o is a Map.Entry, and calls o.setValue.
    1708              */
    1709             public boolean containsAll(Collection<?> coll) {
    1710                 for (Object e : coll) {
    1711                     if (!contains(e)) // Invokes safe contains() above
    1712                         return false;
    1713                 }
    1714                 return true;
    1715             }
    1716             public boolean equals(Object o) {
    1717                 if (o == this)
    1718                     return true;
    1719
    1720                 if (!(o instanceof Set))
    1721                     return false;
    1722                 Set<?> s = (Set<?>) o;
    1723                 if (s.size() != c.size())
    1724                     return false;
    1725                 return containsAll(s); // Invokes safe containsAll() above
    1726             }
    1727
    1728             /**
    1729              * This "wrapper class" serves two purposes: it prevents
    1730              * the client from modifying the backing Map, by short-circuiting
    1731              * the setValue method, and it protects the backing Map against
    1732              * an ill-behaved Map.Entry that attempts to modify another
    1733              * Map Entry when asked to perform an equality check.
    1734              */
    1735             private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
    1736                 private Map.Entry<? extends K, ? extends V> e;
    1737
    1738                 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e)
    1739                         {this.e = Objects.requireNonNull(e);}
    1740
    1741                 public K getKey()        {return e.getKey();}
    1742                 public V getValue()      {return e.getValue();}
    1743                 public V setValue(V value) {
    1744                     throw new UnsupportedOperationException();
    1745                 }
    1746                 public int hashCode()    {return e.hashCode();}
    1747                 public boolean equals(Object o) {
    1748                     if (this == o)
    1749                         return true;
    1750                     if (!(o instanceof Map.Entry))
    1751                         return false;
    1752                     Map.Entry<?,?> t = (Map.Entry<?,?>)o;
    1753                     return eq(e.getKey(),   t.getKey()) &&
    1754                            eq(e.getValue(), t.getValue());
    1755                 }
    1756                 public String toString() {return e.toString();}
    1757             }
    1758         }
    1759     }
    1760
    1761     /**
    1762      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1763      * specified sorted map. Query operations on the returned sorted map "read through"

    1764      * to the specified sorted map.  Attempts to modify the returned
    1765      * sorted map, whether direct, via its collection views, or via its
    1766      * {@code subMap}, {@code headMap}, or {@code tailMap} views, result in
    1767      * an {@code UnsupportedOperationException}.<p>
    1768      *
    1769      * The returned sorted map will be serializable if the specified sorted map
    1770      * is serializable.
    1771      *
    1772      * @param <K> the class of the map keys
    1773      * @param <V> the class of the map values
    1774      * @param m the sorted map for which an unmodifiable view is to be
    1775      *        returned.
    1776      * @return an unmodifiable view of the specified sorted map.
    1777      */
    1778     public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
    1779         return new UnmodifiableSortedMap<>(m);
    1780     }
    1781
    1782     /**
    1783      * @serial include
    1784      */
    1785     static class UnmodifiableSortedMap<K,V>
    1786           extends UnmodifiableMap<K,V>
    1787           implements SortedMap<K,V>, Serializable {
    1788         private static final long serialVersionUID = -8806743815996713206L;
    1789
    1790         private final SortedMap<K, ? extends V> sm;
    1791
    1792         UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m; }
    1793         public Comparator<? super K> comparator()   { return sm.comparator(); }
    1794         public SortedMap<K,V> subMap(K fromKey, K toKey)
    1795              { return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey)); }
    1796         public SortedMap<K,V> headMap(K toKey)
    1797                      { return new UnmodifiableSortedMap<>(sm.headMap(toKey)); }
    1798         public SortedMap<K,V> tailMap(K fromKey)
    1799                    { return new UnmodifiableSortedMap<>(sm.tailMap(fromKey)); }
    1800         public K firstKey()                           { return sm.firstKey(); }
    1801         public K lastKey()                             { return sm.lastKey(); }
    1802     }
    1803
    1804     /**
    1805      * Returns an <a href="Collection.html#unmodview">unmodifiable view</a> of the
    1806      * specified navigable map. Query operations on the returned navigable map "read

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