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