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