Collections.java revision 92ac90f13cae6440eedd87085a43c3c8e58ddf9d
1/* 2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package java.util; 27import java.io.Serializable; 28import java.io.ObjectOutputStream; 29import java.io.IOException; 30import java.lang.reflect.Array; 31 32/** 33 * This class consists exclusively of static methods that operate on or return 34 * collections. It contains polymorphic algorithms that operate on 35 * collections, "wrappers", which return a new collection backed by a 36 * specified collection, and a few other odds and ends. 37 * 38 * <p>The methods of this class all throw a <tt>NullPointerException</tt> 39 * if the collections or class objects provided to them are null. 40 * 41 * <p>The documentation for the polymorphic algorithms contained in this class 42 * generally includes a brief description of the <i>implementation</i>. Such 43 * descriptions should be regarded as <i>implementation notes</i>, rather than 44 * parts of the <i>specification</i>. Implementors should feel free to 45 * substitute other algorithms, so long as the specification itself is adhered 46 * to. (For example, the algorithm used by <tt>sort</tt> does not have to be 47 * a mergesort, but it does have to be <i>stable</i>.) 48 * 49 * <p>The "destructive" algorithms contained in this class, that is, the 50 * algorithms that modify the collection on which they operate, are specified 51 * to throw <tt>UnsupportedOperationException</tt> if the collection does not 52 * support the appropriate mutation primitive(s), such as the <tt>set</tt> 53 * method. These algorithms may, but are not required to, throw this 54 * exception if an invocation would have no effect on the collection. For 55 * example, invoking the <tt>sort</tt> method on an unmodifiable list that is 56 * already sorted may or may not throw <tt>UnsupportedOperationException</tt>. 57 * 58 * <p>This class is a member of the 59 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 60 * Java Collections Framework</a>. 61 * 62 * @author Josh Bloch 63 * @author Neal Gafter 64 * @see Collection 65 * @see Set 66 * @see List 67 * @see Map 68 * @since 1.2 69 */ 70 71public class Collections { 72 // Suppresses default constructor, ensuring non-instantiability. 73 private Collections() { 74 } 75 76 // Algorithms 77 78 /* 79 * Tuning parameters for algorithms - Many of the List algorithms have 80 * two implementations, one of which is appropriate for RandomAccess 81 * lists, the other for "sequential." Often, the random access variant 82 * yields better performance on small sequential access lists. The 83 * tuning parameters below determine the cutoff point for what constitutes 84 * a "small" sequential access list for each algorithm. The values below 85 * were empirically determined to work well for LinkedList. Hopefully 86 * they should be reasonable for other sequential access List 87 * implementations. Those doing performance work on this code would 88 * do well to validate the values of these parameters from time to time. 89 * (The first word of each tuning parameter name is the algorithm to which 90 * it applies.) 91 */ 92 private static final int BINARYSEARCH_THRESHOLD = 5000; 93 private static final int REVERSE_THRESHOLD = 18; 94 private static final int SHUFFLE_THRESHOLD = 5; 95 private static final int FILL_THRESHOLD = 25; 96 private static final int ROTATE_THRESHOLD = 100; 97 private static final int COPY_THRESHOLD = 10; 98 private static final int REPLACEALL_THRESHOLD = 11; 99 private static final int INDEXOFSUBLIST_THRESHOLD = 35; 100 101 /** 102 * Sorts the specified list into ascending order, according to the 103 * {@linkplain Comparable natural ordering} of its elements. 104 * All elements in the list must implement the {@link Comparable} 105 * interface. Furthermore, all elements in the list must be 106 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} 107 * must not throw a {@code ClassCastException} for any elements 108 * {@code e1} and {@code e2} in the list). 109 * 110 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 111 * not be reordered as a result of the sort. 112 * 113 * <p>The specified list must be modifiable, but need not be resizable. 114 * 115 * <p>Implementation note: This implementation is a stable, adaptive, 116 * iterative mergesort that requires far fewer than n lg(n) comparisons 117 * when the input array is partially sorted, while offering the 118 * performance of a traditional mergesort when the input array is 119 * randomly ordered. If the input array is nearly sorted, the 120 * implementation requires approximately n comparisons. Temporary 121 * storage requirements vary from a small constant for nearly sorted 122 * input arrays to n/2 object references for randomly ordered input 123 * arrays. 124 * 125 * <p>The implementation takes equal advantage of ascending and 126 * descending order in its input array, and can take advantage of 127 * ascending and descending order in different parts of the same 128 * input array. It is well-suited to merging two or more sorted arrays: 129 * simply concatenate the arrays and sort the resulting array. 130 * 131 * <p>The implementation was adapted from Tim Peters's list sort for Python 132 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 133 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic 134 * Sorting and Information Theoretic Complexity", in Proceedings of the 135 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 136 * January 1993. 137 * 138 * <p>This implementation dumps the specified list into an array, sorts 139 * the array, and iterates over the list resetting each element 140 * from the corresponding position in the array. This avoids the 141 * n<sup>2</sup> log(n) performance that would result from attempting 142 * to sort a linked list in place. 143 * 144 * @param list the list to be sorted. 145 * @throws ClassCastException if the list contains elements that are not 146 * <i>mutually comparable</i> (for example, strings and integers). 147 * @throws UnsupportedOperationException if the specified list's 148 * list-iterator does not support the {@code set} operation. 149 * @throws IllegalArgumentException (optional) if the implementation 150 * detects that the natural ordering of the list elements is 151 * found to violate the {@link Comparable} contract 152 */ 153 public static <T extends Comparable<? super T>> void sort(List<T> list) { 154 if (list.getClass() == ArrayList.class) { 155 Arrays.sort(((ArrayList) list).elementData, 0, list.size()); 156 return; 157 } 158 159 Object[] a = list.toArray(); 160 Arrays.sort(a); 161 ListIterator<T> i = list.listIterator(); 162 for (int j=0; j<a.length; j++) { 163 i.next(); 164 i.set((T)a[j]); 165 } 166 } 167 168 /** 169 * Sorts the specified list according to the order induced by the 170 * specified comparator. All elements in the list must be <i>mutually 171 * comparable</i> using the specified comparator (that is, 172 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} 173 * for any elements {@code e1} and {@code e2} in the list). 174 * 175 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will 176 * not be reordered as a result of the sort. 177 * 178 * <p>The specified list must be modifiable, but need not be resizable. 179 * 180 * <p>Implementation note: This implementation is a stable, adaptive, 181 * iterative mergesort that requires far fewer than n lg(n) comparisons 182 * when the input array is partially sorted, while offering the 183 * performance of a traditional mergesort when the input array is 184 * randomly ordered. If the input array is nearly sorted, the 185 * implementation requires approximately n comparisons. Temporary 186 * storage requirements vary from a small constant for nearly sorted 187 * input arrays to n/2 object references for randomly ordered input 188 * arrays. 189 * 190 * <p>The implementation takes equal advantage of ascending and 191 * descending order in its input array, and can take advantage of 192 * ascending and descending order in different parts of the same 193 * input array. It is well-suited to merging two or more sorted arrays: 194 * simply concatenate the arrays and sort the resulting array. 195 * 196 * <p>The implementation was adapted from Tim Peters's list sort for Python 197 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 198 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic 199 * Sorting and Information Theoretic Complexity", in Proceedings of the 200 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 201 * January 1993. 202 * 203 * <p>This implementation dumps the specified list into an array, sorts 204 * the array, and iterates over the list resetting each element 205 * from the corresponding position in the array. This avoids the 206 * n<sup>2</sup> log(n) performance that would result from attempting 207 * to sort a linked list in place. 208 * 209 * @param list the list to be sorted. 210 * @param c the comparator to determine the order of the list. A 211 * {@code null} value indicates that the elements' <i>natural 212 * ordering</i> should be used. 213 * @throws ClassCastException if the list contains elements that are not 214 * <i>mutually comparable</i> using the specified comparator. 215 * @throws UnsupportedOperationException if the specified list's 216 * list-iterator does not support the {@code set} operation. 217 * @throws IllegalArgumentException (optional) if the comparator is 218 * found to violate the {@link Comparator} contract 219 */ 220 public static <T> void sort(List<T> list, Comparator<? super T> c) { 221 if (list.getClass() == ArrayList.class) { 222 Arrays.sort(((ArrayList) list).elementData, 0, list.size(), (Comparator) c); 223 return; 224 } 225 226 Object[] a = list.toArray(); 227 Arrays.sort(a, (Comparator)c); 228 ListIterator i = list.listIterator(); 229 for (int j=0; j<a.length; j++) { 230 i.next(); 231 i.set(a[j]); 232 } 233 } 234 235 236 /** 237 * Searches the specified list for the specified object using the binary 238 * search algorithm. The list must be sorted into ascending order 239 * according to the {@linkplain Comparable natural ordering} of its 240 * elements (as by the {@link #sort(List)} method) prior to making this 241 * call. If it is not sorted, the results are undefined. If the list 242 * contains multiple elements equal to the specified object, there is no 243 * guarantee which one will be found. 244 * 245 * <p>This method runs in log(n) time for a "random access" list (which 246 * provides near-constant-time positional access). If the specified list 247 * does not implement the {@link RandomAccess} interface and is large, 248 * this method will do an iterator-based binary search that performs 249 * O(n) link traversals and O(log n) element comparisons. 250 * 251 * @param list the list to be searched. 252 * @param key the key to be searched for. 253 * @return the index of the search key, if it is contained in the list; 254 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 255 * <i>insertion point</i> is defined as the point at which the 256 * key would be inserted into the list: the index of the first 257 * element greater than the key, or <tt>list.size()</tt> if all 258 * elements in the list are less than the specified key. Note 259 * that this guarantees that the return value will be >= 0 if 260 * and only if the key is found. 261 * @throws ClassCastException if the list contains elements that are not 262 * <i>mutually comparable</i> (for example, strings and 263 * integers), or the search key is not mutually comparable 264 * with the elements of the list. 265 */ 266 public static <T> 267 int binarySearch(List<? extends Comparable<? super T>> list, T key) { 268 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 269 return Collections.indexedBinarySearch(list, key); 270 else 271 return Collections.iteratorBinarySearch(list, key); 272 } 273 274 private static <T> 275 int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) 276 { 277 int low = 0; 278 int high = list.size()-1; 279 280 while (low <= high) { 281 int mid = (low + high) >>> 1; 282 Comparable<? super T> midVal = list.get(mid); 283 int cmp = midVal.compareTo(key); 284 285 if (cmp < 0) 286 low = mid + 1; 287 else if (cmp > 0) 288 high = mid - 1; 289 else 290 return mid; // key found 291 } 292 return -(low + 1); // key not found 293 } 294 295 private static <T> 296 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) 297 { 298 int low = 0; 299 int high = list.size()-1; 300 ListIterator<? extends Comparable<? super T>> i = list.listIterator(); 301 302 while (low <= high) { 303 int mid = (low + high) >>> 1; 304 Comparable<? super T> midVal = get(i, mid); 305 int cmp = midVal.compareTo(key); 306 307 if (cmp < 0) 308 low = mid + 1; 309 else if (cmp > 0) 310 high = mid - 1; 311 else 312 return mid; // key found 313 } 314 return -(low + 1); // key not found 315 } 316 317 /** 318 * Gets the ith element from the given list by repositioning the specified 319 * list listIterator. 320 */ 321 private static <T> T get(ListIterator<? extends T> i, int index) { 322 T obj = null; 323 int pos = i.nextIndex(); 324 if (pos <= index) { 325 do { 326 obj = i.next(); 327 } while (pos++ < index); 328 } else { 329 do { 330 obj = i.previous(); 331 } while (--pos > index); 332 } 333 return obj; 334 } 335 336 /** 337 * Searches the specified list for the specified object using the binary 338 * search algorithm. The list must be sorted into ascending order 339 * according to the specified comparator (as by the 340 * {@link #sort(List, Comparator) sort(List, Comparator)} 341 * method), prior to making this call. If it is 342 * not sorted, the results are undefined. If the list contains multiple 343 * elements equal to the specified object, there is no guarantee which one 344 * will be found. 345 * 346 * <p>This method runs in log(n) time for a "random access" list (which 347 * provides near-constant-time positional access). If the specified list 348 * does not implement the {@link RandomAccess} interface and is large, 349 * this method will do an iterator-based binary search that performs 350 * O(n) link traversals and O(log n) element comparisons. 351 * 352 * @param list the list to be searched. 353 * @param key the key to be searched for. 354 * @param c the comparator by which the list is ordered. 355 * A <tt>null</tt> value indicates that the elements' 356 * {@linkplain Comparable natural ordering} should be used. 357 * @return the index of the search key, if it is contained in the list; 358 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 359 * <i>insertion point</i> is defined as the point at which the 360 * key would be inserted into the list: the index of the first 361 * element greater than the key, or <tt>list.size()</tt> if all 362 * elements in the list are less than the specified key. Note 363 * that this guarantees that the return value will be >= 0 if 364 * and only if the key is found. 365 * @throws ClassCastException if the list contains elements that are not 366 * <i>mutually comparable</i> using the specified comparator, 367 * or the search key is not mutually comparable with the 368 * elements of the list using this comparator. 369 */ 370 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { 371 if (c==null) 372 return binarySearch((List) list, key); 373 374 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 375 return Collections.indexedBinarySearch(list, key, c); 376 else 377 return Collections.iteratorBinarySearch(list, key, c); 378 } 379 380 private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) { 381 int low = 0; 382 int high = l.size()-1; 383 384 while (low <= high) { 385 int mid = (low + high) >>> 1; 386 T midVal = l.get(mid); 387 int cmp = c.compare(midVal, key); 388 389 if (cmp < 0) 390 low = mid + 1; 391 else if (cmp > 0) 392 high = mid - 1; 393 else 394 return mid; // key found 395 } 396 return -(low + 1); // key not found 397 } 398 399 private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) { 400 int low = 0; 401 int high = l.size()-1; 402 ListIterator<? extends T> i = l.listIterator(); 403 404 while (low <= high) { 405 int mid = (low + high) >>> 1; 406 T midVal = get(i, mid); 407 int cmp = c.compare(midVal, key); 408 409 if (cmp < 0) 410 low = mid + 1; 411 else if (cmp > 0) 412 high = mid - 1; 413 else 414 return mid; // key found 415 } 416 return -(low + 1); // key not found 417 } 418 419 private interface SelfComparable extends Comparable<SelfComparable> {} 420 421 422 /** 423 * Reverses the order of the elements in the specified list.<p> 424 * 425 * This method runs in linear time. 426 * 427 * @param list the list whose elements are to be reversed. 428 * @throws UnsupportedOperationException if the specified list or 429 * its list-iterator does not support the <tt>set</tt> operation. 430 */ 431 public static void reverse(List<?> list) { 432 int size = list.size(); 433 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { 434 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) 435 swap(list, i, j); 436 } else { 437 ListIterator fwd = list.listIterator(); 438 ListIterator rev = list.listIterator(size); 439 for (int i=0, mid=list.size()>>1; i<mid; i++) { 440 Object tmp = fwd.next(); 441 fwd.set(rev.previous()); 442 rev.set(tmp); 443 } 444 } 445 } 446 447 /** 448 * Randomly permutes the specified list using a default source of 449 * randomness. All permutations occur with approximately equal 450 * likelihood.<p> 451 * 452 * The hedge "approximately" is used in the foregoing description because 453 * default source of randomness is only approximately an unbiased source 454 * of independently chosen bits. If it were a perfect source of randomly 455 * chosen bits, then the algorithm would choose permutations with perfect 456 * uniformity.<p> 457 * 458 * This implementation traverses the list backwards, from the last element 459 * up to the second, repeatedly swapping a randomly selected element into 460 * the "current position". Elements are randomly selected from the 461 * portion of the list that runs from the first element to the current 462 * position, inclusive.<p> 463 * 464 * This method runs in linear time. If the specified list does not 465 * implement the {@link RandomAccess} interface and is large, this 466 * implementation dumps the specified list into an array before shuffling 467 * it, and dumps the shuffled array back into the list. This avoids the 468 * quadratic behavior that would result from shuffling a "sequential 469 * access" list in place. 470 * 471 * @param list the list to be shuffled. 472 * @throws UnsupportedOperationException if the specified list or 473 * its list-iterator does not support the <tt>set</tt> operation. 474 */ 475 public static void shuffle(List<?> list) { 476 Random rnd = r; 477 if (rnd == null) 478 r = rnd = new Random(); 479 shuffle(list, rnd); 480 } 481 private static Random r; 482 483 /** 484 * Randomly permute the specified list using the specified source of 485 * randomness. All permutations occur with equal likelihood 486 * assuming that the source of randomness is fair.<p> 487 * 488 * This implementation traverses the list backwards, from the last element 489 * up to the second, repeatedly swapping a randomly selected element into 490 * the "current position". Elements are randomly selected from the 491 * portion of the list that runs from the first element to the current 492 * position, inclusive.<p> 493 * 494 * This method runs in linear time. If the specified list does not 495 * implement the {@link RandomAccess} interface and is large, this 496 * implementation dumps the specified list into an array before shuffling 497 * it, and dumps the shuffled array back into the list. This avoids the 498 * quadratic behavior that would result from shuffling a "sequential 499 * access" list in place. 500 * 501 * @param list the list to be shuffled. 502 * @param rnd the source of randomness to use to shuffle the list. 503 * @throws UnsupportedOperationException if the specified list or its 504 * list-iterator does not support the <tt>set</tt> operation. 505 */ 506 public static void shuffle(List<?> list, Random rnd) { 507 int size = list.size(); 508 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 509 for (int i=size; i>1; i--) 510 swap(list, i-1, rnd.nextInt(i)); 511 } else { 512 Object arr[] = list.toArray(); 513 514 // Shuffle array 515 for (int i=size; i>1; i--) 516 swap(arr, i-1, rnd.nextInt(i)); 517 518 // Dump array back into list 519 ListIterator it = list.listIterator(); 520 for (int i=0; i<arr.length; i++) { 521 it.next(); 522 it.set(arr[i]); 523 } 524 } 525 } 526 527 /** 528 * Swaps the elements at the specified positions in the specified list. 529 * (If the specified positions are equal, invoking this method leaves 530 * the list unchanged.) 531 * 532 * @param list The list in which to swap elements. 533 * @param i the index of one element to be swapped. 534 * @param j the index of the other element to be swapped. 535 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt> 536 * is out of range (i < 0 || i >= list.size() 537 * || j < 0 || j >= list.size()). 538 * @since 1.4 539 */ 540 public static void swap(List<?> list, int i, int j) { 541 final List l = list; 542 l.set(i, l.set(j, l.get(i))); 543 } 544 545 /** 546 * Swaps the two specified elements in the specified array. 547 */ 548 private static void swap(Object[] arr, int i, int j) { 549 Object tmp = arr[i]; 550 arr[i] = arr[j]; 551 arr[j] = tmp; 552 } 553 554 /** 555 * Replaces all of the elements of the specified list with the specified 556 * element. <p> 557 * 558 * This method runs in linear time. 559 * 560 * @param list the list to be filled with the specified element. 561 * @param obj The element with which to fill the specified list. 562 * @throws UnsupportedOperationException if the specified list or its 563 * list-iterator does not support the <tt>set</tt> operation. 564 */ 565 public static <T> void fill(List<? super T> list, T obj) { 566 int size = list.size(); 567 568 if (size < FILL_THRESHOLD || list instanceof RandomAccess) { 569 for (int i=0; i<size; i++) 570 list.set(i, obj); 571 } else { 572 ListIterator<? super T> itr = list.listIterator(); 573 for (int i=0; i<size; i++) { 574 itr.next(); 575 itr.set(obj); 576 } 577 } 578 } 579 580 /** 581 * Copies all of the elements from one list into another. After the 582 * operation, the index of each copied element in the destination list 583 * will be identical to its index in the source list. The destination 584 * list must be at least as long as the source list. If it is longer, the 585 * remaining elements in the destination list are unaffected. <p> 586 * 587 * This method runs in linear time. 588 * 589 * @param dest The destination list. 590 * @param src The source list. 591 * @throws IndexOutOfBoundsException if the destination list is too small 592 * to contain the entire source List. 593 * @throws UnsupportedOperationException if the destination list's 594 * list-iterator does not support the <tt>set</tt> operation. 595 */ 596 public static <T> void copy(List<? super T> dest, List<? extends T> src) { 597 int srcSize = src.size(); 598 if (srcSize > dest.size()) 599 throw new IndexOutOfBoundsException("Source does not fit in dest"); 600 601 if (srcSize < COPY_THRESHOLD || 602 (src instanceof RandomAccess && dest instanceof RandomAccess)) { 603 for (int i=0; i<srcSize; i++) 604 dest.set(i, src.get(i)); 605 } else { 606 ListIterator<? super T> di=dest.listIterator(); 607 ListIterator<? extends T> si=src.listIterator(); 608 for (int i=0; i<srcSize; i++) { 609 di.next(); 610 di.set(si.next()); 611 } 612 } 613 } 614 615 /** 616 * Returns the minimum element of the given collection, according to the 617 * <i>natural ordering</i> of its elements. All elements in the 618 * collection must implement the <tt>Comparable</tt> interface. 619 * Furthermore, all elements in the collection must be <i>mutually 620 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a 621 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 622 * <tt>e2</tt> in the collection).<p> 623 * 624 * This method iterates over the entire collection, hence it requires 625 * time proportional to the size of the collection. 626 * 627 * @param coll the collection whose minimum element is to be determined. 628 * @return the minimum element of the given collection, according 629 * to the <i>natural ordering</i> of its elements. 630 * @throws ClassCastException if the collection contains elements that are 631 * not <i>mutually comparable</i> (for example, strings and 632 * integers). 633 * @throws NoSuchElementException if the collection is empty. 634 * @see Comparable 635 */ 636 public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) { 637 Iterator<? extends T> i = coll.iterator(); 638 T candidate = i.next(); 639 640 while (i.hasNext()) { 641 T next = i.next(); 642 if (next.compareTo(candidate) < 0) 643 candidate = next; 644 } 645 return candidate; 646 } 647 648 /** 649 * Returns the minimum element of the given collection, according to the 650 * order induced by the specified comparator. All elements in the 651 * collection must be <i>mutually comparable</i> by the specified 652 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a 653 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 654 * <tt>e2</tt> in the collection).<p> 655 * 656 * This method iterates over the entire collection, hence it requires 657 * time proportional to the size of the collection. 658 * 659 * @param coll the collection whose minimum element is to be determined. 660 * @param comp the comparator with which to determine the minimum element. 661 * A <tt>null</tt> value indicates that the elements' <i>natural 662 * ordering</i> should be used. 663 * @return the minimum element of the given collection, according 664 * to the specified comparator. 665 * @throws ClassCastException if the collection contains elements that are 666 * not <i>mutually comparable</i> using the specified comparator. 667 * @throws NoSuchElementException if the collection is empty. 668 * @see Comparable 669 */ 670 public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) { 671 if (comp==null) 672 return (T)min((Collection<SelfComparable>) (Collection) coll); 673 674 Iterator<? extends T> i = coll.iterator(); 675 T candidate = i.next(); 676 677 while (i.hasNext()) { 678 T next = i.next(); 679 if (comp.compare(next, candidate) < 0) 680 candidate = next; 681 } 682 return candidate; 683 } 684 685 /** 686 * Returns the maximum element of the given collection, according to the 687 * <i>natural ordering</i> of its elements. All elements in the 688 * collection must implement the <tt>Comparable</tt> interface. 689 * Furthermore, all elements in the collection must be <i>mutually 690 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a 691 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 692 * <tt>e2</tt> in the collection).<p> 693 * 694 * This method iterates over the entire collection, hence it requires 695 * time proportional to the size of the collection. 696 * 697 * @param coll the collection whose maximum element is to be determined. 698 * @return the maximum element of the given collection, according 699 * to the <i>natural ordering</i> of its elements. 700 * @throws ClassCastException if the collection contains elements that are 701 * not <i>mutually comparable</i> (for example, strings and 702 * integers). 703 * @throws NoSuchElementException if the collection is empty. 704 * @see Comparable 705 */ 706 public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) { 707 Iterator<? extends T> i = coll.iterator(); 708 T candidate = i.next(); 709 710 while (i.hasNext()) { 711 T next = i.next(); 712 if (next.compareTo(candidate) > 0) 713 candidate = next; 714 } 715 return candidate; 716 } 717 718 /** 719 * Returns the maximum element of the given collection, according to the 720 * order induced by the specified comparator. All elements in the 721 * collection must be <i>mutually comparable</i> by the specified 722 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a 723 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 724 * <tt>e2</tt> in the collection).<p> 725 * 726 * This method iterates over the entire collection, hence it requires 727 * time proportional to the size of the collection. 728 * 729 * @param coll the collection whose maximum element is to be determined. 730 * @param comp the comparator with which to determine the maximum element. 731 * A <tt>null</tt> value indicates that the elements' <i>natural 732 * ordering</i> should be used. 733 * @return the maximum element of the given collection, according 734 * to the specified comparator. 735 * @throws ClassCastException if the collection contains elements that are 736 * not <i>mutually comparable</i> using the specified comparator. 737 * @throws NoSuchElementException if the collection is empty. 738 * @see Comparable 739 */ 740 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) { 741 if (comp==null) 742 return (T)max((Collection<SelfComparable>) (Collection) coll); 743 744 Iterator<? extends T> i = coll.iterator(); 745 T candidate = i.next(); 746 747 while (i.hasNext()) { 748 T next = i.next(); 749 if (comp.compare(next, candidate) > 0) 750 candidate = next; 751 } 752 return candidate; 753 } 754 755 /** 756 * Rotates the elements in the specified list by the specified distance. 757 * After calling this method, the element at index <tt>i</tt> will be 758 * the element previously at index <tt>(i - distance)</tt> mod 759 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt> 760 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on 761 * the size of the list.) 762 * 763 * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>. 764 * After invoking <tt>Collections.rotate(list, 1)</tt> (or 765 * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise 766 * <tt>[s, t, a, n, k]</tt>. 767 * 768 * <p>Note that this method can usefully be applied to sublists to 769 * move one or more elements within a list while preserving the 770 * order of the remaining elements. For example, the following idiom 771 * moves the element at index <tt>j</tt> forward to position 772 * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>): 773 * <pre> 774 * Collections.rotate(list.subList(j, k+1), -1); 775 * </pre> 776 * To make this concrete, suppose <tt>list</tt> comprises 777 * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt> 778 * (<tt>b</tt>) forward two positions, perform the following invocation: 779 * <pre> 780 * Collections.rotate(l.subList(1, 4), -1); 781 * </pre> 782 * The resulting list is <tt>[a, c, d, b, e]</tt>. 783 * 784 * <p>To move more than one element forward, increase the absolute value 785 * of the rotation distance. To move elements backward, use a positive 786 * shift distance. 787 * 788 * <p>If the specified list is small or implements the {@link 789 * RandomAccess} interface, this implementation exchanges the first 790 * element into the location it should go, and then repeatedly exchanges 791 * the displaced element into the location it should go until a displaced 792 * element is swapped into the first element. If necessary, the process 793 * is repeated on the second and successive elements, until the rotation 794 * is complete. If the specified list is large and doesn't implement the 795 * <tt>RandomAccess</tt> interface, this implementation breaks the 796 * list into two sublist views around index <tt>-distance mod size</tt>. 797 * Then the {@link #reverse(List)} method is invoked on each sublist view, 798 * and finally it is invoked on the entire list. For a more complete 799 * description of both algorithms, see Section 2.3 of Jon Bentley's 800 * <i>Programming Pearls</i> (Addison-Wesley, 1986). 801 * 802 * @param list the list to be rotated. 803 * @param distance the distance to rotate the list. There are no 804 * constraints on this value; it may be zero, negative, or 805 * greater than <tt>list.size()</tt>. 806 * @throws UnsupportedOperationException if the specified list or 807 * its list-iterator does not support the <tt>set</tt> operation. 808 * @since 1.4 809 */ 810 public static void rotate(List<?> list, int distance) { 811 if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) 812 rotate1(list, distance); 813 else 814 rotate2(list, distance); 815 } 816 817 private static <T> void rotate1(List<T> list, int distance) { 818 int size = list.size(); 819 if (size == 0) 820 return; 821 distance = distance % size; 822 if (distance < 0) 823 distance += size; 824 if (distance == 0) 825 return; 826 827 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { 828 T displaced = list.get(cycleStart); 829 int i = cycleStart; 830 do { 831 i += distance; 832 if (i >= size) 833 i -= size; 834 displaced = list.set(i, displaced); 835 nMoved ++; 836 } while (i != cycleStart); 837 } 838 } 839 840 private static void rotate2(List<?> list, int distance) { 841 int size = list.size(); 842 if (size == 0) 843 return; 844 int mid = -distance % size; 845 if (mid < 0) 846 mid += size; 847 if (mid == 0) 848 return; 849 850 reverse(list.subList(0, mid)); 851 reverse(list.subList(mid, size)); 852 reverse(list); 853 } 854 855 /** 856 * Replaces all occurrences of one specified value in a list with another. 857 * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt> 858 * in <tt>list</tt> such that 859 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>. 860 * (This method has no effect on the size of the list.) 861 * 862 * @param list the list in which replacement is to occur. 863 * @param oldVal the old value to be replaced. 864 * @param newVal the new value with which <tt>oldVal</tt> is to be 865 * replaced. 866 * @return <tt>true</tt> if <tt>list</tt> contained one or more elements 867 * <tt>e</tt> such that 868 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>. 869 * @throws UnsupportedOperationException if the specified list or 870 * its list-iterator does not support the <tt>set</tt> operation. 871 * @since 1.4 872 */ 873 public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) { 874 boolean result = false; 875 int size = list.size(); 876 if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { 877 if (oldVal==null) { 878 for (int i=0; i<size; i++) { 879 if (list.get(i)==null) { 880 list.set(i, newVal); 881 result = true; 882 } 883 } 884 } else { 885 for (int i=0; i<size; i++) { 886 if (oldVal.equals(list.get(i))) { 887 list.set(i, newVal); 888 result = true; 889 } 890 } 891 } 892 } else { 893 ListIterator<T> itr=list.listIterator(); 894 if (oldVal==null) { 895 for (int i=0; i<size; i++) { 896 if (itr.next()==null) { 897 itr.set(newVal); 898 result = true; 899 } 900 } 901 } else { 902 for (int i=0; i<size; i++) { 903 if (oldVal.equals(itr.next())) { 904 itr.set(newVal); 905 result = true; 906 } 907 } 908 } 909 } 910 return result; 911 } 912 913 /** 914 * Returns the starting position of the first occurrence of the specified 915 * target list within the specified source list, or -1 if there is no 916 * such occurrence. More formally, returns the lowest index <tt>i</tt> 917 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>, 918 * or -1 if there is no such index. (Returns -1 if 919 * <tt>target.size() > source.size()</tt>.) 920 * 921 * <p>This implementation uses the "brute force" technique of scanning 922 * over the source list, looking for a match with the target at each 923 * location in turn. 924 * 925 * @param source the list in which to search for the first occurrence 926 * of <tt>target</tt>. 927 * @param target the list to search for as a subList of <tt>source</tt>. 928 * @return the starting position of the first occurrence of the specified 929 * target list within the specified source list, or -1 if there 930 * is no such occurrence. 931 * @since 1.4 932 */ 933 public static int indexOfSubList(List<?> source, List<?> target) { 934 int sourceSize = source.size(); 935 int targetSize = target.size(); 936 int maxCandidate = sourceSize - targetSize; 937 938 if (sourceSize < INDEXOFSUBLIST_THRESHOLD || 939 (source instanceof RandomAccess&&target instanceof RandomAccess)) { 940 nextCand: 941 for (int candidate = 0; candidate <= maxCandidate; candidate++) { 942 for (int i=0, j=candidate; i<targetSize; i++, j++) 943 if (!eq(target.get(i), source.get(j))) 944 continue nextCand; // Element mismatch, try next cand 945 return candidate; // All elements of candidate matched target 946 } 947 } else { // Iterator version of above algorithm 948 ListIterator<?> si = source.listIterator(); 949 nextCand: 950 for (int candidate = 0; candidate <= maxCandidate; candidate++) { 951 ListIterator<?> ti = target.listIterator(); 952 for (int i=0; i<targetSize; i++) { 953 if (!eq(ti.next(), si.next())) { 954 // Back up source iterator to next candidate 955 for (int j=0; j<i; j++) 956 si.previous(); 957 continue nextCand; 958 } 959 } 960 return candidate; 961 } 962 } 963 return -1; // No candidate matched the target 964 } 965 966 /** 967 * Returns the starting position of the last occurrence of the specified 968 * target list within the specified source list, or -1 if there is no such 969 * occurrence. More formally, returns the highest index <tt>i</tt> 970 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>, 971 * or -1 if there is no such index. (Returns -1 if 972 * <tt>target.size() > source.size()</tt>.) 973 * 974 * <p>This implementation uses the "brute force" technique of iterating 975 * over the source list, looking for a match with the target at each 976 * location in turn. 977 * 978 * @param source the list in which to search for the last occurrence 979 * of <tt>target</tt>. 980 * @param target the list to search for as a subList of <tt>source</tt>. 981 * @return the starting position of the last occurrence of the specified 982 * target list within the specified source list, or -1 if there 983 * is no such occurrence. 984 * @since 1.4 985 */ 986 public static int lastIndexOfSubList(List<?> source, List<?> target) { 987 int sourceSize = source.size(); 988 int targetSize = target.size(); 989 int maxCandidate = sourceSize - targetSize; 990 991 if (sourceSize < INDEXOFSUBLIST_THRESHOLD || 992 source instanceof RandomAccess) { // Index access version 993 nextCand: 994 for (int candidate = maxCandidate; candidate >= 0; candidate--) { 995 for (int i=0, j=candidate; i<targetSize; i++, j++) 996 if (!eq(target.get(i), source.get(j))) 997 continue nextCand; // Element mismatch, try next cand 998 return candidate; // All elements of candidate matched target 999 } 1000 } else { // Iterator version of above algorithm 1001 if (maxCandidate < 0) 1002 return -1; 1003 ListIterator<?> si = source.listIterator(maxCandidate); 1004 nextCand: 1005 for (int candidate = maxCandidate; candidate >= 0; candidate--) { 1006 ListIterator<?> ti = target.listIterator(); 1007 for (int i=0; i<targetSize; i++) { 1008 if (!eq(ti.next(), si.next())) { 1009 if (candidate != 0) { 1010 // Back up source iterator to next candidate 1011 for (int j=0; j<=i+1; j++) 1012 si.previous(); 1013 } 1014 continue nextCand; 1015 } 1016 } 1017 return candidate; 1018 } 1019 } 1020 return -1; // No candidate matched the target 1021 } 1022 1023 1024 // Unmodifiable Wrappers 1025 1026 /** 1027 * Returns an unmodifiable view of the specified collection. This method 1028 * allows modules to provide users with "read-only" access to internal 1029 * collections. Query operations on the returned collection "read through" 1030 * to the specified collection, and attempts to modify the returned 1031 * collection, whether direct or via its iterator, result in an 1032 * <tt>UnsupportedOperationException</tt>.<p> 1033 * 1034 * The returned collection does <i>not</i> pass the hashCode and equals 1035 * operations through to the backing collection, but relies on 1036 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This 1037 * is necessary to preserve the contracts of these operations in the case 1038 * that the backing collection is a set or a list.<p> 1039 * 1040 * The returned collection will be serializable if the specified collection 1041 * is serializable. 1042 * 1043 * @param c the collection for which an unmodifiable view is to be 1044 * returned. 1045 * @return an unmodifiable view of the specified collection. 1046 */ 1047 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) { 1048 return new UnmodifiableCollection<>(c); 1049 } 1050 1051 /** 1052 * @serial include 1053 */ 1054 static class UnmodifiableCollection<E> implements Collection<E>, Serializable { 1055 private static final long serialVersionUID = 1820017752578914078L; 1056 1057 final Collection<? extends E> c; 1058 1059 UnmodifiableCollection(Collection<? extends E> c) { 1060 if (c==null) 1061 throw new NullPointerException(); 1062 this.c = c; 1063 } 1064 1065 public int size() {return c.size();} 1066 public boolean isEmpty() {return c.isEmpty();} 1067 public boolean contains(Object o) {return c.contains(o);} 1068 public Object[] toArray() {return c.toArray();} 1069 public <T> T[] toArray(T[] a) {return c.toArray(a);} 1070 public String toString() {return c.toString();} 1071 1072 public Iterator<E> iterator() { 1073 return new Iterator<E>() { 1074 private final Iterator<? extends E> i = c.iterator(); 1075 1076 public boolean hasNext() {return i.hasNext();} 1077 public E next() {return i.next();} 1078 public void remove() { 1079 throw new UnsupportedOperationException(); 1080 } 1081 }; 1082 } 1083 1084 public boolean add(E e) { 1085 throw new UnsupportedOperationException(); 1086 } 1087 public boolean remove(Object o) { 1088 throw new UnsupportedOperationException(); 1089 } 1090 1091 public boolean containsAll(Collection<?> coll) { 1092 return c.containsAll(coll); 1093 } 1094 public boolean addAll(Collection<? extends E> coll) { 1095 throw new UnsupportedOperationException(); 1096 } 1097 public boolean removeAll(Collection<?> coll) { 1098 throw new UnsupportedOperationException(); 1099 } 1100 public boolean retainAll(Collection<?> coll) { 1101 throw new UnsupportedOperationException(); 1102 } 1103 public void clear() { 1104 throw new UnsupportedOperationException(); 1105 } 1106 } 1107 1108 /** 1109 * Returns an unmodifiable view of the specified set. This method allows 1110 * modules to provide users with "read-only" access to internal sets. 1111 * Query operations on the returned set "read through" to the specified 1112 * set, and attempts to modify the returned set, whether direct or via its 1113 * iterator, result in an <tt>UnsupportedOperationException</tt>.<p> 1114 * 1115 * The returned set will be serializable if the specified set 1116 * is serializable. 1117 * 1118 * @param s the set for which an unmodifiable view is to be returned. 1119 * @return an unmodifiable view of the specified set. 1120 */ 1121 public static <T> Set<T> unmodifiableSet(Set<? extends T> s) { 1122 return new UnmodifiableSet<>(s); 1123 } 1124 1125 /** 1126 * @serial include 1127 */ 1128 static class UnmodifiableSet<E> extends UnmodifiableCollection<E> 1129 implements Set<E>, Serializable { 1130 private static final long serialVersionUID = -9215047833775013803L; 1131 1132 UnmodifiableSet(Set<? extends E> s) {super(s);} 1133 public boolean equals(Object o) {return o == this || c.equals(o);} 1134 public int hashCode() {return c.hashCode();} 1135 } 1136 1137 /** 1138 * Returns an unmodifiable view of the specified sorted set. This method 1139 * allows modules to provide users with "read-only" access to internal 1140 * sorted sets. Query operations on the returned sorted set "read 1141 * through" to the specified sorted set. Attempts to modify the returned 1142 * sorted set, whether direct, via its iterator, or via its 1143 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in 1144 * an <tt>UnsupportedOperationException</tt>.<p> 1145 * 1146 * The returned sorted set will be serializable if the specified sorted set 1147 * is serializable. 1148 * 1149 * @param s the sorted set for which an unmodifiable view is to be 1150 * returned. 1151 * @return an unmodifiable view of the specified sorted set. 1152 */ 1153 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) { 1154 return new UnmodifiableSortedSet<>(s); 1155 } 1156 1157 /** 1158 * @serial include 1159 */ 1160 static class UnmodifiableSortedSet<E> 1161 extends UnmodifiableSet<E> 1162 implements SortedSet<E>, Serializable { 1163 private static final long serialVersionUID = -4929149591599911165L; 1164 private final SortedSet<E> ss; 1165 1166 UnmodifiableSortedSet(SortedSet<E> s) {super(s); ss = s;} 1167 1168 public Comparator<? super E> comparator() {return ss.comparator();} 1169 1170 public SortedSet<E> subSet(E fromElement, E toElement) { 1171 return new UnmodifiableSortedSet<>(ss.subSet(fromElement,toElement)); 1172 } 1173 public SortedSet<E> headSet(E toElement) { 1174 return new UnmodifiableSortedSet<>(ss.headSet(toElement)); 1175 } 1176 public SortedSet<E> tailSet(E fromElement) { 1177 return new UnmodifiableSortedSet<>(ss.tailSet(fromElement)); 1178 } 1179 1180 public E first() {return ss.first();} 1181 public E last() {return ss.last();} 1182 } 1183 1184 /** 1185 * Returns an unmodifiable view of the specified list. This method allows 1186 * modules to provide users with "read-only" access to internal 1187 * lists. Query operations on the returned list "read through" to the 1188 * specified list, and attempts to modify the returned list, whether 1189 * direct or via its iterator, result in an 1190 * <tt>UnsupportedOperationException</tt>.<p> 1191 * 1192 * The returned list will be serializable if the specified list 1193 * is serializable. Similarly, the returned list will implement 1194 * {@link RandomAccess} if the specified list does. 1195 * 1196 * @param list the list for which an unmodifiable view is to be returned. 1197 * @return an unmodifiable view of the specified list. 1198 */ 1199 public static <T> List<T> unmodifiableList(List<? extends T> list) { 1200 return (list instanceof RandomAccess ? 1201 new UnmodifiableRandomAccessList<>(list) : 1202 new UnmodifiableList<>(list)); 1203 } 1204 1205 /** 1206 * @serial include 1207 */ 1208 static class UnmodifiableList<E> extends UnmodifiableCollection<E> 1209 implements List<E> { 1210 private static final long serialVersionUID = -283967356065247728L; 1211 final List<? extends E> list; 1212 1213 UnmodifiableList(List<? extends E> list) { 1214 super(list); 1215 this.list = list; 1216 } 1217 1218 public boolean equals(Object o) {return o == this || list.equals(o);} 1219 public int hashCode() {return list.hashCode();} 1220 1221 public E get(int index) {return list.get(index);} 1222 public E set(int index, E element) { 1223 throw new UnsupportedOperationException(); 1224 } 1225 public void add(int index, E element) { 1226 throw new UnsupportedOperationException(); 1227 } 1228 public E remove(int index) { 1229 throw new UnsupportedOperationException(); 1230 } 1231 public int indexOf(Object o) {return list.indexOf(o);} 1232 public int lastIndexOf(Object o) {return list.lastIndexOf(o);} 1233 public boolean addAll(int index, Collection<? extends E> c) { 1234 throw new UnsupportedOperationException(); 1235 } 1236 public ListIterator<E> listIterator() {return listIterator(0);} 1237 1238 public ListIterator<E> listIterator(final int index) { 1239 return new ListIterator<E>() { 1240 private final ListIterator<? extends E> i 1241 = list.listIterator(index); 1242 1243 public boolean hasNext() {return i.hasNext();} 1244 public E next() {return i.next();} 1245 public boolean hasPrevious() {return i.hasPrevious();} 1246 public E previous() {return i.previous();} 1247 public int nextIndex() {return i.nextIndex();} 1248 public int previousIndex() {return i.previousIndex();} 1249 1250 public void remove() { 1251 throw new UnsupportedOperationException(); 1252 } 1253 public void set(E e) { 1254 throw new UnsupportedOperationException(); 1255 } 1256 public void add(E e) { 1257 throw new UnsupportedOperationException(); 1258 } 1259 }; 1260 } 1261 1262 public List<E> subList(int fromIndex, int toIndex) { 1263 return new UnmodifiableList<>(list.subList(fromIndex, toIndex)); 1264 } 1265 1266 /** 1267 * UnmodifiableRandomAccessList instances are serialized as 1268 * UnmodifiableList instances to allow them to be deserialized 1269 * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList). 1270 * This method inverts the transformation. As a beneficial 1271 * side-effect, it also grafts the RandomAccess marker onto 1272 * UnmodifiableList instances that were serialized in pre-1.4 JREs. 1273 * 1274 * Note: Unfortunately, UnmodifiableRandomAccessList instances 1275 * serialized in 1.4.1 and deserialized in 1.4 will become 1276 * UnmodifiableList instances, as this method was missing in 1.4. 1277 */ 1278 private Object readResolve() { 1279 return (list instanceof RandomAccess 1280 ? new UnmodifiableRandomAccessList<>(list) 1281 : this); 1282 } 1283 } 1284 1285 /** 1286 * @serial include 1287 */ 1288 static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E> 1289 implements RandomAccess 1290 { 1291 UnmodifiableRandomAccessList(List<? extends E> list) { 1292 super(list); 1293 } 1294 1295 public List<E> subList(int fromIndex, int toIndex) { 1296 return new UnmodifiableRandomAccessList<>( 1297 list.subList(fromIndex, toIndex)); 1298 } 1299 1300 private static final long serialVersionUID = -2542308836966382001L; 1301 1302 /** 1303 * Allows instances to be deserialized in pre-1.4 JREs (which do 1304 * not have UnmodifiableRandomAccessList). UnmodifiableList has 1305 * a readResolve method that inverts this transformation upon 1306 * deserialization. 1307 */ 1308 private Object writeReplace() { 1309 return new UnmodifiableList<>(list); 1310 } 1311 } 1312 1313 /** 1314 * Returns an unmodifiable view of the specified map. This method 1315 * allows modules to provide users with "read-only" access to internal 1316 * maps. Query operations on the returned map "read through" 1317 * to the specified map, and attempts to modify the returned 1318 * map, whether direct or via its collection views, result in an 1319 * <tt>UnsupportedOperationException</tt>.<p> 1320 * 1321 * The returned map will be serializable if the specified map 1322 * is serializable. 1323 * 1324 * @param m the map for which an unmodifiable view is to be returned. 1325 * @return an unmodifiable view of the specified map. 1326 */ 1327 public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) { 1328 return new UnmodifiableMap<>(m); 1329 } 1330 1331 /** 1332 * @serial include 1333 */ 1334 private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable { 1335 private static final long serialVersionUID = -1034234728574286014L; 1336 1337 private final Map<? extends K, ? extends V> m; 1338 1339 UnmodifiableMap(Map<? extends K, ? extends V> m) { 1340 if (m==null) 1341 throw new NullPointerException(); 1342 this.m = m; 1343 } 1344 1345 public int size() {return m.size();} 1346 public boolean isEmpty() {return m.isEmpty();} 1347 public boolean containsKey(Object key) {return m.containsKey(key);} 1348 public boolean containsValue(Object val) {return m.containsValue(val);} 1349 public V get(Object key) {return m.get(key);} 1350 1351 public V put(K key, V value) { 1352 throw new UnsupportedOperationException(); 1353 } 1354 public V remove(Object key) { 1355 throw new UnsupportedOperationException(); 1356 } 1357 public void putAll(Map<? extends K, ? extends V> m) { 1358 throw new UnsupportedOperationException(); 1359 } 1360 public void clear() { 1361 throw new UnsupportedOperationException(); 1362 } 1363 1364 private transient Set<K> keySet = null; 1365 private transient Set<Map.Entry<K,V>> entrySet = null; 1366 private transient Collection<V> values = null; 1367 1368 public Set<K> keySet() { 1369 if (keySet==null) 1370 keySet = unmodifiableSet(m.keySet()); 1371 return keySet; 1372 } 1373 1374 public Set<Map.Entry<K,V>> entrySet() { 1375 if (entrySet==null) 1376 entrySet = new UnmodifiableEntrySet<>(m.entrySet()); 1377 return entrySet; 1378 } 1379 1380 public Collection<V> values() { 1381 if (values==null) 1382 values = unmodifiableCollection(m.values()); 1383 return values; 1384 } 1385 1386 public boolean equals(Object o) {return o == this || m.equals(o);} 1387 public int hashCode() {return m.hashCode();} 1388 public String toString() {return m.toString();} 1389 1390 /** 1391 * We need this class in addition to UnmodifiableSet as 1392 * Map.Entries themselves permit modification of the backing Map 1393 * via their setValue operation. This class is subtle: there are 1394 * many possible attacks that must be thwarted. 1395 * 1396 * @serial include 1397 */ 1398 static class UnmodifiableEntrySet<K,V> 1399 extends UnmodifiableSet<Map.Entry<K,V>> { 1400 private static final long serialVersionUID = 7854390611657943733L; 1401 1402 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) { 1403 super((Set)s); 1404 } 1405 public Iterator<Map.Entry<K,V>> iterator() { 1406 return new Iterator<Map.Entry<K,V>>() { 1407 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator(); 1408 1409 public boolean hasNext() { 1410 return i.hasNext(); 1411 } 1412 public Map.Entry<K,V> next() { 1413 return new UnmodifiableEntry<>(i.next()); 1414 } 1415 public void remove() { 1416 throw new UnsupportedOperationException(); 1417 } 1418 }; 1419 } 1420 1421 public Object[] toArray() { 1422 Object[] a = c.toArray(); 1423 for (int i=0; i<a.length; i++) 1424 a[i] = new UnmodifiableEntry<>((Map.Entry<K,V>)a[i]); 1425 return a; 1426 } 1427 1428 public <T> T[] toArray(T[] a) { 1429 // We don't pass a to c.toArray, to avoid window of 1430 // vulnerability wherein an unscrupulous multithreaded client 1431 // could get his hands on raw (unwrapped) Entries from c. 1432 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); 1433 1434 for (int i=0; i<arr.length; i++) 1435 arr[i] = new UnmodifiableEntry<>((Map.Entry<K,V>)arr[i]); 1436 1437 if (arr.length > a.length) 1438 return (T[])arr; 1439 1440 System.arraycopy(arr, 0, a, 0, arr.length); 1441 if (a.length > arr.length) 1442 a[arr.length] = null; 1443 return a; 1444 } 1445 1446 /** 1447 * This method is overridden to protect the backing set against 1448 * an object with a nefarious equals function that senses 1449 * that the equality-candidate is Map.Entry and calls its 1450 * setValue method. 1451 */ 1452 public boolean contains(Object o) { 1453 if (!(o instanceof Map.Entry)) 1454 return false; 1455 return c.contains( 1456 new UnmodifiableEntry<>((Map.Entry<?,?>) o)); 1457 } 1458 1459 /** 1460 * The next two methods are overridden to protect against 1461 * an unscrupulous List whose contains(Object o) method senses 1462 * when o is a Map.Entry, and calls o.setValue. 1463 */ 1464 public boolean containsAll(Collection<?> coll) { 1465 for (Object e : coll) { 1466 if (!contains(e)) // Invokes safe contains() above 1467 return false; 1468 } 1469 return true; 1470 } 1471 public boolean equals(Object o) { 1472 if (o == this) 1473 return true; 1474 1475 if (!(o instanceof Set)) 1476 return false; 1477 Set s = (Set) o; 1478 if (s.size() != c.size()) 1479 return false; 1480 return containsAll(s); // Invokes safe containsAll() above 1481 } 1482 1483 /** 1484 * This "wrapper class" serves two purposes: it prevents 1485 * the client from modifying the backing Map, by short-circuiting 1486 * the setValue method, and it protects the backing Map against 1487 * an ill-behaved Map.Entry that attempts to modify another 1488 * Map Entry when asked to perform an equality check. 1489 */ 1490 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> { 1491 private Map.Entry<? extends K, ? extends V> e; 1492 1493 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;} 1494 1495 public K getKey() {return e.getKey();} 1496 public V getValue() {return e.getValue();} 1497 public V setValue(V value) { 1498 throw new UnsupportedOperationException(); 1499 } 1500 public int hashCode() {return e.hashCode();} 1501 public boolean equals(Object o) { 1502 if (this == o) 1503 return true; 1504 if (!(o instanceof Map.Entry)) 1505 return false; 1506 Map.Entry t = (Map.Entry)o; 1507 return eq(e.getKey(), t.getKey()) && 1508 eq(e.getValue(), t.getValue()); 1509 } 1510 public String toString() {return e.toString();} 1511 } 1512 } 1513 } 1514 1515 /** 1516 * Returns an unmodifiable view of the specified sorted map. This method 1517 * allows modules to provide users with "read-only" access to internal 1518 * sorted maps. Query operations on the returned sorted map "read through" 1519 * to the specified sorted map. Attempts to modify the returned 1520 * sorted map, whether direct, via its collection views, or via its 1521 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in 1522 * an <tt>UnsupportedOperationException</tt>.<p> 1523 * 1524 * The returned sorted map will be serializable if the specified sorted map 1525 * is serializable. 1526 * 1527 * @param m the sorted map for which an unmodifiable view is to be 1528 * returned. 1529 * @return an unmodifiable view of the specified sorted map. 1530 */ 1531 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) { 1532 return new UnmodifiableSortedMap<>(m); 1533 } 1534 1535 /** 1536 * @serial include 1537 */ 1538 static class UnmodifiableSortedMap<K,V> 1539 extends UnmodifiableMap<K,V> 1540 implements SortedMap<K,V>, Serializable { 1541 private static final long serialVersionUID = -8806743815996713206L; 1542 1543 private final SortedMap<K, ? extends V> sm; 1544 1545 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;} 1546 1547 public Comparator<? super K> comparator() {return sm.comparator();} 1548 1549 public SortedMap<K,V> subMap(K fromKey, K toKey) { 1550 return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey)); 1551 } 1552 public SortedMap<K,V> headMap(K toKey) { 1553 return new UnmodifiableSortedMap<>(sm.headMap(toKey)); 1554 } 1555 public SortedMap<K,V> tailMap(K fromKey) { 1556 return new UnmodifiableSortedMap<>(sm.tailMap(fromKey)); 1557 } 1558 1559 public K firstKey() {return sm.firstKey();} 1560 public K lastKey() {return sm.lastKey();} 1561 } 1562 1563 1564 // Synch Wrappers 1565 1566 /** 1567 * Returns a synchronized (thread-safe) collection backed by the specified 1568 * collection. In order to guarantee serial access, it is critical that 1569 * <strong>all</strong> access to the backing collection is accomplished 1570 * through the returned collection.<p> 1571 * 1572 * It is imperative that the user manually synchronize on the returned 1573 * collection when iterating over it: 1574 * <pre> 1575 * Collection c = Collections.synchronizedCollection(myCollection); 1576 * ... 1577 * synchronized (c) { 1578 * Iterator i = c.iterator(); // Must be in the synchronized block 1579 * while (i.hasNext()) 1580 * foo(i.next()); 1581 * } 1582 * </pre> 1583 * Failure to follow this advice may result in non-deterministic behavior. 1584 * 1585 * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt> 1586 * and <tt>equals</tt> operations through to the backing collection, but 1587 * relies on <tt>Object</tt>'s equals and hashCode methods. This is 1588 * necessary to preserve the contracts of these operations in the case 1589 * that the backing collection is a set or a list.<p> 1590 * 1591 * The returned collection will be serializable if the specified collection 1592 * is serializable. 1593 * 1594 * @param c the collection to be "wrapped" in a synchronized collection. 1595 * @return a synchronized view of the specified collection. 1596 */ 1597 public static <T> Collection<T> synchronizedCollection(Collection<T> c) { 1598 return new SynchronizedCollection<>(c); 1599 } 1600 1601 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) { 1602 return new SynchronizedCollection<>(c, mutex); 1603 } 1604 1605 /** 1606 * @serial include 1607 */ 1608 static class SynchronizedCollection<E> implements Collection<E>, Serializable { 1609 private static final long serialVersionUID = 3053995032091335093L; 1610 1611 final Collection<E> c; // Backing Collection 1612 final Object mutex; // Object on which to synchronize 1613 1614 SynchronizedCollection(Collection<E> c) { 1615 if (c==null) 1616 throw new NullPointerException(); 1617 this.c = c; 1618 mutex = this; 1619 } 1620 SynchronizedCollection(Collection<E> c, Object mutex) { 1621 this.c = c; 1622 this.mutex = mutex; 1623 } 1624 1625 public int size() { 1626 synchronized (mutex) {return c.size();} 1627 } 1628 public boolean isEmpty() { 1629 synchronized (mutex) {return c.isEmpty();} 1630 } 1631 public boolean contains(Object o) { 1632 synchronized (mutex) {return c.contains(o);} 1633 } 1634 public Object[] toArray() { 1635 synchronized (mutex) {return c.toArray();} 1636 } 1637 public <T> T[] toArray(T[] a) { 1638 synchronized (mutex) {return c.toArray(a);} 1639 } 1640 1641 public Iterator<E> iterator() { 1642 return c.iterator(); // Must be manually synched by user! 1643 } 1644 1645 public boolean add(E e) { 1646 synchronized (mutex) {return c.add(e);} 1647 } 1648 public boolean remove(Object o) { 1649 synchronized (mutex) {return c.remove(o);} 1650 } 1651 1652 public boolean containsAll(Collection<?> coll) { 1653 synchronized (mutex) {return c.containsAll(coll);} 1654 } 1655 public boolean addAll(Collection<? extends E> coll) { 1656 synchronized (mutex) {return c.addAll(coll);} 1657 } 1658 public boolean removeAll(Collection<?> coll) { 1659 synchronized (mutex) {return c.removeAll(coll);} 1660 } 1661 public boolean retainAll(Collection<?> coll) { 1662 synchronized (mutex) {return c.retainAll(coll);} 1663 } 1664 public void clear() { 1665 synchronized (mutex) {c.clear();} 1666 } 1667 public String toString() { 1668 synchronized (mutex) {return c.toString();} 1669 } 1670 private void writeObject(ObjectOutputStream s) throws IOException { 1671 synchronized (mutex) {s.defaultWriteObject();} 1672 } 1673 } 1674 1675 /** 1676 * Returns a synchronized (thread-safe) set backed by the specified 1677 * set. In order to guarantee serial access, it is critical that 1678 * <strong>all</strong> access to the backing set is accomplished 1679 * through the returned set.<p> 1680 * 1681 * It is imperative that the user manually synchronize on the returned 1682 * set when iterating over it: 1683 * <pre> 1684 * Set s = Collections.synchronizedSet(new HashSet()); 1685 * ... 1686 * synchronized (s) { 1687 * Iterator i = s.iterator(); // Must be in the synchronized block 1688 * while (i.hasNext()) 1689 * foo(i.next()); 1690 * } 1691 * </pre> 1692 * Failure to follow this advice may result in non-deterministic behavior. 1693 * 1694 * <p>The returned set will be serializable if the specified set is 1695 * serializable. 1696 * 1697 * @param s the set to be "wrapped" in a synchronized set. 1698 * @return a synchronized view of the specified set. 1699 */ 1700 public static <T> Set<T> synchronizedSet(Set<T> s) { 1701 return new SynchronizedSet<>(s); 1702 } 1703 1704 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) { 1705 return new SynchronizedSet<>(s, mutex); 1706 } 1707 1708 /** 1709 * @serial include 1710 */ 1711 static class SynchronizedSet<E> 1712 extends SynchronizedCollection<E> 1713 implements Set<E> { 1714 private static final long serialVersionUID = 487447009682186044L; 1715 1716 SynchronizedSet(Set<E> s) { 1717 super(s); 1718 } 1719 SynchronizedSet(Set<E> s, Object mutex) { 1720 super(s, mutex); 1721 } 1722 1723 public boolean equals(Object o) { 1724 if (this == o) 1725 return true; 1726 synchronized (mutex) {return c.equals(o);} 1727 } 1728 public int hashCode() { 1729 synchronized (mutex) {return c.hashCode();} 1730 } 1731 } 1732 1733 /** 1734 * Returns a synchronized (thread-safe) sorted set backed by the specified 1735 * sorted set. In order to guarantee serial access, it is critical that 1736 * <strong>all</strong> access to the backing sorted set is accomplished 1737 * through the returned sorted set (or its views).<p> 1738 * 1739 * It is imperative that the user manually synchronize on the returned 1740 * sorted set when iterating over it or any of its <tt>subSet</tt>, 1741 * <tt>headSet</tt>, or <tt>tailSet</tt> views. 1742 * <pre> 1743 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet()); 1744 * ... 1745 * synchronized (s) { 1746 * Iterator i = s.iterator(); // Must be in the synchronized block 1747 * while (i.hasNext()) 1748 * foo(i.next()); 1749 * } 1750 * </pre> 1751 * or: 1752 * <pre> 1753 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet()); 1754 * SortedSet s2 = s.headSet(foo); 1755 * ... 1756 * synchronized (s) { // Note: s, not s2!!! 1757 * Iterator i = s2.iterator(); // Must be in the synchronized block 1758 * while (i.hasNext()) 1759 * foo(i.next()); 1760 * } 1761 * </pre> 1762 * Failure to follow this advice may result in non-deterministic behavior. 1763 * 1764 * <p>The returned sorted set will be serializable if the specified 1765 * sorted set is serializable. 1766 * 1767 * @param s the sorted set to be "wrapped" in a synchronized sorted set. 1768 * @return a synchronized view of the specified sorted set. 1769 */ 1770 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) { 1771 return new SynchronizedSortedSet<>(s); 1772 } 1773 1774 /** 1775 * @serial include 1776 */ 1777 static class SynchronizedSortedSet<E> 1778 extends SynchronizedSet<E> 1779 implements SortedSet<E> 1780 { 1781 private static final long serialVersionUID = 8695801310862127406L; 1782 1783 private final SortedSet<E> ss; 1784 1785 SynchronizedSortedSet(SortedSet<E> s) { 1786 super(s); 1787 ss = s; 1788 } 1789 SynchronizedSortedSet(SortedSet<E> s, Object mutex) { 1790 super(s, mutex); 1791 ss = s; 1792 } 1793 1794 public Comparator<? super E> comparator() { 1795 synchronized (mutex) {return ss.comparator();} 1796 } 1797 1798 public SortedSet<E> subSet(E fromElement, E toElement) { 1799 synchronized (mutex) { 1800 return new SynchronizedSortedSet<>( 1801 ss.subSet(fromElement, toElement), mutex); 1802 } 1803 } 1804 public SortedSet<E> headSet(E toElement) { 1805 synchronized (mutex) { 1806 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex); 1807 } 1808 } 1809 public SortedSet<E> tailSet(E fromElement) { 1810 synchronized (mutex) { 1811 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex); 1812 } 1813 } 1814 1815 public E first() { 1816 synchronized (mutex) {return ss.first();} 1817 } 1818 public E last() { 1819 synchronized (mutex) {return ss.last();} 1820 } 1821 } 1822 1823 /** 1824 * Returns a synchronized (thread-safe) list backed by the specified 1825 * list. In order to guarantee serial access, it is critical that 1826 * <strong>all</strong> access to the backing list is accomplished 1827 * through the returned list.<p> 1828 * 1829 * It is imperative that the user manually synchronize on the returned 1830 * list when iterating over it: 1831 * <pre> 1832 * List list = Collections.synchronizedList(new ArrayList()); 1833 * ... 1834 * synchronized (list) { 1835 * Iterator i = list.iterator(); // Must be in synchronized block 1836 * while (i.hasNext()) 1837 * foo(i.next()); 1838 * } 1839 * </pre> 1840 * Failure to follow this advice may result in non-deterministic behavior. 1841 * 1842 * <p>The returned list will be serializable if the specified list is 1843 * serializable. 1844 * 1845 * @param list the list to be "wrapped" in a synchronized list. 1846 * @return a synchronized view of the specified list. 1847 */ 1848 public static <T> List<T> synchronizedList(List<T> list) { 1849 return (list instanceof RandomAccess ? 1850 new SynchronizedRandomAccessList<>(list) : 1851 new SynchronizedList<>(list)); 1852 } 1853 1854 static <T> List<T> synchronizedList(List<T> list, Object mutex) { 1855 return (list instanceof RandomAccess ? 1856 new SynchronizedRandomAccessList<>(list, mutex) : 1857 new SynchronizedList<>(list, mutex)); 1858 } 1859 1860 /** 1861 * @serial include 1862 */ 1863 static class SynchronizedList<E> 1864 extends SynchronizedCollection<E> 1865 implements List<E> { 1866 private static final long serialVersionUID = -7754090372962971524L; 1867 1868 final List<E> list; 1869 1870 SynchronizedList(List<E> list) { 1871 super(list); 1872 this.list = list; 1873 } 1874 SynchronizedList(List<E> list, Object mutex) { 1875 super(list, mutex); 1876 this.list = list; 1877 } 1878 1879 public boolean equals(Object o) { 1880 if (this == o) 1881 return true; 1882 synchronized (mutex) {return list.equals(o);} 1883 } 1884 public int hashCode() { 1885 synchronized (mutex) {return list.hashCode();} 1886 } 1887 1888 public E get(int index) { 1889 synchronized (mutex) {return list.get(index);} 1890 } 1891 public E set(int index, E element) { 1892 synchronized (mutex) {return list.set(index, element);} 1893 } 1894 public void add(int index, E element) { 1895 synchronized (mutex) {list.add(index, element);} 1896 } 1897 public E remove(int index) { 1898 synchronized (mutex) {return list.remove(index);} 1899 } 1900 1901 public int indexOf(Object o) { 1902 synchronized (mutex) {return list.indexOf(o);} 1903 } 1904 public int lastIndexOf(Object o) { 1905 synchronized (mutex) {return list.lastIndexOf(o);} 1906 } 1907 1908 public boolean addAll(int index, Collection<? extends E> c) { 1909 synchronized (mutex) {return list.addAll(index, c);} 1910 } 1911 1912 public ListIterator<E> listIterator() { 1913 return list.listIterator(); // Must be manually synched by user 1914 } 1915 1916 public ListIterator<E> listIterator(int index) { 1917 return list.listIterator(index); // Must be manually synched by user 1918 } 1919 1920 public List<E> subList(int fromIndex, int toIndex) { 1921 synchronized (mutex) { 1922 return new SynchronizedList<>(list.subList(fromIndex, toIndex), 1923 mutex); 1924 } 1925 } 1926 1927 /** 1928 * SynchronizedRandomAccessList instances are serialized as 1929 * SynchronizedList instances to allow them to be deserialized 1930 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList). 1931 * This method inverts the transformation. As a beneficial 1932 * side-effect, it also grafts the RandomAccess marker onto 1933 * SynchronizedList instances that were serialized in pre-1.4 JREs. 1934 * 1935 * Note: Unfortunately, SynchronizedRandomAccessList instances 1936 * serialized in 1.4.1 and deserialized in 1.4 will become 1937 * SynchronizedList instances, as this method was missing in 1.4. 1938 */ 1939 private Object readResolve() { 1940 return (list instanceof RandomAccess 1941 ? new SynchronizedRandomAccessList<>(list) 1942 : this); 1943 } 1944 } 1945 1946 /** 1947 * @serial include 1948 */ 1949 static class SynchronizedRandomAccessList<E> 1950 extends SynchronizedList<E> 1951 implements RandomAccess { 1952 1953 SynchronizedRandomAccessList(List<E> list) { 1954 super(list); 1955 } 1956 1957 SynchronizedRandomAccessList(List<E> list, Object mutex) { 1958 super(list, mutex); 1959 } 1960 1961 public List<E> subList(int fromIndex, int toIndex) { 1962 synchronized (mutex) { 1963 return new SynchronizedRandomAccessList<>( 1964 list.subList(fromIndex, toIndex), mutex); 1965 } 1966 } 1967 1968 private static final long serialVersionUID = 1530674583602358482L; 1969 1970 /** 1971 * Allows instances to be deserialized in pre-1.4 JREs (which do 1972 * not have SynchronizedRandomAccessList). SynchronizedList has 1973 * a readResolve method that inverts this transformation upon 1974 * deserialization. 1975 */ 1976 private Object writeReplace() { 1977 return new SynchronizedList<>(list); 1978 } 1979 } 1980 1981 /** 1982 * Returns a synchronized (thread-safe) map backed by the specified 1983 * map. In order to guarantee serial access, it is critical that 1984 * <strong>all</strong> access to the backing map is accomplished 1985 * through the returned map.<p> 1986 * 1987 * It is imperative that the user manually synchronize on the returned 1988 * map when iterating over any of its collection views: 1989 * <pre> 1990 * Map m = Collections.synchronizedMap(new HashMap()); 1991 * ... 1992 * Set s = m.keySet(); // Needn't be in synchronized block 1993 * ... 1994 * synchronized (m) { // Synchronizing on m, not s! 1995 * Iterator i = s.iterator(); // Must be in synchronized block 1996 * while (i.hasNext()) 1997 * foo(i.next()); 1998 * } 1999 * </pre> 2000 * Failure to follow this advice may result in non-deterministic behavior. 2001 * 2002 * <p>The returned map will be serializable if the specified map is 2003 * serializable. 2004 * 2005 * @param m the map to be "wrapped" in a synchronized map. 2006 * @return a synchronized view of the specified map. 2007 */ 2008 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { 2009 return new SynchronizedMap<>(m); 2010 } 2011 2012 /** 2013 * @serial include 2014 */ 2015 private static class SynchronizedMap<K,V> 2016 implements Map<K,V>, Serializable { 2017 private static final long serialVersionUID = 1978198479659022715L; 2018 2019 private final Map<K,V> m; // Backing Map 2020 final Object mutex; // Object on which to synchronize 2021 2022 SynchronizedMap(Map<K,V> m) { 2023 if (m==null) 2024 throw new NullPointerException(); 2025 this.m = m; 2026 mutex = this; 2027 } 2028 2029 SynchronizedMap(Map<K,V> m, Object mutex) { 2030 this.m = m; 2031 this.mutex = mutex; 2032 } 2033 2034 public int size() { 2035 synchronized (mutex) {return m.size();} 2036 } 2037 public boolean isEmpty() { 2038 synchronized (mutex) {return m.isEmpty();} 2039 } 2040 public boolean containsKey(Object key) { 2041 synchronized (mutex) {return m.containsKey(key);} 2042 } 2043 public boolean containsValue(Object value) { 2044 synchronized (mutex) {return m.containsValue(value);} 2045 } 2046 public V get(Object key) { 2047 synchronized (mutex) {return m.get(key);} 2048 } 2049 2050 public V put(K key, V value) { 2051 synchronized (mutex) {return m.put(key, value);} 2052 } 2053 public V remove(Object key) { 2054 synchronized (mutex) {return m.remove(key);} 2055 } 2056 public void putAll(Map<? extends K, ? extends V> map) { 2057 synchronized (mutex) {m.putAll(map);} 2058 } 2059 public void clear() { 2060 synchronized (mutex) {m.clear();} 2061 } 2062 2063 private transient Set<K> keySet = null; 2064 private transient Set<Map.Entry<K,V>> entrySet = null; 2065 private transient Collection<V> values = null; 2066 2067 public Set<K> keySet() { 2068 synchronized (mutex) { 2069 if (keySet==null) 2070 keySet = new SynchronizedSet<>(m.keySet(), mutex); 2071 return keySet; 2072 } 2073 } 2074 2075 public Set<Map.Entry<K,V>> entrySet() { 2076 synchronized (mutex) { 2077 if (entrySet==null) 2078 entrySet = new SynchronizedSet<>(m.entrySet(), mutex); 2079 return entrySet; 2080 } 2081 } 2082 2083 public Collection<V> values() { 2084 synchronized (mutex) { 2085 if (values==null) 2086 values = new SynchronizedCollection<>(m.values(), mutex); 2087 return values; 2088 } 2089 } 2090 2091 public boolean equals(Object o) { 2092 if (this == o) 2093 return true; 2094 synchronized (mutex) {return m.equals(o);} 2095 } 2096 public int hashCode() { 2097 synchronized (mutex) {return m.hashCode();} 2098 } 2099 public String toString() { 2100 synchronized (mutex) {return m.toString();} 2101 } 2102 private void writeObject(ObjectOutputStream s) throws IOException { 2103 synchronized (mutex) {s.defaultWriteObject();} 2104 } 2105 } 2106 2107 /** 2108 * Returns a synchronized (thread-safe) sorted map backed by the specified 2109 * sorted map. In order to guarantee serial access, it is critical that 2110 * <strong>all</strong> access to the backing sorted map is accomplished 2111 * through the returned sorted map (or its views).<p> 2112 * 2113 * It is imperative that the user manually synchronize on the returned 2114 * sorted map when iterating over any of its collection views, or the 2115 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or 2116 * <tt>tailMap</tt> views. 2117 * <pre> 2118 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap()); 2119 * ... 2120 * Set s = m.keySet(); // Needn't be in synchronized block 2121 * ... 2122 * synchronized (m) { // Synchronizing on m, not s! 2123 * Iterator i = s.iterator(); // Must be in synchronized block 2124 * while (i.hasNext()) 2125 * foo(i.next()); 2126 * } 2127 * </pre> 2128 * or: 2129 * <pre> 2130 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap()); 2131 * SortedMap m2 = m.subMap(foo, bar); 2132 * ... 2133 * Set s2 = m2.keySet(); // Needn't be in synchronized block 2134 * ... 2135 * synchronized (m) { // Synchronizing on m, not m2 or s2! 2136 * Iterator i = s.iterator(); // Must be in synchronized block 2137 * while (i.hasNext()) 2138 * foo(i.next()); 2139 * } 2140 * </pre> 2141 * Failure to follow this advice may result in non-deterministic behavior. 2142 * 2143 * <p>The returned sorted map will be serializable if the specified 2144 * sorted map is serializable. 2145 * 2146 * @param m the sorted map to be "wrapped" in a synchronized sorted map. 2147 * @return a synchronized view of the specified sorted map. 2148 */ 2149 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) { 2150 return new SynchronizedSortedMap<>(m); 2151 } 2152 2153 2154 /** 2155 * @serial include 2156 */ 2157 static class SynchronizedSortedMap<K,V> 2158 extends SynchronizedMap<K,V> 2159 implements SortedMap<K,V> 2160 { 2161 private static final long serialVersionUID = -8798146769416483793L; 2162 2163 private final SortedMap<K,V> sm; 2164 2165 SynchronizedSortedMap(SortedMap<K,V> m) { 2166 super(m); 2167 sm = m; 2168 } 2169 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) { 2170 super(m, mutex); 2171 sm = m; 2172 } 2173 2174 public Comparator<? super K> comparator() { 2175 synchronized (mutex) {return sm.comparator();} 2176 } 2177 2178 public SortedMap<K,V> subMap(K fromKey, K toKey) { 2179 synchronized (mutex) { 2180 return new SynchronizedSortedMap<>( 2181 sm.subMap(fromKey, toKey), mutex); 2182 } 2183 } 2184 public SortedMap<K,V> headMap(K toKey) { 2185 synchronized (mutex) { 2186 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex); 2187 } 2188 } 2189 public SortedMap<K,V> tailMap(K fromKey) { 2190 synchronized (mutex) { 2191 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex); 2192 } 2193 } 2194 2195 public K firstKey() { 2196 synchronized (mutex) {return sm.firstKey();} 2197 } 2198 public K lastKey() { 2199 synchronized (mutex) {return sm.lastKey();} 2200 } 2201 } 2202 2203 // Dynamically typesafe collection wrappers 2204 2205 /** 2206 * Returns a dynamically typesafe view of the specified collection. 2207 * Any attempt to insert an element of the wrong type will result in an 2208 * immediate {@link ClassCastException}. Assuming a collection 2209 * contains no incorrectly typed elements prior to the time a 2210 * dynamically typesafe view is generated, and that all subsequent 2211 * access to the collection takes place through the view, it is 2212 * <i>guaranteed</i> that the collection cannot contain an incorrectly 2213 * typed element. 2214 * 2215 * <p>The generics mechanism in the language provides compile-time 2216 * (static) type checking, but it is possible to defeat this mechanism 2217 * with unchecked casts. Usually this is not a problem, as the compiler 2218 * issues warnings on all such unchecked operations. There are, however, 2219 * times when static type checking alone is not sufficient. For example, 2220 * suppose a collection is passed to a third-party library and it is 2221 * imperative that the library code not corrupt the collection by 2222 * inserting an element of the wrong type. 2223 * 2224 * <p>Another use of dynamically typesafe views is debugging. Suppose a 2225 * program fails with a {@code ClassCastException}, indicating that an 2226 * incorrectly typed element was put into a parameterized collection. 2227 * Unfortunately, the exception can occur at any time after the erroneous 2228 * element is inserted, so it typically provides little or no information 2229 * as to the real source of the problem. If the problem is reproducible, 2230 * one can quickly determine its source by temporarily modifying the 2231 * program to wrap the collection with a dynamically typesafe view. 2232 * For example, this declaration: 2233 * <pre> {@code 2234 * Collection<String> c = new HashSet<String>(); 2235 * }</pre> 2236 * may be replaced temporarily by this one: 2237 * <pre> {@code 2238 * Collection<String> c = Collections.checkedCollection( 2239 * new HashSet<String>(), String.class); 2240 * }</pre> 2241 * Running the program again will cause it to fail at the point where 2242 * an incorrectly typed element is inserted into the collection, clearly 2243 * identifying the source of the problem. Once the problem is fixed, the 2244 * modified declaration may be reverted back to the original. 2245 * 2246 * <p>The returned collection does <i>not</i> pass the hashCode and equals 2247 * operations through to the backing collection, but relies on 2248 * {@code Object}'s {@code equals} and {@code hashCode} methods. This 2249 * is necessary to preserve the contracts of these operations in the case 2250 * that the backing collection is a set or a list. 2251 * 2252 * <p>The returned collection will be serializable if the specified 2253 * collection is serializable. 2254 * 2255 * <p>Since {@code null} is considered to be a value of any reference 2256 * type, the returned collection permits insertion of null elements 2257 * whenever the backing collection does. 2258 * 2259 * @param c the collection for which a dynamically typesafe view is to be 2260 * returned 2261 * @param type the type of element that {@code c} is permitted to hold 2262 * @return a dynamically typesafe view of the specified collection 2263 * @since 1.5 2264 */ 2265 public static <E> Collection<E> checkedCollection(Collection<E> c, 2266 Class<E> type) { 2267 return new CheckedCollection<>(c, type); 2268 } 2269 2270 @SuppressWarnings("unchecked") 2271 static <T> T[] zeroLengthArray(Class<T> type) { 2272 return (T[]) Array.newInstance(type, 0); 2273 } 2274 2275 /** 2276 * @serial include 2277 */ 2278 static class CheckedCollection<E> implements Collection<E>, Serializable { 2279 private static final long serialVersionUID = 1578914078182001775L; 2280 2281 final Collection<E> c; 2282 final Class<E> type; 2283 2284 void typeCheck(Object o) { 2285 if (o != null && !type.isInstance(o)) 2286 throw new ClassCastException(badElementMsg(o)); 2287 } 2288 2289 private String badElementMsg(Object o) { 2290 return "Attempt to insert " + o.getClass() + 2291 " element into collection with element type " + type; 2292 } 2293 2294 CheckedCollection(Collection<E> c, Class<E> type) { 2295 if (c==null || type == null) 2296 throw new NullPointerException(); 2297 this.c = c; 2298 this.type = type; 2299 } 2300 2301 public int size() { return c.size(); } 2302 public boolean isEmpty() { return c.isEmpty(); } 2303 public boolean contains(Object o) { return c.contains(o); } 2304 public Object[] toArray() { return c.toArray(); } 2305 public <T> T[] toArray(T[] a) { return c.toArray(a); } 2306 public String toString() { return c.toString(); } 2307 public boolean remove(Object o) { return c.remove(o); } 2308 public void clear() { c.clear(); } 2309 2310 public boolean containsAll(Collection<?> coll) { 2311 return c.containsAll(coll); 2312 } 2313 public boolean removeAll(Collection<?> coll) { 2314 return c.removeAll(coll); 2315 } 2316 public boolean retainAll(Collection<?> coll) { 2317 return c.retainAll(coll); 2318 } 2319 2320 public Iterator<E> iterator() { 2321 final Iterator<E> it = c.iterator(); 2322 return new Iterator<E>() { 2323 public boolean hasNext() { return it.hasNext(); } 2324 public E next() { return it.next(); } 2325 public void remove() { it.remove(); }}; 2326 } 2327 2328 public boolean add(E e) { 2329 typeCheck(e); 2330 return c.add(e); 2331 } 2332 2333 private E[] zeroLengthElementArray = null; // Lazily initialized 2334 2335 private E[] zeroLengthElementArray() { 2336 return zeroLengthElementArray != null ? zeroLengthElementArray : 2337 (zeroLengthElementArray = zeroLengthArray(type)); 2338 } 2339 2340 @SuppressWarnings("unchecked") 2341 Collection<E> checkedCopyOf(Collection<? extends E> coll) { 2342 Object[] a = null; 2343 try { 2344 E[] z = zeroLengthElementArray(); 2345 a = coll.toArray(z); 2346 // Defend against coll violating the toArray contract 2347 if (a.getClass() != z.getClass()) 2348 a = Arrays.copyOf(a, a.length, z.getClass()); 2349 } catch (ArrayStoreException ignore) { 2350 // To get better and consistent diagnostics, 2351 // we call typeCheck explicitly on each element. 2352 // We call clone() to defend against coll retaining a 2353 // reference to the returned array and storing a bad 2354 // element into it after it has been type checked. 2355 a = coll.toArray().clone(); 2356 for (Object o : a) 2357 typeCheck(o); 2358 } 2359 // A slight abuse of the type system, but safe here. 2360 return (Collection<E>) Arrays.asList(a); 2361 } 2362 2363 public boolean addAll(Collection<? extends E> coll) { 2364 // Doing things this way insulates us from concurrent changes 2365 // in the contents of coll and provides all-or-nothing 2366 // semantics (which we wouldn't get if we type-checked each 2367 // element as we added it) 2368 return c.addAll(checkedCopyOf(coll)); 2369 } 2370 } 2371 2372 /** 2373 * Returns a dynamically typesafe view of the specified set. 2374 * Any attempt to insert an element of the wrong type will result in 2375 * an immediate {@link ClassCastException}. Assuming a set contains 2376 * no incorrectly typed elements prior to the time a dynamically typesafe 2377 * view is generated, and that all subsequent access to the set 2378 * takes place through the view, it is <i>guaranteed</i> that the 2379 * set cannot contain an incorrectly typed element. 2380 * 2381 * <p>A discussion of the use of dynamically typesafe views may be 2382 * found in the documentation for the {@link #checkedCollection 2383 * checkedCollection} method. 2384 * 2385 * <p>The returned set will be serializable if the specified set is 2386 * serializable. 2387 * 2388 * <p>Since {@code null} is considered to be a value of any reference 2389 * type, the returned set permits insertion of null elements whenever 2390 * the backing set does. 2391 * 2392 * @param s the set for which a dynamically typesafe view is to be 2393 * returned 2394 * @param type the type of element that {@code s} is permitted to hold 2395 * @return a dynamically typesafe view of the specified set 2396 * @since 1.5 2397 */ 2398 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) { 2399 return new CheckedSet<>(s, type); 2400 } 2401 2402 /** 2403 * @serial include 2404 */ 2405 static class CheckedSet<E> extends CheckedCollection<E> 2406 implements Set<E>, Serializable 2407 { 2408 private static final long serialVersionUID = 4694047833775013803L; 2409 2410 CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); } 2411 2412 public boolean equals(Object o) { return o == this || c.equals(o); } 2413 public int hashCode() { return c.hashCode(); } 2414 } 2415 2416 /** 2417 * Returns a dynamically typesafe view of the specified sorted set. 2418 * Any attempt to insert an element of the wrong type will result in an 2419 * immediate {@link ClassCastException}. Assuming a sorted set 2420 * contains no incorrectly typed elements prior to the time a 2421 * dynamically typesafe view is generated, and that all subsequent 2422 * access to the sorted set takes place through the view, it is 2423 * <i>guaranteed</i> that the sorted set cannot contain an incorrectly 2424 * typed element. 2425 * 2426 * <p>A discussion of the use of dynamically typesafe views may be 2427 * found in the documentation for the {@link #checkedCollection 2428 * checkedCollection} method. 2429 * 2430 * <p>The returned sorted set will be serializable if the specified sorted 2431 * set is serializable. 2432 * 2433 * <p>Since {@code null} is considered to be a value of any reference 2434 * type, the returned sorted set permits insertion of null elements 2435 * whenever the backing sorted set does. 2436 * 2437 * @param s the sorted set for which a dynamically typesafe view is to be 2438 * returned 2439 * @param type the type of element that {@code s} is permitted to hold 2440 * @return a dynamically typesafe view of the specified sorted set 2441 * @since 1.5 2442 */ 2443 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, 2444 Class<E> type) { 2445 return new CheckedSortedSet<>(s, type); 2446 } 2447 2448 /** 2449 * @serial include 2450 */ 2451 static class CheckedSortedSet<E> extends CheckedSet<E> 2452 implements SortedSet<E>, Serializable 2453 { 2454 private static final long serialVersionUID = 1599911165492914959L; 2455 private final SortedSet<E> ss; 2456 2457 CheckedSortedSet(SortedSet<E> s, Class<E> type) { 2458 super(s, type); 2459 ss = s; 2460 } 2461 2462 public Comparator<? super E> comparator() { return ss.comparator(); } 2463 public E first() { return ss.first(); } 2464 public E last() { return ss.last(); } 2465 2466 public SortedSet<E> subSet(E fromElement, E toElement) { 2467 return checkedSortedSet(ss.subSet(fromElement,toElement), type); 2468 } 2469 public SortedSet<E> headSet(E toElement) { 2470 return checkedSortedSet(ss.headSet(toElement), type); 2471 } 2472 public SortedSet<E> tailSet(E fromElement) { 2473 return checkedSortedSet(ss.tailSet(fromElement), type); 2474 } 2475 } 2476 2477 /** 2478 * Returns a dynamically typesafe view of the specified list. 2479 * Any attempt to insert an element of the wrong type will result in 2480 * an immediate {@link ClassCastException}. Assuming a list contains 2481 * no incorrectly typed elements prior to the time a dynamically typesafe 2482 * view is generated, and that all subsequent access to the list 2483 * takes place through the view, it is <i>guaranteed</i> that the 2484 * list cannot contain an incorrectly typed element. 2485 * 2486 * <p>A discussion of the use of dynamically typesafe views may be 2487 * found in the documentation for the {@link #checkedCollection 2488 * checkedCollection} method. 2489 * 2490 * <p>The returned list will be serializable if the specified list 2491 * is serializable. 2492 * 2493 * <p>Since {@code null} is considered to be a value of any reference 2494 * type, the returned list permits insertion of null elements whenever 2495 * the backing list does. 2496 * 2497 * @param list the list for which a dynamically typesafe view is to be 2498 * returned 2499 * @param type the type of element that {@code list} is permitted to hold 2500 * @return a dynamically typesafe view of the specified list 2501 * @since 1.5 2502 */ 2503 public static <E> List<E> checkedList(List<E> list, Class<E> type) { 2504 return (list instanceof RandomAccess ? 2505 new CheckedRandomAccessList<>(list, type) : 2506 new CheckedList<>(list, type)); 2507 } 2508 2509 /** 2510 * @serial include 2511 */ 2512 static class CheckedList<E> 2513 extends CheckedCollection<E> 2514 implements List<E> 2515 { 2516 private static final long serialVersionUID = 65247728283967356L; 2517 final List<E> list; 2518 2519 CheckedList(List<E> list, Class<E> type) { 2520 super(list, type); 2521 this.list = list; 2522 } 2523 2524 public boolean equals(Object o) { return o == this || list.equals(o); } 2525 public int hashCode() { return list.hashCode(); } 2526 public E get(int index) { return list.get(index); } 2527 public E remove(int index) { return list.remove(index); } 2528 public int indexOf(Object o) { return list.indexOf(o); } 2529 public int lastIndexOf(Object o) { return list.lastIndexOf(o); } 2530 2531 public E set(int index, E element) { 2532 typeCheck(element); 2533 return list.set(index, element); 2534 } 2535 2536 public void add(int index, E element) { 2537 typeCheck(element); 2538 list.add(index, element); 2539 } 2540 2541 public boolean addAll(int index, Collection<? extends E> c) { 2542 return list.addAll(index, checkedCopyOf(c)); 2543 } 2544 public ListIterator<E> listIterator() { return listIterator(0); } 2545 2546 public ListIterator<E> listIterator(final int index) { 2547 final ListIterator<E> i = list.listIterator(index); 2548 2549 return new ListIterator<E>() { 2550 public boolean hasNext() { return i.hasNext(); } 2551 public E next() { return i.next(); } 2552 public boolean hasPrevious() { return i.hasPrevious(); } 2553 public E previous() { return i.previous(); } 2554 public int nextIndex() { return i.nextIndex(); } 2555 public int previousIndex() { return i.previousIndex(); } 2556 public void remove() { i.remove(); } 2557 2558 public void set(E e) { 2559 typeCheck(e); 2560 i.set(e); 2561 } 2562 2563 public void add(E e) { 2564 typeCheck(e); 2565 i.add(e); 2566 } 2567 }; 2568 } 2569 2570 public List<E> subList(int fromIndex, int toIndex) { 2571 return new CheckedList<>(list.subList(fromIndex, toIndex), type); 2572 } 2573 } 2574 2575 /** 2576 * @serial include 2577 */ 2578 static class CheckedRandomAccessList<E> extends CheckedList<E> 2579 implements RandomAccess 2580 { 2581 private static final long serialVersionUID = 1638200125423088369L; 2582 2583 CheckedRandomAccessList(List<E> list, Class<E> type) { 2584 super(list, type); 2585 } 2586 2587 public List<E> subList(int fromIndex, int toIndex) { 2588 return new CheckedRandomAccessList<>( 2589 list.subList(fromIndex, toIndex), type); 2590 } 2591 } 2592 2593 /** 2594 * Returns a dynamically typesafe view of the specified map. 2595 * Any attempt to insert a mapping whose key or value have the wrong 2596 * type will result in an immediate {@link ClassCastException}. 2597 * Similarly, any attempt to modify the value currently associated with 2598 * a key will result in an immediate {@link ClassCastException}, 2599 * whether the modification is attempted directly through the map 2600 * itself, or through a {@link Map.Entry} instance obtained from the 2601 * map's {@link Map#entrySet() entry set} view. 2602 * 2603 * <p>Assuming a map contains no incorrectly typed keys or values 2604 * prior to the time a dynamically typesafe view is generated, and 2605 * that all subsequent access to the map takes place through the view 2606 * (or one of its collection views), it is <i>guaranteed</i> that the 2607 * map cannot contain an incorrectly typed key or value. 2608 * 2609 * <p>A discussion of the use of dynamically typesafe views may be 2610 * found in the documentation for the {@link #checkedCollection 2611 * checkedCollection} method. 2612 * 2613 * <p>The returned map will be serializable if the specified map is 2614 * serializable. 2615 * 2616 * <p>Since {@code null} is considered to be a value of any reference 2617 * type, the returned map permits insertion of null keys or values 2618 * whenever the backing map does. 2619 * 2620 * @param m the map for which a dynamically typesafe view is to be 2621 * returned 2622 * @param keyType the type of key that {@code m} is permitted to hold 2623 * @param valueType the type of value that {@code m} is permitted to hold 2624 * @return a dynamically typesafe view of the specified map 2625 * @since 1.5 2626 */ 2627 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, 2628 Class<K> keyType, 2629 Class<V> valueType) { 2630 return new CheckedMap<>(m, keyType, valueType); 2631 } 2632 2633 2634 /** 2635 * @serial include 2636 */ 2637 private static class CheckedMap<K,V> 2638 implements Map<K,V>, Serializable 2639 { 2640 private static final long serialVersionUID = 5742860141034234728L; 2641 2642 private final Map<K, V> m; 2643 final Class<K> keyType; 2644 final Class<V> valueType; 2645 2646 private void typeCheck(Object key, Object value) { 2647 if (key != null && !keyType.isInstance(key)) 2648 throw new ClassCastException(badKeyMsg(key)); 2649 2650 if (value != null && !valueType.isInstance(value)) 2651 throw new ClassCastException(badValueMsg(value)); 2652 } 2653 2654 private String badKeyMsg(Object key) { 2655 return "Attempt to insert " + key.getClass() + 2656 " key into map with key type " + keyType; 2657 } 2658 2659 private String badValueMsg(Object value) { 2660 return "Attempt to insert " + value.getClass() + 2661 " value into map with value type " + valueType; 2662 } 2663 2664 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) { 2665 if (m == null || keyType == null || valueType == null) 2666 throw new NullPointerException(); 2667 this.m = m; 2668 this.keyType = keyType; 2669 this.valueType = valueType; 2670 } 2671 2672 public int size() { return m.size(); } 2673 public boolean isEmpty() { return m.isEmpty(); } 2674 public boolean containsKey(Object key) { return m.containsKey(key); } 2675 public boolean containsValue(Object v) { return m.containsValue(v); } 2676 public V get(Object key) { return m.get(key); } 2677 public V remove(Object key) { return m.remove(key); } 2678 public void clear() { m.clear(); } 2679 public Set<K> keySet() { return m.keySet(); } 2680 public Collection<V> values() { return m.values(); } 2681 public boolean equals(Object o) { return o == this || m.equals(o); } 2682 public int hashCode() { return m.hashCode(); } 2683 public String toString() { return m.toString(); } 2684 2685 public V put(K key, V value) { 2686 typeCheck(key, value); 2687 return m.put(key, value); 2688 } 2689 2690 @SuppressWarnings("unchecked") 2691 public void putAll(Map<? extends K, ? extends V> t) { 2692 // Satisfy the following goals: 2693 // - good diagnostics in case of type mismatch 2694 // - all-or-nothing semantics 2695 // - protection from malicious t 2696 // - correct behavior if t is a concurrent map 2697 Object[] entries = t.entrySet().toArray(); 2698 List<Map.Entry<K,V>> checked = new ArrayList<>(entries.length); 2699 for (Object o : entries) { 2700 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 2701 Object k = e.getKey(); 2702 Object v = e.getValue(); 2703 typeCheck(k, v); 2704 checked.add( 2705 new AbstractMap.SimpleImmutableEntry<>((K) k, (V) v)); 2706 } 2707 for (Map.Entry<K,V> e : checked) 2708 m.put(e.getKey(), e.getValue()); 2709 } 2710 2711 private transient Set<Map.Entry<K,V>> entrySet = null; 2712 2713 public Set<Map.Entry<K,V>> entrySet() { 2714 if (entrySet==null) 2715 entrySet = new CheckedEntrySet<>(m.entrySet(), valueType); 2716 return entrySet; 2717 } 2718 2719 /** 2720 * We need this class in addition to CheckedSet as Map.Entry permits 2721 * modification of the backing Map via the setValue operation. This 2722 * class is subtle: there are many possible attacks that must be 2723 * thwarted. 2724 * 2725 * @serial exclude 2726 */ 2727 static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> { 2728 private final Set<Map.Entry<K,V>> s; 2729 private final Class<V> valueType; 2730 2731 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) { 2732 this.s = s; 2733 this.valueType = valueType; 2734 } 2735 2736 public int size() { return s.size(); } 2737 public boolean isEmpty() { return s.isEmpty(); } 2738 public String toString() { return s.toString(); } 2739 public int hashCode() { return s.hashCode(); } 2740 public void clear() { s.clear(); } 2741 2742 public boolean add(Map.Entry<K, V> e) { 2743 throw new UnsupportedOperationException(); 2744 } 2745 public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) { 2746 throw new UnsupportedOperationException(); 2747 } 2748 2749 public Iterator<Map.Entry<K,V>> iterator() { 2750 final Iterator<Map.Entry<K, V>> i = s.iterator(); 2751 final Class<V> valueType = this.valueType; 2752 2753 return new Iterator<Map.Entry<K,V>>() { 2754 public boolean hasNext() { return i.hasNext(); } 2755 public void remove() { i.remove(); } 2756 2757 public Map.Entry<K,V> next() { 2758 return checkedEntry(i.next(), valueType); 2759 } 2760 }; 2761 } 2762 2763 @SuppressWarnings("unchecked") 2764 public Object[] toArray() { 2765 Object[] source = s.toArray(); 2766 2767 /* 2768 * Ensure that we don't get an ArrayStoreException even if 2769 * s.toArray returns an array of something other than Object 2770 */ 2771 Object[] dest = (CheckedEntry.class.isInstance( 2772 source.getClass().getComponentType()) ? source : 2773 new Object[source.length]); 2774 2775 for (int i = 0; i < source.length; i++) 2776 dest[i] = checkedEntry((Map.Entry<K,V>)source[i], 2777 valueType); 2778 return dest; 2779 } 2780 2781 @SuppressWarnings("unchecked") 2782 public <T> T[] toArray(T[] a) { 2783 // We don't pass a to s.toArray, to avoid window of 2784 // vulnerability wherein an unscrupulous multithreaded client 2785 // could get his hands on raw (unwrapped) Entries from s. 2786 T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); 2787 2788 for (int i=0; i<arr.length; i++) 2789 arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i], 2790 valueType); 2791 if (arr.length > a.length) 2792 return arr; 2793 2794 System.arraycopy(arr, 0, a, 0, arr.length); 2795 if (a.length > arr.length) 2796 a[arr.length] = null; 2797 return a; 2798 } 2799 2800 /** 2801 * This method is overridden to protect the backing set against 2802 * an object with a nefarious equals function that senses 2803 * that the equality-candidate is Map.Entry and calls its 2804 * setValue method. 2805 */ 2806 public boolean contains(Object o) { 2807 if (!(o instanceof Map.Entry)) 2808 return false; 2809 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 2810 return s.contains( 2811 (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType)); 2812 } 2813 2814 /** 2815 * The bulk collection methods are overridden to protect 2816 * against an unscrupulous collection whose contains(Object o) 2817 * method senses when o is a Map.Entry, and calls o.setValue. 2818 */ 2819 public boolean containsAll(Collection<?> c) { 2820 for (Object o : c) 2821 if (!contains(o)) // Invokes safe contains() above 2822 return false; 2823 return true; 2824 } 2825 2826 public boolean remove(Object o) { 2827 if (!(o instanceof Map.Entry)) 2828 return false; 2829 return s.remove(new AbstractMap.SimpleImmutableEntry 2830 <>((Map.Entry<?,?>)o)); 2831 } 2832 2833 public boolean removeAll(Collection<?> c) { 2834 return batchRemove(c, false); 2835 } 2836 public boolean retainAll(Collection<?> c) { 2837 return batchRemove(c, true); 2838 } 2839 private boolean batchRemove(Collection<?> c, boolean complement) { 2840 boolean modified = false; 2841 Iterator<Map.Entry<K,V>> it = iterator(); 2842 while (it.hasNext()) { 2843 if (c.contains(it.next()) != complement) { 2844 it.remove(); 2845 modified = true; 2846 } 2847 } 2848 return modified; 2849 } 2850 2851 public boolean equals(Object o) { 2852 if (o == this) 2853 return true; 2854 if (!(o instanceof Set)) 2855 return false; 2856 Set<?> that = (Set<?>) o; 2857 return that.size() == s.size() 2858 && containsAll(that); // Invokes safe containsAll() above 2859 } 2860 2861 static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e, 2862 Class<T> valueType) { 2863 return new CheckedEntry<>(e, valueType); 2864 } 2865 2866 /** 2867 * This "wrapper class" serves two purposes: it prevents 2868 * the client from modifying the backing Map, by short-circuiting 2869 * the setValue method, and it protects the backing Map against 2870 * an ill-behaved Map.Entry that attempts to modify another 2871 * Map.Entry when asked to perform an equality check. 2872 */ 2873 private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> { 2874 private final Map.Entry<K, V> e; 2875 private final Class<T> valueType; 2876 2877 CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) { 2878 this.e = e; 2879 this.valueType = valueType; 2880 } 2881 2882 public K getKey() { return e.getKey(); } 2883 public V getValue() { return e.getValue(); } 2884 public int hashCode() { return e.hashCode(); } 2885 public String toString() { return e.toString(); } 2886 2887 public V setValue(V value) { 2888 if (value != null && !valueType.isInstance(value)) 2889 throw new ClassCastException(badValueMsg(value)); 2890 return e.setValue(value); 2891 } 2892 2893 private String badValueMsg(Object value) { 2894 return "Attempt to insert " + value.getClass() + 2895 " value into map with value type " + valueType; 2896 } 2897 2898 public boolean equals(Object o) { 2899 if (o == this) 2900 return true; 2901 if (!(o instanceof Map.Entry)) 2902 return false; 2903 return e.equals(new AbstractMap.SimpleImmutableEntry 2904 <>((Map.Entry<?,?>)o)); 2905 } 2906 } 2907 } 2908 } 2909 2910 /** 2911 * Returns a dynamically typesafe view of the specified sorted map. 2912 * Any attempt to insert a mapping whose key or value have the wrong 2913 * type will result in an immediate {@link ClassCastException}. 2914 * Similarly, any attempt to modify the value currently associated with 2915 * a key will result in an immediate {@link ClassCastException}, 2916 * whether the modification is attempted directly through the map 2917 * itself, or through a {@link Map.Entry} instance obtained from the 2918 * map's {@link Map#entrySet() entry set} view. 2919 * 2920 * <p>Assuming a map contains no incorrectly typed keys or values 2921 * prior to the time a dynamically typesafe view is generated, and 2922 * that all subsequent access to the map takes place through the view 2923 * (or one of its collection views), it is <i>guaranteed</i> that the 2924 * map cannot contain an incorrectly typed key or value. 2925 * 2926 * <p>A discussion of the use of dynamically typesafe views may be 2927 * found in the documentation for the {@link #checkedCollection 2928 * checkedCollection} method. 2929 * 2930 * <p>The returned map will be serializable if the specified map is 2931 * serializable. 2932 * 2933 * <p>Since {@code null} is considered to be a value of any reference 2934 * type, the returned map permits insertion of null keys or values 2935 * whenever the backing map does. 2936 * 2937 * @param m the map for which a dynamically typesafe view is to be 2938 * returned 2939 * @param keyType the type of key that {@code m} is permitted to hold 2940 * @param valueType the type of value that {@code m} is permitted to hold 2941 * @return a dynamically typesafe view of the specified map 2942 * @since 1.5 2943 */ 2944 public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, 2945 Class<K> keyType, 2946 Class<V> valueType) { 2947 return new CheckedSortedMap<>(m, keyType, valueType); 2948 } 2949 2950 /** 2951 * @serial include 2952 */ 2953 static class CheckedSortedMap<K,V> extends CheckedMap<K,V> 2954 implements SortedMap<K,V>, Serializable 2955 { 2956 private static final long serialVersionUID = 1599671320688067438L; 2957 2958 private final SortedMap<K, V> sm; 2959 2960 CheckedSortedMap(SortedMap<K, V> m, 2961 Class<K> keyType, Class<V> valueType) { 2962 super(m, keyType, valueType); 2963 sm = m; 2964 } 2965 2966 public Comparator<? super K> comparator() { return sm.comparator(); } 2967 public K firstKey() { return sm.firstKey(); } 2968 public K lastKey() { return sm.lastKey(); } 2969 2970 public SortedMap<K,V> subMap(K fromKey, K toKey) { 2971 return checkedSortedMap(sm.subMap(fromKey, toKey), 2972 keyType, valueType); 2973 } 2974 public SortedMap<K,V> headMap(K toKey) { 2975 return checkedSortedMap(sm.headMap(toKey), keyType, valueType); 2976 } 2977 public SortedMap<K,V> tailMap(K fromKey) { 2978 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType); 2979 } 2980 } 2981 2982 // Empty collections 2983 2984 /** 2985 * Returns an iterator that has no elements. More precisely, 2986 * 2987 * <ul compact> 2988 * 2989 * <li>{@link Iterator#hasNext hasNext} always returns {@code 2990 * false}. 2991 * 2992 * <li>{@link Iterator#next next} always throws {@link 2993 * NoSuchElementException}. 2994 * 2995 * <li>{@link Iterator#remove remove} always throws {@link 2996 * IllegalStateException}. 2997 * 2998 * </ul> 2999 * 3000 * <p>Implementations of this method are permitted, but not 3001 * required, to return the same object from multiple invocations. 3002 * 3003 * @return an empty iterator 3004 * @since 1.7 3005 */ 3006 @SuppressWarnings("unchecked") 3007 public static <T> Iterator<T> emptyIterator() { 3008 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR; 3009 } 3010 3011 private static class EmptyIterator<E> implements Iterator<E> { 3012 static final EmptyIterator<Object> EMPTY_ITERATOR 3013 = new EmptyIterator<>(); 3014 3015 public boolean hasNext() { return false; } 3016 public E next() { throw new NoSuchElementException(); } 3017 public void remove() { throw new IllegalStateException(); } 3018 } 3019 3020 /** 3021 * Returns a list iterator that has no elements. More precisely, 3022 * 3023 * <ul compact> 3024 * 3025 * <li>{@link Iterator#hasNext hasNext} and {@link 3026 * ListIterator#hasPrevious hasPrevious} always return {@code 3027 * false}. 3028 * 3029 * <li>{@link Iterator#next next} and {@link ListIterator#previous 3030 * previous} always throw {@link NoSuchElementException}. 3031 * 3032 * <li>{@link Iterator#remove remove} and {@link ListIterator#set 3033 * set} always throw {@link IllegalStateException}. 3034 * 3035 * <li>{@link ListIterator#add add} always throws {@link 3036 * UnsupportedOperationException}. 3037 * 3038 * <li>{@link ListIterator#nextIndex nextIndex} always returns 3039 * {@code 0} . 3040 * 3041 * <li>{@link ListIterator#previousIndex previousIndex} always 3042 * returns {@code -1}. 3043 * 3044 * </ul> 3045 * 3046 * <p>Implementations of this method are permitted, but not 3047 * required, to return the same object from multiple invocations. 3048 * 3049 * @return an empty list iterator 3050 * @since 1.7 3051 */ 3052 @SuppressWarnings("unchecked") 3053 public static <T> ListIterator<T> emptyListIterator() { 3054 return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR; 3055 } 3056 3057 private static class EmptyListIterator<E> 3058 extends EmptyIterator<E> 3059 implements ListIterator<E> 3060 { 3061 static final EmptyListIterator<Object> EMPTY_ITERATOR 3062 = new EmptyListIterator<>(); 3063 3064 public boolean hasPrevious() { return false; } 3065 public E previous() { throw new NoSuchElementException(); } 3066 public int nextIndex() { return 0; } 3067 public int previousIndex() { return -1; } 3068 public void set(E e) { throw new IllegalStateException(); } 3069 public void add(E e) { throw new UnsupportedOperationException(); } 3070 } 3071 3072 /** 3073 * Returns an enumeration that has no elements. More precisely, 3074 * 3075 * <ul compact> 3076 * 3077 * <li>{@link Enumeration#hasMoreElements hasMoreElements} always 3078 * returns {@code false}. 3079 * 3080 * <li> {@link Enumeration#nextElement nextElement} always throws 3081 * {@link NoSuchElementException}. 3082 * 3083 * </ul> 3084 * 3085 * <p>Implementations of this method are permitted, but not 3086 * required, to return the same object from multiple invocations. 3087 * 3088 * @return an empty enumeration 3089 * @since 1.7 3090 */ 3091 @SuppressWarnings("unchecked") 3092 public static <T> Enumeration<T> emptyEnumeration() { 3093 return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION; 3094 } 3095 3096 private static class EmptyEnumeration<E> implements Enumeration<E> { 3097 static final EmptyEnumeration<Object> EMPTY_ENUMERATION 3098 = new EmptyEnumeration<>(); 3099 3100 public boolean hasMoreElements() { return false; } 3101 public E nextElement() { throw new NoSuchElementException(); } 3102 } 3103 3104 /** 3105 * The empty set (immutable). This set is serializable. 3106 * 3107 * @see #emptySet() 3108 */ 3109 @SuppressWarnings("unchecked") 3110 public static final Set EMPTY_SET = new EmptySet<>(); 3111 3112 /** 3113 * Returns the empty set (immutable). This set is serializable. 3114 * Unlike the like-named field, this method is parameterized. 3115 * 3116 * <p>This example illustrates the type-safe way to obtain an empty set: 3117 * <pre> 3118 * Set<String> s = Collections.emptySet(); 3119 * </pre> 3120 * Implementation note: Implementations of this method need not 3121 * create a separate <tt>Set</tt> object for each call. Using this 3122 * method is likely to have comparable cost to using the like-named 3123 * field. (Unlike this method, the field does not provide type safety.) 3124 * 3125 * @see #EMPTY_SET 3126 * @since 1.5 3127 */ 3128 @SuppressWarnings("unchecked") 3129 public static final <T> Set<T> emptySet() { 3130 return (Set<T>) EMPTY_SET; 3131 } 3132 3133 /** 3134 * @serial include 3135 */ 3136 private static class EmptySet<E> 3137 extends AbstractSet<E> 3138 implements Serializable 3139 { 3140 private static final long serialVersionUID = 1582296315990362920L; 3141 3142 public Iterator<E> iterator() { return emptyIterator(); } 3143 3144 public int size() {return 0;} 3145 public boolean isEmpty() {return true;} 3146 3147 public boolean contains(Object obj) {return false;} 3148 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 3149 3150 public Object[] toArray() { return new Object[0]; } 3151 3152 public <T> T[] toArray(T[] a) { 3153 if (a.length > 0) 3154 a[0] = null; 3155 return a; 3156 } 3157 3158 // Preserves singleton property 3159 private Object readResolve() { 3160 return EMPTY_SET; 3161 } 3162 } 3163 3164 /** 3165 * The empty list (immutable). This list is serializable. 3166 * 3167 * @see #emptyList() 3168 */ 3169 @SuppressWarnings("unchecked") 3170 public static final List EMPTY_LIST = new EmptyList<>(); 3171 3172 /** 3173 * Returns the empty list (immutable). This list is serializable. 3174 * 3175 * <p>This example illustrates the type-safe way to obtain an empty list: 3176 * <pre> 3177 * List<String> s = Collections.emptyList(); 3178 * </pre> 3179 * Implementation note: Implementations of this method need not 3180 * create a separate <tt>List</tt> object for each call. Using this 3181 * method is likely to have comparable cost to using the like-named 3182 * field. (Unlike this method, the field does not provide type safety.) 3183 * 3184 * @see #EMPTY_LIST 3185 * @since 1.5 3186 */ 3187 @SuppressWarnings("unchecked") 3188 public static final <T> List<T> emptyList() { 3189 return (List<T>) EMPTY_LIST; 3190 } 3191 3192 /** 3193 * @serial include 3194 */ 3195 private static class EmptyList<E> 3196 extends AbstractList<E> 3197 implements RandomAccess, Serializable { 3198 private static final long serialVersionUID = 8842843931221139166L; 3199 3200 public Iterator<E> iterator() { 3201 return emptyIterator(); 3202 } 3203 public ListIterator<E> listIterator() { 3204 return emptyListIterator(); 3205 } 3206 3207 public int size() {return 0;} 3208 public boolean isEmpty() {return true;} 3209 3210 public boolean contains(Object obj) {return false;} 3211 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 3212 3213 public Object[] toArray() { return new Object[0]; } 3214 3215 public <T> T[] toArray(T[] a) { 3216 if (a.length > 0) 3217 a[0] = null; 3218 return a; 3219 } 3220 3221 public E get(int index) { 3222 throw new IndexOutOfBoundsException("Index: "+index); 3223 } 3224 3225 public boolean equals(Object o) { 3226 return (o instanceof List) && ((List<?>)o).isEmpty(); 3227 } 3228 3229 public int hashCode() { return 1; } 3230 3231 // Preserves singleton property 3232 private Object readResolve() { 3233 return EMPTY_LIST; 3234 } 3235 } 3236 3237 /** 3238 * The empty map (immutable). This map is serializable. 3239 * 3240 * @see #emptyMap() 3241 * @since 1.3 3242 */ 3243 @SuppressWarnings("unchecked") 3244 public static final Map EMPTY_MAP = new EmptyMap<>(); 3245 3246 /** 3247 * Returns the empty map (immutable). This map is serializable. 3248 * 3249 * <p>This example illustrates the type-safe way to obtain an empty set: 3250 * <pre> 3251 * Map<String, Date> s = Collections.emptyMap(); 3252 * </pre> 3253 * Implementation note: Implementations of this method need not 3254 * create a separate <tt>Map</tt> object for each call. Using this 3255 * method is likely to have comparable cost to using the like-named 3256 * field. (Unlike this method, the field does not provide type safety.) 3257 * 3258 * @see #EMPTY_MAP 3259 * @since 1.5 3260 */ 3261 @SuppressWarnings("unchecked") 3262 public static final <K,V> Map<K,V> emptyMap() { 3263 return (Map<K,V>) EMPTY_MAP; 3264 } 3265 3266 /** 3267 * @serial include 3268 */ 3269 private static class EmptyMap<K,V> 3270 extends AbstractMap<K,V> 3271 implements Serializable 3272 { 3273 private static final long serialVersionUID = 6428348081105594320L; 3274 3275 public int size() {return 0;} 3276 public boolean isEmpty() {return true;} 3277 public boolean containsKey(Object key) {return false;} 3278 public boolean containsValue(Object value) {return false;} 3279 public V get(Object key) {return null;} 3280 public Set<K> keySet() {return emptySet();} 3281 public Collection<V> values() {return emptySet();} 3282 public Set<Map.Entry<K,V>> entrySet() {return emptySet();} 3283 3284 public boolean equals(Object o) { 3285 return (o instanceof Map) && ((Map<?,?>)o).isEmpty(); 3286 } 3287 3288 public int hashCode() {return 0;} 3289 3290 // Preserves singleton property 3291 private Object readResolve() { 3292 return EMPTY_MAP; 3293 } 3294 } 3295 3296 // Singleton collections 3297 3298 /** 3299 * Returns an immutable set containing only the specified object. 3300 * The returned set is serializable. 3301 * 3302 * @param o the sole object to be stored in the returned set. 3303 * @return an immutable set containing only the specified object. 3304 */ 3305 public static <E> Set<E> singleton(E o) { 3306 return new SingletonSet<>(o); 3307 } 3308 3309 static <E> Iterator<E> singletonIterator(final E e) { 3310 return new Iterator<E>() { 3311 private boolean hasNext = true; 3312 public boolean hasNext() { 3313 return hasNext; 3314 } 3315 public E next() { 3316 if (hasNext) { 3317 hasNext = false; 3318 return e; 3319 } 3320 throw new NoSuchElementException(); 3321 } 3322 public void remove() { 3323 throw new UnsupportedOperationException(); 3324 } 3325 }; 3326 } 3327 3328 /** 3329 * @serial include 3330 */ 3331 private static class SingletonSet<E> 3332 extends AbstractSet<E> 3333 implements Serializable 3334 { 3335 private static final long serialVersionUID = 3193687207550431679L; 3336 3337 private final E element; 3338 3339 SingletonSet(E e) {element = e;} 3340 3341 public Iterator<E> iterator() { 3342 return singletonIterator(element); 3343 } 3344 3345 public int size() {return 1;} 3346 3347 public boolean contains(Object o) {return eq(o, element);} 3348 } 3349 3350 /** 3351 * Returns an immutable list containing only the specified object. 3352 * The returned list is serializable. 3353 * 3354 * @param o the sole object to be stored in the returned list. 3355 * @return an immutable list containing only the specified object. 3356 * @since 1.3 3357 */ 3358 public static <E> List<E> singletonList(E o) { 3359 return new SingletonList<>(o); 3360 } 3361 3362 /** 3363 * @serial include 3364 */ 3365 private static class SingletonList<E> 3366 extends AbstractList<E> 3367 implements RandomAccess, Serializable { 3368 3369 private static final long serialVersionUID = 3093736618740652951L; 3370 3371 private final E element; 3372 3373 SingletonList(E obj) {element = obj;} 3374 3375 public Iterator<E> iterator() { 3376 return singletonIterator(element); 3377 } 3378 3379 public int size() {return 1;} 3380 3381 public boolean contains(Object obj) {return eq(obj, element);} 3382 3383 public E get(int index) { 3384 if (index != 0) 3385 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); 3386 return element; 3387 } 3388 } 3389 3390 /** 3391 * Returns an immutable map, mapping only the specified key to the 3392 * specified value. The returned map is serializable. 3393 * 3394 * @param key the sole key to be stored in the returned map. 3395 * @param value the value to which the returned map maps <tt>key</tt>. 3396 * @return an immutable map containing only the specified key-value 3397 * mapping. 3398 * @since 1.3 3399 */ 3400 public static <K,V> Map<K,V> singletonMap(K key, V value) { 3401 return new SingletonMap<>(key, value); 3402 } 3403 3404 /** 3405 * @serial include 3406 */ 3407 private static class SingletonMap<K,V> 3408 extends AbstractMap<K,V> 3409 implements Serializable { 3410 private static final long serialVersionUID = -6979724477215052911L; 3411 3412 private final K k; 3413 private final V v; 3414 3415 SingletonMap(K key, V value) { 3416 k = key; 3417 v = value; 3418 } 3419 3420 public int size() {return 1;} 3421 3422 public boolean isEmpty() {return false;} 3423 3424 public boolean containsKey(Object key) {return eq(key, k);} 3425 3426 public boolean containsValue(Object value) {return eq(value, v);} 3427 3428 public V get(Object key) {return (eq(key, k) ? v : null);} 3429 3430 private transient Set<K> keySet = null; 3431 private transient Set<Map.Entry<K,V>> entrySet = null; 3432 private transient Collection<V> values = null; 3433 3434 public Set<K> keySet() { 3435 if (keySet==null) 3436 keySet = singleton(k); 3437 return keySet; 3438 } 3439 3440 public Set<Map.Entry<K,V>> entrySet() { 3441 if (entrySet==null) 3442 entrySet = Collections.<Map.Entry<K,V>>singleton( 3443 new SimpleImmutableEntry<>(k, v)); 3444 return entrySet; 3445 } 3446 3447 public Collection<V> values() { 3448 if (values==null) 3449 values = singleton(v); 3450 return values; 3451 } 3452 3453 } 3454 3455 // Miscellaneous 3456 3457 /** 3458 * Returns an immutable list consisting of <tt>n</tt> copies of the 3459 * specified object. The newly allocated data object is tiny (it contains 3460 * a single reference to the data object). This method is useful in 3461 * combination with the <tt>List.addAll</tt> method to grow lists. 3462 * The returned list is serializable. 3463 * 3464 * @param n the number of elements in the returned list. 3465 * @param o the element to appear repeatedly in the returned list. 3466 * @return an immutable list consisting of <tt>n</tt> copies of the 3467 * specified object. 3468 * @throws IllegalArgumentException if {@code n < 0} 3469 * @see List#addAll(Collection) 3470 * @see List#addAll(int, Collection) 3471 */ 3472 public static <T> List<T> nCopies(int n, T o) { 3473 if (n < 0) 3474 throw new IllegalArgumentException("List length = " + n); 3475 return new CopiesList<>(n, o); 3476 } 3477 3478 /** 3479 * @serial include 3480 */ 3481 private static class CopiesList<E> 3482 extends AbstractList<E> 3483 implements RandomAccess, Serializable 3484 { 3485 private static final long serialVersionUID = 2739099268398711800L; 3486 3487 final int n; 3488 final E element; 3489 3490 CopiesList(int n, E e) { 3491 assert n >= 0; 3492 this.n = n; 3493 element = e; 3494 } 3495 3496 public int size() { 3497 return n; 3498 } 3499 3500 public boolean contains(Object obj) { 3501 return n != 0 && eq(obj, element); 3502 } 3503 3504 public int indexOf(Object o) { 3505 return contains(o) ? 0 : -1; 3506 } 3507 3508 public int lastIndexOf(Object o) { 3509 return contains(o) ? n - 1 : -1; 3510 } 3511 3512 public E get(int index) { 3513 if (index < 0 || index >= n) 3514 throw new IndexOutOfBoundsException("Index: "+index+ 3515 ", Size: "+n); 3516 return element; 3517 } 3518 3519 public Object[] toArray() { 3520 final Object[] a = new Object[n]; 3521 if (element != null) 3522 Arrays.fill(a, 0, n, element); 3523 return a; 3524 } 3525 3526 public <T> T[] toArray(T[] a) { 3527 final int n = this.n; 3528 if (a.length < n) { 3529 a = (T[])java.lang.reflect.Array 3530 .newInstance(a.getClass().getComponentType(), n); 3531 if (element != null) 3532 Arrays.fill(a, 0, n, element); 3533 } else { 3534 Arrays.fill(a, 0, n, element); 3535 if (a.length > n) 3536 a[n] = null; 3537 } 3538 return a; 3539 } 3540 3541 public List<E> subList(int fromIndex, int toIndex) { 3542 if (fromIndex < 0) 3543 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 3544 if (toIndex > n) 3545 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 3546 if (fromIndex > toIndex) 3547 throw new IllegalArgumentException("fromIndex(" + fromIndex + 3548 ") > toIndex(" + toIndex + ")"); 3549 return new CopiesList<>(toIndex - fromIndex, element); 3550 } 3551 } 3552 3553 /** 3554 * Returns a comparator that imposes the reverse of the <em>natural 3555 * ordering</em> on a collection of objects that implement the 3556 * {@code Comparable} interface. (The natural ordering is the ordering 3557 * imposed by the objects' own {@code compareTo} method.) This enables a 3558 * simple idiom for sorting (or maintaining) collections (or arrays) of 3559 * objects that implement the {@code Comparable} interface in 3560 * reverse-natural-order. For example, suppose {@code a} is an array of 3561 * strings. Then: <pre> 3562 * Arrays.sort(a, Collections.reverseOrder()); 3563 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p> 3564 * 3565 * The returned comparator is serializable. 3566 * 3567 * @return A comparator that imposes the reverse of the <i>natural 3568 * ordering</i> on a collection of objects that implement 3569 * the <tt>Comparable</tt> interface. 3570 * @see Comparable 3571 */ 3572 public static <T> Comparator<T> reverseOrder() { 3573 return (Comparator<T>) ReverseComparator.REVERSE_ORDER; 3574 } 3575 3576 /** 3577 * @serial include 3578 */ 3579 private static class ReverseComparator 3580 implements Comparator<Comparable<Object>>, Serializable { 3581 3582 private static final long serialVersionUID = 7207038068494060240L; 3583 3584 static final ReverseComparator REVERSE_ORDER 3585 = new ReverseComparator(); 3586 3587 public int compare(Comparable<Object> c1, Comparable<Object> c2) { 3588 return c2.compareTo(c1); 3589 } 3590 3591 private Object readResolve() { return reverseOrder(); } 3592 } 3593 3594 /** 3595 * Returns a comparator that imposes the reverse ordering of the specified 3596 * comparator. If the specified comparator is {@code null}, this method is 3597 * equivalent to {@link #reverseOrder()} (in other words, it returns a 3598 * comparator that imposes the reverse of the <em>natural ordering</em> on 3599 * a collection of objects that implement the Comparable interface). 3600 * 3601 * <p>The returned comparator is serializable (assuming the specified 3602 * comparator is also serializable or {@code null}). 3603 * 3604 * @param cmp a comparator who's ordering is to be reversed by the returned 3605 * comparator or {@code null} 3606 * @return A comparator that imposes the reverse ordering of the 3607 * specified comparator. 3608 * @since 1.5 3609 */ 3610 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) { 3611 if (cmp == null) 3612 return reverseOrder(); 3613 3614 if (cmp instanceof ReverseComparator2) 3615 return ((ReverseComparator2<T>)cmp).cmp; 3616 3617 return new ReverseComparator2<>(cmp); 3618 } 3619 3620 /** 3621 * @serial include 3622 */ 3623 private static class ReverseComparator2<T> implements Comparator<T>, 3624 Serializable 3625 { 3626 private static final long serialVersionUID = 4374092139857L; 3627 3628 /** 3629 * The comparator specified in the static factory. This will never 3630 * be null, as the static factory returns a ReverseComparator 3631 * instance if its argument is null. 3632 * 3633 * @serial 3634 */ 3635 final Comparator<T> cmp; 3636 3637 ReverseComparator2(Comparator<T> cmp) { 3638 assert cmp != null; 3639 this.cmp = cmp; 3640 } 3641 3642 public int compare(T t1, T t2) { 3643 return cmp.compare(t2, t1); 3644 } 3645 3646 public boolean equals(Object o) { 3647 return (o == this) || 3648 (o instanceof ReverseComparator2 && 3649 cmp.equals(((ReverseComparator2)o).cmp)); 3650 } 3651 3652 public int hashCode() { 3653 return cmp.hashCode() ^ Integer.MIN_VALUE; 3654 } 3655 } 3656 3657 /** 3658 * Returns an enumeration over the specified collection. This provides 3659 * interoperability with legacy APIs that require an enumeration 3660 * as input. 3661 * 3662 * @param c the collection for which an enumeration is to be returned. 3663 * @return an enumeration over the specified collection. 3664 * @see Enumeration 3665 */ 3666 public static <T> Enumeration<T> enumeration(final Collection<T> c) { 3667 return new Enumeration<T>() { 3668 private final Iterator<T> i = c.iterator(); 3669 3670 public boolean hasMoreElements() { 3671 return i.hasNext(); 3672 } 3673 3674 public T nextElement() { 3675 return i.next(); 3676 } 3677 }; 3678 } 3679 3680 /** 3681 * Returns an array list containing the elements returned by the 3682 * specified enumeration in the order they are returned by the 3683 * enumeration. This method provides interoperability between 3684 * legacy APIs that return enumerations and new APIs that require 3685 * collections. 3686 * 3687 * @param e enumeration providing elements for the returned 3688 * array list 3689 * @return an array list containing the elements returned 3690 * by the specified enumeration. 3691 * @since 1.4 3692 * @see Enumeration 3693 * @see ArrayList 3694 */ 3695 public static <T> ArrayList<T> list(Enumeration<T> e) { 3696 ArrayList<T> l = new ArrayList<>(); 3697 while (e.hasMoreElements()) 3698 l.add(e.nextElement()); 3699 return l; 3700 } 3701 3702 /** 3703 * Returns true if the specified arguments are equal, or both null. 3704 */ 3705 static boolean eq(Object o1, Object o2) { 3706 return o1==null ? o2==null : o1.equals(o2); 3707 } 3708 3709 /** 3710 * Returns the number of elements in the specified collection equal to the 3711 * specified object. More formally, returns the number of elements 3712 * <tt>e</tt> in the collection such that 3713 * <tt>(o == null ? e == null : o.equals(e))</tt>. 3714 * 3715 * @param c the collection in which to determine the frequency 3716 * of <tt>o</tt> 3717 * @param o the object whose frequency is to be determined 3718 * @throws NullPointerException if <tt>c</tt> is null 3719 * @since 1.5 3720 */ 3721 public static int frequency(Collection<?> c, Object o) { 3722 int result = 0; 3723 if (o == null) { 3724 for (Object e : c) 3725 if (e == null) 3726 result++; 3727 } else { 3728 for (Object e : c) 3729 if (o.equals(e)) 3730 result++; 3731 } 3732 return result; 3733 } 3734 3735 /** 3736 * Returns {@code true} if the two specified collections have no 3737 * elements in common. 3738 * 3739 * <p>Care must be exercised if this method is used on collections that 3740 * do not comply with the general contract for {@code Collection}. 3741 * Implementations may elect to iterate over either collection and test 3742 * for containment in the other collection (or to perform any equivalent 3743 * computation). If either collection uses a nonstandard equality test 3744 * (as does a {@link SortedSet} whose ordering is not <em>compatible with 3745 * equals</em>, or the key set of an {@link IdentityHashMap}), both 3746 * collections must use the same nonstandard equality test, or the 3747 * result of this method is undefined. 3748 * 3749 * <p>Care must also be exercised when using collections that have 3750 * restrictions on the elements that they may contain. Collection 3751 * implementations are allowed to throw exceptions for any operation 3752 * involving elements they deem ineligible. For absolute safety the 3753 * specified collections should contain only elements which are 3754 * eligible elements for both collections. 3755 * 3756 * <p>Note that it is permissible to pass the same collection in both 3757 * parameters, in which case the method will return {@code true} if and 3758 * only if the collection is empty. 3759 * 3760 * @param c1 a collection 3761 * @param c2 a collection 3762 * @return {@code true} if the two specified collections have no 3763 * elements in common. 3764 * @throws NullPointerException if either collection is {@code null}. 3765 * @throws NullPointerException if one collection contains a {@code null} 3766 * element and {@code null} is not an eligible element for the other collection. 3767 * (<a href="Collection.html#optional-restrictions">optional</a>) 3768 * @throws ClassCastException if one collection contains an element that is 3769 * of a type which is ineligible for the other collection. 3770 * (<a href="Collection.html#optional-restrictions">optional</a>) 3771 * @since 1.5 3772 */ 3773 public static boolean disjoint(Collection<?> c1, Collection<?> c2) { 3774 // The collection to be used for contains(). Preference is given to 3775 // the collection who's contains() has lower O() complexity. 3776 Collection<?> contains = c2; 3777 // The collection to be iterated. If the collections' contains() impl 3778 // are of different O() complexity, the collection with slower 3779 // contains() will be used for iteration. For collections who's 3780 // contains() are of the same complexity then best performance is 3781 // achieved by iterating the smaller collection. 3782 Collection<?> iterate = c1; 3783 3784 // Performance optimization cases. The heuristics: 3785 // 1. Generally iterate over c1. 3786 // 2. If c1 is a Set then iterate over c2. 3787 // 3. If either collection is empty then result is always true. 3788 // 4. Iterate over the smaller Collection. 3789 if (c1 instanceof Set) { 3790 // Use c1 for contains as a Set's contains() is expected to perform 3791 // better than O(N/2) 3792 iterate = c2; 3793 contains = c1; 3794 } else if (!(c2 instanceof Set)) { 3795 // Both are mere Collections. Iterate over smaller collection. 3796 // Example: If c1 contains 3 elements and c2 contains 50 elements and 3797 // assuming contains() requires ceiling(N/2) comparisons then 3798 // checking for all c1 elements in c2 would require 75 comparisons 3799 // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring 3800 // 100 comparisons (50 * ceiling(3/2)). 3801 int c1size = c1.size(); 3802 int c2size = c2.size(); 3803 if (c1size == 0 || c2size == 0) { 3804 // At least one collection is empty. Nothing will match. 3805 return true; 3806 } 3807 3808 if (c1size > c2size) { 3809 iterate = c2; 3810 contains = c1; 3811 } 3812 } 3813 3814 for (Object e : iterate) { 3815 if (contains.contains(e)) { 3816 // Found a common element. Collections are not disjoint. 3817 return false; 3818 } 3819 } 3820 3821 // No common elements were found. 3822 return true; 3823 } 3824 3825 /** 3826 * Adds all of the specified elements to the specified collection. 3827 * Elements to be added may be specified individually or as an array. 3828 * The behavior of this convenience method is identical to that of 3829 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely 3830 * to run significantly faster under most implementations. 3831 * 3832 * <p>When elements are specified individually, this method provides a 3833 * convenient way to add a few elements to an existing collection: 3834 * <pre> 3835 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon"); 3836 * </pre> 3837 * 3838 * @param c the collection into which <tt>elements</tt> are to be inserted 3839 * @param elements the elements to insert into <tt>c</tt> 3840 * @return <tt>true</tt> if the collection changed as a result of the call 3841 * @throws UnsupportedOperationException if <tt>c</tt> does not support 3842 * the <tt>add</tt> operation 3843 * @throws NullPointerException if <tt>elements</tt> contains one or more 3844 * null values and <tt>c</tt> does not permit null elements, or 3845 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt> 3846 * @throws IllegalArgumentException if some property of a value in 3847 * <tt>elements</tt> prevents it from being added to <tt>c</tt> 3848 * @see Collection#addAll(Collection) 3849 * @since 1.5 3850 */ 3851 @SafeVarargs 3852 public static <T> boolean addAll(Collection<? super T> c, T... elements) { 3853 boolean result = false; 3854 for (T element : elements) 3855 result |= c.add(element); 3856 return result; 3857 } 3858 3859 /** 3860 * Returns a set backed by the specified map. The resulting set displays 3861 * the same ordering, concurrency, and performance characteristics as the 3862 * backing map. In essence, this factory method provides a {@link Set} 3863 * implementation corresponding to any {@link Map} implementation. There 3864 * is no need to use this method on a {@link Map} implementation that 3865 * already has a corresponding {@link Set} implementation (such as {@link 3866 * HashMap} or {@link TreeMap}). 3867 * 3868 * <p>Each method invocation on the set returned by this method results in 3869 * exactly one method invocation on the backing map or its <tt>keySet</tt> 3870 * view, with one exception. The <tt>addAll</tt> method is implemented 3871 * as a sequence of <tt>put</tt> invocations on the backing map. 3872 * 3873 * <p>The specified map must be empty at the time this method is invoked, 3874 * and should not be accessed directly after this method returns. These 3875 * conditions are ensured if the map is created empty, passed directly 3876 * to this method, and no reference to the map is retained, as illustrated 3877 * in the following code fragment: 3878 * <pre> 3879 * Set<Object> weakHashSet = Collections.newSetFromMap( 3880 * new WeakHashMap<Object, Boolean>()); 3881 * </pre> 3882 * 3883 * @param map the backing map 3884 * @return the set backed by the map 3885 * @throws IllegalArgumentException if <tt>map</tt> is not empty 3886 * @since 1.6 3887 */ 3888 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 3889 return new SetFromMap<>(map); 3890 } 3891 3892 /** 3893 * @serial include 3894 */ 3895 private static class SetFromMap<E> extends AbstractSet<E> 3896 implements Set<E>, Serializable 3897 { 3898 private final Map<E, Boolean> m; // The backing map 3899 private transient Set<E> s; // Its keySet 3900 3901 SetFromMap(Map<E, Boolean> map) { 3902 if (!map.isEmpty()) 3903 throw new IllegalArgumentException("Map is non-empty"); 3904 m = map; 3905 s = map.keySet(); 3906 } 3907 3908 public void clear() { m.clear(); } 3909 public int size() { return m.size(); } 3910 public boolean isEmpty() { return m.isEmpty(); } 3911 public boolean contains(Object o) { return m.containsKey(o); } 3912 public boolean remove(Object o) { return m.remove(o) != null; } 3913 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } 3914 public Iterator<E> iterator() { return s.iterator(); } 3915 public Object[] toArray() { return s.toArray(); } 3916 public <T> T[] toArray(T[] a) { return s.toArray(a); } 3917 public String toString() { return s.toString(); } 3918 public int hashCode() { return s.hashCode(); } 3919 public boolean equals(Object o) { return o == this || s.equals(o); } 3920 public boolean containsAll(Collection<?> c) {return s.containsAll(c);} 3921 public boolean removeAll(Collection<?> c) {return s.removeAll(c);} 3922 public boolean retainAll(Collection<?> c) {return s.retainAll(c);} 3923 // addAll is the only inherited implementation 3924 3925 private static final long serialVersionUID = 2454657854757543876L; 3926 3927 private void readObject(java.io.ObjectInputStream stream) 3928 throws IOException, ClassNotFoundException 3929 { 3930 stream.defaultReadObject(); 3931 s = m.keySet(); 3932 } 3933 } 3934 3935 /** 3936 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo) 3937 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>, 3938 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This 3939 * view can be useful when you would like to use a method 3940 * requiring a <tt>Queue</tt> but you need Lifo ordering. 3941 * 3942 * <p>Each method invocation on the queue returned by this method 3943 * results in exactly one method invocation on the backing deque, with 3944 * one exception. The {@link Queue#addAll addAll} method is 3945 * implemented as a sequence of {@link Deque#addFirst addFirst} 3946 * invocations on the backing deque. 3947 * 3948 * @param deque the deque 3949 * @return the queue 3950 * @since 1.6 3951 */ 3952 public static <T> Queue<T> asLifoQueue(Deque<T> deque) { 3953 return new AsLIFOQueue<>(deque); 3954 } 3955 3956 /** 3957 * @serial include 3958 */ 3959 static class AsLIFOQueue<E> extends AbstractQueue<E> 3960 implements Queue<E>, Serializable { 3961 private static final long serialVersionUID = 1802017725587941708L; 3962 private final Deque<E> q; 3963 AsLIFOQueue(Deque<E> q) { this.q = q; } 3964 public boolean add(E e) { q.addFirst(e); return true; } 3965 public boolean offer(E e) { return q.offerFirst(e); } 3966 public E poll() { return q.pollFirst(); } 3967 public E remove() { return q.removeFirst(); } 3968 public E peek() { return q.peekFirst(); } 3969 public E element() { return q.getFirst(); } 3970 public void clear() { q.clear(); } 3971 public int size() { return q.size(); } 3972 public boolean isEmpty() { return q.isEmpty(); } 3973 public boolean contains(Object o) { return q.contains(o); } 3974 public boolean remove(Object o) { return q.remove(o); } 3975 public Iterator<E> iterator() { return q.iterator(); } 3976 public Object[] toArray() { return q.toArray(); } 3977 public <T> T[] toArray(T[] a) { return q.toArray(a); } 3978 public String toString() { return q.toString(); } 3979 public boolean containsAll(Collection<?> c) {return q.containsAll(c);} 3980 public boolean removeAll(Collection<?> c) {return q.removeAll(c);} 3981 public boolean retainAll(Collection<?> c) {return q.retainAll(c);} 3982 // We use inherited addAll; forwarding addAll would be wrong 3983 } 3984} 3985