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