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 { 272 int low = 0; 273 int high = list.size()-1; 274 275 while (low <= high) { 276 int mid = (low + high) >>> 1; 277 Comparable<? super T> midVal = list.get(mid); 278 int cmp = midVal.compareTo(key); 279 280 if (cmp < 0) 281 low = mid + 1; 282 else if (cmp > 0) 283 high = mid - 1; 284 else 285 return mid; // key found 286 } 287 return -(low + 1); // key not found 288 } 289 290 private static <T> 291 int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) 292 { 293 int low = 0; 294 int high = list.size()-1; 295 ListIterator<? extends Comparable<? super T>> i = list.listIterator(); 296 297 while (low <= high) { 298 int mid = (low + high) >>> 1; 299 Comparable<? super T> midVal = get(i, mid); 300 int cmp = midVal.compareTo(key); 301 302 if (cmp < 0) 303 low = mid + 1; 304 else if (cmp > 0) 305 high = mid - 1; 306 else 307 return mid; // key found 308 } 309 return -(low + 1); // key not found 310 } 311 312 /** 313 * Gets the ith element from the given list by repositioning the specified 314 * list listIterator. 315 */ 316 private static <T> T get(ListIterator<? extends T> i, int index) { 317 T obj = null; 318 int pos = i.nextIndex(); 319 if (pos <= index) { 320 do { 321 obj = i.next(); 322 } while (pos++ < index); 323 } else { 324 do { 325 obj = i.previous(); 326 } while (--pos > index); 327 } 328 return obj; 329 } 330 331 /** 332 * Searches the specified list for the specified object using the binary 333 * search algorithm. The list must be sorted into ascending order 334 * according to the specified comparator (as by the 335 * {@link #sort(List, Comparator) sort(List, Comparator)} 336 * method), prior to making this call. If it is 337 * not sorted, the results are undefined. If the list contains multiple 338 * elements equal to the specified object, there is no guarantee which one 339 * will be found. 340 * 341 * <p>This method runs in log(n) time for a "random access" list (which 342 * provides near-constant-time positional access). If the specified list 343 * does not implement the {@link RandomAccess} interface and is large, 344 * this method will do an iterator-based binary search that performs 345 * O(n) link traversals and O(log n) element comparisons. 346 * 347 * @param list the list to be searched. 348 * @param key the key to be searched for. 349 * @param c the comparator by which the list is ordered. 350 * A <tt>null</tt> value indicates that the elements' 351 * {@linkplain Comparable natural ordering} should be used. 352 * @return the index of the search key, if it is contained in the list; 353 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 354 * <i>insertion point</i> is defined as the point at which the 355 * key would be inserted into the list: the index of the first 356 * element greater than the key, or <tt>list.size()</tt> if all 357 * elements in the list are less than the specified key. Note 358 * that this guarantees that the return value will be >= 0 if 359 * and only if the key is found. 360 * @throws ClassCastException if the list contains elements that are not 361 * <i>mutually comparable</i> using the specified comparator, 362 * or the search key is not mutually comparable with the 363 * elements of the list using this comparator. 364 */ 365 @SuppressWarnings("unchecked") 366 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { 367 if (c==null) 368 return binarySearch((List<? extends Comparable<? super T>>) list, key); 369 370 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 371 return Collections.indexedBinarySearch(list, key, c); 372 else 373 return Collections.iteratorBinarySearch(list, key, c); 374 } 375 376 private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) { 377 int low = 0; 378 int high = l.size()-1; 379 380 while (low <= high) { 381 int mid = (low + high) >>> 1; 382 T midVal = l.get(mid); 383 int cmp = c.compare(midVal, key); 384 385 if (cmp < 0) 386 low = mid + 1; 387 else if (cmp > 0) 388 high = mid - 1; 389 else 390 return mid; // key found 391 } 392 return -(low + 1); // key not found 393 } 394 395 private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) { 396 int low = 0; 397 int high = l.size()-1; 398 ListIterator<? extends T> i = l.listIterator(); 399 400 while (low <= high) { 401 int mid = (low + high) >>> 1; 402 T midVal = get(i, mid); 403 int cmp = c.compare(midVal, key); 404 405 if (cmp < 0) 406 low = mid + 1; 407 else if (cmp > 0) 408 high = mid - 1; 409 else 410 return mid; // key found 411 } 412 return -(low + 1); // key not found 413 } 414 415 /** 416 * Reverses the order of the elements in the specified list.<p> 417 * 418 * This method runs in linear time. 419 * 420 * @param list the list whose elements are to be reversed. 421 * @throws UnsupportedOperationException if the specified list or 422 * its list-iterator does not support the <tt>set</tt> operation. 423 */ 424 @SuppressWarnings({"rawtypes", "unchecked"}) 425 public static void reverse(List<?> list) { 426 int size = list.size(); 427 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { 428 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) 429 swap(list, i, j); 430 } else { 431 // instead of using a raw type here, it's possible to capture 432 // the wildcard but it will require a call to a supplementary 433 // private method 434 ListIterator fwd = list.listIterator(); 435 ListIterator rev = list.listIterator(size); 436 for (int i=0, mid=list.size()>>1; i<mid; i++) { 437 Object tmp = fwd.next(); 438 fwd.set(rev.previous()); 439 rev.set(tmp); 440 } 441 } 442 } 443 444 /** 445 * Randomly permutes the specified list using a default source of 446 * randomness. All permutations occur with approximately equal 447 * likelihood.<p> 448 * 449 * The hedge "approximately" is used in the foregoing description because 450 * default source of randomness is only approximately an unbiased source 451 * of independently chosen bits. If it were a perfect source of randomly 452 * chosen bits, then the algorithm would choose permutations with perfect 453 * uniformity.<p> 454 * 455 * This implementation traverses the list backwards, from the last element 456 * up to the second, repeatedly swapping a randomly selected element into 457 * the "current position". Elements are randomly selected from the 458 * portion of the list that runs from the first element to the current 459 * position, inclusive.<p> 460 * 461 * This method runs in linear time. If the specified list does not 462 * implement the {@link RandomAccess} interface and is large, this 463 * implementation dumps the specified list into an array before shuffling 464 * it, and dumps the shuffled array back into the list. This avoids the 465 * quadratic behavior that would result from shuffling a "sequential 466 * access" list in place. 467 * 468 * @param list the list to be shuffled. 469 * @throws UnsupportedOperationException if the specified list or 470 * its list-iterator does not support the <tt>set</tt> operation. 471 */ 472 public static void shuffle(List<?> list) { 473 Random rnd = r; 474 if (rnd == null) 475 r = rnd = new Random(); 476 shuffle(list, rnd); 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 public V putIfAbsent(K key, V value) { 1400 throw new UnsupportedOperationException(); 1401 } 1402 1403 @Override 1404 public boolean remove(Object key, Object value) { 1405 throw new UnsupportedOperationException(); 1406 } 1407 1408 @Override 1409 public boolean replace(K key, V oldValue, V newValue) { 1410 throw new UnsupportedOperationException(); 1411 } 1412 1413 @Override 1414 public V replace(K key, V value) { 1415 throw new UnsupportedOperationException(); 1416 } 1417 1418 @Override 1419 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 1420 throw new UnsupportedOperationException(); 1421 } 1422 1423 @Override 1424 public V computeIfPresent(K key, 1425 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1426 throw new UnsupportedOperationException(); 1427 } 1428 1429 @Override 1430 public V compute(K key, 1431 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1432 throw new UnsupportedOperationException(); 1433 } 1434 1435 @Override 1436 public V merge(K key, V value, 1437 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1438 throw new UnsupportedOperationException(); 1439 } 1440 1441 /** 1442 * We need this class in addition to UnmodifiableSet as 1443 * Map.Entries themselves permit modification of the backing Map 1444 * via their setValue operation. This class is subtle: there are 1445 * many possible attacks that must be thwarted. 1446 * 1447 * @serial include 1448 */ 1449 static class UnmodifiableEntrySet<K,V> 1450 extends UnmodifiableSet<Map.Entry<K,V>> { 1451 private static final long serialVersionUID = 7854390611657943733L; 1452 1453 @SuppressWarnings({"unchecked", "rawtypes"}) 1454 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) { 1455 // Need to cast to raw in order to work around a limitation in the type system 1456 super((Set)s); 1457 } 1458 public Iterator<Map.Entry<K,V>> iterator() { 1459 return new Iterator<Map.Entry<K,V>>() { 1460 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator(); 1461 1462 public boolean hasNext() { 1463 return i.hasNext(); 1464 } 1465 public Map.Entry<K,V> next() { 1466 return new UnmodifiableEntry<>(i.next()); 1467 } 1468 public void remove() { 1469 throw new UnsupportedOperationException(); 1470 } 1471 }; 1472 } 1473 1474 @SuppressWarnings("unchecked") 1475 public Object[] toArray() { 1476 Object[] a = c.toArray(); 1477 for (int i=0; i<a.length; i++) 1478 a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]); 1479 return a; 1480 } 1481 1482 @SuppressWarnings("unchecked") 1483 public <T> T[] toArray(T[] a) { 1484 // We don't pass a to c.toArray, to avoid window of 1485 // vulnerability wherein an unscrupulous multithreaded client 1486 // could get his hands on raw (unwrapped) Entries from c. 1487 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); 1488 1489 for (int i=0; i<arr.length; i++) 1490 arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]); 1491 1492 if (arr.length > a.length) 1493 return (T[])arr; 1494 1495 System.arraycopy(arr, 0, a, 0, arr.length); 1496 if (a.length > arr.length) 1497 a[arr.length] = null; 1498 return a; 1499 } 1500 1501 /** 1502 * This method is overridden to protect the backing set against 1503 * an object with a nefarious equals function that senses 1504 * that the equality-candidate is Map.Entry and calls its 1505 * setValue method. 1506 */ 1507 public boolean contains(Object o) { 1508 if (!(o instanceof Map.Entry)) 1509 return false; 1510 return c.contains( 1511 new UnmodifiableEntry<>((Map.Entry<?,?>) o)); 1512 } 1513 1514 /** 1515 * The next two methods are overridden to protect against 1516 * an unscrupulous List whose contains(Object o) method senses 1517 * when o is a Map.Entry, and calls o.setValue. 1518 */ 1519 public boolean containsAll(Collection<?> coll) { 1520 for (Object e : coll) { 1521 if (!contains(e)) // Invokes safe contains() above 1522 return false; 1523 } 1524 return true; 1525 } 1526 public boolean equals(Object o) { 1527 if (o == this) 1528 return true; 1529 1530 if (!(o instanceof Set)) 1531 return false; 1532 Set<?> s = (Set<?>) o; 1533 if (s.size() != c.size()) 1534 return false; 1535 return containsAll(s); // Invokes safe containsAll() above 1536 } 1537 1538 /** 1539 * This "wrapper class" serves two purposes: it prevents 1540 * the client from modifying the backing Map, by short-circuiting 1541 * the setValue method, and it protects the backing Map against 1542 * an ill-behaved Map.Entry that attempts to modify another 1543 * Map Entry when asked to perform an equality check. 1544 */ 1545 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> { 1546 private Map.Entry<? extends K, ? extends V> e; 1547 1548 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;} 1549 1550 public K getKey() {return e.getKey();} 1551 public V getValue() {return e.getValue();} 1552 public V setValue(V value) { 1553 throw new UnsupportedOperationException(); 1554 } 1555 public int hashCode() {return e.hashCode();} 1556 public boolean equals(Object o) { 1557 if (this == o) 1558 return true; 1559 if (!(o instanceof Map.Entry)) 1560 return false; 1561 Map.Entry<?,?> t = (Map.Entry<?,?>)o; 1562 return eq(e.getKey(), t.getKey()) && 1563 eq(e.getValue(), t.getValue()); 1564 } 1565 public String toString() {return e.toString();} 1566 } 1567 } 1568 } 1569 1570 /** 1571 * Returns an unmodifiable view of the specified sorted map. This method 1572 * allows modules to provide users with "read-only" access to internal 1573 * sorted maps. Query operations on the returned sorted map "read through" 1574 * to the specified sorted map. Attempts to modify the returned 1575 * sorted map, whether direct, via its collection views, or via its 1576 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in 1577 * an <tt>UnsupportedOperationException</tt>.<p> 1578 * 1579 * The returned sorted map will be serializable if the specified sorted map 1580 * is serializable. 1581 * 1582 * @param m the sorted map for which an unmodifiable view is to be 1583 * returned. 1584 * @return an unmodifiable view of the specified sorted map. 1585 */ 1586 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) { 1587 return new UnmodifiableSortedMap<>(m); 1588 } 1589 1590 /** 1591 * @serial include 1592 */ 1593 static class UnmodifiableSortedMap<K,V> 1594 extends UnmodifiableMap<K,V> 1595 implements SortedMap<K,V>, Serializable { 1596 private static final long serialVersionUID = -8806743815996713206L; 1597 1598 private final SortedMap<K, ? extends V> sm; 1599 1600 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;} 1601 1602 public Comparator<? super K> comparator() {return sm.comparator();} 1603 1604 public SortedMap<K,V> subMap(K fromKey, K toKey) { 1605 return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey)); 1606 } 1607 public SortedMap<K,V> headMap(K toKey) { 1608 return new UnmodifiableSortedMap<>(sm.headMap(toKey)); 1609 } 1610 public SortedMap<K,V> tailMap(K fromKey) { 1611 return new UnmodifiableSortedMap<>(sm.tailMap(fromKey)); 1612 } 1613 1614 public K firstKey() {return sm.firstKey();} 1615 public K lastKey() {return sm.lastKey();} 1616 } 1617 1618 1619 // Synch Wrappers 1620 1621 /** 1622 * Returns a synchronized (thread-safe) collection backed by the specified 1623 * collection. In order to guarantee serial access, it is critical that 1624 * <strong>all</strong> access to the backing collection is accomplished 1625 * through the returned collection.<p> 1626 * 1627 * It is imperative that the user manually synchronize on the returned 1628 * collection when iterating over it: 1629 * <pre> 1630 * Collection c = Collections.synchronizedCollection(myCollection); 1631 * ... 1632 * synchronized (c) { 1633 * Iterator i = c.iterator(); // Must be in the synchronized block 1634 * while (i.hasNext()) 1635 * foo(i.next()); 1636 * } 1637 * </pre> 1638 * Failure to follow this advice may result in non-deterministic behavior. 1639 * 1640 * <p>The returned collection does <i>not</i> pass the {@code hashCode} 1641 * and {@code equals} operations through to the backing collection, but 1642 * relies on {@code Object}'s equals and hashCode methods. This is 1643 * necessary to preserve the contracts of these operations in the case 1644 * that the backing collection is a set or a list.<p> 1645 * 1646 * The returned collection will be serializable if the specified collection 1647 * is serializable. 1648 * 1649 * @param c the collection to be "wrapped" in a synchronized collection. 1650 * @return a synchronized view of the specified collection. 1651 */ 1652 public static <T> Collection<T> synchronizedCollection(Collection<T> c) { 1653 return new SynchronizedCollection<>(c); 1654 } 1655 1656 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) { 1657 return new SynchronizedCollection<>(c, mutex); 1658 } 1659 1660 /** 1661 * @serial include 1662 */ 1663 static class SynchronizedCollection<E> implements Collection<E>, Serializable { 1664 private static final long serialVersionUID = 3053995032091335093L; 1665 1666 final Collection<E> c; // Backing Collection 1667 final Object mutex; // Object on which to synchronize 1668 1669 SynchronizedCollection(Collection<E> c) { 1670 if (c==null) 1671 throw new NullPointerException(); 1672 this.c = c; 1673 mutex = this; 1674 } 1675 SynchronizedCollection(Collection<E> c, Object mutex) { 1676 this.c = c; 1677 this.mutex = mutex; 1678 } 1679 1680 public int size() { 1681 synchronized (mutex) {return c.size();} 1682 } 1683 public boolean isEmpty() { 1684 synchronized (mutex) {return c.isEmpty();} 1685 } 1686 public boolean contains(Object o) { 1687 synchronized (mutex) {return c.contains(o);} 1688 } 1689 public Object[] toArray() { 1690 synchronized (mutex) {return c.toArray();} 1691 } 1692 public <T> T[] toArray(T[] a) { 1693 synchronized (mutex) {return c.toArray(a);} 1694 } 1695 1696 public Iterator<E> iterator() { 1697 return c.iterator(); // Must be manually synched by user! 1698 } 1699 1700 public boolean add(E e) { 1701 synchronized (mutex) {return c.add(e);} 1702 } 1703 public boolean remove(Object o) { 1704 synchronized (mutex) {return c.remove(o);} 1705 } 1706 1707 public boolean containsAll(Collection<?> coll) { 1708 synchronized (mutex) {return c.containsAll(coll);} 1709 } 1710 public boolean addAll(Collection<? extends E> coll) { 1711 synchronized (mutex) {return c.addAll(coll);} 1712 } 1713 public boolean removeAll(Collection<?> coll) { 1714 synchronized (mutex) {return c.removeAll(coll);} 1715 } 1716 public boolean retainAll(Collection<?> coll) { 1717 synchronized (mutex) {return c.retainAll(coll);} 1718 } 1719 public void clear() { 1720 synchronized (mutex) {c.clear();} 1721 } 1722 public String toString() { 1723 synchronized (mutex) {return c.toString();} 1724 } 1725 private void writeObject(ObjectOutputStream s) throws IOException { 1726 synchronized (mutex) {s.defaultWriteObject();} 1727 } 1728 } 1729 1730 /** 1731 * Returns a synchronized (thread-safe) set backed by the specified 1732 * set. In order to guarantee serial access, it is critical that 1733 * <strong>all</strong> access to the backing set is accomplished 1734 * through the returned set.<p> 1735 * 1736 * It is imperative that the user manually synchronize on the returned 1737 * set when iterating over it: 1738 * <pre> 1739 * Set s = Collections.synchronizedSet(new HashSet()); 1740 * ... 1741 * synchronized (s) { 1742 * Iterator i = s.iterator(); // Must be in the synchronized block 1743 * while (i.hasNext()) 1744 * foo(i.next()); 1745 * } 1746 * </pre> 1747 * Failure to follow this advice may result in non-deterministic behavior. 1748 * 1749 * <p>The returned set will be serializable if the specified set is 1750 * serializable. 1751 * 1752 * @param s the set to be "wrapped" in a synchronized set. 1753 * @return a synchronized view of the specified set. 1754 */ 1755 public static <T> Set<T> synchronizedSet(Set<T> s) { 1756 return new SynchronizedSet<>(s); 1757 } 1758 1759 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) { 1760 return new SynchronizedSet<>(s, mutex); 1761 } 1762 1763 /** 1764 * @serial include 1765 */ 1766 static class SynchronizedSet<E> 1767 extends SynchronizedCollection<E> 1768 implements Set<E> { 1769 private static final long serialVersionUID = 487447009682186044L; 1770 1771 SynchronizedSet(Set<E> s) { 1772 super(s); 1773 } 1774 SynchronizedSet(Set<E> s, Object mutex) { 1775 super(s, mutex); 1776 } 1777 1778 public boolean equals(Object o) { 1779 if (this == o) 1780 return true; 1781 synchronized (mutex) {return c.equals(o);} 1782 } 1783 public int hashCode() { 1784 synchronized (mutex) {return c.hashCode();} 1785 } 1786 } 1787 1788 /** 1789 * Returns a synchronized (thread-safe) sorted set backed by the specified 1790 * sorted set. In order to guarantee serial access, it is critical that 1791 * <strong>all</strong> access to the backing sorted set is accomplished 1792 * through the returned sorted set (or its views).<p> 1793 * 1794 * It is imperative that the user manually synchronize on the returned 1795 * sorted set when iterating over it or any of its <tt>subSet</tt>, 1796 * <tt>headSet</tt>, or <tt>tailSet</tt> views. 1797 * <pre> 1798 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet()); 1799 * ... 1800 * synchronized (s) { 1801 * Iterator i = s.iterator(); // Must be in the synchronized block 1802 * while (i.hasNext()) 1803 * foo(i.next()); 1804 * } 1805 * </pre> 1806 * or: 1807 * <pre> 1808 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet()); 1809 * SortedSet s2 = s.headSet(foo); 1810 * ... 1811 * synchronized (s) { // Note: s, not s2!!! 1812 * Iterator i = s2.iterator(); // Must be in the synchronized block 1813 * while (i.hasNext()) 1814 * foo(i.next()); 1815 * } 1816 * </pre> 1817 * Failure to follow this advice may result in non-deterministic behavior. 1818 * 1819 * <p>The returned sorted set will be serializable if the specified 1820 * sorted set is serializable. 1821 * 1822 * @param s the sorted set to be "wrapped" in a synchronized sorted set. 1823 * @return a synchronized view of the specified sorted set. 1824 */ 1825 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) { 1826 return new SynchronizedSortedSet<>(s); 1827 } 1828 1829 /** 1830 * @serial include 1831 */ 1832 static class SynchronizedSortedSet<E> 1833 extends SynchronizedSet<E> 1834 implements SortedSet<E> 1835 { 1836 private static final long serialVersionUID = 8695801310862127406L; 1837 1838 private final SortedSet<E> ss; 1839 1840 SynchronizedSortedSet(SortedSet<E> s) { 1841 super(s); 1842 ss = s; 1843 } 1844 SynchronizedSortedSet(SortedSet<E> s, Object mutex) { 1845 super(s, mutex); 1846 ss = s; 1847 } 1848 1849 public Comparator<? super E> comparator() { 1850 synchronized (mutex) {return ss.comparator();} 1851 } 1852 1853 public SortedSet<E> subSet(E fromElement, E toElement) { 1854 synchronized (mutex) { 1855 return new SynchronizedSortedSet<>( 1856 ss.subSet(fromElement, toElement), mutex); 1857 } 1858 } 1859 public SortedSet<E> headSet(E toElement) { 1860 synchronized (mutex) { 1861 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex); 1862 } 1863 } 1864 public SortedSet<E> tailSet(E fromElement) { 1865 synchronized (mutex) { 1866 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex); 1867 } 1868 } 1869 1870 public E first() { 1871 synchronized (mutex) {return ss.first();} 1872 } 1873 public E last() { 1874 synchronized (mutex) {return ss.last();} 1875 } 1876 } 1877 1878 /** 1879 * Returns a synchronized (thread-safe) list backed by the specified 1880 * list. In order to guarantee serial access, it is critical that 1881 * <strong>all</strong> access to the backing list is accomplished 1882 * through the returned list.<p> 1883 * 1884 * It is imperative that the user manually synchronize on the returned 1885 * list when iterating over it: 1886 * <pre> 1887 * List list = Collections.synchronizedList(new ArrayList()); 1888 * ... 1889 * synchronized (list) { 1890 * Iterator i = list.iterator(); // Must be in synchronized block 1891 * while (i.hasNext()) 1892 * foo(i.next()); 1893 * } 1894 * </pre> 1895 * Failure to follow this advice may result in non-deterministic behavior. 1896 * 1897 * <p>The returned list will be serializable if the specified list is 1898 * serializable. 1899 * 1900 * @param list the list to be "wrapped" in a synchronized list. 1901 * @return a synchronized view of the specified list. 1902 */ 1903 public static <T> List<T> synchronizedList(List<T> list) { 1904 return (list instanceof RandomAccess ? 1905 new SynchronizedRandomAccessList<>(list) : 1906 new SynchronizedList<>(list)); 1907 } 1908 1909 static <T> List<T> synchronizedList(List<T> list, Object mutex) { 1910 return (list instanceof RandomAccess ? 1911 new SynchronizedRandomAccessList<>(list, mutex) : 1912 new SynchronizedList<>(list, mutex)); 1913 } 1914 1915 /** 1916 * @serial include 1917 */ 1918 static class SynchronizedList<E> 1919 extends SynchronizedCollection<E> 1920 implements List<E> { 1921 private static final long serialVersionUID = -7754090372962971524L; 1922 1923 final List<E> list; 1924 1925 SynchronizedList(List<E> list) { 1926 super(list); 1927 this.list = list; 1928 } 1929 SynchronizedList(List<E> list, Object mutex) { 1930 super(list, mutex); 1931 this.list = list; 1932 } 1933 1934 public boolean equals(Object o) { 1935 if (this == o) 1936 return true; 1937 synchronized (mutex) {return list.equals(o);} 1938 } 1939 public int hashCode() { 1940 synchronized (mutex) {return list.hashCode();} 1941 } 1942 1943 public E get(int index) { 1944 synchronized (mutex) {return list.get(index);} 1945 } 1946 public E set(int index, E element) { 1947 synchronized (mutex) {return list.set(index, element);} 1948 } 1949 public void add(int index, E element) { 1950 synchronized (mutex) {list.add(index, element);} 1951 } 1952 public E remove(int index) { 1953 synchronized (mutex) {return list.remove(index);} 1954 } 1955 1956 public int indexOf(Object o) { 1957 synchronized (mutex) {return list.indexOf(o);} 1958 } 1959 public int lastIndexOf(Object o) { 1960 synchronized (mutex) {return list.lastIndexOf(o);} 1961 } 1962 1963 public boolean addAll(int index, Collection<? extends E> c) { 1964 synchronized (mutex) {return list.addAll(index, c);} 1965 } 1966 1967 public ListIterator<E> listIterator() { 1968 return list.listIterator(); // Must be manually synched by user 1969 } 1970 1971 public ListIterator<E> listIterator(int index) { 1972 return list.listIterator(index); // Must be manually synched by user 1973 } 1974 1975 public List<E> subList(int fromIndex, int toIndex) { 1976 synchronized (mutex) { 1977 return new SynchronizedList<>(list.subList(fromIndex, toIndex), 1978 mutex); 1979 } 1980 } 1981 1982 /** 1983 * SynchronizedRandomAccessList instances are serialized as 1984 * SynchronizedList instances to allow them to be deserialized 1985 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList). 1986 * This method inverts the transformation. As a beneficial 1987 * side-effect, it also grafts the RandomAccess marker onto 1988 * SynchronizedList instances that were serialized in pre-1.4 JREs. 1989 * 1990 * Note: Unfortunately, SynchronizedRandomAccessList instances 1991 * serialized in 1.4.1 and deserialized in 1.4 will become 1992 * SynchronizedList instances, as this method was missing in 1.4. 1993 */ 1994 private Object readResolve() { 1995 return (list instanceof RandomAccess 1996 ? new SynchronizedRandomAccessList<>(list) 1997 : this); 1998 } 1999 } 2000 2001 /** 2002 * @serial include 2003 */ 2004 static class SynchronizedRandomAccessList<E> 2005 extends SynchronizedList<E> 2006 implements RandomAccess { 2007 2008 SynchronizedRandomAccessList(List<E> list) { 2009 super(list); 2010 } 2011 2012 SynchronizedRandomAccessList(List<E> list, Object mutex) { 2013 super(list, mutex); 2014 } 2015 2016 public List<E> subList(int fromIndex, int toIndex) { 2017 synchronized (mutex) { 2018 return new SynchronizedRandomAccessList<>( 2019 list.subList(fromIndex, toIndex), mutex); 2020 } 2021 } 2022 2023 private static final long serialVersionUID = 1530674583602358482L; 2024 2025 /** 2026 * Allows instances to be deserialized in pre-1.4 JREs (which do 2027 * not have SynchronizedRandomAccessList). SynchronizedList has 2028 * a readResolve method that inverts this transformation upon 2029 * deserialization. 2030 */ 2031 private Object writeReplace() { 2032 return new SynchronizedList<>(list); 2033 } 2034 } 2035 2036 /** 2037 * Returns a synchronized (thread-safe) map backed by the specified 2038 * map. In order to guarantee serial access, it is critical that 2039 * <strong>all</strong> access to the backing map is accomplished 2040 * through the returned map.<p> 2041 * 2042 * It is imperative that the user manually synchronize on the returned 2043 * map when iterating over any of its collection views: 2044 * <pre> 2045 * Map m = Collections.synchronizedMap(new HashMap()); 2046 * ... 2047 * Set s = m.keySet(); // Needn't be in synchronized block 2048 * ... 2049 * synchronized (m) { // Synchronizing on m, not s! 2050 * Iterator i = s.iterator(); // Must be in synchronized block 2051 * while (i.hasNext()) 2052 * foo(i.next()); 2053 * } 2054 * </pre> 2055 * Failure to follow this advice may result in non-deterministic behavior. 2056 * 2057 * <p>The returned map will be serializable if the specified map is 2058 * serializable. 2059 * 2060 * @param m the map to be "wrapped" in a synchronized map. 2061 * @return a synchronized view of the specified map. 2062 */ 2063 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { 2064 return new SynchronizedMap<>(m); 2065 } 2066 2067 /** 2068 * @serial include 2069 */ 2070 private static class SynchronizedMap<K,V> 2071 implements Map<K,V>, Serializable { 2072 private static final long serialVersionUID = 1978198479659022715L; 2073 2074 private final Map<K,V> m; // Backing Map 2075 final Object mutex; // Object on which to synchronize 2076 2077 SynchronizedMap(Map<K,V> m) { 2078 if (m==null) 2079 throw new NullPointerException(); 2080 this.m = m; 2081 mutex = this; 2082 } 2083 2084 SynchronizedMap(Map<K,V> m, Object mutex) { 2085 this.m = m; 2086 this.mutex = mutex; 2087 } 2088 2089 public int size() { 2090 synchronized (mutex) {return m.size();} 2091 } 2092 public boolean isEmpty() { 2093 synchronized (mutex) {return m.isEmpty();} 2094 } 2095 public boolean containsKey(Object key) { 2096 synchronized (mutex) {return m.containsKey(key);} 2097 } 2098 public boolean containsValue(Object value) { 2099 synchronized (mutex) {return m.containsValue(value);} 2100 } 2101 public V get(Object key) { 2102 synchronized (mutex) {return m.get(key);} 2103 } 2104 2105 public V put(K key, V value) { 2106 synchronized (mutex) {return m.put(key, value);} 2107 } 2108 public V remove(Object key) { 2109 synchronized (mutex) {return m.remove(key);} 2110 } 2111 public void putAll(Map<? extends K, ? extends V> map) { 2112 synchronized (mutex) {m.putAll(map);} 2113 } 2114 public void clear() { 2115 synchronized (mutex) {m.clear();} 2116 } 2117 2118 private transient Set<K> keySet = null; 2119 private transient Set<Map.Entry<K,V>> entrySet = null; 2120 private transient Collection<V> values = null; 2121 2122 public Set<K> keySet() { 2123 synchronized (mutex) { 2124 if (keySet==null) 2125 keySet = new SynchronizedSet<>(m.keySet(), mutex); 2126 return keySet; 2127 } 2128 } 2129 2130 public Set<Map.Entry<K,V>> entrySet() { 2131 synchronized (mutex) { 2132 if (entrySet==null) 2133 entrySet = new SynchronizedSet<>(m.entrySet(), mutex); 2134 return entrySet; 2135 } 2136 } 2137 2138 public Collection<V> values() { 2139 synchronized (mutex) { 2140 if (values==null) 2141 values = new SynchronizedCollection<>(m.values(), mutex); 2142 return values; 2143 } 2144 } 2145 2146 public boolean equals(Object o) { 2147 if (this == o) 2148 return true; 2149 synchronized (mutex) {return m.equals(o);} 2150 } 2151 public int hashCode() { 2152 synchronized (mutex) {return m.hashCode();} 2153 } 2154 public String toString() { 2155 synchronized (mutex) {return m.toString();} 2156 } 2157 2158 // Override default methods in Map 2159 @Override 2160 public V getOrDefault(Object k, V defaultValue) { 2161 synchronized (mutex) {return m.getOrDefault(k, defaultValue);} 2162 } 2163 2164 @Override 2165 public void forEach(BiConsumer<? super K, ? super V> action) { 2166 synchronized (mutex) {m.forEach(action);} 2167 } 2168 @Override 2169 public V putIfAbsent(K key, V value) { 2170 synchronized (mutex) {return m.putIfAbsent(key, value);} 2171 } 2172 @Override 2173 public boolean remove(Object key, Object value) { 2174 synchronized (mutex) {return m.remove(key, value);} 2175 } 2176 @Override 2177 public boolean replace(K key, V oldValue, V newValue) { 2178 synchronized (mutex) {return m.replace(key, oldValue, newValue);} 2179 } 2180 @Override 2181 public V replace(K key, V value) { 2182 synchronized (mutex) {return m.replace(key, value);} 2183 } 2184 @Override 2185 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 2186 synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);} 2187 } 2188 @Override 2189 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 2190 synchronized (mutex) {return m.computeIfPresent(key, remappingFunction);} 2191 } 2192 @Override 2193 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 2194 synchronized (mutex) {return m.compute(key, remappingFunction);} 2195 } 2196 @Override 2197 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 2198 synchronized (mutex) {return m.merge(key, value, remappingFunction);} 2199 } 2200 2201 private void writeObject(ObjectOutputStream s) throws IOException { 2202 synchronized (mutex) {s.defaultWriteObject();} 2203 } 2204 } 2205 2206 /** 2207 * Returns a synchronized (thread-safe) sorted map backed by the specified 2208 * sorted map. In order to guarantee serial access, it is critical that 2209 * <strong>all</strong> access to the backing sorted map is accomplished 2210 * through the returned sorted map (or its views).<p> 2211 * 2212 * It is imperative that the user manually synchronize on the returned 2213 * sorted map when iterating over any of its collection views, or the 2214 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or 2215 * <tt>tailMap</tt> views. 2216 * <pre> 2217 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap()); 2218 * ... 2219 * Set s = m.keySet(); // Needn't be in synchronized block 2220 * ... 2221 * synchronized (m) { // Synchronizing on m, not s! 2222 * Iterator i = s.iterator(); // Must be in synchronized block 2223 * while (i.hasNext()) 2224 * foo(i.next()); 2225 * } 2226 * </pre> 2227 * or: 2228 * <pre> 2229 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap()); 2230 * SortedMap m2 = m.subMap(foo, bar); 2231 * ... 2232 * Set s2 = m2.keySet(); // Needn't be in synchronized block 2233 * ... 2234 * synchronized (m) { // Synchronizing on m, not m2 or s2! 2235 * Iterator i = s.iterator(); // Must be in synchronized block 2236 * while (i.hasNext()) 2237 * foo(i.next()); 2238 * } 2239 * </pre> 2240 * Failure to follow this advice may result in non-deterministic behavior. 2241 * 2242 * <p>The returned sorted map will be serializable if the specified 2243 * sorted map is serializable. 2244 * 2245 * @param m the sorted map to be "wrapped" in a synchronized sorted map. 2246 * @return a synchronized view of the specified sorted map. 2247 */ 2248 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) { 2249 return new SynchronizedSortedMap<>(m); 2250 } 2251 2252 2253 /** 2254 * @serial include 2255 */ 2256 static class SynchronizedSortedMap<K,V> 2257 extends SynchronizedMap<K,V> 2258 implements SortedMap<K,V> 2259 { 2260 private static final long serialVersionUID = -8798146769416483793L; 2261 2262 private final SortedMap<K,V> sm; 2263 2264 SynchronizedSortedMap(SortedMap<K,V> m) { 2265 super(m); 2266 sm = m; 2267 } 2268 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) { 2269 super(m, mutex); 2270 sm = m; 2271 } 2272 2273 public Comparator<? super K> comparator() { 2274 synchronized (mutex) {return sm.comparator();} 2275 } 2276 2277 public SortedMap<K,V> subMap(K fromKey, K toKey) { 2278 synchronized (mutex) { 2279 return new SynchronizedSortedMap<>( 2280 sm.subMap(fromKey, toKey), mutex); 2281 } 2282 } 2283 public SortedMap<K,V> headMap(K toKey) { 2284 synchronized (mutex) { 2285 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex); 2286 } 2287 } 2288 public SortedMap<K,V> tailMap(K fromKey) { 2289 synchronized (mutex) { 2290 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex); 2291 } 2292 } 2293 2294 public K firstKey() { 2295 synchronized (mutex) {return sm.firstKey();} 2296 } 2297 public K lastKey() { 2298 synchronized (mutex) {return sm.lastKey();} 2299 } 2300 } 2301 2302 // Dynamically typesafe collection wrappers 2303 2304 /** 2305 * Returns a dynamically typesafe view of the specified collection. 2306 * Any attempt to insert an element of the wrong type will result in an 2307 * immediate {@link ClassCastException}. Assuming a collection 2308 * contains no incorrectly typed elements prior to the time a 2309 * dynamically typesafe view is generated, and that all subsequent 2310 * access to the collection takes place through the view, it is 2311 * <i>guaranteed</i> that the collection cannot contain an incorrectly 2312 * typed element. 2313 * 2314 * <p>The generics mechanism in the language provides compile-time 2315 * (static) type checking, but it is possible to defeat this mechanism 2316 * with unchecked casts. Usually this is not a problem, as the compiler 2317 * issues warnings on all such unchecked operations. There are, however, 2318 * times when static type checking alone is not sufficient. For example, 2319 * suppose a collection is passed to a third-party library and it is 2320 * imperative that the library code not corrupt the collection by 2321 * inserting an element of the wrong type. 2322 * 2323 * <p>Another use of dynamically typesafe views is debugging. Suppose a 2324 * program fails with a {@code ClassCastException}, indicating that an 2325 * incorrectly typed element was put into a parameterized collection. 2326 * Unfortunately, the exception can occur at any time after the erroneous 2327 * element is inserted, so it typically provides little or no information 2328 * as to the real source of the problem. If the problem is reproducible, 2329 * one can quickly determine its source by temporarily modifying the 2330 * program to wrap the collection with a dynamically typesafe view. 2331 * For example, this declaration: 2332 * <pre> {@code 2333 * Collection<String> c = new HashSet<String>(); 2334 * }</pre> 2335 * may be replaced temporarily by this one: 2336 * <pre> {@code 2337 * Collection<String> c = Collections.checkedCollection( 2338 * new HashSet<String>(), String.class); 2339 * }</pre> 2340 * Running the program again will cause it to fail at the point where 2341 * an incorrectly typed element is inserted into the collection, clearly 2342 * identifying the source of the problem. Once the problem is fixed, the 2343 * modified declaration may be reverted back to the original. 2344 * 2345 * <p>The returned collection does <i>not</i> pass the hashCode and equals 2346 * operations through to the backing collection, but relies on 2347 * {@code Object}'s {@code equals} and {@code hashCode} methods. This 2348 * is necessary to preserve the contracts of these operations in the case 2349 * that the backing collection is a set or a list. 2350 * 2351 * <p>The returned collection will be serializable if the specified 2352 * collection is serializable. 2353 * 2354 * <p>Since {@code null} is considered to be a value of any reference 2355 * type, the returned collection permits insertion of null elements 2356 * whenever the backing collection does. 2357 * 2358 * @param c the collection for which a dynamically typesafe view is to be 2359 * returned 2360 * @param type the type of element that {@code c} is permitted to hold 2361 * @return a dynamically typesafe view of the specified collection 2362 * @since 1.5 2363 */ 2364 public static <E> Collection<E> checkedCollection(Collection<E> c, 2365 Class<E> type) { 2366 return new CheckedCollection<>(c, type); 2367 } 2368 2369 @SuppressWarnings("unchecked") 2370 static <T> T[] zeroLengthArray(Class<T> type) { 2371 return (T[]) Array.newInstance(type, 0); 2372 } 2373 2374 /** 2375 * @serial include 2376 */ 2377 static class CheckedCollection<E> implements Collection<E>, Serializable { 2378 private static final long serialVersionUID = 1578914078182001775L; 2379 2380 final Collection<E> c; 2381 final Class<E> type; 2382 2383 void typeCheck(Object o) { 2384 if (o != null && !type.isInstance(o)) 2385 throw new ClassCastException(badElementMsg(o)); 2386 } 2387 2388 private String badElementMsg(Object o) { 2389 return "Attempt to insert " + o.getClass() + 2390 " element into collection with element type " + type; 2391 } 2392 2393 CheckedCollection(Collection<E> c, Class<E> type) { 2394 if (c==null || type == null) 2395 throw new NullPointerException(); 2396 this.c = c; 2397 this.type = type; 2398 } 2399 2400 public int size() { return c.size(); } 2401 public boolean isEmpty() { return c.isEmpty(); } 2402 public boolean contains(Object o) { return c.contains(o); } 2403 public Object[] toArray() { return c.toArray(); } 2404 public <T> T[] toArray(T[] a) { return c.toArray(a); } 2405 public String toString() { return c.toString(); } 2406 public boolean remove(Object o) { return c.remove(o); } 2407 public void clear() { c.clear(); } 2408 2409 public boolean containsAll(Collection<?> coll) { 2410 return c.containsAll(coll); 2411 } 2412 public boolean removeAll(Collection<?> coll) { 2413 return c.removeAll(coll); 2414 } 2415 public boolean retainAll(Collection<?> coll) { 2416 return c.retainAll(coll); 2417 } 2418 2419 public Iterator<E> iterator() { 2420 final Iterator<E> it = c.iterator(); 2421 return new Iterator<E>() { 2422 public boolean hasNext() { return it.hasNext(); } 2423 public E next() { return it.next(); } 2424 public void remove() { it.remove(); }}; 2425 } 2426 2427 public boolean add(E e) { 2428 typeCheck(e); 2429 return c.add(e); 2430 } 2431 2432 private E[] zeroLengthElementArray = null; // Lazily initialized 2433 2434 private E[] zeroLengthElementArray() { 2435 return zeroLengthElementArray != null ? zeroLengthElementArray : 2436 (zeroLengthElementArray = zeroLengthArray(type)); 2437 } 2438 2439 @SuppressWarnings("unchecked") 2440 Collection<E> checkedCopyOf(Collection<? extends E> coll) { 2441 Object[] a = null; 2442 try { 2443 E[] z = zeroLengthElementArray(); 2444 a = coll.toArray(z); 2445 // Defend against coll violating the toArray contract 2446 if (a.getClass() != z.getClass()) 2447 a = Arrays.copyOf(a, a.length, z.getClass()); 2448 } catch (ArrayStoreException ignore) { 2449 // To get better and consistent diagnostics, 2450 // we call typeCheck explicitly on each element. 2451 // We call clone() to defend against coll retaining a 2452 // reference to the returned array and storing a bad 2453 // element into it after it has been type checked. 2454 a = coll.toArray().clone(); 2455 for (Object o : a) 2456 typeCheck(o); 2457 } 2458 // A slight abuse of the type system, but safe here. 2459 return (Collection<E>) Arrays.asList(a); 2460 } 2461 2462 public boolean addAll(Collection<? extends E> coll) { 2463 // Doing things this way insulates us from concurrent changes 2464 // in the contents of coll and provides all-or-nothing 2465 // semantics (which we wouldn't get if we type-checked each 2466 // element as we added it) 2467 return c.addAll(checkedCopyOf(coll)); 2468 } 2469 } 2470 2471 /** 2472 * Returns a dynamically typesafe view of the specified queue. 2473 * Any attempt to insert an element of the wrong type will result in 2474 * an immediate {@link ClassCastException}. Assuming a queue contains 2475 * no incorrectly typed elements prior to the time a dynamically typesafe 2476 * view is generated, and that all subsequent access to the queue 2477 * takes place through the view, it is <i>guaranteed</i> that the 2478 * queue cannot contain an incorrectly typed element. 2479 * 2480 * <p>A discussion of the use of dynamically typesafe views may be 2481 * found in the documentation for the {@link #checkedCollection 2482 * checkedCollection} method. 2483 * 2484 * <p>The returned queue will be serializable if the specified queue 2485 * is serializable. 2486 * 2487 * <p>Since {@code null} is considered to be a value of any reference 2488 * type, the returned queue permits insertion of {@code null} elements 2489 * whenever the backing queue does. 2490 * 2491 * @param queue the queue for which a dynamically typesafe view is to be 2492 * returned 2493 * @param type the type of element that {@code queue} is permitted to hold 2494 * @return a dynamically typesafe view of the specified queue 2495 * @since 1.8 2496 */ 2497 public static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type) { 2498 return new CheckedQueue<>(queue, type); 2499 } 2500 2501 /** 2502 * @serial include 2503 */ 2504 static class CheckedQueue<E> 2505 extends CheckedCollection<E> 2506 implements Queue<E>, Serializable 2507 { 2508 private static final long serialVersionUID = 1433151992604707767L; 2509 final Queue<E> queue; 2510 2511 CheckedQueue(Queue<E> queue, Class<E> elementType) { 2512 super(queue, elementType); 2513 this.queue = queue; 2514 } 2515 2516 public E element() {return queue.element();} 2517 public boolean equals(Object o) {return o == this || c.equals(o);} 2518 public int hashCode() {return c.hashCode();} 2519 public E peek() {return queue.peek();} 2520 public E poll() {return queue.poll();} 2521 public E remove() {return queue.remove();} 2522 2523 public boolean offer(E e) { 2524 typeCheck(e); 2525 return add(e); 2526 } 2527 } 2528 2529 /** 2530 * Returns a dynamically typesafe view of the specified set. 2531 * Any attempt to insert an element of the wrong type will result in 2532 * an immediate {@link ClassCastException}. Assuming a set contains 2533 * no incorrectly typed elements prior to the time a dynamically typesafe 2534 * view is generated, and that all subsequent access to the set 2535 * takes place through the view, it is <i>guaranteed</i> that the 2536 * set cannot contain an incorrectly typed element. 2537 * 2538 * <p>A discussion of the use of dynamically typesafe views may be 2539 * found in the documentation for the {@link #checkedCollection 2540 * checkedCollection} method. 2541 * 2542 * <p>The returned set will be serializable if the specified set is 2543 * serializable. 2544 * 2545 * <p>Since {@code null} is considered to be a value of any reference 2546 * type, the returned set permits insertion of null elements whenever 2547 * the backing set does. 2548 * 2549 * @param s the set for which a dynamically typesafe view is to be 2550 * returned 2551 * @param type the type of element that {@code s} is permitted to hold 2552 * @return a dynamically typesafe view of the specified set 2553 * @since 1.5 2554 */ 2555 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) { 2556 return new CheckedSet<>(s, type); 2557 } 2558 2559 /** 2560 * @serial include 2561 */ 2562 static class CheckedSet<E> extends CheckedCollection<E> 2563 implements Set<E>, Serializable 2564 { 2565 private static final long serialVersionUID = 4694047833775013803L; 2566 2567 CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); } 2568 2569 public boolean equals(Object o) { return o == this || c.equals(o); } 2570 public int hashCode() { return c.hashCode(); } 2571 } 2572 2573 /** 2574 * Returns a dynamically typesafe view of the specified sorted set. 2575 * Any attempt to insert an element of the wrong type will result in an 2576 * immediate {@link ClassCastException}. Assuming a sorted set 2577 * contains no incorrectly typed elements prior to the time a 2578 * dynamically typesafe view is generated, and that all subsequent 2579 * access to the sorted set takes place through the view, it is 2580 * <i>guaranteed</i> that the sorted set cannot contain an incorrectly 2581 * typed element. 2582 * 2583 * <p>A discussion of the use of dynamically typesafe views may be 2584 * found in the documentation for the {@link #checkedCollection 2585 * checkedCollection} method. 2586 * 2587 * <p>The returned sorted set will be serializable if the specified sorted 2588 * set is serializable. 2589 * 2590 * <p>Since {@code null} is considered to be a value of any reference 2591 * type, the returned sorted set permits insertion of null elements 2592 * whenever the backing sorted set does. 2593 * 2594 * @param s the sorted set for which a dynamically typesafe view is to be 2595 * returned 2596 * @param type the type of element that {@code s} is permitted to hold 2597 * @return a dynamically typesafe view of the specified sorted set 2598 * @since 1.5 2599 */ 2600 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, 2601 Class<E> type) { 2602 return new CheckedSortedSet<>(s, type); 2603 } 2604 2605 /** 2606 * @serial include 2607 */ 2608 static class CheckedSortedSet<E> extends CheckedSet<E> 2609 implements SortedSet<E>, Serializable 2610 { 2611 private static final long serialVersionUID = 1599911165492914959L; 2612 private final SortedSet<E> ss; 2613 2614 CheckedSortedSet(SortedSet<E> s, Class<E> type) { 2615 super(s, type); 2616 ss = s; 2617 } 2618 2619 public Comparator<? super E> comparator() { return ss.comparator(); } 2620 public E first() { return ss.first(); } 2621 public E last() { return ss.last(); } 2622 2623 public SortedSet<E> subSet(E fromElement, E toElement) { 2624 return checkedSortedSet(ss.subSet(fromElement,toElement), type); 2625 } 2626 public SortedSet<E> headSet(E toElement) { 2627 return checkedSortedSet(ss.headSet(toElement), type); 2628 } 2629 public SortedSet<E> tailSet(E fromElement) { 2630 return checkedSortedSet(ss.tailSet(fromElement), type); 2631 } 2632 } 2633 2634 /** 2635 * Returns a dynamically typesafe view of the specified list. 2636 * Any attempt to insert an element of the wrong type will result in 2637 * an immediate {@link ClassCastException}. Assuming a list contains 2638 * no incorrectly typed elements prior to the time a dynamically typesafe 2639 * view is generated, and that all subsequent access to the list 2640 * takes place through the view, it is <i>guaranteed</i> that the 2641 * list cannot contain an incorrectly typed element. 2642 * 2643 * <p>A discussion of the use of dynamically typesafe views may be 2644 * found in the documentation for the {@link #checkedCollection 2645 * checkedCollection} method. 2646 * 2647 * <p>The returned list will be serializable if the specified list 2648 * is serializable. 2649 * 2650 * <p>Since {@code null} is considered to be a value of any reference 2651 * type, the returned list permits insertion of null elements whenever 2652 * the backing list does. 2653 * 2654 * @param list the list for which a dynamically typesafe view is to be 2655 * returned 2656 * @param type the type of element that {@code list} is permitted to hold 2657 * @return a dynamically typesafe view of the specified list 2658 * @since 1.5 2659 */ 2660 public static <E> List<E> checkedList(List<E> list, Class<E> type) { 2661 return (list instanceof RandomAccess ? 2662 new CheckedRandomAccessList<>(list, type) : 2663 new CheckedList<>(list, type)); 2664 } 2665 2666 /** 2667 * @serial include 2668 */ 2669 static class CheckedList<E> 2670 extends CheckedCollection<E> 2671 implements List<E> 2672 { 2673 private static final long serialVersionUID = 65247728283967356L; 2674 final List<E> list; 2675 2676 CheckedList(List<E> list, Class<E> type) { 2677 super(list, type); 2678 this.list = list; 2679 } 2680 2681 public boolean equals(Object o) { return o == this || list.equals(o); } 2682 public int hashCode() { return list.hashCode(); } 2683 public E get(int index) { return list.get(index); } 2684 public E remove(int index) { return list.remove(index); } 2685 public int indexOf(Object o) { return list.indexOf(o); } 2686 public int lastIndexOf(Object o) { return list.lastIndexOf(o); } 2687 2688 public E set(int index, E element) { 2689 typeCheck(element); 2690 return list.set(index, element); 2691 } 2692 2693 public void add(int index, E element) { 2694 typeCheck(element); 2695 list.add(index, element); 2696 } 2697 2698 public boolean addAll(int index, Collection<? extends E> c) { 2699 return list.addAll(index, checkedCopyOf(c)); 2700 } 2701 public ListIterator<E> listIterator() { return listIterator(0); } 2702 2703 public ListIterator<E> listIterator(final int index) { 2704 final ListIterator<E> i = list.listIterator(index); 2705 2706 return new ListIterator<E>() { 2707 public boolean hasNext() { return i.hasNext(); } 2708 public E next() { return i.next(); } 2709 public boolean hasPrevious() { return i.hasPrevious(); } 2710 public E previous() { return i.previous(); } 2711 public int nextIndex() { return i.nextIndex(); } 2712 public int previousIndex() { return i.previousIndex(); } 2713 public void remove() { i.remove(); } 2714 2715 public void set(E e) { 2716 typeCheck(e); 2717 i.set(e); 2718 } 2719 2720 public void add(E e) { 2721 typeCheck(e); 2722 i.add(e); 2723 } 2724 }; 2725 } 2726 2727 public List<E> subList(int fromIndex, int toIndex) { 2728 return new CheckedList<>(list.subList(fromIndex, toIndex), type); 2729 } 2730 } 2731 2732 /** 2733 * @serial include 2734 */ 2735 static class CheckedRandomAccessList<E> extends CheckedList<E> 2736 implements RandomAccess 2737 { 2738 private static final long serialVersionUID = 1638200125423088369L; 2739 2740 CheckedRandomAccessList(List<E> list, Class<E> type) { 2741 super(list, type); 2742 } 2743 2744 public List<E> subList(int fromIndex, int toIndex) { 2745 return new CheckedRandomAccessList<>( 2746 list.subList(fromIndex, toIndex), type); 2747 } 2748 } 2749 2750 /** 2751 * Returns a dynamically typesafe view of the specified map. 2752 * Any attempt to insert a mapping whose key or value have the wrong 2753 * type will result in an immediate {@link ClassCastException}. 2754 * Similarly, any attempt to modify the value currently associated with 2755 * a key will result in an immediate {@link ClassCastException}, 2756 * whether the modification is attempted directly through the map 2757 * itself, or through a {@link Map.Entry} instance obtained from the 2758 * map's {@link Map#entrySet() entry set} view. 2759 * 2760 * <p>Assuming a map contains no incorrectly typed keys or values 2761 * prior to the time a dynamically typesafe view is generated, and 2762 * that all subsequent access to the map takes place through the view 2763 * (or one of its collection views), it is <i>guaranteed</i> that the 2764 * map cannot contain an incorrectly typed key or value. 2765 * 2766 * <p>A discussion of the use of dynamically typesafe views may be 2767 * found in the documentation for the {@link #checkedCollection 2768 * checkedCollection} method. 2769 * 2770 * <p>The returned map will be serializable if the specified map is 2771 * serializable. 2772 * 2773 * <p>Since {@code null} is considered to be a value of any reference 2774 * type, the returned map permits insertion of null keys or values 2775 * whenever the backing map does. 2776 * 2777 * @param m the map for which a dynamically typesafe view is to be 2778 * returned 2779 * @param keyType the type of key that {@code m} is permitted to hold 2780 * @param valueType the type of value that {@code m} is permitted to hold 2781 * @return a dynamically typesafe view of the specified map 2782 * @since 1.5 2783 */ 2784 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, 2785 Class<K> keyType, 2786 Class<V> valueType) { 2787 return new CheckedMap<>(m, keyType, valueType); 2788 } 2789 2790 2791 /** 2792 * @serial include 2793 */ 2794 private static class CheckedMap<K,V> 2795 implements Map<K,V>, Serializable 2796 { 2797 private static final long serialVersionUID = 5742860141034234728L; 2798 2799 private final Map<K, V> m; 2800 final Class<K> keyType; 2801 final Class<V> valueType; 2802 2803 private void typeCheck(Object key, Object value) { 2804 if (key != null && !keyType.isInstance(key)) 2805 throw new ClassCastException(badKeyMsg(key)); 2806 2807 if (value != null && !valueType.isInstance(value)) 2808 throw new ClassCastException(badValueMsg(value)); 2809 } 2810 2811 private String badKeyMsg(Object key) { 2812 return "Attempt to insert " + key.getClass() + 2813 " key into map with key type " + keyType; 2814 } 2815 2816 private String badValueMsg(Object value) { 2817 return "Attempt to insert " + value.getClass() + 2818 " value into map with value type " + valueType; 2819 } 2820 2821 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) { 2822 if (m == null || keyType == null || valueType == null) 2823 throw new NullPointerException(); 2824 this.m = m; 2825 this.keyType = keyType; 2826 this.valueType = valueType; 2827 } 2828 2829 public int size() { return m.size(); } 2830 public boolean isEmpty() { return m.isEmpty(); } 2831 public boolean containsKey(Object key) { return m.containsKey(key); } 2832 public boolean containsValue(Object v) { return m.containsValue(v); } 2833 public V get(Object key) { return m.get(key); } 2834 public V remove(Object key) { return m.remove(key); } 2835 public void clear() { m.clear(); } 2836 public Set<K> keySet() { return m.keySet(); } 2837 public Collection<V> values() { return m.values(); } 2838 public boolean equals(Object o) { return o == this || m.equals(o); } 2839 public int hashCode() { return m.hashCode(); } 2840 public String toString() { return m.toString(); } 2841 2842 public V put(K key, V value) { 2843 typeCheck(key, value); 2844 return m.put(key, value); 2845 } 2846 2847 @SuppressWarnings("unchecked") 2848 public void putAll(Map<? extends K, ? extends V> t) { 2849 // Satisfy the following goals: 2850 // - good diagnostics in case of type mismatch 2851 // - all-or-nothing semantics 2852 // - protection from malicious t 2853 // - correct behavior if t is a concurrent map 2854 Object[] entries = t.entrySet().toArray(); 2855 List<Map.Entry<K,V>> checked = new ArrayList<>(entries.length); 2856 for (Object o : entries) { 2857 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 2858 Object k = e.getKey(); 2859 Object v = e.getValue(); 2860 typeCheck(k, v); 2861 checked.add( 2862 new AbstractMap.SimpleImmutableEntry<>((K) k, (V) v)); 2863 } 2864 for (Map.Entry<K,V> e : checked) 2865 m.put(e.getKey(), e.getValue()); 2866 } 2867 2868 private transient Set<Map.Entry<K,V>> entrySet = null; 2869 2870 public Set<Map.Entry<K,V>> entrySet() { 2871 if (entrySet==null) 2872 entrySet = new CheckedEntrySet<>(m.entrySet(), valueType); 2873 return entrySet; 2874 } 2875 2876 /** 2877 * We need this class in addition to CheckedSet as Map.Entry permits 2878 * modification of the backing Map via the setValue operation. This 2879 * class is subtle: there are many possible attacks that must be 2880 * thwarted. 2881 * 2882 * @serial exclude 2883 */ 2884 static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> { 2885 private final Set<Map.Entry<K,V>> s; 2886 private final Class<V> valueType; 2887 2888 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) { 2889 this.s = s; 2890 this.valueType = valueType; 2891 } 2892 2893 public int size() { return s.size(); } 2894 public boolean isEmpty() { return s.isEmpty(); } 2895 public String toString() { return s.toString(); } 2896 public int hashCode() { return s.hashCode(); } 2897 public void clear() { s.clear(); } 2898 2899 public boolean add(Map.Entry<K, V> e) { 2900 throw new UnsupportedOperationException(); 2901 } 2902 public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) { 2903 throw new UnsupportedOperationException(); 2904 } 2905 2906 public Iterator<Map.Entry<K,V>> iterator() { 2907 final Iterator<Map.Entry<K, V>> i = s.iterator(); 2908 final Class<V> valueType = this.valueType; 2909 2910 return new Iterator<Map.Entry<K,V>>() { 2911 public boolean hasNext() { return i.hasNext(); } 2912 public void remove() { i.remove(); } 2913 2914 public Map.Entry<K,V> next() { 2915 return checkedEntry(i.next(), valueType); 2916 } 2917 }; 2918 } 2919 2920 @SuppressWarnings("unchecked") 2921 public Object[] toArray() { 2922 Object[] source = s.toArray(); 2923 2924 /* 2925 * Ensure that we don't get an ArrayStoreException even if 2926 * s.toArray returns an array of something other than Object 2927 */ 2928 Object[] dest = (CheckedEntry.class.isInstance( 2929 source.getClass().getComponentType()) ? source : 2930 new Object[source.length]); 2931 2932 for (int i = 0; i < source.length; i++) 2933 dest[i] = checkedEntry((Map.Entry<K,V>)source[i], 2934 valueType); 2935 return dest; 2936 } 2937 2938 @SuppressWarnings("unchecked") 2939 public <T> T[] toArray(T[] a) { 2940 // We don't pass a to s.toArray, to avoid window of 2941 // vulnerability wherein an unscrupulous multithreaded client 2942 // could get his hands on raw (unwrapped) Entries from s. 2943 T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); 2944 2945 for (int i=0; i<arr.length; i++) 2946 arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i], 2947 valueType); 2948 if (arr.length > a.length) 2949 return arr; 2950 2951 System.arraycopy(arr, 0, a, 0, arr.length); 2952 if (a.length > arr.length) 2953 a[arr.length] = null; 2954 return a; 2955 } 2956 2957 /** 2958 * This method is overridden to protect the backing set against 2959 * an object with a nefarious equals function that senses 2960 * that the equality-candidate is Map.Entry and calls its 2961 * setValue method. 2962 */ 2963 public boolean contains(Object o) { 2964 if (!(o instanceof Map.Entry)) 2965 return false; 2966 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 2967 return s.contains( 2968 (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType)); 2969 } 2970 2971 /** 2972 * The bulk collection methods are overridden to protect 2973 * against an unscrupulous collection whose contains(Object o) 2974 * method senses when o is a Map.Entry, and calls o.setValue. 2975 */ 2976 public boolean containsAll(Collection<?> c) { 2977 for (Object o : c) 2978 if (!contains(o)) // Invokes safe contains() above 2979 return false; 2980 return true; 2981 } 2982 2983 public boolean remove(Object o) { 2984 if (!(o instanceof Map.Entry)) 2985 return false; 2986 return s.remove(new AbstractMap.SimpleImmutableEntry 2987 <>((Map.Entry<?,?>)o)); 2988 } 2989 2990 public boolean removeAll(Collection<?> c) { 2991 return batchRemove(c, false); 2992 } 2993 public boolean retainAll(Collection<?> c) { 2994 return batchRemove(c, true); 2995 } 2996 private boolean batchRemove(Collection<?> c, boolean complement) { 2997 boolean modified = false; 2998 Iterator<Map.Entry<K,V>> it = iterator(); 2999 while (it.hasNext()) { 3000 if (c.contains(it.next()) != complement) { 3001 it.remove(); 3002 modified = true; 3003 } 3004 } 3005 return modified; 3006 } 3007 3008 public boolean equals(Object o) { 3009 if (o == this) 3010 return true; 3011 if (!(o instanceof Set)) 3012 return false; 3013 Set<?> that = (Set<?>) o; 3014 return that.size() == s.size() 3015 && containsAll(that); // Invokes safe containsAll() above 3016 } 3017 3018 static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e, 3019 Class<T> valueType) { 3020 return new CheckedEntry<>(e, valueType); 3021 } 3022 3023 /** 3024 * This "wrapper class" serves two purposes: it prevents 3025 * the client from modifying the backing Map, by short-circuiting 3026 * the setValue method, and it protects the backing Map against 3027 * an ill-behaved Map.Entry that attempts to modify another 3028 * Map.Entry when asked to perform an equality check. 3029 */ 3030 private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> { 3031 private final Map.Entry<K, V> e; 3032 private final Class<T> valueType; 3033 3034 CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) { 3035 this.e = e; 3036 this.valueType = valueType; 3037 } 3038 3039 public K getKey() { return e.getKey(); } 3040 public V getValue() { return e.getValue(); } 3041 public int hashCode() { return e.hashCode(); } 3042 public String toString() { return e.toString(); } 3043 3044 public V setValue(V value) { 3045 if (value != null && !valueType.isInstance(value)) 3046 throw new ClassCastException(badValueMsg(value)); 3047 return e.setValue(value); 3048 } 3049 3050 private String badValueMsg(Object value) { 3051 return "Attempt to insert " + value.getClass() + 3052 " value into map with value type " + valueType; 3053 } 3054 3055 public boolean equals(Object o) { 3056 if (o == this) 3057 return true; 3058 if (!(o instanceof Map.Entry)) 3059 return false; 3060 return e.equals(new AbstractMap.SimpleImmutableEntry 3061 <>((Map.Entry<?,?>)o)); 3062 } 3063 } 3064 } 3065 } 3066 3067 /** 3068 * Returns a dynamically typesafe view of the specified sorted map. 3069 * Any attempt to insert a mapping whose key or value have the wrong 3070 * type will result in an immediate {@link ClassCastException}. 3071 * Similarly, any attempt to modify the value currently associated with 3072 * a key will result in an immediate {@link ClassCastException}, 3073 * whether the modification is attempted directly through the map 3074 * itself, or through a {@link Map.Entry} instance obtained from the 3075 * map's {@link Map#entrySet() entry set} view. 3076 * 3077 * <p>Assuming a map contains no incorrectly typed keys or values 3078 * prior to the time a dynamically typesafe view is generated, and 3079 * that all subsequent access to the map takes place through the view 3080 * (or one of its collection views), it is <i>guaranteed</i> that the 3081 * map cannot contain an incorrectly typed key or value. 3082 * 3083 * <p>A discussion of the use of dynamically typesafe views may be 3084 * found in the documentation for the {@link #checkedCollection 3085 * checkedCollection} method. 3086 * 3087 * <p>The returned map will be serializable if the specified map is 3088 * serializable. 3089 * 3090 * <p>Since {@code null} is considered to be a value of any reference 3091 * type, the returned map permits insertion of null keys or values 3092 * whenever the backing map does. 3093 * 3094 * @param m the map for which a dynamically typesafe view is to be 3095 * returned 3096 * @param keyType the type of key that {@code m} is permitted to hold 3097 * @param valueType the type of value that {@code m} is permitted to hold 3098 * @return a dynamically typesafe view of the specified map 3099 * @since 1.5 3100 */ 3101 public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, 3102 Class<K> keyType, 3103 Class<V> valueType) { 3104 return new CheckedSortedMap<>(m, keyType, valueType); 3105 } 3106 3107 /** 3108 * @serial include 3109 */ 3110 static class CheckedSortedMap<K,V> extends CheckedMap<K,V> 3111 implements SortedMap<K,V>, Serializable 3112 { 3113 private static final long serialVersionUID = 1599671320688067438L; 3114 3115 private final SortedMap<K, V> sm; 3116 3117 CheckedSortedMap(SortedMap<K, V> m, 3118 Class<K> keyType, Class<V> valueType) { 3119 super(m, keyType, valueType); 3120 sm = m; 3121 } 3122 3123 public Comparator<? super K> comparator() { return sm.comparator(); } 3124 public K firstKey() { return sm.firstKey(); } 3125 public K lastKey() { return sm.lastKey(); } 3126 3127 public SortedMap<K,V> subMap(K fromKey, K toKey) { 3128 return checkedSortedMap(sm.subMap(fromKey, toKey), 3129 keyType, valueType); 3130 } 3131 public SortedMap<K,V> headMap(K toKey) { 3132 return checkedSortedMap(sm.headMap(toKey), keyType, valueType); 3133 } 3134 public SortedMap<K,V> tailMap(K fromKey) { 3135 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType); 3136 } 3137 } 3138 3139 // Empty collections 3140 3141 /** 3142 * Returns an iterator that has no elements. More precisely, 3143 * 3144 * <ul compact> 3145 * 3146 * <li>{@link Iterator#hasNext hasNext} always returns {@code 3147 * false}. 3148 * 3149 * <li>{@link Iterator#next next} always throws {@link 3150 * NoSuchElementException}. 3151 * 3152 * <li>{@link Iterator#remove remove} always throws {@link 3153 * IllegalStateException}. 3154 * 3155 * </ul> 3156 * 3157 * <p>Implementations of this method are permitted, but not 3158 * required, to return the same object from multiple invocations. 3159 * 3160 * @return an empty iterator 3161 * @since 1.7 3162 */ 3163 @SuppressWarnings("unchecked") 3164 public static <T> Iterator<T> emptyIterator() { 3165 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR; 3166 } 3167 3168 private static class EmptyIterator<E> implements Iterator<E> { 3169 static final EmptyIterator<Object> EMPTY_ITERATOR 3170 = new EmptyIterator<>(); 3171 3172 public boolean hasNext() { return false; } 3173 public E next() { throw new NoSuchElementException(); } 3174 public void remove() { throw new IllegalStateException(); } 3175 } 3176 3177 /** 3178 * Returns a list iterator that has no elements. More precisely, 3179 * 3180 * <ul compact> 3181 * 3182 * <li>{@link Iterator#hasNext hasNext} and {@link 3183 * ListIterator#hasPrevious hasPrevious} always return {@code 3184 * false}. 3185 * 3186 * <li>{@link Iterator#next next} and {@link ListIterator#previous 3187 * previous} always throw {@link NoSuchElementException}. 3188 * 3189 * <li>{@link Iterator#remove remove} and {@link ListIterator#set 3190 * set} always throw {@link IllegalStateException}. 3191 * 3192 * <li>{@link ListIterator#add add} always throws {@link 3193 * UnsupportedOperationException}. 3194 * 3195 * <li>{@link ListIterator#nextIndex nextIndex} always returns 3196 * {@code 0} . 3197 * 3198 * <li>{@link ListIterator#previousIndex previousIndex} always 3199 * returns {@code -1}. 3200 * 3201 * </ul> 3202 * 3203 * <p>Implementations of this method are permitted, but not 3204 * required, to return the same object from multiple invocations. 3205 * 3206 * @return an empty list iterator 3207 * @since 1.7 3208 */ 3209 @SuppressWarnings("unchecked") 3210 public static <T> ListIterator<T> emptyListIterator() { 3211 return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR; 3212 } 3213 3214 private static class EmptyListIterator<E> 3215 extends EmptyIterator<E> 3216 implements ListIterator<E> 3217 { 3218 static final EmptyListIterator<Object> EMPTY_ITERATOR 3219 = new EmptyListIterator<>(); 3220 3221 public boolean hasPrevious() { return false; } 3222 public E previous() { throw new NoSuchElementException(); } 3223 public int nextIndex() { return 0; } 3224 public int previousIndex() { return -1; } 3225 public void set(E e) { throw new IllegalStateException(); } 3226 public void add(E e) { throw new UnsupportedOperationException(); } 3227 } 3228 3229 /** 3230 * Returns an enumeration that has no elements. More precisely, 3231 * 3232 * <ul compact> 3233 * 3234 * <li>{@link Enumeration#hasMoreElements hasMoreElements} always 3235 * returns {@code false}. 3236 * 3237 * <li> {@link Enumeration#nextElement nextElement} always throws 3238 * {@link NoSuchElementException}. 3239 * 3240 * </ul> 3241 * 3242 * <p>Implementations of this method are permitted, but not 3243 * required, to return the same object from multiple invocations. 3244 * 3245 * @return an empty enumeration 3246 * @since 1.7 3247 */ 3248 @SuppressWarnings("unchecked") 3249 public static <T> Enumeration<T> emptyEnumeration() { 3250 return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION; 3251 } 3252 3253 private static class EmptyEnumeration<E> implements Enumeration<E> { 3254 static final EmptyEnumeration<Object> EMPTY_ENUMERATION 3255 = new EmptyEnumeration<>(); 3256 3257 public boolean hasMoreElements() { return false; } 3258 public E nextElement() { throw new NoSuchElementException(); } 3259 } 3260 3261 /** 3262 * The empty set (immutable). This set is serializable. 3263 * 3264 * @see #emptySet() 3265 */ 3266 @SuppressWarnings("rawtypes") 3267 public static final Set EMPTY_SET = new EmptySet<>(); 3268 3269 /** 3270 * Returns the empty set (immutable). This set is serializable. 3271 * Unlike the like-named field, this method is parameterized. 3272 * 3273 * <p>This example illustrates the type-safe way to obtain an empty set: 3274 * <pre> 3275 * Set<String> s = Collections.emptySet(); 3276 * </pre> 3277 * Implementation note: Implementations of this method need not 3278 * create a separate <tt>Set</tt> object for each call. Using this 3279 * method is likely to have comparable cost to using the like-named 3280 * field. (Unlike this method, the field does not provide type safety.) 3281 * 3282 * @see #EMPTY_SET 3283 * @since 1.5 3284 */ 3285 @SuppressWarnings("unchecked") 3286 public static final <T> Set<T> emptySet() { 3287 return (Set<T>) EMPTY_SET; 3288 } 3289 3290 /** 3291 * @serial include 3292 */ 3293 private static class EmptySet<E> 3294 extends AbstractSet<E> 3295 implements Serializable 3296 { 3297 private static final long serialVersionUID = 1582296315990362920L; 3298 3299 public Iterator<E> iterator() { return emptyIterator(); } 3300 3301 public int size() {return 0;} 3302 public boolean isEmpty() {return true;} 3303 3304 public boolean contains(Object obj) {return false;} 3305 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 3306 3307 public Object[] toArray() { return new Object[0]; } 3308 3309 public <T> T[] toArray(T[] a) { 3310 if (a.length > 0) 3311 a[0] = null; 3312 return a; 3313 } 3314 3315 // Preserves singleton property 3316 private Object readResolve() { 3317 return EMPTY_SET; 3318 } 3319 } 3320 3321 /** 3322 * Returns the empty sorted set (immutable). This set is serializable. 3323 * 3324 * <p>This example illustrates the type-safe way to obtain an empty sorted 3325 * set: 3326 * <pre> 3327 * SortedSet<String> s = Collections.emptySortedSet(); 3328 * </pre> 3329 * Implementation note: Implementations of this method need not 3330 * create a separate <tt>SortedSet</tt> object for each call. 3331 * 3332 * @since 1.8 3333 */ 3334 @SuppressWarnings("unchecked") 3335 public static final <E> SortedSet<E> emptySortedSet() { 3336 return (SortedSet<E>) new EmptySortedSet<>(); 3337 } 3338 3339 /** 3340 * @serial include 3341 */ 3342 private static class EmptySortedSet<E> 3343 extends AbstractSet<E> 3344 implements SortedSet<E>, Serializable 3345 { 3346 private static final long serialVersionUID = 6316515401502265487L; 3347 public Iterator<E> iterator() { return emptyIterator(); } 3348 public int size() {return 0;} 3349 public boolean isEmpty() {return true;} 3350 public boolean contains(Object obj) {return false;} 3351 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 3352 public Object[] toArray() { return new Object[0]; } 3353 3354 public <E> E[] toArray(E[] a) { 3355 if (a.length > 0) 3356 a[0] = null; 3357 return a; 3358 } 3359 3360 // Preserves singleton property 3361 private Object readResolve() { 3362 return new EmptySortedSet<>(); 3363 } 3364 3365 @Override 3366 public Comparator<? super E> comparator() { 3367 return null; 3368 } 3369 3370 @Override 3371 @SuppressWarnings("unchecked") 3372 public SortedSet<E> subSet(Object fromElement, Object toElement) { 3373 Objects.requireNonNull(fromElement); 3374 Objects.requireNonNull(toElement); 3375 3376 if (!(fromElement instanceof Comparable) || 3377 !(toElement instanceof Comparable)) 3378 { 3379 throw new ClassCastException(); 3380 } 3381 3382 if ((((Comparable)fromElement).compareTo(toElement) >= 0) || 3383 (((Comparable)toElement).compareTo(fromElement) < 0)) 3384 { 3385 throw new IllegalArgumentException(); 3386 } 3387 3388 return emptySortedSet(); 3389 } 3390 3391 @Override 3392 public SortedSet<E> headSet(Object toElement) { 3393 Objects.requireNonNull(toElement); 3394 3395 if (!(toElement instanceof Comparable)) { 3396 throw new ClassCastException(); 3397 } 3398 3399 return emptySortedSet(); 3400 } 3401 3402 @Override 3403 public SortedSet<E> tailSet(Object fromElement) { 3404 Objects.requireNonNull(fromElement); 3405 3406 if (!(fromElement instanceof Comparable)) { 3407 throw new ClassCastException(); 3408 } 3409 3410 return emptySortedSet(); 3411 } 3412 3413 @Override 3414 public E first() { 3415 throw new NoSuchElementException(); 3416 } 3417 3418 @Override 3419 public E last() { 3420 throw new NoSuchElementException(); 3421 } 3422 } 3423 3424 /** 3425 * The empty list (immutable). This list is serializable. 3426 * 3427 * @see #emptyList() 3428 */ 3429 @SuppressWarnings("rawtypes") 3430 public static final List EMPTY_LIST = new EmptyList<>(); 3431 3432 /** 3433 * Returns the empty list (immutable). This list is serializable. 3434 * 3435 * <p>This example illustrates the type-safe way to obtain an empty list: 3436 * <pre> 3437 * List<String> s = Collections.emptyList(); 3438 * </pre> 3439 * Implementation note: Implementations of this method need not 3440 * create a separate <tt>List</tt> object for each call. Using this 3441 * method is likely to have comparable cost to using the like-named 3442 * field. (Unlike this method, the field does not provide type safety.) 3443 * 3444 * @see #EMPTY_LIST 3445 * @since 1.5 3446 */ 3447 @SuppressWarnings("unchecked") 3448 public static final <T> List<T> emptyList() { 3449 return (List<T>) EMPTY_LIST; 3450 } 3451 3452 /** 3453 * @serial include 3454 */ 3455 private static class EmptyList<E> 3456 extends AbstractList<E> 3457 implements RandomAccess, Serializable { 3458 private static final long serialVersionUID = 8842843931221139166L; 3459 3460 public Iterator<E> iterator() { 3461 return emptyIterator(); 3462 } 3463 public ListIterator<E> listIterator() { 3464 return emptyListIterator(); 3465 } 3466 3467 public int size() {return 0;} 3468 public boolean isEmpty() {return true;} 3469 3470 public boolean contains(Object obj) {return false;} 3471 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 3472 3473 public Object[] toArray() { return new Object[0]; } 3474 3475 public <T> T[] toArray(T[] a) { 3476 if (a.length > 0) 3477 a[0] = null; 3478 return a; 3479 } 3480 3481 public E get(int index) { 3482 throw new IndexOutOfBoundsException("Index: "+index); 3483 } 3484 3485 public boolean equals(Object o) { 3486 return (o instanceof List) && ((List<?>)o).isEmpty(); 3487 } 3488 3489 public int hashCode() { return 1; } 3490 3491 // Preserves singleton property 3492 private Object readResolve() { 3493 return EMPTY_LIST; 3494 } 3495 } 3496 3497 /** 3498 * The empty map (immutable). This map is serializable. 3499 * 3500 * @see #emptyMap() 3501 * @since 1.3 3502 */ 3503 @SuppressWarnings("rawtypes") 3504 public static final Map EMPTY_MAP = new EmptyMap<>(); 3505 3506 /** 3507 * Returns the empty map (immutable). This map is serializable. 3508 * 3509 * <p>This example illustrates the type-safe way to obtain an empty set: 3510 * <pre> 3511 * Map<String, Date> s = Collections.emptyMap(); 3512 * </pre> 3513 * Implementation note: Implementations of this method need not 3514 * create a separate <tt>Map</tt> object for each call. Using this 3515 * method is likely to have comparable cost to using the like-named 3516 * field. (Unlike this method, the field does not provide type safety.) 3517 * 3518 * @see #EMPTY_MAP 3519 * @since 1.5 3520 */ 3521 @SuppressWarnings("unchecked") 3522 public static final <K,V> Map<K,V> emptyMap() { 3523 return (Map<K,V>) EMPTY_MAP; 3524 } 3525 3526 /** 3527 * @serial include 3528 */ 3529 private static class EmptyMap<K,V> 3530 extends AbstractMap<K,V> 3531 implements Serializable 3532 { 3533 private static final long serialVersionUID = 6428348081105594320L; 3534 3535 public int size() {return 0;} 3536 public boolean isEmpty() {return true;} 3537 public boolean containsKey(Object key) {return false;} 3538 public boolean containsValue(Object value) {return false;} 3539 public V get(Object key) {return null;} 3540 public Set<K> keySet() {return emptySet();} 3541 public Collection<V> values() {return emptySet();} 3542 public Set<Map.Entry<K,V>> entrySet() {return emptySet();} 3543 3544 public boolean equals(Object o) { 3545 return (o instanceof Map) && ((Map<?,?>)o).isEmpty(); 3546 } 3547 3548 public int hashCode() {return 0;} 3549 3550 // Preserves singleton property 3551 private Object readResolve() { 3552 return EMPTY_MAP; 3553 } 3554 } 3555 3556 // Singleton collections 3557 3558 /** 3559 * Returns an immutable set containing only the specified object. 3560 * The returned set is serializable. 3561 * 3562 * @param o the sole object to be stored in the returned set. 3563 * @return an immutable set containing only the specified object. 3564 */ 3565 public static <T> Set<T> singleton(T o) { 3566 return new SingletonSet<>(o); 3567 } 3568 3569 static <E> Iterator<E> singletonIterator(final E e) { 3570 return new Iterator<E>() { 3571 private boolean hasNext = true; 3572 public boolean hasNext() { 3573 return hasNext; 3574 } 3575 public E next() { 3576 if (hasNext) { 3577 hasNext = false; 3578 return e; 3579 } 3580 throw new NoSuchElementException(); 3581 } 3582 public void remove() { 3583 throw new UnsupportedOperationException(); 3584 } 3585 }; 3586 } 3587 3588 /** 3589 * @serial include 3590 */ 3591 private static class SingletonSet<E> 3592 extends AbstractSet<E> 3593 implements Serializable 3594 { 3595 private static final long serialVersionUID = 3193687207550431679L; 3596 3597 private final E element; 3598 3599 SingletonSet(E e) {element = e;} 3600 3601 public Iterator<E> iterator() { 3602 return singletonIterator(element); 3603 } 3604 3605 public int size() {return 1;} 3606 3607 public boolean contains(Object o) {return eq(o, element);} 3608 } 3609 3610 /** 3611 * Returns an immutable list containing only the specified object. 3612 * The returned list is serializable. 3613 * 3614 * @param o the sole object to be stored in the returned list. 3615 * @return an immutable list containing only the specified object. 3616 * @since 1.3 3617 */ 3618 public static <T> List<T> singletonList(T o) { 3619 return new SingletonList<>(o); 3620 } 3621 3622 /** 3623 * @serial include 3624 */ 3625 private static class SingletonList<E> 3626 extends AbstractList<E> 3627 implements RandomAccess, Serializable { 3628 3629 private static final long serialVersionUID = 3093736618740652951L; 3630 3631 private final E element; 3632 3633 SingletonList(E obj) {element = obj;} 3634 3635 public Iterator<E> iterator() { 3636 return singletonIterator(element); 3637 } 3638 3639 public int size() {return 1;} 3640 3641 public boolean contains(Object obj) {return eq(obj, element);} 3642 3643 public E get(int index) { 3644 if (index != 0) 3645 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); 3646 return element; 3647 } 3648 } 3649 3650 /** 3651 * Returns an immutable map, mapping only the specified key to the 3652 * specified value. The returned map is serializable. 3653 * 3654 * @param key the sole key to be stored in the returned map. 3655 * @param value the value to which the returned map maps <tt>key</tt>. 3656 * @return an immutable map containing only the specified key-value 3657 * mapping. 3658 * @since 1.3 3659 */ 3660 public static <K,V> Map<K,V> singletonMap(K key, V value) { 3661 return new SingletonMap<>(key, value); 3662 } 3663 3664 /** 3665 * @serial include 3666 */ 3667 private static class SingletonMap<K,V> 3668 extends AbstractMap<K,V> 3669 implements Serializable { 3670 private static final long serialVersionUID = -6979724477215052911L; 3671 3672 private final K k; 3673 private final V v; 3674 3675 SingletonMap(K key, V value) { 3676 k = key; 3677 v = value; 3678 } 3679 3680 public int size() {return 1;} 3681 3682 public boolean isEmpty() {return false;} 3683 3684 public boolean containsKey(Object key) {return eq(key, k);} 3685 3686 public boolean containsValue(Object value) {return eq(value, v);} 3687 3688 public V get(Object key) {return (eq(key, k) ? v : null);} 3689 3690 private transient Set<K> keySet = null; 3691 private transient Set<Map.Entry<K,V>> entrySet = null; 3692 private transient Collection<V> values = null; 3693 3694 public Set<K> keySet() { 3695 if (keySet==null) 3696 keySet = singleton(k); 3697 return keySet; 3698 } 3699 3700 public Set<Map.Entry<K,V>> entrySet() { 3701 if (entrySet==null) 3702 entrySet = Collections.<Map.Entry<K,V>>singleton( 3703 new SimpleImmutableEntry<>(k, v)); 3704 return entrySet; 3705 } 3706 3707 public Collection<V> values() { 3708 if (values==null) 3709 values = singleton(v); 3710 return values; 3711 } 3712 3713 } 3714 3715 // Miscellaneous 3716 3717 /** 3718 * Returns an immutable list consisting of <tt>n</tt> copies of the 3719 * specified object. The newly allocated data object is tiny (it contains 3720 * a single reference to the data object). This method is useful in 3721 * combination with the <tt>List.addAll</tt> method to grow lists. 3722 * The returned list is serializable. 3723 * 3724 * @param n the number of elements in the returned list. 3725 * @param o the element to appear repeatedly in the returned list. 3726 * @return an immutable list consisting of <tt>n</tt> copies of the 3727 * specified object. 3728 * @throws IllegalArgumentException if {@code n < 0} 3729 * @see List#addAll(Collection) 3730 * @see List#addAll(int, Collection) 3731 */ 3732 public static <T> List<T> nCopies(int n, T o) { 3733 if (n < 0) 3734 throw new IllegalArgumentException("List length = " + n); 3735 return new CopiesList<>(n, o); 3736 } 3737 3738 /** 3739 * @serial include 3740 */ 3741 private static class CopiesList<E> 3742 extends AbstractList<E> 3743 implements RandomAccess, Serializable 3744 { 3745 private static final long serialVersionUID = 2739099268398711800L; 3746 3747 final int n; 3748 final E element; 3749 3750 CopiesList(int n, E e) { 3751 assert n >= 0; 3752 this.n = n; 3753 element = e; 3754 } 3755 3756 public int size() { 3757 return n; 3758 } 3759 3760 public boolean contains(Object obj) { 3761 return n != 0 && eq(obj, element); 3762 } 3763 3764 public int indexOf(Object o) { 3765 return contains(o) ? 0 : -1; 3766 } 3767 3768 public int lastIndexOf(Object o) { 3769 return contains(o) ? n - 1 : -1; 3770 } 3771 3772 public E get(int index) { 3773 if (index < 0 || index >= n) 3774 throw new IndexOutOfBoundsException("Index: "+index+ 3775 ", Size: "+n); 3776 return element; 3777 } 3778 3779 public Object[] toArray() { 3780 final Object[] a = new Object[n]; 3781 if (element != null) 3782 Arrays.fill(a, 0, n, element); 3783 return a; 3784 } 3785 3786 @SuppressWarnings("unchecked") 3787 public <T> T[] toArray(T[] a) { 3788 final int n = this.n; 3789 if (a.length < n) { 3790 a = (T[])java.lang.reflect.Array 3791 .newInstance(a.getClass().getComponentType(), n); 3792 if (element != null) 3793 Arrays.fill(a, 0, n, element); 3794 } else { 3795 Arrays.fill(a, 0, n, element); 3796 if (a.length > n) 3797 a[n] = null; 3798 } 3799 return a; 3800 } 3801 3802 public List<E> subList(int fromIndex, int toIndex) { 3803 if (fromIndex < 0) 3804 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 3805 if (toIndex > n) 3806 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 3807 if (fromIndex > toIndex) 3808 throw new IllegalArgumentException("fromIndex(" + fromIndex + 3809 ") > toIndex(" + toIndex + ")"); 3810 return new CopiesList<>(toIndex - fromIndex, element); 3811 } 3812 } 3813 3814 /** 3815 * Returns a comparator that imposes the reverse of the <em>natural 3816 * ordering</em> on a collection of objects that implement the 3817 * {@code Comparable} interface. (The natural ordering is the ordering 3818 * imposed by the objects' own {@code compareTo} method.) This enables a 3819 * simple idiom for sorting (or maintaining) collections (or arrays) of 3820 * objects that implement the {@code Comparable} interface in 3821 * reverse-natural-order. For example, suppose {@code a} is an array of 3822 * strings. Then: <pre> 3823 * Arrays.sort(a, Collections.reverseOrder()); 3824 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p> 3825 * 3826 * The returned comparator is serializable. 3827 * 3828 * @return A comparator that imposes the reverse of the <i>natural 3829 * ordering</i> on a collection of objects that implement 3830 * the <tt>Comparable</tt> interface. 3831 * @see Comparable 3832 */ 3833 @SuppressWarnings("unchecked") 3834 public static <T> Comparator<T> reverseOrder() { 3835 return (Comparator<T>) ReverseComparator.REVERSE_ORDER; 3836 } 3837 3838 /** 3839 * @serial include 3840 */ 3841 private static class ReverseComparator 3842 implements Comparator<Comparable<Object>>, Serializable { 3843 3844 private static final long serialVersionUID = 7207038068494060240L; 3845 3846 static final ReverseComparator REVERSE_ORDER 3847 = new ReverseComparator(); 3848 3849 public int compare(Comparable<Object> c1, Comparable<Object> c2) { 3850 return c2.compareTo(c1); 3851 } 3852 3853 private Object readResolve() { return Collections.reverseOrder(); } 3854 } 3855 3856 /** 3857 * Returns a comparator that imposes the reverse ordering of the specified 3858 * comparator. If the specified comparator is {@code null}, this method is 3859 * equivalent to {@link #reverseOrder()} (in other words, it returns a 3860 * comparator that imposes the reverse of the <em>natural ordering</em> on 3861 * a collection of objects that implement the Comparable interface). 3862 * 3863 * <p>The returned comparator is serializable (assuming the specified 3864 * comparator is also serializable or {@code null}). 3865 * 3866 * @param cmp a comparator who's ordering is to be reversed by the returned 3867 * comparator or {@code null} 3868 * @return A comparator that imposes the reverse ordering of the 3869 * specified comparator. 3870 * @since 1.5 3871 */ 3872 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) { 3873 if (cmp == null) 3874 return reverseOrder(); 3875 3876 if (cmp instanceof ReverseComparator2) 3877 return ((ReverseComparator2<T>)cmp).cmp; 3878 3879 return new ReverseComparator2<>(cmp); 3880 } 3881 3882 /** 3883 * @serial include 3884 */ 3885 private static class ReverseComparator2<T> implements Comparator<T>, 3886 Serializable 3887 { 3888 private static final long serialVersionUID = 4374092139857L; 3889 3890 /** 3891 * The comparator specified in the static factory. This will never 3892 * be null, as the static factory returns a ReverseComparator 3893 * instance if its argument is null. 3894 * 3895 * @serial 3896 */ 3897 final Comparator<T> cmp; 3898 3899 ReverseComparator2(Comparator<T> cmp) { 3900 assert cmp != null; 3901 this.cmp = cmp; 3902 } 3903 3904 public int compare(T t1, T t2) { 3905 return cmp.compare(t2, t1); 3906 } 3907 3908 public boolean equals(Object o) { 3909 return (o == this) || 3910 (o instanceof ReverseComparator2 && 3911 cmp.equals(((ReverseComparator2)o).cmp)); 3912 } 3913 3914 public int hashCode() { 3915 return cmp.hashCode() ^ Integer.MIN_VALUE; 3916 } 3917 } 3918 3919 /** 3920 * Returns an enumeration over the specified collection. This provides 3921 * interoperability with legacy APIs that require an enumeration 3922 * as input. 3923 * 3924 * @param c the collection for which an enumeration is to be returned. 3925 * @return an enumeration over the specified collection. 3926 * @see Enumeration 3927 */ 3928 public static <T> Enumeration<T> enumeration(final Collection<T> c) { 3929 return new Enumeration<T>() { 3930 private final Iterator<T> i = c.iterator(); 3931 3932 public boolean hasMoreElements() { 3933 return i.hasNext(); 3934 } 3935 3936 public T nextElement() { 3937 return i.next(); 3938 } 3939 }; 3940 } 3941 3942 /** 3943 * Returns an array list containing the elements returned by the 3944 * specified enumeration in the order they are returned by the 3945 * enumeration. This method provides interoperability between 3946 * legacy APIs that return enumerations and new APIs that require 3947 * collections. 3948 * 3949 * @param e enumeration providing elements for the returned 3950 * array list 3951 * @return an array list containing the elements returned 3952 * by the specified enumeration. 3953 * @since 1.4 3954 * @see Enumeration 3955 * @see ArrayList 3956 */ 3957 public static <T> ArrayList<T> list(Enumeration<T> e) { 3958 ArrayList<T> l = new ArrayList<>(); 3959 while (e.hasMoreElements()) 3960 l.add(e.nextElement()); 3961 return l; 3962 } 3963 3964 /** 3965 * Returns true if the specified arguments are equal, or both null. 3966 */ 3967 static boolean eq(Object o1, Object o2) { 3968 return o1==null ? o2==null : o1.equals(o2); 3969 } 3970 3971 /** 3972 * Returns the number of elements in the specified collection equal to the 3973 * specified object. More formally, returns the number of elements 3974 * <tt>e</tt> in the collection such that 3975 * <tt>(o == null ? e == null : o.equals(e))</tt>. 3976 * 3977 * @param c the collection in which to determine the frequency 3978 * of <tt>o</tt> 3979 * @param o the object whose frequency is to be determined 3980 * @throws NullPointerException if <tt>c</tt> is null 3981 * @since 1.5 3982 */ 3983 public static int frequency(Collection<?> c, Object o) { 3984 int result = 0; 3985 if (o == null) { 3986 for (Object e : c) 3987 if (e == null) 3988 result++; 3989 } else { 3990 for (Object e : c) 3991 if (o.equals(e)) 3992 result++; 3993 } 3994 return result; 3995 } 3996 3997 /** 3998 * Returns {@code true} if the two specified collections have no 3999 * elements in common. 4000 * 4001 * <p>Care must be exercised if this method is used on collections that 4002 * do not comply with the general contract for {@code Collection}. 4003 * Implementations may elect to iterate over either collection and test 4004 * for containment in the other collection (or to perform any equivalent 4005 * computation). If either collection uses a nonstandard equality test 4006 * (as does a {@link SortedSet} whose ordering is not <em>compatible with 4007 * equals</em>, or the key set of an {@link IdentityHashMap}), both 4008 * collections must use the same nonstandard equality test, or the 4009 * result of this method is undefined. 4010 * 4011 * <p>Care must also be exercised when using collections that have 4012 * restrictions on the elements that they may contain. Collection 4013 * implementations are allowed to throw exceptions for any operation 4014 * involving elements they deem ineligible. For absolute safety the 4015 * specified collections should contain only elements which are 4016 * eligible elements for both collections. 4017 * 4018 * <p>Note that it is permissible to pass the same collection in both 4019 * parameters, in which case the method will return {@code true} if and 4020 * only if the collection is empty. 4021 * 4022 * @param c1 a collection 4023 * @param c2 a collection 4024 * @return {@code true} if the two specified collections have no 4025 * elements in common. 4026 * @throws NullPointerException if either collection is {@code null}. 4027 * @throws NullPointerException if one collection contains a {@code null} 4028 * element and {@code null} is not an eligible element for the other collection. 4029 * (<a href="Collection.html#optional-restrictions">optional</a>) 4030 * @throws ClassCastException if one collection contains an element that is 4031 * of a type which is ineligible for the other collection. 4032 * (<a href="Collection.html#optional-restrictions">optional</a>) 4033 * @since 1.5 4034 */ 4035 public static boolean disjoint(Collection<?> c1, Collection<?> c2) { 4036 // The collection to be used for contains(). Preference is given to 4037 // the collection who's contains() has lower O() complexity. 4038 Collection<?> contains = c2; 4039 // The collection to be iterated. If the collections' contains() impl 4040 // are of different O() complexity, the collection with slower 4041 // contains() will be used for iteration. For collections who's 4042 // contains() are of the same complexity then best performance is 4043 // achieved by iterating the smaller collection. 4044 Collection<?> iterate = c1; 4045 4046 // Performance optimization cases. The heuristics: 4047 // 1. Generally iterate over c1. 4048 // 2. If c1 is a Set then iterate over c2. 4049 // 3. If either collection is empty then result is always true. 4050 // 4. Iterate over the smaller Collection. 4051 if (c1 instanceof Set) { 4052 // Use c1 for contains as a Set's contains() is expected to perform 4053 // better than O(N/2) 4054 iterate = c2; 4055 contains = c1; 4056 } else if (!(c2 instanceof Set)) { 4057 // Both are mere Collections. Iterate over smaller collection. 4058 // Example: If c1 contains 3 elements and c2 contains 50 elements and 4059 // assuming contains() requires ceiling(N/2) comparisons then 4060 // checking for all c1 elements in c2 would require 75 comparisons 4061 // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring 4062 // 100 comparisons (50 * ceiling(3/2)). 4063 int c1size = c1.size(); 4064 int c2size = c2.size(); 4065 if (c1size == 0 || c2size == 0) { 4066 // At least one collection is empty. Nothing will match. 4067 return true; 4068 } 4069 4070 if (c1size > c2size) { 4071 iterate = c2; 4072 contains = c1; 4073 } 4074 } 4075 4076 for (Object e : iterate) { 4077 if (contains.contains(e)) { 4078 // Found a common element. Collections are not disjoint. 4079 return false; 4080 } 4081 } 4082 4083 // No common elements were found. 4084 return true; 4085 } 4086 4087 /** 4088 * Adds all of the specified elements to the specified collection. 4089 * Elements to be added may be specified individually or as an array. 4090 * The behavior of this convenience method is identical to that of 4091 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely 4092 * to run significantly faster under most implementations. 4093 * 4094 * <p>When elements are specified individually, this method provides a 4095 * convenient way to add a few elements to an existing collection: 4096 * <pre> 4097 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon"); 4098 * </pre> 4099 * 4100 * @param c the collection into which <tt>elements</tt> are to be inserted 4101 * @param elements the elements to insert into <tt>c</tt> 4102 * @return <tt>true</tt> if the collection changed as a result of the call 4103 * @throws UnsupportedOperationException if <tt>c</tt> does not support 4104 * the <tt>add</tt> operation 4105 * @throws NullPointerException if <tt>elements</tt> contains one or more 4106 * null values and <tt>c</tt> does not permit null elements, or 4107 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt> 4108 * @throws IllegalArgumentException if some property of a value in 4109 * <tt>elements</tt> prevents it from being added to <tt>c</tt> 4110 * @see Collection#addAll(Collection) 4111 * @since 1.5 4112 */ 4113 @SafeVarargs 4114 public static <T> boolean addAll(Collection<? super T> c, T... elements) { 4115 boolean result = false; 4116 for (T element : elements) 4117 result |= c.add(element); 4118 return result; 4119 } 4120 4121 /** 4122 * Returns a set backed by the specified map. The resulting set displays 4123 * the same ordering, concurrency, and performance characteristics as the 4124 * backing map. In essence, this factory method provides a {@link Set} 4125 * implementation corresponding to any {@link Map} implementation. There 4126 * is no need to use this method on a {@link Map} implementation that 4127 * already has a corresponding {@link Set} implementation (such as {@link 4128 * HashMap} or {@link TreeMap}). 4129 * 4130 * <p>Each method invocation on the set returned by this method results in 4131 * exactly one method invocation on the backing map or its <tt>keySet</tt> 4132 * view, with one exception. The <tt>addAll</tt> method is implemented 4133 * as a sequence of <tt>put</tt> invocations on the backing map. 4134 * 4135 * <p>The specified map must be empty at the time this method is invoked, 4136 * and should not be accessed directly after this method returns. These 4137 * conditions are ensured if the map is created empty, passed directly 4138 * to this method, and no reference to the map is retained, as illustrated 4139 * in the following code fragment: 4140 * <pre> 4141 * Set<Object> weakHashSet = Collections.newSetFromMap( 4142 * new WeakHashMap<Object, Boolean>()); 4143 * </pre> 4144 * 4145 * @param map the backing map 4146 * @return the set backed by the map 4147 * @throws IllegalArgumentException if <tt>map</tt> is not empty 4148 * @since 1.6 4149 */ 4150 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 4151 return new SetFromMap<>(map); 4152 } 4153 4154 /** 4155 * @serial include 4156 */ 4157 private static class SetFromMap<E> extends AbstractSet<E> 4158 implements Set<E>, Serializable 4159 { 4160 private final Map<E, Boolean> m; // The backing map 4161 private transient Set<E> s; // Its keySet 4162 4163 SetFromMap(Map<E, Boolean> map) { 4164 if (!map.isEmpty()) 4165 throw new IllegalArgumentException("Map is non-empty"); 4166 m = map; 4167 s = map.keySet(); 4168 } 4169 4170 public void clear() { m.clear(); } 4171 public int size() { return m.size(); } 4172 public boolean isEmpty() { return m.isEmpty(); } 4173 public boolean contains(Object o) { return m.containsKey(o); } 4174 public boolean remove(Object o) { return m.remove(o) != null; } 4175 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } 4176 public Iterator<E> iterator() { return s.iterator(); } 4177 public Object[] toArray() { return s.toArray(); } 4178 public <T> T[] toArray(T[] a) { return s.toArray(a); } 4179 public String toString() { return s.toString(); } 4180 public int hashCode() { return s.hashCode(); } 4181 public boolean equals(Object o) { return o == this || s.equals(o); } 4182 public boolean containsAll(Collection<?> c) {return s.containsAll(c);} 4183 public boolean removeAll(Collection<?> c) {return s.removeAll(c);} 4184 public boolean retainAll(Collection<?> c) {return s.retainAll(c);} 4185 // addAll is the only inherited implementation 4186 4187 private static final long serialVersionUID = 2454657854757543876L; 4188 4189 private void readObject(java.io.ObjectInputStream stream) 4190 throws IOException, ClassNotFoundException 4191 { 4192 stream.defaultReadObject(); 4193 s = m.keySet(); 4194 } 4195 } 4196 4197 /** 4198 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo) 4199 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>, 4200 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This 4201 * view can be useful when you would like to use a method 4202 * requiring a <tt>Queue</tt> but you need Lifo ordering. 4203 * 4204 * <p>Each method invocation on the queue returned by this method 4205 * results in exactly one method invocation on the backing deque, with 4206 * one exception. The {@link Queue#addAll addAll} method is 4207 * implemented as a sequence of {@link Deque#addFirst addFirst} 4208 * invocations on the backing deque. 4209 * 4210 * @param deque the deque 4211 * @return the queue 4212 * @since 1.6 4213 */ 4214 public static <T> Queue<T> asLifoQueue(Deque<T> deque) { 4215 return new AsLIFOQueue<>(deque); 4216 } 4217 4218 /** 4219 * @serial include 4220 */ 4221 static class AsLIFOQueue<E> extends AbstractQueue<E> 4222 implements Queue<E>, Serializable { 4223 private static final long serialVersionUID = 1802017725587941708L; 4224 private final Deque<E> q; 4225 AsLIFOQueue(Deque<E> q) { this.q = q; } 4226 public boolean add(E e) { q.addFirst(e); return true; } 4227 public boolean offer(E e) { return q.offerFirst(e); } 4228 public E poll() { return q.pollFirst(); } 4229 public E remove() { return q.removeFirst(); } 4230 public E peek() { return q.peekFirst(); } 4231 public E element() { return q.getFirst(); } 4232 public void clear() { q.clear(); } 4233 public int size() { return q.size(); } 4234 public boolean isEmpty() { return q.isEmpty(); } 4235 public boolean contains(Object o) { return q.contains(o); } 4236 public boolean remove(Object o) { return q.remove(o); } 4237 public Iterator<E> iterator() { return q.iterator(); } 4238 public Object[] toArray() { return q.toArray(); } 4239 public <T> T[] toArray(T[] a) { return q.toArray(a); } 4240 public String toString() { return q.toString(); } 4241 public boolean containsAll(Collection<?> c) {return q.containsAll(c);} 4242 public boolean removeAll(Collection<?> c) {return q.removeAll(c);} 4243 public boolean retainAll(Collection<?> c) {return q.retainAll(c);} 4244 // We use inherited addAll; forwarding addAll would be wrong 4245 } 4246 }