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