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