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