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