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