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