1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/Collections.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,3953 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +import java.io.Serializable;
1.31 +import java.io.IOException;
1.32 +import java.lang.reflect.Array;
1.33 +
1.34 +/**
1.35 + * This class consists exclusively of static methods that operate on or return
1.36 + * collections. It contains polymorphic algorithms that operate on
1.37 + * collections, "wrappers", which return a new collection backed by a
1.38 + * specified collection, and a few other odds and ends.
1.39 + *
1.40 + * <p>The methods of this class all throw a <tt>NullPointerException</tt>
1.41 + * if the collections or class objects provided to them are null.
1.42 + *
1.43 + * <p>The documentation for the polymorphic algorithms contained in this class
1.44 + * generally includes a brief description of the <i>implementation</i>. Such
1.45 + * descriptions should be regarded as <i>implementation notes</i>, rather than
1.46 + * parts of the <i>specification</i>. Implementors should feel free to
1.47 + * substitute other algorithms, so long as the specification itself is adhered
1.48 + * to. (For example, the algorithm used by <tt>sort</tt> does not have to be
1.49 + * a mergesort, but it does have to be <i>stable</i>.)
1.50 + *
1.51 + * <p>The "destructive" algorithms contained in this class, that is, the
1.52 + * algorithms that modify the collection on which they operate, are specified
1.53 + * to throw <tt>UnsupportedOperationException</tt> if the collection does not
1.54 + * support the appropriate mutation primitive(s), such as the <tt>set</tt>
1.55 + * method. These algorithms may, but are not required to, throw this
1.56 + * exception if an invocation would have no effect on the collection. For
1.57 + * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
1.58 + * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
1.59 + *
1.60 + * <p>This class is a member of the
1.61 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.62 + * Java Collections Framework</a>.
1.63 + *
1.64 + * @author Josh Bloch
1.65 + * @author Neal Gafter
1.66 + * @see Collection
1.67 + * @see Set
1.68 + * @see List
1.69 + * @see Map
1.70 + * @since 1.2
1.71 + */
1.72 +
1.73 +public class Collections {
1.74 + // Suppresses default constructor, ensuring non-instantiability.
1.75 + private Collections() {
1.76 + }
1.77 +
1.78 + // Algorithms
1.79 +
1.80 + /*
1.81 + * Tuning parameters for algorithms - Many of the List algorithms have
1.82 + * two implementations, one of which is appropriate for RandomAccess
1.83 + * lists, the other for "sequential." Often, the random access variant
1.84 + * yields better performance on small sequential access lists. The
1.85 + * tuning parameters below determine the cutoff point for what constitutes
1.86 + * a "small" sequential access list for each algorithm. The values below
1.87 + * were empirically determined to work well for LinkedList. Hopefully
1.88 + * they should be reasonable for other sequential access List
1.89 + * implementations. Those doing performance work on this code would
1.90 + * do well to validate the values of these parameters from time to time.
1.91 + * (The first word of each tuning parameter name is the algorithm to which
1.92 + * it applies.)
1.93 + */
1.94 + private static final int BINARYSEARCH_THRESHOLD = 5000;
1.95 + private static final int REVERSE_THRESHOLD = 18;
1.96 + private static final int SHUFFLE_THRESHOLD = 5;
1.97 + private static final int FILL_THRESHOLD = 25;
1.98 + private static final int ROTATE_THRESHOLD = 100;
1.99 + private static final int COPY_THRESHOLD = 10;
1.100 + private static final int REPLACEALL_THRESHOLD = 11;
1.101 + private static final int INDEXOFSUBLIST_THRESHOLD = 35;
1.102 +
1.103 + /**
1.104 + * Sorts the specified list into ascending order, according to the
1.105 + * {@linkplain Comparable natural ordering} of its elements.
1.106 + * All elements in the list must implement the {@link Comparable}
1.107 + * interface. Furthermore, all elements in the list must be
1.108 + * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)}
1.109 + * must not throw a {@code ClassCastException} for any elements
1.110 + * {@code e1} and {@code e2} in the list).
1.111 + *
1.112 + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1.113 + * not be reordered as a result of the sort.
1.114 + *
1.115 + * <p>The specified list must be modifiable, but need not be resizable.
1.116 + *
1.117 + * <p>Implementation note: This implementation is a stable, adaptive,
1.118 + * iterative mergesort that requires far fewer than n lg(n) comparisons
1.119 + * when the input array is partially sorted, while offering the
1.120 + * performance of a traditional mergesort when the input array is
1.121 + * randomly ordered. If the input array is nearly sorted, the
1.122 + * implementation requires approximately n comparisons. Temporary
1.123 + * storage requirements vary from a small constant for nearly sorted
1.124 + * input arrays to n/2 object references for randomly ordered input
1.125 + * arrays.
1.126 + *
1.127 + * <p>The implementation takes equal advantage of ascending and
1.128 + * descending order in its input array, and can take advantage of
1.129 + * ascending and descending order in different parts of the same
1.130 + * input array. It is well-suited to merging two or more sorted arrays:
1.131 + * simply concatenate the arrays and sort the resulting array.
1.132 + *
1.133 + * <p>The implementation was adapted from Tim Peters's list sort for Python
1.134 + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1.135 + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1.136 + * Sorting and Information Theoretic Complexity", in Proceedings of the
1.137 + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1.138 + * January 1993.
1.139 + *
1.140 + * <p>This implementation dumps the specified list into an array, sorts
1.141 + * the array, and iterates over the list resetting each element
1.142 + * from the corresponding position in the array. This avoids the
1.143 + * n<sup>2</sup> log(n) performance that would result from attempting
1.144 + * to sort a linked list in place.
1.145 + *
1.146 + * @param list the list to be sorted.
1.147 + * @throws ClassCastException if the list contains elements that are not
1.148 + * <i>mutually comparable</i> (for example, strings and integers).
1.149 + * @throws UnsupportedOperationException if the specified list's
1.150 + * list-iterator does not support the {@code set} operation.
1.151 + * @throws IllegalArgumentException (optional) if the implementation
1.152 + * detects that the natural ordering of the list elements is
1.153 + * found to violate the {@link Comparable} contract
1.154 + */
1.155 + public static <T extends Comparable<? super T>> void sort(List<T> list) {
1.156 + Object[] a = list.toArray();
1.157 + Arrays.sort(a);
1.158 + ListIterator<T> i = list.listIterator();
1.159 + for (int j=0; j<a.length; j++) {
1.160 + i.next();
1.161 + i.set((T)a[j]);
1.162 + }
1.163 + }
1.164 +
1.165 + /**
1.166 + * Sorts the specified list according to the order induced by the
1.167 + * specified comparator. All elements in the list must be <i>mutually
1.168 + * comparable</i> using the specified comparator (that is,
1.169 + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
1.170 + * for any elements {@code e1} and {@code e2} in the list).
1.171 + *
1.172 + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1.173 + * not be reordered as a result of the sort.
1.174 + *
1.175 + * <p>The specified list must be modifiable, but need not be resizable.
1.176 + *
1.177 + * <p>Implementation note: This implementation is a stable, adaptive,
1.178 + * iterative mergesort that requires far fewer than n lg(n) comparisons
1.179 + * when the input array is partially sorted, while offering the
1.180 + * performance of a traditional mergesort when the input array is
1.181 + * randomly ordered. If the input array is nearly sorted, the
1.182 + * implementation requires approximately n comparisons. Temporary
1.183 + * storage requirements vary from a small constant for nearly sorted
1.184 + * input arrays to n/2 object references for randomly ordered input
1.185 + * arrays.
1.186 + *
1.187 + * <p>The implementation takes equal advantage of ascending and
1.188 + * descending order in its input array, and can take advantage of
1.189 + * ascending and descending order in different parts of the same
1.190 + * input array. It is well-suited to merging two or more sorted arrays:
1.191 + * simply concatenate the arrays and sort the resulting array.
1.192 + *
1.193 + * <p>The implementation was adapted from Tim Peters's list sort for Python
1.194 + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1.195 + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1.196 + * Sorting and Information Theoretic Complexity", in Proceedings of the
1.197 + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1.198 + * January 1993.
1.199 + *
1.200 + * <p>This implementation dumps the specified list into an array, sorts
1.201 + * the array, and iterates over the list resetting each element
1.202 + * from the corresponding position in the array. This avoids the
1.203 + * n<sup>2</sup> log(n) performance that would result from attempting
1.204 + * to sort a linked list in place.
1.205 + *
1.206 + * @param list the list to be sorted.
1.207 + * @param c the comparator to determine the order of the list. A
1.208 + * {@code null} value indicates that the elements' <i>natural
1.209 + * ordering</i> should be used.
1.210 + * @throws ClassCastException if the list contains elements that are not
1.211 + * <i>mutually comparable</i> using the specified comparator.
1.212 + * @throws UnsupportedOperationException if the specified list's
1.213 + * list-iterator does not support the {@code set} operation.
1.214 + * @throws IllegalArgumentException (optional) if the comparator is
1.215 + * found to violate the {@link Comparator} contract
1.216 + */
1.217 + public static <T> void sort(List<T> list, Comparator<? super T> c) {
1.218 + Object[] a = list.toArray();
1.219 + Arrays.sort(a, (Comparator)c);
1.220 + ListIterator i = list.listIterator();
1.221 + for (int j=0; j<a.length; j++) {
1.222 + i.next();
1.223 + i.set(a[j]);
1.224 + }
1.225 + }
1.226 +
1.227 +
1.228 + /**
1.229 + * Searches the specified list for the specified object using the binary
1.230 + * search algorithm. The list must be sorted into ascending order
1.231 + * according to the {@linkplain Comparable natural ordering} of its
1.232 + * elements (as by the {@link #sort(List)} method) prior to making this
1.233 + * call. If it is not sorted, the results are undefined. If the list
1.234 + * contains multiple elements equal to the specified object, there is no
1.235 + * guarantee which one will be found.
1.236 + *
1.237 + * <p>This method runs in log(n) time for a "random access" list (which
1.238 + * provides near-constant-time positional access). If the specified list
1.239 + * does not implement the {@link RandomAccess} interface and is large,
1.240 + * this method will do an iterator-based binary search that performs
1.241 + * O(n) link traversals and O(log n) element comparisons.
1.242 + *
1.243 + * @param list the list to be searched.
1.244 + * @param key the key to be searched for.
1.245 + * @return the index of the search key, if it is contained in the list;
1.246 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.247 + * <i>insertion point</i> is defined as the point at which the
1.248 + * key would be inserted into the list: the index of the first
1.249 + * element greater than the key, or <tt>list.size()</tt> if all
1.250 + * elements in the list are less than the specified key. Note
1.251 + * that this guarantees that the return value will be >= 0 if
1.252 + * and only if the key is found.
1.253 + * @throws ClassCastException if the list contains elements that are not
1.254 + * <i>mutually comparable</i> (for example, strings and
1.255 + * integers), or the search key is not mutually comparable
1.256 + * with the elements of the list.
1.257 + */
1.258 + public static <T>
1.259 + int binarySearch(List<? extends Comparable<? super T>> list, T key) {
1.260 + if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
1.261 + return Collections.indexedBinarySearch(list, key);
1.262 + else
1.263 + return Collections.iteratorBinarySearch(list, key);
1.264 + }
1.265 +
1.266 + private static <T>
1.267 + int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
1.268 + {
1.269 + int low = 0;
1.270 + int high = list.size()-1;
1.271 +
1.272 + while (low <= high) {
1.273 + int mid = (low + high) >>> 1;
1.274 + Comparable<? super T> midVal = list.get(mid);
1.275 + int cmp = midVal.compareTo(key);
1.276 +
1.277 + if (cmp < 0)
1.278 + low = mid + 1;
1.279 + else if (cmp > 0)
1.280 + high = mid - 1;
1.281 + else
1.282 + return mid; // key found
1.283 + }
1.284 + return -(low + 1); // key not found
1.285 + }
1.286 +
1.287 + private static <T>
1.288 + int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
1.289 + {
1.290 + int low = 0;
1.291 + int high = list.size()-1;
1.292 + ListIterator<? extends Comparable<? super T>> i = list.listIterator();
1.293 +
1.294 + while (low <= high) {
1.295 + int mid = (low + high) >>> 1;
1.296 + Comparable<? super T> midVal = get(i, mid);
1.297 + int cmp = midVal.compareTo(key);
1.298 +
1.299 + if (cmp < 0)
1.300 + low = mid + 1;
1.301 + else if (cmp > 0)
1.302 + high = mid - 1;
1.303 + else
1.304 + return mid; // key found
1.305 + }
1.306 + return -(low + 1); // key not found
1.307 + }
1.308 +
1.309 + /**
1.310 + * Gets the ith element from the given list by repositioning the specified
1.311 + * list listIterator.
1.312 + */
1.313 + private static <T> T get(ListIterator<? extends T> i, int index) {
1.314 + T obj = null;
1.315 + int pos = i.nextIndex();
1.316 + if (pos <= index) {
1.317 + do {
1.318 + obj = i.next();
1.319 + } while (pos++ < index);
1.320 + } else {
1.321 + do {
1.322 + obj = i.previous();
1.323 + } while (--pos > index);
1.324 + }
1.325 + return obj;
1.326 + }
1.327 +
1.328 + /**
1.329 + * Searches the specified list for the specified object using the binary
1.330 + * search algorithm. The list must be sorted into ascending order
1.331 + * according to the specified comparator (as by the
1.332 + * {@link #sort(List, Comparator) sort(List, Comparator)}
1.333 + * method), prior to making this call. If it is
1.334 + * not sorted, the results are undefined. If the list contains multiple
1.335 + * elements equal to the specified object, there is no guarantee which one
1.336 + * will be found.
1.337 + *
1.338 + * <p>This method runs in log(n) time for a "random access" list (which
1.339 + * provides near-constant-time positional access). If the specified list
1.340 + * does not implement the {@link RandomAccess} interface and is large,
1.341 + * this method will do an iterator-based binary search that performs
1.342 + * O(n) link traversals and O(log n) element comparisons.
1.343 + *
1.344 + * @param list the list to be searched.
1.345 + * @param key the key to be searched for.
1.346 + * @param c the comparator by which the list is ordered.
1.347 + * A <tt>null</tt> value indicates that the elements'
1.348 + * {@linkplain Comparable natural ordering} should be used.
1.349 + * @return the index of the search key, if it is contained in the list;
1.350 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.351 + * <i>insertion point</i> is defined as the point at which the
1.352 + * key would be inserted into the list: the index of the first
1.353 + * element greater than the key, or <tt>list.size()</tt> if all
1.354 + * elements in the list are less than the specified key. Note
1.355 + * that this guarantees that the return value will be >= 0 if
1.356 + * and only if the key is found.
1.357 + * @throws ClassCastException if the list contains elements that are not
1.358 + * <i>mutually comparable</i> using the specified comparator,
1.359 + * or the search key is not mutually comparable with the
1.360 + * elements of the list using this comparator.
1.361 + */
1.362 + public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
1.363 + if (c==null)
1.364 + return binarySearch((List) list, key);
1.365 +
1.366 + if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
1.367 + return Collections.indexedBinarySearch(list, key, c);
1.368 + else
1.369 + return Collections.iteratorBinarySearch(list, key, c);
1.370 + }
1.371 +
1.372 + private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
1.373 + int low = 0;
1.374 + int high = l.size()-1;
1.375 +
1.376 + while (low <= high) {
1.377 + int mid = (low + high) >>> 1;
1.378 + T midVal = l.get(mid);
1.379 + int cmp = c.compare(midVal, key);
1.380 +
1.381 + if (cmp < 0)
1.382 + low = mid + 1;
1.383 + else if (cmp > 0)
1.384 + high = mid - 1;
1.385 + else
1.386 + return mid; // key found
1.387 + }
1.388 + return -(low + 1); // key not found
1.389 + }
1.390 +
1.391 + private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
1.392 + int low = 0;
1.393 + int high = l.size()-1;
1.394 + ListIterator<? extends T> i = l.listIterator();
1.395 +
1.396 + while (low <= high) {
1.397 + int mid = (low + high) >>> 1;
1.398 + T midVal = get(i, mid);
1.399 + int cmp = c.compare(midVal, key);
1.400 +
1.401 + if (cmp < 0)
1.402 + low = mid + 1;
1.403 + else if (cmp > 0)
1.404 + high = mid - 1;
1.405 + else
1.406 + return mid; // key found
1.407 + }
1.408 + return -(low + 1); // key not found
1.409 + }
1.410 +
1.411 + private interface SelfComparable extends Comparable<SelfComparable> {}
1.412 +
1.413 +
1.414 + /**
1.415 + * Reverses the order of the elements in the specified list.<p>
1.416 + *
1.417 + * This method runs in linear time.
1.418 + *
1.419 + * @param list the list whose elements are to be reversed.
1.420 + * @throws UnsupportedOperationException if the specified list or
1.421 + * its list-iterator does not support the <tt>set</tt> operation.
1.422 + */
1.423 + public static void reverse(List<?> list) {
1.424 + int size = list.size();
1.425 + if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
1.426 + for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
1.427 + swap(list, i, j);
1.428 + } else {
1.429 + ListIterator fwd = list.listIterator();
1.430 + ListIterator rev = list.listIterator(size);
1.431 + for (int i=0, mid=list.size()>>1; i<mid; i++) {
1.432 + Object tmp = fwd.next();
1.433 + fwd.set(rev.previous());
1.434 + rev.set(tmp);
1.435 + }
1.436 + }
1.437 + }
1.438 +
1.439 + /**
1.440 + * Randomly permutes the specified list using a default source of
1.441 + * randomness. All permutations occur with approximately equal
1.442 + * likelihood.<p>
1.443 + *
1.444 + * The hedge "approximately" is used in the foregoing description because
1.445 + * default source of randomness is only approximately an unbiased source
1.446 + * of independently chosen bits. If it were a perfect source of randomly
1.447 + * chosen bits, then the algorithm would choose permutations with perfect
1.448 + * uniformity.<p>
1.449 + *
1.450 + * This implementation traverses the list backwards, from the last element
1.451 + * up to the second, repeatedly swapping a randomly selected element into
1.452 + * the "current position". Elements are randomly selected from the
1.453 + * portion of the list that runs from the first element to the current
1.454 + * position, inclusive.<p>
1.455 + *
1.456 + * This method runs in linear time. If the specified list does not
1.457 + * implement the {@link RandomAccess} interface and is large, this
1.458 + * implementation dumps the specified list into an array before shuffling
1.459 + * it, and dumps the shuffled array back into the list. This avoids the
1.460 + * quadratic behavior that would result from shuffling a "sequential
1.461 + * access" list in place.
1.462 + *
1.463 + * @param list the list to be shuffled.
1.464 + * @throws UnsupportedOperationException if the specified list or
1.465 + * its list-iterator does not support the <tt>set</tt> operation.
1.466 + */
1.467 + public static void shuffle(List<?> list) {
1.468 + Random rnd = r;
1.469 + if (rnd == null)
1.470 + r = rnd = new Random();
1.471 + shuffle(list, rnd);
1.472 + }
1.473 + private static Random r;
1.474 +
1.475 + /**
1.476 + * Randomly permute the specified list using the specified source of
1.477 + * randomness. All permutations occur with equal likelihood
1.478 + * assuming that the source of randomness is fair.<p>
1.479 + *
1.480 + * This implementation traverses the list backwards, from the last element
1.481 + * up to the second, repeatedly swapping a randomly selected element into
1.482 + * the "current position". Elements are randomly selected from the
1.483 + * portion of the list that runs from the first element to the current
1.484 + * position, inclusive.<p>
1.485 + *
1.486 + * This method runs in linear time. If the specified list does not
1.487 + * implement the {@link RandomAccess} interface and is large, this
1.488 + * implementation dumps the specified list into an array before shuffling
1.489 + * it, and dumps the shuffled array back into the list. This avoids the
1.490 + * quadratic behavior that would result from shuffling a "sequential
1.491 + * access" list in place.
1.492 + *
1.493 + * @param list the list to be shuffled.
1.494 + * @param rnd the source of randomness to use to shuffle the list.
1.495 + * @throws UnsupportedOperationException if the specified list or its
1.496 + * list-iterator does not support the <tt>set</tt> operation.
1.497 + */
1.498 + public static void shuffle(List<?> list, Random rnd) {
1.499 + int size = list.size();
1.500 + if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
1.501 + for (int i=size; i>1; i--)
1.502 + swap(list, i-1, rnd.nextInt(i));
1.503 + } else {
1.504 + Object arr[] = list.toArray();
1.505 +
1.506 + // Shuffle array
1.507 + for (int i=size; i>1; i--)
1.508 + swap(arr, i-1, rnd.nextInt(i));
1.509 +
1.510 + // Dump array back into list
1.511 + ListIterator it = list.listIterator();
1.512 + for (int i=0; i<arr.length; i++) {
1.513 + it.next();
1.514 + it.set(arr[i]);
1.515 + }
1.516 + }
1.517 + }
1.518 +
1.519 + /**
1.520 + * Swaps the elements at the specified positions in the specified list.
1.521 + * (If the specified positions are equal, invoking this method leaves
1.522 + * the list unchanged.)
1.523 + *
1.524 + * @param list The list in which to swap elements.
1.525 + * @param i the index of one element to be swapped.
1.526 + * @param j the index of the other element to be swapped.
1.527 + * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
1.528 + * is out of range (i < 0 || i >= list.size()
1.529 + * || j < 0 || j >= list.size()).
1.530 + * @since 1.4
1.531 + */
1.532 + public static void swap(List<?> list, int i, int j) {
1.533 + final List l = list;
1.534 + l.set(i, l.set(j, l.get(i)));
1.535 + }
1.536 +
1.537 + /**
1.538 + * Swaps the two specified elements in the specified array.
1.539 + */
1.540 + private static void swap(Object[] arr, int i, int j) {
1.541 + Object tmp = arr[i];
1.542 + arr[i] = arr[j];
1.543 + arr[j] = tmp;
1.544 + }
1.545 +
1.546 + /**
1.547 + * Replaces all of the elements of the specified list with the specified
1.548 + * element. <p>
1.549 + *
1.550 + * This method runs in linear time.
1.551 + *
1.552 + * @param list the list to be filled with the specified element.
1.553 + * @param obj The element with which to fill the specified list.
1.554 + * @throws UnsupportedOperationException if the specified list or its
1.555 + * list-iterator does not support the <tt>set</tt> operation.
1.556 + */
1.557 + public static <T> void fill(List<? super T> list, T obj) {
1.558 + int size = list.size();
1.559 +
1.560 + if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
1.561 + for (int i=0; i<size; i++)
1.562 + list.set(i, obj);
1.563 + } else {
1.564 + ListIterator<? super T> itr = list.listIterator();
1.565 + for (int i=0; i<size; i++) {
1.566 + itr.next();
1.567 + itr.set(obj);
1.568 + }
1.569 + }
1.570 + }
1.571 +
1.572 + /**
1.573 + * Copies all of the elements from one list into another. After the
1.574 + * operation, the index of each copied element in the destination list
1.575 + * will be identical to its index in the source list. The destination
1.576 + * list must be at least as long as the source list. If it is longer, the
1.577 + * remaining elements in the destination list are unaffected. <p>
1.578 + *
1.579 + * This method runs in linear time.
1.580 + *
1.581 + * @param dest The destination list.
1.582 + * @param src The source list.
1.583 + * @throws IndexOutOfBoundsException if the destination list is too small
1.584 + * to contain the entire source List.
1.585 + * @throws UnsupportedOperationException if the destination list's
1.586 + * list-iterator does not support the <tt>set</tt> operation.
1.587 + */
1.588 + public static <T> void copy(List<? super T> dest, List<? extends T> src) {
1.589 + int srcSize = src.size();
1.590 + if (srcSize > dest.size())
1.591 + throw new IndexOutOfBoundsException("Source does not fit in dest");
1.592 +
1.593 + if (srcSize < COPY_THRESHOLD ||
1.594 + (src instanceof RandomAccess && dest instanceof RandomAccess)) {
1.595 + for (int i=0; i<srcSize; i++)
1.596 + dest.set(i, src.get(i));
1.597 + } else {
1.598 + ListIterator<? super T> di=dest.listIterator();
1.599 + ListIterator<? extends T> si=src.listIterator();
1.600 + for (int i=0; i<srcSize; i++) {
1.601 + di.next();
1.602 + di.set(si.next());
1.603 + }
1.604 + }
1.605 + }
1.606 +
1.607 + /**
1.608 + * Returns the minimum element of the given collection, according to the
1.609 + * <i>natural ordering</i> of its elements. All elements in the
1.610 + * collection must implement the <tt>Comparable</tt> interface.
1.611 + * Furthermore, all elements in the collection must be <i>mutually
1.612 + * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
1.613 + * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1.614 + * <tt>e2</tt> in the collection).<p>
1.615 + *
1.616 + * This method iterates over the entire collection, hence it requires
1.617 + * time proportional to the size of the collection.
1.618 + *
1.619 + * @param coll the collection whose minimum element is to be determined.
1.620 + * @return the minimum element of the given collection, according
1.621 + * to the <i>natural ordering</i> of its elements.
1.622 + * @throws ClassCastException if the collection contains elements that are
1.623 + * not <i>mutually comparable</i> (for example, strings and
1.624 + * integers).
1.625 + * @throws NoSuchElementException if the collection is empty.
1.626 + * @see Comparable
1.627 + */
1.628 + public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {
1.629 + Iterator<? extends T> i = coll.iterator();
1.630 + T candidate = i.next();
1.631 +
1.632 + while (i.hasNext()) {
1.633 + T next = i.next();
1.634 + if (next.compareTo(candidate) < 0)
1.635 + candidate = next;
1.636 + }
1.637 + return candidate;
1.638 + }
1.639 +
1.640 + /**
1.641 + * Returns the minimum element of the given collection, according to the
1.642 + * order induced by the specified comparator. All elements in the
1.643 + * collection must be <i>mutually comparable</i> by the specified
1.644 + * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
1.645 + * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1.646 + * <tt>e2</tt> in the collection).<p>
1.647 + *
1.648 + * This method iterates over the entire collection, hence it requires
1.649 + * time proportional to the size of the collection.
1.650 + *
1.651 + * @param coll the collection whose minimum element is to be determined.
1.652 + * @param comp the comparator with which to determine the minimum element.
1.653 + * A <tt>null</tt> value indicates that the elements' <i>natural
1.654 + * ordering</i> should be used.
1.655 + * @return the minimum element of the given collection, according
1.656 + * to the specified comparator.
1.657 + * @throws ClassCastException if the collection contains elements that are
1.658 + * not <i>mutually comparable</i> using the specified comparator.
1.659 + * @throws NoSuchElementException if the collection is empty.
1.660 + * @see Comparable
1.661 + */
1.662 + public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
1.663 + if (comp==null)
1.664 + return (T)min((Collection<SelfComparable>) (Collection) coll);
1.665 +
1.666 + Iterator<? extends T> i = coll.iterator();
1.667 + T candidate = i.next();
1.668 +
1.669 + while (i.hasNext()) {
1.670 + T next = i.next();
1.671 + if (comp.compare(next, candidate) < 0)
1.672 + candidate = next;
1.673 + }
1.674 + return candidate;
1.675 + }
1.676 +
1.677 + /**
1.678 + * Returns the maximum element of the given collection, according to the
1.679 + * <i>natural ordering</i> of its elements. All elements in the
1.680 + * collection must implement the <tt>Comparable</tt> interface.
1.681 + * Furthermore, all elements in the collection must be <i>mutually
1.682 + * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
1.683 + * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1.684 + * <tt>e2</tt> in the collection).<p>
1.685 + *
1.686 + * This method iterates over the entire collection, hence it requires
1.687 + * time proportional to the size of the collection.
1.688 + *
1.689 + * @param coll the collection whose maximum element is to be determined.
1.690 + * @return the maximum element of the given collection, according
1.691 + * to the <i>natural ordering</i> of its elements.
1.692 + * @throws ClassCastException if the collection contains elements that are
1.693 + * not <i>mutually comparable</i> (for example, strings and
1.694 + * integers).
1.695 + * @throws NoSuchElementException if the collection is empty.
1.696 + * @see Comparable
1.697 + */
1.698 + public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
1.699 + Iterator<? extends T> i = coll.iterator();
1.700 + T candidate = i.next();
1.701 +
1.702 + while (i.hasNext()) {
1.703 + T next = i.next();
1.704 + if (next.compareTo(candidate) > 0)
1.705 + candidate = next;
1.706 + }
1.707 + return candidate;
1.708 + }
1.709 +
1.710 + /**
1.711 + * Returns the maximum element of the given collection, according to the
1.712 + * order induced by the specified comparator. All elements in the
1.713 + * collection must be <i>mutually comparable</i> by the specified
1.714 + * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
1.715 + * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1.716 + * <tt>e2</tt> in the collection).<p>
1.717 + *
1.718 + * This method iterates over the entire collection, hence it requires
1.719 + * time proportional to the size of the collection.
1.720 + *
1.721 + * @param coll the collection whose maximum element is to be determined.
1.722 + * @param comp the comparator with which to determine the maximum element.
1.723 + * A <tt>null</tt> value indicates that the elements' <i>natural
1.724 + * ordering</i> should be used.
1.725 + * @return the maximum element of the given collection, according
1.726 + * to the specified comparator.
1.727 + * @throws ClassCastException if the collection contains elements that are
1.728 + * not <i>mutually comparable</i> using the specified comparator.
1.729 + * @throws NoSuchElementException if the collection is empty.
1.730 + * @see Comparable
1.731 + */
1.732 + public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
1.733 + if (comp==null)
1.734 + return (T)max((Collection<SelfComparable>) (Collection) coll);
1.735 +
1.736 + Iterator<? extends T> i = coll.iterator();
1.737 + T candidate = i.next();
1.738 +
1.739 + while (i.hasNext()) {
1.740 + T next = i.next();
1.741 + if (comp.compare(next, candidate) > 0)
1.742 + candidate = next;
1.743 + }
1.744 + return candidate;
1.745 + }
1.746 +
1.747 + /**
1.748 + * Rotates the elements in the specified list by the specified distance.
1.749 + * After calling this method, the element at index <tt>i</tt> will be
1.750 + * the element previously at index <tt>(i - distance)</tt> mod
1.751 + * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
1.752 + * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
1.753 + * the size of the list.)
1.754 + *
1.755 + * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
1.756 + * After invoking <tt>Collections.rotate(list, 1)</tt> (or
1.757 + * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
1.758 + * <tt>[s, t, a, n, k]</tt>.
1.759 + *
1.760 + * <p>Note that this method can usefully be applied to sublists to
1.761 + * move one or more elements within a list while preserving the
1.762 + * order of the remaining elements. For example, the following idiom
1.763 + * moves the element at index <tt>j</tt> forward to position
1.764 + * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
1.765 + * <pre>
1.766 + * Collections.rotate(list.subList(j, k+1), -1);
1.767 + * </pre>
1.768 + * To make this concrete, suppose <tt>list</tt> comprises
1.769 + * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt>
1.770 + * (<tt>b</tt>) forward two positions, perform the following invocation:
1.771 + * <pre>
1.772 + * Collections.rotate(l.subList(1, 4), -1);
1.773 + * </pre>
1.774 + * The resulting list is <tt>[a, c, d, b, e]</tt>.
1.775 + *
1.776 + * <p>To move more than one element forward, increase the absolute value
1.777 + * of the rotation distance. To move elements backward, use a positive
1.778 + * shift distance.
1.779 + *
1.780 + * <p>If the specified list is small or implements the {@link
1.781 + * RandomAccess} interface, this implementation exchanges the first
1.782 + * element into the location it should go, and then repeatedly exchanges
1.783 + * the displaced element into the location it should go until a displaced
1.784 + * element is swapped into the first element. If necessary, the process
1.785 + * is repeated on the second and successive elements, until the rotation
1.786 + * is complete. If the specified list is large and doesn't implement the
1.787 + * <tt>RandomAccess</tt> interface, this implementation breaks the
1.788 + * list into two sublist views around index <tt>-distance mod size</tt>.
1.789 + * Then the {@link #reverse(List)} method is invoked on each sublist view,
1.790 + * and finally it is invoked on the entire list. For a more complete
1.791 + * description of both algorithms, see Section 2.3 of Jon Bentley's
1.792 + * <i>Programming Pearls</i> (Addison-Wesley, 1986).
1.793 + *
1.794 + * @param list the list to be rotated.
1.795 + * @param distance the distance to rotate the list. There are no
1.796 + * constraints on this value; it may be zero, negative, or
1.797 + * greater than <tt>list.size()</tt>.
1.798 + * @throws UnsupportedOperationException if the specified list or
1.799 + * its list-iterator does not support the <tt>set</tt> operation.
1.800 + * @since 1.4
1.801 + */
1.802 + public static void rotate(List<?> list, int distance) {
1.803 + if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
1.804 + rotate1(list, distance);
1.805 + else
1.806 + rotate2(list, distance);
1.807 + }
1.808 +
1.809 + private static <T> void rotate1(List<T> list, int distance) {
1.810 + int size = list.size();
1.811 + if (size == 0)
1.812 + return;
1.813 + distance = distance % size;
1.814 + if (distance < 0)
1.815 + distance += size;
1.816 + if (distance == 0)
1.817 + return;
1.818 +
1.819 + for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
1.820 + T displaced = list.get(cycleStart);
1.821 + int i = cycleStart;
1.822 + do {
1.823 + i += distance;
1.824 + if (i >= size)
1.825 + i -= size;
1.826 + displaced = list.set(i, displaced);
1.827 + nMoved ++;
1.828 + } while (i != cycleStart);
1.829 + }
1.830 + }
1.831 +
1.832 + private static void rotate2(List<?> list, int distance) {
1.833 + int size = list.size();
1.834 + if (size == 0)
1.835 + return;
1.836 + int mid = -distance % size;
1.837 + if (mid < 0)
1.838 + mid += size;
1.839 + if (mid == 0)
1.840 + return;
1.841 +
1.842 + reverse(list.subList(0, mid));
1.843 + reverse(list.subList(mid, size));
1.844 + reverse(list);
1.845 + }
1.846 +
1.847 + /**
1.848 + * Replaces all occurrences of one specified value in a list with another.
1.849 + * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
1.850 + * in <tt>list</tt> such that
1.851 + * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
1.852 + * (This method has no effect on the size of the list.)
1.853 + *
1.854 + * @param list the list in which replacement is to occur.
1.855 + * @param oldVal the old value to be replaced.
1.856 + * @param newVal the new value with which <tt>oldVal</tt> is to be
1.857 + * replaced.
1.858 + * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
1.859 + * <tt>e</tt> such that
1.860 + * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
1.861 + * @throws UnsupportedOperationException if the specified list or
1.862 + * its list-iterator does not support the <tt>set</tt> operation.
1.863 + * @since 1.4
1.864 + */
1.865 + public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
1.866 + boolean result = false;
1.867 + int size = list.size();
1.868 + if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
1.869 + if (oldVal==null) {
1.870 + for (int i=0; i<size; i++) {
1.871 + if (list.get(i)==null) {
1.872 + list.set(i, newVal);
1.873 + result = true;
1.874 + }
1.875 + }
1.876 + } else {
1.877 + for (int i=0; i<size; i++) {
1.878 + if (oldVal.equals(list.get(i))) {
1.879 + list.set(i, newVal);
1.880 + result = true;
1.881 + }
1.882 + }
1.883 + }
1.884 + } else {
1.885 + ListIterator<T> itr=list.listIterator();
1.886 + if (oldVal==null) {
1.887 + for (int i=0; i<size; i++) {
1.888 + if (itr.next()==null) {
1.889 + itr.set(newVal);
1.890 + result = true;
1.891 + }
1.892 + }
1.893 + } else {
1.894 + for (int i=0; i<size; i++) {
1.895 + if (oldVal.equals(itr.next())) {
1.896 + itr.set(newVal);
1.897 + result = true;
1.898 + }
1.899 + }
1.900 + }
1.901 + }
1.902 + return result;
1.903 + }
1.904 +
1.905 + /**
1.906 + * Returns the starting position of the first occurrence of the specified
1.907 + * target list within the specified source list, or -1 if there is no
1.908 + * such occurrence. More formally, returns the lowest index <tt>i</tt>
1.909 + * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
1.910 + * or -1 if there is no such index. (Returns -1 if
1.911 + * <tt>target.size() > source.size()</tt>.)
1.912 + *
1.913 + * <p>This implementation uses the "brute force" technique of scanning
1.914 + * over the source list, looking for a match with the target at each
1.915 + * location in turn.
1.916 + *
1.917 + * @param source the list in which to search for the first occurrence
1.918 + * of <tt>target</tt>.
1.919 + * @param target the list to search for as a subList of <tt>source</tt>.
1.920 + * @return the starting position of the first occurrence of the specified
1.921 + * target list within the specified source list, or -1 if there
1.922 + * is no such occurrence.
1.923 + * @since 1.4
1.924 + */
1.925 + public static int indexOfSubList(List<?> source, List<?> target) {
1.926 + int sourceSize = source.size();
1.927 + int targetSize = target.size();
1.928 + int maxCandidate = sourceSize - targetSize;
1.929 +
1.930 + if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
1.931 + (source instanceof RandomAccess&&target instanceof RandomAccess)) {
1.932 + nextCand:
1.933 + for (int candidate = 0; candidate <= maxCandidate; candidate++) {
1.934 + for (int i=0, j=candidate; i<targetSize; i++, j++)
1.935 + if (!eq(target.get(i), source.get(j)))
1.936 + continue nextCand; // Element mismatch, try next cand
1.937 + return candidate; // All elements of candidate matched target
1.938 + }
1.939 + } else { // Iterator version of above algorithm
1.940 + ListIterator<?> si = source.listIterator();
1.941 + nextCand:
1.942 + for (int candidate = 0; candidate <= maxCandidate; candidate++) {
1.943 + ListIterator<?> ti = target.listIterator();
1.944 + for (int i=0; i<targetSize; i++) {
1.945 + if (!eq(ti.next(), si.next())) {
1.946 + // Back up source iterator to next candidate
1.947 + for (int j=0; j<i; j++)
1.948 + si.previous();
1.949 + continue nextCand;
1.950 + }
1.951 + }
1.952 + return candidate;
1.953 + }
1.954 + }
1.955 + return -1; // No candidate matched the target
1.956 + }
1.957 +
1.958 + /**
1.959 + * Returns the starting position of the last occurrence of the specified
1.960 + * target list within the specified source list, or -1 if there is no such
1.961 + * occurrence. More formally, returns the highest index <tt>i</tt>
1.962 + * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
1.963 + * or -1 if there is no such index. (Returns -1 if
1.964 + * <tt>target.size() > source.size()</tt>.)
1.965 + *
1.966 + * <p>This implementation uses the "brute force" technique of iterating
1.967 + * over the source list, looking for a match with the target at each
1.968 + * location in turn.
1.969 + *
1.970 + * @param source the list in which to search for the last occurrence
1.971 + * of <tt>target</tt>.
1.972 + * @param target the list to search for as a subList of <tt>source</tt>.
1.973 + * @return the starting position of the last occurrence of the specified
1.974 + * target list within the specified source list, or -1 if there
1.975 + * is no such occurrence.
1.976 + * @since 1.4
1.977 + */
1.978 + public static int lastIndexOfSubList(List<?> source, List<?> target) {
1.979 + int sourceSize = source.size();
1.980 + int targetSize = target.size();
1.981 + int maxCandidate = sourceSize - targetSize;
1.982 +
1.983 + if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
1.984 + source instanceof RandomAccess) { // Index access version
1.985 + nextCand:
1.986 + for (int candidate = maxCandidate; candidate >= 0; candidate--) {
1.987 + for (int i=0, j=candidate; i<targetSize; i++, j++)
1.988 + if (!eq(target.get(i), source.get(j)))
1.989 + continue nextCand; // Element mismatch, try next cand
1.990 + return candidate; // All elements of candidate matched target
1.991 + }
1.992 + } else { // Iterator version of above algorithm
1.993 + if (maxCandidate < 0)
1.994 + return -1;
1.995 + ListIterator<?> si = source.listIterator(maxCandidate);
1.996 + nextCand:
1.997 + for (int candidate = maxCandidate; candidate >= 0; candidate--) {
1.998 + ListIterator<?> ti = target.listIterator();
1.999 + for (int i=0; i<targetSize; i++) {
1.1000 + if (!eq(ti.next(), si.next())) {
1.1001 + if (candidate != 0) {
1.1002 + // Back up source iterator to next candidate
1.1003 + for (int j=0; j<=i+1; j++)
1.1004 + si.previous();
1.1005 + }
1.1006 + continue nextCand;
1.1007 + }
1.1008 + }
1.1009 + return candidate;
1.1010 + }
1.1011 + }
1.1012 + return -1; // No candidate matched the target
1.1013 + }
1.1014 +
1.1015 +
1.1016 + // Unmodifiable Wrappers
1.1017 +
1.1018 + /**
1.1019 + * Returns an unmodifiable view of the specified collection. This method
1.1020 + * allows modules to provide users with "read-only" access to internal
1.1021 + * collections. Query operations on the returned collection "read through"
1.1022 + * to the specified collection, and attempts to modify the returned
1.1023 + * collection, whether direct or via its iterator, result in an
1.1024 + * <tt>UnsupportedOperationException</tt>.<p>
1.1025 + *
1.1026 + * The returned collection does <i>not</i> pass the hashCode and equals
1.1027 + * operations through to the backing collection, but relies on
1.1028 + * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
1.1029 + * is necessary to preserve the contracts of these operations in the case
1.1030 + * that the backing collection is a set or a list.<p>
1.1031 + *
1.1032 + * The returned collection will be serializable if the specified collection
1.1033 + * is serializable.
1.1034 + *
1.1035 + * @param c the collection for which an unmodifiable view is to be
1.1036 + * returned.
1.1037 + * @return an unmodifiable view of the specified collection.
1.1038 + */
1.1039 + public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
1.1040 + return new UnmodifiableCollection<>(c);
1.1041 + }
1.1042 +
1.1043 + /**
1.1044 + * @serial include
1.1045 + */
1.1046 + static class UnmodifiableCollection<E> implements Collection<E>, Serializable {
1.1047 + private static final long serialVersionUID = 1820017752578914078L;
1.1048 +
1.1049 + final Collection<? extends E> c;
1.1050 +
1.1051 + UnmodifiableCollection(Collection<? extends E> c) {
1.1052 + if (c==null)
1.1053 + throw new NullPointerException();
1.1054 + this.c = c;
1.1055 + }
1.1056 +
1.1057 + public int size() {return c.size();}
1.1058 + public boolean isEmpty() {return c.isEmpty();}
1.1059 + public boolean contains(Object o) {return c.contains(o);}
1.1060 + public Object[] toArray() {return c.toArray();}
1.1061 + public <T> T[] toArray(T[] a) {return c.toArray(a);}
1.1062 + public String toString() {return c.toString();}
1.1063 +
1.1064 + public Iterator<E> iterator() {
1.1065 + return new Iterator<E>() {
1.1066 + private final Iterator<? extends E> i = c.iterator();
1.1067 +
1.1068 + public boolean hasNext() {return i.hasNext();}
1.1069 + public E next() {return i.next();}
1.1070 + public void remove() {
1.1071 + throw new UnsupportedOperationException();
1.1072 + }
1.1073 + };
1.1074 + }
1.1075 +
1.1076 + public boolean add(E e) {
1.1077 + throw new UnsupportedOperationException();
1.1078 + }
1.1079 + public boolean remove(Object o) {
1.1080 + throw new UnsupportedOperationException();
1.1081 + }
1.1082 +
1.1083 + public boolean containsAll(Collection<?> coll) {
1.1084 + return c.containsAll(coll);
1.1085 + }
1.1086 + public boolean addAll(Collection<? extends E> coll) {
1.1087 + throw new UnsupportedOperationException();
1.1088 + }
1.1089 + public boolean removeAll(Collection<?> coll) {
1.1090 + throw new UnsupportedOperationException();
1.1091 + }
1.1092 + public boolean retainAll(Collection<?> coll) {
1.1093 + throw new UnsupportedOperationException();
1.1094 + }
1.1095 + public void clear() {
1.1096 + throw new UnsupportedOperationException();
1.1097 + }
1.1098 + }
1.1099 +
1.1100 + /**
1.1101 + * Returns an unmodifiable view of the specified set. This method allows
1.1102 + * modules to provide users with "read-only" access to internal sets.
1.1103 + * Query operations on the returned set "read through" to the specified
1.1104 + * set, and attempts to modify the returned set, whether direct or via its
1.1105 + * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1.1106 + *
1.1107 + * The returned set will be serializable if the specified set
1.1108 + * is serializable.
1.1109 + *
1.1110 + * @param s the set for which an unmodifiable view is to be returned.
1.1111 + * @return an unmodifiable view of the specified set.
1.1112 + */
1.1113 + public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1.1114 + return new UnmodifiableSet<>(s);
1.1115 + }
1.1116 +
1.1117 + /**
1.1118 + * @serial include
1.1119 + */
1.1120 + static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
1.1121 + implements Set<E>, Serializable {
1.1122 + private static final long serialVersionUID = -9215047833775013803L;
1.1123 +
1.1124 + UnmodifiableSet(Set<? extends E> s) {super(s);}
1.1125 + public boolean equals(Object o) {return o == this || c.equals(o);}
1.1126 + public int hashCode() {return c.hashCode();}
1.1127 + }
1.1128 +
1.1129 + /**
1.1130 + * Returns an unmodifiable view of the specified sorted set. This method
1.1131 + * allows modules to provide users with "read-only" access to internal
1.1132 + * sorted sets. Query operations on the returned sorted set "read
1.1133 + * through" to the specified sorted set. Attempts to modify the returned
1.1134 + * sorted set, whether direct, via its iterator, or via its
1.1135 + * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1.1136 + * an <tt>UnsupportedOperationException</tt>.<p>
1.1137 + *
1.1138 + * The returned sorted set will be serializable if the specified sorted set
1.1139 + * is serializable.
1.1140 + *
1.1141 + * @param s the sorted set for which an unmodifiable view is to be
1.1142 + * returned.
1.1143 + * @return an unmodifiable view of the specified sorted set.
1.1144 + */
1.1145 + public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
1.1146 + return new UnmodifiableSortedSet<>(s);
1.1147 + }
1.1148 +
1.1149 + /**
1.1150 + * @serial include
1.1151 + */
1.1152 + static class UnmodifiableSortedSet<E>
1.1153 + extends UnmodifiableSet<E>
1.1154 + implements SortedSet<E>, Serializable {
1.1155 + private static final long serialVersionUID = -4929149591599911165L;
1.1156 + private final SortedSet<E> ss;
1.1157 +
1.1158 + UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;}
1.1159 +
1.1160 + public Comparator<? super E> comparator() {return ss.comparator();}
1.1161 +
1.1162 + public SortedSet<E> subSet(E fromElement, E toElement) {
1.1163 + return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement));
1.1164 + }
1.1165 + public SortedSet<E> headSet(E toElement) {
1.1166 + return new UnmodifiableSortedSet<>(ss.headSet(toElement));
1.1167 + }
1.1168 + public SortedSet<E> tailSet(E fromElement) {
1.1169 + return new UnmodifiableSortedSet<>(ss.tailSet(fromElement));
1.1170 + }
1.1171 +
1.1172 + public E first() {return ss.first();}
1.1173 + public E last() {return ss.last();}
1.1174 + }
1.1175 +
1.1176 + /**
1.1177 + * Returns an unmodifiable view of the specified list. This method allows
1.1178 + * modules to provide users with "read-only" access to internal
1.1179 + * lists. Query operations on the returned list "read through" to the
1.1180 + * specified list, and attempts to modify the returned list, whether
1.1181 + * direct or via its iterator, result in an
1.1182 + * <tt>UnsupportedOperationException</tt>.<p>
1.1183 + *
1.1184 + * The returned list will be serializable if the specified list
1.1185 + * is serializable. Similarly, the returned list will implement
1.1186 + * {@link RandomAccess} if the specified list does.
1.1187 + *
1.1188 + * @param list the list for which an unmodifiable view is to be returned.
1.1189 + * @return an unmodifiable view of the specified list.
1.1190 + */
1.1191 + public static <T> List<T> unmodifiableList(List<? extends T> list) {
1.1192 + return (list instanceof RandomAccess ?
1.1193 + new UnmodifiableRandomAccessList<>(list) :
1.1194 + new UnmodifiableList<>(list));
1.1195 + }
1.1196 +
1.1197 + /**
1.1198 + * @serial include
1.1199 + */
1.1200 + static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1.1201 + implements List<E> {
1.1202 + private static final long serialVersionUID = -283967356065247728L;
1.1203 + final List<? extends E> list;
1.1204 +
1.1205 + UnmodifiableList(List<? extends E> list) {
1.1206 + super(list);
1.1207 + this.list = list;
1.1208 + }
1.1209 +
1.1210 + public boolean equals(Object o) {return o == this || list.equals(o);}
1.1211 + public int hashCode() {return list.hashCode();}
1.1212 +
1.1213 + public E get(int index) {return list.get(index);}
1.1214 + public E set(int index, E element) {
1.1215 + throw new UnsupportedOperationException();
1.1216 + }
1.1217 + public void add(int index, E element) {
1.1218 + throw new UnsupportedOperationException();
1.1219 + }
1.1220 + public E remove(int index) {
1.1221 + throw new UnsupportedOperationException();
1.1222 + }
1.1223 + public int indexOf(Object o) {return list.indexOf(o);}
1.1224 + public int lastIndexOf(Object o) {return list.lastIndexOf(o);}
1.1225 + public boolean addAll(int index, Collection<? extends E> c) {
1.1226 + throw new UnsupportedOperationException();
1.1227 + }
1.1228 + public ListIterator<E> listIterator() {return listIterator(0);}
1.1229 +
1.1230 + public ListIterator<E> listIterator(final int index) {
1.1231 + return new ListIterator<E>() {
1.1232 + private final ListIterator<? extends E> i
1.1233 + = list.listIterator(index);
1.1234 +
1.1235 + public boolean hasNext() {return i.hasNext();}
1.1236 + public E next() {return i.next();}
1.1237 + public boolean hasPrevious() {return i.hasPrevious();}
1.1238 + public E previous() {return i.previous();}
1.1239 + public int nextIndex() {return i.nextIndex();}
1.1240 + public int previousIndex() {return i.previousIndex();}
1.1241 +
1.1242 + public void remove() {
1.1243 + throw new UnsupportedOperationException();
1.1244 + }
1.1245 + public void set(E e) {
1.1246 + throw new UnsupportedOperationException();
1.1247 + }
1.1248 + public void add(E e) {
1.1249 + throw new UnsupportedOperationException();
1.1250 + }
1.1251 + };
1.1252 + }
1.1253 +
1.1254 + public List<E> subList(int fromIndex, int toIndex) {
1.1255 + return new UnmodifiableList<>(list.subList(fromIndex, toIndex));
1.1256 + }
1.1257 +
1.1258 + /**
1.1259 + * UnmodifiableRandomAccessList instances are serialized as
1.1260 + * UnmodifiableList instances to allow them to be deserialized
1.1261 + * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
1.1262 + * This method inverts the transformation. As a beneficial
1.1263 + * side-effect, it also grafts the RandomAccess marker onto
1.1264 + * UnmodifiableList instances that were serialized in pre-1.4 JREs.
1.1265 + *
1.1266 + * Note: Unfortunately, UnmodifiableRandomAccessList instances
1.1267 + * serialized in 1.4.1 and deserialized in 1.4 will become
1.1268 + * UnmodifiableList instances, as this method was missing in 1.4.
1.1269 + */
1.1270 + private Object readResolve() {
1.1271 + return (list instanceof RandomAccess
1.1272 + ? new UnmodifiableRandomAccessList<>(list)
1.1273 + : this);
1.1274 + }
1.1275 + }
1.1276 +
1.1277 + /**
1.1278 + * @serial include
1.1279 + */
1.1280 + static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E>
1.1281 + implements RandomAccess
1.1282 + {
1.1283 + UnmodifiableRandomAccessList(List<? extends E> list) {
1.1284 + super(list);
1.1285 + }
1.1286 +
1.1287 + public List<E> subList(int fromIndex, int toIndex) {
1.1288 + return new UnmodifiableRandomAccessList<>(
1.1289 + list.subList(fromIndex, toIndex));
1.1290 + }
1.1291 +
1.1292 + private static final long serialVersionUID = -2542308836966382001L;
1.1293 +
1.1294 + /**
1.1295 + * Allows instances to be deserialized in pre-1.4 JREs (which do
1.1296 + * not have UnmodifiableRandomAccessList). UnmodifiableList has
1.1297 + * a readResolve method that inverts this transformation upon
1.1298 + * deserialization.
1.1299 + */
1.1300 + private Object writeReplace() {
1.1301 + return new UnmodifiableList<>(list);
1.1302 + }
1.1303 + }
1.1304 +
1.1305 + /**
1.1306 + * Returns an unmodifiable view of the specified map. This method
1.1307 + * allows modules to provide users with "read-only" access to internal
1.1308 + * maps. Query operations on the returned map "read through"
1.1309 + * to the specified map, and attempts to modify the returned
1.1310 + * map, whether direct or via its collection views, result in an
1.1311 + * <tt>UnsupportedOperationException</tt>.<p>
1.1312 + *
1.1313 + * The returned map will be serializable if the specified map
1.1314 + * is serializable.
1.1315 + *
1.1316 + * @param m the map for which an unmodifiable view is to be returned.
1.1317 + * @return an unmodifiable view of the specified map.
1.1318 + */
1.1319 + public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) {
1.1320 + return new UnmodifiableMap<>(m);
1.1321 + }
1.1322 +
1.1323 + /**
1.1324 + * @serial include
1.1325 + */
1.1326 + private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable {
1.1327 + private static final long serialVersionUID = -1034234728574286014L;
1.1328 +
1.1329 + private final Map<? extends K, ? extends V> m;
1.1330 +
1.1331 + UnmodifiableMap(Map<? extends K, ? extends V> m) {
1.1332 + if (m==null)
1.1333 + throw new NullPointerException();
1.1334 + this.m = m;
1.1335 + }
1.1336 +
1.1337 + public int size() {return m.size();}
1.1338 + public boolean isEmpty() {return m.isEmpty();}
1.1339 + public boolean containsKey(Object key) {return m.containsKey(key);}
1.1340 + public boolean containsValue(Object val) {return m.containsValue(val);}
1.1341 + public V get(Object key) {return m.get(key);}
1.1342 +
1.1343 + public V put(K key, V value) {
1.1344 + throw new UnsupportedOperationException();
1.1345 + }
1.1346 + public V remove(Object key) {
1.1347 + throw new UnsupportedOperationException();
1.1348 + }
1.1349 + public void putAll(Map<? extends K, ? extends V> m) {
1.1350 + throw new UnsupportedOperationException();
1.1351 + }
1.1352 + public void clear() {
1.1353 + throw new UnsupportedOperationException();
1.1354 + }
1.1355 +
1.1356 + private transient Set<K> keySet = null;
1.1357 + private transient Set<Map.Entry<K,V>> entrySet = null;
1.1358 + private transient Collection<V> values = null;
1.1359 +
1.1360 + public Set<K> keySet() {
1.1361 + if (keySet==null)
1.1362 + keySet = unmodifiableSet(m.keySet());
1.1363 + return keySet;
1.1364 + }
1.1365 +
1.1366 + public Set<Map.Entry<K,V>> entrySet() {
1.1367 + if (entrySet==null)
1.1368 + entrySet = new UnmodifiableEntrySet<>(m.entrySet());
1.1369 + return entrySet;
1.1370 + }
1.1371 +
1.1372 + public Collection<V> values() {
1.1373 + if (values==null)
1.1374 + values = unmodifiableCollection(m.values());
1.1375 + return values;
1.1376 + }
1.1377 +
1.1378 + public boolean equals(Object o) {return o == this || m.equals(o);}
1.1379 + public int hashCode() {return m.hashCode();}
1.1380 + public String toString() {return m.toString();}
1.1381 +
1.1382 + /**
1.1383 + * We need this class in addition to UnmodifiableSet as
1.1384 + * Map.Entries themselves permit modification of the backing Map
1.1385 + * via their setValue operation. This class is subtle: there are
1.1386 + * many possible attacks that must be thwarted.
1.1387 + *
1.1388 + * @serial include
1.1389 + */
1.1390 + static class UnmodifiableEntrySet<K,V>
1.1391 + extends UnmodifiableSet<Map.Entry<K,V>> {
1.1392 + private static final long serialVersionUID = 7854390611657943733L;
1.1393 +
1.1394 + UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1.1395 + super((Set)s);
1.1396 + }
1.1397 + public Iterator<Map.Entry<K,V>> iterator() {
1.1398 + return new Iterator<Map.Entry<K,V>>() {
1.1399 + private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1.1400 +
1.1401 + public boolean hasNext() {
1.1402 + return i.hasNext();
1.1403 + }
1.1404 + public Map.Entry<K,V> next() {
1.1405 + return new UnmodifiableEntry<>(i.next());
1.1406 + }
1.1407 + public void remove() {
1.1408 + throw new UnsupportedOperationException();
1.1409 + }
1.1410 + };
1.1411 + }
1.1412 +
1.1413 + public Object[] toArray() {
1.1414 + Object[] a = c.toArray();
1.1415 + for (int i=0; i<a.length; i++)
1.1416 + a[i] = new UnmodifiableEntry<>((Map.Entry<K,V>)a[i]);
1.1417 + return a;
1.1418 + }
1.1419 +
1.1420 + public <T> T[] toArray(T[] a) {
1.1421 + // We don't pass a to c.toArray, to avoid window of
1.1422 + // vulnerability wherein an unscrupulous multithreaded client
1.1423 + // could get his hands on raw (unwrapped) Entries from c.
1.1424 + Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1.1425 +
1.1426 + for (int i=0; i<arr.length; i++)
1.1427 + arr[i] = new UnmodifiableEntry<>((Map.Entry<K,V>)arr[i]);
1.1428 +
1.1429 + if (arr.length > a.length)
1.1430 + return (T[])arr;
1.1431 +
1.1432 + System.arraycopy(arr, 0, a, 0, arr.length);
1.1433 + if (a.length > arr.length)
1.1434 + a[arr.length] = null;
1.1435 + return a;
1.1436 + }
1.1437 +
1.1438 + /**
1.1439 + * This method is overridden to protect the backing set against
1.1440 + * an object with a nefarious equals function that senses
1.1441 + * that the equality-candidate is Map.Entry and calls its
1.1442 + * setValue method.
1.1443 + */
1.1444 + public boolean contains(Object o) {
1.1445 + if (!(o instanceof Map.Entry))
1.1446 + return false;
1.1447 + return c.contains(
1.1448 + new UnmodifiableEntry<>((Map.Entry<?,?>) o));
1.1449 + }
1.1450 +
1.1451 + /**
1.1452 + * The next two methods are overridden to protect against
1.1453 + * an unscrupulous List whose contains(Object o) method senses
1.1454 + * when o is a Map.Entry, and calls o.setValue.
1.1455 + */
1.1456 + public boolean containsAll(Collection<?> coll) {
1.1457 + for (Object e : coll) {
1.1458 + if (!contains(e)) // Invokes safe contains() above
1.1459 + return false;
1.1460 + }
1.1461 + return true;
1.1462 + }
1.1463 + public boolean equals(Object o) {
1.1464 + if (o == this)
1.1465 + return true;
1.1466 +
1.1467 + if (!(o instanceof Set))
1.1468 + return false;
1.1469 + Set s = (Set) o;
1.1470 + if (s.size() != c.size())
1.1471 + return false;
1.1472 + return containsAll(s); // Invokes safe containsAll() above
1.1473 + }
1.1474 +
1.1475 + /**
1.1476 + * This "wrapper class" serves two purposes: it prevents
1.1477 + * the client from modifying the backing Map, by short-circuiting
1.1478 + * the setValue method, and it protects the backing Map against
1.1479 + * an ill-behaved Map.Entry that attempts to modify another
1.1480 + * Map Entry when asked to perform an equality check.
1.1481 + */
1.1482 + private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> {
1.1483 + private Map.Entry<? extends K, ? extends V> e;
1.1484 +
1.1485 + UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;}
1.1486 +
1.1487 + public K getKey() {return e.getKey();}
1.1488 + public V getValue() {return e.getValue();}
1.1489 + public V setValue(V value) {
1.1490 + throw new UnsupportedOperationException();
1.1491 + }
1.1492 + public int hashCode() {return e.hashCode();}
1.1493 + public boolean equals(Object o) {
1.1494 + if (!(o instanceof Map.Entry))
1.1495 + return false;
1.1496 + Map.Entry t = (Map.Entry)o;
1.1497 + return eq(e.getKey(), t.getKey()) &&
1.1498 + eq(e.getValue(), t.getValue());
1.1499 + }
1.1500 + public String toString() {return e.toString();}
1.1501 + }
1.1502 + }
1.1503 + }
1.1504 +
1.1505 + /**
1.1506 + * Returns an unmodifiable view of the specified sorted map. This method
1.1507 + * allows modules to provide users with "read-only" access to internal
1.1508 + * sorted maps. Query operations on the returned sorted map "read through"
1.1509 + * to the specified sorted map. Attempts to modify the returned
1.1510 + * sorted map, whether direct, via its collection views, or via its
1.1511 + * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1.1512 + * an <tt>UnsupportedOperationException</tt>.<p>
1.1513 + *
1.1514 + * The returned sorted map will be serializable if the specified sorted map
1.1515 + * is serializable.
1.1516 + *
1.1517 + * @param m the sorted map for which an unmodifiable view is to be
1.1518 + * returned.
1.1519 + * @return an unmodifiable view of the specified sorted map.
1.1520 + */
1.1521 + public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1.1522 + return new UnmodifiableSortedMap<>(m);
1.1523 + }
1.1524 +
1.1525 + /**
1.1526 + * @serial include
1.1527 + */
1.1528 + static class UnmodifiableSortedMap<K,V>
1.1529 + extends UnmodifiableMap<K,V>
1.1530 + implements SortedMap<K,V>, Serializable {
1.1531 + private static final long serialVersionUID = -8806743815996713206L;
1.1532 +
1.1533 + private final SortedMap<K, ? extends V> sm;
1.1534 +
1.1535 + UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;}
1.1536 +
1.1537 + public Comparator<? super K> comparator() {return sm.comparator();}
1.1538 +
1.1539 + public SortedMap<K,V> subMap(K fromKey, K toKey) {
1.1540 + return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey));
1.1541 + }
1.1542 + public SortedMap<K,V> headMap(K toKey) {
1.1543 + return new UnmodifiableSortedMap<>(sm.headMap(toKey));
1.1544 + }
1.1545 + public SortedMap<K,V> tailMap(K fromKey) {
1.1546 + return new UnmodifiableSortedMap<>(sm.tailMap(fromKey));
1.1547 + }
1.1548 +
1.1549 + public K firstKey() {return sm.firstKey();}
1.1550 + public K lastKey() {return sm.lastKey();}
1.1551 + }
1.1552 +
1.1553 +
1.1554 + // Synch Wrappers
1.1555 +
1.1556 + /**
1.1557 + * Returns a synchronized (thread-safe) collection backed by the specified
1.1558 + * collection. In order to guarantee serial access, it is critical that
1.1559 + * <strong>all</strong> access to the backing collection is accomplished
1.1560 + * through the returned collection.<p>
1.1561 + *
1.1562 + * It is imperative that the user manually synchronize on the returned
1.1563 + * collection when iterating over it:
1.1564 + * <pre>
1.1565 + * Collection c = Collections.synchronizedCollection(myCollection);
1.1566 + * ...
1.1567 + * synchronized (c) {
1.1568 + * Iterator i = c.iterator(); // Must be in the synchronized block
1.1569 + * while (i.hasNext())
1.1570 + * foo(i.next());
1.1571 + * }
1.1572 + * </pre>
1.1573 + * Failure to follow this advice may result in non-deterministic behavior.
1.1574 + *
1.1575 + * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1.1576 + * and <tt>equals</tt> operations through to the backing collection, but
1.1577 + * relies on <tt>Object</tt>'s equals and hashCode methods. This is
1.1578 + * necessary to preserve the contracts of these operations in the case
1.1579 + * that the backing collection is a set or a list.<p>
1.1580 + *
1.1581 + * The returned collection will be serializable if the specified collection
1.1582 + * is serializable.
1.1583 + *
1.1584 + * @param c the collection to be "wrapped" in a synchronized collection.
1.1585 + * @return a synchronized view of the specified collection.
1.1586 + */
1.1587 + public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
1.1588 + return new SynchronizedCollection<>(c);
1.1589 + }
1.1590 +
1.1591 + static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
1.1592 + return new SynchronizedCollection<>(c, mutex);
1.1593 + }
1.1594 +
1.1595 + /**
1.1596 + * @serial include
1.1597 + */
1.1598 + static class SynchronizedCollection<E> implements Collection<E>, Serializable {
1.1599 + private static final long serialVersionUID = 3053995032091335093L;
1.1600 +
1.1601 + final Collection<E> c; // Backing Collection
1.1602 + final Object mutex; // Object on which to synchronize
1.1603 +
1.1604 + SynchronizedCollection(Collection<E> c) {
1.1605 + if (c==null)
1.1606 + throw new NullPointerException();
1.1607 + this.c = c;
1.1608 + mutex = this;
1.1609 + }
1.1610 + SynchronizedCollection(Collection<E> c, Object mutex) {
1.1611 + this.c = c;
1.1612 + this.mutex = mutex;
1.1613 + }
1.1614 +
1.1615 + public int size() {
1.1616 + synchronized (mutex) {return c.size();}
1.1617 + }
1.1618 + public boolean isEmpty() {
1.1619 + synchronized (mutex) {return c.isEmpty();}
1.1620 + }
1.1621 + public boolean contains(Object o) {
1.1622 + synchronized (mutex) {return c.contains(o);}
1.1623 + }
1.1624 + public Object[] toArray() {
1.1625 + synchronized (mutex) {return c.toArray();}
1.1626 + }
1.1627 + public <T> T[] toArray(T[] a) {
1.1628 + synchronized (mutex) {return c.toArray(a);}
1.1629 + }
1.1630 +
1.1631 + public Iterator<E> iterator() {
1.1632 + return c.iterator(); // Must be manually synched by user!
1.1633 + }
1.1634 +
1.1635 + public boolean add(E e) {
1.1636 + synchronized (mutex) {return c.add(e);}
1.1637 + }
1.1638 + public boolean remove(Object o) {
1.1639 + synchronized (mutex) {return c.remove(o);}
1.1640 + }
1.1641 +
1.1642 + public boolean containsAll(Collection<?> coll) {
1.1643 + synchronized (mutex) {return c.containsAll(coll);}
1.1644 + }
1.1645 + public boolean addAll(Collection<? extends E> coll) {
1.1646 + synchronized (mutex) {return c.addAll(coll);}
1.1647 + }
1.1648 + public boolean removeAll(Collection<?> coll) {
1.1649 + synchronized (mutex) {return c.removeAll(coll);}
1.1650 + }
1.1651 + public boolean retainAll(Collection<?> coll) {
1.1652 + synchronized (mutex) {return c.retainAll(coll);}
1.1653 + }
1.1654 + public void clear() {
1.1655 + synchronized (mutex) {c.clear();}
1.1656 + }
1.1657 + public String toString() {
1.1658 + synchronized (mutex) {return c.toString();}
1.1659 + }
1.1660 + }
1.1661 +
1.1662 + /**
1.1663 + * Returns a synchronized (thread-safe) set backed by the specified
1.1664 + * set. In order to guarantee serial access, it is critical that
1.1665 + * <strong>all</strong> access to the backing set is accomplished
1.1666 + * through the returned set.<p>
1.1667 + *
1.1668 + * It is imperative that the user manually synchronize on the returned
1.1669 + * set when iterating over it:
1.1670 + * <pre>
1.1671 + * Set s = Collections.synchronizedSet(new HashSet());
1.1672 + * ...
1.1673 + * synchronized (s) {
1.1674 + * Iterator i = s.iterator(); // Must be in the synchronized block
1.1675 + * while (i.hasNext())
1.1676 + * foo(i.next());
1.1677 + * }
1.1678 + * </pre>
1.1679 + * Failure to follow this advice may result in non-deterministic behavior.
1.1680 + *
1.1681 + * <p>The returned set will be serializable if the specified set is
1.1682 + * serializable.
1.1683 + *
1.1684 + * @param s the set to be "wrapped" in a synchronized set.
1.1685 + * @return a synchronized view of the specified set.
1.1686 + */
1.1687 + public static <T> Set<T> synchronizedSet(Set<T> s) {
1.1688 + return new SynchronizedSet<>(s);
1.1689 + }
1.1690 +
1.1691 + static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1.1692 + return new SynchronizedSet<>(s, mutex);
1.1693 + }
1.1694 +
1.1695 + /**
1.1696 + * @serial include
1.1697 + */
1.1698 + static class SynchronizedSet<E>
1.1699 + extends SynchronizedCollection<E>
1.1700 + implements Set<E> {
1.1701 + private static final long serialVersionUID = 487447009682186044L;
1.1702 +
1.1703 + SynchronizedSet(Set<E> s) {
1.1704 + super(s);
1.1705 + }
1.1706 + SynchronizedSet(Set<E> s, Object mutex) {
1.1707 + super(s, mutex);
1.1708 + }
1.1709 +
1.1710 + public boolean equals(Object o) {
1.1711 + synchronized (mutex) {return c.equals(o);}
1.1712 + }
1.1713 + public int hashCode() {
1.1714 + synchronized (mutex) {return c.hashCode();}
1.1715 + }
1.1716 + }
1.1717 +
1.1718 + /**
1.1719 + * Returns a synchronized (thread-safe) sorted set backed by the specified
1.1720 + * sorted set. In order to guarantee serial access, it is critical that
1.1721 + * <strong>all</strong> access to the backing sorted set is accomplished
1.1722 + * through the returned sorted set (or its views).<p>
1.1723 + *
1.1724 + * It is imperative that the user manually synchronize on the returned
1.1725 + * sorted set when iterating over it or any of its <tt>subSet</tt>,
1.1726 + * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1.1727 + * <pre>
1.1728 + * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1.1729 + * ...
1.1730 + * synchronized (s) {
1.1731 + * Iterator i = s.iterator(); // Must be in the synchronized block
1.1732 + * while (i.hasNext())
1.1733 + * foo(i.next());
1.1734 + * }
1.1735 + * </pre>
1.1736 + * or:
1.1737 + * <pre>
1.1738 + * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1.1739 + * SortedSet s2 = s.headSet(foo);
1.1740 + * ...
1.1741 + * synchronized (s) { // Note: s, not s2!!!
1.1742 + * Iterator i = s2.iterator(); // Must be in the synchronized block
1.1743 + * while (i.hasNext())
1.1744 + * foo(i.next());
1.1745 + * }
1.1746 + * </pre>
1.1747 + * Failure to follow this advice may result in non-deterministic behavior.
1.1748 + *
1.1749 + * <p>The returned sorted set will be serializable if the specified
1.1750 + * sorted set is serializable.
1.1751 + *
1.1752 + * @param s the sorted set to be "wrapped" in a synchronized sorted set.
1.1753 + * @return a synchronized view of the specified sorted set.
1.1754 + */
1.1755 + public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1.1756 + return new SynchronizedSortedSet<>(s);
1.1757 + }
1.1758 +
1.1759 + /**
1.1760 + * @serial include
1.1761 + */
1.1762 + static class SynchronizedSortedSet<E>
1.1763 + extends SynchronizedSet<E>
1.1764 + implements SortedSet<E>
1.1765 + {
1.1766 + private static final long serialVersionUID = 8695801310862127406L;
1.1767 +
1.1768 + private final SortedSet<E> ss;
1.1769 +
1.1770 + SynchronizedSortedSet(SortedSet<E> s) {
1.1771 + super(s);
1.1772 + ss = s;
1.1773 + }
1.1774 + SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1.1775 + super(s, mutex);
1.1776 + ss = s;
1.1777 + }
1.1778 +
1.1779 + public Comparator<? super E> comparator() {
1.1780 + synchronized (mutex) {return ss.comparator();}
1.1781 + }
1.1782 +
1.1783 + public SortedSet<E> subSet(E fromElement, E toElement) {
1.1784 + synchronized (mutex) {
1.1785 + return new SynchronizedSortedSet<>(
1.1786 + ss.subSet(fromElement, toElement), mutex);
1.1787 + }
1.1788 + }
1.1789 + public SortedSet<E> headSet(E toElement) {
1.1790 + synchronized (mutex) {
1.1791 + return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex);
1.1792 + }
1.1793 + }
1.1794 + public SortedSet<E> tailSet(E fromElement) {
1.1795 + synchronized (mutex) {
1.1796 + return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex);
1.1797 + }
1.1798 + }
1.1799 +
1.1800 + public E first() {
1.1801 + synchronized (mutex) {return ss.first();}
1.1802 + }
1.1803 + public E last() {
1.1804 + synchronized (mutex) {return ss.last();}
1.1805 + }
1.1806 + }
1.1807 +
1.1808 + /**
1.1809 + * Returns a synchronized (thread-safe) list backed by the specified
1.1810 + * list. In order to guarantee serial access, it is critical that
1.1811 + * <strong>all</strong> access to the backing list is accomplished
1.1812 + * through the returned list.<p>
1.1813 + *
1.1814 + * It is imperative that the user manually synchronize on the returned
1.1815 + * list when iterating over it:
1.1816 + * <pre>
1.1817 + * List list = Collections.synchronizedList(new ArrayList());
1.1818 + * ...
1.1819 + * synchronized (list) {
1.1820 + * Iterator i = list.iterator(); // Must be in synchronized block
1.1821 + * while (i.hasNext())
1.1822 + * foo(i.next());
1.1823 + * }
1.1824 + * </pre>
1.1825 + * Failure to follow this advice may result in non-deterministic behavior.
1.1826 + *
1.1827 + * <p>The returned list will be serializable if the specified list is
1.1828 + * serializable.
1.1829 + *
1.1830 + * @param list the list to be "wrapped" in a synchronized list.
1.1831 + * @return a synchronized view of the specified list.
1.1832 + */
1.1833 + public static <T> List<T> synchronizedList(List<T> list) {
1.1834 + return (list instanceof RandomAccess ?
1.1835 + new SynchronizedRandomAccessList<>(list) :
1.1836 + new SynchronizedList<>(list));
1.1837 + }
1.1838 +
1.1839 + static <T> List<T> synchronizedList(List<T> list, Object mutex) {
1.1840 + return (list instanceof RandomAccess ?
1.1841 + new SynchronizedRandomAccessList<>(list, mutex) :
1.1842 + new SynchronizedList<>(list, mutex));
1.1843 + }
1.1844 +
1.1845 + /**
1.1846 + * @serial include
1.1847 + */
1.1848 + static class SynchronizedList<E>
1.1849 + extends SynchronizedCollection<E>
1.1850 + implements List<E> {
1.1851 + private static final long serialVersionUID = -7754090372962971524L;
1.1852 +
1.1853 + final List<E> list;
1.1854 +
1.1855 + SynchronizedList(List<E> list) {
1.1856 + super(list);
1.1857 + this.list = list;
1.1858 + }
1.1859 + SynchronizedList(List<E> list, Object mutex) {
1.1860 + super(list, mutex);
1.1861 + this.list = list;
1.1862 + }
1.1863 +
1.1864 + public boolean equals(Object o) {
1.1865 + synchronized (mutex) {return list.equals(o);}
1.1866 + }
1.1867 + public int hashCode() {
1.1868 + synchronized (mutex) {return list.hashCode();}
1.1869 + }
1.1870 +
1.1871 + public E get(int index) {
1.1872 + synchronized (mutex) {return list.get(index);}
1.1873 + }
1.1874 + public E set(int index, E element) {
1.1875 + synchronized (mutex) {return list.set(index, element);}
1.1876 + }
1.1877 + public void add(int index, E element) {
1.1878 + synchronized (mutex) {list.add(index, element);}
1.1879 + }
1.1880 + public E remove(int index) {
1.1881 + synchronized (mutex) {return list.remove(index);}
1.1882 + }
1.1883 +
1.1884 + public int indexOf(Object o) {
1.1885 + synchronized (mutex) {return list.indexOf(o);}
1.1886 + }
1.1887 + public int lastIndexOf(Object o) {
1.1888 + synchronized (mutex) {return list.lastIndexOf(o);}
1.1889 + }
1.1890 +
1.1891 + public boolean addAll(int index, Collection<? extends E> c) {
1.1892 + synchronized (mutex) {return list.addAll(index, c);}
1.1893 + }
1.1894 +
1.1895 + public ListIterator<E> listIterator() {
1.1896 + return list.listIterator(); // Must be manually synched by user
1.1897 + }
1.1898 +
1.1899 + public ListIterator<E> listIterator(int index) {
1.1900 + return list.listIterator(index); // Must be manually synched by user
1.1901 + }
1.1902 +
1.1903 + public List<E> subList(int fromIndex, int toIndex) {
1.1904 + synchronized (mutex) {
1.1905 + return new SynchronizedList<>(list.subList(fromIndex, toIndex),
1.1906 + mutex);
1.1907 + }
1.1908 + }
1.1909 +
1.1910 + /**
1.1911 + * SynchronizedRandomAccessList instances are serialized as
1.1912 + * SynchronizedList instances to allow them to be deserialized
1.1913 + * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
1.1914 + * This method inverts the transformation. As a beneficial
1.1915 + * side-effect, it also grafts the RandomAccess marker onto
1.1916 + * SynchronizedList instances that were serialized in pre-1.4 JREs.
1.1917 + *
1.1918 + * Note: Unfortunately, SynchronizedRandomAccessList instances
1.1919 + * serialized in 1.4.1 and deserialized in 1.4 will become
1.1920 + * SynchronizedList instances, as this method was missing in 1.4.
1.1921 + */
1.1922 + private Object readResolve() {
1.1923 + return (list instanceof RandomAccess
1.1924 + ? new SynchronizedRandomAccessList<>(list)
1.1925 + : this);
1.1926 + }
1.1927 + }
1.1928 +
1.1929 + /**
1.1930 + * @serial include
1.1931 + */
1.1932 + static class SynchronizedRandomAccessList<E>
1.1933 + extends SynchronizedList<E>
1.1934 + implements RandomAccess {
1.1935 +
1.1936 + SynchronizedRandomAccessList(List<E> list) {
1.1937 + super(list);
1.1938 + }
1.1939 +
1.1940 + SynchronizedRandomAccessList(List<E> list, Object mutex) {
1.1941 + super(list, mutex);
1.1942 + }
1.1943 +
1.1944 + public List<E> subList(int fromIndex, int toIndex) {
1.1945 + synchronized (mutex) {
1.1946 + return new SynchronizedRandomAccessList<>(
1.1947 + list.subList(fromIndex, toIndex), mutex);
1.1948 + }
1.1949 + }
1.1950 +
1.1951 + private static final long serialVersionUID = 1530674583602358482L;
1.1952 +
1.1953 + /**
1.1954 + * Allows instances to be deserialized in pre-1.4 JREs (which do
1.1955 + * not have SynchronizedRandomAccessList). SynchronizedList has
1.1956 + * a readResolve method that inverts this transformation upon
1.1957 + * deserialization.
1.1958 + */
1.1959 + private Object writeReplace() {
1.1960 + return new SynchronizedList<>(list);
1.1961 + }
1.1962 + }
1.1963 +
1.1964 + /**
1.1965 + * Returns a synchronized (thread-safe) map backed by the specified
1.1966 + * map. In order to guarantee serial access, it is critical that
1.1967 + * <strong>all</strong> access to the backing map is accomplished
1.1968 + * through the returned map.<p>
1.1969 + *
1.1970 + * It is imperative that the user manually synchronize on the returned
1.1971 + * map when iterating over any of its collection views:
1.1972 + * <pre>
1.1973 + * Map m = Collections.synchronizedMap(new HashMap());
1.1974 + * ...
1.1975 + * Set s = m.keySet(); // Needn't be in synchronized block
1.1976 + * ...
1.1977 + * synchronized (m) { // Synchronizing on m, not s!
1.1978 + * Iterator i = s.iterator(); // Must be in synchronized block
1.1979 + * while (i.hasNext())
1.1980 + * foo(i.next());
1.1981 + * }
1.1982 + * </pre>
1.1983 + * Failure to follow this advice may result in non-deterministic behavior.
1.1984 + *
1.1985 + * <p>The returned map will be serializable if the specified map is
1.1986 + * serializable.
1.1987 + *
1.1988 + * @param m the map to be "wrapped" in a synchronized map.
1.1989 + * @return a synchronized view of the specified map.
1.1990 + */
1.1991 + public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
1.1992 + return new SynchronizedMap<>(m);
1.1993 + }
1.1994 +
1.1995 + /**
1.1996 + * @serial include
1.1997 + */
1.1998 + private static class SynchronizedMap<K,V>
1.1999 + implements Map<K,V>, Serializable {
1.2000 + private static final long serialVersionUID = 1978198479659022715L;
1.2001 +
1.2002 + private final Map<K,V> m; // Backing Map
1.2003 + final Object mutex; // Object on which to synchronize
1.2004 +
1.2005 + SynchronizedMap(Map<K,V> m) {
1.2006 + if (m==null)
1.2007 + throw new NullPointerException();
1.2008 + this.m = m;
1.2009 + mutex = this;
1.2010 + }
1.2011 +
1.2012 + SynchronizedMap(Map<K,V> m, Object mutex) {
1.2013 + this.m = m;
1.2014 + this.mutex = mutex;
1.2015 + }
1.2016 +
1.2017 + public int size() {
1.2018 + synchronized (mutex) {return m.size();}
1.2019 + }
1.2020 + public boolean isEmpty() {
1.2021 + synchronized (mutex) {return m.isEmpty();}
1.2022 + }
1.2023 + public boolean containsKey(Object key) {
1.2024 + synchronized (mutex) {return m.containsKey(key);}
1.2025 + }
1.2026 + public boolean containsValue(Object value) {
1.2027 + synchronized (mutex) {return m.containsValue(value);}
1.2028 + }
1.2029 + public V get(Object key) {
1.2030 + synchronized (mutex) {return m.get(key);}
1.2031 + }
1.2032 +
1.2033 + public V put(K key, V value) {
1.2034 + synchronized (mutex) {return m.put(key, value);}
1.2035 + }
1.2036 + public V remove(Object key) {
1.2037 + synchronized (mutex) {return m.remove(key);}
1.2038 + }
1.2039 + public void putAll(Map<? extends K, ? extends V> map) {
1.2040 + synchronized (mutex) {m.putAll(map);}
1.2041 + }
1.2042 + public void clear() {
1.2043 + synchronized (mutex) {m.clear();}
1.2044 + }
1.2045 +
1.2046 + private transient Set<K> keySet = null;
1.2047 + private transient Set<Map.Entry<K,V>> entrySet = null;
1.2048 + private transient Collection<V> values = null;
1.2049 +
1.2050 + public Set<K> keySet() {
1.2051 + synchronized (mutex) {
1.2052 + if (keySet==null)
1.2053 + keySet = new SynchronizedSet<>(m.keySet(), mutex);
1.2054 + return keySet;
1.2055 + }
1.2056 + }
1.2057 +
1.2058 + public Set<Map.Entry<K,V>> entrySet() {
1.2059 + synchronized (mutex) {
1.2060 + if (entrySet==null)
1.2061 + entrySet = new SynchronizedSet<>(m.entrySet(), mutex);
1.2062 + return entrySet;
1.2063 + }
1.2064 + }
1.2065 +
1.2066 + public Collection<V> values() {
1.2067 + synchronized (mutex) {
1.2068 + if (values==null)
1.2069 + values = new SynchronizedCollection<>(m.values(), mutex);
1.2070 + return values;
1.2071 + }
1.2072 + }
1.2073 +
1.2074 + public boolean equals(Object o) {
1.2075 + synchronized (mutex) {return m.equals(o);}
1.2076 + }
1.2077 + public int hashCode() {
1.2078 + synchronized (mutex) {return m.hashCode();}
1.2079 + }
1.2080 + public String toString() {
1.2081 + synchronized (mutex) {return m.toString();}
1.2082 + }
1.2083 + }
1.2084 +
1.2085 + /**
1.2086 + * Returns a synchronized (thread-safe) sorted map backed by the specified
1.2087 + * sorted map. In order to guarantee serial access, it is critical that
1.2088 + * <strong>all</strong> access to the backing sorted map is accomplished
1.2089 + * through the returned sorted map (or its views).<p>
1.2090 + *
1.2091 + * It is imperative that the user manually synchronize on the returned
1.2092 + * sorted map when iterating over any of its collection views, or the
1.2093 + * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
1.2094 + * <tt>tailMap</tt> views.
1.2095 + * <pre>
1.2096 + * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
1.2097 + * ...
1.2098 + * Set s = m.keySet(); // Needn't be in synchronized block
1.2099 + * ...
1.2100 + * synchronized (m) { // Synchronizing on m, not s!
1.2101 + * Iterator i = s.iterator(); // Must be in synchronized block
1.2102 + * while (i.hasNext())
1.2103 + * foo(i.next());
1.2104 + * }
1.2105 + * </pre>
1.2106 + * or:
1.2107 + * <pre>
1.2108 + * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
1.2109 + * SortedMap m2 = m.subMap(foo, bar);
1.2110 + * ...
1.2111 + * Set s2 = m2.keySet(); // Needn't be in synchronized block
1.2112 + * ...
1.2113 + * synchronized (m) { // Synchronizing on m, not m2 or s2!
1.2114 + * Iterator i = s.iterator(); // Must be in synchronized block
1.2115 + * while (i.hasNext())
1.2116 + * foo(i.next());
1.2117 + * }
1.2118 + * </pre>
1.2119 + * Failure to follow this advice may result in non-deterministic behavior.
1.2120 + *
1.2121 + * <p>The returned sorted map will be serializable if the specified
1.2122 + * sorted map is serializable.
1.2123 + *
1.2124 + * @param m the sorted map to be "wrapped" in a synchronized sorted map.
1.2125 + * @return a synchronized view of the specified sorted map.
1.2126 + */
1.2127 + public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) {
1.2128 + return new SynchronizedSortedMap<>(m);
1.2129 + }
1.2130 +
1.2131 +
1.2132 + /**
1.2133 + * @serial include
1.2134 + */
1.2135 + static class SynchronizedSortedMap<K,V>
1.2136 + extends SynchronizedMap<K,V>
1.2137 + implements SortedMap<K,V>
1.2138 + {
1.2139 + private static final long serialVersionUID = -8798146769416483793L;
1.2140 +
1.2141 + private final SortedMap<K,V> sm;
1.2142 +
1.2143 + SynchronizedSortedMap(SortedMap<K,V> m) {
1.2144 + super(m);
1.2145 + sm = m;
1.2146 + }
1.2147 + SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) {
1.2148 + super(m, mutex);
1.2149 + sm = m;
1.2150 + }
1.2151 +
1.2152 + public Comparator<? super K> comparator() {
1.2153 + synchronized (mutex) {return sm.comparator();}
1.2154 + }
1.2155 +
1.2156 + public SortedMap<K,V> subMap(K fromKey, K toKey) {
1.2157 + synchronized (mutex) {
1.2158 + return new SynchronizedSortedMap<>(
1.2159 + sm.subMap(fromKey, toKey), mutex);
1.2160 + }
1.2161 + }
1.2162 + public SortedMap<K,V> headMap(K toKey) {
1.2163 + synchronized (mutex) {
1.2164 + return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex);
1.2165 + }
1.2166 + }
1.2167 + public SortedMap<K,V> tailMap(K fromKey) {
1.2168 + synchronized (mutex) {
1.2169 + return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex);
1.2170 + }
1.2171 + }
1.2172 +
1.2173 + public K firstKey() {
1.2174 + synchronized (mutex) {return sm.firstKey();}
1.2175 + }
1.2176 + public K lastKey() {
1.2177 + synchronized (mutex) {return sm.lastKey();}
1.2178 + }
1.2179 + }
1.2180 +
1.2181 + // Dynamically typesafe collection wrappers
1.2182 +
1.2183 + /**
1.2184 + * Returns a dynamically typesafe view of the specified collection.
1.2185 + * Any attempt to insert an element of the wrong type will result in an
1.2186 + * immediate {@link ClassCastException}. Assuming a collection
1.2187 + * contains no incorrectly typed elements prior to the time a
1.2188 + * dynamically typesafe view is generated, and that all subsequent
1.2189 + * access to the collection takes place through the view, it is
1.2190 + * <i>guaranteed</i> that the collection cannot contain an incorrectly
1.2191 + * typed element.
1.2192 + *
1.2193 + * <p>The generics mechanism in the language provides compile-time
1.2194 + * (static) type checking, but it is possible to defeat this mechanism
1.2195 + * with unchecked casts. Usually this is not a problem, as the compiler
1.2196 + * issues warnings on all such unchecked operations. There are, however,
1.2197 + * times when static type checking alone is not sufficient. For example,
1.2198 + * suppose a collection is passed to a third-party library and it is
1.2199 + * imperative that the library code not corrupt the collection by
1.2200 + * inserting an element of the wrong type.
1.2201 + *
1.2202 + * <p>Another use of dynamically typesafe views is debugging. Suppose a
1.2203 + * program fails with a {@code ClassCastException}, indicating that an
1.2204 + * incorrectly typed element was put into a parameterized collection.
1.2205 + * Unfortunately, the exception can occur at any time after the erroneous
1.2206 + * element is inserted, so it typically provides little or no information
1.2207 + * as to the real source of the problem. If the problem is reproducible,
1.2208 + * one can quickly determine its source by temporarily modifying the
1.2209 + * program to wrap the collection with a dynamically typesafe view.
1.2210 + * For example, this declaration:
1.2211 + * <pre> {@code
1.2212 + * Collection<String> c = new HashSet<String>();
1.2213 + * }</pre>
1.2214 + * may be replaced temporarily by this one:
1.2215 + * <pre> {@code
1.2216 + * Collection<String> c = Collections.checkedCollection(
1.2217 + * new HashSet<String>(), String.class);
1.2218 + * }</pre>
1.2219 + * Running the program again will cause it to fail at the point where
1.2220 + * an incorrectly typed element is inserted into the collection, clearly
1.2221 + * identifying the source of the problem. Once the problem is fixed, the
1.2222 + * modified declaration may be reverted back to the original.
1.2223 + *
1.2224 + * <p>The returned collection does <i>not</i> pass the hashCode and equals
1.2225 + * operations through to the backing collection, but relies on
1.2226 + * {@code Object}'s {@code equals} and {@code hashCode} methods. This
1.2227 + * is necessary to preserve the contracts of these operations in the case
1.2228 + * that the backing collection is a set or a list.
1.2229 + *
1.2230 + * <p>The returned collection will be serializable if the specified
1.2231 + * collection is serializable.
1.2232 + *
1.2233 + * <p>Since {@code null} is considered to be a value of any reference
1.2234 + * type, the returned collection permits insertion of null elements
1.2235 + * whenever the backing collection does.
1.2236 + *
1.2237 + * @param c the collection for which a dynamically typesafe view is to be
1.2238 + * returned
1.2239 + * @param type the type of element that {@code c} is permitted to hold
1.2240 + * @return a dynamically typesafe view of the specified collection
1.2241 + * @since 1.5
1.2242 + */
1.2243 + public static <E> Collection<E> checkedCollection(Collection<E> c,
1.2244 + Class<E> type) {
1.2245 + return new CheckedCollection<>(c, type);
1.2246 + }
1.2247 +
1.2248 + @SuppressWarnings("unchecked")
1.2249 + static <T> T[] zeroLengthArray(Class<T> type) {
1.2250 + return (T[]) Array.newInstance(type, 0);
1.2251 + }
1.2252 +
1.2253 + /**
1.2254 + * @serial include
1.2255 + */
1.2256 + static class CheckedCollection<E> implements Collection<E>, Serializable {
1.2257 + private static final long serialVersionUID = 1578914078182001775L;
1.2258 +
1.2259 + final Collection<E> c;
1.2260 + final Class<E> type;
1.2261 +
1.2262 + void typeCheck(Object o) {
1.2263 + if (o != null && !type.isInstance(o))
1.2264 + throw new ClassCastException(badElementMsg(o));
1.2265 + }
1.2266 +
1.2267 + private String badElementMsg(Object o) {
1.2268 + return "Attempt to insert " + o.getClass() +
1.2269 + " element into collection with element type " + type;
1.2270 + }
1.2271 +
1.2272 + CheckedCollection(Collection<E> c, Class<E> type) {
1.2273 + if (c==null || type == null)
1.2274 + throw new NullPointerException();
1.2275 + this.c = c;
1.2276 + this.type = type;
1.2277 + }
1.2278 +
1.2279 + public int size() { return c.size(); }
1.2280 + public boolean isEmpty() { return c.isEmpty(); }
1.2281 + public boolean contains(Object o) { return c.contains(o); }
1.2282 + public Object[] toArray() { return c.toArray(); }
1.2283 + public <T> T[] toArray(T[] a) { return c.toArray(a); }
1.2284 + public String toString() { return c.toString(); }
1.2285 + public boolean remove(Object o) { return c.remove(o); }
1.2286 + public void clear() { c.clear(); }
1.2287 +
1.2288 + public boolean containsAll(Collection<?> coll) {
1.2289 + return c.containsAll(coll);
1.2290 + }
1.2291 + public boolean removeAll(Collection<?> coll) {
1.2292 + return c.removeAll(coll);
1.2293 + }
1.2294 + public boolean retainAll(Collection<?> coll) {
1.2295 + return c.retainAll(coll);
1.2296 + }
1.2297 +
1.2298 + public Iterator<E> iterator() {
1.2299 + final Iterator<E> it = c.iterator();
1.2300 + return new Iterator<E>() {
1.2301 + public boolean hasNext() { return it.hasNext(); }
1.2302 + public E next() { return it.next(); }
1.2303 + public void remove() { it.remove(); }};
1.2304 + }
1.2305 +
1.2306 + public boolean add(E e) {
1.2307 + typeCheck(e);
1.2308 + return c.add(e);
1.2309 + }
1.2310 +
1.2311 + private E[] zeroLengthElementArray = null; // Lazily initialized
1.2312 +
1.2313 + private E[] zeroLengthElementArray() {
1.2314 + return zeroLengthElementArray != null ? zeroLengthElementArray :
1.2315 + (zeroLengthElementArray = zeroLengthArray(type));
1.2316 + }
1.2317 +
1.2318 + @SuppressWarnings("unchecked")
1.2319 + Collection<E> checkedCopyOf(Collection<? extends E> coll) {
1.2320 + Object[] a = null;
1.2321 + try {
1.2322 + E[] z = zeroLengthElementArray();
1.2323 + a = coll.toArray(z);
1.2324 + // Defend against coll violating the toArray contract
1.2325 + if (a.getClass() != z.getClass())
1.2326 + a = Arrays.copyOf(a, a.length, z.getClass());
1.2327 + } catch (ArrayStoreException ignore) {
1.2328 + // To get better and consistent diagnostics,
1.2329 + // we call typeCheck explicitly on each element.
1.2330 + // We call clone() to defend against coll retaining a
1.2331 + // reference to the returned array and storing a bad
1.2332 + // element into it after it has been type checked.
1.2333 + a = coll.toArray().clone();
1.2334 + for (Object o : a)
1.2335 + typeCheck(o);
1.2336 + }
1.2337 + // A slight abuse of the type system, but safe here.
1.2338 + return (Collection<E>) Arrays.asList(a);
1.2339 + }
1.2340 +
1.2341 + public boolean addAll(Collection<? extends E> coll) {
1.2342 + // Doing things this way insulates us from concurrent changes
1.2343 + // in the contents of coll and provides all-or-nothing
1.2344 + // semantics (which we wouldn't get if we type-checked each
1.2345 + // element as we added it)
1.2346 + return c.addAll(checkedCopyOf(coll));
1.2347 + }
1.2348 + }
1.2349 +
1.2350 + /**
1.2351 + * Returns a dynamically typesafe view of the specified set.
1.2352 + * Any attempt to insert an element of the wrong type will result in
1.2353 + * an immediate {@link ClassCastException}. Assuming a set contains
1.2354 + * no incorrectly typed elements prior to the time a dynamically typesafe
1.2355 + * view is generated, and that all subsequent access to the set
1.2356 + * takes place through the view, it is <i>guaranteed</i> that the
1.2357 + * set cannot contain an incorrectly typed element.
1.2358 + *
1.2359 + * <p>A discussion of the use of dynamically typesafe views may be
1.2360 + * found in the documentation for the {@link #checkedCollection
1.2361 + * checkedCollection} method.
1.2362 + *
1.2363 + * <p>The returned set will be serializable if the specified set is
1.2364 + * serializable.
1.2365 + *
1.2366 + * <p>Since {@code null} is considered to be a value of any reference
1.2367 + * type, the returned set permits insertion of null elements whenever
1.2368 + * the backing set does.
1.2369 + *
1.2370 + * @param s the set for which a dynamically typesafe view is to be
1.2371 + * returned
1.2372 + * @param type the type of element that {@code s} is permitted to hold
1.2373 + * @return a dynamically typesafe view of the specified set
1.2374 + * @since 1.5
1.2375 + */
1.2376 + public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
1.2377 + return new CheckedSet<>(s, type);
1.2378 + }
1.2379 +
1.2380 + /**
1.2381 + * @serial include
1.2382 + */
1.2383 + static class CheckedSet<E> extends CheckedCollection<E>
1.2384 + implements Set<E>, Serializable
1.2385 + {
1.2386 + private static final long serialVersionUID = 4694047833775013803L;
1.2387 +
1.2388 + CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
1.2389 +
1.2390 + public boolean equals(Object o) { return o == this || c.equals(o); }
1.2391 + public int hashCode() { return c.hashCode(); }
1.2392 + }
1.2393 +
1.2394 + /**
1.2395 + * Returns a dynamically typesafe view of the specified sorted set.
1.2396 + * Any attempt to insert an element of the wrong type will result in an
1.2397 + * immediate {@link ClassCastException}. Assuming a sorted set
1.2398 + * contains no incorrectly typed elements prior to the time a
1.2399 + * dynamically typesafe view is generated, and that all subsequent
1.2400 + * access to the sorted set takes place through the view, it is
1.2401 + * <i>guaranteed</i> that the sorted set cannot contain an incorrectly
1.2402 + * typed element.
1.2403 + *
1.2404 + * <p>A discussion of the use of dynamically typesafe views may be
1.2405 + * found in the documentation for the {@link #checkedCollection
1.2406 + * checkedCollection} method.
1.2407 + *
1.2408 + * <p>The returned sorted set will be serializable if the specified sorted
1.2409 + * set is serializable.
1.2410 + *
1.2411 + * <p>Since {@code null} is considered to be a value of any reference
1.2412 + * type, the returned sorted set permits insertion of null elements
1.2413 + * whenever the backing sorted set does.
1.2414 + *
1.2415 + * @param s the sorted set for which a dynamically typesafe view is to be
1.2416 + * returned
1.2417 + * @param type the type of element that {@code s} is permitted to hold
1.2418 + * @return a dynamically typesafe view of the specified sorted set
1.2419 + * @since 1.5
1.2420 + */
1.2421 + public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
1.2422 + Class<E> type) {
1.2423 + return new CheckedSortedSet<>(s, type);
1.2424 + }
1.2425 +
1.2426 + /**
1.2427 + * @serial include
1.2428 + */
1.2429 + static class CheckedSortedSet<E> extends CheckedSet<E>
1.2430 + implements SortedSet<E>, Serializable
1.2431 + {
1.2432 + private static final long serialVersionUID = 1599911165492914959L;
1.2433 + private final SortedSet<E> ss;
1.2434 +
1.2435 + CheckedSortedSet(SortedSet<E> s, Class<E> type) {
1.2436 + super(s, type);
1.2437 + ss = s;
1.2438 + }
1.2439 +
1.2440 + public Comparator<? super E> comparator() { return ss.comparator(); }
1.2441 + public E first() { return ss.first(); }
1.2442 + public E last() { return ss.last(); }
1.2443 +
1.2444 + public SortedSet<E> subSet(E fromElement, E toElement) {
1.2445 + return checkedSortedSet(ss.subSet(fromElement,toElement), type);
1.2446 + }
1.2447 + public SortedSet<E> headSet(E toElement) {
1.2448 + return checkedSortedSet(ss.headSet(toElement), type);
1.2449 + }
1.2450 + public SortedSet<E> tailSet(E fromElement) {
1.2451 + return checkedSortedSet(ss.tailSet(fromElement), type);
1.2452 + }
1.2453 + }
1.2454 +
1.2455 + /**
1.2456 + * Returns a dynamically typesafe view of the specified list.
1.2457 + * Any attempt to insert an element of the wrong type will result in
1.2458 + * an immediate {@link ClassCastException}. Assuming a list contains
1.2459 + * no incorrectly typed elements prior to the time a dynamically typesafe
1.2460 + * view is generated, and that all subsequent access to the list
1.2461 + * takes place through the view, it is <i>guaranteed</i> that the
1.2462 + * list cannot contain an incorrectly typed element.
1.2463 + *
1.2464 + * <p>A discussion of the use of dynamically typesafe views may be
1.2465 + * found in the documentation for the {@link #checkedCollection
1.2466 + * checkedCollection} method.
1.2467 + *
1.2468 + * <p>The returned list will be serializable if the specified list
1.2469 + * is serializable.
1.2470 + *
1.2471 + * <p>Since {@code null} is considered to be a value of any reference
1.2472 + * type, the returned list permits insertion of null elements whenever
1.2473 + * the backing list does.
1.2474 + *
1.2475 + * @param list the list for which a dynamically typesafe view is to be
1.2476 + * returned
1.2477 + * @param type the type of element that {@code list} is permitted to hold
1.2478 + * @return a dynamically typesafe view of the specified list
1.2479 + * @since 1.5
1.2480 + */
1.2481 + public static <E> List<E> checkedList(List<E> list, Class<E> type) {
1.2482 + return (list instanceof RandomAccess ?
1.2483 + new CheckedRandomAccessList<>(list, type) :
1.2484 + new CheckedList<>(list, type));
1.2485 + }
1.2486 +
1.2487 + /**
1.2488 + * @serial include
1.2489 + */
1.2490 + static class CheckedList<E>
1.2491 + extends CheckedCollection<E>
1.2492 + implements List<E>
1.2493 + {
1.2494 + private static final long serialVersionUID = 65247728283967356L;
1.2495 + final List<E> list;
1.2496 +
1.2497 + CheckedList(List<E> list, Class<E> type) {
1.2498 + super(list, type);
1.2499 + this.list = list;
1.2500 + }
1.2501 +
1.2502 + public boolean equals(Object o) { return o == this || list.equals(o); }
1.2503 + public int hashCode() { return list.hashCode(); }
1.2504 + public E get(int index) { return list.get(index); }
1.2505 + public E remove(int index) { return list.remove(index); }
1.2506 + public int indexOf(Object o) { return list.indexOf(o); }
1.2507 + public int lastIndexOf(Object o) { return list.lastIndexOf(o); }
1.2508 +
1.2509 + public E set(int index, E element) {
1.2510 + typeCheck(element);
1.2511 + return list.set(index, element);
1.2512 + }
1.2513 +
1.2514 + public void add(int index, E element) {
1.2515 + typeCheck(element);
1.2516 + list.add(index, element);
1.2517 + }
1.2518 +
1.2519 + public boolean addAll(int index, Collection<? extends E> c) {
1.2520 + return list.addAll(index, checkedCopyOf(c));
1.2521 + }
1.2522 + public ListIterator<E> listIterator() { return listIterator(0); }
1.2523 +
1.2524 + public ListIterator<E> listIterator(final int index) {
1.2525 + final ListIterator<E> i = list.listIterator(index);
1.2526 +
1.2527 + return new ListIterator<E>() {
1.2528 + public boolean hasNext() { return i.hasNext(); }
1.2529 + public E next() { return i.next(); }
1.2530 + public boolean hasPrevious() { return i.hasPrevious(); }
1.2531 + public E previous() { return i.previous(); }
1.2532 + public int nextIndex() { return i.nextIndex(); }
1.2533 + public int previousIndex() { return i.previousIndex(); }
1.2534 + public void remove() { i.remove(); }
1.2535 +
1.2536 + public void set(E e) {
1.2537 + typeCheck(e);
1.2538 + i.set(e);
1.2539 + }
1.2540 +
1.2541 + public void add(E e) {
1.2542 + typeCheck(e);
1.2543 + i.add(e);
1.2544 + }
1.2545 + };
1.2546 + }
1.2547 +
1.2548 + public List<E> subList(int fromIndex, int toIndex) {
1.2549 + return new CheckedList<>(list.subList(fromIndex, toIndex), type);
1.2550 + }
1.2551 + }
1.2552 +
1.2553 + /**
1.2554 + * @serial include
1.2555 + */
1.2556 + static class CheckedRandomAccessList<E> extends CheckedList<E>
1.2557 + implements RandomAccess
1.2558 + {
1.2559 + private static final long serialVersionUID = 1638200125423088369L;
1.2560 +
1.2561 + CheckedRandomAccessList(List<E> list, Class<E> type) {
1.2562 + super(list, type);
1.2563 + }
1.2564 +
1.2565 + public List<E> subList(int fromIndex, int toIndex) {
1.2566 + return new CheckedRandomAccessList<>(
1.2567 + list.subList(fromIndex, toIndex), type);
1.2568 + }
1.2569 + }
1.2570 +
1.2571 + /**
1.2572 + * Returns a dynamically typesafe view of the specified map.
1.2573 + * Any attempt to insert a mapping whose key or value have the wrong
1.2574 + * type will result in an immediate {@link ClassCastException}.
1.2575 + * Similarly, any attempt to modify the value currently associated with
1.2576 + * a key will result in an immediate {@link ClassCastException},
1.2577 + * whether the modification is attempted directly through the map
1.2578 + * itself, or through a {@link Map.Entry} instance obtained from the
1.2579 + * map's {@link Map#entrySet() entry set} view.
1.2580 + *
1.2581 + * <p>Assuming a map contains no incorrectly typed keys or values
1.2582 + * prior to the time a dynamically typesafe view is generated, and
1.2583 + * that all subsequent access to the map takes place through the view
1.2584 + * (or one of its collection views), it is <i>guaranteed</i> that the
1.2585 + * map cannot contain an incorrectly typed key or value.
1.2586 + *
1.2587 + * <p>A discussion of the use of dynamically typesafe views may be
1.2588 + * found in the documentation for the {@link #checkedCollection
1.2589 + * checkedCollection} method.
1.2590 + *
1.2591 + * <p>The returned map will be serializable if the specified map is
1.2592 + * serializable.
1.2593 + *
1.2594 + * <p>Since {@code null} is considered to be a value of any reference
1.2595 + * type, the returned map permits insertion of null keys or values
1.2596 + * whenever the backing map does.
1.2597 + *
1.2598 + * @param m the map for which a dynamically typesafe view is to be
1.2599 + * returned
1.2600 + * @param keyType the type of key that {@code m} is permitted to hold
1.2601 + * @param valueType the type of value that {@code m} is permitted to hold
1.2602 + * @return a dynamically typesafe view of the specified map
1.2603 + * @since 1.5
1.2604 + */
1.2605 + public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
1.2606 + Class<K> keyType,
1.2607 + Class<V> valueType) {
1.2608 + return new CheckedMap<>(m, keyType, valueType);
1.2609 + }
1.2610 +
1.2611 +
1.2612 + /**
1.2613 + * @serial include
1.2614 + */
1.2615 + private static class CheckedMap<K,V>
1.2616 + implements Map<K,V>, Serializable
1.2617 + {
1.2618 + private static final long serialVersionUID = 5742860141034234728L;
1.2619 +
1.2620 + private final Map<K, V> m;
1.2621 + final Class<K> keyType;
1.2622 + final Class<V> valueType;
1.2623 +
1.2624 + private void typeCheck(Object key, Object value) {
1.2625 + if (key != null && !keyType.isInstance(key))
1.2626 + throw new ClassCastException(badKeyMsg(key));
1.2627 +
1.2628 + if (value != null && !valueType.isInstance(value))
1.2629 + throw new ClassCastException(badValueMsg(value));
1.2630 + }
1.2631 +
1.2632 + private String badKeyMsg(Object key) {
1.2633 + return "Attempt to insert " + key.getClass() +
1.2634 + " key into map with key type " + keyType;
1.2635 + }
1.2636 +
1.2637 + private String badValueMsg(Object value) {
1.2638 + return "Attempt to insert " + value.getClass() +
1.2639 + " value into map with value type " + valueType;
1.2640 + }
1.2641 +
1.2642 + CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
1.2643 + if (m == null || keyType == null || valueType == null)
1.2644 + throw new NullPointerException();
1.2645 + this.m = m;
1.2646 + this.keyType = keyType;
1.2647 + this.valueType = valueType;
1.2648 + }
1.2649 +
1.2650 + public int size() { return m.size(); }
1.2651 + public boolean isEmpty() { return m.isEmpty(); }
1.2652 + public boolean containsKey(Object key) { return m.containsKey(key); }
1.2653 + public boolean containsValue(Object v) { return m.containsValue(v); }
1.2654 + public V get(Object key) { return m.get(key); }
1.2655 + public V remove(Object key) { return m.remove(key); }
1.2656 + public void clear() { m.clear(); }
1.2657 + public Set<K> keySet() { return m.keySet(); }
1.2658 + public Collection<V> values() { return m.values(); }
1.2659 + public boolean equals(Object o) { return o == this || m.equals(o); }
1.2660 + public int hashCode() { return m.hashCode(); }
1.2661 + public String toString() { return m.toString(); }
1.2662 +
1.2663 + public V put(K key, V value) {
1.2664 + typeCheck(key, value);
1.2665 + return m.put(key, value);
1.2666 + }
1.2667 +
1.2668 + @SuppressWarnings("unchecked")
1.2669 + public void putAll(Map<? extends K, ? extends V> t) {
1.2670 + // Satisfy the following goals:
1.2671 + // - good diagnostics in case of type mismatch
1.2672 + // - all-or-nothing semantics
1.2673 + // - protection from malicious t
1.2674 + // - correct behavior if t is a concurrent map
1.2675 + Object[] entries = t.entrySet().toArray();
1.2676 + List<Map.Entry<K,V>> checked = new ArrayList<>(entries.length);
1.2677 + for (Object o : entries) {
1.2678 + Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1.2679 + Object k = e.getKey();
1.2680 + Object v = e.getValue();
1.2681 + typeCheck(k, v);
1.2682 + checked.add(
1.2683 + new AbstractMap.SimpleImmutableEntry<>((K) k, (V) v));
1.2684 + }
1.2685 + for (Map.Entry<K,V> e : checked)
1.2686 + m.put(e.getKey(), e.getValue());
1.2687 + }
1.2688 +
1.2689 + private transient Set<Map.Entry<K,V>> entrySet = null;
1.2690 +
1.2691 + public Set<Map.Entry<K,V>> entrySet() {
1.2692 + if (entrySet==null)
1.2693 + entrySet = new CheckedEntrySet<>(m.entrySet(), valueType);
1.2694 + return entrySet;
1.2695 + }
1.2696 +
1.2697 + /**
1.2698 + * We need this class in addition to CheckedSet as Map.Entry permits
1.2699 + * modification of the backing Map via the setValue operation. This
1.2700 + * class is subtle: there are many possible attacks that must be
1.2701 + * thwarted.
1.2702 + *
1.2703 + * @serial exclude
1.2704 + */
1.2705 + static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> {
1.2706 + private final Set<Map.Entry<K,V>> s;
1.2707 + private final Class<V> valueType;
1.2708 +
1.2709 + CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
1.2710 + this.s = s;
1.2711 + this.valueType = valueType;
1.2712 + }
1.2713 +
1.2714 + public int size() { return s.size(); }
1.2715 + public boolean isEmpty() { return s.isEmpty(); }
1.2716 + public String toString() { return s.toString(); }
1.2717 + public int hashCode() { return s.hashCode(); }
1.2718 + public void clear() { s.clear(); }
1.2719 +
1.2720 + public boolean add(Map.Entry<K, V> e) {
1.2721 + throw new UnsupportedOperationException();
1.2722 + }
1.2723 + public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
1.2724 + throw new UnsupportedOperationException();
1.2725 + }
1.2726 +
1.2727 + public Iterator<Map.Entry<K,V>> iterator() {
1.2728 + final Iterator<Map.Entry<K, V>> i = s.iterator();
1.2729 + final Class<V> valueType = this.valueType;
1.2730 +
1.2731 + return new Iterator<Map.Entry<K,V>>() {
1.2732 + public boolean hasNext() { return i.hasNext(); }
1.2733 + public void remove() { i.remove(); }
1.2734 +
1.2735 + public Map.Entry<K,V> next() {
1.2736 + return checkedEntry(i.next(), valueType);
1.2737 + }
1.2738 + };
1.2739 + }
1.2740 +
1.2741 + @SuppressWarnings("unchecked")
1.2742 + public Object[] toArray() {
1.2743 + Object[] source = s.toArray();
1.2744 +
1.2745 + /*
1.2746 + * Ensure that we don't get an ArrayStoreException even if
1.2747 + * s.toArray returns an array of something other than Object
1.2748 + */
1.2749 + Object[] dest = (CheckedEntry.class.isInstance(
1.2750 + source.getClass().getComponentType()) ? source :
1.2751 + new Object[source.length]);
1.2752 +
1.2753 + for (int i = 0; i < source.length; i++)
1.2754 + dest[i] = checkedEntry((Map.Entry<K,V>)source[i],
1.2755 + valueType);
1.2756 + return dest;
1.2757 + }
1.2758 +
1.2759 + @SuppressWarnings("unchecked")
1.2760 + public <T> T[] toArray(T[] a) {
1.2761 + // We don't pass a to s.toArray, to avoid window of
1.2762 + // vulnerability wherein an unscrupulous multithreaded client
1.2763 + // could get his hands on raw (unwrapped) Entries from s.
1.2764 + T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
1.2765 +
1.2766 + for (int i=0; i<arr.length; i++)
1.2767 + arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i],
1.2768 + valueType);
1.2769 + if (arr.length > a.length)
1.2770 + return arr;
1.2771 +
1.2772 + System.arraycopy(arr, 0, a, 0, arr.length);
1.2773 + if (a.length > arr.length)
1.2774 + a[arr.length] = null;
1.2775 + return a;
1.2776 + }
1.2777 +
1.2778 + /**
1.2779 + * This method is overridden to protect the backing set against
1.2780 + * an object with a nefarious equals function that senses
1.2781 + * that the equality-candidate is Map.Entry and calls its
1.2782 + * setValue method.
1.2783 + */
1.2784 + public boolean contains(Object o) {
1.2785 + if (!(o instanceof Map.Entry))
1.2786 + return false;
1.2787 + Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1.2788 + return s.contains(
1.2789 + (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType));
1.2790 + }
1.2791 +
1.2792 + /**
1.2793 + * The bulk collection methods are overridden to protect
1.2794 + * against an unscrupulous collection whose contains(Object o)
1.2795 + * method senses when o is a Map.Entry, and calls o.setValue.
1.2796 + */
1.2797 + public boolean containsAll(Collection<?> c) {
1.2798 + for (Object o : c)
1.2799 + if (!contains(o)) // Invokes safe contains() above
1.2800 + return false;
1.2801 + return true;
1.2802 + }
1.2803 +
1.2804 + public boolean remove(Object o) {
1.2805 + if (!(o instanceof Map.Entry))
1.2806 + return false;
1.2807 + return s.remove(new AbstractMap.SimpleImmutableEntry
1.2808 + <>((Map.Entry<?,?>)o));
1.2809 + }
1.2810 +
1.2811 + public boolean removeAll(Collection<?> c) {
1.2812 + return batchRemove(c, false);
1.2813 + }
1.2814 + public boolean retainAll(Collection<?> c) {
1.2815 + return batchRemove(c, true);
1.2816 + }
1.2817 + private boolean batchRemove(Collection<?> c, boolean complement) {
1.2818 + boolean modified = false;
1.2819 + Iterator<Map.Entry<K,V>> it = iterator();
1.2820 + while (it.hasNext()) {
1.2821 + if (c.contains(it.next()) != complement) {
1.2822 + it.remove();
1.2823 + modified = true;
1.2824 + }
1.2825 + }
1.2826 + return modified;
1.2827 + }
1.2828 +
1.2829 + public boolean equals(Object o) {
1.2830 + if (o == this)
1.2831 + return true;
1.2832 + if (!(o instanceof Set))
1.2833 + return false;
1.2834 + Set<?> that = (Set<?>) o;
1.2835 + return that.size() == s.size()
1.2836 + && containsAll(that); // Invokes safe containsAll() above
1.2837 + }
1.2838 +
1.2839 + static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e,
1.2840 + Class<T> valueType) {
1.2841 + return new CheckedEntry<>(e, valueType);
1.2842 + }
1.2843 +
1.2844 + /**
1.2845 + * This "wrapper class" serves two purposes: it prevents
1.2846 + * the client from modifying the backing Map, by short-circuiting
1.2847 + * the setValue method, and it protects the backing Map against
1.2848 + * an ill-behaved Map.Entry that attempts to modify another
1.2849 + * Map.Entry when asked to perform an equality check.
1.2850 + */
1.2851 + private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> {
1.2852 + private final Map.Entry<K, V> e;
1.2853 + private final Class<T> valueType;
1.2854 +
1.2855 + CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) {
1.2856 + this.e = e;
1.2857 + this.valueType = valueType;
1.2858 + }
1.2859 +
1.2860 + public K getKey() { return e.getKey(); }
1.2861 + public V getValue() { return e.getValue(); }
1.2862 + public int hashCode() { return e.hashCode(); }
1.2863 + public String toString() { return e.toString(); }
1.2864 +
1.2865 + public V setValue(V value) {
1.2866 + if (value != null && !valueType.isInstance(value))
1.2867 + throw new ClassCastException(badValueMsg(value));
1.2868 + return e.setValue(value);
1.2869 + }
1.2870 +
1.2871 + private String badValueMsg(Object value) {
1.2872 + return "Attempt to insert " + value.getClass() +
1.2873 + " value into map with value type " + valueType;
1.2874 + }
1.2875 +
1.2876 + public boolean equals(Object o) {
1.2877 + if (o == this)
1.2878 + return true;
1.2879 + if (!(o instanceof Map.Entry))
1.2880 + return false;
1.2881 + return e.equals(new AbstractMap.SimpleImmutableEntry
1.2882 + <>((Map.Entry<?,?>)o));
1.2883 + }
1.2884 + }
1.2885 + }
1.2886 + }
1.2887 +
1.2888 + /**
1.2889 + * Returns a dynamically typesafe view of the specified sorted map.
1.2890 + * Any attempt to insert a mapping whose key or value have the wrong
1.2891 + * type will result in an immediate {@link ClassCastException}.
1.2892 + * Similarly, any attempt to modify the value currently associated with
1.2893 + * a key will result in an immediate {@link ClassCastException},
1.2894 + * whether the modification is attempted directly through the map
1.2895 + * itself, or through a {@link Map.Entry} instance obtained from the
1.2896 + * map's {@link Map#entrySet() entry set} view.
1.2897 + *
1.2898 + * <p>Assuming a map contains no incorrectly typed keys or values
1.2899 + * prior to the time a dynamically typesafe view is generated, and
1.2900 + * that all subsequent access to the map takes place through the view
1.2901 + * (or one of its collection views), it is <i>guaranteed</i> that the
1.2902 + * map cannot contain an incorrectly typed key or value.
1.2903 + *
1.2904 + * <p>A discussion of the use of dynamically typesafe views may be
1.2905 + * found in the documentation for the {@link #checkedCollection
1.2906 + * checkedCollection} method.
1.2907 + *
1.2908 + * <p>The returned map will be serializable if the specified map is
1.2909 + * serializable.
1.2910 + *
1.2911 + * <p>Since {@code null} is considered to be a value of any reference
1.2912 + * type, the returned map permits insertion of null keys or values
1.2913 + * whenever the backing map does.
1.2914 + *
1.2915 + * @param m the map for which a dynamically typesafe view is to be
1.2916 + * returned
1.2917 + * @param keyType the type of key that {@code m} is permitted to hold
1.2918 + * @param valueType the type of value that {@code m} is permitted to hold
1.2919 + * @return a dynamically typesafe view of the specified map
1.2920 + * @since 1.5
1.2921 + */
1.2922 + public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m,
1.2923 + Class<K> keyType,
1.2924 + Class<V> valueType) {
1.2925 + return new CheckedSortedMap<>(m, keyType, valueType);
1.2926 + }
1.2927 +
1.2928 + /**
1.2929 + * @serial include
1.2930 + */
1.2931 + static class CheckedSortedMap<K,V> extends CheckedMap<K,V>
1.2932 + implements SortedMap<K,V>, Serializable
1.2933 + {
1.2934 + private static final long serialVersionUID = 1599671320688067438L;
1.2935 +
1.2936 + private final SortedMap<K, V> sm;
1.2937 +
1.2938 + CheckedSortedMap(SortedMap<K, V> m,
1.2939 + Class<K> keyType, Class<V> valueType) {
1.2940 + super(m, keyType, valueType);
1.2941 + sm = m;
1.2942 + }
1.2943 +
1.2944 + public Comparator<? super K> comparator() { return sm.comparator(); }
1.2945 + public K firstKey() { return sm.firstKey(); }
1.2946 + public K lastKey() { return sm.lastKey(); }
1.2947 +
1.2948 + public SortedMap<K,V> subMap(K fromKey, K toKey) {
1.2949 + return checkedSortedMap(sm.subMap(fromKey, toKey),
1.2950 + keyType, valueType);
1.2951 + }
1.2952 + public SortedMap<K,V> headMap(K toKey) {
1.2953 + return checkedSortedMap(sm.headMap(toKey), keyType, valueType);
1.2954 + }
1.2955 + public SortedMap<K,V> tailMap(K fromKey) {
1.2956 + return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType);
1.2957 + }
1.2958 + }
1.2959 +
1.2960 + // Empty collections
1.2961 +
1.2962 + /**
1.2963 + * Returns an iterator that has no elements. More precisely,
1.2964 + *
1.2965 + * <ul compact>
1.2966 + *
1.2967 + * <li>{@link Iterator#hasNext hasNext} always returns {@code
1.2968 + * false}.
1.2969 + *
1.2970 + * <li>{@link Iterator#next next} always throws {@link
1.2971 + * NoSuchElementException}.
1.2972 + *
1.2973 + * <li>{@link Iterator#remove remove} always throws {@link
1.2974 + * IllegalStateException}.
1.2975 + *
1.2976 + * </ul>
1.2977 + *
1.2978 + * <p>Implementations of this method are permitted, but not
1.2979 + * required, to return the same object from multiple invocations.
1.2980 + *
1.2981 + * @return an empty iterator
1.2982 + * @since 1.7
1.2983 + */
1.2984 + @SuppressWarnings("unchecked")
1.2985 + public static <T> Iterator<T> emptyIterator() {
1.2986 + return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
1.2987 + }
1.2988 +
1.2989 + private static class EmptyIterator<E> implements Iterator<E> {
1.2990 + static final EmptyIterator<Object> EMPTY_ITERATOR
1.2991 + = new EmptyIterator<>();
1.2992 +
1.2993 + public boolean hasNext() { return false; }
1.2994 + public E next() { throw new NoSuchElementException(); }
1.2995 + public void remove() { throw new IllegalStateException(); }
1.2996 + }
1.2997 +
1.2998 + /**
1.2999 + * Returns a list iterator that has no elements. More precisely,
1.3000 + *
1.3001 + * <ul compact>
1.3002 + *
1.3003 + * <li>{@link Iterator#hasNext hasNext} and {@link
1.3004 + * ListIterator#hasPrevious hasPrevious} always return {@code
1.3005 + * false}.
1.3006 + *
1.3007 + * <li>{@link Iterator#next next} and {@link ListIterator#previous
1.3008 + * previous} always throw {@link NoSuchElementException}.
1.3009 + *
1.3010 + * <li>{@link Iterator#remove remove} and {@link ListIterator#set
1.3011 + * set} always throw {@link IllegalStateException}.
1.3012 + *
1.3013 + * <li>{@link ListIterator#add add} always throws {@link
1.3014 + * UnsupportedOperationException}.
1.3015 + *
1.3016 + * <li>{@link ListIterator#nextIndex nextIndex} always returns
1.3017 + * {@code 0} .
1.3018 + *
1.3019 + * <li>{@link ListIterator#previousIndex previousIndex} always
1.3020 + * returns {@code -1}.
1.3021 + *
1.3022 + * </ul>
1.3023 + *
1.3024 + * <p>Implementations of this method are permitted, but not
1.3025 + * required, to return the same object from multiple invocations.
1.3026 + *
1.3027 + * @return an empty list iterator
1.3028 + * @since 1.7
1.3029 + */
1.3030 + @SuppressWarnings("unchecked")
1.3031 + public static <T> ListIterator<T> emptyListIterator() {
1.3032 + return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
1.3033 + }
1.3034 +
1.3035 + private static class EmptyListIterator<E>
1.3036 + extends EmptyIterator<E>
1.3037 + implements ListIterator<E>
1.3038 + {
1.3039 + static final EmptyListIterator<Object> EMPTY_ITERATOR
1.3040 + = new EmptyListIterator<>();
1.3041 +
1.3042 + public boolean hasPrevious() { return false; }
1.3043 + public E previous() { throw new NoSuchElementException(); }
1.3044 + public int nextIndex() { return 0; }
1.3045 + public int previousIndex() { return -1; }
1.3046 + public void set(E e) { throw new IllegalStateException(); }
1.3047 + public void add(E e) { throw new UnsupportedOperationException(); }
1.3048 + }
1.3049 +
1.3050 + /**
1.3051 + * Returns an enumeration that has no elements. More precisely,
1.3052 + *
1.3053 + * <ul compact>
1.3054 + *
1.3055 + * <li>{@link Enumeration#hasMoreElements hasMoreElements} always
1.3056 + * returns {@code false}.
1.3057 + *
1.3058 + * <li> {@link Enumeration#nextElement nextElement} always throws
1.3059 + * {@link NoSuchElementException}.
1.3060 + *
1.3061 + * </ul>
1.3062 + *
1.3063 + * <p>Implementations of this method are permitted, but not
1.3064 + * required, to return the same object from multiple invocations.
1.3065 + *
1.3066 + * @return an empty enumeration
1.3067 + * @since 1.7
1.3068 + */
1.3069 + @SuppressWarnings("unchecked")
1.3070 + public static <T> Enumeration<T> emptyEnumeration() {
1.3071 + return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
1.3072 + }
1.3073 +
1.3074 + private static class EmptyEnumeration<E> implements Enumeration<E> {
1.3075 + static final EmptyEnumeration<Object> EMPTY_ENUMERATION
1.3076 + = new EmptyEnumeration<>();
1.3077 +
1.3078 + public boolean hasMoreElements() { return false; }
1.3079 + public E nextElement() { throw new NoSuchElementException(); }
1.3080 + }
1.3081 +
1.3082 + /**
1.3083 + * The empty set (immutable). This set is serializable.
1.3084 + *
1.3085 + * @see #emptySet()
1.3086 + */
1.3087 + @SuppressWarnings("unchecked")
1.3088 + public static final Set EMPTY_SET = new EmptySet<>();
1.3089 +
1.3090 + /**
1.3091 + * Returns the empty set (immutable). This set is serializable.
1.3092 + * Unlike the like-named field, this method is parameterized.
1.3093 + *
1.3094 + * <p>This example illustrates the type-safe way to obtain an empty set:
1.3095 + * <pre>
1.3096 + * Set<String> s = Collections.emptySet();
1.3097 + * </pre>
1.3098 + * Implementation note: Implementations of this method need not
1.3099 + * create a separate <tt>Set</tt> object for each call. Using this
1.3100 + * method is likely to have comparable cost to using the like-named
1.3101 + * field. (Unlike this method, the field does not provide type safety.)
1.3102 + *
1.3103 + * @see #EMPTY_SET
1.3104 + * @since 1.5
1.3105 + */
1.3106 + @SuppressWarnings("unchecked")
1.3107 + public static final <T> Set<T> emptySet() {
1.3108 + return (Set<T>) EMPTY_SET;
1.3109 + }
1.3110 +
1.3111 + /**
1.3112 + * @serial include
1.3113 + */
1.3114 + private static class EmptySet<E>
1.3115 + extends AbstractSet<E>
1.3116 + implements Serializable
1.3117 + {
1.3118 + private static final long serialVersionUID = 1582296315990362920L;
1.3119 +
1.3120 + public Iterator<E> iterator() { return emptyIterator(); }
1.3121 +
1.3122 + public int size() {return 0;}
1.3123 + public boolean isEmpty() {return true;}
1.3124 +
1.3125 + public boolean contains(Object obj) {return false;}
1.3126 + public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
1.3127 +
1.3128 + public Object[] toArray() { return new Object[0]; }
1.3129 +
1.3130 + public <T> T[] toArray(T[] a) {
1.3131 + if (a.length > 0)
1.3132 + a[0] = null;
1.3133 + return a;
1.3134 + }
1.3135 +
1.3136 + // Preserves singleton property
1.3137 + private Object readResolve() {
1.3138 + return EMPTY_SET;
1.3139 + }
1.3140 + }
1.3141 +
1.3142 + /**
1.3143 + * The empty list (immutable). This list is serializable.
1.3144 + *
1.3145 + * @see #emptyList()
1.3146 + */
1.3147 + @SuppressWarnings("unchecked")
1.3148 + public static final List EMPTY_LIST = new EmptyList<>();
1.3149 +
1.3150 + /**
1.3151 + * Returns the empty list (immutable). This list is serializable.
1.3152 + *
1.3153 + * <p>This example illustrates the type-safe way to obtain an empty list:
1.3154 + * <pre>
1.3155 + * List<String> s = Collections.emptyList();
1.3156 + * </pre>
1.3157 + * Implementation note: Implementations of this method need not
1.3158 + * create a separate <tt>List</tt> object for each call. Using this
1.3159 + * method is likely to have comparable cost to using the like-named
1.3160 + * field. (Unlike this method, the field does not provide type safety.)
1.3161 + *
1.3162 + * @see #EMPTY_LIST
1.3163 + * @since 1.5
1.3164 + */
1.3165 + @SuppressWarnings("unchecked")
1.3166 + public static final <T> List<T> emptyList() {
1.3167 + return (List<T>) EMPTY_LIST;
1.3168 + }
1.3169 +
1.3170 + /**
1.3171 + * @serial include
1.3172 + */
1.3173 + private static class EmptyList<E>
1.3174 + extends AbstractList<E>
1.3175 + implements RandomAccess, Serializable {
1.3176 + private static final long serialVersionUID = 8842843931221139166L;
1.3177 +
1.3178 + public Iterator<E> iterator() {
1.3179 + return emptyIterator();
1.3180 + }
1.3181 + public ListIterator<E> listIterator() {
1.3182 + return emptyListIterator();
1.3183 + }
1.3184 +
1.3185 + public int size() {return 0;}
1.3186 + public boolean isEmpty() {return true;}
1.3187 +
1.3188 + public boolean contains(Object obj) {return false;}
1.3189 + public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
1.3190 +
1.3191 + public Object[] toArray() { return new Object[0]; }
1.3192 +
1.3193 + public <T> T[] toArray(T[] a) {
1.3194 + if (a.length > 0)
1.3195 + a[0] = null;
1.3196 + return a;
1.3197 + }
1.3198 +
1.3199 + public E get(int index) {
1.3200 + throw new IndexOutOfBoundsException("Index: "+index);
1.3201 + }
1.3202 +
1.3203 + public boolean equals(Object o) {
1.3204 + return (o instanceof List) && ((List<?>)o).isEmpty();
1.3205 + }
1.3206 +
1.3207 + public int hashCode() { return 1; }
1.3208 +
1.3209 + // Preserves singleton property
1.3210 + private Object readResolve() {
1.3211 + return EMPTY_LIST;
1.3212 + }
1.3213 + }
1.3214 +
1.3215 + /**
1.3216 + * The empty map (immutable). This map is serializable.
1.3217 + *
1.3218 + * @see #emptyMap()
1.3219 + * @since 1.3
1.3220 + */
1.3221 + @SuppressWarnings("unchecked")
1.3222 + public static final Map EMPTY_MAP = new EmptyMap<>();
1.3223 +
1.3224 + /**
1.3225 + * Returns the empty map (immutable). This map is serializable.
1.3226 + *
1.3227 + * <p>This example illustrates the type-safe way to obtain an empty set:
1.3228 + * <pre>
1.3229 + * Map<String, Date> s = Collections.emptyMap();
1.3230 + * </pre>
1.3231 + * Implementation note: Implementations of this method need not
1.3232 + * create a separate <tt>Map</tt> object for each call. Using this
1.3233 + * method is likely to have comparable cost to using the like-named
1.3234 + * field. (Unlike this method, the field does not provide type safety.)
1.3235 + *
1.3236 + * @see #EMPTY_MAP
1.3237 + * @since 1.5
1.3238 + */
1.3239 + @SuppressWarnings("unchecked")
1.3240 + public static final <K,V> Map<K,V> emptyMap() {
1.3241 + return (Map<K,V>) EMPTY_MAP;
1.3242 + }
1.3243 +
1.3244 + /**
1.3245 + * @serial include
1.3246 + */
1.3247 + private static class EmptyMap<K,V>
1.3248 + extends AbstractMap<K,V>
1.3249 + implements Serializable
1.3250 + {
1.3251 + private static final long serialVersionUID = 6428348081105594320L;
1.3252 +
1.3253 + public int size() {return 0;}
1.3254 + public boolean isEmpty() {return true;}
1.3255 + public boolean containsKey(Object key) {return false;}
1.3256 + public boolean containsValue(Object value) {return false;}
1.3257 + public V get(Object key) {return null;}
1.3258 + public Set<K> keySet() {return emptySet();}
1.3259 + public Collection<V> values() {return emptySet();}
1.3260 + public Set<Map.Entry<K,V>> entrySet() {return emptySet();}
1.3261 +
1.3262 + public boolean equals(Object o) {
1.3263 + return (o instanceof Map) && ((Map<?,?>)o).isEmpty();
1.3264 + }
1.3265 +
1.3266 + public int hashCode() {return 0;}
1.3267 +
1.3268 + // Preserves singleton property
1.3269 + private Object readResolve() {
1.3270 + return EMPTY_MAP;
1.3271 + }
1.3272 + }
1.3273 +
1.3274 + // Singleton collections
1.3275 +
1.3276 + /**
1.3277 + * Returns an immutable set containing only the specified object.
1.3278 + * The returned set is serializable.
1.3279 + *
1.3280 + * @param o the sole object to be stored in the returned set.
1.3281 + * @return an immutable set containing only the specified object.
1.3282 + */
1.3283 + public static <T> Set<T> singleton(T o) {
1.3284 + return new SingletonSet<>(o);
1.3285 + }
1.3286 +
1.3287 + static <E> Iterator<E> singletonIterator(final E e) {
1.3288 + return new Iterator<E>() {
1.3289 + private boolean hasNext = true;
1.3290 + public boolean hasNext() {
1.3291 + return hasNext;
1.3292 + }
1.3293 + public E next() {
1.3294 + if (hasNext) {
1.3295 + hasNext = false;
1.3296 + return e;
1.3297 + }
1.3298 + throw new NoSuchElementException();
1.3299 + }
1.3300 + public void remove() {
1.3301 + throw new UnsupportedOperationException();
1.3302 + }
1.3303 + };
1.3304 + }
1.3305 +
1.3306 + /**
1.3307 + * @serial include
1.3308 + */
1.3309 + private static class SingletonSet<E>
1.3310 + extends AbstractSet<E>
1.3311 + implements Serializable
1.3312 + {
1.3313 + private static final long serialVersionUID = 3193687207550431679L;
1.3314 +
1.3315 + private final E element;
1.3316 +
1.3317 + SingletonSet(E e) {element = e;}
1.3318 +
1.3319 + public Iterator<E> iterator() {
1.3320 + return singletonIterator(element);
1.3321 + }
1.3322 +
1.3323 + public int size() {return 1;}
1.3324 +
1.3325 + public boolean contains(Object o) {return eq(o, element);}
1.3326 + }
1.3327 +
1.3328 + /**
1.3329 + * Returns an immutable list containing only the specified object.
1.3330 + * The returned list is serializable.
1.3331 + *
1.3332 + * @param o the sole object to be stored in the returned list.
1.3333 + * @return an immutable list containing only the specified object.
1.3334 + * @since 1.3
1.3335 + */
1.3336 + public static <T> List<T> singletonList(T o) {
1.3337 + return new SingletonList<>(o);
1.3338 + }
1.3339 +
1.3340 + /**
1.3341 + * @serial include
1.3342 + */
1.3343 + private static class SingletonList<E>
1.3344 + extends AbstractList<E>
1.3345 + implements RandomAccess, Serializable {
1.3346 +
1.3347 + private static final long serialVersionUID = 3093736618740652951L;
1.3348 +
1.3349 + private final E element;
1.3350 +
1.3351 + SingletonList(E obj) {element = obj;}
1.3352 +
1.3353 + public Iterator<E> iterator() {
1.3354 + return singletonIterator(element);
1.3355 + }
1.3356 +
1.3357 + public int size() {return 1;}
1.3358 +
1.3359 + public boolean contains(Object obj) {return eq(obj, element);}
1.3360 +
1.3361 + public E get(int index) {
1.3362 + if (index != 0)
1.3363 + throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
1.3364 + return element;
1.3365 + }
1.3366 + }
1.3367 +
1.3368 + /**
1.3369 + * Returns an immutable map, mapping only the specified key to the
1.3370 + * specified value. The returned map is serializable.
1.3371 + *
1.3372 + * @param key the sole key to be stored in the returned map.
1.3373 + * @param value the value to which the returned map maps <tt>key</tt>.
1.3374 + * @return an immutable map containing only the specified key-value
1.3375 + * mapping.
1.3376 + * @since 1.3
1.3377 + */
1.3378 + public static <K,V> Map<K,V> singletonMap(K key, V value) {
1.3379 + return new SingletonMap<>(key, value);
1.3380 + }
1.3381 +
1.3382 + /**
1.3383 + * @serial include
1.3384 + */
1.3385 + private static class SingletonMap<K,V>
1.3386 + extends AbstractMap<K,V>
1.3387 + implements Serializable {
1.3388 + private static final long serialVersionUID = -6979724477215052911L;
1.3389 +
1.3390 + private final K k;
1.3391 + private final V v;
1.3392 +
1.3393 + SingletonMap(K key, V value) {
1.3394 + k = key;
1.3395 + v = value;
1.3396 + }
1.3397 +
1.3398 + public int size() {return 1;}
1.3399 +
1.3400 + public boolean isEmpty() {return false;}
1.3401 +
1.3402 + public boolean containsKey(Object key) {return eq(key, k);}
1.3403 +
1.3404 + public boolean containsValue(Object value) {return eq(value, v);}
1.3405 +
1.3406 + public V get(Object key) {return (eq(key, k) ? v : null);}
1.3407 +
1.3408 + private transient Set<K> keySet = null;
1.3409 + private transient Set<Map.Entry<K,V>> entrySet = null;
1.3410 + private transient Collection<V> values = null;
1.3411 +
1.3412 + public Set<K> keySet() {
1.3413 + if (keySet==null)
1.3414 + keySet = singleton(k);
1.3415 + return keySet;
1.3416 + }
1.3417 +
1.3418 + public Set<Map.Entry<K,V>> entrySet() {
1.3419 + if (entrySet==null)
1.3420 + entrySet = Collections.<Map.Entry<K,V>>singleton(
1.3421 + new SimpleImmutableEntry<>(k, v));
1.3422 + return entrySet;
1.3423 + }
1.3424 +
1.3425 + public Collection<V> values() {
1.3426 + if (values==null)
1.3427 + values = singleton(v);
1.3428 + return values;
1.3429 + }
1.3430 +
1.3431 + }
1.3432 +
1.3433 + // Miscellaneous
1.3434 +
1.3435 + /**
1.3436 + * Returns an immutable list consisting of <tt>n</tt> copies of the
1.3437 + * specified object. The newly allocated data object is tiny (it contains
1.3438 + * a single reference to the data object). This method is useful in
1.3439 + * combination with the <tt>List.addAll</tt> method to grow lists.
1.3440 + * The returned list is serializable.
1.3441 + *
1.3442 + * @param n the number of elements in the returned list.
1.3443 + * @param o the element to appear repeatedly in the returned list.
1.3444 + * @return an immutable list consisting of <tt>n</tt> copies of the
1.3445 + * specified object.
1.3446 + * @throws IllegalArgumentException if {@code n < 0}
1.3447 + * @see List#addAll(Collection)
1.3448 + * @see List#addAll(int, Collection)
1.3449 + */
1.3450 + public static <T> List<T> nCopies(int n, T o) {
1.3451 + if (n < 0)
1.3452 + throw new IllegalArgumentException("List length = " + n);
1.3453 + return new CopiesList<>(n, o);
1.3454 + }
1.3455 +
1.3456 + /**
1.3457 + * @serial include
1.3458 + */
1.3459 + private static class CopiesList<E>
1.3460 + extends AbstractList<E>
1.3461 + implements RandomAccess, Serializable
1.3462 + {
1.3463 + private static final long serialVersionUID = 2739099268398711800L;
1.3464 +
1.3465 + final int n;
1.3466 + final E element;
1.3467 +
1.3468 + CopiesList(int n, E e) {
1.3469 + assert n >= 0;
1.3470 + this.n = n;
1.3471 + element = e;
1.3472 + }
1.3473 +
1.3474 + public int size() {
1.3475 + return n;
1.3476 + }
1.3477 +
1.3478 + public boolean contains(Object obj) {
1.3479 + return n != 0 && eq(obj, element);
1.3480 + }
1.3481 +
1.3482 + public int indexOf(Object o) {
1.3483 + return contains(o) ? 0 : -1;
1.3484 + }
1.3485 +
1.3486 + public int lastIndexOf(Object o) {
1.3487 + return contains(o) ? n - 1 : -1;
1.3488 + }
1.3489 +
1.3490 + public E get(int index) {
1.3491 + if (index < 0 || index >= n)
1.3492 + throw new IndexOutOfBoundsException("Index: "+index+
1.3493 + ", Size: "+n);
1.3494 + return element;
1.3495 + }
1.3496 +
1.3497 + public Object[] toArray() {
1.3498 + final Object[] a = new Object[n];
1.3499 + if (element != null)
1.3500 + Arrays.fill(a, 0, n, element);
1.3501 + return a;
1.3502 + }
1.3503 +
1.3504 + public <T> T[] toArray(T[] a) {
1.3505 + final int n = this.n;
1.3506 + if (a.length < n) {
1.3507 + a = (T[])java.lang.reflect.Array
1.3508 + .newInstance(a.getClass().getComponentType(), n);
1.3509 + if (element != null)
1.3510 + Arrays.fill(a, 0, n, element);
1.3511 + } else {
1.3512 + Arrays.fill(a, 0, n, element);
1.3513 + if (a.length > n)
1.3514 + a[n] = null;
1.3515 + }
1.3516 + return a;
1.3517 + }
1.3518 +
1.3519 + public List<E> subList(int fromIndex, int toIndex) {
1.3520 + if (fromIndex < 0)
1.3521 + throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
1.3522 + if (toIndex > n)
1.3523 + throw new IndexOutOfBoundsException("toIndex = " + toIndex);
1.3524 + if (fromIndex > toIndex)
1.3525 + throw new IllegalArgumentException("fromIndex(" + fromIndex +
1.3526 + ") > toIndex(" + toIndex + ")");
1.3527 + return new CopiesList<>(toIndex - fromIndex, element);
1.3528 + }
1.3529 + }
1.3530 +
1.3531 + /**
1.3532 + * Returns a comparator that imposes the reverse of the <em>natural
1.3533 + * ordering</em> on a collection of objects that implement the
1.3534 + * {@code Comparable} interface. (The natural ordering is the ordering
1.3535 + * imposed by the objects' own {@code compareTo} method.) This enables a
1.3536 + * simple idiom for sorting (or maintaining) collections (or arrays) of
1.3537 + * objects that implement the {@code Comparable} interface in
1.3538 + * reverse-natural-order. For example, suppose {@code a} is an array of
1.3539 + * strings. Then: <pre>
1.3540 + * Arrays.sort(a, Collections.reverseOrder());
1.3541 + * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
1.3542 + *
1.3543 + * The returned comparator is serializable.
1.3544 + *
1.3545 + * @return A comparator that imposes the reverse of the <i>natural
1.3546 + * ordering</i> on a collection of objects that implement
1.3547 + * the <tt>Comparable</tt> interface.
1.3548 + * @see Comparable
1.3549 + */
1.3550 + public static <T> Comparator<T> reverseOrder() {
1.3551 + return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
1.3552 + }
1.3553 +
1.3554 + /**
1.3555 + * @serial include
1.3556 + */
1.3557 + private static class ReverseComparator
1.3558 + implements Comparator<Comparable<Object>>, Serializable {
1.3559 +
1.3560 + private static final long serialVersionUID = 7207038068494060240L;
1.3561 +
1.3562 + static final ReverseComparator REVERSE_ORDER
1.3563 + = new ReverseComparator();
1.3564 +
1.3565 + public int compare(Comparable<Object> c1, Comparable<Object> c2) {
1.3566 + return c2.compareTo(c1);
1.3567 + }
1.3568 +
1.3569 + private Object readResolve() { return reverseOrder(); }
1.3570 + }
1.3571 +
1.3572 + /**
1.3573 + * Returns a comparator that imposes the reverse ordering of the specified
1.3574 + * comparator. If the specified comparator is {@code null}, this method is
1.3575 + * equivalent to {@link #reverseOrder()} (in other words, it returns a
1.3576 + * comparator that imposes the reverse of the <em>natural ordering</em> on
1.3577 + * a collection of objects that implement the Comparable interface).
1.3578 + *
1.3579 + * <p>The returned comparator is serializable (assuming the specified
1.3580 + * comparator is also serializable or {@code null}).
1.3581 + *
1.3582 + * @param cmp a comparator who's ordering is to be reversed by the returned
1.3583 + * comparator or {@code null}
1.3584 + * @return A comparator that imposes the reverse ordering of the
1.3585 + * specified comparator.
1.3586 + * @since 1.5
1.3587 + */
1.3588 + public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
1.3589 + if (cmp == null)
1.3590 + return reverseOrder();
1.3591 +
1.3592 + if (cmp instanceof ReverseComparator2)
1.3593 + return ((ReverseComparator2<T>)cmp).cmp;
1.3594 +
1.3595 + return new ReverseComparator2<>(cmp);
1.3596 + }
1.3597 +
1.3598 + /**
1.3599 + * @serial include
1.3600 + */
1.3601 + private static class ReverseComparator2<T> implements Comparator<T>,
1.3602 + Serializable
1.3603 + {
1.3604 + private static final long serialVersionUID = 4374092139857L;
1.3605 +
1.3606 + /**
1.3607 + * The comparator specified in the static factory. This will never
1.3608 + * be null, as the static factory returns a ReverseComparator
1.3609 + * instance if its argument is null.
1.3610 + *
1.3611 + * @serial
1.3612 + */
1.3613 + final Comparator<T> cmp;
1.3614 +
1.3615 + ReverseComparator2(Comparator<T> cmp) {
1.3616 + assert cmp != null;
1.3617 + this.cmp = cmp;
1.3618 + }
1.3619 +
1.3620 + public int compare(T t1, T t2) {
1.3621 + return cmp.compare(t2, t1);
1.3622 + }
1.3623 +
1.3624 + public boolean equals(Object o) {
1.3625 + return (o == this) ||
1.3626 + (o instanceof ReverseComparator2 &&
1.3627 + cmp.equals(((ReverseComparator2)o).cmp));
1.3628 + }
1.3629 +
1.3630 + public int hashCode() {
1.3631 + return cmp.hashCode() ^ Integer.MIN_VALUE;
1.3632 + }
1.3633 + }
1.3634 +
1.3635 + /**
1.3636 + * Returns an enumeration over the specified collection. This provides
1.3637 + * interoperability with legacy APIs that require an enumeration
1.3638 + * as input.
1.3639 + *
1.3640 + * @param c the collection for which an enumeration is to be returned.
1.3641 + * @return an enumeration over the specified collection.
1.3642 + * @see Enumeration
1.3643 + */
1.3644 + public static <T> Enumeration<T> enumeration(final Collection<T> c) {
1.3645 + return new Enumeration<T>() {
1.3646 + private final Iterator<T> i = c.iterator();
1.3647 +
1.3648 + public boolean hasMoreElements() {
1.3649 + return i.hasNext();
1.3650 + }
1.3651 +
1.3652 + public T nextElement() {
1.3653 + return i.next();
1.3654 + }
1.3655 + };
1.3656 + }
1.3657 +
1.3658 + /**
1.3659 + * Returns an array list containing the elements returned by the
1.3660 + * specified enumeration in the order they are returned by the
1.3661 + * enumeration. This method provides interoperability between
1.3662 + * legacy APIs that return enumerations and new APIs that require
1.3663 + * collections.
1.3664 + *
1.3665 + * @param e enumeration providing elements for the returned
1.3666 + * array list
1.3667 + * @return an array list containing the elements returned
1.3668 + * by the specified enumeration.
1.3669 + * @since 1.4
1.3670 + * @see Enumeration
1.3671 + * @see ArrayList
1.3672 + */
1.3673 + public static <T> ArrayList<T> list(Enumeration<T> e) {
1.3674 + ArrayList<T> l = new ArrayList<>();
1.3675 + while (e.hasMoreElements())
1.3676 + l.add(e.nextElement());
1.3677 + return l;
1.3678 + }
1.3679 +
1.3680 + /**
1.3681 + * Returns true if the specified arguments are equal, or both null.
1.3682 + */
1.3683 + static boolean eq(Object o1, Object o2) {
1.3684 + return o1==null ? o2==null : o1.equals(o2);
1.3685 + }
1.3686 +
1.3687 + /**
1.3688 + * Returns the number of elements in the specified collection equal to the
1.3689 + * specified object. More formally, returns the number of elements
1.3690 + * <tt>e</tt> in the collection such that
1.3691 + * <tt>(o == null ? e == null : o.equals(e))</tt>.
1.3692 + *
1.3693 + * @param c the collection in which to determine the frequency
1.3694 + * of <tt>o</tt>
1.3695 + * @param o the object whose frequency is to be determined
1.3696 + * @throws NullPointerException if <tt>c</tt> is null
1.3697 + * @since 1.5
1.3698 + */
1.3699 + public static int frequency(Collection<?> c, Object o) {
1.3700 + int result = 0;
1.3701 + if (o == null) {
1.3702 + for (Object e : c)
1.3703 + if (e == null)
1.3704 + result++;
1.3705 + } else {
1.3706 + for (Object e : c)
1.3707 + if (o.equals(e))
1.3708 + result++;
1.3709 + }
1.3710 + return result;
1.3711 + }
1.3712 +
1.3713 + /**
1.3714 + * Returns {@code true} if the two specified collections have no
1.3715 + * elements in common.
1.3716 + *
1.3717 + * <p>Care must be exercised if this method is used on collections that
1.3718 + * do not comply with the general contract for {@code Collection}.
1.3719 + * Implementations may elect to iterate over either collection and test
1.3720 + * for containment in the other collection (or to perform any equivalent
1.3721 + * computation). If either collection uses a nonstandard equality test
1.3722 + * (as does a {@link SortedSet} whose ordering is not <em>compatible with
1.3723 + * equals</em>, or the key set of an {@link IdentityHashMap}), both
1.3724 + * collections must use the same nonstandard equality test, or the
1.3725 + * result of this method is undefined.
1.3726 + *
1.3727 + * <p>Care must also be exercised when using collections that have
1.3728 + * restrictions on the elements that they may contain. Collection
1.3729 + * implementations are allowed to throw exceptions for any operation
1.3730 + * involving elements they deem ineligible. For absolute safety the
1.3731 + * specified collections should contain only elements which are
1.3732 + * eligible elements for both collections.
1.3733 + *
1.3734 + * <p>Note that it is permissible to pass the same collection in both
1.3735 + * parameters, in which case the method will return {@code true} if and
1.3736 + * only if the collection is empty.
1.3737 + *
1.3738 + * @param c1 a collection
1.3739 + * @param c2 a collection
1.3740 + * @return {@code true} if the two specified collections have no
1.3741 + * elements in common.
1.3742 + * @throws NullPointerException if either collection is {@code null}.
1.3743 + * @throws NullPointerException if one collection contains a {@code null}
1.3744 + * element and {@code null} is not an eligible element for the other collection.
1.3745 + * (<a href="Collection.html#optional-restrictions">optional</a>)
1.3746 + * @throws ClassCastException if one collection contains an element that is
1.3747 + * of a type which is ineligible for the other collection.
1.3748 + * (<a href="Collection.html#optional-restrictions">optional</a>)
1.3749 + * @since 1.5
1.3750 + */
1.3751 + public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
1.3752 + // The collection to be used for contains(). Preference is given to
1.3753 + // the collection who's contains() has lower O() complexity.
1.3754 + Collection<?> contains = c2;
1.3755 + // The collection to be iterated. If the collections' contains() impl
1.3756 + // are of different O() complexity, the collection with slower
1.3757 + // contains() will be used for iteration. For collections who's
1.3758 + // contains() are of the same complexity then best performance is
1.3759 + // achieved by iterating the smaller collection.
1.3760 + Collection<?> iterate = c1;
1.3761 +
1.3762 + // Performance optimization cases. The heuristics:
1.3763 + // 1. Generally iterate over c1.
1.3764 + // 2. If c1 is a Set then iterate over c2.
1.3765 + // 3. If either collection is empty then result is always true.
1.3766 + // 4. Iterate over the smaller Collection.
1.3767 + if (c1 instanceof Set) {
1.3768 + // Use c1 for contains as a Set's contains() is expected to perform
1.3769 + // better than O(N/2)
1.3770 + iterate = c2;
1.3771 + contains = c1;
1.3772 + } else if (!(c2 instanceof Set)) {
1.3773 + // Both are mere Collections. Iterate over smaller collection.
1.3774 + // Example: If c1 contains 3 elements and c2 contains 50 elements and
1.3775 + // assuming contains() requires ceiling(N/2) comparisons then
1.3776 + // checking for all c1 elements in c2 would require 75 comparisons
1.3777 + // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring
1.3778 + // 100 comparisons (50 * ceiling(3/2)).
1.3779 + int c1size = c1.size();
1.3780 + int c2size = c2.size();
1.3781 + if (c1size == 0 || c2size == 0) {
1.3782 + // At least one collection is empty. Nothing will match.
1.3783 + return true;
1.3784 + }
1.3785 +
1.3786 + if (c1size > c2size) {
1.3787 + iterate = c2;
1.3788 + contains = c1;
1.3789 + }
1.3790 + }
1.3791 +
1.3792 + for (Object e : iterate) {
1.3793 + if (contains.contains(e)) {
1.3794 + // Found a common element. Collections are not disjoint.
1.3795 + return false;
1.3796 + }
1.3797 + }
1.3798 +
1.3799 + // No common elements were found.
1.3800 + return true;
1.3801 + }
1.3802 +
1.3803 + /**
1.3804 + * Adds all of the specified elements to the specified collection.
1.3805 + * Elements to be added may be specified individually or as an array.
1.3806 + * The behavior of this convenience method is identical to that of
1.3807 + * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely
1.3808 + * to run significantly faster under most implementations.
1.3809 + *
1.3810 + * <p>When elements are specified individually, this method provides a
1.3811 + * convenient way to add a few elements to an existing collection:
1.3812 + * <pre>
1.3813 + * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
1.3814 + * </pre>
1.3815 + *
1.3816 + * @param c the collection into which <tt>elements</tt> are to be inserted
1.3817 + * @param elements the elements to insert into <tt>c</tt>
1.3818 + * @return <tt>true</tt> if the collection changed as a result of the call
1.3819 + * @throws UnsupportedOperationException if <tt>c</tt> does not support
1.3820 + * the <tt>add</tt> operation
1.3821 + * @throws NullPointerException if <tt>elements</tt> contains one or more
1.3822 + * null values and <tt>c</tt> does not permit null elements, or
1.3823 + * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
1.3824 + * @throws IllegalArgumentException if some property of a value in
1.3825 + * <tt>elements</tt> prevents it from being added to <tt>c</tt>
1.3826 + * @see Collection#addAll(Collection)
1.3827 + * @since 1.5
1.3828 + */
1.3829 + @SafeVarargs
1.3830 + public static <T> boolean addAll(Collection<? super T> c, T... elements) {
1.3831 + boolean result = false;
1.3832 + for (T element : elements)
1.3833 + result |= c.add(element);
1.3834 + return result;
1.3835 + }
1.3836 +
1.3837 + /**
1.3838 + * Returns a set backed by the specified map. The resulting set displays
1.3839 + * the same ordering, concurrency, and performance characteristics as the
1.3840 + * backing map. In essence, this factory method provides a {@link Set}
1.3841 + * implementation corresponding to any {@link Map} implementation. There
1.3842 + * is no need to use this method on a {@link Map} implementation that
1.3843 + * already has a corresponding {@link Set} implementation (such as {@link
1.3844 + * HashMap} or {@link TreeMap}).
1.3845 + *
1.3846 + * <p>Each method invocation on the set returned by this method results in
1.3847 + * exactly one method invocation on the backing map or its <tt>keySet</tt>
1.3848 + * view, with one exception. The <tt>addAll</tt> method is implemented
1.3849 + * as a sequence of <tt>put</tt> invocations on the backing map.
1.3850 + *
1.3851 + * <p>The specified map must be empty at the time this method is invoked,
1.3852 + * and should not be accessed directly after this method returns. These
1.3853 + * conditions are ensured if the map is created empty, passed directly
1.3854 + * to this method, and no reference to the map is retained, as illustrated
1.3855 + * in the following code fragment:
1.3856 + * <pre>
1.3857 + * Set<Object> weakHashSet = Collections.newSetFromMap(
1.3858 + * new WeakHashMap<Object, Boolean>());
1.3859 + * </pre>
1.3860 + *
1.3861 + * @param map the backing map
1.3862 + * @return the set backed by the map
1.3863 + * @throws IllegalArgumentException if <tt>map</tt> is not empty
1.3864 + * @since 1.6
1.3865 + */
1.3866 + public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
1.3867 + return new SetFromMap<>(map);
1.3868 + }
1.3869 +
1.3870 + /**
1.3871 + * @serial include
1.3872 + */
1.3873 + private static class SetFromMap<E> extends AbstractSet<E>
1.3874 + implements Set<E>, Serializable
1.3875 + {
1.3876 + private final Map<E, Boolean> m; // The backing map
1.3877 + private transient Set<E> s; // Its keySet
1.3878 +
1.3879 + SetFromMap(Map<E, Boolean> map) {
1.3880 + if (!map.isEmpty())
1.3881 + throw new IllegalArgumentException("Map is non-empty");
1.3882 + m = map;
1.3883 + s = map.keySet();
1.3884 + }
1.3885 +
1.3886 + public void clear() { m.clear(); }
1.3887 + public int size() { return m.size(); }
1.3888 + public boolean isEmpty() { return m.isEmpty(); }
1.3889 + public boolean contains(Object o) { return m.containsKey(o); }
1.3890 + public boolean remove(Object o) { return m.remove(o) != null; }
1.3891 + public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
1.3892 + public Iterator<E> iterator() { return s.iterator(); }
1.3893 + public Object[] toArray() { return s.toArray(); }
1.3894 + public <T> T[] toArray(T[] a) { return s.toArray(a); }
1.3895 + public String toString() { return s.toString(); }
1.3896 + public int hashCode() { return s.hashCode(); }
1.3897 + public boolean equals(Object o) { return o == this || s.equals(o); }
1.3898 + public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
1.3899 + public boolean removeAll(Collection<?> c) {return s.removeAll(c);}
1.3900 + public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
1.3901 + // addAll is the only inherited implementation
1.3902 +
1.3903 + private static final long serialVersionUID = 2454657854757543876L;
1.3904 +
1.3905 + }
1.3906 +
1.3907 + /**
1.3908 + * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
1.3909 + * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
1.3910 + * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
1.3911 + * view can be useful when you would like to use a method
1.3912 + * requiring a <tt>Queue</tt> but you need Lifo ordering.
1.3913 + *
1.3914 + * <p>Each method invocation on the queue returned by this method
1.3915 + * results in exactly one method invocation on the backing deque, with
1.3916 + * one exception. The {@link Queue#addAll addAll} method is
1.3917 + * implemented as a sequence of {@link Deque#addFirst addFirst}
1.3918 + * invocations on the backing deque.
1.3919 + *
1.3920 + * @param deque the deque
1.3921 + * @return the queue
1.3922 + * @since 1.6
1.3923 + */
1.3924 + public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
1.3925 + return new AsLIFOQueue<>(deque);
1.3926 + }
1.3927 +
1.3928 + /**
1.3929 + * @serial include
1.3930 + */
1.3931 + static class AsLIFOQueue<E> extends AbstractQueue<E>
1.3932 + implements Queue<E>, Serializable {
1.3933 + private static final long serialVersionUID = 1802017725587941708L;
1.3934 + private final Deque<E> q;
1.3935 + AsLIFOQueue(Deque<E> q) { this.q = q; }
1.3936 + public boolean add(E e) { q.addFirst(e); return true; }
1.3937 + public boolean offer(E e) { return q.offerFirst(e); }
1.3938 + public E poll() { return q.pollFirst(); }
1.3939 + public E remove() { return q.removeFirst(); }
1.3940 + public E peek() { return q.peekFirst(); }
1.3941 + public E element() { return q.getFirst(); }
1.3942 + public void clear() { q.clear(); }
1.3943 + public int size() { return q.size(); }
1.3944 + public boolean isEmpty() { return q.isEmpty(); }
1.3945 + public boolean contains(Object o) { return q.contains(o); }
1.3946 + public boolean remove(Object o) { return q.remove(o); }
1.3947 + public Iterator<E> iterator() { return q.iterator(); }
1.3948 + public Object[] toArray() { return q.toArray(); }
1.3949 + public <T> T[] toArray(T[] a) { return q.toArray(a); }
1.3950 + public String toString() { return q.toString(); }
1.3951 + public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
1.3952 + public boolean removeAll(Collection<?> c) {return q.removeAll(c);}
1.3953 + public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
1.3954 + // We use inherited addAll; forwarding addAll would be wrong
1.3955 + }
1.3956 +}