0001 /*
0002 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 import java.io.Serializable;
0029 import java.io.ObjectOutputStream;
0030 import java.io.IOException;
0031 import java.lang.reflect.Array;
0032
0033 /**
0034 * This class consists exclusively of static methods that operate on or return
0035 * collections. It contains polymorphic algorithms that operate on
0036 * collections, "wrappers", which return a new collection backed by a
0037 * specified collection, and a few other odds and ends.
0038 *
0039 * <p>The methods of this class all throw a <tt>NullPointerException</tt>
0040 * if the collections or class objects provided to them are null.
0041 *
0042 * <p>The documentation for the polymorphic algorithms contained in this class
0043 * generally includes a brief description of the <i>implementation</i>. Such
0044 * descriptions should be regarded as <i>implementation notes</i>, rather than
0045 * parts of the <i>specification</i>. Implementors should feel free to
0046 * substitute other algorithms, so long as the specification itself is adhered
0047 * to. (For example, the algorithm used by <tt>sort</tt> does not have to be
0048 * a mergesort, but it does have to be <i>stable</i>.)
0049 *
0050 * <p>The "destructive" algorithms contained in this class, that is, the
0051 * algorithms that modify the collection on which they operate, are specified
0052 * to throw <tt>UnsupportedOperationException</tt> if the collection does not
0053 * support the appropriate mutation primitive(s), such as the <tt>set</tt>
0054 * method. These algorithms may, but are not required to, throw this
0055 * exception if an invocation would have no effect on the collection. For
0056 * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
0057 * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
0058 *
0059 * <p>This class is a member of the
0060 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0061 * Java Collections Framework</a>.
0062 *
0063 * @author Josh Bloch
0064 * @author Neal Gafter
0065 * @version 1.116, 07/23/07
0066 * @see Collection
0067 * @see Set
0068 * @see List
0069 * @see Map
0070 * @since 1.2
0071 */
0072
0073 public class Collections {
0074 // Suppresses default constructor, ensuring non-instantiability.
0075 private Collections() {
0076 }
0077
0078 // Algorithms
0079
0080 /*
0081 * Tuning parameters for algorithms - Many of the List algorithms have
0082 * two implementations, one of which is appropriate for RandomAccess
0083 * lists, the other for "sequential." Often, the random access variant
0084 * yields better performance on small sequential access lists. The
0085 * tuning parameters below determine the cutoff point for what constitutes
0086 * a "small" sequential access list for each algorithm. The values below
0087 * were empirically determined to work well for LinkedList. Hopefully
0088 * they should be reasonable for other sequential access List
0089 * implementations. Those doing performance work on this code would
0090 * do well to validate the values of these parameters from time to time.
0091 * (The first word of each tuning parameter name is the algorithm to which
0092 * it applies.)
0093 */
0094 private static final int BINARYSEARCH_THRESHOLD = 5000;
0095 private static final int REVERSE_THRESHOLD = 18;
0096 private static final int SHUFFLE_THRESHOLD = 5;
0097 private static final int FILL_THRESHOLD = 25;
0098 private static final int ROTATE_THRESHOLD = 100;
0099 private static final int COPY_THRESHOLD = 10;
0100 private static final int REPLACEALL_THRESHOLD = 11;
0101 private static final int INDEXOFSUBLIST_THRESHOLD = 35;
0102
0103 /**
0104 * Sorts the specified list into ascending order, according to the
0105 * <i>natural ordering</i> of its elements. All elements in the list must
0106 * implement the <tt>Comparable</tt> interface. Furthermore, all elements
0107 * in the list must be <i>mutually comparable</i> (that is,
0108 * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
0109 * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
0110 *
0111 * This sort is guaranteed to be <i>stable</i>: equal elements will
0112 * not be reordered as a result of the sort.<p>
0113 *
0114 * The specified list must be modifiable, but need not be resizable.<p>
0115 *
0116 * The sorting algorithm is a modified mergesort (in which the merge is
0117 * omitted if the highest element in the low sublist is less than the
0118 * lowest element in the high sublist). This algorithm offers guaranteed
0119 * n log(n) performance.
0120 *
0121 * This implementation dumps the specified list into an array, sorts
0122 * the array, and iterates over the list resetting each element
0123 * from the corresponding position in the array. This avoids the
0124 * n<sup>2</sup> log(n) performance that would result from attempting
0125 * to sort a linked list in place.
0126 *
0127 * @param list the list to be sorted.
0128 * @throws ClassCastException if the list contains elements that are not
0129 * <i>mutually comparable</i> (for example, strings and integers).
0130 * @throws UnsupportedOperationException if the specified list's
0131 * list-iterator does not support the <tt>set</tt> operation.
0132 * @see Comparable
0133 */
0134 public static <T extends Comparable<? super T>> void sort(
0135 List<T> list) {
0136 Object[] a = list.toArray();
0137 Arrays.sort(a);
0138 ListIterator<T> i = list.listIterator();
0139 for (int j = 0; j < a.length; j++) {
0140 i.next();
0141 i.set((T) a[j]);
0142 }
0143 }
0144
0145 /**
0146 * Sorts the specified list according to the order induced by the
0147 * specified comparator. All elements in the list must be <i>mutually
0148 * comparable</i> using the specified comparator (that is,
0149 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
0150 * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
0151 *
0152 * This sort is guaranteed to be <i>stable</i>: equal elements will
0153 * not be reordered as a result of the sort.<p>
0154 *
0155 * The sorting algorithm is a modified mergesort (in which the merge is
0156 * omitted if the highest element in the low sublist is less than the
0157 * lowest element in the high sublist). This algorithm offers guaranteed
0158 * n log(n) performance.
0159 *
0160 * The specified list must be modifiable, but need not be resizable.
0161 * This implementation dumps the specified list into an array, sorts
0162 * the array, and iterates over the list resetting each element
0163 * from the corresponding position in the array. This avoids the
0164 * n<sup>2</sup> log(n) performance that would result from attempting
0165 * to sort a linked list in place.
0166 *
0167 * @param list the list to be sorted.
0168 * @param c the comparator to determine the order of the list. A
0169 * <tt>null</tt> value indicates that the elements' <i>natural
0170 * ordering</i> should be used.
0171 * @throws ClassCastException if the list contains elements that are not
0172 * <i>mutually comparable</i> using the specified comparator.
0173 * @throws UnsupportedOperationException if the specified list's
0174 * list-iterator does not support the <tt>set</tt> operation.
0175 * @see Comparator
0176 */
0177 public static <T> void sort(List<T> list, Comparator<? super T> c) {
0178 Object[] a = list.toArray();
0179 Arrays.sort(a, (Comparator) c);
0180 ListIterator i = list.listIterator();
0181 for (int j = 0; j < a.length; j++) {
0182 i.next();
0183 i.set(a[j]);
0184 }
0185 }
0186
0187 /**
0188 * Searches the specified list for the specified object using the binary
0189 * search algorithm. The list must be sorted into ascending order
0190 * according to the {@linkplain Comparable natural ordering} of its
0191 * elements (as by the {@link #sort(List)} method) prior to making this
0192 * call. If it is not sorted, the results are undefined. If the list
0193 * contains multiple elements equal to the specified object, there is no
0194 * guarantee which one will be found.
0195 *
0196 * <p>This method runs in log(n) time for a "random access" list (which
0197 * provides near-constant-time positional access). If the specified list
0198 * does not implement the {@link RandomAccess} interface and is large,
0199 * this method will do an iterator-based binary search that performs
0200 * O(n) link traversals and O(log n) element comparisons.
0201 *
0202 * @param list the list to be searched.
0203 * @param key the key to be searched for.
0204 * @return the index of the search key, if it is contained in the list;
0205 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
0206 * <i>insertion point</i> is defined as the point at which the
0207 * key would be inserted into the list: the index of the first
0208 * element greater than the key, or <tt>list.size()</tt> if all
0209 * elements in the list are less than the specified key. Note
0210 * that this guarantees that the return value will be >= 0 if
0211 * and only if the key is found.
0212 * @throws ClassCastException if the list contains elements that are not
0213 * <i>mutually comparable</i> (for example, strings and
0214 * integers), or the search key is not mutually comparable
0215 * with the elements of the list.
0216 */
0217 public static <T> int binarySearch(
0218 List<? extends Comparable<? super T>> list, T key) {
0219 if (list instanceof RandomAccess
0220 || list.size() < BINARYSEARCH_THRESHOLD)
0221 return Collections.indexedBinarySearch(list, key);
0222 else
0223 return Collections.iteratorBinarySearch(list, key);
0224 }
0225
0226 private static <T> int indexedBinarySearch(
0227 List<? extends Comparable<? super T>> list, T key) {
0228 int low = 0;
0229 int high = list.size() - 1;
0230
0231 while (low <= high) {
0232 int mid = (low + high) >>> 1;
0233 Comparable<? super T> midVal = list.get(mid);
0234 int cmp = midVal.compareTo(key);
0235
0236 if (cmp < 0)
0237 low = mid + 1;
0238 else if (cmp > 0)
0239 high = mid - 1;
0240 else
0241 return mid; // key found
0242 }
0243 return -(low + 1); // key not found
0244 }
0245
0246 private static <T> int iteratorBinarySearch(
0247 List<? extends Comparable<? super T>> list, T key) {
0248 int low = 0;
0249 int high = list.size() - 1;
0250 ListIterator<? extends Comparable<? super T>> i = list
0251 .listIterator();
0252
0253 while (low <= high) {
0254 int mid = (low + high) >>> 1;
0255 Comparable<? super T> midVal = get(i, mid);
0256 int cmp = midVal.compareTo(key);
0257
0258 if (cmp < 0)
0259 low = mid + 1;
0260 else if (cmp > 0)
0261 high = mid - 1;
0262 else
0263 return mid; // key found
0264 }
0265 return -(low + 1); // key not found
0266 }
0267
0268 /**
0269 * Gets the ith element from the given list by repositioning the specified
0270 * list listIterator.
0271 */
0272 private static <T> T get(ListIterator<? extends T> i, int index) {
0273 T obj = null;
0274 int pos = i.nextIndex();
0275 if (pos <= index) {
0276 do {
0277 obj = i.next();
0278 } while (pos++ < index);
0279 } else {
0280 do {
0281 obj = i.previous();
0282 } while (--pos > index);
0283 }
0284 return obj;
0285 }
0286
0287 /**
0288 * Searches the specified list for the specified object using the binary
0289 * search algorithm. The list must be sorted into ascending order
0290 * according to the specified comparator (as by the
0291 * {@link #sort(List, Comparator) sort(List, Comparator)}
0292 * method), prior to making this call. If it is
0293 * not sorted, the results are undefined. If the list contains multiple
0294 * elements equal to the specified object, there is no guarantee which one
0295 * will be found.
0296 *
0297 * <p>This method runs in log(n) time for a "random access" list (which
0298 * provides near-constant-time positional access). If the specified list
0299 * does not implement the {@link RandomAccess} interface and is large,
0300 * this method will do an iterator-based binary search that performs
0301 * O(n) link traversals and O(log n) element comparisons.
0302 *
0303 * @param list the list to be searched.
0304 * @param key the key to be searched for.
0305 * @param c the comparator by which the list is ordered.
0306 * A <tt>null</tt> value indicates that the elements'
0307 * {@linkplain Comparable natural ordering} should be used.
0308 * @return the index of the search key, if it is contained in the list;
0309 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
0310 * <i>insertion point</i> is defined as the point at which the
0311 * key would be inserted into the list: the index of the first
0312 * element greater than the key, or <tt>list.size()</tt> if all
0313 * elements in the list are less than the specified key. Note
0314 * that this guarantees that the return value will be >= 0 if
0315 * and only if the key is found.
0316 * @throws ClassCastException if the list contains elements that are not
0317 * <i>mutually comparable</i> using the specified comparator,
0318 * or the search key is not mutually comparable with the
0319 * elements of the list using this comparator.
0320 */
0321 public static <T> int binarySearch(List<? extends T> list, T key,
0322 Comparator<? super T> c) {
0323 if (c == null)
0324 return binarySearch((List) list, key);
0325
0326 if (list instanceof RandomAccess
0327 || list.size() < BINARYSEARCH_THRESHOLD)
0328 return Collections.indexedBinarySearch(list, key, c);
0329 else
0330 return Collections.iteratorBinarySearch(list, key, c);
0331 }
0332
0333 private static <T> int indexedBinarySearch(List<? extends T> l,
0334 T key, Comparator<? super T> c) {
0335 int low = 0;
0336 int high = l.size() - 1;
0337
0338 while (low <= high) {
0339 int mid = (low + high) >>> 1;
0340 T midVal = l.get(mid);
0341 int cmp = c.compare(midVal, key);
0342
0343 if (cmp < 0)
0344 low = mid + 1;
0345 else if (cmp > 0)
0346 high = mid - 1;
0347 else
0348 return mid; // key found
0349 }
0350 return -(low + 1); // key not found
0351 }
0352
0353 private static <T> int iteratorBinarySearch(List<? extends T> l,
0354 T key, Comparator<? super T> c) {
0355 int low = 0;
0356 int high = l.size() - 1;
0357 ListIterator<? extends T> i = l.listIterator();
0358
0359 while (low <= high) {
0360 int mid = (low + high) >>> 1;
0361 T midVal = get(i, mid);
0362 int cmp = c.compare(midVal, key);
0363
0364 if (cmp < 0)
0365 low = mid + 1;
0366 else if (cmp > 0)
0367 high = mid - 1;
0368 else
0369 return mid; // key found
0370 }
0371 return -(low + 1); // key not found
0372 }
0373
0374 private interface SelfComparable extends Comparable<SelfComparable> {
0375 }
0376
0377 /**
0378 * Reverses the order of the elements in the specified list.<p>
0379 *
0380 * This method runs in linear time.
0381 *
0382 * @param list the list whose elements are to be reversed.
0383 * @throws UnsupportedOperationException if the specified list or
0384 * its list-iterator does not support the <tt>set</tt> operation.
0385 */
0386 public static void reverse(List<?> list) {
0387 int size = list.size();
0388 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
0389 for (int i = 0, mid = size >> 1, j = size - 1; i < mid; i++, j--)
0390 swap(list, i, j);
0391 } else {
0392 ListIterator fwd = list.listIterator();
0393 ListIterator rev = list.listIterator(size);
0394 for (int i = 0, mid = list.size() >> 1; i < mid; i++) {
0395 Object tmp = fwd.next();
0396 fwd.set(rev.previous());
0397 rev.set(tmp);
0398 }
0399 }
0400 }
0401
0402 /**
0403 * Randomly permutes the specified list using a default source of
0404 * randomness. All permutations occur with approximately equal
0405 * likelihood.<p>
0406 *
0407 * The hedge "approximately" is used in the foregoing description because
0408 * default source of randomness is only approximately an unbiased source
0409 * of independently chosen bits. If it were a perfect source of randomly
0410 * chosen bits, then the algorithm would choose permutations with perfect
0411 * uniformity.<p>
0412 *
0413 * This implementation traverses the list backwards, from the last element
0414 * up to the second, repeatedly swapping a randomly selected element into
0415 * the "current position". Elements are randomly selected from the
0416 * portion of the list that runs from the first element to the current
0417 * position, inclusive.<p>
0418 *
0419 * This method runs in linear time. If the specified list does not
0420 * implement the {@link RandomAccess} interface and is large, this
0421 * implementation dumps the specified list into an array before shuffling
0422 * it, and dumps the shuffled array back into the list. This avoids the
0423 * quadratic behavior that would result from shuffling a "sequential
0424 * access" list in place.
0425 *
0426 * @param list the list to be shuffled.
0427 * @throws UnsupportedOperationException if the specified list or
0428 * its list-iterator does not support the <tt>set</tt> operation.
0429 */
0430 public static void shuffle(List<?> list) {
0431 if (r == null) {
0432 r = new Random();
0433 }
0434 shuffle(list, r);
0435 }
0436
0437 private static Random r;
0438
0439 /**
0440 * Randomly permute the specified list using the specified source of
0441 * randomness. All permutations occur with equal likelihood
0442 * assuming that the source of randomness is fair.<p>
0443 *
0444 * This implementation traverses the list backwards, from the last element
0445 * up to the second, repeatedly swapping a randomly selected element into
0446 * the "current position". Elements are randomly selected from the
0447 * portion of the list that runs from the first element to the current
0448 * position, inclusive.<p>
0449 *
0450 * This method runs in linear time. If the specified list does not
0451 * implement the {@link RandomAccess} interface and is large, this
0452 * implementation dumps the specified list into an array before shuffling
0453 * it, and dumps the shuffled array back into the list. This avoids the
0454 * quadratic behavior that would result from shuffling a "sequential
0455 * access" list in place.
0456 *
0457 * @param list the list to be shuffled.
0458 * @param rnd the source of randomness to use to shuffle the list.
0459 * @throws UnsupportedOperationException if the specified list or its
0460 * list-iterator does not support the <tt>set</tt> operation.
0461 */
0462 public static void shuffle(List<?> list, Random rnd) {
0463 int size = list.size();
0464 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
0465 for (int i = size; i > 1; i--)
0466 swap(list, i - 1, rnd.nextInt(i));
0467 } else {
0468 Object arr[] = list.toArray();
0469
0470 // Shuffle array
0471 for (int i = size; i > 1; i--)
0472 swap(arr, i - 1, rnd.nextInt(i));
0473
0474 // Dump array back into list
0475 ListIterator it = list.listIterator();
0476 for (int i = 0; i < arr.length; i++) {
0477 it.next();
0478 it.set(arr[i]);
0479 }
0480 }
0481 }
0482
0483 /**
0484 * Swaps the elements at the specified positions in the specified list.
0485 * (If the specified positions are equal, invoking this method leaves
0486 * the list unchanged.)
0487 *
0488 * @param list The list in which to swap elements.
0489 * @param i the index of one element to be swapped.
0490 * @param j the index of the other element to be swapped.
0491 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
0492 * is out of range (i < 0 || i >= list.size()
0493 * || j < 0 || j >= list.size()).
0494 * @since 1.4
0495 */
0496 public static void swap(List<?> list, int i, int j) {
0497 final List l = list;
0498 l.set(i, l.set(j, l.get(i)));
0499 }
0500
0501 /**
0502 * Swaps the two specified elements in the specified array.
0503 */
0504 private static void swap(Object[] arr, int i, int j) {
0505 Object tmp = arr[i];
0506 arr[i] = arr[j];
0507 arr[j] = tmp;
0508 }
0509
0510 /**
0511 * Replaces all of the elements of the specified list with the specified
0512 * element. <p>
0513 *
0514 * This method runs in linear time.
0515 *
0516 * @param list the list to be filled with the specified element.
0517 * @param obj The element with which to fill the specified list.
0518 * @throws UnsupportedOperationException if the specified list or its
0519 * list-iterator does not support the <tt>set</tt> operation.
0520 */
0521 public static <T> void fill(List<? super T> list, T obj) {
0522 int size = list.size();
0523
0524 if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
0525 for (int i = 0; i < size; i++)
0526 list.set(i, obj);
0527 } else {
0528 ListIterator<? super T> itr = list.listIterator();
0529 for (int i = 0; i < size; i++) {
0530 itr.next();
0531 itr.set(obj);
0532 }
0533 }
0534 }
0535
0536 /**
0537 * Copies all of the elements from one list into another. After the
0538 * operation, the index of each copied element in the destination list
0539 * will be identical to its index in the source list. The destination
0540 * list must be at least as long as the source list. If it is longer, the
0541 * remaining elements in the destination list are unaffected. <p>
0542 *
0543 * This method runs in linear time.
0544 *
0545 * @param dest The destination list.
0546 * @param src The source list.
0547 * @throws IndexOutOfBoundsException if the destination list is too small
0548 * to contain the entire source List.
0549 * @throws UnsupportedOperationException if the destination list's
0550 * list-iterator does not support the <tt>set</tt> operation.
0551 */
0552 public static <T> void copy(List<? super T> dest,
0553 List<? extends T> src) {
0554 int srcSize = src.size();
0555 if (srcSize > dest.size())
0556 throw new IndexOutOfBoundsException(
0557 "Source does not fit in dest");
0558
0559 if (srcSize < COPY_THRESHOLD
0560 || (src instanceof RandomAccess && dest instanceof RandomAccess)) {
0561 for (int i = 0; i < srcSize; i++)
0562 dest.set(i, src.get(i));
0563 } else {
0564 ListIterator<? super T> di = dest.listIterator();
0565 ListIterator<? extends T> si = src.listIterator();
0566 for (int i = 0; i < srcSize; i++) {
0567 di.next();
0568 di.set(si.next());
0569 }
0570 }
0571 }
0572
0573 /**
0574 * Returns the minimum element of the given collection, according to the
0575 * <i>natural ordering</i> of its elements. All elements in the
0576 * collection must implement the <tt>Comparable</tt> interface.
0577 * Furthermore, all elements in the collection must be <i>mutually
0578 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
0579 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0580 * <tt>e2</tt> in the collection).<p>
0581 *
0582 * This method iterates over the entire collection, hence it requires
0583 * time proportional to the size of the collection.
0584 *
0585 * @param coll the collection whose minimum element is to be determined.
0586 * @return the minimum element of the given collection, according
0587 * to the <i>natural ordering</i> of its elements.
0588 * @throws ClassCastException if the collection contains elements that are
0589 * not <i>mutually comparable</i> (for example, strings and
0590 * integers).
0591 * @throws NoSuchElementException if the collection is empty.
0592 * @see Comparable
0593 */
0594 public static <T extends Object & Comparable<? super T>> T min(
0595 Collection<? extends T> coll) {
0596 Iterator<? extends T> i = coll.iterator();
0597 T candidate = i.next();
0598
0599 while (i.hasNext()) {
0600 T next = i.next();
0601 if (next.compareTo(candidate) < 0)
0602 candidate = next;
0603 }
0604 return candidate;
0605 }
0606
0607 /**
0608 * Returns the minimum element of the given collection, according to the
0609 * order induced by the specified comparator. All elements in the
0610 * collection must be <i>mutually comparable</i> by the specified
0611 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
0612 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0613 * <tt>e2</tt> in the collection).<p>
0614 *
0615 * This method iterates over the entire collection, hence it requires
0616 * time proportional to the size of the collection.
0617 *
0618 * @param coll the collection whose minimum element is to be determined.
0619 * @param comp the comparator with which to determine the minimum element.
0620 * A <tt>null</tt> value indicates that the elements' <i>natural
0621 * ordering</i> should be used.
0622 * @return the minimum element of the given collection, according
0623 * to the specified comparator.
0624 * @throws ClassCastException if the collection contains elements that are
0625 * not <i>mutually comparable</i> using the specified comparator.
0626 * @throws NoSuchElementException if the collection is empty.
0627 * @see Comparable
0628 */
0629 public static <T> T min(Collection<? extends T> coll,
0630 Comparator<? super T> comp) {
0631 if (comp == null)
0632 return (T) min((Collection<SelfComparable>) (Collection) coll);
0633
0634 Iterator<? extends T> i = coll.iterator();
0635 T candidate = i.next();
0636
0637 while (i.hasNext()) {
0638 T next = i.next();
0639 if (comp.compare(next, candidate) < 0)
0640 candidate = next;
0641 }
0642 return candidate;
0643 }
0644
0645 /**
0646 * Returns the maximum element of the given collection, according to the
0647 * <i>natural ordering</i> of its elements. All elements in the
0648 * collection must implement the <tt>Comparable</tt> interface.
0649 * Furthermore, all elements in the collection must be <i>mutually
0650 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
0651 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0652 * <tt>e2</tt> in the collection).<p>
0653 *
0654 * This method iterates over the entire collection, hence it requires
0655 * time proportional to the size of the collection.
0656 *
0657 * @param coll the collection whose maximum element is to be determined.
0658 * @return the maximum element of the given collection, according
0659 * to the <i>natural ordering</i> of its elements.
0660 * @throws ClassCastException if the collection contains elements that are
0661 * not <i>mutually comparable</i> (for example, strings and
0662 * integers).
0663 * @throws NoSuchElementException if the collection is empty.
0664 * @see Comparable
0665 */
0666 public static <T extends Object & Comparable<? super T>> T max(
0667 Collection<? extends T> coll) {
0668 Iterator<? extends T> i = coll.iterator();
0669 T candidate = i.next();
0670
0671 while (i.hasNext()) {
0672 T next = i.next();
0673 if (next.compareTo(candidate) > 0)
0674 candidate = next;
0675 }
0676 return candidate;
0677 }
0678
0679 /**
0680 * Returns the maximum element of the given collection, according to the
0681 * order induced by the specified comparator. All elements in the
0682 * collection must be <i>mutually comparable</i> by the specified
0683 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
0684 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0685 * <tt>e2</tt> in the collection).<p>
0686 *
0687 * This method iterates over the entire collection, hence it requires
0688 * time proportional to the size of the collection.
0689 *
0690 * @param coll the collection whose maximum element is to be determined.
0691 * @param comp the comparator with which to determine the maximum element.
0692 * A <tt>null</tt> value indicates that the elements' <i>natural
0693 * ordering</i> should be used.
0694 * @return the maximum element of the given collection, according
0695 * to the specified comparator.
0696 * @throws ClassCastException if the collection contains elements that are
0697 * not <i>mutually comparable</i> using the specified comparator.
0698 * @throws NoSuchElementException if the collection is empty.
0699 * @see Comparable
0700 */
0701 public static <T> T max(Collection<? extends T> coll,
0702 Comparator<? super T> comp) {
0703 if (comp == null)
0704 return (T) max((Collection<SelfComparable>) (Collection) coll);
0705
0706 Iterator<? extends T> i = coll.iterator();
0707 T candidate = i.next();
0708
0709 while (i.hasNext()) {
0710 T next = i.next();
0711 if (comp.compare(next, candidate) > 0)
0712 candidate = next;
0713 }
0714 return candidate;
0715 }
0716
0717 /**
0718 * Rotates the elements in the specified list by the specified distance.
0719 * After calling this method, the element at index <tt>i</tt> will be
0720 * the element previously at index <tt>(i - distance)</tt> mod
0721 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
0722 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
0723 * the size of the list.)
0724 *
0725 * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
0726 * After invoking <tt>Collections.rotate(list, 1)</tt> (or
0727 * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
0728 * <tt>[s, t, a, n, k]</tt>.
0729 *
0730 * <p>Note that this method can usefully be applied to sublists to
0731 * move one or more elements within a list while preserving the
0732 * order of the remaining elements. For example, the following idiom
0733 * moves the element at index <tt>j</tt> forward to position
0734 * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
0735 * <pre>
0736 * Collections.rotate(list.subList(j, k+1), -1);
0737 * </pre>
0738 * To make this concrete, suppose <tt>list</tt> comprises
0739 * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt>
0740 * (<tt>b</tt>) forward two positions, perform the following invocation:
0741 * <pre>
0742 * Collections.rotate(l.subList(1, 4), -1);
0743 * </pre>
0744 * The resulting list is <tt>[a, c, d, b, e]</tt>.
0745 *
0746 * <p>To move more than one element forward, increase the absolute value
0747 * of the rotation distance. To move elements backward, use a positive
0748 * shift distance.
0749 *
0750 * <p>If the specified list is small or implements the {@link
0751 * RandomAccess} interface, this implementation exchanges the first
0752 * element into the location it should go, and then repeatedly exchanges
0753 * the displaced element into the location it should go until a displaced
0754 * element is swapped into the first element. If necessary, the process
0755 * is repeated on the second and successive elements, until the rotation
0756 * is complete. If the specified list is large and doesn't implement the
0757 * <tt>RandomAccess</tt> interface, this implementation breaks the
0758 * list into two sublist views around index <tt>-distance mod size</tt>.
0759 * Then the {@link #reverse(List)} method is invoked on each sublist view,
0760 * and finally it is invoked on the entire list. For a more complete
0761 * description of both algorithms, see Section 2.3 of Jon Bentley's
0762 * <i>Programming Pearls</i> (Addison-Wesley, 1986).
0763 *
0764 * @param list the list to be rotated.
0765 * @param distance the distance to rotate the list. There are no
0766 * constraints on this value; it may be zero, negative, or
0767 * greater than <tt>list.size()</tt>.
0768 * @throws UnsupportedOperationException if the specified list or
0769 * its list-iterator does not support the <tt>set</tt> operation.
0770 * @since 1.4
0771 */
0772 public static void rotate(List<?> list, int distance) {
0773 if (list instanceof RandomAccess
0774 || list.size() < ROTATE_THRESHOLD)
0775 rotate1(list, distance);
0776 else
0777 rotate2(list, distance);
0778 }
0779
0780 private static <T> void rotate1(List<T> list, int distance) {
0781 int size = list.size();
0782 if (size == 0)
0783 return;
0784 distance = distance % size;
0785 if (distance < 0)
0786 distance += size;
0787 if (distance == 0)
0788 return;
0789
0790 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
0791 T displaced = list.get(cycleStart);
0792 int i = cycleStart;
0793 do {
0794 i += distance;
0795 if (i >= size)
0796 i -= size;
0797 displaced = list.set(i, displaced);
0798 nMoved++;
0799 } while (i != cycleStart);
0800 }
0801 }
0802
0803 private static void rotate2(List<?> list, int distance) {
0804 int size = list.size();
0805 if (size == 0)
0806 return;
0807 int mid = -distance % size;
0808 if (mid < 0)
0809 mid += size;
0810 if (mid == 0)
0811 return;
0812
0813 reverse(list.subList(0, mid));
0814 reverse(list.subList(mid, size));
0815 reverse(list);
0816 }
0817
0818 /**
0819 * Replaces all occurrences of one specified value in a list with another.
0820 * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
0821 * in <tt>list</tt> such that
0822 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
0823 * (This method has no effect on the size of the list.)
0824 *
0825 * @param list the list in which replacement is to occur.
0826 * @param oldVal the old value to be replaced.
0827 * @param newVal the new value with which <tt>oldVal</tt> is to be
0828 * replaced.
0829 * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
0830 * <tt>e</tt> such that
0831 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
0832 * @throws UnsupportedOperationException if the specified list or
0833 * its list-iterator does not support the <tt>set</tt> operation.
0834 * @since 1.4
0835 */
0836 public static <T> boolean replaceAll(List<T> list, T oldVal,
0837 T newVal) {
0838 boolean result = false;
0839 int size = list.size();
0840 if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
0841 if (oldVal == null) {
0842 for (int i = 0; i < size; i++) {
0843 if (list.get(i) == null) {
0844 list.set(i, newVal);
0845 result = true;
0846 }
0847 }
0848 } else {
0849 for (int i = 0; i < size; i++) {
0850 if (oldVal.equals(list.get(i))) {
0851 list.set(i, newVal);
0852 result = true;
0853 }
0854 }
0855 }
0856 } else {
0857 ListIterator<T> itr = list.listIterator();
0858 if (oldVal == null) {
0859 for (int i = 0; i < size; i++) {
0860 if (itr.next() == null) {
0861 itr.set(newVal);
0862 result = true;
0863 }
0864 }
0865 } else {
0866 for (int i = 0; i < size; i++) {
0867 if (oldVal.equals(itr.next())) {
0868 itr.set(newVal);
0869 result = true;
0870 }
0871 }
0872 }
0873 }
0874 return result;
0875 }
0876
0877 /**
0878 * Returns the starting position of the first occurrence of the specified
0879 * target list within the specified source list, or -1 if there is no
0880 * such occurrence. More formally, returns the lowest index <tt>i</tt>
0881 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
0882 * or -1 if there is no such index. (Returns -1 if
0883 * <tt>target.size() > source.size()</tt>.)
0884 *
0885 * <p>This implementation uses the "brute force" technique of scanning
0886 * over the source list, looking for a match with the target at each
0887 * location in turn.
0888 *
0889 * @param source the list in which to search for the first occurrence
0890 * of <tt>target</tt>.
0891 * @param target the list to search for as a subList of <tt>source</tt>.
0892 * @return the starting position of the first occurrence of the specified
0893 * target list within the specified source list, or -1 if there
0894 * is no such occurrence.
0895 * @since 1.4
0896 */
0897 public static int indexOfSubList(List<?> source, List<?> target) {
0898 int sourceSize = source.size();
0899 int targetSize = target.size();
0900 int maxCandidate = sourceSize - targetSize;
0901
0902 if (sourceSize < INDEXOFSUBLIST_THRESHOLD
0903 || (source instanceof RandomAccess && target instanceof RandomAccess)) {
0904 nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
0905 for (int i = 0, j = candidate; i < targetSize; i++, j++)
0906 if (!eq(target.get(i), source.get(j)))
0907 continue nextCand; // Element mismatch, try next cand
0908 return candidate; // All elements of candidate matched target
0909 }
0910 } else { // Iterator version of above algorithm
0911 ListIterator<?> si = source.listIterator();
0912 nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
0913 ListIterator<?> ti = target.listIterator();
0914 for (int i = 0; i < targetSize; i++) {
0915 if (!eq(ti.next(), si.next())) {
0916 // Back up source iterator to next candidate
0917 for (int j = 0; j < i; j++)
0918 si.previous();
0919 continue nextCand;
0920 }
0921 }
0922 return candidate;
0923 }
0924 }
0925 return -1; // No candidate matched the target
0926 }
0927
0928 /**
0929 * Returns the starting position of the last occurrence of the specified
0930 * target list within the specified source list, or -1 if there is no such
0931 * occurrence. More formally, returns the highest index <tt>i</tt>
0932 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
0933 * or -1 if there is no such index. (Returns -1 if
0934 * <tt>target.size() > source.size()</tt>.)
0935 *
0936 * <p>This implementation uses the "brute force" technique of iterating
0937 * over the source list, looking for a match with the target at each
0938 * location in turn.
0939 *
0940 * @param source the list in which to search for the last occurrence
0941 * of <tt>target</tt>.
0942 * @param target the list to search for as a subList of <tt>source</tt>.
0943 * @return the starting position of the last occurrence of the specified
0944 * target list within the specified source list, or -1 if there
0945 * is no such occurrence.
0946 * @since 1.4
0947 */
0948 public static int lastIndexOfSubList(List<?> source, List<?> target) {
0949 int sourceSize = source.size();
0950 int targetSize = target.size();
0951 int maxCandidate = sourceSize - targetSize;
0952
0953 if (sourceSize < INDEXOFSUBLIST_THRESHOLD
0954 || source instanceof RandomAccess) { // Index access version
0955 nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) {
0956 for (int i = 0, j = candidate; i < targetSize; i++, j++)
0957 if (!eq(target.get(i), source.get(j)))
0958 continue nextCand; // Element mismatch, try next cand
0959 return candidate; // All elements of candidate matched target
0960 }
0961 } else { // Iterator version of above algorithm
0962 if (maxCandidate < 0)
0963 return -1;
0964 ListIterator<?> si = source.listIterator(maxCandidate);
0965 nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) {
0966 ListIterator<?> ti = target.listIterator();
0967 for (int i = 0; i < targetSize; i++) {
0968 if (!eq(ti.next(), si.next())) {
0969 if (candidate != 0) {
0970 // Back up source iterator to next candidate
0971 for (int j = 0; j <= i + 1; j++)
0972 si.previous();
0973 }
0974 continue nextCand;
0975 }
0976 }
0977 return candidate;
0978 }
0979 }
0980 return -1; // No candidate matched the target
0981 }
0982
0983 // Unmodifiable Wrappers
0984
0985 /**
0986 * Returns an unmodifiable view of the specified collection. This method
0987 * allows modules to provide users with "read-only" access to internal
0988 * collections. Query operations on the returned collection "read through"
0989 * to the specified collection, and attempts to modify the returned
0990 * collection, whether direct or via its iterator, result in an
0991 * <tt>UnsupportedOperationException</tt>.<p>
0992 *
0993 * The returned collection does <i>not</i> pass the hashCode and equals
0994 * operations through to the backing collection, but relies on
0995 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
0996 * is necessary to preserve the contracts of these operations in the case
0997 * that the backing collection is a set or a list.<p>
0998 *
0999 * The returned collection will be serializable if the specified collection
1000 * is serializable.
1001 *
1002 * @param c the collection for which an unmodifiable view is to be
1003 * returned.
1004 * @return an unmodifiable view of the specified collection.
1005 */
1006 public static <T> Collection<T> unmodifiableCollection(
1007 Collection<? extends T> c) {
1008 return new UnmodifiableCollection<T>(c);
1009 }
1010
1011 /**
1012 * @serial include
1013 */
1014 static class UnmodifiableCollection<E> implements Collection<E>,
1015 Serializable {
1016 private static final long serialVersionUID = 1820017752578914078L;
1017
1018 final Collection<? extends E> c;
1019
1020 UnmodifiableCollection(Collection<? extends E> c) {
1021 if (c == null)
1022 throw new NullPointerException();
1023 this .c = c;
1024 }
1025
1026 public int size() {
1027 return c.size();
1028 }
1029
1030 public boolean isEmpty() {
1031 return c.isEmpty();
1032 }
1033
1034 public boolean contains(Object o) {
1035 return c.contains(o);
1036 }
1037
1038 public Object[] toArray() {
1039 return c.toArray();
1040 }
1041
1042 public <T> T[] toArray(T[] a) {
1043 return c.toArray(a);
1044 }
1045
1046 public String toString() {
1047 return c.toString();
1048 }
1049
1050 public Iterator<E> iterator() {
1051 return new Iterator<E>() {
1052 private final Iterator<? extends E> i = c.iterator();
1053
1054 public boolean hasNext() {
1055 return i.hasNext();
1056 }
1057
1058 public E next() {
1059 return i.next();
1060 }
1061
1062 public void remove() {
1063 throw new UnsupportedOperationException();
1064 }
1065 };
1066 }
1067
1068 public boolean add(E e) {
1069 throw new UnsupportedOperationException();
1070 }
1071
1072 public boolean remove(Object o) {
1073 throw new UnsupportedOperationException();
1074 }
1075
1076 public boolean containsAll(Collection<?> coll) {
1077 return c.containsAll(coll);
1078 }
1079
1080 public boolean addAll(Collection<? extends E> coll) {
1081 throw new UnsupportedOperationException();
1082 }
1083
1084 public boolean removeAll(Collection<?> coll) {
1085 throw new UnsupportedOperationException();
1086 }
1087
1088 public boolean retainAll(Collection<?> coll) {
1089 throw new UnsupportedOperationException();
1090 }
1091
1092 public void clear() {
1093 throw new UnsupportedOperationException();
1094 }
1095 }
1096
1097 /**
1098 * Returns an unmodifiable view of the specified set. This method allows
1099 * modules to provide users with "read-only" access to internal sets.
1100 * Query operations on the returned set "read through" to the specified
1101 * set, and attempts to modify the returned set, whether direct or via its
1102 * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1103 *
1104 * The returned set will be serializable if the specified set
1105 * is serializable.
1106 *
1107 * @param s the set for which an unmodifiable view is to be returned.
1108 * @return an unmodifiable view of the specified set.
1109 */
1110 public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1111 return new UnmodifiableSet<T>(s);
1112 }
1113
1114 /**
1115 * @serial include
1116 */
1117 static class UnmodifiableSet<E> extends UnmodifiableCollection<E>
1118 implements Set<E>, Serializable {
1119 private static final long serialVersionUID = -9215047833775013803L;
1120
1121 UnmodifiableSet(Set<? extends E> s) {
1122 super (s);
1123 }
1124
1125 public boolean equals(Object o) {
1126 return o == this || c.equals(o);
1127 }
1128
1129 public int hashCode() {
1130 return c.hashCode();
1131 }
1132 }
1133
1134 /**
1135 * Returns an unmodifiable view of the specified sorted set. This method
1136 * allows modules to provide users with "read-only" access to internal
1137 * sorted sets. Query operations on the returned sorted set "read
1138 * through" to the specified sorted set. Attempts to modify the returned
1139 * sorted set, whether direct, via its iterator, or via its
1140 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1141 * an <tt>UnsupportedOperationException</tt>.<p>
1142 *
1143 * The returned sorted set will be serializable if the specified sorted set
1144 * is serializable.
1145 *
1146 * @param s the sorted set for which an unmodifiable view is to be
1147 * returned.
1148 * @return an unmodifiable view of the specified sorted set.
1149 */
1150 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
1151 return new UnmodifiableSortedSet<T>(s);
1152 }
1153
1154 /**
1155 * @serial include
1156 */
1157 static class UnmodifiableSortedSet<E> extends UnmodifiableSet<E>
1158 implements SortedSet<E>, Serializable {
1159 private static final long serialVersionUID = -4929149591599911165L;
1160 private final SortedSet<E> ss;
1161
1162 UnmodifiableSortedSet(SortedSet<E> s) {
1163 super (s);
1164 ss = s;
1165 }
1166
1167 public Comparator<? super E> comparator() {
1168 return ss.comparator();
1169 }
1170
1171 public SortedSet<E> subSet(E fromElement, E toElement) {
1172 return new UnmodifiableSortedSet<E>(ss.subSet(fromElement,
1173 toElement));
1174 }
1175
1176 public SortedSet<E> headSet(E toElement) {
1177 return new UnmodifiableSortedSet<E>(ss.headSet(toElement));
1178 }
1179
1180 public SortedSet<E> tailSet(E fromElement) {
1181 return new UnmodifiableSortedSet<E>(ss.tailSet(fromElement));
1182 }
1183
1184 public E first() {
1185 return ss.first();
1186 }
1187
1188 public E last() {
1189 return ss.last();
1190 }
1191 }
1192
1193 /**
1194 * Returns an unmodifiable view of the specified list. This method allows
1195 * modules to provide users with "read-only" access to internal
1196 * lists. Query operations on the returned list "read through" to the
1197 * specified list, and attempts to modify the returned list, whether
1198 * direct or via its iterator, result in an
1199 * <tt>UnsupportedOperationException</tt>.<p>
1200 *
1201 * The returned list will be serializable if the specified list
1202 * is serializable. Similarly, the returned list will implement
1203 * {@link RandomAccess} if the specified list does.
1204 *
1205 * @param list the list for which an unmodifiable view is to be returned.
1206 * @return an unmodifiable view of the specified list.
1207 */
1208 public static <T> List<T> unmodifiableList(List<? extends T> list) {
1209 return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList<T>(
1210 list)
1211 : new UnmodifiableList<T>(list));
1212 }
1213
1214 /**
1215 * @serial include
1216 */
1217 static class UnmodifiableList<E> extends UnmodifiableCollection<E>
1218 implements List<E> {
1219 private static final long serialVersionUID = -283967356065247728L;
1220 final List<? extends E> list;
1221
1222 UnmodifiableList(List<? extends E> list) {
1223 super (list);
1224 this .list = list;
1225 }
1226
1227 public boolean equals(Object o) {
1228 return o == this || list.equals(o);
1229 }
1230
1231 public int hashCode() {
1232 return list.hashCode();
1233 }
1234
1235 public E get(int index) {
1236 return list.get(index);
1237 }
1238
1239 public E set(int index, E element) {
1240 throw new UnsupportedOperationException();
1241 }
1242
1243 public void add(int index, E element) {
1244 throw new UnsupportedOperationException();
1245 }
1246
1247 public E remove(int index) {
1248 throw new UnsupportedOperationException();
1249 }
1250
1251 public int indexOf(Object o) {
1252 return list.indexOf(o);
1253 }
1254
1255 public int lastIndexOf(Object o) {
1256 return list.lastIndexOf(o);
1257 }
1258
1259 public boolean addAll(int index, Collection<? extends E> c) {
1260 throw new UnsupportedOperationException();
1261 }
1262
1263 public ListIterator<E> listIterator() {
1264 return listIterator(0);
1265 }
1266
1267 public ListIterator<E> listIterator(final int index) {
1268 return new ListIterator<E>() {
1269 private final ListIterator<? extends E> i = list
1270 .listIterator(index);
1271
1272 public boolean hasNext() {
1273 return i.hasNext();
1274 }
1275
1276 public E next() {
1277 return i.next();
1278 }
1279
1280 public boolean hasPrevious() {
1281 return i.hasPrevious();
1282 }
1283
1284 public E previous() {
1285 return i.previous();
1286 }
1287
1288 public int nextIndex() {
1289 return i.nextIndex();
1290 }
1291
1292 public int previousIndex() {
1293 return i.previousIndex();
1294 }
1295
1296 public void remove() {
1297 throw new UnsupportedOperationException();
1298 }
1299
1300 public void set(E e) {
1301 throw new UnsupportedOperationException();
1302 }
1303
1304 public void add(E e) {
1305 throw new UnsupportedOperationException();
1306 }
1307 };
1308 }
1309
1310 public List<E> subList(int fromIndex, int toIndex) {
1311 return new UnmodifiableList<E>(list.subList(fromIndex,
1312 toIndex));
1313 }
1314
1315 /**
1316 * UnmodifiableRandomAccessList instances are serialized as
1317 * UnmodifiableList instances to allow them to be deserialized
1318 * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
1319 * This method inverts the transformation. As a beneficial
1320 * side-effect, it also grafts the RandomAccess marker onto
1321 * UnmodifiableList instances that were serialized in pre-1.4 JREs.
1322 *
1323 * Note: Unfortunately, UnmodifiableRandomAccessList instances
1324 * serialized in 1.4.1 and deserialized in 1.4 will become
1325 * UnmodifiableList instances, as this method was missing in 1.4.
1326 */
1327 private Object readResolve() {
1328 return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList<E>(
1329 list)
1330 : this );
1331 }
1332 }
1333
1334 /**
1335 * @serial include
1336 */
1337 static class UnmodifiableRandomAccessList<E> extends
1338 UnmodifiableList<E> implements RandomAccess {
1339 UnmodifiableRandomAccessList(List<? extends E> list) {
1340 super (list);
1341 }
1342
1343 public List<E> subList(int fromIndex, int toIndex) {
1344 return new UnmodifiableRandomAccessList<E>(list.subList(
1345 fromIndex, toIndex));
1346 }
1347
1348 private static final long serialVersionUID = -2542308836966382001L;
1349
1350 /**
1351 * Allows instances to be deserialized in pre-1.4 JREs (which do
1352 * not have UnmodifiableRandomAccessList). UnmodifiableList has
1353 * a readResolve method that inverts this transformation upon
1354 * deserialization.
1355 */
1356 private Object writeReplace() {
1357 return new UnmodifiableList<E>(list);
1358 }
1359 }
1360
1361 /**
1362 * Returns an unmodifiable view of the specified map. This method
1363 * allows modules to provide users with "read-only" access to internal
1364 * maps. Query operations on the returned map "read through"
1365 * to the specified map, and attempts to modify the returned
1366 * map, whether direct or via its collection views, result in an
1367 * <tt>UnsupportedOperationException</tt>.<p>
1368 *
1369 * The returned map will be serializable if the specified map
1370 * is serializable.
1371 *
1372 * @param m the map for which an unmodifiable view is to be returned.
1373 * @return an unmodifiable view of the specified map.
1374 */
1375 public static <K, V> Map<K, V> unmodifiableMap(
1376 Map<? extends K, ? extends V> m) {
1377 return new UnmodifiableMap<K, V>(m);
1378 }
1379
1380 /**
1381 * @serial include
1382 */
1383 private static class UnmodifiableMap<K, V> implements Map<K, V>,
1384 Serializable {
1385 private static final long serialVersionUID = -1034234728574286014L;
1386
1387 private final Map<? extends K, ? extends V> m;
1388
1389 UnmodifiableMap(Map<? extends K, ? extends V> m) {
1390 if (m == null)
1391 throw new NullPointerException();
1392 this .m = m;
1393 }
1394
1395 public int size() {
1396 return m.size();
1397 }
1398
1399 public boolean isEmpty() {
1400 return m.isEmpty();
1401 }
1402
1403 public boolean containsKey(Object key) {
1404 return m.containsKey(key);
1405 }
1406
1407 public boolean containsValue(Object val) {
1408 return m.containsValue(val);
1409 }
1410
1411 public V get(Object key) {
1412 return m.get(key);
1413 }
1414
1415 public V put(K key, V value) {
1416 throw new UnsupportedOperationException();
1417 }
1418
1419 public V remove(Object key) {
1420 throw new UnsupportedOperationException();
1421 }
1422
1423 public void putAll(Map<? extends K, ? extends V> m) {
1424 throw new UnsupportedOperationException();
1425 }
1426
1427 public void clear() {
1428 throw new UnsupportedOperationException();
1429 }
1430
1431 private transient Set<K> keySet = null;
1432 private transient Set<Map.Entry<K, V>> entrySet = null;
1433 private transient Collection<V> values = null;
1434
1435 public Set<K> keySet() {
1436 if (keySet == null)
1437 keySet = unmodifiableSet(m.keySet());
1438 return keySet;
1439 }
1440
1441 public Set<Map.Entry<K, V>> entrySet() {
1442 if (entrySet == null)
1443 entrySet = new UnmodifiableEntrySet<K, V>(m.entrySet());
1444 return entrySet;
1445 }
1446
1447 public Collection<V> values() {
1448 if (values == null)
1449 values = unmodifiableCollection(m.values());
1450 return values;
1451 }
1452
1453 public boolean equals(Object o) {
1454 return o == this || m.equals(o);
1455 }
1456
1457 public int hashCode() {
1458 return m.hashCode();
1459 }
1460
1461 public String toString() {
1462 return m.toString();
1463 }
1464
1465 /**
1466 * We need this class in addition to UnmodifiableSet as
1467 * Map.Entries themselves permit modification of the backing Map
1468 * via their setValue operation. This class is subtle: there are
1469 * many possible attacks that must be thwarted.
1470 *
1471 * @serial include
1472 */
1473 static class UnmodifiableEntrySet<K, V> extends
1474 UnmodifiableSet<Map.Entry<K, V>> {
1475 private static final long serialVersionUID = 7854390611657943733L;
1476
1477 UnmodifiableEntrySet(
1478 Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1479 super ((Set) s);
1480 }
1481
1482 public Iterator<Map.Entry<K, V>> iterator() {
1483 return new Iterator<Map.Entry<K, V>>() {
1484 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c
1485 .iterator();
1486
1487 public boolean hasNext() {
1488 return i.hasNext();
1489 }
1490
1491 public Map.Entry<K, V> next() {
1492 return new UnmodifiableEntry<K, V>(i.next());
1493 }
1494
1495 public void remove() {
1496 throw new UnsupportedOperationException();
1497 }
1498 };
1499 }
1500
1501 public Object[] toArray() {
1502 Object[] a = c.toArray();
1503 for (int i = 0; i < a.length; i++)
1504 a[i] = new UnmodifiableEntry<K, V>(
1505 (Map.Entry<K, V>) a[i]);
1506 return a;
1507 }
1508
1509 public <T> T[] toArray(T[] a) {
1510 // We don't pass a to c.toArray, to avoid window of
1511 // vulnerability wherein an unscrupulous multithreaded client
1512 // could get his hands on raw (unwrapped) Entries from c.
1513 Object[] arr = c.toArray(a.length == 0 ? a : Arrays
1514 .copyOf(a, 0));
1515
1516 for (int i = 0; i < arr.length; i++)
1517 arr[i] = new UnmodifiableEntry<K, V>(
1518 (Map.Entry<K, V>) arr[i]);
1519
1520 if (arr.length > a.length)
1521 return (T[]) arr;
1522
1523 System.arraycopy(arr, 0, a, 0, arr.length);
1524 if (a.length > arr.length)
1525 a[arr.length] = null;
1526 return a;
1527 }
1528
1529 /**
1530 * This method is overridden to protect the backing set against
1531 * an object with a nefarious equals function that senses
1532 * that the equality-candidate is Map.Entry and calls its
1533 * setValue method.
1534 */
1535 public boolean contains(Object o) {
1536 if (!(o instanceof Map.Entry))
1537 return false;
1538 return c.contains(new UnmodifiableEntry<K, V>(
1539 (Map.Entry<K, V>) o));
1540 }
1541
1542 /**
1543 * The next two methods are overridden to protect against
1544 * an unscrupulous List whose contains(Object o) method senses
1545 * when o is a Map.Entry, and calls o.setValue.
1546 */
1547 public boolean containsAll(Collection<?> coll) {
1548 Iterator<?> e = coll.iterator();
1549 while (e.hasNext())
1550 if (!contains(e.next())) // Invokes safe contains() above
1551 return false;
1552 return true;
1553 }
1554
1555 public boolean equals(Object o) {
1556 if (o == this )
1557 return true;
1558
1559 if (!(o instanceof Set))
1560 return false;
1561 Set s = (Set) o;
1562 if (s.size() != c.size())
1563 return false;
1564 return containsAll(s); // Invokes safe containsAll() above
1565 }
1566
1567 /**
1568 * This "wrapper class" serves two purposes: it prevents
1569 * the client from modifying the backing Map, by short-circuiting
1570 * the setValue method, and it protects the backing Map against
1571 * an ill-behaved Map.Entry that attempts to modify another
1572 * Map Entry when asked to perform an equality check.
1573 */
1574 private static class UnmodifiableEntry<K, V> implements
1575 Map.Entry<K, V> {
1576 private Map.Entry<? extends K, ? extends V> e;
1577
1578 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {
1579 this .e = e;
1580 }
1581
1582 public K getKey() {
1583 return e.getKey();
1584 }
1585
1586 public V getValue() {
1587 return e.getValue();
1588 }
1589
1590 public V setValue(V value) {
1591 throw new UnsupportedOperationException();
1592 }
1593
1594 public int hashCode() {
1595 return e.hashCode();
1596 }
1597
1598 public boolean equals(Object o) {
1599 if (!(o instanceof Map.Entry))
1600 return false;
1601 Map.Entry t = (Map.Entry) o;
1602 return eq(e.getKey(), t.getKey())
1603 && eq(e.getValue(), t.getValue());
1604 }
1605
1606 public String toString() {
1607 return e.toString();
1608 }
1609 }
1610 }
1611 }
1612
1613 /**
1614 * Returns an unmodifiable view of the specified sorted map. This method
1615 * allows modules to provide users with "read-only" access to internal
1616 * sorted maps. Query operations on the returned sorted map "read through"
1617 * to the specified sorted map. Attempts to modify the returned
1618 * sorted map, whether direct, via its collection views, or via its
1619 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1620 * an <tt>UnsupportedOperationException</tt>.<p>
1621 *
1622 * The returned sorted map will be serializable if the specified sorted map
1623 * is serializable.
1624 *
1625 * @param m the sorted map for which an unmodifiable view is to be
1626 * returned.
1627 * @return an unmodifiable view of the specified sorted map.
1628 */
1629 public static <K, V> SortedMap<K, V> unmodifiableSortedMap(
1630 SortedMap<K, ? extends V> m) {
1631 return new UnmodifiableSortedMap<K, V>(m);
1632 }
1633
1634 /**
1635 * @serial include
1636 */
1637 static class UnmodifiableSortedMap<K, V> extends
1638 UnmodifiableMap<K, V> implements SortedMap<K, V>,
1639 Serializable {
1640 private static final long serialVersionUID = -8806743815996713206L;
1641
1642 private final SortedMap<K, ? extends V> sm;
1643
1644 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {
1645 super (m);
1646 sm = m;
1647 }
1648
1649 public Comparator<? super K> comparator() {
1650 return sm.comparator();
1651 }
1652
1653 public SortedMap<K, V> subMap(K fromKey, K toKey) {
1654 return new UnmodifiableSortedMap<K, V>(sm.subMap(fromKey,
1655 toKey));
1656 }
1657
1658 public SortedMap<K, V> headMap(K toKey) {
1659 return new UnmodifiableSortedMap<K, V>(sm.headMap(toKey));
1660 }
1661
1662 public SortedMap<K, V> tailMap(K fromKey) {
1663 return new UnmodifiableSortedMap<K, V>(sm.tailMap(fromKey));
1664 }
1665
1666 public K firstKey() {
1667 return sm.firstKey();
1668 }
1669
1670 public K lastKey() {
1671 return sm.lastKey();
1672 }
1673 }
1674
1675 // Synch Wrappers
1676
1677 /**
1678 * Returns a synchronized (thread-safe) collection backed by the specified
1679 * collection. In order to guarantee serial access, it is critical that
1680 * <strong>all</strong> access to the backing collection is accomplished
1681 * through the returned collection.<p>
1682 *
1683 * It is imperative that the user manually synchronize on the returned
1684 * collection when iterating over it:
1685 * <pre>
1686 * Collection c = Collections.synchronizedCollection(myCollection);
1687 * ...
1688 * synchronized(c) {
1689 * Iterator i = c.iterator(); // Must be in the synchronized block
1690 * while (i.hasNext())
1691 * foo(i.next());
1692 * }
1693 * </pre>
1694 * Failure to follow this advice may result in non-deterministic behavior.
1695 *
1696 * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1697 * and <tt>equals</tt> operations through to the backing collection, but
1698 * relies on <tt>Object</tt>'s equals and hashCode methods. This is
1699 * necessary to preserve the contracts of these operations in the case
1700 * that the backing collection is a set or a list.<p>
1701 *
1702 * The returned collection will be serializable if the specified collection
1703 * is serializable.
1704 *
1705 * @param c the collection to be "wrapped" in a synchronized collection.
1706 * @return a synchronized view of the specified collection.
1707 */
1708 public static <T> Collection<T> synchronizedCollection(
1709 Collection<T> c) {
1710 return new SynchronizedCollection<T>(c);
1711 }
1712
1713 static <T> Collection<T> synchronizedCollection(Collection<T> c,
1714 Object mutex) {
1715 return new SynchronizedCollection<T>(c, mutex);
1716 }
1717
1718 /**
1719 * @serial include
1720 */
1721 static class SynchronizedCollection<E> implements Collection<E>,
1722 Serializable {
1723 private static final long serialVersionUID = 3053995032091335093L;
1724
1725 final Collection<E> c; // Backing Collection
1726 final Object mutex; // Object on which to synchronize
1727
1728 SynchronizedCollection(Collection<E> c) {
1729 if (c == null)
1730 throw new NullPointerException();
1731 this .c = c;
1732 mutex = this ;
1733 }
1734
1735 SynchronizedCollection(Collection<E> c, Object mutex) {
1736 this .c = c;
1737 this .mutex = mutex;
1738 }
1739
1740 public int size() {
1741 synchronized (mutex) {
1742 return c.size();
1743 }
1744 }
1745
1746 public boolean isEmpty() {
1747 synchronized (mutex) {
1748 return c.isEmpty();
1749 }
1750 }
1751
1752 public boolean contains(Object o) {
1753 synchronized (mutex) {
1754 return c.contains(o);
1755 }
1756 }
1757
1758 public Object[] toArray() {
1759 synchronized (mutex) {
1760 return c.toArray();
1761 }
1762 }
1763
1764 public <T> T[] toArray(T[] a) {
1765 synchronized (mutex) {
1766 return c.toArray(a);
1767 }
1768 }
1769
1770 public Iterator<E> iterator() {
1771 return c.iterator(); // Must be manually synched by user!
1772 }
1773
1774 public boolean add(E e) {
1775 synchronized (mutex) {
1776 return c.add(e);
1777 }
1778 }
1779
1780 public boolean remove(Object o) {
1781 synchronized (mutex) {
1782 return c.remove(o);
1783 }
1784 }
1785
1786 public boolean containsAll(Collection<?> coll) {
1787 synchronized (mutex) {
1788 return c.containsAll(coll);
1789 }
1790 }
1791
1792 public boolean addAll(Collection<? extends E> coll) {
1793 synchronized (mutex) {
1794 return c.addAll(coll);
1795 }
1796 }
1797
1798 public boolean removeAll(Collection<?> coll) {
1799 synchronized (mutex) {
1800 return c.removeAll(coll);
1801 }
1802 }
1803
1804 public boolean retainAll(Collection<?> coll) {
1805 synchronized (mutex) {
1806 return c.retainAll(coll);
1807 }
1808 }
1809
1810 public void clear() {
1811 synchronized (mutex) {
1812 c.clear();
1813 }
1814 }
1815
1816 public String toString() {
1817 synchronized (mutex) {
1818 return c.toString();
1819 }
1820 }
1821
1822 private void writeObject(ObjectOutputStream s)
1823 throws IOException {
1824 synchronized (mutex) {
1825 s.defaultWriteObject();
1826 }
1827 }
1828 }
1829
1830 /**
1831 * Returns a synchronized (thread-safe) set backed by the specified
1832 * set. In order to guarantee serial access, it is critical that
1833 * <strong>all</strong> access to the backing set is accomplished
1834 * through the returned set.<p>
1835 *
1836 * It is imperative that the user manually synchronize on the returned
1837 * set when iterating over it:
1838 * <pre>
1839 * Set s = Collections.synchronizedSet(new HashSet());
1840 * ...
1841 * synchronized(s) {
1842 * Iterator i = s.iterator(); // Must be in the synchronized block
1843 * while (i.hasNext())
1844 * foo(i.next());
1845 * }
1846 * </pre>
1847 * Failure to follow this advice may result in non-deterministic behavior.
1848 *
1849 * <p>The returned set will be serializable if the specified set is
1850 * serializable.
1851 *
1852 * @param s the set to be "wrapped" in a synchronized set.
1853 * @return a synchronized view of the specified set.
1854 */
1855 public static <T> Set<T> synchronizedSet(Set<T> s) {
1856 return new SynchronizedSet<T>(s);
1857 }
1858
1859 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) {
1860 return new SynchronizedSet<T>(s, mutex);
1861 }
1862
1863 /**
1864 * @serial include
1865 */
1866 static class SynchronizedSet<E> extends SynchronizedCollection<E>
1867 implements Set<E> {
1868 private static final long serialVersionUID = 487447009682186044L;
1869
1870 SynchronizedSet(Set<E> s) {
1871 super (s);
1872 }
1873
1874 SynchronizedSet(Set<E> s, Object mutex) {
1875 super (s, mutex);
1876 }
1877
1878 public boolean equals(Object o) {
1879 synchronized (mutex) {
1880 return c.equals(o);
1881 }
1882 }
1883
1884 public int hashCode() {
1885 synchronized (mutex) {
1886 return c.hashCode();
1887 }
1888 }
1889 }
1890
1891 /**
1892 * Returns a synchronized (thread-safe) sorted set backed by the specified
1893 * sorted set. In order to guarantee serial access, it is critical that
1894 * <strong>all</strong> access to the backing sorted set is accomplished
1895 * through the returned sorted set (or its views).<p>
1896 *
1897 * It is imperative that the user manually synchronize on the returned
1898 * sorted set when iterating over it or any of its <tt>subSet</tt>,
1899 * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1900 * <pre>
1901 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1902 * ...
1903 * synchronized(s) {
1904 * Iterator i = s.iterator(); // Must be in the synchronized block
1905 * while (i.hasNext())
1906 * foo(i.next());
1907 * }
1908 * </pre>
1909 * or:
1910 * <pre>
1911 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1912 * SortedSet s2 = s.headSet(foo);
1913 * ...
1914 * synchronized(s) { // Note: s, not s2!!!
1915 * Iterator i = s2.iterator(); // Must be in the synchronized block
1916 * while (i.hasNext())
1917 * foo(i.next());
1918 * }
1919 * </pre>
1920 * Failure to follow this advice may result in non-deterministic behavior.
1921 *
1922 * <p>The returned sorted set will be serializable if the specified
1923 * sorted set is serializable.
1924 *
1925 * @param s the sorted set to be "wrapped" in a synchronized sorted set.
1926 * @return a synchronized view of the specified sorted set.
1927 */
1928 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
1929 return new SynchronizedSortedSet<T>(s);
1930 }
1931
1932 /**
1933 * @serial include
1934 */
1935 static class SynchronizedSortedSet<E> extends SynchronizedSet<E>
1936 implements SortedSet<E> {
1937 private static final long serialVersionUID = 8695801310862127406L;
1938
1939 final private SortedSet<E> ss;
1940
1941 SynchronizedSortedSet(SortedSet<E> s) {
1942 super (s);
1943 ss = s;
1944 }
1945
1946 SynchronizedSortedSet(SortedSet<E> s, Object mutex) {
1947 super (s, mutex);
1948 ss = s;
1949 }
1950
1951 public Comparator<? super E> comparator() {
1952 synchronized (mutex) {
1953 return ss.comparator();
1954 }
1955 }
1956
1957 public SortedSet<E> subSet(E fromElement, E toElement) {
1958 synchronized (mutex) {
1959 return new SynchronizedSortedSet<E>(ss.subSet(
1960 fromElement, toElement), mutex);
1961 }
1962 }
1963
1964 public SortedSet<E> headSet(E toElement) {
1965 synchronized (mutex) {
1966 return new SynchronizedSortedSet<E>(ss
1967 .headSet(toElement), mutex);
1968 }
1969 }
1970
1971 public SortedSet<E> tailSet(E fromElement) {
1972 synchronized (mutex) {
1973 return new SynchronizedSortedSet<E>(ss
1974 .tailSet(fromElement), mutex);
1975 }
1976 }
1977
1978 public E first() {
1979 synchronized (mutex) {
1980 return ss.first();
1981 }
1982 }
1983
1984 public E last() {
1985 synchronized (mutex) {
1986 return ss.last();
1987 }
1988 }
1989 }
1990
1991 /**
1992 * Returns a synchronized (thread-safe) list backed by the specified
1993 * list. In order to guarantee serial access, it is critical that
1994 * <strong>all</strong> access to the backing list is accomplished
1995 * through the returned list.<p>
1996 *
1997 * It is imperative that the user manually synchronize on the returned
1998 * list when iterating over it:
1999 * <pre>
2000 * List list = Collections.synchronizedList(new ArrayList());
2001 * ...
2002 * synchronized(list) {
2003 * Iterator i = list.iterator(); // Must be in synchronized block
2004 * while (i.hasNext())
2005 * foo(i.next());
2006 * }
2007 * </pre>
2008 * Failure to follow this advice may result in non-deterministic behavior.
2009 *
2010 * <p>The returned list will be serializable if the specified list is
2011 * serializable.
2012 *
2013 * @param list the list to be "wrapped" in a synchronized list.
2014 * @return a synchronized view of the specified list.
2015 */
2016 public static <T> List<T> synchronizedList(List<T> list) {
2017 return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<T>(
2018 list)
2019 : new SynchronizedList<T>(list));
2020 }
2021
2022 static <T> List<T> synchronizedList(List<T> list, Object mutex) {
2023 return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<T>(
2024 list, mutex)
2025 : new SynchronizedList<T>(list, mutex));
2026 }
2027
2028 /**
2029 * @serial include
2030 */
2031 static class SynchronizedList<E> extends SynchronizedCollection<E>
2032 implements List<E> {
2033 private static final long serialVersionUID = -7754090372962971524L;
2034
2035 final List<E> list;
2036
2037 SynchronizedList(List<E> list) {
2038 super (list);
2039 this .list = list;
2040 }
2041
2042 SynchronizedList(List<E> list, Object mutex) {
2043 super (list, mutex);
2044 this .list = list;
2045 }
2046
2047 public boolean equals(Object o) {
2048 synchronized (mutex) {
2049 return list.equals(o);
2050 }
2051 }
2052
2053 public int hashCode() {
2054 synchronized (mutex) {
2055 return list.hashCode();
2056 }
2057 }
2058
2059 public E get(int index) {
2060 synchronized (mutex) {
2061 return list.get(index);
2062 }
2063 }
2064
2065 public E set(int index, E element) {
2066 synchronized (mutex) {
2067 return list.set(index, element);
2068 }
2069 }
2070
2071 public void add(int index, E element) {
2072 synchronized (mutex) {
2073 list.add(index, element);
2074 }
2075 }
2076
2077 public E remove(int index) {
2078 synchronized (mutex) {
2079 return list.remove(index);
2080 }
2081 }
2082
2083 public int indexOf(Object o) {
2084 synchronized (mutex) {
2085 return list.indexOf(o);
2086 }
2087 }
2088
2089 public int lastIndexOf(Object o) {
2090 synchronized (mutex) {
2091 return list.lastIndexOf(o);
2092 }
2093 }
2094
2095 public boolean addAll(int index, Collection<? extends E> c) {
2096 synchronized (mutex) {
2097 return list.addAll(index, c);
2098 }
2099 }
2100
2101 public ListIterator<E> listIterator() {
2102 return list.listIterator(); // Must be manually synched by user
2103 }
2104
2105 public ListIterator<E> listIterator(int index) {
2106 return list.listIterator(index); // Must be manually synched by user
2107 }
2108
2109 public List<E> subList(int fromIndex, int toIndex) {
2110 synchronized (mutex) {
2111 return new SynchronizedList<E>(list.subList(fromIndex,
2112 toIndex), mutex);
2113 }
2114 }
2115
2116 /**
2117 * SynchronizedRandomAccessList instances are serialized as
2118 * SynchronizedList instances to allow them to be deserialized
2119 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
2120 * This method inverts the transformation. As a beneficial
2121 * side-effect, it also grafts the RandomAccess marker onto
2122 * SynchronizedList instances that were serialized in pre-1.4 JREs.
2123 *
2124 * Note: Unfortunately, SynchronizedRandomAccessList instances
2125 * serialized in 1.4.1 and deserialized in 1.4 will become
2126 * SynchronizedList instances, as this method was missing in 1.4.
2127 */
2128 private Object readResolve() {
2129 return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<E>(
2130 list)
2131 : this );
2132 }
2133 }
2134
2135 /**
2136 * @serial include
2137 */
2138 static class SynchronizedRandomAccessList<E> extends
2139 SynchronizedList<E> implements RandomAccess {
2140
2141 SynchronizedRandomAccessList(List<E> list) {
2142 super (list);
2143 }
2144
2145 SynchronizedRandomAccessList(List<E> list, Object mutex) {
2146 super (list, mutex);
2147 }
2148
2149 public List<E> subList(int fromIndex, int toIndex) {
2150 synchronized (mutex) {
2151 return new SynchronizedRandomAccessList<E>(list
2152 .subList(fromIndex, toIndex), mutex);
2153 }
2154 }
2155
2156 private static final long serialVersionUID = 1530674583602358482L;
2157
2158 /**
2159 * Allows instances to be deserialized in pre-1.4 JREs (which do
2160 * not have SynchronizedRandomAccessList). SynchronizedList has
2161 * a readResolve method that inverts this transformation upon
2162 * deserialization.
2163 */
2164 private Object writeReplace() {
2165 return new SynchronizedList<E>(list);
2166 }
2167 }
2168
2169 /**
2170 * Returns a synchronized (thread-safe) map backed by the specified
2171 * map. In order to guarantee serial access, it is critical that
2172 * <strong>all</strong> access to the backing map is accomplished
2173 * through the returned map.<p>
2174 *
2175 * It is imperative that the user manually synchronize on the returned
2176 * map when iterating over any of its collection views:
2177 * <pre>
2178 * Map m = Collections.synchronizedMap(new HashMap());
2179 * ...
2180 * Set s = m.keySet(); // Needn't be in synchronized block
2181 * ...
2182 * synchronized(m) { // Synchronizing on m, not s!
2183 * Iterator i = s.iterator(); // Must be in synchronized block
2184 * while (i.hasNext())
2185 * foo(i.next());
2186 * }
2187 * </pre>
2188 * Failure to follow this advice may result in non-deterministic behavior.
2189 *
2190 * <p>The returned map will be serializable if the specified map is
2191 * serializable.
2192 *
2193 * @param m the map to be "wrapped" in a synchronized map.
2194 * @return a synchronized view of the specified map.
2195 */
2196 public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m) {
2197 return new SynchronizedMap<K, V>(m);
2198 }
2199
2200 /**
2201 * @serial include
2202 */
2203 private static class SynchronizedMap<K, V> implements Map<K, V>,
2204 Serializable {
2205 private static final long serialVersionUID = 1978198479659022715L;
2206
2207 private final Map<K, V> m; // Backing Map
2208 final Object mutex; // Object on which to synchronize
2209
2210 SynchronizedMap(Map<K, V> m) {
2211 if (m == null)
2212 throw new NullPointerException();
2213 this .m = m;
2214 mutex = this ;
2215 }
2216
2217 SynchronizedMap(Map<K, V> m, Object mutex) {
2218 this .m = m;
2219 this .mutex = mutex;
2220 }
2221
2222 public int size() {
2223 synchronized (mutex) {
2224 return m.size();
2225 }
2226 }
2227
2228 public boolean isEmpty() {
2229 synchronized (mutex) {
2230 return m.isEmpty();
2231 }
2232 }
2233
2234 public boolean containsKey(Object key) {
2235 synchronized (mutex) {
2236 return m.containsKey(key);
2237 }
2238 }
2239
2240 public boolean containsValue(Object value) {
2241 synchronized (mutex) {
2242 return m.containsValue(value);
2243 }
2244 }
2245
2246 public V get(Object key) {
2247 synchronized (mutex) {
2248 return m.get(key);
2249 }
2250 }
2251
2252 public V put(K key, V value) {
2253 synchronized (mutex) {
2254 return m.put(key, value);
2255 }
2256 }
2257
2258 public V remove(Object key) {
2259 synchronized (mutex) {
2260 return m.remove(key);
2261 }
2262 }
2263
2264 public void putAll(Map<? extends K, ? extends V> map) {
2265 synchronized (mutex) {
2266 m.putAll(map);
2267 }
2268 }
2269
2270 public void clear() {
2271 synchronized (mutex) {
2272 m.clear();
2273 }
2274 }
2275
2276 private transient Set<K> keySet = null;
2277 private transient Set<Map.Entry<K, V>> entrySet = null;
2278 private transient Collection<V> values = null;
2279
2280 public Set<K> keySet() {
2281 synchronized (mutex) {
2282 if (keySet == null)
2283 keySet = new SynchronizedSet<K>(m.keySet(), mutex);
2284 return keySet;
2285 }
2286 }
2287
2288 public Set<Map.Entry<K, V>> entrySet() {
2289 synchronized (mutex) {
2290 if (entrySet == null)
2291 entrySet = new SynchronizedSet<Map.Entry<K, V>>(m
2292 .entrySet(), mutex);
2293 return entrySet;
2294 }
2295 }
2296
2297 public Collection<V> values() {
2298 synchronized (mutex) {
2299 if (values == null)
2300 values = new SynchronizedCollection<V>(m.values(),
2301 mutex);
2302 return values;
2303 }
2304 }
2305
2306 public boolean equals(Object o) {
2307 synchronized (mutex) {
2308 return m.equals(o);
2309 }
2310 }
2311
2312 public int hashCode() {
2313 synchronized (mutex) {
2314 return m.hashCode();
2315 }
2316 }
2317
2318 public String toString() {
2319 synchronized (mutex) {
2320 return m.toString();
2321 }
2322 }
2323
2324 private void writeObject(ObjectOutputStream s)
2325 throws IOException {
2326 synchronized (mutex) {
2327 s.defaultWriteObject();
2328 }
2329 }
2330 }
2331
2332 /**
2333 * Returns a synchronized (thread-safe) sorted map backed by the specified
2334 * sorted map. In order to guarantee serial access, it is critical that
2335 * <strong>all</strong> access to the backing sorted map is accomplished
2336 * through the returned sorted map (or its views).<p>
2337 *
2338 * It is imperative that the user manually synchronize on the returned
2339 * sorted map when iterating over any of its collection views, or the
2340 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2341 * <tt>tailMap</tt> views.
2342 * <pre>
2343 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2344 * ...
2345 * Set s = m.keySet(); // Needn't be in synchronized block
2346 * ...
2347 * synchronized(m) { // Synchronizing on m, not s!
2348 * Iterator i = s.iterator(); // Must be in synchronized block
2349 * while (i.hasNext())
2350 * foo(i.next());
2351 * }
2352 * </pre>
2353 * or:
2354 * <pre>
2355 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2356 * SortedMap m2 = m.subMap(foo, bar);
2357 * ...
2358 * Set s2 = m2.keySet(); // Needn't be in synchronized block
2359 * ...
2360 * synchronized(m) { // Synchronizing on m, not m2 or s2!
2361 * Iterator i = s.iterator(); // Must be in synchronized block
2362 * while (i.hasNext())
2363 * foo(i.next());
2364 * }
2365 * </pre>
2366 * Failure to follow this advice may result in non-deterministic behavior.
2367 *
2368 * <p>The returned sorted map will be serializable if the specified
2369 * sorted map is serializable.
2370 *
2371 * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2372 * @return a synchronized view of the specified sorted map.
2373 */
2374 public static <K, V> SortedMap<K, V> synchronizedSortedMap(
2375 SortedMap<K, V> m) {
2376 return new SynchronizedSortedMap<K, V>(m);
2377 }
2378
2379 /**
2380 * @serial include
2381 */
2382 static class SynchronizedSortedMap<K, V> extends
2383 SynchronizedMap<K, V> implements SortedMap<K, V> {
2384 private static final long serialVersionUID = -8798146769416483793L;
2385
2386 private final SortedMap<K, V> sm;
2387
2388 SynchronizedSortedMap(SortedMap<K, V> m) {
2389 super (m);
2390 sm = m;
2391 }
2392
2393 SynchronizedSortedMap(SortedMap<K, V> m, Object mutex) {
2394 super (m, mutex);
2395 sm = m;
2396 }
2397
2398 public Comparator<? super K> comparator() {
2399 synchronized (mutex) {
2400 return sm.comparator();
2401 }
2402 }
2403
2404 public SortedMap<K, V> subMap(K fromKey, K toKey) {
2405 synchronized (mutex) {
2406 return new SynchronizedSortedMap<K, V>(sm.subMap(
2407 fromKey, toKey), mutex);
2408 }
2409 }
2410
2411 public SortedMap<K, V> headMap(K toKey) {
2412 synchronized (mutex) {
2413 return new SynchronizedSortedMap<K, V>(sm
2414 .headMap(toKey), mutex);
2415 }
2416 }
2417
2418 public SortedMap<K, V> tailMap(K fromKey) {
2419 synchronized (mutex) {
2420 return new SynchronizedSortedMap<K, V>(sm
2421 .tailMap(fromKey), mutex);
2422 }
2423 }
2424
2425 public K firstKey() {
2426 synchronized (mutex) {
2427 return sm.firstKey();
2428 }
2429 }
2430
2431 public K lastKey() {
2432 synchronized (mutex) {
2433 return sm.lastKey();
2434 }
2435 }
2436 }
2437
2438 // Dynamically typesafe collection wrappers
2439
2440 /**
2441 * Returns a dynamically typesafe view of the specified collection. Any
2442 * attempt to insert an element of the wrong type will result in an
2443 * immediate <tt>ClassCastException</tt>. Assuming a collection contains
2444 * no incorrectly typed elements prior to the time a dynamically typesafe
2445 * view is generated, and that all subsequent access to the collection
2446 * takes place through the view, it is <i>guaranteed</i> that the
2447 * collection cannot contain an incorrectly typed element.
2448 *
2449 * <p>The generics mechanism in the language provides compile-time
2450 * (static) type checking, but it is possible to defeat this mechanism
2451 * with unchecked casts. Usually this is not a problem, as the compiler
2452 * issues warnings on all such unchecked operations. There are, however,
2453 * times when static type checking alone is not sufficient. For example,
2454 * suppose a collection is passed to a third-party library and it is
2455 * imperative that the library code not corrupt the collection by
2456 * inserting an element of the wrong type.
2457 *
2458 * <p>Another use of dynamically typesafe views is debugging. Suppose a
2459 * program fails with a <tt>ClassCastException</tt>, indicating that an
2460 * incorrectly typed element was put into a parameterized collection.
2461 * Unfortunately, the exception can occur at any time after the erroneous
2462 * element is inserted, so it typically provides little or no information
2463 * as to the real source of the problem. If the problem is reproducible,
2464 * one can quickly determine its source by temporarily modifying the
2465 * program to wrap the collection with a dynamically typesafe view.
2466 * For example, this declaration:
2467 * <pre>
2468 * Collection<String> c = new HashSet<String>();
2469 * </pre>
2470 * may be replaced temporarily by this one:
2471 * <pre>
2472 * Collection<String> c = Collections.checkedCollection(
2473 * new HashSet<String>(), String.class);
2474 * </pre>
2475 * Running the program again will cause it to fail at the point where
2476 * an incorrectly typed element is inserted into the collection, clearly
2477 * identifying the source of the problem. Once the problem is fixed, the
2478 * modified declaration may be reverted back to the original.
2479 *
2480 * <p>The returned collection does <i>not</i> pass the hashCode and equals
2481 * operations through to the backing collection, but relies on
2482 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
2483 * is necessary to preserve the contracts of these operations in the case
2484 * that the backing collection is a set or a list.
2485 *
2486 * <p>The returned collection will be serializable if the specified
2487 * collection is serializable.
2488 *
2489 * @param c the collection for which a dynamically typesafe view is to be
2490 * returned
2491 * @param type the type of element that <tt>c</tt> is permitted to hold
2492 * @return a dynamically typesafe view of the specified collection
2493 * @since 1.5
2494 */
2495 public static <E> Collection<E> checkedCollection(Collection<E> c,
2496 Class<E> type) {
2497 return new CheckedCollection<E>(c, type);
2498 }
2499
2500 /**
2501 * @serial include
2502 */
2503 static class CheckedCollection<E> implements Collection<E>,
2504 Serializable {
2505 private static final long serialVersionUID = 1578914078182001775L;
2506
2507 final Collection<E> c;
2508 final Class<E> type;
2509
2510 void typeCheck(Object o) {
2511 if (!type.isInstance(o))
2512 throw new ClassCastException("Attempt to insert "
2513 + o.getClass()
2514 + " element into collection with element type "
2515 + type);
2516 }
2517
2518 CheckedCollection(Collection<E> c, Class<E> type) {
2519 if (c == null || type == null)
2520 throw new NullPointerException();
2521 this .c = c;
2522 this .type = type;
2523 }
2524
2525 public int size() {
2526 return c.size();
2527 }
2528
2529 public boolean isEmpty() {
2530 return c.isEmpty();
2531 }
2532
2533 public boolean contains(Object o) {
2534 return c.contains(o);
2535 }
2536
2537 public Object[] toArray() {
2538 return c.toArray();
2539 }
2540
2541 public <T> T[] toArray(T[] a) {
2542 return c.toArray(a);
2543 }
2544
2545 public String toString() {
2546 return c.toString();
2547 }
2548
2549 public boolean remove(Object o) {
2550 return c.remove(o);
2551 }
2552
2553 public boolean containsAll(Collection<?> coll) {
2554 return c.containsAll(coll);
2555 }
2556
2557 public boolean removeAll(Collection<?> coll) {
2558 return c.removeAll(coll);
2559 }
2560
2561 public boolean retainAll(Collection<?> coll) {
2562 return c.retainAll(coll);
2563 }
2564
2565 public void clear() {
2566 c.clear();
2567 }
2568
2569 public Iterator<E> iterator() {
2570 return new Iterator<E>() {
2571 private final Iterator<E> it = c.iterator();
2572
2573 public boolean hasNext() {
2574 return it.hasNext();
2575 }
2576
2577 public E next() {
2578 return it.next();
2579 }
2580
2581 public void remove() {
2582 it.remove();
2583 }
2584 };
2585 }
2586
2587 public boolean add(E e) {
2588 typeCheck(e);
2589 return c.add(e);
2590 }
2591
2592 public boolean addAll(Collection<? extends E> coll) {
2593 /*
2594 * Dump coll into an array of the required type. This serves
2595 * three purposes: it insulates us from concurrent changes in
2596 * the contents of coll, it type-checks all of the elements in
2597 * coll, and it provides all-or-nothing semantics (which we
2598 * wouldn't get if we type-checked each element as we added it).
2599 */
2600 E[] a = null;
2601 try {
2602 a = coll.toArray(zeroLengthElementArray());
2603 } catch (ArrayStoreException e) {
2604 throw new ClassCastException();
2605 }
2606
2607 return c.addAll(Arrays.asList(a));
2608 }
2609
2610 private E[] zeroLengthElementArray = null; // Lazily initialized
2611
2612 /*
2613 * We don't need locking or volatile, because it's OK if we create
2614 * several zeroLengthElementArrays, and they're immutable.
2615 */
2616 E[] zeroLengthElementArray() {
2617 if (zeroLengthElementArray == null)
2618 zeroLengthElementArray = (E[]) Array.newInstance(type,
2619 0);
2620 return zeroLengthElementArray;
2621 }
2622 }
2623
2624 /**
2625 * Returns a dynamically typesafe view of the specified set.
2626 * Any attempt to insert an element of the wrong type will result in
2627 * an immediate <tt>ClassCastException</tt>. Assuming a set contains
2628 * no incorrectly typed elements prior to the time a dynamically typesafe
2629 * view is generated, and that all subsequent access to the set
2630 * takes place through the view, it is <i>guaranteed</i> that the
2631 * set cannot contain an incorrectly typed element.
2632 *
2633 * <p>A discussion of the use of dynamically typesafe views may be
2634 * found in the documentation for the {@link #checkedCollection checkedCollection}
2635 * method.
2636 *
2637 * <p>The returned set will be serializable if the specified set is
2638 * serializable.
2639 *
2640 * @param s the set for which a dynamically typesafe view is to be
2641 * returned
2642 * @param type the type of element that <tt>s</tt> is permitted to hold
2643 * @return a dynamically typesafe view of the specified set
2644 * @since 1.5
2645 */
2646 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2647 return new CheckedSet<E>(s, type);
2648 }
2649
2650 /**
2651 * @serial include
2652 */
2653 static class CheckedSet<E> extends CheckedCollection<E> implements
2654 Set<E>, Serializable {
2655 private static final long serialVersionUID = 4694047833775013803L;
2656
2657 CheckedSet(Set<E> s, Class<E> elementType) {
2658 super (s, elementType);
2659 }
2660
2661 public boolean equals(Object o) {
2662 return o == this || c.equals(o);
2663 }
2664
2665 public int hashCode() {
2666 return c.hashCode();
2667 }
2668 }
2669
2670 /**
2671 * Returns a dynamically typesafe view of the specified sorted set. Any
2672 * attempt to insert an element of the wrong type will result in an
2673 * immediate <tt>ClassCastException</tt>. Assuming a sorted set contains
2674 * no incorrectly typed elements prior to the time a dynamically typesafe
2675 * view is generated, and that all subsequent access to the sorted set
2676 * takes place through the view, it is <i>guaranteed</i> that the sorted
2677 * set cannot contain an incorrectly typed element.
2678 *
2679 * <p>A discussion of the use of dynamically typesafe views may be
2680 * found in the documentation for the {@link #checkedCollection checkedCollection}
2681 * method.
2682 *
2683 * <p>The returned sorted set will be serializable if the specified sorted
2684 * set is serializable.
2685 *
2686 * @param s the sorted set for which a dynamically typesafe view is to be
2687 * returned
2688 * @param type the type of element that <tt>s</tt> is permitted to hold
2689 * @return a dynamically typesafe view of the specified sorted set
2690 * @since 1.5
2691 */
2692 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
2693 Class<E> type) {
2694 return new CheckedSortedSet<E>(s, type);
2695 }
2696
2697 /**
2698 * @serial include
2699 */
2700 static class CheckedSortedSet<E> extends CheckedSet<E> implements
2701 SortedSet<E>, Serializable {
2702 private static final long serialVersionUID = 1599911165492914959L;
2703 private final SortedSet<E> ss;
2704
2705 CheckedSortedSet(SortedSet<E> s, Class<E> type) {
2706 super (s, type);
2707 ss = s;
2708 }
2709
2710 public Comparator<? super E> comparator() {
2711 return ss.comparator();
2712 }
2713
2714 public E first() {
2715 return ss.first();
2716 }
2717
2718 public E last() {
2719 return ss.last();
2720 }
2721
2722 public SortedSet<E> subSet(E fromElement, E toElement) {
2723 return new CheckedSortedSet<E>(ss.subSet(fromElement,
2724 toElement), type);
2725 }
2726
2727 public SortedSet<E> headSet(E toElement) {
2728 return new CheckedSortedSet<E>(ss.headSet(toElement), type);
2729 }
2730
2731 public SortedSet<E> tailSet(E fromElement) {
2732 return new CheckedSortedSet<E>(ss.tailSet(fromElement),
2733 type);
2734 }
2735 }
2736
2737 /**
2738 * Returns a dynamically typesafe view of the specified list.
2739 * Any attempt to insert an element of the wrong type will result in
2740 * an immediate <tt>ClassCastException</tt>. Assuming a list contains
2741 * no incorrectly typed elements prior to the time a dynamically typesafe
2742 * view is generated, and that all subsequent access to the list
2743 * takes place through the view, it is <i>guaranteed</i> that the
2744 * list cannot contain an incorrectly typed element.
2745 *
2746 * <p>A discussion of the use of dynamically typesafe views may be
2747 * found in the documentation for the {@link #checkedCollection checkedCollection}
2748 * method.
2749 *
2750 * <p>The returned list will be serializable if the specified list is
2751 * serializable.
2752 *
2753 * @param list the list for which a dynamically typesafe view is to be
2754 * returned
2755 * @param type the type of element that <tt>list</tt> is permitted to hold
2756 * @return a dynamically typesafe view of the specified list
2757 * @since 1.5
2758 */
2759 public static <E> List<E> checkedList(List<E> list, Class<E> type) {
2760 return (list instanceof RandomAccess ? new CheckedRandomAccessList<E>(
2761 list, type)
2762 : new CheckedList<E>(list, type));
2763 }
2764
2765 /**
2766 * @serial include
2767 */
2768 static class CheckedList<E> extends CheckedCollection<E> implements
2769 List<E> {
2770 private static final long serialVersionUID = 65247728283967356L;
2771 final List<E> list;
2772
2773 CheckedList(List<E> list, Class<E> type) {
2774 super (list, type);
2775 this .list = list;
2776 }
2777
2778 public boolean equals(Object o) {
2779 return o == this || list.equals(o);
2780 }
2781
2782 public int hashCode() {
2783 return list.hashCode();
2784 }
2785
2786 public E get(int index) {
2787 return list.get(index);
2788 }
2789
2790 public E remove(int index) {
2791 return list.remove(index);
2792 }
2793
2794 public int indexOf(Object o) {
2795 return list.indexOf(o);
2796 }
2797
2798 public int lastIndexOf(Object o) {
2799 return list.lastIndexOf(o);
2800 }
2801
2802 public E set(int index, E element) {
2803 typeCheck(element);
2804 return list.set(index, element);
2805 }
2806
2807 public void add(int index, E element) {
2808 typeCheck(element);
2809 list.add(index, element);
2810 }
2811
2812 public boolean addAll(int index, Collection<? extends E> c) {
2813 // See CheckCollection.addAll, above, for an explanation
2814 E[] a = null;
2815 try {
2816 a = c.toArray(zeroLengthElementArray());
2817 } catch (ArrayStoreException e) {
2818 throw new ClassCastException();
2819 }
2820
2821 return list.addAll(index, Arrays.asList(a));
2822 }
2823
2824 public ListIterator<E> listIterator() {
2825 return listIterator(0);
2826 }
2827
2828 public ListIterator<E> listIterator(final int index) {
2829 return new ListIterator<E>() {
2830 private final ListIterator<E> i = list
2831 .listIterator(index);
2832
2833 public boolean hasNext() {
2834 return i.hasNext();
2835 }
2836
2837 public E next() {
2838 return i.next();
2839 }
2840
2841 public boolean hasPrevious() {
2842 return i.hasPrevious();
2843 }
2844
2845 public E previous() {
2846 return i.previous();
2847 }
2848
2849 public int nextIndex() {
2850 return i.nextIndex();
2851 }
2852
2853 public int previousIndex() {
2854 return i.previousIndex();
2855 }
2856
2857 public void remove() {
2858 i.remove();
2859 }
2860
2861 public void set(E e) {
2862 typeCheck(e);
2863 i.set(e);
2864 }
2865
2866 public void add(E e) {
2867 typeCheck(e);
2868 i.add(e);
2869 }
2870 };
2871 }
2872
2873 public List<E> subList(int fromIndex, int toIndex) {
2874 return new CheckedList<E>(list.subList(fromIndex, toIndex),
2875 type);
2876 }
2877 }
2878
2879 /**
2880 * @serial include
2881 */
2882 static class CheckedRandomAccessList<E> extends CheckedList<E>
2883 implements RandomAccess {
2884 private static final long serialVersionUID = 1638200125423088369L;
2885
2886 CheckedRandomAccessList(List<E> list, Class<E> type) {
2887 super (list, type);
2888 }
2889
2890 public List<E> subList(int fromIndex, int toIndex) {
2891 return new CheckedRandomAccessList<E>(list.subList(
2892 fromIndex, toIndex), type);
2893 }
2894 }
2895
2896 /**
2897 * Returns a dynamically typesafe view of the specified map. Any attempt
2898 * to insert a mapping whose key or value have the wrong type will result
2899 * in an immediate <tt>ClassCastException</tt>. Similarly, any attempt to
2900 * modify the value currently associated with a key will result in an
2901 * immediate <tt>ClassCastException</tt>, whether the modification is
2902 * attempted directly through the map itself, or through a {@link
2903 * Map.Entry} instance obtained from the map's {@link Map#entrySet()
2904 * entry set} view.
2905 *
2906 * <p>Assuming a map contains no incorrectly typed keys or values
2907 * prior to the time a dynamically typesafe view is generated, and
2908 * that all subsequent access to the map takes place through the view
2909 * (or one of its collection views), it is <i>guaranteed</i> that the
2910 * map cannot contain an incorrectly typed key or value.
2911 *
2912 * <p>A discussion of the use of dynamically typesafe views may be
2913 * found in the documentation for the {@link #checkedCollection checkedCollection}
2914 * method.
2915 *
2916 * <p>The returned map will be serializable if the specified map is
2917 * serializable.
2918 *
2919 * @param m the map for which a dynamically typesafe view is to be
2920 * returned
2921 * @param keyType the type of key that <tt>m</tt> is permitted to hold
2922 * @param valueType the type of value that <tt>m</tt> is permitted to hold
2923 * @return a dynamically typesafe view of the specified map
2924 * @since 1.5
2925 */
2926 public static <K, V> Map<K, V> checkedMap(Map<K, V> m,
2927 Class<K> keyType, Class<V> valueType) {
2928 return new CheckedMap<K, V>(m, keyType, valueType);
2929 }
2930
2931 /**
2932 * @serial include
2933 */
2934 private static class CheckedMap<K, V> implements Map<K, V>,
2935 Serializable {
2936 private static final long serialVersionUID = 5742860141034234728L;
2937
2938 private final Map<K, V> m;
2939 final Class<K> keyType;
2940 final Class<V> valueType;
2941
2942 private void typeCheck(Object key, Object value) {
2943 if (!keyType.isInstance(key))
2944 throw new ClassCastException("Attempt to insert "
2945 + key.getClass()
2946 + " key into collection with key type "
2947 + keyType);
2948
2949 if (!valueType.isInstance(value))
2950 throw new ClassCastException("Attempt to insert "
2951 + value.getClass()
2952 + " value into collection with value type "
2953 + valueType);
2954 }
2955
2956 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) {
2957 if (m == null || keyType == null || valueType == null)
2958 throw new NullPointerException();
2959 this .m = m;
2960 this .keyType = keyType;
2961 this .valueType = valueType;
2962 }
2963
2964 public int size() {
2965 return m.size();
2966 }
2967
2968 public boolean isEmpty() {
2969 return m.isEmpty();
2970 }
2971
2972 public boolean containsKey(Object key) {
2973 return m.containsKey(key);
2974 }
2975
2976 public boolean containsValue(Object v) {
2977 return m.containsValue(v);
2978 }
2979
2980 public V get(Object key) {
2981 return m.get(key);
2982 }
2983
2984 public V remove(Object key) {
2985 return m.remove(key);
2986 }
2987
2988 public void clear() {
2989 m.clear();
2990 }
2991
2992 public Set<K> keySet() {
2993 return m.keySet();
2994 }
2995
2996 public Collection<V> values() {
2997 return m.values();
2998 }
2999
3000 public boolean equals(Object o) {
3001 return o == this || m.equals(o);
3002 }
3003
3004 public int hashCode() {
3005 return m.hashCode();
3006 }
3007
3008 public String toString() {
3009 return m.toString();
3010 }
3011
3012 public V put(K key, V value) {
3013 typeCheck(key, value);
3014 return m.put(key, value);
3015 }
3016
3017 public void putAll(Map<? extends K, ? extends V> t) {
3018 // See CheckCollection.addAll, above, for an explanation
3019 K[] keys = null;
3020 try {
3021 keys = t.keySet().toArray(zeroLengthKeyArray());
3022 } catch (ArrayStoreException e) {
3023 throw new ClassCastException();
3024 }
3025 V[] values = null;
3026 try {
3027 values = t.values().toArray(zeroLengthValueArray());
3028 } catch (ArrayStoreException e) {
3029 throw new ClassCastException();
3030 }
3031
3032 if (keys.length != values.length)
3033 throw new ConcurrentModificationException();
3034
3035 for (int i = 0; i < keys.length; i++)
3036 m.put(keys[i], values[i]);
3037 }
3038
3039 // Lazily initialized
3040 private K[] zeroLengthKeyArray = null;
3041 private V[] zeroLengthValueArray = null;
3042
3043 /*
3044 * We don't need locking or volatile, because it's OK if we create
3045 * several zeroLengthValueArrays, and they're immutable.
3046 */
3047 private K[] zeroLengthKeyArray() {
3048 if (zeroLengthKeyArray == null)
3049 zeroLengthKeyArray = (K[]) Array
3050 .newInstance(keyType, 0);
3051 return zeroLengthKeyArray;
3052 }
3053
3054 private V[] zeroLengthValueArray() {
3055 if (zeroLengthValueArray == null)
3056 zeroLengthValueArray = (V[]) Array.newInstance(
3057 valueType, 0);
3058 return zeroLengthValueArray;
3059 }
3060
3061 private transient Set<Map.Entry<K, V>> entrySet = null;
3062
3063 public Set<Map.Entry<K, V>> entrySet() {
3064 if (entrySet == null)
3065 entrySet = new CheckedEntrySet<K, V>(m.entrySet(),
3066 valueType);
3067 return entrySet;
3068 }
3069
3070 /**
3071 * We need this class in addition to CheckedSet as Map.Entry permits
3072 * modification of the backing Map via the setValue operation. This
3073 * class is subtle: there are many possible attacks that must be
3074 * thwarted.
3075 *
3076 * @serial exclude
3077 */
3078 static class CheckedEntrySet<K, V> implements
3079 Set<Map.Entry<K, V>> {
3080 Set<Map.Entry<K, V>> s;
3081 Class<V> valueType;
3082
3083 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) {
3084 this .s = s;
3085 this .valueType = valueType;
3086 }
3087
3088 public int size() {
3089 return s.size();
3090 }
3091
3092 public boolean isEmpty() {
3093 return s.isEmpty();
3094 }
3095
3096 public String toString() {
3097 return s.toString();
3098 }
3099
3100 public int hashCode() {
3101 return s.hashCode();
3102 }
3103
3104 public boolean remove(Object o) {
3105 return s.remove(o);
3106 }
3107
3108 public boolean removeAll(Collection<?> coll) {
3109 return s.removeAll(coll);
3110 }
3111
3112 public boolean retainAll(Collection<?> coll) {
3113 return s.retainAll(coll);
3114 }
3115
3116 public void clear() {
3117 s.clear();
3118 }
3119
3120 public boolean add(Map.Entry<K, V> e) {
3121 throw new UnsupportedOperationException();
3122 }
3123
3124 public boolean addAll(
3125 Collection<? extends Map.Entry<K, V>> coll) {
3126 throw new UnsupportedOperationException();
3127 }
3128
3129 public Iterator<Map.Entry<K, V>> iterator() {
3130 return new Iterator<Map.Entry<K, V>>() {
3131 private final Iterator<Map.Entry<K, V>> i = s
3132 .iterator();
3133
3134 public boolean hasNext() {
3135 return i.hasNext();
3136 }
3137
3138 public void remove() {
3139 i.remove();
3140 }
3141
3142 public Map.Entry<K, V> next() {
3143 return new CheckedEntry<K, V>(i.next(),
3144 valueType);
3145 }
3146 };
3147 }
3148
3149 public Object[] toArray() {
3150 Object[] source = s.toArray();
3151
3152 /*
3153 * Ensure that we don't get an ArrayStoreException even if
3154 * s.toArray returns an array of something other than Object
3155 */
3156 Object[] dest = (CheckedEntry.class.isInstance(source
3157 .getClass().getComponentType()) ? source
3158 : new Object[source.length]);
3159
3160 for (int i = 0; i < source.length; i++)
3161 dest[i] = new CheckedEntry<K, V>(
3162 (Map.Entry<K, V>) source[i], valueType);
3163 return dest;
3164 }
3165
3166 public <T> T[] toArray(T[] a) {
3167 // We don't pass a to s.toArray, to avoid window of
3168 // vulnerability wherein an unscrupulous multithreaded client
3169 // could get his hands on raw (unwrapped) Entries from s.
3170 Object[] arr = s.toArray(a.length == 0 ? a : Arrays
3171 .copyOf(a, 0));
3172
3173 for (int i = 0; i < arr.length; i++)
3174 arr[i] = new CheckedEntry<K, V>(
3175 (Map.Entry<K, V>) arr[i], valueType);
3176 if (arr.length > a.length)
3177 return (T[]) arr;
3178
3179 System.arraycopy(arr, 0, a, 0, arr.length);
3180 if (a.length > arr.length)
3181 a[arr.length] = null;
3182 return a;
3183 }
3184
3185 /**
3186 * This method is overridden to protect the backing set against
3187 * an object with a nefarious equals function that senses
3188 * that the equality-candidate is Map.Entry and calls its
3189 * setValue method.
3190 */
3191 public boolean contains(Object o) {
3192 if (!(o instanceof Map.Entry))
3193 return false;
3194 return s.contains(new CheckedEntry<K, V>(
3195 (Map.Entry<K, V>) o, valueType));
3196 }
3197
3198 /**
3199 * The next two methods are overridden to protect against
3200 * an unscrupulous collection whose contains(Object o) method
3201 * senses when o is a Map.Entry, and calls o.setValue.
3202 */
3203 public boolean containsAll(Collection<?> coll) {
3204 Iterator<?> e = coll.iterator();
3205 while (e.hasNext())
3206 if (!contains(e.next())) // Invokes safe contains() above
3207 return false;
3208 return true;
3209 }
3210
3211 public boolean equals(Object o) {
3212 if (o == this )
3213 return true;
3214 if (!(o instanceof Set))
3215 return false;
3216 Set<?> that = (Set<?>) o;
3217 if (that.size() != s.size())
3218 return false;
3219 return containsAll(that); // Invokes safe containsAll() above
3220 }
3221
3222 /**
3223 * This "wrapper class" serves two purposes: it prevents
3224 * the client from modifying the backing Map, by short-circuiting
3225 * the setValue method, and it protects the backing Map against
3226 * an ill-behaved Map.Entry that attempts to modify another
3227 * Map Entry when asked to perform an equality check.
3228 */
3229 private static class CheckedEntry<K, V> implements
3230 Map.Entry<K, V> {
3231 private Map.Entry<K, V> e;
3232 private Class<V> valueType;
3233
3234 CheckedEntry(Map.Entry<K, V> e, Class<V> valueType) {
3235 this .e = e;
3236 this .valueType = valueType;
3237 }
3238
3239 public K getKey() {
3240 return e.getKey();
3241 }
3242
3243 public V getValue() {
3244 return e.getValue();
3245 }
3246
3247 public int hashCode() {
3248 return e.hashCode();
3249 }
3250
3251 public String toString() {
3252 return e.toString();
3253 }
3254
3255 public V setValue(V value) {
3256 if (!valueType.isInstance(value))
3257 throw new ClassCastException(
3258 "Attempt to insert "
3259 + value.getClass()
3260 + " value into collection with value type "
3261 + valueType);
3262 return e.setValue(value);
3263 }
3264
3265 public boolean equals(Object o) {
3266 if (!(o instanceof Map.Entry))
3267 return false;
3268 Map.Entry t = (Map.Entry) o;
3269 return eq(e.getKey(), t.getKey())
3270 && eq(e.getValue(), t.getValue());
3271 }
3272 }
3273 }
3274 }
3275
3276 /**
3277 * Returns a dynamically typesafe view of the specified sorted map. Any
3278 * attempt to insert a mapping whose key or value have the wrong type will
3279 * result in an immediate <tt>ClassCastException</tt>. Similarly, any
3280 * attempt to modify the value currently associated with a key will result
3281 * in an immediate <tt>ClassCastException</tt>, whether the modification
3282 * is attempted directly through the map itself, or through a {@link
3283 * Map.Entry} instance obtained from the map's {@link Map#entrySet() entry
3284 * set} view.
3285 *
3286 * <p>Assuming a map contains no incorrectly typed keys or values
3287 * prior to the time a dynamically typesafe view is generated, and
3288 * that all subsequent access to the map takes place through the view
3289 * (or one of its collection views), it is <i>guaranteed</i> that the
3290 * map cannot contain an incorrectly typed key or value.
3291 *
3292 * <p>A discussion of the use of dynamically typesafe views may be
3293 * found in the documentation for the {@link #checkedCollection checkedCollection}
3294 * method.
3295 *
3296 * <p>The returned map will be serializable if the specified map is
3297 * serializable.
3298 *
3299 * @param m the map for which a dynamically typesafe view is to be
3300 * returned
3301 * @param keyType the type of key that <tt>m</tt> is permitted to hold
3302 * @param valueType the type of value that <tt>m</tt> is permitted to hold
3303 * @return a dynamically typesafe view of the specified map
3304 * @since 1.5
3305 */
3306 public static <K, V> SortedMap<K, V> checkedSortedMap(
3307 SortedMap<K, V> m, Class<K> keyType, Class<V> valueType) {
3308 return new CheckedSortedMap<K, V>(m, keyType, valueType);
3309 }
3310
3311 /**
3312 * @serial include
3313 */
3314 static class CheckedSortedMap<K, V> extends CheckedMap<K, V>
3315 implements SortedMap<K, V>, Serializable {
3316 private static final long serialVersionUID = 1599671320688067438L;
3317
3318 private final SortedMap<K, V> sm;
3319
3320 CheckedSortedMap(SortedMap<K, V> m, Class<K> keyType,
3321 Class<V> valueType) {
3322 super (m, keyType, valueType);
3323 sm = m;
3324 }
3325
3326 public Comparator<? super K> comparator() {
3327 return sm.comparator();
3328 }
3329
3330 public K firstKey() {
3331 return sm.firstKey();
3332 }
3333
3334 public K lastKey() {
3335 return sm.lastKey();
3336 }
3337
3338 public SortedMap<K, V> subMap(K fromKey, K toKey) {
3339 return new CheckedSortedMap<K, V>(
3340 sm.subMap(fromKey, toKey), keyType, valueType);
3341 }
3342
3343 public SortedMap<K, V> headMap(K toKey) {
3344 return new CheckedSortedMap<K, V>(sm.headMap(toKey),
3345 keyType, valueType);
3346 }
3347
3348 public SortedMap<K, V> tailMap(K fromKey) {
3349 return new CheckedSortedMap<K, V>(sm.tailMap(fromKey),
3350 keyType, valueType);
3351 }
3352 }
3353
3354 // Empty collections
3355
3356 /**
3357 * Returns an iterator that has no elements. More precisely,
3358 *
3359 * <ul compact>
3360 *
3361 * <li>{@link Iterator#hasNext hasNext} always returns {@code
3362 * false}.
3363 *
3364 * <li>{@link Iterator#next next} always throws {@link
3365 * NoSuchElementException}.
3366 *
3367 * <li>{@link Iterator#remove remove} always throws {@link
3368 * IllegalStateException}.
3369 *
3370 * </ul>
3371 *
3372 * <p>Implementations of this method are permitted, but not
3373 * required, to return the same object from multiple invocations.
3374 *
3375 * @return an empty iterator
3376 * @since 1.7
3377 */
3378 @SuppressWarnings("unchecked")
3379 public static <T> Iterator<T> emptyIterator() {
3380 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
3381 }
3382
3383 private static class EmptyIterator<E> implements Iterator<E> {
3384 static final EmptyIterator<Object> EMPTY_ITERATOR = new EmptyIterator<Object>();
3385
3386 public boolean hasNext() {
3387 return false;
3388 }
3389
3390 public E next() {
3391 throw new NoSuchElementException();
3392 }
3393
3394 public void remove() {
3395 throw new IllegalStateException();
3396 }
3397 }
3398
3399 /**
3400 * Returns a list iterator that has no elements. More precisely,
3401 *
3402 * <ul compact>
3403 *
3404 * <li>{@link Iterator#hasNext hasNext} and {@link
3405 * ListIterator#hasPrevious hasPrevious} always return {@code
3406 * false}.
3407 *
3408 * <li>{@link Iterator#next next} and {@link ListIterator#previous
3409 * previous} always throw {@link NoSuchElementException}.
3410 *
3411 * <li>{@link Iterator#remove remove} and {@link ListIterator#set
3412 * set} always throw {@link IllegalStateException}.
3413 *
3414 * <li>{@link ListIterator#add add} always throws {@link
3415 * UnsupportedOperationException}.
3416 *
3417 * <li>{@link ListIterator#nextIndex nextIndex} always returns
3418 * {@code 0} .
3419 *
3420 * <li>{@link ListIterator#previousIndex previousIndex} always
3421 * returns {@code -1}.
3422 *
3423 * </ul>
3424 *
3425 * <p>Implementations of this method are permitted, but not
3426 * required, to return the same object from multiple invocations.
3427 *
3428 * @return an empty list iterator
3429 * @since 1.7
3430 */
3431 @SuppressWarnings("unchecked")
3432 public static <T> ListIterator<T> emptyListIterator() {
3433 return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR;
3434 }
3435
3436 private static class EmptyListIterator<E> extends EmptyIterator<E>
3437 implements ListIterator<E> {
3438 static final EmptyListIterator<Object> EMPTY_ITERATOR = new EmptyListIterator<Object>();
3439
3440 public boolean hasPrevious() {
3441 return false;
3442 }
3443
3444 public E previous() {
3445 throw new NoSuchElementException();
3446 }
3447
3448 public int nextIndex() {
3449 return 0;
3450 }
3451
3452 public int previousIndex() {
3453 return -1;
3454 }
3455
3456 public void set(E e) {
3457 throw new IllegalStateException();
3458 }
3459
3460 public void add(E e) {
3461 throw new UnsupportedOperationException();
3462 }
3463 }
3464
3465 /**
3466 * Returns an enumeration that has no elements. More precisely,
3467 *
3468 * <ul compact>
3469 *
3470 * <li>{@link Enumeration#hasMoreElements hasMoreElements} always
3471 * returns {@code false}.
3472 *
3473 * <li> {@link Enumeration#nextElement nextElement} always throws
3474 * {@link NoSuchElementException}.
3475 *
3476 * </ul>
3477 *
3478 * <p>Implementations of this method are permitted, but not
3479 * required, to return the same object from multiple invocations.
3480 *
3481 * @return an empty enumeration
3482 * @since 1.7
3483 */
3484 @SuppressWarnings("unchecked")
3485 public static <T> Enumeration<T> emptyEnumeration() {
3486 return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
3487 }
3488
3489 private static class EmptyEnumeration<E> implements Enumeration<E> {
3490 static final EmptyEnumeration<Object> EMPTY_ENUMERATION = new EmptyEnumeration<Object>();
3491
3492 public boolean hasMoreElements() {
3493 return false;
3494 }
3495
3496 public E nextElement() {
3497 throw new NoSuchElementException();
3498 }
3499 }
3500
3501 /**
3502 * The empty set (immutable). This set is serializable.
3503 *
3504 * @see #emptySet()
3505 */
3506 @SuppressWarnings("unchecked")
3507 public static final Set EMPTY_SET = new EmptySet<Object>();
3508
3509 /**
3510 * Returns the empty set (immutable). This set is serializable.
3511 * Unlike the like-named field, this method is parameterized.
3512 *
3513 * <p>This example illustrates the type-safe way to obtain an empty set:
3514 * <pre>
3515 * Set<String> s = Collections.emptySet();
3516 * </pre>
3517 * Implementation note: Implementations of this method need not
3518 * create a separate <tt>Set</tt> object for each call. Using this
3519 * method is likely to have comparable cost to using the like-named
3520 * field. (Unlike this method, the field does not provide type safety.)
3521 *
3522 * @see #EMPTY_SET
3523 * @since 1.5
3524 */
3525 @SuppressWarnings("unchecked")
3526 public static final <T> Set<T> emptySet() {
3527 return (Set<T>) EMPTY_SET;
3528 }
3529
3530 /**
3531 * @serial include
3532 */
3533 private static class EmptySet<E> extends AbstractSet<E> implements
3534 Serializable {
3535 private static final long serialVersionUID = 1582296315990362920L;
3536
3537 public Iterator<E> iterator() {
3538 return emptyIterator();
3539 }
3540
3541 public int size() {
3542 return 0;
3543 }
3544
3545 public boolean isEmpty() {
3546 return true;
3547 }
3548
3549 public boolean contains(Object obj) {
3550 return false;
3551 }
3552
3553 public boolean containsAll(Collection<?> c) {
3554 return c.isEmpty();
3555 }
3556
3557 public Object[] toArray() {
3558 return new Object[0];
3559 }
3560
3561 public <T> T[] toArray(T[] a) {
3562 if (a.length > 0)
3563 a[0] = null;
3564 return a;
3565 }
3566
3567 // Preserves singleton property
3568 private Object readResolve() {
3569 return EMPTY_SET;
3570 }
3571 }
3572
3573 /**
3574 * The empty list (immutable). This list is serializable.
3575 *
3576 * @see #emptyList()
3577 */
3578 @SuppressWarnings("unchecked")
3579 public static final List EMPTY_LIST = new EmptyList<Object>();
3580
3581 /**
3582 * Returns the empty list (immutable). This list is serializable.
3583 *
3584 * <p>This example illustrates the type-safe way to obtain an empty list:
3585 * <pre>
3586 * List<String> s = Collections.emptyList();
3587 * </pre>
3588 * Implementation note: Implementations of this method need not
3589 * create a separate <tt>List</tt> object for each call. Using this
3590 * method is likely to have comparable cost to using the like-named
3591 * field. (Unlike this method, the field does not provide type safety.)
3592 *
3593 * @see #EMPTY_LIST
3594 * @since 1.5
3595 */
3596 @SuppressWarnings("unchecked")
3597 public static final <T> List<T> emptyList() {
3598 return (List<T>) EMPTY_LIST;
3599 }
3600
3601 /**
3602 * @serial include
3603 */
3604 private static class EmptyList<E> extends AbstractList<E> implements
3605 RandomAccess, Serializable {
3606 private static final long serialVersionUID = 8842843931221139166L;
3607
3608 public Iterator<E> iterator() {
3609 return emptyIterator();
3610 }
3611
3612 public ListIterator<E> listIterator() {
3613 return emptyListIterator();
3614 }
3615
3616 public int size() {
3617 return 0;
3618 }
3619
3620 public boolean isEmpty() {
3621 return true;
3622 }
3623
3624 public boolean contains(Object obj) {
3625 return false;
3626 }
3627
3628 public boolean containsAll(Collection<?> c) {
3629 return c.isEmpty();
3630 }
3631
3632 public Object[] toArray() {
3633 return new Object[0];
3634 }
3635
3636 public <T> T[] toArray(T[] a) {
3637 if (a.length > 0)
3638 a[0] = null;
3639 return a;
3640 }
3641
3642 public E get(int index) {
3643 throw new IndexOutOfBoundsException("Index: " + index);
3644 }
3645
3646 public boolean equals(Object o) {
3647 return (o instanceof List) && ((List<?>) o).isEmpty();
3648 }
3649
3650 public int hashCode() {
3651 return 1;
3652 }
3653
3654 // Preserves singleton property
3655 private Object readResolve() {
3656 return EMPTY_LIST;
3657 }
3658 }
3659
3660 /**
3661 * The empty map (immutable). This map is serializable.
3662 *
3663 * @see #emptyMap()
3664 * @since 1.3
3665 */
3666 @SuppressWarnings("unchecked")
3667 public static final Map EMPTY_MAP = new EmptyMap<Object, Object>();
3668
3669 /**
3670 * Returns the empty map (immutable). This map is serializable.
3671 *
3672 * <p>This example illustrates the type-safe way to obtain an empty set:
3673 * <pre>
3674 * Map<String, Date> s = Collections.emptyMap();
3675 * </pre>
3676 * Implementation note: Implementations of this method need not
3677 * create a separate <tt>Map</tt> object for each call. Using this
3678 * method is likely to have comparable cost to using the like-named
3679 * field. (Unlike this method, the field does not provide type safety.)
3680 *
3681 * @see #EMPTY_MAP
3682 * @since 1.5
3683 */
3684 @SuppressWarnings("unchecked")
3685 public static final <K, V> Map<K, V> emptyMap() {
3686 return (Map<K, V>) EMPTY_MAP;
3687 }
3688
3689 /**
3690 * @serial include
3691 */
3692 private static class EmptyMap<K, V> extends AbstractMap<K, V>
3693 implements Serializable {
3694 private static final long serialVersionUID = 6428348081105594320L;
3695
3696 public int size() {
3697 return 0;
3698 }
3699
3700 public boolean isEmpty() {
3701 return true;
3702 }
3703
3704 public boolean containsKey(Object key) {
3705 return false;
3706 }
3707
3708 public boolean containsValue(Object value) {
3709 return false;
3710 }
3711
3712 public V get(Object key) {
3713 return null;
3714 }
3715
3716 public Set<K> keySet() {
3717 return emptySet();
3718 }
3719
3720 public Collection<V> values() {
3721 return emptySet();
3722 }
3723
3724 public Set<Map.Entry<K, V>> entrySet() {
3725 return emptySet();
3726 }
3727
3728 public boolean equals(Object o) {
3729 return (o instanceof Map) && ((Map<?, ?>) o).isEmpty();
3730 }
3731
3732 public int hashCode() {
3733 return 0;
3734 }
3735
3736 // Preserves singleton property
3737 private Object readResolve() {
3738 return EMPTY_MAP;
3739 }
3740 }
3741
3742 // Singleton collections
3743
3744 /**
3745 * Returns an immutable set containing only the specified object.
3746 * The returned set is serializable.
3747 *
3748 * @param o the sole object to be stored in the returned set.
3749 * @return an immutable set containing only the specified object.
3750 */
3751 public static <T> Set<T> singleton(T o) {
3752 return new SingletonSet<T>(o);
3753 }
3754
3755 static <E> Iterator<E> singletonIterator(final E e) {
3756 return new Iterator<E>() {
3757 private boolean hasNext = true;
3758
3759 public boolean hasNext() {
3760 return hasNext;
3761 }
3762
3763 public E next() {
3764 if (hasNext) {
3765 hasNext = false;
3766 return e;
3767 }
3768 throw new NoSuchElementException();
3769 }
3770
3771 public void remove() {
3772 throw new UnsupportedOperationException();
3773 }
3774 };
3775 }
3776
3777 /**
3778 * @serial include
3779 */
3780 private static class SingletonSet<E> extends AbstractSet<E>
3781 implements Serializable {
3782 private static final long serialVersionUID = 3193687207550431679L;
3783
3784 final private E element;
3785
3786 SingletonSet(E e) {
3787 element = e;
3788 }
3789
3790 public Iterator<E> iterator() {
3791 return singletonIterator(element);
3792 }
3793
3794 public int size() {
3795 return 1;
3796 }
3797
3798 public boolean contains(Object o) {
3799 return eq(o, element);
3800 }
3801 }
3802
3803 /**
3804 * Returns an immutable list containing only the specified object.
3805 * The returned list is serializable.
3806 *
3807 * @param o the sole object to be stored in the returned list.
3808 * @return an immutable list containing only the specified object.
3809 * @since 1.3
3810 */
3811 public static <T> List<T> singletonList(T o) {
3812 return new SingletonList<T>(o);
3813 }
3814
3815 /**
3816 * @serial include
3817 */
3818 private static class SingletonList<E> extends AbstractList<E>
3819 implements RandomAccess, Serializable {
3820
3821 private static final long serialVersionUID = 3093736618740652951L;
3822
3823 private final E element;
3824
3825 SingletonList(E obj) {
3826 element = obj;
3827 }
3828
3829 public Iterator<E> iterator() {
3830 return singletonIterator(element);
3831 }
3832
3833 public int size() {
3834 return 1;
3835 }
3836
3837 public boolean contains(Object obj) {
3838 return eq(obj, element);
3839 }
3840
3841 public E get(int index) {
3842 if (index != 0)
3843 throw new IndexOutOfBoundsException("Index: " + index
3844 + ", Size: 1");
3845 return element;
3846 }
3847 }
3848
3849 /**
3850 * Returns an immutable map, mapping only the specified key to the
3851 * specified value. The returned map is serializable.
3852 *
3853 * @param key the sole key to be stored in the returned map.
3854 * @param value the value to which the returned map maps <tt>key</tt>.
3855 * @return an immutable map containing only the specified key-value
3856 * mapping.
3857 * @since 1.3
3858 */
3859 public static <K, V> Map<K, V> singletonMap(K key, V value) {
3860 return new SingletonMap<K, V>(key, value);
3861 }
3862
3863 /**
3864 * @serial include
3865 */
3866 private static class SingletonMap<K, V> extends AbstractMap<K, V>
3867 implements Serializable {
3868 private static final long serialVersionUID = -6979724477215052911L;
3869
3870 private final K k;
3871 private final V v;
3872
3873 SingletonMap(K key, V value) {
3874 k = key;
3875 v = value;
3876 }
3877
3878 public int size() {
3879 return 1;
3880 }
3881
3882 public boolean isEmpty() {
3883 return false;
3884 }
3885
3886 public boolean containsKey(Object key) {
3887 return eq(key, k);
3888 }
3889
3890 public boolean containsValue(Object value) {
3891 return eq(value, v);
3892 }
3893
3894 public V get(Object key) {
3895 return (eq(key, k) ? v : null);
3896 }
3897
3898 private transient Set<K> keySet = null;
3899 private transient Set<Map.Entry<K, V>> entrySet = null;
3900 private transient Collection<V> values = null;
3901
3902 public Set<K> keySet() {
3903 if (keySet == null)
3904 keySet = singleton(k);
3905 return keySet;
3906 }
3907
3908 public Set<Map.Entry<K, V>> entrySet() {
3909 if (entrySet == null)
3910 entrySet = Collections
3911 .<Map.Entry<K, V>> singleton(new SimpleImmutableEntry<K, V>(
3912 k, v));
3913 return entrySet;
3914 }
3915
3916 public Collection<V> values() {
3917 if (values == null)
3918 values = singleton(v);
3919 return values;
3920 }
3921
3922 }
3923
3924 // Miscellaneous
3925
3926 /**
3927 * Returns an immutable list consisting of <tt>n</tt> copies of the
3928 * specified object. The newly allocated data object is tiny (it contains
3929 * a single reference to the data object). This method is useful in
3930 * combination with the <tt>List.addAll</tt> method to grow lists.
3931 * The returned list is serializable.
3932 *
3933 * @param n the number of elements in the returned list.
3934 * @param o the element to appear repeatedly in the returned list.
3935 * @return an immutable list consisting of <tt>n</tt> copies of the
3936 * specified object.
3937 * @throws IllegalArgumentException if n < 0.
3938 * @see List#addAll(Collection)
3939 * @see List#addAll(int, Collection)
3940 */
3941 public static <T> List<T> nCopies(int n, T o) {
3942 if (n < 0)
3943 throw new IllegalArgumentException("List length = " + n);
3944 return new CopiesList<T>(n, o);
3945 }
3946
3947 /**
3948 * @serial include
3949 */
3950 private static class CopiesList<E> extends AbstractList<E>
3951 implements RandomAccess, Serializable {
3952 private static final long serialVersionUID = 2739099268398711800L;
3953
3954 final int n;
3955 final E element;
3956
3957 CopiesList(int n, E e) {
3958 assert n >= 0;
3959 this .n = n;
3960 element = e;
3961 }
3962
3963 public int size() {
3964 return n;
3965 }
3966
3967 public boolean contains(Object obj) {
3968 return n != 0 && eq(obj, element);
3969 }
3970
3971 public int indexOf(Object o) {
3972 return contains(o) ? 0 : -1;
3973 }
3974
3975 public int lastIndexOf(Object o) {
3976 return contains(o) ? n - 1 : -1;
3977 }
3978
3979 public E get(int index) {
3980 if (index < 0 || index >= n)
3981 throw new IndexOutOfBoundsException("Index: " + index
3982 + ", Size: " + n);
3983 return element;
3984 }
3985
3986 public Object[] toArray() {
3987 final Object[] a = new Object[n];
3988 if (element != null)
3989 Arrays.fill(a, 0, n, element);
3990 return a;
3991 }
3992
3993 public <T> T[] toArray(T[] a) {
3994 final int n = this .n;
3995 if (a.length < n) {
3996 a = (T[]) java.lang.reflect.Array.newInstance(a
3997 .getClass().getComponentType(), n);
3998 if (element != null)
3999 Arrays.fill(a, 0, n, element);
4000 } else {
4001 Arrays.fill(a, 0, n, element);
4002 if (a.length > n)
4003 a[n] = null;
4004 }
4005 return a;
4006 }
4007
4008 public List<E> subList(int fromIndex, int toIndex) {
4009 if (fromIndex < 0)
4010 throw new IndexOutOfBoundsException("fromIndex = "
4011 + fromIndex);
4012 if (toIndex > n)
4013 throw new IndexOutOfBoundsException("toIndex = "
4014 + toIndex);
4015 if (fromIndex > toIndex)
4016 throw new IllegalArgumentException("fromIndex("
4017 + fromIndex + ") > toIndex(" + toIndex + ")");
4018 return new CopiesList<E>(toIndex - fromIndex, element);
4019 }
4020 }
4021
4022 /**
4023 * Returns a comparator that imposes the reverse of the <i>natural
4024 * ordering</i> on a collection of objects that implement the
4025 * <tt>Comparable</tt> interface. (The natural ordering is the ordering
4026 * imposed by the objects' own <tt>compareTo</tt> method.) This enables a
4027 * simple idiom for sorting (or maintaining) collections (or arrays) of
4028 * objects that implement the <tt>Comparable</tt> interface in
4029 * reverse-natural-order. For example, suppose a is an array of
4030 * strings. Then: <pre>
4031 * Arrays.sort(a, Collections.reverseOrder());
4032 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
4033 *
4034 * The returned comparator is serializable.
4035 *
4036 * @return a comparator that imposes the reverse of the <i>natural
4037 * ordering</i> on a collection of objects that implement
4038 * the <tt>Comparable</tt> interface.
4039 * @see Comparable
4040 */
4041 public static <T> Comparator<T> reverseOrder() {
4042 return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
4043 }
4044
4045 /**
4046 * @serial include
4047 */
4048 private static class ReverseComparator implements
4049 Comparator<Comparable<Object>>, Serializable {
4050
4051 private static final long serialVersionUID = 7207038068494060240L;
4052
4053 private static final ReverseComparator REVERSE_ORDER = new ReverseComparator();
4054
4055 public int compare(Comparable<Object> c1, Comparable<Object> c2) {
4056 return c2.compareTo(c1);
4057 }
4058
4059 private Object readResolve() {
4060 return reverseOrder();
4061 }
4062 }
4063
4064 /**
4065 * Returns a comparator that imposes the reverse ordering of the specified
4066 * comparator. If the specified comparator is null, this method is
4067 * equivalent to {@link #reverseOrder()} (in other words, it returns a
4068 * comparator that imposes the reverse of the <i>natural ordering</i> on a
4069 * collection of objects that implement the Comparable interface).
4070 *
4071 * <p>The returned comparator is serializable (assuming the specified
4072 * comparator is also serializable or null).
4073 *
4074 * @return a comparator that imposes the reverse ordering of the
4075 * specified comparator
4076 * @since 1.5
4077 */
4078 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
4079 if (cmp == null)
4080 return reverseOrder();
4081
4082 if (cmp instanceof ReverseComparator2)
4083 return ((ReverseComparator2<T>) cmp).cmp;
4084
4085 return new ReverseComparator2<T>(cmp);
4086 }
4087
4088 /**
4089 * @serial include
4090 */
4091 private static class ReverseComparator2<T> implements
4092 Comparator<T>, Serializable {
4093 private static final long serialVersionUID = 4374092139857L;
4094
4095 /**
4096 * The comparator specified in the static factory. This will never
4097 * be null, as the static factory returns a ReverseComparator
4098 * instance if its argument is null.
4099 *
4100 * @serial
4101 */
4102 private final Comparator<T> cmp;
4103
4104 ReverseComparator2(Comparator<T> cmp) {
4105 assert cmp != null;
4106 this .cmp = cmp;
4107 }
4108
4109 public int compare(T t1, T t2) {
4110 return cmp.compare(t2, t1);
4111 }
4112
4113 public boolean equals(Object o) {
4114 return (o == this )
4115 || (o instanceof ReverseComparator2 && cmp
4116 .equals(((ReverseComparator2) o).cmp));
4117 }
4118
4119 public int hashCode() {
4120 return cmp.hashCode() ^ Integer.MIN_VALUE;
4121 }
4122 }
4123
4124 /**
4125 * Returns an enumeration over the specified collection. This provides
4126 * interoperability with legacy APIs that require an enumeration
4127 * as input.
4128 *
4129 * @param c the collection for which an enumeration is to be returned.
4130 * @return an enumeration over the specified collection.
4131 * @see Enumeration
4132 */
4133 public static <T> Enumeration<T> enumeration(final Collection<T> c) {
4134 return new Enumeration<T>() {
4135 private final Iterator<T> i = c.iterator();
4136
4137 public boolean hasMoreElements() {
4138 return i.hasNext();
4139 }
4140
4141 public T nextElement() {
4142 return i.next();
4143 }
4144 };
4145 }
4146
4147 /**
4148 * Returns an array list containing the elements returned by the
4149 * specified enumeration in the order they are returned by the
4150 * enumeration. This method provides interoperability between
4151 * legacy APIs that return enumerations and new APIs that require
4152 * collections.
4153 *
4154 * @param e enumeration providing elements for the returned
4155 * array list
4156 * @return an array list containing the elements returned
4157 * by the specified enumeration.
4158 * @since 1.4
4159 * @see Enumeration
4160 * @see ArrayList
4161 */
4162 public static <T> ArrayList<T> list(Enumeration<T> e) {
4163 ArrayList<T> l = new ArrayList<T>();
4164 while (e.hasMoreElements())
4165 l.add(e.nextElement());
4166 return l;
4167 }
4168
4169 /**
4170 * Returns true if the specified arguments are equal, or both null.
4171 */
4172 private static boolean eq(Object o1, Object o2) {
4173 return (o1 == null ? o2 == null : o1.equals(o2));
4174 }
4175
4176 /**
4177 * Returns the number of elements in the specified collection equal to the
4178 * specified object. More formally, returns the number of elements
4179 * <tt>e</tt> in the collection such that
4180 * <tt>(o == null ? e == null : o.equals(e))</tt>.
4181 *
4182 * @param c the collection in which to determine the frequency
4183 * of <tt>o</tt>
4184 * @param o the object whose frequency is to be determined
4185 * @throws NullPointerException if <tt>c</tt> is null
4186 * @since 1.5
4187 */
4188 public static int frequency(Collection<?> c, Object o) {
4189 int result = 0;
4190 if (o == null) {
4191 for (Object e : c)
4192 if (e == null)
4193 result++;
4194 } else {
4195 for (Object e : c)
4196 if (o.equals(e))
4197 result++;
4198 }
4199 return result;
4200 }
4201
4202 /**
4203 * Returns <tt>true</tt> if the two specified collections have no
4204 * elements in common.
4205 *
4206 * <p>Care must be exercised if this method is used on collections that
4207 * do not comply with the general contract for <tt>Collection</tt>.
4208 * Implementations may elect to iterate over either collection and test
4209 * for containment in the other collection (or to perform any equivalent
4210 * computation). If either collection uses a nonstandard equality test
4211 * (as does a {@link SortedSet} whose ordering is not <i>compatible with
4212 * equals</i>, or the key set of an {@link IdentityHashMap}), both
4213 * collections must use the same nonstandard equality test, or the
4214 * result of this method is undefined.
4215 *
4216 * <p>Note that it is permissible to pass the same collection in both
4217 * parameters, in which case the method will return true if and only if
4218 * the collection is empty.
4219 *
4220 * @param c1 a collection
4221 * @param c2 a collection
4222 * @throws NullPointerException if either collection is null
4223 * @since 1.5
4224 */
4225 public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
4226 /*
4227 * We're going to iterate through c1 and test for inclusion in c2.
4228 * If c1 is a Set and c2 isn't, swap the collections. Otherwise,
4229 * place the shorter collection in c1. Hopefully this heuristic
4230 * will minimize the cost of the operation.
4231 */
4232 if ((c1 instanceof Set) && !(c2 instanceof Set)
4233 || (c1.size() > c2.size())) {
4234 Collection<?> tmp = c1;
4235 c1 = c2;
4236 c2 = tmp;
4237 }
4238
4239 for (Object e : c1)
4240 if (c2.contains(e))
4241 return false;
4242 return true;
4243 }
4244
4245 /**
4246 * Adds all of the specified elements to the specified collection.
4247 * Elements to be added may be specified individually or as an array.
4248 * The behavior of this convenience method is identical to that of
4249 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely
4250 * to run significantly faster under most implementations.
4251 *
4252 * <p>When elements are specified individually, this method provides a
4253 * convenient way to add a few elements to an existing collection:
4254 * <pre>
4255 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
4256 * </pre>
4257 *
4258 * @param c the collection into which <tt>elements</tt> are to be inserted
4259 * @param elements the elements to insert into <tt>c</tt>
4260 * @return <tt>true</tt> if the collection changed as a result of the call
4261 * @throws UnsupportedOperationException if <tt>c</tt> does not support
4262 * the <tt>add</tt> operation
4263 * @throws NullPointerException if <tt>elements</tt> contains one or more
4264 * null values and <tt>c</tt> does not permit null elements, or
4265 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
4266 * @throws IllegalArgumentException if some property of a value in
4267 * <tt>elements</tt> prevents it from being added to <tt>c</tt>
4268 * @see Collection#addAll(Collection)
4269 * @since 1.5
4270 */
4271 public static <T> boolean addAll(Collection<? super T> c,
4272 T... elements) {
4273 boolean result = false;
4274 for (T element : elements)
4275 result |= c.add(element);
4276 return result;
4277 }
4278
4279 /**
4280 * Returns a set backed by the specified map. The resulting set displays
4281 * the same ordering, concurrency, and performance characteristics as the
4282 * backing map. In essence, this factory method provides a {@link Set}
4283 * implementation corresponding to any {@link Map} implementation. There
4284 * is no need to use this method on a {@link Map} implementation that
4285 * already has a corresponding {@link Set} implementation (such as {@link
4286 * HashMap} or {@link TreeMap}).
4287 *
4288 * <p>Each method invocation on the set returned by this method results in
4289 * exactly one method invocation on the backing map or its <tt>keySet</tt>
4290 * view, with one exception. The <tt>addAll</tt> method is implemented
4291 * as a sequence of <tt>put</tt> invocations on the backing map.
4292 *
4293 * <p>The specified map must be empty at the time this method is invoked,
4294 * and should not be accessed directly after this method returns. These
4295 * conditions are ensured if the map is created empty, passed directly
4296 * to this method, and no reference to the map is retained, as illustrated
4297 * in the following code fragment:
4298 * <pre>
4299 * Set<Object> weakHashSet = Collections.newSetFromMap(
4300 * new WeakHashMap<Object, Boolean>());
4301 * </pre>
4302 *
4303 * @param map the backing map
4304 * @return the set backed by the map
4305 * @throws IllegalArgumentException if <tt>map</tt> is not empty
4306 * @since 1.6
4307 */
4308 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
4309 return new SetFromMap<E>(map);
4310 }
4311
4312 /**
4313 * @serial include
4314 */
4315 private static class SetFromMap<E> extends AbstractSet<E> implements
4316 Set<E>, Serializable {
4317 private final Map<E, Boolean> m; // The backing map
4318 private transient Set<E> s; // Its keySet
4319
4320 SetFromMap(Map<E, Boolean> map) {
4321 if (!map.isEmpty())
4322 throw new IllegalArgumentException("Map is non-empty");
4323 m = map;
4324 s = map.keySet();
4325 }
4326
4327 public void clear() {
4328 m.clear();
4329 }
4330
4331 public int size() {
4332 return m.size();
4333 }
4334
4335 public boolean isEmpty() {
4336 return m.isEmpty();
4337 }
4338
4339 public boolean contains(Object o) {
4340 return m.containsKey(o);
4341 }
4342
4343 public boolean remove(Object o) {
4344 return m.remove(o) != null;
4345 }
4346
4347 public boolean add(E e) {
4348 return m.put(e, Boolean.TRUE) == null;
4349 }
4350
4351 public Iterator<E> iterator() {
4352 return s.iterator();
4353 }
4354
4355 public Object[] toArray() {
4356 return s.toArray();
4357 }
4358
4359 public <T> T[] toArray(T[] a) {
4360 return s.toArray(a);
4361 }
4362
4363 public String toString() {
4364 return s.toString();
4365 }
4366
4367 public int hashCode() {
4368 return s.hashCode();
4369 }
4370
4371 public boolean equals(Object o) {
4372 return o == this || s.equals(o);
4373 }
4374
4375 public boolean containsAll(Collection<?> c) {
4376 return s.containsAll(c);
4377 }
4378
4379 public boolean removeAll(Collection<?> c) {
4380 return s.removeAll(c);
4381 }
4382
4383 public boolean retainAll(Collection<?> c) {
4384 return s.retainAll(c);
4385 }
4386
4387 // addAll is the only inherited implementation
4388
4389 private static final long serialVersionUID = 2454657854757543876L;
4390
4391 private void readObject(java.io.ObjectInputStream stream)
4392 throws IOException, ClassNotFoundException {
4393 stream.defaultReadObject();
4394 s = m.keySet();
4395 }
4396 }
4397
4398 /**
4399 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo)
4400 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>,
4401 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
4402 * view can be useful when you would like to use a method
4403 * requiring a <tt>Queue</tt> but you need Lifo ordering.
4404 *
4405 * <p>Each method invocation on the queue returned by this method
4406 * results in exactly one method invocation on the backing deque, with
4407 * one exception. The {@link Queue#addAll addAll} method is
4408 * implemented as a sequence of {@link Deque#addFirst addFirst}
4409 * invocations on the backing deque.
4410 *
4411 * @param deque the deque
4412 * @return the queue
4413 * @since 1.6
4414 */
4415 public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
4416 return new AsLIFOQueue<T>(deque);
4417 }
4418
4419 /**
4420 * @serial include
4421 */
4422 static class AsLIFOQueue<E> extends AbstractQueue<E> implements
4423 Queue<E>, Serializable {
4424 private static final long serialVersionUID = 1802017725587941708L;
4425 private final Deque<E> q;
4426
4427 AsLIFOQueue(Deque<E> q) {
4428 this .q = q;
4429 }
4430
4431 public boolean add(E e) {
4432 q.addFirst(e);
4433 return true;
4434 }
4435
4436 public boolean offer(E e) {
4437 return q.offerFirst(e);
4438 }
4439
4440 public E poll() {
4441 return q.pollFirst();
4442 }
4443
4444 public E remove() {
4445 return q.removeFirst();
4446 }
4447
4448 public E peek() {
4449 return q.peekFirst();
4450 }
4451
4452 public E element() {
4453 return q.getFirst();
4454 }
4455
4456 public void clear() {
4457 q.clear();
4458 }
4459
4460 public int size() {
4461 return q.size();
4462 }
4463
4464 public boolean isEmpty() {
4465 return q.isEmpty();
4466 }
4467
4468 public boolean contains(Object o) {
4469 return q.contains(o);
4470 }
4471
4472 public boolean remove(Object o) {
4473 return q.remove(o);
4474 }
4475
4476 public Iterator<E> iterator() {
4477 return q.iterator();
4478 }
4479
4480 public Object[] toArray() {
4481 return q.toArray();
4482 }
4483
4484 public <T> T[] toArray(T[] a) {
4485 return q.toArray(a);
4486 }
4487
4488 public String toString() {
4489 return q.toString();
4490 }
4491
4492 public boolean containsAll(Collection<?> c) {
4493 return q.containsAll(c);
4494 }
4495
4496 public boolean removeAll(Collection<?> c) {
4497 return q.removeAll(c);
4498 }
4499
4500 public boolean retainAll(Collection<?> c) {
4501 return q.retainAll(c);
4502 }
4503 // We use inherited addAll; forwarding addAll would be wrong
4504 }
4505 }
|