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