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