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 <tt>source.subList(i, i+target.size()).equals(target)</tt>, 929 * or -1 if there is no such index. (Returns -1 if 930 * <tt>target.size() > source.size()</tt>.) 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 <tt>source.subList(i, i+target.size()).equals(target)</tt>, 982 * or -1 if there is no such index. (Returns -1 if 983 * <tt>target.size() > source.size()</tt>.) 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 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in 1222 * an <tt>UnsupportedOperationException</tt>.<p> 1223 * 1224 * The returned navigable set will be serializable if the specified sorted set 1225 * 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 * @serial include 1238 */ 1239 static class UnmodifiableNavigableSet<E> 1240 extends UnmodifiableSortedSet<E> 1241 implements NavigableSet<E>, Serializable { 1242 1243 private static final long serialVersionUID = -6027448201786391929L; 1244 1245 private final NavigableSet<E> ns; 1246 1247 UnmodifiableNavigableSet(NavigableSet<E> s) {super(s); ns = s;} 1248 1249 @Override public E lower(E e) { return ns.lower(e); } 1250 @Override public E floor(E e) { return ns.floor(e); } 1251 @Override public E ceiling(E e) { return ns.ceiling(e); } 1252 @Override public E higher(E e) { return ns.higher(e); } 1253 @Override public E pollFirst() { throw new UnsupportedOperationException(); } 1254 @Override public E pollLast() { throw new UnsupportedOperationException(); } 1255 @Override 1256 public NavigableSet<E> descendingSet() { 1257 return new UnmodifiableNavigableSet<>(ns.descendingSet()); 1258 } 1259 1260 @Override 1261 public Iterator<E> descendingIterator() { 1262 return descendingSet().iterator(); 1263 } 1264 1265 @Override 1266 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 1267 return new UnmodifiableNavigableSet<>(ns.subSet(fromElement, fromInclusive, toElement, toInclusive)); 1268 } 1269 1270 @Override 1271 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 1272 return new UnmodifiableNavigableSet<>(ns.headSet(toElement, inclusive)); 1273 } 1274 1275 @Override 1276 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 1277 return new UnmodifiableNavigableSet<>(ns.tailSet(fromElement, inclusive)); 1278 } 1279 } 1280 1281 /** 1282 * Returns an unmodifiable view of the specified list. This method allows 1283 * modules to provide users with "read-only" access to internal 1284 * lists. Query operations on the returned list "read through" to the 1285 * specified list, and attempts to modify the returned list, whether 1286 * direct or via its iterator, result in an 1287 * <tt>UnsupportedOperationException</tt>.<p> 1288 * 1289 * The returned list will be serializable if the specified list 1290 * is serializable. Similarly, the returned list will implement 1291 * {@link RandomAccess} if the specified list does. 1292 * 1293 * @param list the list for which an unmodifiable view is to be returned. 1294 * @return an unmodifiable view of the specified list. 1295 */ 1296 public static <T> List<T> unmodifiableList(List<? extends T> list) { 1297 return (list instanceof RandomAccess ? 1298 new UnmodifiableRandomAccessList<>(list) : 1299 new UnmodifiableList<>(list)); 1300 } 1301 1302 /** 1303 * @serial include 1304 */ 1305 static class UnmodifiableList<E> extends UnmodifiableCollection<E> 1306 implements List<E> { 1307 private static final long serialVersionUID = -283967356065247728L; 1308 1309 final List<? extends E> list; 1310 1311 UnmodifiableList(List<? extends E> list) { 1312 super(list); 1313 this.list = list; 1314 } 1315 1316 public boolean equals(Object o) {return o == this || list.equals(o);} 1317 public int hashCode() {return list.hashCode();} 1318 1319 public E get(int index) {return list.get(index);} 1320 public E set(int index, E element) { 1321 throw new UnsupportedOperationException(); 1322 } 1323 public void add(int index, E element) { 1324 throw new UnsupportedOperationException(); 1325 } 1326 public E remove(int index) { 1327 throw new UnsupportedOperationException(); 1328 } 1329 public int indexOf(Object o) {return list.indexOf(o);} 1330 public int lastIndexOf(Object o) {return list.lastIndexOf(o);} 1331 public boolean addAll(int index, Collection<? extends E> c) { 1332 throw new UnsupportedOperationException(); 1333 } 1334 1335 @Override 1336 public void replaceAll(UnaryOperator<E> operator) { 1337 throw new UnsupportedOperationException(); 1338 } 1339 @Override 1340 public void sort(Comparator<? super E> c) { 1341 throw new UnsupportedOperationException(); 1342 } 1343 1344 public ListIterator<E> listIterator() {return listIterator(0);} 1345 1346 public ListIterator<E> listIterator(final int index) { 1347 return new ListIterator<E>() { 1348 private final ListIterator<? extends E> i 1349 = list.listIterator(index); 1350 1351 public boolean hasNext() {return i.hasNext();} 1352 public E next() {return i.next();} 1353 public boolean hasPrevious() {return i.hasPrevious();} 1354 public E previous() {return i.previous();} 1355 public int nextIndex() {return i.nextIndex();} 1356 public int previousIndex() {return i.previousIndex();} 1357 1358 public void remove() { 1359 throw new UnsupportedOperationException(); 1360 } 1361 public void set(E e) { 1362 throw new UnsupportedOperationException(); 1363 } 1364 public void add(E e) { 1365 throw new UnsupportedOperationException(); 1366 } 1367 1368 @Override 1369 public void forEachRemaining(Consumer<? super E> action) { 1370 i.forEachRemaining(action); 1371 } 1372 }; 1373 } 1374 1375 public List<E> subList(int fromIndex, int toIndex) { 1376 return new UnmodifiableList<>(list.subList(fromIndex, toIndex)); 1377 } 1378 1379 /** 1380 * UnmodifiableRandomAccessList instances are serialized as 1381 * UnmodifiableList instances to allow them to be deserialized 1382 * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList). 1383 * This method inverts the transformation. As a beneficial 1384 * side-effect, it also grafts the RandomAccess marker onto 1385 * UnmodifiableList instances that were serialized in pre-1.4 JREs. 1386 * 1387 * Note: Unfortunately, UnmodifiableRandomAccessList instances 1388 * serialized in 1.4.1 and deserialized in 1.4 will become 1389 * UnmodifiableList instances, as this method was missing in 1.4. 1390 */ 1391 private Object readResolve() { 1392 return (list instanceof RandomAccess 1393 ? new UnmodifiableRandomAccessList<>(list) 1394 : this); 1395 } 1396 } 1397 1398 /** 1399 * @serial include 1400 */ 1401 static class UnmodifiableRandomAccessList<E> extends UnmodifiableList<E> 1402 implements RandomAccess 1403 { 1404 UnmodifiableRandomAccessList(List<? extends E> list) { 1405 super(list); 1406 } 1407 1408 public List<E> subList(int fromIndex, int toIndex) { 1409 return new UnmodifiableRandomAccessList<>( 1410 list.subList(fromIndex, toIndex)); 1411 } 1412 1413 private static final long serialVersionUID = -2542308836966382001L; 1414 1415 /** 1416 * Allows instances to be deserialized in pre-1.4 JREs (which do 1417 * not have UnmodifiableRandomAccessList). UnmodifiableList has 1418 * a readResolve method that inverts this transformation upon 1419 * deserialization. 1420 */ 1421 private Object writeReplace() { 1422 return new UnmodifiableList<>(list); 1423 } 1424 } 1425 1426 /** 1427 * Returns an unmodifiable view of the specified map. This method 1428 * allows modules to provide users with "read-only" access to internal 1429 * maps. Query operations on the returned map "read through" 1430 * to the specified map, and attempts to modify the returned 1431 * map, whether direct or via its collection views, result in an 1432 * <tt>UnsupportedOperationException</tt>.<p> 1433 * 1434 * The returned map will be serializable if the specified map 1435 * is serializable. 1436 * 1437 * @param m the map for which an unmodifiable view is to be returned. 1438 * @return an unmodifiable view of the specified map. 1439 */ 1440 public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m) { 1441 return new UnmodifiableMap<>(m); 1442 } 1443 1444 /** 1445 * @serial include 1446 */ 1447 private static class UnmodifiableMap<K,V> implements Map<K,V>, Serializable { 1448 private static final long serialVersionUID = -1034234728574286014L; 1449 1450 private final Map<? extends K, ? extends V> m; 1451 1452 UnmodifiableMap(Map<? extends K, ? extends V> m) { 1453 if (m==null) 1454 throw new NullPointerException(); 1455 this.m = m; 1456 } 1457 1458 public int size() {return m.size();} 1459 public boolean isEmpty() {return m.isEmpty();} 1460 public boolean containsKey(Object key) {return m.containsKey(key);} 1461 public boolean containsValue(Object val) {return m.containsValue(val);} 1462 public V get(Object key) {return m.get(key);} 1463 1464 public V put(K key, V value) { 1465 throw new UnsupportedOperationException(); 1466 } 1467 public V remove(Object key) { 1468 throw new UnsupportedOperationException(); 1469 } 1470 public void putAll(Map<? extends K, ? extends V> m) { 1471 throw new UnsupportedOperationException(); 1472 } 1473 public void clear() { 1474 throw new UnsupportedOperationException(); 1475 } 1476 1477 private transient Set<K> keySet = null; 1478 private transient Set<Map.Entry<K,V>> entrySet = null; 1479 private transient Collection<V> values = null; 1480 1481 public Set<K> keySet() { 1482 if (keySet==null) 1483 keySet = unmodifiableSet(m.keySet()); 1484 return keySet; 1485 } 1486 1487 public Set<Map.Entry<K,V>> entrySet() { 1488 if (entrySet==null) 1489 entrySet = new UnmodifiableEntrySet<>(m.entrySet()); 1490 return entrySet; 1491 } 1492 1493 public Collection<V> values() { 1494 if (values==null) 1495 values = unmodifiableCollection(m.values()); 1496 return values; 1497 } 1498 1499 public boolean equals(Object o) {return o == this || m.equals(o);} 1500 public int hashCode() {return m.hashCode();} 1501 public String toString() {return m.toString();} 1502 1503 // Override default methods in Map 1504 @Override 1505 @SuppressWarnings("unchecked") 1506 public V getOrDefault(Object k, V defaultValue) { 1507 // Safe cast as we don't change the value 1508 return ((Map<K, V>)m).getOrDefault(k, defaultValue); 1509 } 1510 1511 @Override 1512 public void forEach(BiConsumer<? super K, ? super V> action) { 1513 m.forEach(action); 1514 } 1515 1516 @Override 1517 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1518 throw new UnsupportedOperationException(); 1519 } 1520 1521 @Override 1522 public V putIfAbsent(K key, V value) { 1523 throw new UnsupportedOperationException(); 1524 } 1525 1526 @Override 1527 public boolean remove(Object key, Object value) { 1528 throw new UnsupportedOperationException(); 1529 } 1530 1531 @Override 1532 public boolean replace(K key, V oldValue, V newValue) { 1533 throw new UnsupportedOperationException(); 1534 } 1535 1536 @Override 1537 public V replace(K key, V value) { 1538 throw new UnsupportedOperationException(); 1539 } 1540 1541 @Override 1542 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 1543 throw new UnsupportedOperationException(); 1544 } 1545 1546 @Override 1547 public V computeIfPresent(K key, 1548 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1549 throw new UnsupportedOperationException(); 1550 } 1551 1552 @Override 1553 public V compute(K key, 1554 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1555 throw new UnsupportedOperationException(); 1556 } 1557 1558 @Override 1559 public V merge(K key, V value, 1560 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1561 throw new UnsupportedOperationException(); 1562 } 1563 1564 /** 1565 * We need this class in addition to UnmodifiableSet as 1566 * Map.Entries themselves permit modification of the backing Map 1567 * via their setValue operation. This class is subtle: there are 1568 * many possible attacks that must be thwarted. 1569 * 1570 * @serial include 1571 */ 1572 static class UnmodifiableEntrySet<K,V> 1573 extends UnmodifiableSet<Map.Entry<K,V>> { 1574 private static final long serialVersionUID = 7854390611657943733L; 1575 1576 @SuppressWarnings({"unchecked", "rawtypes"}) 1577 UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) { 1578 // Need to cast to raw in order to work around a limitation in the type system 1579 super((Set)s); 1580 } 1581 public Iterator<Map.Entry<K,V>> iterator() { 1582 return new Iterator<Map.Entry<K,V>>() { 1583 private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator(); 1584 1585 public boolean hasNext() { 1586 return i.hasNext(); 1587 } 1588 public Map.Entry<K,V> next() { 1589 return new UnmodifiableEntry<>(i.next()); 1590 } 1591 public void remove() { 1592 throw new UnsupportedOperationException(); 1593 } 1594 }; 1595 } 1596 1597 @SuppressWarnings("unchecked") 1598 public Object[] toArray() { 1599 Object[] a = c.toArray(); 1600 for (int i=0; i<a.length; i++) 1601 a[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)a[i]); 1602 return a; 1603 } 1604 1605 @SuppressWarnings("unchecked") 1606 public <T> T[] toArray(T[] a) { 1607 // We don't pass a to c.toArray, to avoid window of 1608 // vulnerability wherein an unscrupulous multithreaded client 1609 // could get his hands on raw (unwrapped) Entries from c. 1610 Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); 1611 1612 for (int i=0; i<arr.length; i++) 1613 arr[i] = new UnmodifiableEntry<>((Map.Entry<? extends K, ? extends V>)arr[i]); 1614 1615 if (arr.length > a.length) 1616 return (T[])arr; 1617 1618 System.arraycopy(arr, 0, a, 0, arr.length); 1619 if (a.length > arr.length) 1620 a[arr.length] = null; 1621 return a; 1622 } 1623 1624 /** 1625 * This method is overridden to protect the backing set against 1626 * an object with a nefarious equals function that senses 1627 * that the equality-candidate is Map.Entry and calls its 1628 * setValue method. 1629 */ 1630 public boolean contains(Object o) { 1631 if (!(o instanceof Map.Entry)) 1632 return false; 1633 return c.contains( 1634 new UnmodifiableEntry<>((Map.Entry<?,?>) o)); 1635 } 1636 1637 /** 1638 * The next two methods are overridden to protect against 1639 * an unscrupulous List whose contains(Object o) method senses 1640 * when o is a Map.Entry, and calls o.setValue. 1641 */ 1642 public boolean containsAll(Collection<?> coll) { 1643 for (Object e : coll) { 1644 if (!contains(e)) // Invokes safe contains() above 1645 return false; 1646 } 1647 return true; 1648 } 1649 public boolean equals(Object o) { 1650 if (o == this) 1651 return true; 1652 1653 if (!(o instanceof Set)) 1654 return false; 1655 Set<?> s = (Set<?>) o; 1656 if (s.size() != c.size()) 1657 return false; 1658 return containsAll(s); // Invokes safe containsAll() above 1659 } 1660 1661 /** 1662 * This "wrapper class" serves two purposes: it prevents 1663 * the client from modifying the backing Map, by short-circuiting 1664 * the setValue method, and it protects the backing Map against 1665 * an ill-behaved Map.Entry that attempts to modify another 1666 * Map Entry when asked to perform an equality check. 1667 */ 1668 private static class UnmodifiableEntry<K,V> implements Map.Entry<K,V> { 1669 private Map.Entry<? extends K, ? extends V> e; 1670 1671 UnmodifiableEntry(Map.Entry<? extends K, ? extends V> e) {this.e = e;} 1672 1673 public K getKey() {return e.getKey();} 1674 public V getValue() {return e.getValue();} 1675 public V setValue(V value) { 1676 throw new UnsupportedOperationException(); 1677 } 1678 public int hashCode() {return e.hashCode();} 1679 public boolean equals(Object o) { 1680 if (this == o) 1681 return true; 1682 if (!(o instanceof Map.Entry)) 1683 return false; 1684 Map.Entry<?,?> t = (Map.Entry<?,?>)o; 1685 return eq(e.getKey(), t.getKey()) && 1686 eq(e.getValue(), t.getValue()); 1687 } 1688 public String toString() {return e.toString();} 1689 } 1690 } 1691 } 1692 1693 /** 1694 * Returns an unmodifiable view of the specified sorted map. This method 1695 * allows modules to provide users with "read-only" access to internal 1696 * sorted maps. Query operations on the returned sorted map "read through" 1697 * to the specified sorted map. Attempts to modify the returned 1698 * sorted map, whether direct, via its collection views, or via its 1699 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in 1700 * an <tt>UnsupportedOperationException</tt>.<p> 1701 * 1702 * The returned sorted map will be serializable if the specified sorted map 1703 * is serializable. 1704 * 1705 * @param m the sorted map for which an unmodifiable view is to be 1706 * returned. 1707 * @return an unmodifiable view of the specified sorted map. 1708 */ 1709 public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) { 1710 return new UnmodifiableSortedMap<>(m); 1711 } 1712 1713 /** 1714 * @serial include 1715 */ 1716 static class UnmodifiableSortedMap<K,V> 1717 extends UnmodifiableMap<K,V> 1718 implements SortedMap<K,V>, Serializable { 1719 private static final long serialVersionUID = -8806743815996713206L; 1720 1721 private final SortedMap<K, ? extends V> sm; 1722 1723 UnmodifiableSortedMap(SortedMap<K, ? extends V> m) {super(m); sm = m;} 1724 1725 public Comparator<? super K> comparator() {return sm.comparator();} 1726 1727 public SortedMap<K,V> subMap(K fromKey, K toKey) { 1728 return new UnmodifiableSortedMap<>(sm.subMap(fromKey, toKey)); 1729 } 1730 public SortedMap<K,V> headMap(K toKey) { 1731 return new UnmodifiableSortedMap<>(sm.headMap(toKey)); 1732 } 1733 public SortedMap<K,V> tailMap(K fromKey) { 1734 return new UnmodifiableSortedMap<>(sm.tailMap(fromKey)); 1735 } 1736 1737 public K firstKey() {return sm.firstKey();} 1738 public K lastKey() {return sm.lastKey();} 1739 } 1740 1741 /** 1742 * Returns an unmodifiable view of the specified navigable map. This method 1743 * allows modules to provide users with "read-only" access to internal 1744 * navigable maps. Query operations on the returned navigable map "read 1745 * through" to the specified navigable map. Attempts to modify the returned 1746 * navigable map, whether direct, via its collection views, or via its 1747 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in 1748 * an <tt>UnsupportedOperationException</tt>.<p> 1749 * 1750 * The returned navigable map will be serializable if the specified 1751 * navigable map is serializable. 1752 * 1753 * @param m the navigable map for which an unmodifiable view is to be 1754 * returned 1755 * @return an unmodifiable view of the specified navigable map 1756 * @since 1.8 1757 */ 1758 public static <K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m) { 1759 return new UnmodifiableNavigableMap<>(m); 1760 } 1761 1762 /** 1763 * @serial include 1764 */ 1765 static class UnmodifiableNavigableMap<K,V> 1766 extends UnmodifiableSortedMap<K,V> 1767 implements NavigableMap<K,V>, Serializable { 1768 private static final long serialVersionUID = -4858195264774772197L; 1769 1770 private final NavigableMap<K, ? extends V> nm; 1771 1772 UnmodifiableNavigableMap(NavigableMap<K, ? extends V> m) {super(m); nm = m;} 1773 1774 @Override 1775 public Entry<K, V> lowerEntry(K key) { 1776 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.lowerEntry(key)); 1777 } 1778 1779 @Override 1780 public K lowerKey(K key) { 1781 return nm.lowerKey(key); 1782 } 1783 1784 @Override 1785 public Entry<K, V> floorEntry(K key) { 1786 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.floorEntry(key)); 1787 } 1788 1789 @Override 1790 public K floorKey(K key) { 1791 return nm.floorKey(key); 1792 } 1793 1794 @Override 1795 public Entry<K, V> ceilingEntry(K key) { 1796 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.ceilingEntry(key)); 1797 } 1798 1799 @Override 1800 public K ceilingKey(K key) { 1801 return nm.ceilingKey(key); 1802 } 1803 1804 @Override 1805 public Entry<K, V> higherEntry(K key) { 1806 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.higherEntry(key)); 1807 } 1808 1809 @Override 1810 public K higherKey(K key) { 1811 return nm.higherKey(key); 1812 } 1813 1814 @Override 1815 public Entry<K, V> firstEntry() { 1816 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.firstEntry()); 1817 } 1818 1819 @Override 1820 public Entry<K, V> lastEntry() { 1821 return new UnmodifiableEntrySet.UnmodifiableEntry(nm.lastEntry()); 1822 } 1823 1824 @Override 1825 public Entry<K, V> pollFirstEntry() { 1826 Entry<K,V> entry = (Entry<K,V>) nm.pollFirstEntry(); 1827 return (null == entry) ? null : new UnmodifiableEntrySet.UnmodifiableEntry(entry); 1828 } 1829 1830 @Override 1831 public Entry<K, V> pollLastEntry() { 1832 Entry<K,V> entry = (Entry<K,V>) nm.pollLastEntry(); 1833 return (null == entry) ? null : new UnmodifiableEntrySet.UnmodifiableEntry(entry); 1834 } 1835 1836 @Override 1837 public NavigableMap<K, V> descendingMap() { 1838 return unmodifiableNavigableMap(nm.descendingMap()); 1839 } 1840 1841 @Override 1842 public NavigableSet<K> navigableKeySet() { 1843 return unmodifiableNavigableSet(nm.navigableKeySet()); 1844 } 1845 1846 @Override 1847 public NavigableSet<K> descendingKeySet() { 1848 return unmodifiableNavigableSet(nm.descendingKeySet()); 1849 } 1850 1851 @Override 1852 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 1853 return unmodifiableNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive)); 1854 } 1855 1856 @Override 1857 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 1858 return unmodifiableNavigableMap(nm.headMap(toKey, inclusive)); 1859 } 1860 1861 @Override 1862 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 1863 return unmodifiableNavigableMap(nm.tailMap(fromKey, inclusive)); 1864 } 1865 } 1866 1867 // Synch Wrappers 1868 1869 /** 1870 * Returns a synchronized (thread-safe) collection backed by the specified 1871 * collection. In order to guarantee serial access, it is critical that 1872 * <strong>all</strong> access to the backing collection is accomplished 1873 * through the returned collection.<p> 1874 * 1875 * It is imperative that the user manually synchronize on the returned 1876 * collection when traversing it via {@link Iterator} or 1877 * {@link Spliterator}: 1878 * <pre> 1879 * Collection c = Collections.synchronizedCollection(myCollection); 1880 * ... 1881 * synchronized (c) { 1882 * Iterator i = c.iterator(); // Must be in the synchronized block 1883 * while (i.hasNext()) 1884 * foo(i.next()); 1885 * } 1886 * </pre> 1887 * Failure to follow this advice may result in non-deterministic behavior. 1888 * 1889 * <p>The returned collection does <i>not</i> pass the {@code hashCode} 1890 * and {@code equals} operations through to the backing collection, but 1891 * relies on {@code Object}'s equals and hashCode methods. This is 1892 * necessary to preserve the contracts of these operations in the case 1893 * that the backing collection is a set or a list.<p> 1894 * 1895 * The returned collection will be serializable if the specified collection 1896 * is serializable. 1897 * 1898 * @param c the collection to be "wrapped" in a synchronized collection. 1899 * @return a synchronized view of the specified collection. 1900 */ 1901 public static <T> Collection<T> synchronizedCollection(Collection<T> c) { 1902 return new SynchronizedCollection<>(c); 1903 } 1904 1905 static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) { 1906 return new SynchronizedCollection<>(c, mutex); 1907 } 1908 1909 /** 1910 * @serial include 1911 */ 1912 static class SynchronizedCollection<E> implements Collection<E>, Serializable { 1913 private static final long serialVersionUID = 3053995032091335093L; 1914 1915 final Collection<E> c; // Backing Collection 1916 final Object mutex; // Object on which to synchronize 1917 1918 SynchronizedCollection(Collection<E> c) { 1919 this.c = Objects.requireNonNull(c); 1920 mutex = this; 1921 } 1922 1923 SynchronizedCollection(Collection<E> c, Object mutex) { 1924 this.c = Objects.requireNonNull(c); 1925 this.mutex = Objects.requireNonNull(mutex); 1926 } 1927 1928 public int size() { 1929 synchronized (mutex) {return c.size();} 1930 } 1931 public boolean isEmpty() { 1932 synchronized (mutex) {return c.isEmpty();} 1933 } 1934 public boolean contains(Object o) { 1935 synchronized (mutex) {return c.contains(o);} 1936 } 1937 public Object[] toArray() { 1938 synchronized (mutex) {return c.toArray();} 1939 } 1940 public <T> T[] toArray(T[] a) { 1941 synchronized (mutex) {return c.toArray(a);} 1942 } 1943 1944 public Iterator<E> iterator() { 1945 return c.iterator(); // Must be manually synched by user! 1946 } 1947 1948 public boolean add(E e) { 1949 synchronized (mutex) {return c.add(e);} 1950 } 1951 public boolean remove(Object o) { 1952 synchronized (mutex) {return c.remove(o);} 1953 } 1954 1955 public boolean containsAll(Collection<?> coll) { 1956 synchronized (mutex) {return c.containsAll(coll);} 1957 } 1958 public boolean addAll(Collection<? extends E> coll) { 1959 synchronized (mutex) {return c.addAll(coll);} 1960 } 1961 public boolean removeAll(Collection<?> coll) { 1962 synchronized (mutex) {return c.removeAll(coll);} 1963 } 1964 public boolean retainAll(Collection<?> coll) { 1965 synchronized (mutex) {return c.retainAll(coll);} 1966 } 1967 public void clear() { 1968 synchronized (mutex) {c.clear();} 1969 } 1970 public String toString() { 1971 synchronized (mutex) {return c.toString();} 1972 } 1973 // Override default methods in Collection 1974 @Override 1975 public void forEach(Consumer<? super E> consumer) { 1976 synchronized (mutex) {c.forEach(consumer);} 1977 } 1978 @Override 1979 public boolean removeIf(Predicate<? super E> filter) { 1980 synchronized (mutex) {return c.removeIf(filter);} 1981 } 1982 @Override 1983 public Spliterator<E> spliterator() { 1984 return c.spliterator(); // Must be manually synched by user! 1985 } 1986 private void writeObject(ObjectOutputStream s) throws IOException { 1987 synchronized (mutex) {s.defaultWriteObject();} 1988 } 1989 } 1990 1991 /** 1992 * Returns a synchronized (thread-safe) set backed by the specified 1993 * set. In order to guarantee serial access, it is critical that 1994 * <strong>all</strong> access to the backing set is accomplished 1995 * through the returned set.<p> 1996 * 1997 * It is imperative that the user manually synchronize on the returned 1998 * set when iterating over it: 1999 * <pre> 2000 * Set s = Collections.synchronizedSet(new HashSet()); 2001 * ... 2002 * synchronized (s) { 2003 * Iterator i = s.iterator(); // Must be in the synchronized block 2004 * while (i.hasNext()) 2005 * foo(i.next()); 2006 * } 2007 * </pre> 2008 * Failure to follow this advice may result in non-deterministic behavior. 2009 * 2010 * <p>The returned set will be serializable if the specified set is 2011 * serializable. 2012 * 2013 * @param s the set to be "wrapped" in a synchronized set. 2014 * @return a synchronized view of the specified set. 2015 */ 2016 public static <T> Set<T> synchronizedSet(Set<T> s) { 2017 return new SynchronizedSet<>(s); 2018 } 2019 2020 static <T> Set<T> synchronizedSet(Set<T> s, Object mutex) { 2021 return new SynchronizedSet<>(s, mutex); 2022 } 2023 2024 /** 2025 * @serial include 2026 */ 2027 static class SynchronizedSet<E> 2028 extends SynchronizedCollection<E> 2029 implements Set<E> { 2030 private static final long serialVersionUID = 487447009682186044L; 2031 2032 SynchronizedSet(Set<E> s) { 2033 super(s); 2034 } 2035 SynchronizedSet(Set<E> s, Object mutex) { 2036 super(s, mutex); 2037 } 2038 2039 public boolean equals(Object o) { 2040 if (this == o) 2041 return true; 2042 synchronized (mutex) {return c.equals(o);} 2043 } 2044 public int hashCode() { 2045 synchronized (mutex) {return c.hashCode();} 2046 } 2047 } 2048 2049 /** 2050 * Returns a synchronized (thread-safe) sorted set backed by the specified 2051 * sorted set. In order to guarantee serial access, it is critical that 2052 * <strong>all</strong> access to the backing sorted set is accomplished 2053 * through the returned sorted set (or its views).<p> 2054 * 2055 * It is imperative that the user manually synchronize on the returned 2056 * sorted set when iterating over it or any of its <tt>subSet</tt>, 2057 * <tt>headSet</tt>, or <tt>tailSet</tt> views. 2058 * <pre> 2059 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet()); 2060 * ... 2061 * synchronized (s) { 2062 * Iterator i = s.iterator(); // Must be in the synchronized block 2063 * while (i.hasNext()) 2064 * foo(i.next()); 2065 * } 2066 * </pre> 2067 * or: 2068 * <pre> 2069 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet()); 2070 * SortedSet s2 = s.headSet(foo); 2071 * ... 2072 * synchronized (s) { // Note: s, not s2!!! 2073 * Iterator i = s2.iterator(); // Must be in the synchronized block 2074 * while (i.hasNext()) 2075 * foo(i.next()); 2076 * } 2077 * </pre> 2078 * Failure to follow this advice may result in non-deterministic behavior. 2079 * 2080 * <p>The returned sorted set will be serializable if the specified 2081 * sorted set is serializable. 2082 * 2083 * @param s the sorted set to be "wrapped" in a synchronized sorted set. 2084 * @return a synchronized view of the specified sorted set. 2085 */ 2086 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) { 2087 return new SynchronizedSortedSet<>(s); 2088 } 2089 2090 /** 2091 * @serial include 2092 */ 2093 static class SynchronizedSortedSet<E> 2094 extends SynchronizedSet<E> 2095 implements SortedSet<E> 2096 { 2097 private static final long serialVersionUID = 8695801310862127406L; 2098 2099 private final SortedSet<E> ss; 2100 2101 SynchronizedSortedSet(SortedSet<E> s) { 2102 super(s); 2103 ss = s; 2104 } 2105 SynchronizedSortedSet(SortedSet<E> s, Object mutex) { 2106 super(s, mutex); 2107 ss = s; 2108 } 2109 2110 public Comparator<? super E> comparator() { 2111 synchronized (mutex) {return ss.comparator();} 2112 } 2113 2114 public SortedSet<E> subSet(E fromElement, E toElement) { 2115 synchronized (mutex) { 2116 return new SynchronizedSortedSet<>( 2117 ss.subSet(fromElement, toElement), mutex); 2118 } 2119 } 2120 public SortedSet<E> headSet(E toElement) { 2121 synchronized (mutex) { 2122 return new SynchronizedSortedSet<>(ss.headSet(toElement), mutex); 2123 } 2124 } 2125 public SortedSet<E> tailSet(E fromElement) { 2126 synchronized (mutex) { 2127 return new SynchronizedSortedSet<>(ss.tailSet(fromElement),mutex); 2128 } 2129 } 2130 2131 public E first() { 2132 synchronized (mutex) {return ss.first();} 2133 } 2134 public E last() { 2135 synchronized (mutex) {return ss.last();} 2136 } 2137 } 2138 2139 /** 2140 * Returns a synchronized (thread-safe) sorted set backed by the specified 2141 * navigable set. In order to guarantee serial access, it is critical that 2142 * <strong>all</strong> access to the backing sorted set is accomplished 2143 * through the returned navigable set (or its views).<p> 2144 * 2145 * It is imperative that the user manually synchronize on the returned 2146 * navigable set when iterating over it or any of its {@code subSet}, 2147 * {@code headSet}, or {@code tailSet} views. 2148 * <pre> 2149 * SortedSet s = Collections.synchronizedNavigableSet(new TreeSet()); 2150 * ... 2151 * synchronized (s) { 2152 * Iterator i = s.iterator(); // Must be in the synchronized block 2153 * while (i.hasNext()) 2154 * foo(i.next()); 2155 * } 2156 * </pre> 2157 * or: 2158 * <pre> 2159 * SortedSet s = Collections.synchronizedNavigableSet(new TreeSet()); 2160 * SortedSet s2 = s.headSet(foo); 2161 * ... 2162 * synchronized (s) { // Note: s, not s2!!! 2163 * Iterator i = s2.iterator(); // Must be in the synchronized block 2164 * while (i.hasNext()) 2165 * foo(i.next()); 2166 * } 2167 * </pre> 2168 * Failure to follow this advice may result in non-deterministic behavior. 2169 * 2170 * <p>The returned navigable set will be serializable if the specified 2171 * navigable set is serializable. 2172 * 2173 * @param s the navigable set to be "wrapped" in a synchronized navigable 2174 * set 2175 * @return a synchronized view of the specified navigable set 2176 * @since 1.8 2177 */ 2178 public static <T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s) { 2179 return new SynchronizedNavigableSet<>(s); 2180 } 2181 2182 /** 2183 * @serial include 2184 */ 2185 static class SynchronizedNavigableSet<E> 2186 extends SynchronizedSortedSet<E> 2187 implements NavigableSet<E> 2188 { 2189 private static final long serialVersionUID = -5505529816273629798L; 2190 2191 private final NavigableSet<E> ns; 2192 2193 SynchronizedNavigableSet(NavigableSet<E> s) { 2194 super(s); 2195 ns = s; 2196 } 2197 2198 SynchronizedNavigableSet(NavigableSet<E> s, Object mutex) { 2199 super(s, mutex); 2200 ns = s; 2201 } 2202 public E lower(E e) { synchronized (mutex) {return ns.lower(e);} } 2203 public E floor(E e) { synchronized (mutex) {return ns.floor(e);} } 2204 public E ceiling(E e) { synchronized (mutex) {return ns.ceiling(e);} } 2205 public E higher(E e) { synchronized (mutex) {return ns.higher(e);} } 2206 public E pollFirst() { synchronized (mutex) {return ns.pollFirst();} } 2207 public E pollLast() { synchronized (mutex) {return ns.pollLast();} } 2208 2209 public NavigableSet<E> descendingSet() { 2210 synchronized (mutex) { 2211 return new SynchronizedNavigableSet<>(ns.descendingSet(), mutex); 2212 } 2213 } 2214 2215 public Iterator<E> descendingIterator() 2216 { synchronized (mutex) { return descendingSet().iterator(); } } 2217 2218 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 2219 synchronized (mutex) { 2220 return new SynchronizedNavigableSet<>(ns.subSet(fromElement, fromInclusive, toElement, toInclusive), mutex); 2221 } 2222 } 2223 2224 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 2225 synchronized (mutex) { 2226 return new SynchronizedNavigableSet<>(ns.headSet(toElement, inclusive), mutex); 2227 } 2228 } 2229 2230 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 2231 synchronized (mutex) { 2232 return new SynchronizedNavigableSet<>(ns.tailSet(fromElement, inclusive)); 2233 } 2234 } 2235 } 2236 2237 /** 2238 * Returns a synchronized (thread-safe) list backed by the specified 2239 * list. In order to guarantee serial access, it is critical that 2240 * <strong>all</strong> access to the backing list is accomplished 2241 * through the returned list.<p> 2242 * 2243 * It is imperative that the user manually synchronize on the returned 2244 * list when iterating over it: 2245 * <pre> 2246 * List list = Collections.synchronizedList(new ArrayList()); 2247 * ... 2248 * synchronized (list) { 2249 * Iterator i = list.iterator(); // Must be in synchronized block 2250 * while (i.hasNext()) 2251 * foo(i.next()); 2252 * } 2253 * </pre> 2254 * Failure to follow this advice may result in non-deterministic behavior. 2255 * 2256 * <p>The returned list will be serializable if the specified list is 2257 * serializable. 2258 * 2259 * @param list the list to be "wrapped" in a synchronized list. 2260 * @return a synchronized view of the specified list. 2261 */ 2262 public static <T> List<T> synchronizedList(List<T> list) { 2263 return (list instanceof RandomAccess ? 2264 new SynchronizedRandomAccessList<>(list) : 2265 new SynchronizedList<>(list)); 2266 } 2267 2268 static <T> List<T> synchronizedList(List<T> list, Object mutex) { 2269 return (list instanceof RandomAccess ? 2270 new SynchronizedRandomAccessList<>(list, mutex) : 2271 new SynchronizedList<>(list, mutex)); 2272 } 2273 2274 /** 2275 * @serial include 2276 */ 2277 static class SynchronizedList<E> 2278 extends SynchronizedCollection<E> 2279 implements List<E> { 2280 private static final long serialVersionUID = -7754090372962971524L; 2281 2282 final List<E> list; 2283 2284 SynchronizedList(List<E> list) { 2285 super(list); 2286 this.list = list; 2287 } 2288 SynchronizedList(List<E> list, Object mutex) { 2289 super(list, mutex); 2290 this.list = list; 2291 } 2292 2293 public boolean equals(Object o) { 2294 if (this == o) 2295 return true; 2296 synchronized (mutex) {return list.equals(o);} 2297 } 2298 public int hashCode() { 2299 synchronized (mutex) {return list.hashCode();} 2300 } 2301 2302 public E get(int index) { 2303 synchronized (mutex) {return list.get(index);} 2304 } 2305 public E set(int index, E element) { 2306 synchronized (mutex) {return list.set(index, element);} 2307 } 2308 public void add(int index, E element) { 2309 synchronized (mutex) {list.add(index, element);} 2310 } 2311 public E remove(int index) { 2312 synchronized (mutex) {return list.remove(index);} 2313 } 2314 2315 public int indexOf(Object o) { 2316 synchronized (mutex) {return list.indexOf(o);} 2317 } 2318 public int lastIndexOf(Object o) { 2319 synchronized (mutex) {return list.lastIndexOf(o);} 2320 } 2321 2322 public boolean addAll(int index, Collection<? extends E> c) { 2323 synchronized (mutex) {return list.addAll(index, c);} 2324 } 2325 2326 public ListIterator<E> listIterator() { 2327 return list.listIterator(); // Must be manually synched by user 2328 } 2329 2330 public ListIterator<E> listIterator(int index) { 2331 return list.listIterator(index); // Must be manually synched by user 2332 } 2333 2334 public List<E> subList(int fromIndex, int toIndex) { 2335 synchronized (mutex) { 2336 return new SynchronizedList<>(list.subList(fromIndex, toIndex), 2337 mutex); 2338 } 2339 } 2340 2341 @Override 2342 public void replaceAll(UnaryOperator<E> operator) { 2343 synchronized (mutex) {list.replaceAll(operator);} 2344 } 2345 @Override 2346 public void sort(Comparator<? super E> c) { 2347 synchronized (mutex) {list.sort(c);} 2348 } 2349 2350 /** 2351 * SynchronizedRandomAccessList instances are serialized as 2352 * SynchronizedList instances to allow them to be deserialized 2353 * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList). 2354 * This method inverts the transformation. As a beneficial 2355 * side-effect, it also grafts the RandomAccess marker onto 2356 * SynchronizedList instances that were serialized in pre-1.4 JREs. 2357 * 2358 * Note: Unfortunately, SynchronizedRandomAccessList instances 2359 * serialized in 1.4.1 and deserialized in 1.4 will become 2360 * SynchronizedList instances, as this method was missing in 1.4. 2361 */ 2362 private Object readResolve() { 2363 return (list instanceof RandomAccess 2364 ? new SynchronizedRandomAccessList<>(list) 2365 : this); 2366 } 2367 } 2368 2369 /** 2370 * @serial include 2371 */ 2372 static class SynchronizedRandomAccessList<E> 2373 extends SynchronizedList<E> 2374 implements RandomAccess { 2375 2376 SynchronizedRandomAccessList(List<E> list) { 2377 super(list); 2378 } 2379 2380 SynchronizedRandomAccessList(List<E> list, Object mutex) { 2381 super(list, mutex); 2382 } 2383 2384 public List<E> subList(int fromIndex, int toIndex) { 2385 synchronized (mutex) { 2386 return new SynchronizedRandomAccessList<>( 2387 list.subList(fromIndex, toIndex), mutex); 2388 } 2389 } 2390 2391 private static final long serialVersionUID = 1530674583602358482L; 2392 2393 /** 2394 * Allows instances to be deserialized in pre-1.4 JREs (which do 2395 * not have SynchronizedRandomAccessList). SynchronizedList has 2396 * a readResolve method that inverts this transformation upon 2397 * deserialization. 2398 */ 2399 private Object writeReplace() { 2400 return new SynchronizedList<>(list); 2401 } 2402 } 2403 2404 /** 2405 * Returns a synchronized (thread-safe) map backed by the specified 2406 * map. In order to guarantee serial access, it is critical that 2407 * <strong>all</strong> access to the backing map is accomplished 2408 * through the returned map.<p> 2409 * 2410 * It is imperative that the user manually synchronize on the returned 2411 * map when iterating over any of its collection views: 2412 * <pre> 2413 * Map m = Collections.synchronizedMap(new HashMap()); 2414 * ... 2415 * Set s = m.keySet(); // Needn't be in synchronized block 2416 * ... 2417 * synchronized (m) { // Synchronizing on m, not s! 2418 * Iterator i = s.iterator(); // Must be in synchronized block 2419 * while (i.hasNext()) 2420 * foo(i.next()); 2421 * } 2422 * </pre> 2423 * Failure to follow this advice may result in non-deterministic behavior. 2424 * 2425 * <p>The returned map will be serializable if the specified map is 2426 * serializable. 2427 * 2428 * @param m the map to be "wrapped" in a synchronized map. 2429 * @return a synchronized view of the specified map. 2430 */ 2431 public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { 2432 return new SynchronizedMap<>(m); 2433 } 2434 2435 /** 2436 * @serial include 2437 */ 2438 private static class SynchronizedMap<K,V> 2439 implements Map<K,V>, Serializable { 2440 private static final long serialVersionUID = 1978198479659022715L; 2441 2442 private final Map<K,V> m; // Backing Map 2443 final Object mutex; // Object on which to synchronize 2444 2445 SynchronizedMap(Map<K,V> m) { 2446 this.m = Objects.requireNonNull(m); 2447 mutex = this; 2448 } 2449 2450 SynchronizedMap(Map<K,V> m, Object mutex) { 2451 this.m = m; 2452 this.mutex = mutex; 2453 } 2454 2455 public int size() { 2456 synchronized (mutex) {return m.size();} 2457 } 2458 public boolean isEmpty() { 2459 synchronized (mutex) {return m.isEmpty();} 2460 } 2461 public boolean containsKey(Object key) { 2462 synchronized (mutex) {return m.containsKey(key);} 2463 } 2464 public boolean containsValue(Object value) { 2465 synchronized (mutex) {return m.containsValue(value);} 2466 } 2467 public V get(Object key) { 2468 synchronized (mutex) {return m.get(key);} 2469 } 2470 2471 public V put(K key, V value) { 2472 synchronized (mutex) {return m.put(key, value);} 2473 } 2474 public V remove(Object key) { 2475 synchronized (mutex) {return m.remove(key);} 2476 } 2477 public void putAll(Map<? extends K, ? extends V> map) { 2478 synchronized (mutex) {m.putAll(map);} 2479 } 2480 public void clear() { 2481 synchronized (mutex) {m.clear();} 2482 } 2483 2484 private transient Set<K> keySet = null; 2485 private transient Set<Map.Entry<K,V>> entrySet = null; 2486 private transient Collection<V> values = null; 2487 2488 public Set<K> keySet() { 2489 synchronized (mutex) { 2490 if (keySet==null) 2491 keySet = new SynchronizedSet<>(m.keySet(), mutex); 2492 return keySet; 2493 } 2494 } 2495 2496 public Set<Map.Entry<K,V>> entrySet() { 2497 synchronized (mutex) { 2498 if (entrySet==null) 2499 entrySet = new SynchronizedSet<>(m.entrySet(), mutex); 2500 return entrySet; 2501 } 2502 } 2503 2504 public Collection<V> values() { 2505 synchronized (mutex) { 2506 if (values==null) 2507 values = new SynchronizedCollection<>(m.values(), mutex); 2508 return values; 2509 } 2510 } 2511 2512 public boolean equals(Object o) { 2513 if (this == o) 2514 return true; 2515 synchronized (mutex) {return m.equals(o);} 2516 } 2517 public int hashCode() { 2518 synchronized (mutex) {return m.hashCode();} 2519 } 2520 public String toString() { 2521 synchronized (mutex) {return m.toString();} 2522 } 2523 2524 // Override default methods in Map 2525 @Override 2526 public V getOrDefault(Object k, V defaultValue) { 2527 synchronized (mutex) {return m.getOrDefault(k, defaultValue);} 2528 } 2529 @Override 2530 public void forEach(BiConsumer<? super K, ? super V> action) { 2531 synchronized (mutex) {m.forEach(action);} 2532 } 2533 @Override 2534 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 2535 synchronized (mutex) {m.replaceAll(function);} 2536 } 2537 @Override 2538 public V putIfAbsent(K key, V value) { 2539 synchronized (mutex) {return m.putIfAbsent(key, value);} 2540 } 2541 @Override 2542 public boolean remove(Object key, Object value) { 2543 synchronized (mutex) {return m.remove(key, value);} 2544 } 2545 @Override 2546 public boolean replace(K key, V oldValue, V newValue) { 2547 synchronized (mutex) {return m.replace(key, oldValue, newValue);} 2548 } 2549 @Override 2550 public V replace(K key, V value) { 2551 synchronized (mutex) {return m.replace(key, value);} 2552 } 2553 @Override 2554 public V computeIfAbsent(K key, 2555 Function<? super K, ? extends V> mappingFunction) { 2556 synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);} 2557 } 2558 @Override 2559 public V computeIfPresent(K key, 2560 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 2561 synchronized (mutex) {return m.computeIfPresent(key, remappingFunction);} 2562 } 2563 @Override 2564 public V compute(K key, 2565 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 2566 synchronized (mutex) {return m.compute(key, remappingFunction);} 2567 } 2568 @Override 2569 public V merge(K key, V value, 2570 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 2571 synchronized (mutex) {return m.merge(key, value, remappingFunction);} 2572 } 2573 2574 private void writeObject(ObjectOutputStream s) throws IOException { 2575 synchronized (mutex) {s.defaultWriteObject();} 2576 } 2577 } 2578 2579 /** 2580 * Returns a synchronized (thread-safe) sorted map backed by the specified 2581 * sorted map. In order to guarantee serial access, it is critical that 2582 * <strong>all</strong> access to the backing sorted map is accomplished 2583 * through the returned sorted map (or its views).<p> 2584 * 2585 * It is imperative that the user manually synchronize on the returned 2586 * sorted map when iterating over any of its collection views, or the 2587 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or 2588 * <tt>tailMap</tt> views. 2589 * <pre> 2590 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap()); 2591 * ... 2592 * Set s = m.keySet(); // Needn't be in synchronized block 2593 * ... 2594 * synchronized (m) { // Synchronizing on m, not s! 2595 * Iterator i = s.iterator(); // Must be in synchronized block 2596 * while (i.hasNext()) 2597 * foo(i.next()); 2598 * } 2599 * </pre> 2600 * or: 2601 * <pre> 2602 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap()); 2603 * SortedMap m2 = m.subMap(foo, bar); 2604 * ... 2605 * Set s2 = m2.keySet(); // Needn't be in synchronized block 2606 * ... 2607 * synchronized (m) { // Synchronizing on m, not m2 or s2! 2608 * Iterator i = s.iterator(); // Must be in synchronized block 2609 * while (i.hasNext()) 2610 * foo(i.next()); 2611 * } 2612 * </pre> 2613 * Failure to follow this advice may result in non-deterministic behavior. 2614 * 2615 * <p>The returned sorted map will be serializable if the specified 2616 * sorted map is serializable. 2617 * 2618 * @param m the sorted map to be "wrapped" in a synchronized sorted map. 2619 * @return a synchronized view of the specified sorted map. 2620 */ 2621 public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m) { 2622 return new SynchronizedSortedMap<>(m); 2623 } 2624 2625 /** 2626 * @serial include 2627 */ 2628 static class SynchronizedSortedMap<K,V> 2629 extends SynchronizedMap<K,V> 2630 implements SortedMap<K,V> 2631 { 2632 private static final long serialVersionUID = -8798146769416483793L; 2633 2634 private final SortedMap<K,V> sm; 2635 2636 SynchronizedSortedMap(SortedMap<K,V> m) { 2637 super(m); 2638 sm = m; 2639 } 2640 SynchronizedSortedMap(SortedMap<K,V> m, Object mutex) { 2641 super(m, mutex); 2642 sm = m; 2643 } 2644 2645 public Comparator<? super K> comparator() { 2646 synchronized (mutex) {return sm.comparator();} 2647 } 2648 2649 public SortedMap<K,V> subMap(K fromKey, K toKey) { 2650 synchronized (mutex) { 2651 return new SynchronizedSortedMap<>( 2652 sm.subMap(fromKey, toKey), mutex); 2653 } 2654 } 2655 public SortedMap<K,V> headMap(K toKey) { 2656 synchronized (mutex) { 2657 return new SynchronizedSortedMap<>(sm.headMap(toKey), mutex); 2658 } 2659 } 2660 public SortedMap<K,V> tailMap(K fromKey) { 2661 synchronized (mutex) { 2662 return new SynchronizedSortedMap<>(sm.tailMap(fromKey),mutex); 2663 } 2664 } 2665 2666 public K firstKey() { 2667 synchronized (mutex) {return sm.firstKey();} 2668 } 2669 public K lastKey() { 2670 synchronized (mutex) {return sm.lastKey();} 2671 } 2672 } 2673 2674 /** 2675 * Returns a synchronized (thread-safe) navigable map backed by the 2676 * specified navigable map. In order to guarantee serial access, it is 2677 * critical that <strong>all</strong> access to the backing navigable map is 2678 * accomplished through the returned navigable map (or its views).<p> 2679 * 2680 * It is imperative that the user manually synchronize on the returned 2681 * navigable map when iterating over any of its collection views, or the 2682 * collections views of any of its {@code subMap}, {@code headMap} or 2683 * {@code tailMap} views. 2684 * <pre> 2685 * SortedMap m = Collections.synchronizedNavigableMap(new TreeMap()); 2686 * ... 2687 * Set s = m.keySet(); // Needn't be in synchronized block 2688 * ... 2689 * synchronized (m) { // Synchronizing on m, not s! 2690 * Iterator i = s.iterator(); // Must be in synchronized block 2691 * while (i.hasNext()) 2692 * foo(i.next()); 2693 * } 2694 * </pre> 2695 * or: 2696 * <pre> 2697 * SortedMap m = Collections.synchronizedNavigableMap(new TreeMap()); 2698 * SortedMap m2 = m.subMap(foo, bar); 2699 * ... 2700 * Set s2 = m2.keySet(); // Needn't be in synchronized block 2701 * ... 2702 * synchronized (m) { // Synchronizing on m, not m2 or s2! 2703 * Iterator i = s.iterator(); // Must be in synchronized block 2704 * while (i.hasNext()) 2705 * foo(i.next()); 2706 * } 2707 * </pre> 2708 * Failure to follow this advice may result in non-deterministic behavior. 2709 * 2710 * <p>The returned navigable map will be serializable if the specified 2711 * navigable map is serializable. 2712 * 2713 * @param m the navigable map to be "wrapped" in a synchronized navigable 2714 * map 2715 * @return a synchronized view of the specified navigable map. 2716 * @since 1.8 2717 */ 2718 public static <K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m) { 2719 return new SynchronizedNavigableMap<>(m); 2720 } 2721 2722 /** 2723 * A synchronized NavigableMap. 2724 * 2725 * @serial include 2726 */ 2727 static class SynchronizedNavigableMap<K,V> 2728 extends SynchronizedSortedMap<K,V> 2729 implements NavigableMap<K,V> 2730 { 2731 private static final long serialVersionUID = 699392247599746807L; 2732 2733 private final NavigableMap<K,V> nm; 2734 2735 SynchronizedNavigableMap(NavigableMap<K,V> m) { 2736 super(m); 2737 nm = m; 2738 } 2739 SynchronizedNavigableMap(NavigableMap<K,V> m, Object mutex) { 2740 super(m, mutex); 2741 nm = m; 2742 } 2743 2744 public Entry<K, V> lowerEntry(K key) 2745 { synchronized (mutex) { return nm.lowerEntry(key); } } 2746 public K lowerKey(K key) 2747 { synchronized (mutex) { return nm.lowerKey(key); } } 2748 public Entry<K, V> floorEntry(K key) 2749 { synchronized (mutex) { return nm.floorEntry(key); } } 2750 public K floorKey(K key) 2751 { synchronized (mutex) { return nm.floorKey(key); } } 2752 public Entry<K, V> ceilingEntry(K key) 2753 { synchronized (mutex) { return nm.ceilingEntry(key); } } 2754 public K ceilingKey(K key) 2755 { synchronized (mutex) { return nm.ceilingKey(key); } } 2756 2757 @Override 2758 public Entry<K, V> higherEntry(K key) { 2759 synchronized (mutex) { return nm.higherEntry(key); } 2760 } 2761 2762 @Override 2763 public K higherKey(K key) { 2764 synchronized (mutex) { return nm.higherKey(key); } 2765 } 2766 2767 @Override 2768 public Entry<K, V> firstEntry() { 2769 synchronized (mutex) { return nm.firstEntry(); } 2770 } 2771 2772 @Override 2773 public Entry<K, V> lastEntry() { 2774 synchronized (mutex) { return nm.lastEntry(); } 2775 } 2776 2777 @Override 2778 public Entry<K, V> pollFirstEntry() { 2779 synchronized (mutex) { 2780 return nm.pollFirstEntry(); 2781 } 2782 } 2783 2784 @Override 2785 public Entry<K, V> pollLastEntry() { 2786 synchronized (mutex) { 2787 return nm.pollLastEntry(); 2788 } 2789 } 2790 2791 @Override 2792 public NavigableMap<K, V> descendingMap() { 2793 synchronized (mutex) { 2794 return (NavigableMap<K,V>) 2795 new SynchronizedNavigableMap(nm.descendingMap(), mutex); 2796 } 2797 } 2798 2799 @Override 2800 public NavigableSet<K> navigableKeySet() { 2801 synchronized (mutex) { 2802 return new SynchronizedNavigableSet(nm.navigableKeySet(), mutex); 2803 } 2804 } 2805 2806 @Override 2807 public NavigableSet<K> descendingKeySet() { 2808 synchronized (mutex) { 2809 return new SynchronizedNavigableSet(nm.descendingKeySet(), mutex); 2810 } 2811 } 2812 2813 @Override 2814 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 2815 synchronized (mutex) { 2816 return (NavigableMap<K,V>) new SynchronizedNavigableMap( 2817 nm.subMap(fromKey, fromInclusive, toKey, toInclusive), mutex); 2818 } 2819 } 2820 2821 @Override 2822 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 2823 synchronized (mutex) { 2824 return (NavigableMap<K,V>) new SynchronizedNavigableMap( 2825 nm.headMap(toKey, inclusive), mutex); 2826 } 2827 } 2828 2829 @Override 2830 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 2831 synchronized (mutex) { 2832 return (NavigableMap<K,V>) new SynchronizedNavigableMap( 2833 nm.tailMap(fromKey, inclusive), mutex); 2834 } 2835 } 2836 } 2837 2838 // Dynamically typesafe collection wrappers 2839 2840 /** 2841 * Returns a dynamically typesafe view of the specified collection. 2842 * Any attempt to insert an element of the wrong type will result in an 2843 * immediate {@link ClassCastException}. Assuming a collection 2844 * contains no incorrectly typed elements prior to the time a 2845 * dynamically typesafe view is generated, and that all subsequent 2846 * access to the collection takes place through the view, it is 2847 * <i>guaranteed</i> that the collection cannot contain an incorrectly 2848 * typed element. 2849 * 2850 * <p>The generics mechanism in the language provides compile-time 2851 * (static) type checking, but it is possible to defeat this mechanism 2852 * with unchecked casts. Usually this is not a problem, as the compiler 2853 * issues warnings on all such unchecked operations. There are, however, 2854 * times when static type checking alone is not sufficient. For example, 2855 * suppose a collection is passed to a third-party library and it is 2856 * imperative that the library code not corrupt the collection by 2857 * inserting an element of the wrong type. 2858 * 2859 * <p>Another use of dynamically typesafe views is debugging. Suppose a 2860 * program fails with a {@code ClassCastException}, indicating that an 2861 * incorrectly typed element was put into a parameterized collection. 2862 * Unfortunately, the exception can occur at any time after the erroneous 2863 * element is inserted, so it typically provides little or no information 2864 * as to the real source of the problem. If the problem is reproducible, 2865 * one can quickly determine its source by temporarily modifying the 2866 * program to wrap the collection with a dynamically typesafe view. 2867 * For example, this declaration: 2868 * <pre> {@code 2869 * Collection<String> c = new HashSet<>(); 2870 * }</pre> 2871 * may be replaced temporarily by this one: 2872 * <pre> {@code 2873 * Collection<String> c = Collections.checkedCollection( 2874 * new HashSet<>(), String.class); 2875 * }</pre> 2876 * Running the program again will cause it to fail at the point where 2877 * an incorrectly typed element is inserted into the collection, clearly 2878 * identifying the source of the problem. Once the problem is fixed, the 2879 * modified declaration may be reverted back to the original. 2880 * 2881 * <p>The returned collection does <i>not</i> pass the hashCode and equals 2882 * operations through to the backing collection, but relies on 2883 * {@code Object}'s {@code equals} and {@code hashCode} methods. This 2884 * is necessary to preserve the contracts of these operations in the case 2885 * that the backing collection is a set or a list. 2886 * 2887 * <p>The returned collection will be serializable if the specified 2888 * collection is serializable. 2889 * 2890 * <p>Since {@code null} is considered to be a value of any reference 2891 * type, the returned collection permits insertion of null elements 2892 * whenever the backing collection does. 2893 * 2894 * @param c the collection for which a dynamically typesafe view is to be 2895 * returned 2896 * @param type the type of element that {@code c} is permitted to hold 2897 * @return a dynamically typesafe view of the specified collection 2898 * @since 1.5 2899 */ 2900 public static <E> Collection<E> checkedCollection(Collection<E> c, 2901 Class<E> type) { 2902 return new CheckedCollection<>(c, type); 2903 } 2904 2905 @SuppressWarnings("unchecked") 2906 static <T> T[] zeroLengthArray(Class<T> type) { 2907 return (T[]) Array.newInstance(type, 0); 2908 } 2909 2910 /** 2911 * @serial include 2912 */ 2913 static class CheckedCollection<E> implements Collection<E>, Serializable { 2914 private static final long serialVersionUID = 1578914078182001775L; 2915 2916 final Collection<E> c; 2917 final Class<E> type; 2918 2919 void typeCheck(Object o) { 2920 if (o != null && !type.isInstance(o)) 2921 throw new ClassCastException(badElementMsg(o)); 2922 } 2923 2924 private String badElementMsg(Object o) { 2925 return "Attempt to insert " + o.getClass() + 2926 " element into collection with element type " + type; 2927 } 2928 2929 CheckedCollection(Collection<E> c, Class<E> type) { 2930 if (c==null || type == null) 2931 throw new NullPointerException(); 2932 this.c = c; 2933 this.type = type; 2934 } 2935 2936 public int size() { return c.size(); } 2937 public boolean isEmpty() { return c.isEmpty(); } 2938 public boolean contains(Object o) { return c.contains(o); } 2939 public Object[] toArray() { return c.toArray(); } 2940 public <T> T[] toArray(T[] a) { return c.toArray(a); } 2941 public String toString() { return c.toString(); } 2942 public boolean remove(Object o) { return c.remove(o); } 2943 public void clear() { c.clear(); } 2944 2945 public boolean containsAll(Collection<?> coll) { 2946 return c.containsAll(coll); 2947 } 2948 public boolean removeAll(Collection<?> coll) { 2949 return c.removeAll(coll); 2950 } 2951 public boolean retainAll(Collection<?> coll) { 2952 return c.retainAll(coll); 2953 } 2954 2955 public Iterator<E> iterator() { 2956 // JDK-6363904 - unwrapped iterator could be typecast to 2957 // ListIterator with unsafe set() 2958 final Iterator<E> it = c.iterator(); 2959 return new Iterator<E>() { 2960 public boolean hasNext() { return it.hasNext(); } 2961 public E next() { return it.next(); } 2962 public void remove() { it.remove(); }}; 2963 } 2964 2965 public boolean add(E e) { 2966 typeCheck(e); 2967 return c.add(e); 2968 } 2969 2970 private E[] zeroLengthElementArray = null; // Lazily initialized 2971 2972 private E[] zeroLengthElementArray() { 2973 return zeroLengthElementArray != null ? zeroLengthElementArray : 2974 (zeroLengthElementArray = zeroLengthArray(type)); 2975 } 2976 2977 @SuppressWarnings("unchecked") 2978 Collection<E> checkedCopyOf(Collection<? extends E> coll) { 2979 Object[] a = null; 2980 try { 2981 E[] z = zeroLengthElementArray(); 2982 a = coll.toArray(z); 2983 // Defend against coll violating the toArray contract 2984 if (a.getClass() != z.getClass()) 2985 a = Arrays.copyOf(a, a.length, z.getClass()); 2986 } catch (ArrayStoreException ignore) { 2987 // To get better and consistent diagnostics, 2988 // we call typeCheck explicitly on each element. 2989 // We call clone() to defend against coll retaining a 2990 // reference to the returned array and storing a bad 2991 // element into it after it has been type checked. 2992 a = coll.toArray().clone(); 2993 for (Object o : a) 2994 typeCheck(o); 2995 } 2996 // A slight abuse of the type system, but safe here. 2997 return (Collection<E>) Arrays.asList(a); 2998 } 2999 3000 public boolean addAll(Collection<? extends E> coll) { 3001 // Doing things this way insulates us from concurrent changes 3002 // in the contents of coll and provides all-or-nothing 3003 // semantics (which we wouldn't get if we type-checked each 3004 // element as we added it) 3005 return c.addAll(checkedCopyOf(coll)); 3006 } 3007 3008 // Override default methods in Collection 3009 @Override 3010 public void forEach(Consumer<? super E> action) {c.forEach(action);} 3011 @Override 3012 public boolean removeIf(Predicate<? super E> filter) { 3013 return c.removeIf(filter); 3014 } 3015 @Override 3016 public Spliterator<E> spliterator() {return c.spliterator();} 3017 } 3018 3019 /** 3020 * Returns a dynamically typesafe view of the specified queue. 3021 * Any attempt to insert an element of the wrong type will result in 3022 * an immediate {@link ClassCastException}. Assuming a queue contains 3023 * no incorrectly typed elements prior to the time a dynamically typesafe 3024 * view is generated, and that all subsequent access to the queue 3025 * takes place through the view, it is <i>guaranteed</i> that the 3026 * queue cannot contain an incorrectly typed element. 3027 * 3028 * <p>A discussion of the use of dynamically typesafe views may be 3029 * found in the documentation for the {@link #checkedCollection 3030 * checkedCollection} method. 3031 * 3032 * <p>The returned queue will be serializable if the specified queue 3033 * is serializable. 3034 * 3035 * <p>Since {@code null} is considered to be a value of any reference 3036 * type, the returned queue permits insertion of {@code null} elements 3037 * whenever the backing queue does. 3038 * 3039 * @param queue the queue for which a dynamically typesafe view is to be 3040 * returned 3041 * @param type the type of element that {@code queue} is permitted to hold 3042 * @return a dynamically typesafe view of the specified queue 3043 * @since 1.8 3044 */ 3045 public static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type) { 3046 return new CheckedQueue<>(queue, type); 3047 } 3048 3049 /** 3050 * @serial include 3051 */ 3052 static class CheckedQueue<E> 3053 extends CheckedCollection<E> 3054 implements Queue<E>, Serializable 3055 { 3056 private static final long serialVersionUID = 1433151992604707767L; 3057 final Queue<E> queue; 3058 3059 CheckedQueue(Queue<E> queue, Class<E> elementType) { 3060 super(queue, elementType); 3061 this.queue = queue; 3062 } 3063 3064 public E element() {return queue.element();} 3065 public boolean equals(Object o) {return o == this || c.equals(o);} 3066 public int hashCode() {return c.hashCode();} 3067 public E peek() {return queue.peek();} 3068 public E poll() {return queue.poll();} 3069 public E remove() {return queue.remove();} 3070 3071 public boolean offer(E e) { 3072 typeCheck(e); 3073 return add(e); 3074 } 3075 } 3076 3077 /** 3078 * Returns a dynamically typesafe view of the specified set. 3079 * Any attempt to insert an element of the wrong type will result in 3080 * an immediate {@link ClassCastException}. Assuming a set contains 3081 * no incorrectly typed elements prior to the time a dynamically typesafe 3082 * view is generated, and that all subsequent access to the set 3083 * takes place through the view, it is <i>guaranteed</i> that the 3084 * set cannot contain an incorrectly typed element. 3085 * 3086 * <p>A discussion of the use of dynamically typesafe views may be 3087 * found in the documentation for the {@link #checkedCollection 3088 * checkedCollection} method. 3089 * 3090 * <p>The returned set will be serializable if the specified set is 3091 * serializable. 3092 * 3093 * <p>Since {@code null} is considered to be a value of any reference 3094 * type, the returned set permits insertion of null elements whenever 3095 * the backing set does. 3096 * 3097 * @param s the set for which a dynamically typesafe view is to be 3098 * returned 3099 * @param type the type of element that {@code s} is permitted to hold 3100 * @return a dynamically typesafe view of the specified set 3101 * @since 1.5 3102 */ 3103 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) { 3104 return new CheckedSet<>(s, type); 3105 } 3106 3107 /** 3108 * @serial include 3109 */ 3110 static class CheckedSet<E> extends CheckedCollection<E> 3111 implements Set<E>, Serializable 3112 { 3113 private static final long serialVersionUID = 4694047833775013803L; 3114 3115 CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); } 3116 3117 public boolean equals(Object o) { return o == this || c.equals(o); } 3118 public int hashCode() { return c.hashCode(); } 3119 } 3120 3121 /** 3122 * Returns a dynamically typesafe view of the specified sorted set. 3123 * Any attempt to insert an element of the wrong type will result in an 3124 * immediate {@link ClassCastException}. Assuming a sorted set 3125 * contains no incorrectly typed elements prior to the time a 3126 * dynamically typesafe view is generated, and that all subsequent 3127 * access to the sorted set takes place through the view, it is 3128 * <i>guaranteed</i> that the sorted set cannot contain an incorrectly 3129 * typed element. 3130 * 3131 * <p>A discussion of the use of dynamically typesafe views may be 3132 * found in the documentation for the {@link #checkedCollection 3133 * checkedCollection} method. 3134 * 3135 * <p>The returned sorted set will be serializable if the specified sorted 3136 * set is serializable. 3137 * 3138 * <p>Since {@code null} is considered to be a value of any reference 3139 * type, the returned sorted set permits insertion of null elements 3140 * whenever the backing sorted set does. 3141 * 3142 * @param s the sorted set for which a dynamically typesafe view is to be 3143 * returned 3144 * @param type the type of element that {@code s} is permitted to hold 3145 * @return a dynamically typesafe view of the specified sorted set 3146 * @since 1.5 3147 */ 3148 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, 3149 Class<E> type) { 3150 return new CheckedSortedSet<>(s, type); 3151 } 3152 3153 /** 3154 * @serial include 3155 */ 3156 static class CheckedSortedSet<E> extends CheckedSet<E> 3157 implements SortedSet<E>, Serializable 3158 { 3159 private static final long serialVersionUID = 1599911165492914959L; 3160 3161 private final SortedSet<E> ss; 3162 3163 CheckedSortedSet(SortedSet<E> s, Class<E> type) { 3164 super(s, type); 3165 ss = s; 3166 } 3167 3168 public Comparator<? super E> comparator() { return ss.comparator(); } 3169 public E first() { return ss.first(); } 3170 public E last() { return ss.last(); } 3171 3172 public SortedSet<E> subSet(E fromElement, E toElement) { 3173 return checkedSortedSet(ss.subSet(fromElement,toElement), type); 3174 } 3175 public SortedSet<E> headSet(E toElement) { 3176 return checkedSortedSet(ss.headSet(toElement), type); 3177 } 3178 public SortedSet<E> tailSet(E fromElement) { 3179 return checkedSortedSet(ss.tailSet(fromElement), type); 3180 } 3181 } 3182 3183 /** 3184 * Returns a dynamically typesafe view of the specified navigable set. 3185 * Any attempt to insert an element of the wrong type will result in an 3186 * immediate {@link ClassCastException}. Assuming a navigable set 3187 * contains no incorrectly typed elements prior to the time a 3188 * dynamically typesafe view is generated, and that all subsequent 3189 * access to the navigable set takes place through the view, it is 3190 * <em>guaranteed</em> that the navigable set cannot contain an incorrectly 3191 * typed element. 3192 * 3193 * <p>A discussion of the use of dynamically typesafe views may be 3194 * found in the documentation for the {@link #checkedCollection 3195 * checkedCollection} method. 3196 * 3197 * <p>The returned navigable set will be serializable if the specified 3198 * navigable set is serializable. 3199 * 3200 * <p>Since {@code null} is considered to be a value of any reference 3201 * type, the returned navigable set permits insertion of null elements 3202 * whenever the backing sorted set does. 3203 * 3204 * @param s the navigable set for which a dynamically typesafe view is to be 3205 * returned 3206 * @param type the type of element that {@code s} is permitted to hold 3207 * @return a dynamically typesafe view of the specified navigable set 3208 * @since 1.8 3209 */ 3210 public static <E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s, 3211 Class<E> type) { 3212 return new CheckedNavigableSet<>(s, type); 3213 } 3214 3215 /** 3216 * @serial include 3217 */ 3218 static class CheckedNavigableSet<E> extends CheckedSortedSet<E> 3219 implements NavigableSet<E>, Serializable 3220 { 3221 private static final long serialVersionUID = -5429120189805438922L; 3222 3223 private final NavigableSet<E> ns; 3224 3225 CheckedNavigableSet(NavigableSet<E> s, Class<E> type) { 3226 super(s, type); 3227 ns = s; 3228 } 3229 3230 public E lower(E e) { return ns.lower(e); } 3231 public E floor(E e) { return ns.floor(e); } 3232 public E ceiling(E e) { return ns.ceiling(e); } 3233 public E higher(E e) { return ns.higher(e); } 3234 public E pollFirst() { return ns.pollFirst(); } 3235 public E pollLast() {return ns.pollLast(); } 3236 public NavigableSet<E> descendingSet() 3237 { return checkedNavigableSet(ns.descendingSet(), type); } 3238 public Iterator<E> descendingIterator() 3239 {return checkedNavigableSet(ns.descendingSet(), type).iterator(); } 3240 3241 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 3242 return checkedNavigableSet(ns.subSet(fromElement, fromInclusive, toElement, toInclusive), type); 3243 } 3244 3245 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 3246 return checkedNavigableSet(ns.headSet(toElement, inclusive), type); 3247 } 3248 3249 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 3250 return checkedNavigableSet(ns.tailSet(fromElement, inclusive), type); 3251 } 3252 } 3253 3254 /** 3255 * Returns a dynamically typesafe view of the specified list. 3256 * Any attempt to insert an element of the wrong type will result in 3257 * an immediate {@link ClassCastException}. Assuming a list contains 3258 * no incorrectly typed elements prior to the time a dynamically typesafe 3259 * view is generated, and that all subsequent access to the list 3260 * takes place through the view, it is <i>guaranteed</i> that the 3261 * list cannot contain an incorrectly typed element. 3262 * 3263 * <p>A discussion of the use of dynamically typesafe views may be 3264 * found in the documentation for the {@link #checkedCollection 3265 * checkedCollection} method. 3266 * 3267 * <p>The returned list will be serializable if the specified list 3268 * is serializable. 3269 * 3270 * <p>Since {@code null} is considered to be a value of any reference 3271 * type, the returned list permits insertion of null elements whenever 3272 * the backing list does. 3273 * 3274 * @param list the list for which a dynamically typesafe view is to be 3275 * returned 3276 * @param type the type of element that {@code list} is permitted to hold 3277 * @return a dynamically typesafe view of the specified list 3278 * @since 1.5 3279 */ 3280 public static <E> List<E> checkedList(List<E> list, Class<E> type) { 3281 return (list instanceof RandomAccess ? 3282 new CheckedRandomAccessList<>(list, type) : 3283 new CheckedList<>(list, type)); 3284 } 3285 3286 /** 3287 * @serial include 3288 */ 3289 static class CheckedList<E> 3290 extends CheckedCollection<E> 3291 implements List<E> 3292 { 3293 private static final long serialVersionUID = 65247728283967356L; 3294 final List<E> list; 3295 3296 CheckedList(List<E> list, Class<E> type) { 3297 super(list, type); 3298 this.list = list; 3299 } 3300 3301 public boolean equals(Object o) { return o == this || list.equals(o); } 3302 public int hashCode() { return list.hashCode(); } 3303 public E get(int index) { return list.get(index); } 3304 public E remove(int index) { return list.remove(index); } 3305 public int indexOf(Object o) { return list.indexOf(o); } 3306 public int lastIndexOf(Object o) { return list.lastIndexOf(o); } 3307 3308 public E set(int index, E element) { 3309 typeCheck(element); 3310 return list.set(index, element); 3311 } 3312 3313 public void add(int index, E element) { 3314 typeCheck(element); 3315 list.add(index, element); 3316 } 3317 3318 public boolean addAll(int index, Collection<? extends E> c) { 3319 return list.addAll(index, checkedCopyOf(c)); 3320 } 3321 public ListIterator<E> listIterator() { return listIterator(0); } 3322 3323 public ListIterator<E> listIterator(final int index) { 3324 final ListIterator<E> i = list.listIterator(index); 3325 3326 return new ListIterator<E>() { 3327 public boolean hasNext() { return i.hasNext(); } 3328 public E next() { return i.next(); } 3329 public boolean hasPrevious() { return i.hasPrevious(); } 3330 public E previous() { return i.previous(); } 3331 public int nextIndex() { return i.nextIndex(); } 3332 public int previousIndex() { return i.previousIndex(); } 3333 public void remove() { i.remove(); } 3334 3335 public void set(E e) { 3336 typeCheck(e); 3337 i.set(e); 3338 } 3339 3340 public void add(E e) { 3341 typeCheck(e); 3342 i.add(e); 3343 } 3344 3345 @Override 3346 public void forEachRemaining(Consumer<? super E> action) { 3347 i.forEachRemaining(action); 3348 } 3349 }; 3350 } 3351 3352 public List<E> subList(int fromIndex, int toIndex) { 3353 return new CheckedList<>(list.subList(fromIndex, toIndex), type); 3354 } 3355 3356 @Override 3357 public void replaceAll(UnaryOperator<E> operator) { 3358 list.replaceAll(operator); 3359 } 3360 @Override 3361 public void sort(Comparator<? super E> c) { 3362 list.sort(c); 3363 } 3364 } 3365 3366 /** 3367 * @serial include 3368 */ 3369 static class CheckedRandomAccessList<E> extends CheckedList<E> 3370 implements RandomAccess 3371 { 3372 private static final long serialVersionUID = 1638200125423088369L; 3373 3374 CheckedRandomAccessList(List<E> list, Class<E> type) { 3375 super(list, type); 3376 } 3377 3378 public List<E> subList(int fromIndex, int toIndex) { 3379 return new CheckedRandomAccessList<>( 3380 list.subList(fromIndex, toIndex), type); 3381 } 3382 } 3383 3384 /** 3385 * Returns a dynamically typesafe view of the specified map. 3386 * Any attempt to insert a mapping whose key or value have the wrong 3387 * type will result in an immediate {@link ClassCastException}. 3388 * Similarly, any attempt to modify the value currently associated with 3389 * a key will result in an immediate {@link ClassCastException}, 3390 * whether the modification is attempted directly through the map 3391 * itself, or through a {@link Map.Entry} instance obtained from the 3392 * map's {@link Map#entrySet() entry set} view. 3393 * 3394 * <p>Assuming a map contains no incorrectly typed keys or values 3395 * prior to the time a dynamically typesafe view is generated, and 3396 * that all subsequent access to the map takes place through the view 3397 * (or one of its collection views), it is <i>guaranteed</i> that the 3398 * map cannot contain an incorrectly typed key or value. 3399 * 3400 * <p>A discussion of the use of dynamically typesafe views may be 3401 * found in the documentation for the {@link #checkedCollection 3402 * checkedCollection} method. 3403 * 3404 * <p>The returned map will be serializable if the specified map is 3405 * serializable. 3406 * 3407 * <p>Since {@code null} is considered to be a value of any reference 3408 * type, the returned map permits insertion of null keys or values 3409 * whenever the backing map does. 3410 * 3411 * @param m the map for which a dynamically typesafe view is to be 3412 * returned 3413 * @param keyType the type of key that {@code m} is permitted to hold 3414 * @param valueType the type of value that {@code m} is permitted to hold 3415 * @return a dynamically typesafe view of the specified map 3416 * @since 1.5 3417 */ 3418 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, 3419 Class<K> keyType, 3420 Class<V> valueType) { 3421 return new CheckedMap<>(m, keyType, valueType); 3422 } 3423 3424 3425 /** 3426 * @serial include 3427 */ 3428 private static class CheckedMap<K,V> 3429 implements Map<K,V>, Serializable 3430 { 3431 private static final long serialVersionUID = 5742860141034234728L; 3432 3433 private final Map<K, V> m; 3434 final Class<K> keyType; 3435 final Class<V> valueType; 3436 3437 private void typeCheck(Object key, Object value) { 3438 if (key != null && !keyType.isInstance(key)) 3439 throw new ClassCastException(badKeyMsg(key)); 3440 3441 if (value != null && !valueType.isInstance(value)) 3442 throw new ClassCastException(badValueMsg(value)); 3443 } 3444 3445 private BiFunction<? super K, ? super V, ? extends V> typeCheck( 3446 BiFunction<? super K, ? super V, ? extends V> func) { 3447 Objects.requireNonNull(func); 3448 return (k, v) -> { 3449 V newValue = func.apply(k, v); 3450 typeCheck(k, newValue); 3451 return newValue; 3452 }; 3453 } 3454 3455 private String badKeyMsg(Object key) { 3456 return "Attempt to insert " + key.getClass() + 3457 " key into map with key type " + keyType; 3458 } 3459 3460 private String badValueMsg(Object value) { 3461 return "Attempt to insert " + value.getClass() + 3462 " value into map with value type " + valueType; 3463 } 3464 3465 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) { 3466 this.m = Objects.requireNonNull(m); 3467 this.keyType = Objects.requireNonNull(keyType); 3468 this.valueType = Objects.requireNonNull(valueType); 3469 } 3470 3471 public int size() { return m.size(); } 3472 public boolean isEmpty() { return m.isEmpty(); } 3473 public boolean containsKey(Object key) { return m.containsKey(key); } 3474 public boolean containsValue(Object v) { return m.containsValue(v); } 3475 public V get(Object key) { return m.get(key); } 3476 public V remove(Object key) { return m.remove(key); } 3477 public void clear() { m.clear(); } 3478 public Set<K> keySet() { return m.keySet(); } 3479 public Collection<V> values() { return m.values(); } 3480 public boolean equals(Object o) { return o == this || m.equals(o); } 3481 public int hashCode() { return m.hashCode(); } 3482 public String toString() { return m.toString(); } 3483 3484 public V put(K key, V value) { 3485 typeCheck(key, value); 3486 return m.put(key, value); 3487 } 3488 3489 @SuppressWarnings("unchecked") 3490 public void putAll(Map<? extends K, ? extends V> t) { 3491 // Satisfy the following goals: 3492 // - good diagnostics in case of type mismatch 3493 // - all-or-nothing semantics 3494 // - protection from malicious t 3495 // - correct behavior if t is a concurrent map 3496 Object[] entries = t.entrySet().toArray(); 3497 List<Map.Entry<K,V>> checked = new ArrayList<>(entries.length); 3498 for (Object o : entries) { 3499 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 3500 Object k = e.getKey(); 3501 Object v = e.getValue(); 3502 typeCheck(k, v); 3503 checked.add( 3504 new AbstractMap.SimpleImmutableEntry<>((K)k, (V)v)); 3505 } 3506 for (Map.Entry<K,V> e : checked) 3507 m.put(e.getKey(), e.getValue()); 3508 } 3509 3510 private transient Set<Map.Entry<K,V>> entrySet = null; 3511 3512 public Set<Map.Entry<K,V>> entrySet() { 3513 if (entrySet==null) 3514 entrySet = new CheckedEntrySet<>(m.entrySet(), valueType); 3515 return entrySet; 3516 } 3517 3518 // Override default methods in Map 3519 @Override 3520 public void forEach(BiConsumer<? super K, ? super V> action) { 3521 m.forEach(action); 3522 } 3523 3524 @Override 3525 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 3526 m.replaceAll(typeCheck(function)); 3527 } 3528 3529 @Override 3530 public V putIfAbsent(K key, V value) { 3531 typeCheck(key, value); 3532 return m.putIfAbsent(key, value); 3533 } 3534 3535 @Override 3536 public boolean remove(Object key, Object value) { 3537 return m.remove(key, value); 3538 } 3539 3540 @Override 3541 public boolean replace(K key, V oldValue, V newValue) { 3542 typeCheck(key, newValue); 3543 return m.replace(key, oldValue, newValue); 3544 } 3545 3546 @Override 3547 public V replace(K key, V value) { 3548 typeCheck(key, value); 3549 return m.replace(key, value); 3550 } 3551 3552 @Override 3553 public V computeIfAbsent(K key, 3554 Function<? super K, ? extends V> mappingFunction) { 3555 Objects.requireNonNull(mappingFunction); 3556 return m.computeIfAbsent(key, k -> { 3557 V value = mappingFunction.apply(k); 3558 typeCheck(k, value); 3559 return value; 3560 }); 3561 } 3562 3563 @Override 3564 public V computeIfPresent(K key, 3565 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 3566 return m.computeIfPresent(key, typeCheck(remappingFunction)); 3567 } 3568 3569 @Override 3570 public V compute(K key, 3571 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 3572 return m.compute(key, typeCheck(remappingFunction)); 3573 } 3574 3575 @Override 3576 public V merge(K key, V value, 3577 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 3578 Objects.requireNonNull(remappingFunction); 3579 return m.merge(key, value, (v1, v2) -> { 3580 V newValue = remappingFunction.apply(v1, v2); 3581 typeCheck(null, newValue); 3582 return newValue; 3583 }); 3584 } 3585 3586 /** 3587 * We need this class in addition to CheckedSet as Map.Entry permits 3588 * modification of the backing Map via the setValue operation. This 3589 * class is subtle: there are many possible attacks that must be 3590 * thwarted. 3591 * 3592 * @serial exclude 3593 */ 3594 static class CheckedEntrySet<K,V> implements Set<Map.Entry<K,V>> { 3595 private final Set<Map.Entry<K,V>> s; 3596 private final Class<V> valueType; 3597 3598 CheckedEntrySet(Set<Map.Entry<K, V>> s, Class<V> valueType) { 3599 this.s = s; 3600 this.valueType = valueType; 3601 } 3602 3603 public int size() { return s.size(); } 3604 public boolean isEmpty() { return s.isEmpty(); } 3605 public String toString() { return s.toString(); } 3606 public int hashCode() { return s.hashCode(); } 3607 public void clear() { s.clear(); } 3608 3609 public boolean add(Map.Entry<K, V> e) { 3610 throw new UnsupportedOperationException(); 3611 } 3612 public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) { 3613 throw new UnsupportedOperationException(); 3614 } 3615 3616 public Iterator<Map.Entry<K,V>> iterator() { 3617 final Iterator<Map.Entry<K, V>> i = s.iterator(); 3618 final Class<V> valueType = this.valueType; 3619 3620 return new Iterator<Map.Entry<K,V>>() { 3621 public boolean hasNext() { return i.hasNext(); } 3622 public void remove() { i.remove(); } 3623 3624 public Map.Entry<K,V> next() { 3625 return checkedEntry(i.next(), valueType); 3626 } 3627 }; 3628 } 3629 3630 @SuppressWarnings("unchecked") 3631 public Object[] toArray() { 3632 Object[] source = s.toArray(); 3633 3634 /* 3635 * Ensure that we don't get an ArrayStoreException even if 3636 * s.toArray returns an array of something other than Object 3637 */ 3638 Object[] dest = (CheckedEntry.class.isInstance( 3639 source.getClass().getComponentType()) ? source : 3640 new Object[source.length]); 3641 3642 for (int i = 0; i < source.length; i++) 3643 dest[i] = checkedEntry((Map.Entry<K,V>)source[i], 3644 valueType); 3645 return dest; 3646 } 3647 3648 @SuppressWarnings("unchecked") 3649 public <T> T[] toArray(T[] a) { 3650 // We don't pass a to s.toArray, to avoid window of 3651 // vulnerability wherein an unscrupulous multithreaded client 3652 // could get his hands on raw (unwrapped) Entries from s. 3653 T[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0)); 3654 3655 for (int i=0; i<arr.length; i++) 3656 arr[i] = (T) checkedEntry((Map.Entry<K,V>)arr[i], 3657 valueType); 3658 if (arr.length > a.length) 3659 return arr; 3660 3661 System.arraycopy(arr, 0, a, 0, arr.length); 3662 if (a.length > arr.length) 3663 a[arr.length] = null; 3664 return a; 3665 } 3666 3667 /** 3668 * This method is overridden to protect the backing set against 3669 * an object with a nefarious equals function that senses 3670 * that the equality-candidate is Map.Entry and calls its 3671 * setValue method. 3672 */ 3673 public boolean contains(Object o) { 3674 if (!(o instanceof Map.Entry)) 3675 return false; 3676 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 3677 return s.contains( 3678 (e instanceof CheckedEntry) ? e : checkedEntry(e, valueType)); 3679 } 3680 3681 /** 3682 * The bulk collection methods are overridden to protect 3683 * against an unscrupulous collection whose contains(Object o) 3684 * method senses when o is a Map.Entry, and calls o.setValue. 3685 */ 3686 public boolean containsAll(Collection<?> c) { 3687 for (Object o : c) 3688 if (!contains(o)) // Invokes safe contains() above 3689 return false; 3690 return true; 3691 } 3692 3693 public boolean remove(Object o) { 3694 if (!(o instanceof Map.Entry)) 3695 return false; 3696 return s.remove(new AbstractMap.SimpleImmutableEntry 3697 <>((Map.Entry<?,?>)o)); 3698 } 3699 3700 public boolean removeAll(Collection<?> c) { 3701 return batchRemove(c, false); 3702 } 3703 public boolean retainAll(Collection<?> c) { 3704 return batchRemove(c, true); 3705 } 3706 private boolean batchRemove(Collection<?> c, boolean complement) { 3707 boolean modified = false; 3708 Iterator<Map.Entry<K,V>> it = iterator(); 3709 while (it.hasNext()) { 3710 if (c.contains(it.next()) != complement) { 3711 it.remove(); 3712 modified = true; 3713 } 3714 } 3715 return modified; 3716 } 3717 3718 public boolean equals(Object o) { 3719 if (o == this) 3720 return true; 3721 if (!(o instanceof Set)) 3722 return false; 3723 Set<?> that = (Set<?>) o; 3724 return that.size() == s.size() 3725 && containsAll(that); // Invokes safe containsAll() above 3726 } 3727 3728 static <K,V,T> CheckedEntry<K,V,T> checkedEntry(Map.Entry<K,V> e, 3729 Class<T> valueType) { 3730 return new CheckedEntry<>(e, valueType); 3731 } 3732 3733 /** 3734 * This "wrapper class" serves two purposes: it prevents 3735 * the client from modifying the backing Map, by short-circuiting 3736 * the setValue method, and it protects the backing Map against 3737 * an ill-behaved Map.Entry that attempts to modify another 3738 * Map.Entry when asked to perform an equality check. 3739 */ 3740 private static class CheckedEntry<K,V,T> implements Map.Entry<K,V> { 3741 private final Map.Entry<K, V> e; 3742 private final Class<T> valueType; 3743 3744 CheckedEntry(Map.Entry<K, V> e, Class<T> valueType) { 3745 this.e = e; 3746 this.valueType = valueType; 3747 } 3748 3749 public K getKey() { return e.getKey(); } 3750 public V getValue() { return e.getValue(); } 3751 public int hashCode() { return e.hashCode(); } 3752 public String toString() { return e.toString(); } 3753 3754 public V setValue(V value) { 3755 if (value != null && !valueType.isInstance(value)) 3756 throw new ClassCastException(badValueMsg(value)); 3757 return e.setValue(value); 3758 } 3759 3760 private String badValueMsg(Object value) { 3761 return "Attempt to insert " + value.getClass() + 3762 " value into map with value type " + valueType; 3763 } 3764 3765 public boolean equals(Object o) { 3766 if (o == this) 3767 return true; 3768 if (!(o instanceof Map.Entry)) 3769 return false; 3770 return e.equals(new AbstractMap.SimpleImmutableEntry 3771 <>((Map.Entry<?,?>)o)); 3772 } 3773 } 3774 } 3775 } 3776 3777 /** 3778 * Returns a dynamically typesafe view of the specified sorted map. 3779 * Any attempt to insert a mapping whose key or value have the wrong 3780 * type will result in an immediate {@link ClassCastException}. 3781 * Similarly, any attempt to modify the value currently associated with 3782 * a key will result in an immediate {@link ClassCastException}, 3783 * whether the modification is attempted directly through the map 3784 * itself, or through a {@link Map.Entry} instance obtained from the 3785 * map's {@link Map#entrySet() entry set} view. 3786 * 3787 * <p>Assuming a map contains no incorrectly typed keys or values 3788 * prior to the time a dynamically typesafe view is generated, and 3789 * that all subsequent access to the map takes place through the view 3790 * (or one of its collection views), it is <i>guaranteed</i> that the 3791 * map cannot contain an incorrectly typed key or value. 3792 * 3793 * <p>A discussion of the use of dynamically typesafe views may be 3794 * found in the documentation for the {@link #checkedCollection 3795 * checkedCollection} method. 3796 * 3797 * <p>The returned map will be serializable if the specified map is 3798 * serializable. 3799 * 3800 * <p>Since {@code null} is considered to be a value of any reference 3801 * type, the returned map permits insertion of null keys or values 3802 * whenever the backing map does. 3803 * 3804 * @param m the map for which a dynamically typesafe view is to be 3805 * returned 3806 * @param keyType the type of key that {@code m} is permitted to hold 3807 * @param valueType the type of value that {@code m} is permitted to hold 3808 * @return a dynamically typesafe view of the specified map 3809 * @since 1.5 3810 */ 3811 public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, 3812 Class<K> keyType, 3813 Class<V> valueType) { 3814 return new CheckedSortedMap<>(m, keyType, valueType); 3815 } 3816 3817 /** 3818 * @serial include 3819 */ 3820 static class CheckedSortedMap<K,V> extends CheckedMap<K,V> 3821 implements SortedMap<K,V>, Serializable 3822 { 3823 private static final long serialVersionUID = 1599671320688067438L; 3824 3825 private final SortedMap<K, V> sm; 3826 3827 CheckedSortedMap(SortedMap<K, V> m, 3828 Class<K> keyType, Class<V> valueType) { 3829 super(m, keyType, valueType); 3830 sm = m; 3831 } 3832 3833 public Comparator<? super K> comparator() { return sm.comparator(); } 3834 public K firstKey() { return sm.firstKey(); } 3835 public K lastKey() { return sm.lastKey(); } 3836 3837 public SortedMap<K,V> subMap(K fromKey, K toKey) { 3838 return checkedSortedMap(sm.subMap(fromKey, toKey), 3839 keyType, valueType); 3840 } 3841 public SortedMap<K,V> headMap(K toKey) { 3842 return checkedSortedMap(sm.headMap(toKey), keyType, valueType); 3843 } 3844 public SortedMap<K,V> tailMap(K fromKey) { 3845 return checkedSortedMap(sm.tailMap(fromKey), keyType, valueType); 3846 } 3847 } 3848 3849 /** 3850 * Returns a dynamically typesafe view of the specified navigable map. 3851 * Any attempt to insert a mapping whose key or value have the wrong 3852 * type will result in an immediate {@link ClassCastException}. 3853 * Similarly, any attempt to modify the value currently associated with 3854 * a key will result in an immediate {@link ClassCastException}, 3855 * whether the modification is attempted directly through the map 3856 * itself, or through a {@link Map.Entry} instance obtained from the 3857 * map's {@link Map#entrySet() entry set} view. 3858 * 3859 * <p>Assuming a map contains no incorrectly typed keys or values 3860 * prior to the time a dynamically typesafe view is generated, and 3861 * that all subsequent access to the map takes place through the view 3862 * (or one of its collection views), it is <em>guaranteed</em> that the 3863 * map cannot contain an incorrectly typed key or value. 3864 * 3865 * <p>A discussion of the use of dynamically typesafe views may be 3866 * found in the documentation for the {@link #checkedCollection 3867 * checkedCollection} method. 3868 * 3869 * <p>The returned map will be serializable if the specified map is 3870 * serializable. 3871 * 3872 * <p>Since {@code null} is considered to be a value of any reference 3873 * type, the returned map permits insertion of null keys or values 3874 * whenever the backing map does. 3875 * 3876 * @param <K> type of map keys 3877 * @param <V> type of map values 3878 * @param m the map for which a dynamically typesafe view is to be 3879 * returned 3880 * @param keyType the type of key that {@code m} is permitted to hold 3881 * @param valueType the type of value that {@code m} is permitted to hold 3882 * @return a dynamically typesafe view of the specified map 3883 * @since 1.8 3884 */ 3885 public static <K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K, V> m, 3886 Class<K> keyType, 3887 Class<V> valueType) { 3888 return new CheckedNavigableMap<>(m, keyType, valueType); 3889 } 3890 3891 /** 3892 * @serial include 3893 */ 3894 static class CheckedNavigableMap<K,V> extends CheckedSortedMap<K,V> 3895 implements NavigableMap<K,V>, Serializable 3896 { 3897 private static final long serialVersionUID = -4852462692372534096L; 3898 3899 private final NavigableMap<K, V> nm; 3900 3901 CheckedNavigableMap(NavigableMap<K, V> m, 3902 Class<K> keyType, Class<V> valueType) { 3903 super(m, keyType, valueType); 3904 nm = m; 3905 } 3906 3907 public Comparator<? super K> comparator() { return nm.comparator(); } 3908 public K firstKey() { return nm.firstKey(); } 3909 public K lastKey() { return nm.lastKey(); } 3910 3911 public NavigableMap<K,V> subMap(K fromKey, K toKey) { 3912 return checkedNavigableMap((NavigableMap<K,V>)nm.subMap(fromKey, toKey), 3913 keyType, valueType); 3914 } 3915 public NavigableMap<K,V> headMap(K toKey) { 3916 return checkedNavigableMap((NavigableMap<K,V>)nm.headMap(toKey), keyType, valueType); 3917 } 3918 public NavigableMap<K,V> tailMap(K fromKey) { 3919 return checkedNavigableMap((NavigableMap<K,V>)nm.tailMap(fromKey), keyType, valueType); 3920 } 3921 3922 @Override 3923 public Entry<K, V> lowerEntry(K key) { 3924 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lowerEntry(key), valueType); 3925 } 3926 3927 @Override 3928 public K lowerKey(K key) { 3929 return nm.lowerKey(key); 3930 } 3931 3932 @Override 3933 public Entry<K, V> floorEntry(K key) { 3934 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lowerEntry(key), valueType); 3935 } 3936 3937 @Override 3938 public K floorKey(K key) { 3939 return nm.floorKey(key); 3940 } 3941 3942 @Override 3943 public Entry<K, V> ceilingEntry(K key) { 3944 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.ceilingEntry(key), valueType); 3945 } 3946 3947 @Override 3948 public K ceilingKey(K key) { 3949 return nm.ceilingKey(key); 3950 } 3951 3952 @Override 3953 public Entry<K, V> higherEntry(K key) { 3954 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.higherEntry(key), valueType); 3955 } 3956 3957 @Override 3958 public K higherKey(K key) { 3959 return nm.higherKey(key); 3960 } 3961 3962 @Override 3963 public Entry<K, V> firstEntry() { 3964 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.firstEntry(), valueType); 3965 } 3966 3967 @Override 3968 public Entry<K, V> lastEntry() { 3969 return new CheckedMap.CheckedEntrySet.CheckedEntry(nm.lastEntry(), valueType); 3970 } 3971 3972 @Override 3973 public Entry<K, V> pollFirstEntry() { 3974 Entry<K,V> entry = nm.pollFirstEntry(); 3975 return (null == entry) ? null : new CheckedMap.CheckedEntrySet.CheckedEntry(entry, valueType); 3976 } 3977 3978 @Override 3979 public Entry<K, V> pollLastEntry() { 3980 Entry<K,V> entry = nm.pollLastEntry(); 3981 return (null == entry) ? null : new CheckedMap.CheckedEntrySet.CheckedEntry(entry, valueType); 3982 } 3983 3984 @Override 3985 public NavigableMap<K, V> descendingMap() { 3986 return checkedNavigableMap(nm.descendingMap(), keyType, valueType); 3987 } 3988 3989 @Override 3990 public NavigableSet<K> navigableKeySet() { 3991 return checkedNavigableSet(nm.navigableKeySet(), keyType); 3992 } 3993 3994 @Override 3995 public NavigableSet<K> descendingKeySet() { 3996 return checkedNavigableSet(nm.descendingKeySet(), keyType); 3997 } 3998 3999 @Override 4000 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 4001 return checkedNavigableMap(nm.subMap(fromKey, fromInclusive, toKey, toInclusive), keyType, valueType); 4002 } 4003 4004 @Override 4005 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 4006 return checkedNavigableMap(nm.headMap(toKey, inclusive), keyType, valueType); 4007 } 4008 4009 @Override 4010 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 4011 return checkedNavigableMap(nm.tailMap(fromKey, inclusive), keyType, valueType); 4012 } 4013 } 4014 4015 // Empty collections 4016 4017 /** 4018 * Returns an iterator that has no elements. More precisely, 4019 * 4020 * <ul compact> 4021 * 4022 * <li>{@link Iterator#hasNext hasNext} always returns {@code 4023 * false}. 4024 * 4025 * <li>{@link Iterator#next next} always throws {@link 4026 * NoSuchElementException}. 4027 * 4028 * <li>{@link Iterator#remove remove} always throws {@link 4029 * IllegalStateException}. 4030 * 4031 * </ul> 4032 * 4033 * <p>Implementations of this method are permitted, but not 4034 * required, to return the same object from multiple invocations. 4035 * 4036 * @return an empty iterator 4037 * @since 1.7 4038 */ 4039 @SuppressWarnings("unchecked") 4040 public static <T> Iterator<T> emptyIterator() { 4041 return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR; 4042 } 4043 4044 private static class EmptyIterator<E> implements Iterator<E> { 4045 static final EmptyIterator<Object> EMPTY_ITERATOR 4046 = new EmptyIterator<>(); 4047 4048 public boolean hasNext() { return false; } 4049 public E next() { throw new NoSuchElementException(); } 4050 public void remove() { throw new IllegalStateException(); } 4051 @Override 4052 public void forEachRemaining(Consumer<? super E> action) { 4053 Objects.requireNonNull(action); 4054 } 4055 } 4056 4057 /** 4058 * Returns a list iterator that has no elements. More precisely, 4059 * 4060 * <ul compact> 4061 * 4062 * <li>{@link Iterator#hasNext hasNext} and {@link 4063 * ListIterator#hasPrevious hasPrevious} always return {@code 4064 * false}. 4065 * 4066 * <li>{@link Iterator#next next} and {@link ListIterator#previous 4067 * previous} always throw {@link NoSuchElementException}. 4068 * 4069 * <li>{@link Iterator#remove remove} and {@link ListIterator#set 4070 * set} always throw {@link IllegalStateException}. 4071 * 4072 * <li>{@link ListIterator#add add} always throws {@link 4073 * UnsupportedOperationException}. 4074 * 4075 * <li>{@link ListIterator#nextIndex nextIndex} always returns 4076 * {@code 0} . 4077 * 4078 * <li>{@link ListIterator#previousIndex previousIndex} always 4079 * returns {@code -1}. 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 * @return an empty list iterator 4087 * @since 1.7 4088 */ 4089 @SuppressWarnings("unchecked") 4090 public static <T> ListIterator<T> emptyListIterator() { 4091 return (ListIterator<T>) EmptyListIterator.EMPTY_ITERATOR; 4092 } 4093 4094 private static class EmptyListIterator<E> 4095 extends EmptyIterator<E> 4096 implements ListIterator<E> 4097 { 4098 static final EmptyListIterator<Object> EMPTY_ITERATOR 4099 = new EmptyListIterator<>(); 4100 4101 public boolean hasPrevious() { return false; } 4102 public E previous() { throw new NoSuchElementException(); } 4103 public int nextIndex() { return 0; } 4104 public int previousIndex() { return -1; } 4105 public void set(E e) { throw new IllegalStateException(); } 4106 public void add(E e) { throw new UnsupportedOperationException(); } 4107 } 4108 4109 /** 4110 * Returns an enumeration that has no elements. More precisely, 4111 * 4112 * <ul compact> 4113 * 4114 * <li>{@link Enumeration#hasMoreElements hasMoreElements} always 4115 * returns {@code false}. 4116 * 4117 * <li> {@link Enumeration#nextElement nextElement} always throws 4118 * {@link NoSuchElementException}. 4119 * 4120 * </ul> 4121 * 4122 * <p>Implementations of this method are permitted, but not 4123 * required, to return the same object from multiple invocations. 4124 * 4125 * @return an empty enumeration 4126 * @since 1.7 4127 */ 4128 @SuppressWarnings("unchecked") 4129 public static <T> Enumeration<T> emptyEnumeration() { 4130 return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION; 4131 } 4132 4133 private static class EmptyEnumeration<E> implements Enumeration<E> { 4134 static final EmptyEnumeration<Object> EMPTY_ENUMERATION 4135 = new EmptyEnumeration<>(); 4136 4137 public boolean hasMoreElements() { return false; } 4138 public E nextElement() { throw new NoSuchElementException(); } 4139 } 4140 4141 /** 4142 * The empty set (immutable). This set is serializable. 4143 * 4144 * @see #emptySet() 4145 */ 4146 @SuppressWarnings("rawtypes") 4147 public static final Set EMPTY_SET = new EmptySet<>(); 4148 4149 /** 4150 * Returns the empty set (immutable). This set is serializable. 4151 * Unlike the like-named field, this method is parameterized. 4152 * 4153 * <p>This example illustrates the type-safe way to obtain an empty set: 4154 * <pre> 4155 * Set<String> s = Collections.emptySet(); 4156 * </pre> 4157 * @implNote Implementations of this method need not create a separate 4158 * {@code Set} object for each call. Using this method is likely to have 4159 * comparable cost to using the like-named field. (Unlike this method, the 4160 * field does not provide type safety.) 4161 * 4162 * @return the empty set 4163 * @see #EMPTY_SET 4164 * @since 1.5 4165 */ 4166 @SuppressWarnings("unchecked") 4167 public static final <T> Set<T> emptySet() { 4168 return (Set<T>) EMPTY_SET; 4169 } 4170 4171 /** 4172 * @serial include 4173 */ 4174 private static class EmptySet<E> 4175 extends AbstractSet<E> 4176 implements Serializable 4177 { 4178 private static final long serialVersionUID = 1582296315990362920L; 4179 4180 public Iterator<E> iterator() { return emptyIterator(); } 4181 4182 public int size() {return 0;} 4183 public boolean isEmpty() {return true;} 4184 4185 public boolean contains(Object obj) {return false;} 4186 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 4187 4188 public Object[] toArray() { return new Object[0]; } 4189 4190 public <T> T[] toArray(T[] a) { 4191 if (a.length > 0) 4192 a[0] = null; 4193 return a; 4194 } 4195 4196 // Override default methods in Collection 4197 @Override 4198 public void forEach(Consumer<? super E> action) { 4199 Objects.requireNonNull(action); 4200 } 4201 @Override 4202 public boolean removeIf(Predicate<? super E> filter) { 4203 Objects.requireNonNull(filter); 4204 return false; 4205 } 4206 @Override 4207 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); } 4208 4209 // Preserves singleton property 4210 private Object readResolve() { 4211 return EMPTY_SET; 4212 } 4213 } 4214 4215 /** 4216 * Returns an empty sorted set (immutable). This set is serializable. 4217 * 4218 * <p>This example illustrates the type-safe way to obtain an empty 4219 * sorted set: 4220 * <pre> {@code 4221 * SortedSet<String> s = Collections.emptySortedSet(); 4222 * }</pre> 4223 * 4224 * @implNote Implementations of this method need not create a separate 4225 * {@code SortedSet} object for each call. 4226 * 4227 * @param <E> type of elements, if there were any, in the set 4228 * @return the empty sorted set 4229 * @since 1.8 4230 */ 4231 @SuppressWarnings("unchecked") 4232 public static <E> SortedSet<E> emptySortedSet() { 4233 return (SortedSet<E>) EmptyNavigableSet.EMPTY_NAVIGABLE_SET; 4234 } 4235 4236 /** 4237 * Returns an empty navigable set (immutable). This set is serializable. 4238 * 4239 * <p>This example illustrates the type-safe way to obtain an empty 4240 * navigable set: 4241 * <pre> {@code 4242 * NavigableSet<String> s = Collections.emptyNavigableSet(); 4243 * }</pre> 4244 * 4245 * @implNote Implementations of this method need not 4246 * create a separate {@code NavigableSet} object for each call. 4247 * 4248 * @param <E> type of elements, if there were any, in the set 4249 * @return the empty navigable set 4250 * @since 1.8 4251 */ 4252 @SuppressWarnings("unchecked") 4253 public static <E> NavigableSet<E> emptyNavigableSet() { 4254 return (NavigableSet<E>) EmptyNavigableSet.EMPTY_NAVIGABLE_SET; 4255 } 4256 4257 /** 4258 * The empty list (immutable). This list is serializable. 4259 * 4260 * @see #emptyList() 4261 */ 4262 @SuppressWarnings("rawtypes") 4263 public static final List EMPTY_LIST = new EmptyList<>(); 4264 4265 /** 4266 * Returns the empty list (immutable). This list is serializable. 4267 * 4268 * <p>This example illustrates the type-safe way to obtain an empty list: 4269 * <pre> 4270 * List<String> s = Collections.emptyList(); 4271 * </pre> 4272 * Implementation note: Implementations of this method need not 4273 * create a separate <tt>List</tt> object for each call. Using this 4274 * method is likely to have comparable cost to using the like-named 4275 * field. (Unlike this method, the field does not provide type safety.) 4276 * 4277 * @see #EMPTY_LIST 4278 * @since 1.5 4279 */ 4280 @SuppressWarnings("unchecked") 4281 public static final <T> List<T> emptyList() { 4282 return (List<T>) EMPTY_LIST; 4283 } 4284 4285 /** 4286 * @serial include 4287 */ 4288 private static class EmptyList<E> 4289 extends AbstractList<E> 4290 implements RandomAccess, Serializable { 4291 private static final long serialVersionUID = 8842843931221139166L; 4292 4293 public Iterator<E> iterator() { 4294 return emptyIterator(); 4295 } 4296 public ListIterator<E> listIterator() { 4297 return emptyListIterator(); 4298 } 4299 4300 public int size() {return 0;} 4301 public boolean isEmpty() {return true;} 4302 4303 public boolean contains(Object obj) {return false;} 4304 public boolean containsAll(Collection<?> c) { return c.isEmpty(); } 4305 4306 public Object[] toArray() { return new Object[0]; } 4307 4308 public <T> T[] toArray(T[] a) { 4309 if (a.length > 0) 4310 a[0] = null; 4311 return a; 4312 } 4313 4314 public E get(int index) { 4315 throw new IndexOutOfBoundsException("Index: "+index); 4316 } 4317 4318 public boolean equals(Object o) { 4319 return (o instanceof List) && ((List<?>)o).isEmpty(); 4320 } 4321 4322 public int hashCode() { return 1; } 4323 4324 @Override 4325 public boolean removeIf(Predicate<? super E> filter) { 4326 Objects.requireNonNull(filter); 4327 return false; 4328 } 4329 @Override 4330 public void replaceAll(UnaryOperator<E> operator) { 4331 Objects.requireNonNull(operator); 4332 } 4333 @Override 4334 public void sort(Comparator<? super E> c) { 4335 Objects.requireNonNull(c); 4336 } 4337 4338 // Override default methods in Collection 4339 @Override 4340 public void forEach(Consumer<? super E> action) { 4341 Objects.requireNonNull(action); 4342 } 4343 4344 @Override 4345 public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); } 4346 4347 // Preserves singleton property 4348 private Object readResolve() { 4349 return EMPTY_LIST; 4350 } 4351 } 4352 4353 /** 4354 * An empty navigable map with enforced bounds upon the key set. The bounds 4355 * are generated via the various sub-map operations and enforced on 4356 * subsequent sub-map operations. 4357 * 4358 * @serial include 4359 * 4360 * @param <K> type of keys, if there were any, and bounds 4361 * @param <V> type of values, if there were any 4362 */ 4363 private static class BoundedEmptyNavigableMap<K,V> extends EmptyNavigableMap<K,V> 4364 implements Serializable { 4365 4366 private static final long serialVersionUID = 5065418537829651507L; 4367 4368 /** 4369 * Our bounded keyset. 4370 */ 4371 final BoundedEmptyNavigableSet keySet; 4372 4373 private BoundedEmptyNavigableMap(BoundedEmptyNavigableSet keySet) { 4374 this.keySet = Objects.requireNonNull(keySet); 4375 } 4376 4377 public Comparator<? super K> comparator() 4378 { return keySet.comparator(); } 4379 4380 @Override 4381 public NavigableMap<K, V> descendingMap() { 4382 NavigableSet<K> descending = keySet.descendingSet(); 4383 4384 if(descending == Collections.emptyNavigableSet()) { 4385 return Collections.emptyNavigableMap(); 4386 } else { 4387 return new BoundedEmptyNavigableMap((BoundedEmptyNavigableSet<K>) descending); 4388 } 4389 } 4390 4391 public BoundedEmptyNavigableSet<K> navigableKeySet() { return keySet; } 4392 public EmptyNavigableSet<K> descendingKeySet() 4393 { return keySet.descendingSet(); } 4394 4395 @Override 4396 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 4397 return new BoundedEmptyNavigableMap(keySet.subSet( 4398 fromKey, fromInclusive, 4399 toKey, toInclusive)); 4400 } 4401 4402 @Override 4403 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 4404 return new BoundedEmptyNavigableMap( 4405 keySet.headSet(toKey, inclusive)); 4406 } 4407 4408 @Override 4409 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 4410 return new BoundedEmptyNavigableMap( 4411 keySet.tailSet(fromKey, inclusive)); 4412 } 4413 } 4414 4415 /** 4416 * @serial include 4417 * 4418 * @param <E> type of elements, if there were any 4419 */ 4420 private static class EmptyNavigableSet<E> extends EmptySet<E> 4421 implements NavigableSet<E>, Serializable { 4422 private static final long serialVersionUID = -6291252904449939134L; 4423 4424 @SuppressWarnings("rawtypes") 4425 private static final NavigableSet EMPTY_NAVIGABLE_SET = 4426 new EmptyNavigableSet(); 4427 4428 EmptyNavigableSet() { } 4429 4430 @Override 4431 public boolean contains(Object obj) { 4432 Comparable<E> e = (Comparable<E>) Objects.requireNonNull(obj); 4433 return obj != e; 4434 } 4435 4436 // Preserves singleton property 4437 private Object readResolve() 4438 { return Collections.emptyNavigableSet(); } 4439 public E lower(E e) { return null; } 4440 public E floor(E e) { return null; } 4441 public E ceiling(E e) { return null; } 4442 public E higher(E e) { return null; } 4443 public E pollFirst() { throw new UnsupportedOperationException(); } 4444 public E pollLast() { throw new UnsupportedOperationException(); } 4445 4446 public EmptyNavigableSet<E> descendingSet() { 4447 return new BoundedEmptyNavigableSet(null, false, null, false, true); 4448 } 4449 4450 public Iterator<E> descendingIterator() 4451 { return Collections.emptyIterator(); } 4452 4453 public BoundedEmptyNavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 4454 return new BoundedEmptyNavigableSet<>( 4455 (Comparable<E>) Objects.requireNonNull(fromElement), fromInclusive, 4456 (Comparable<E>) Objects.requireNonNull(toElement), toInclusive, 4457 false); 4458 } 4459 4460 public BoundedEmptyNavigableSet<E> headSet(E toElement, boolean inclusive) { 4461 return new BoundedEmptyNavigableSet<>( 4462 null, false, 4463 (Comparable<E>) Objects.requireNonNull(toElement), inclusive, 4464 false); 4465 } 4466 4467 public BoundedEmptyNavigableSet<E> tailSet(E fromElement, boolean inclusive) { 4468 return new BoundedEmptyNavigableSet<>( 4469 (Comparable<E>) Objects.requireNonNull(fromElement), inclusive, 4470 null, false, 4471 false); 4472 } 4473 4474 public final SortedSet<E> subSet(E fromElement, E toElement) 4475 { return subSet(fromElement, true, toElement, false); } 4476 public final SortedSet<E> headSet(E toElement) 4477 { return headSet(toElement, true); } 4478 public final SortedSet<E> tailSet(E fromElement) 4479 { return tailSet(fromElement, false); } 4480 4481 public Comparator<? super E> comparator() { return null; } 4482 public E first() { throw new NoSuchElementException(); } 4483 public E last() { throw new NoSuchElementException(); } 4484 } 4485 4486 /** 4487 * An empty NavigableSet but bounds are maintained. If you try to sub-set 4488 * outside the bounds you will get an IllegalArgumentException. 4489 * 4490 * @serial include 4491 * 4492 * @param <E> type of elements, if there were any, and bounds 4493 */ 4494 private static class BoundedEmptyNavigableSet<E> extends EmptyNavigableSet<E> 4495 implements Serializable { 4496 private static final long serialVersionUID = 3393358742248855583L; 4497 4498 /** 4499 * {@code true} if lowerBound is "greater" than upperBound. 4500 */ 4501 final boolean descending; 4502 /** 4503 * {@code true} if lowerBound is inclusive. 4504 */ 4505 final boolean lowerInclusive; 4506 /** 4507 * {@code true} if upperBound is inclusive. 4508 */ 4509 final boolean upperInclusive; 4510 /** 4511 * The lower bound of the set. 4512 */ 4513 final Comparable<E> lowerBound; 4514 /** 4515 * The upper bound of the set. 4516 */ 4517 final Comparable<E> upperBound; 4518 4519 public BoundedEmptyNavigableSet( 4520 Comparable<E> fromElement, boolean lowerInclusive, 4521 Comparable<E> toElement, boolean upperInclusive, 4522 boolean descending) { 4523 this.descending = descending; 4524 4525 if ((fromElement != null) && (toElement != null)) { 4526 // both bounds are present we need to ensure that they make 4527 // sense. 4528 int fromCompared = Integer.signum(fromElement.compareTo((E)toElement)); 4529 int toCompared = Integer.signum(toElement.compareTo((E)fromElement)); 4530 4531 if(fromCompared != -toCompared) { 4532 throw new IllegalArgumentException("inconsistent compareTo"); 4533 } 4534 4535 if (descending) { 4536 if (fromCompared < 0) { 4537 throw new IllegalArgumentException(); 4538 } 4539 } else { 4540 if (fromCompared > 0) { 4541 throw new IllegalArgumentException(); 4542 } 4543 } 4544 } 4545 4546 this.lowerBound = fromElement; 4547 this.lowerInclusive = lowerInclusive; 4548 this.upperBound = toElement; 4549 this.upperInclusive = upperInclusive; 4550 } 4551 4552 @Override 4553 public Comparator<? super E> comparator() 4554 { return descending ? Collections.reverseOrder() : null; } 4555 4556 private Comparable<E> inBounds(E element) { 4557 if (!descending) { 4558 if (null != lowerBound) { 4559 if (lowerInclusive) { 4560 if (lowerBound.compareTo(element) > 0) { 4561 throw new IllegalArgumentException("out of bounds"); 4562 } 4563 } else { 4564 if (lowerBound.compareTo(element) >= 0) { 4565 throw new IllegalArgumentException("out of bounds"); 4566 } 4567 } 4568 } 4569 4570 if (null != upperBound) { 4571 if (upperInclusive) { 4572 if (upperBound.compareTo(element) < 0) { 4573 throw new IllegalArgumentException("out of bounds"); 4574 } 4575 } else { 4576 if (upperBound.compareTo(element) <= 0) { 4577 throw new IllegalArgumentException("out of bounds"); 4578 } 4579 } 4580 } 4581 } else { 4582 if (null != lowerBound) { 4583 if (lowerInclusive) { 4584 if (lowerBound.compareTo(element) < 0) { 4585 throw new IllegalArgumentException("out of bounds"); 4586 } 4587 } else { 4588 if (lowerBound.compareTo(element) <= 0) { 4589 throw new IllegalArgumentException("out of bounds"); 4590 } 4591 } 4592 } 4593 4594 if (null != upperBound) { 4595 if (upperInclusive) { 4596 if (upperBound.compareTo(element) > 0) { 4597 throw new IllegalArgumentException("out of bounds"); 4598 } 4599 } else { 4600 if (upperBound.compareTo(element) >= 0) { 4601 throw new IllegalArgumentException("out of bounds"); 4602 } 4603 } 4604 } 4605 } 4606 4607 return (Comparable<E>) Objects.requireNonNull(element); 4608 } 4609 4610 @Override 4611 public EmptyNavigableSet<E> descendingSet() { 4612 if (upperBound == null && lowerBound == null && descending) { 4613 return (EmptyNavigableSet) Collections.emptyNavigableSet(); 4614 } 4615 return new BoundedEmptyNavigableSet( 4616 upperBound, upperInclusive, 4617 lowerBound, lowerInclusive, 4618 !descending); 4619 } 4620 4621 @Override 4622 public BoundedEmptyNavigableSet<E> subSet(E fromKey, boolean fromInclusive, E toKey, boolean toInclusive) { 4623 return new BoundedEmptyNavigableSet( 4624 inBounds(fromKey), fromInclusive, 4625 inBounds(toKey), toInclusive, 4626 descending); 4627 } 4628 4629 @Override 4630 public BoundedEmptyNavigableSet<E> headSet(E toKey, boolean inclusive) { 4631 return new BoundedEmptyNavigableSet( 4632 lowerBound, lowerInclusive, 4633 inBounds(Objects.requireNonNull(toKey)), inclusive, 4634 descending); 4635 } 4636 4637 @Override 4638 public BoundedEmptyNavigableSet<E> tailSet(E fromKey, boolean inclusive) { 4639 return new BoundedEmptyNavigableSet( 4640 inBounds(Objects.requireNonNull(fromKey)), inclusive, 4641 upperBound, upperInclusive, 4642 descending); 4643 } 4644 } 4645 4646 /** 4647 * The empty map (immutable). This map is serializable. 4648 * 4649 * @see #emptyMap() 4650 * @since 1.3 4651 */ 4652 @SuppressWarnings("rawtypes") 4653 public static final Map EMPTY_MAP = new EmptyMap<>(); 4654 4655 /** 4656 * Returns the empty map (immutable). This map is serializable. 4657 * 4658 * <p>This example illustrates the type-safe way to obtain an empty map: 4659 * <pre> 4660 * Map<String, Date> s = Collections.emptyMap(); 4661 * </pre> 4662 * @implNote Implementations of this method need not create a separate 4663 * {@code Map} object for each call. Using this method is likely to have 4664 * comparable cost to using the like-named field. (Unlike this method, the 4665 * field does not provide type safety.) 4666 * 4667 * @return an empty map 4668 * @see #EMPTY_MAP 4669 * @since 1.5 4670 */ 4671 @SuppressWarnings("unchecked") 4672 public static final <K,V> Map<K,V> emptyMap() { 4673 return (Map<K,V>) EMPTY_MAP; 4674 } 4675 4676 /** 4677 * Returns an empty sorted map (immutable). This map is serializable. 4678 * 4679 * <p>This example illustrates the type-safe way to obtain an empty map: 4680 * <pre> {@code 4681 * SortedMap<String, Date> s = Collections.emptySortedMap(); 4682 * }</pre> 4683 * 4684 * @implNote Implementations of this method need not create a separate 4685 * {@code SortedMap} object for each call. 4686 * 4687 * @return an empty sorted map 4688 * @since 1.8 4689 */ 4690 @SuppressWarnings("unchecked") 4691 public static final <K,V> SortedMap<K,V> emptySortedMap() { 4692 return (SortedMap<K,V>) EmptyNavigableMap.EMPTY_NAVIGABLE_MAP; 4693 } 4694 4695 /** 4696 * Returns an empty navigable map (immutable). This map is serializable. 4697 * 4698 * <p>This example illustrates the type-safe way to obtain an empty map: 4699 * <pre> {@code 4700 * NavigableMap<String, Date> s = Collections.emptyNavigableMap(); 4701 * }</pre> 4702 * 4703 * @implNote Implementations of this method need not create a separate 4704 * {@code NavigableMap} object for each call. 4705 * 4706 * @return an empty navigable map 4707 * @since 1.8 4708 */ 4709 @SuppressWarnings("unchecked") 4710 public static final <K,V> NavigableMap<K,V> emptyNavigableMap() { 4711 return (NavigableMap<K,V>) EmptyNavigableMap.EMPTY_NAVIGABLE_MAP; 4712 } 4713 4714 /** 4715 * @serial include 4716 */ 4717 private static class EmptyMap<K,V> 4718 extends AbstractMap<K,V> 4719 implements Serializable 4720 { 4721 private static final long serialVersionUID = 6428348081105594320L; 4722 4723 public int size() {return 0;} 4724 public boolean isEmpty() {return true;} 4725 public boolean containsKey(Object key) {return false;} 4726 public boolean containsValue(Object value) {return false;} 4727 public V get(Object key) {return null;} 4728 public Set<K> keySet() {return emptySet();} 4729 public Collection<V> values() {return emptySet();} 4730 public Set<Map.Entry<K,V>> entrySet() {return emptySet();} 4731 4732 public boolean equals(Object o) { 4733 return (o instanceof Map) && ((Map<?,?>)o).isEmpty(); 4734 } 4735 4736 public int hashCode() {return 0;} 4737 4738 // Override default methods in Map 4739 @Override 4740 @SuppressWarnings("unchecked") 4741 public V getOrDefault(Object k, V defaultValue) { 4742 return defaultValue; 4743 } 4744 4745 @Override 4746 public void forEach(BiConsumer<? super K, ? super V> action) { 4747 Objects.requireNonNull(action); 4748 } 4749 4750 @Override 4751 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 4752 Objects.requireNonNull(function); 4753 } 4754 4755 @Override 4756 public V putIfAbsent(K key, V value) { 4757 throw new UnsupportedOperationException(); 4758 } 4759 4760 @Override 4761 public boolean remove(Object key, Object value) { 4762 throw new UnsupportedOperationException(); 4763 } 4764 4765 @Override 4766 public boolean replace(K key, V oldValue, V newValue) { 4767 throw new UnsupportedOperationException(); 4768 } 4769 4770 @Override 4771 public V replace(K key, V value) { 4772 throw new UnsupportedOperationException(); 4773 } 4774 4775 @Override 4776 public V computeIfAbsent(K key, 4777 Function<? super K, ? extends V> mappingFunction) { 4778 throw new UnsupportedOperationException(); 4779 } 4780 4781 @Override 4782 public V computeIfPresent(K key, 4783 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 4784 throw new UnsupportedOperationException(); 4785 } 4786 4787 @Override 4788 public V compute(K key, 4789 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 4790 throw new UnsupportedOperationException(); 4791 } 4792 4793 @Override 4794 public V merge(K key, V value, 4795 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 4796 throw new UnsupportedOperationException(); 4797 } 4798 4799 // Preserves singleton property 4800 private Object readResolve() { 4801 return EMPTY_MAP; 4802 } 4803 } 4804 4805 /** 4806 * An empty navigable map. 4807 * 4808 * @param <K> type of keys, if there were any in this map 4809 * @param <V> type of values, if there were any in this map 4810 * 4811 * @serial include 4812 */ 4813 private static class EmptyNavigableMap<K,V> extends EmptyMap<K,V> 4814 implements NavigableMap<K,V>, Serializable { 4815 private static final long serialVersionUID = -2239321462712562324L; 4816 4817 @SuppressWarnings("rawtypes") 4818 private static final NavigableMap EMPTY_NAVIGABLE_MAP = 4819 new EmptyNavigableMap(); 4820 4821 EmptyNavigableMap() {} 4822 4823 @Override 4824 public boolean containsKey(Object obj) { 4825 Comparable<K> e = (Comparable<K>) Objects.requireNonNull(obj); 4826 return obj != e; 4827 } 4828 4829 // Preserves singleton property 4830 private Object readResolve() { return Collections.emptyNavigableMap();} 4831 4832 public final K firstKey() { throw new NoSuchElementException(); } 4833 public final K lastKey() { throw new NoSuchElementException(); } 4834 4835 public Entry<K, V> lowerEntry(K key) { 4836 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4837 return null; 4838 } 4839 4840 public K lowerKey(K key) { 4841 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4842 return null; 4843 } 4844 4845 public Entry<K, V> floorEntry(K key) { 4846 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4847 return null; 4848 } 4849 4850 public K floorKey(K key) { 4851 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4852 return null; 4853 } 4854 4855 public Entry<K, V> ceilingEntry(K key) { 4856 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4857 return null; 4858 } 4859 4860 public K ceilingKey(K key) { 4861 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4862 return null; 4863 } 4864 4865 public Entry<K, V> higherEntry(K key) { 4866 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4867 return null; 4868 } 4869 4870 public K higherKey(K key) { 4871 Comparable<K> k = (Comparable<K>) Objects.requireNonNull(key); 4872 return null; 4873 } 4874 4875 public Entry<K, V> firstEntry() { return null; } 4876 public Entry<K, V> lastEntry() { return null; } 4877 public Entry<K, V> pollFirstEntry() 4878 { throw new UnsupportedOperationException(); } 4879 public Entry<K, V> pollLastEntry() 4880 { throw new UnsupportedOperationException(); } 4881 public NavigableMap<K, V> descendingMap() { 4882 EmptyNavigableSet<K> descendingKeys = descendingKeySet(); 4883 4884 if(descendingKeys == emptyNavigableSet()) { 4885 return emptyNavigableMap(); 4886 } else { 4887 return new BoundedEmptyNavigableMap<>((BoundedEmptyNavigableSet<K>) descendingKeys); 4888 } 4889 } 4890 4891 public EmptyNavigableSet<K> navigableKeySet() 4892 { return (EmptyNavigableSet<K>) Collections.emptyNavigableSet(); } 4893 public EmptyNavigableSet<K> descendingKeySet() { 4894 return navigableKeySet().descendingSet(); 4895 } 4896 4897 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 4898 return new BoundedEmptyNavigableMap<>( 4899 ((EmptyNavigableSet<K>) Collections.emptyNavigableSet()).subSet( 4900 fromKey, fromInclusive, 4901 toKey, toInclusive)); 4902 } 4903 4904 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 4905 return new BoundedEmptyNavigableMap<>( 4906 ((EmptyNavigableSet<K>) Collections.emptyNavigableSet()) 4907 .headSet(toKey, inclusive)); 4908 } 4909 4910 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 4911 return new BoundedEmptyNavigableMap<>( 4912 ((EmptyNavigableSet<K>) Collections.emptyNavigableSet()) 4913 .tailSet(fromKey, inclusive)); 4914 } 4915 4916 public final SortedMap<K, V> subMap(K fromKey, K toKey) 4917 { return subMap(fromKey, true, toKey, false); } 4918 4919 public final SortedMap<K, V> headMap(K toKey) 4920 { return headMap(toKey, true); } 4921 4922 public final SortedMap<K, V> tailMap(K fromKey) 4923 { return tailMap(fromKey, false); } 4924 4925 public Comparator<? super K> comparator() { return null; } 4926 } 4927 4928 // Singleton collections 4929 4930 /** 4931 * Returns an immutable set containing only the specified object. 4932 * The returned set is serializable. 4933 * 4934 * @param o the sole object to be stored in the returned set. 4935 * @return an immutable set containing only the specified object. 4936 */ 4937 public static <T> Set<T> singleton(T o) { 4938 return new SingletonSet<>(o); 4939 } 4940 4941 static <E> Iterator<E> singletonIterator(final E e) { 4942 return new Iterator<E>() { 4943 private boolean hasNext = true; 4944 public boolean hasNext() { 4945 return hasNext; 4946 } 4947 public E next() { 4948 if (hasNext) { 4949 hasNext = false; 4950 return e; 4951 } 4952 throw new NoSuchElementException(); 4953 } 4954 public void remove() { 4955 throw new UnsupportedOperationException(); 4956 } 4957 @Override 4958 public void forEachRemaining(Consumer<? super E> action) { 4959 Objects.requireNonNull(action); 4960 if (hasNext) { 4961 action.accept(e); 4962 hasNext = false; 4963 } 4964 } 4965 }; 4966 } 4967 4968 /** 4969 * Creates a {@code Spliterator} with only the specified element 4970 * 4971 * @param <T> Type of elements 4972 * @return A singleton {@code Spliterator} 4973 */ 4974 static <T> Spliterator<T> singletonSpliterator(final T element) { 4975 return new Spliterator<T>() { 4976 long est = 1; 4977 4978 @Override 4979 public Spliterator<T> trySplit() { 4980 return null; 4981 } 4982 4983 @Override 4984 public boolean tryAdvance(Consumer<? super T> consumer) { 4985 Objects.requireNonNull(consumer); 4986 if (est > 0) { 4987 est--; 4988 consumer.accept(element); 4989 return true; 4990 } 4991 return false; 4992 } 4993 4994 @Override 4995 public void forEachRemaining(Consumer<? super T> consumer) { 4996 tryAdvance(consumer); 4997 } 4998 4999 @Override 5000 public long estimateSize() { 5001 return est; 5002 } 5003 5004 @Override 5005 public int characteristics() { 5006 int value = (element != null) ? Spliterator.NONNULL : 0; 5007 5008 return value | Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE | 5009 Spliterator.DISTINCT | Spliterator.ORDERED; 5010 } 5011 }; 5012 } 5013 5014 /** 5015 * @serial include 5016 */ 5017 private static class SingletonSet<E> 5018 extends AbstractSet<E> 5019 implements Serializable 5020 { 5021 private static final long serialVersionUID = 3193687207550431679L; 5022 5023 private final E element; 5024 5025 SingletonSet(E e) {element = e;} 5026 5027 public Iterator<E> iterator() { 5028 return singletonIterator(element); 5029 } 5030 5031 public int size() {return 1;} 5032 5033 public boolean contains(Object o) {return eq(o, element);} 5034 5035 // Override default methods for Collection 5036 @Override 5037 public void forEach(Consumer<? super E> action) { 5038 action.accept(element); 5039 } 5040 @Override 5041 public Spliterator<E> spliterator() { 5042 return singletonSpliterator(element); 5043 } 5044 @Override 5045 public boolean removeIf(Predicate<? super E> filter) { 5046 throw new UnsupportedOperationException(); 5047 } 5048 } 5049 5050 /** 5051 * Returns an immutable list containing only the specified object. 5052 * The returned list is serializable. 5053 * 5054 * @param o the sole object to be stored in the returned list. 5055 * @return an immutable list containing only the specified object. 5056 * @since 1.3 5057 */ 5058 public static <T> List<T> singletonList(T o) { 5059 return new SingletonList<>(o); 5060 } 5061 5062 /** 5063 * @serial include 5064 */ 5065 private static class SingletonList<E> 5066 extends AbstractList<E> 5067 implements RandomAccess, Serializable { 5068 5069 private static final long serialVersionUID = 3093736618740652951L; 5070 5071 private final E element; 5072 5073 SingletonList(E obj) {element = obj;} 5074 5075 public Iterator<E> iterator() { 5076 return singletonIterator(element); 5077 } 5078 5079 public int size() {return 1;} 5080 5081 public boolean contains(Object obj) {return eq(obj, element);} 5082 5083 public E get(int index) { 5084 if (index != 0) 5085 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); 5086 return element; 5087 } 5088 5089 // Override default methods for Collection 5090 @Override 5091 public void forEach(Consumer<? super E> action) { 5092 action.accept(element); 5093 } 5094 @Override 5095 public boolean removeIf(Predicate<? super E> filter) { 5096 throw new UnsupportedOperationException(); 5097 } 5098 @Override 5099 public void replaceAll(UnaryOperator<E> operator) { 5100 throw new UnsupportedOperationException(); 5101 } 5102 @Override 5103 public void sort(Comparator<? super E> c) { 5104 } 5105 @Override 5106 public Spliterator<E> spliterator() { 5107 return singletonSpliterator(element); 5108 } 5109 } 5110 5111 /** 5112 * Returns an immutable map, mapping only the specified key to the 5113 * specified value. The returned map is serializable. 5114 * 5115 * @param key the sole key to be stored in the returned map. 5116 * @param value the value to which the returned map maps <tt>key</tt>. 5117 * @return an immutable map containing only the specified key-value 5118 * mapping. 5119 * @since 1.3 5120 */ 5121 public static <K,V> Map<K,V> singletonMap(K key, V value) { 5122 return new SingletonMap<>(key, value); 5123 } 5124 5125 /** 5126 * @serial include 5127 */ 5128 private static class SingletonMap<K,V> 5129 extends AbstractMap<K,V> 5130 implements Serializable { 5131 private static final long serialVersionUID = -6979724477215052911L; 5132 5133 private final K k; 5134 private final V v; 5135 5136 SingletonMap(K key, V value) { 5137 k = key; 5138 v = value; 5139 } 5140 5141 public int size() {return 1;} 5142 public boolean isEmpty() {return false;} 5143 public boolean containsKey(Object key) {return eq(key, k);} 5144 public boolean containsValue(Object value) {return eq(value, v);} 5145 public V get(Object key) {return (eq(key, k) ? v : null);} 5146 5147 private transient Set<K> keySet = null; 5148 private transient Set<Map.Entry<K,V>> entrySet = null; 5149 private transient Collection<V> values = null; 5150 5151 public Set<K> keySet() { 5152 if (keySet==null) 5153 keySet = singleton(k); 5154 return keySet; 5155 } 5156 5157 public Set<Map.Entry<K,V>> entrySet() { 5158 if (entrySet==null) 5159 entrySet = Collections.<Map.Entry<K,V>>singleton( 5160 new SimpleImmutableEntry<>(k, v)); 5161 return entrySet; 5162 } 5163 5164 public Collection<V> values() { 5165 if (values==null) 5166 values = singleton(v); 5167 return values; 5168 } 5169 5170 // Override default methods in Map 5171 @Override 5172 public V getOrDefault(Object key, V defaultValue) { 5173 return eq(key, k) ? v : defaultValue; 5174 } 5175 5176 @Override 5177 public void forEach(BiConsumer<? super K, ? super V> action) { 5178 action.accept(k, v); 5179 } 5180 5181 @Override 5182 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 5183 throw new UnsupportedOperationException(); 5184 } 5185 5186 @Override 5187 public V putIfAbsent(K key, V value) { 5188 throw new UnsupportedOperationException(); 5189 } 5190 5191 @Override 5192 public boolean remove(Object key, Object value) { 5193 throw new UnsupportedOperationException(); 5194 } 5195 5196 @Override 5197 public boolean replace(K key, V oldValue, V newValue) { 5198 throw new UnsupportedOperationException(); 5199 } 5200 5201 @Override 5202 public V replace(K key, V value) { 5203 throw new UnsupportedOperationException(); 5204 } 5205 5206 @Override 5207 public V computeIfAbsent(K key, 5208 Function<? super K, ? extends V> mappingFunction) { 5209 throw new UnsupportedOperationException(); 5210 } 5211 5212 @Override 5213 public V computeIfPresent(K key, 5214 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 5215 throw new UnsupportedOperationException(); 5216 } 5217 5218 @Override 5219 public V compute(K key, 5220 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 5221 throw new UnsupportedOperationException(); 5222 } 5223 5224 @Override 5225 public V merge(K key, V value, 5226 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 5227 throw new UnsupportedOperationException(); 5228 } 5229 } 5230 5231 // Miscellaneous 5232 5233 /** 5234 * Returns an immutable list consisting of <tt>n</tt> copies of the 5235 * specified object. The newly allocated data object is tiny (it contains 5236 * a single reference to the data object). This method is useful in 5237 * combination with the <tt>List.addAll</tt> method to grow lists. 5238 * The returned list is serializable. 5239 * 5240 * @param n the number of elements in the returned list. 5241 * @param o the element to appear repeatedly in the returned list. 5242 * @return an immutable list consisting of <tt>n</tt> copies of the 5243 * specified object. 5244 * @throws IllegalArgumentException if {@code n < 0} 5245 * @see List#addAll(Collection) 5246 * @see List#addAll(int, Collection) 5247 */ 5248 public static <T> List<T> nCopies(int n, T o) { 5249 if (n < 0) 5250 throw new IllegalArgumentException("List length = " + n); 5251 return new CopiesList<>(n, o); 5252 } 5253 5254 /** 5255 * @serial include 5256 */ 5257 private static class CopiesList<E> 5258 extends AbstractList<E> 5259 implements RandomAccess, Serializable 5260 { 5261 private static final long serialVersionUID = 2739099268398711800L; 5262 5263 final int n; 5264 final E element; 5265 5266 CopiesList(int n, E e) { 5267 assert n >= 0; 5268 this.n = n; 5269 element = e; 5270 } 5271 5272 public int size() { 5273 return n; 5274 } 5275 5276 public boolean contains(Object obj) { 5277 return n != 0 && eq(obj, element); 5278 } 5279 5280 public int indexOf(Object o) { 5281 return contains(o) ? 0 : -1; 5282 } 5283 5284 public int lastIndexOf(Object o) { 5285 return contains(o) ? n - 1 : -1; 5286 } 5287 5288 public E get(int index) { 5289 if (index < 0 || index >= n) 5290 throw new IndexOutOfBoundsException("Index: "+index+ 5291 ", Size: "+n); 5292 return element; 5293 } 5294 5295 public Object[] toArray() { 5296 final Object[] a = new Object[n]; 5297 if (element != null) 5298 Arrays.fill(a, 0, n, element); 5299 return a; 5300 } 5301 5302 @SuppressWarnings("unchecked") 5303 public <T> T[] toArray(T[] a) { 5304 final int n = this.n; 5305 if (a.length < n) { 5306 a = (T[])java.lang.reflect.Array 5307 .newInstance(a.getClass().getComponentType(), n); 5308 if (element != null) 5309 Arrays.fill(a, 0, n, element); 5310 } else { 5311 Arrays.fill(a, 0, n, element); 5312 if (a.length > n) 5313 a[n] = null; 5314 } 5315 return a; 5316 } 5317 5318 public List<E> subList(int fromIndex, int toIndex) { 5319 if (fromIndex < 0) 5320 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 5321 if (toIndex > n) 5322 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 5323 if (fromIndex > toIndex) 5324 throw new IllegalArgumentException("fromIndex(" + fromIndex + 5325 ") > toIndex(" + toIndex + ")"); 5326 return new CopiesList<>(toIndex - fromIndex, element); 5327 } 5328 } 5329 5330 /** 5331 * Returns a comparator that imposes the reverse of the <em>natural 5332 * ordering</em> on a collection of objects that implement the 5333 * {@code Comparable} interface. (The natural ordering is the ordering 5334 * imposed by the objects' own {@code compareTo} method.) This enables a 5335 * simple idiom for sorting (or maintaining) collections (or arrays) of 5336 * objects that implement the {@code Comparable} interface in 5337 * reverse-natural-order. For example, suppose {@code a} is an array of 5338 * strings. Then: <pre> 5339 * Arrays.sort(a, Collections.reverseOrder()); 5340 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p> 5341 * 5342 * The returned comparator is serializable. 5343 * 5344 * @return A comparator that imposes the reverse of the <i>natural 5345 * ordering</i> on a collection of objects that implement 5346 * the <tt>Comparable</tt> interface. 5347 * @see Comparable 5348 */ 5349 @SuppressWarnings("unchecked") 5350 public static <T> Comparator<T> reverseOrder() { 5351 return (Comparator<T>) ReverseComparator.REVERSE_ORDER; 5352 } 5353 5354 /** 5355 * @serial include 5356 */ 5357 private static class ReverseComparator 5358 implements Comparator<Comparable<Object>>, Serializable { 5359 5360 private static final long serialVersionUID = 7207038068494060240L; 5361 5362 static final ReverseComparator REVERSE_ORDER 5363 = new ReverseComparator(); 5364 5365 public int compare(Comparable<Object> c1, Comparable<Object> c2) { 5366 return c2.compareTo(c1); 5367 } 5368 5369 private Object readResolve() { return Collections.reverseOrder(); } 5370 } 5371 5372 /** 5373 * Returns a comparator that imposes the reverse ordering of the specified 5374 * comparator. If the specified comparator is {@code null}, this method is 5375 * equivalent to {@link #reverseOrder()} (in other words, it returns a 5376 * comparator that imposes the reverse of the <em>natural ordering</em> on 5377 * a collection of objects that implement the Comparable interface). 5378 * 5379 * <p>The returned comparator is serializable (assuming the specified 5380 * comparator is also serializable or {@code null}). 5381 * 5382 * @param cmp a comparator who's ordering is to be reversed by the returned 5383 * comparator or {@code null} 5384 * @return A comparator that imposes the reverse ordering of the 5385 * specified comparator. 5386 * @since 1.5 5387 */ 5388 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) { 5389 if (cmp == null) 5390 return reverseOrder(); 5391 5392 if (cmp instanceof ReverseComparator2) 5393 return ((ReverseComparator2<T>)cmp).cmp; 5394 5395 return new ReverseComparator2<>(cmp); 5396 } 5397 5398 /** 5399 * @serial include 5400 */ 5401 private static class ReverseComparator2<T> implements Comparator<T>, 5402 Serializable 5403 { 5404 private static final long serialVersionUID = 4374092139857L; 5405 5406 /** 5407 * The comparator specified in the static factory. This will never 5408 * be null, as the static factory returns a ReverseComparator 5409 * instance if its argument is null. 5410 * 5411 * @serial 5412 */ 5413 final Comparator<T> cmp; 5414 5415 ReverseComparator2(Comparator<T> cmp) { 5416 assert cmp != null; 5417 this.cmp = cmp; 5418 } 5419 5420 public int compare(T t1, T t2) { 5421 return cmp.compare(t2, t1); 5422 } 5423 5424 public boolean equals(Object o) { 5425 return (o == this) || 5426 (o instanceof ReverseComparator2 && 5427 cmp.equals(((ReverseComparator2)o).cmp)); 5428 } 5429 5430 public int hashCode() { 5431 return cmp.hashCode() ^ Integer.MIN_VALUE; 5432 } 5433 } 5434 5435 /** 5436 * Returns an enumeration over the specified collection. This provides 5437 * interoperability with legacy APIs that require an enumeration 5438 * as input. 5439 * 5440 * @param c the collection for which an enumeration is to be returned. 5441 * @return an enumeration over the specified collection. 5442 * @see Enumeration 5443 */ 5444 public static <T> Enumeration<T> enumeration(final Collection<T> c) { 5445 return new Enumeration<T>() { 5446 private final Iterator<T> i = c.iterator(); 5447 5448 public boolean hasMoreElements() { 5449 return i.hasNext(); 5450 } 5451 5452 public T nextElement() { 5453 return i.next(); 5454 } 5455 }; 5456 } 5457 5458 /** 5459 * Returns an array list containing the elements returned by the 5460 * specified enumeration in the order they are returned by the 5461 * enumeration. This method provides interoperability between 5462 * legacy APIs that return enumerations and new APIs that require 5463 * collections. 5464 * 5465 * @param e enumeration providing elements for the returned 5466 * array list 5467 * @return an array list containing the elements returned 5468 * by the specified enumeration. 5469 * @since 1.4 5470 * @see Enumeration 5471 * @see ArrayList 5472 */ 5473 public static <T> ArrayList<T> list(Enumeration<T> e) { 5474 ArrayList<T> l = new ArrayList<>(); 5475 while (e.hasMoreElements()) 5476 l.add(e.nextElement()); 5477 return l; 5478 } 5479 5480 /** 5481 * Returns true if the specified arguments are equal, or both null. 5482 */ 5483 static boolean eq(Object o1, Object o2) { 5484 return o1==null ? o2==null : o1.equals(o2); 5485 } 5486 5487 /** 5488 * Returns the number of elements in the specified collection equal to the 5489 * specified object. More formally, returns the number of elements 5490 * <tt>e</tt> in the collection such that 5491 * <tt>(o == null ? e == null : o.equals(e))</tt>. 5492 * 5493 * @param c the collection in which to determine the frequency 5494 * of <tt>o</tt> 5495 * @param o the object whose frequency is to be determined 5496 * @throws NullPointerException if <tt>c</tt> is null 5497 * @since 1.5 5498 */ 5499 public static int frequency(Collection<?> c, Object o) { 5500 int result = 0; 5501 if (o == null) { 5502 for (Object e : c) 5503 if (e == null) 5504 result++; 5505 } else { 5506 for (Object e : c) 5507 if (o.equals(e)) 5508 result++; 5509 } 5510 return result; 5511 } 5512 5513 /** 5514 * Returns {@code true} if the two specified collections have no 5515 * elements in common. 5516 * 5517 * <p>Care must be exercised if this method is used on collections that 5518 * do not comply with the general contract for {@code Collection}. 5519 * Implementations may elect to iterate over either collection and test 5520 * for containment in the other collection (or to perform any equivalent 5521 * computation). If either collection uses a nonstandard equality test 5522 * (as does a {@link SortedSet} whose ordering is not <em>compatible with 5523 * equals</em>, or the key set of an {@link IdentityHashMap}), both 5524 * collections must use the same nonstandard equality test, or the 5525 * result of this method is undefined. 5526 * 5527 * <p>Care must also be exercised when using collections that have 5528 * restrictions on the elements that they may contain. Collection 5529 * implementations are allowed to throw exceptions for any operation 5530 * involving elements they deem ineligible. For absolute safety the 5531 * specified collections should contain only elements which are 5532 * eligible elements for both collections. 5533 * 5534 * <p>Note that it is permissible to pass the same collection in both 5535 * parameters, in which case the method will return {@code true} if and 5536 * only if the collection is empty. 5537 * 5538 * @param c1 a collection 5539 * @param c2 a collection 5540 * @return {@code true} if the two specified collections have no 5541 * elements in common. 5542 * @throws NullPointerException if either collection is {@code null}. 5543 * @throws NullPointerException if one collection contains a {@code null} 5544 * element and {@code null} is not an eligible element for the other collection. 5545 * (<a href="Collection.html#optional-restrictions">optional</a>) 5546 * @throws ClassCastException if one collection contains an element that is 5547 * of a type which is ineligible for the other collection. 5548 * (<a href="Collection.html#optional-restrictions">optional</a>) 5549 * @since 1.5 5550 */ 5551 public static boolean disjoint(Collection<?> c1, Collection<?> c2) { 5552 // The collection to be used for contains(). Preference is given to 5553 // the collection who's contains() has lower O() complexity. 5554 Collection<?> contains = c2; 5555 // The collection to be iterated. If the collections' contains() impl 5556 // are of different O() complexity, the collection with slower 5557 // contains() will be used for iteration. For collections who's 5558 // contains() are of the same complexity then best performance is 5559 // achieved by iterating the smaller collection. 5560 Collection<?> iterate = c1; 5561 5562 // Performance optimization cases. The heuristics: 5563 // 1. Generally iterate over c1. 5564 // 2. If c1 is a Set then iterate over c2. 5565 // 3. If either collection is empty then result is always true. 5566 // 4. Iterate over the smaller Collection. 5567 if (c1 instanceof Set) { 5568 // Use c1 for contains as a Set's contains() is expected to perform 5569 // better than O(N/2) 5570 iterate = c2; 5571 contains = c1; 5572 } else if (!(c2 instanceof Set)) { 5573 // Both are mere Collections. Iterate over smaller collection. 5574 // Example: If c1 contains 3 elements and c2 contains 50 elements and 5575 // assuming contains() requires ceiling(N/2) comparisons then 5576 // checking for all c1 elements in c2 would require 75 comparisons 5577 // (3 * ceiling(50/2)) vs. checking all c2 elements in c1 requiring 5578 // 100 comparisons (50 * ceiling(3/2)). 5579 int c1size = c1.size(); 5580 int c2size = c2.size(); 5581 if (c1size == 0 || c2size == 0) { 5582 // At least one collection is empty. Nothing will match. 5583 return true; 5584 } 5585 5586 if (c1size > c2size) { 5587 iterate = c2; 5588 contains = c1; 5589 } 5590 } 5591 5592 for (Object e : iterate) { 5593 if (contains.contains(e)) { 5594 // Found a common element. Collections are not disjoint. 5595 return false; 5596 } 5597 } 5598 5599 // No common elements were found. 5600 return true; 5601 } 5602 5603 /** 5604 * Adds all of the specified elements to the specified collection. 5605 * Elements to be added may be specified individually or as an array. 5606 * The behavior of this convenience method is identical to that of 5607 * <tt>c.addAll(Arrays.asList(elements))</tt>, but this method is likely 5608 * to run significantly faster under most implementations. 5609 * 5610 * <p>When elements are specified individually, this method provides a 5611 * convenient way to add a few elements to an existing collection: 5612 * <pre> 5613 * Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon"); 5614 * </pre> 5615 * 5616 * @param c the collection into which <tt>elements</tt> are to be inserted 5617 * @param elements the elements to insert into <tt>c</tt> 5618 * @return <tt>true</tt> if the collection changed as a result of the call 5619 * @throws UnsupportedOperationException if <tt>c</tt> does not support 5620 * the <tt>add</tt> operation 5621 * @throws NullPointerException if <tt>elements</tt> contains one or more 5622 * null values and <tt>c</tt> does not permit null elements, or 5623 * if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt> 5624 * @throws IllegalArgumentException if some property of a value in 5625 * <tt>elements</tt> prevents it from being added to <tt>c</tt> 5626 * @see Collection#addAll(Collection) 5627 * @since 1.5 5628 */ 5629 @SafeVarargs 5630 public static <T> boolean addAll(Collection<? super T> c, T... elements) { 5631 boolean result = false; 5632 for (T element : elements) 5633 result |= c.add(element); 5634 return result; 5635 } 5636 5637 /** 5638 * Returns a set backed by the specified map. The resulting set displays 5639 * the same ordering, concurrency, and performance characteristics as the 5640 * backing map. In essence, this factory method provides a {@link Set} 5641 * implementation corresponding to any {@link Map} implementation. There 5642 * is no need to use this method on a {@link Map} implementation that 5643 * already has a corresponding {@link Set} implementation (such as {@link 5644 * HashMap} or {@link TreeMap}). 5645 * 5646 * <p>Each method invocation on the set returned by this method results in 5647 * exactly one method invocation on the backing map or its <tt>keySet</tt> 5648 * view, with one exception. The <tt>addAll</tt> method is implemented 5649 * as a sequence of <tt>put</tt> invocations on the backing map. 5650 * 5651 * <p>The specified map must be empty at the time this method is invoked, 5652 * and should not be accessed directly after this method returns. These 5653 * conditions are ensured if the map is created empty, passed directly 5654 * to this method, and no reference to the map is retained, as illustrated 5655 * in the following code fragment: 5656 * <pre> 5657 * Set<Object> weakHashSet = Collections.newSetFromMap( 5658 * new WeakHashMap<Object, Boolean>()); 5659 * </pre> 5660 * 5661 * @param map the backing map 5662 * @return the set backed by the map 5663 * @throws IllegalArgumentException if <tt>map</tt> is not empty 5664 * @since 1.6 5665 */ 5666 public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 5667 return new SetFromMap<>(map); 5668 } 5669 5670 /** 5671 * @serial include 5672 */ 5673 private static class SetFromMap<E> extends AbstractSet<E> 5674 implements Set<E>, Serializable 5675 { 5676 private final Map<E, Boolean> m; // The backing map 5677 private transient Set<E> s; // Its keySet 5678 5679 SetFromMap(Map<E, Boolean> map) { 5680 if (!map.isEmpty()) 5681 throw new IllegalArgumentException("Map is non-empty"); 5682 m = map; 5683 s = map.keySet(); 5684 } 5685 5686 public void clear() { m.clear(); } 5687 public int size() { return m.size(); } 5688 public boolean isEmpty() { return m.isEmpty(); } 5689 public boolean contains(Object o) { return m.containsKey(o); } 5690 public boolean remove(Object o) { return m.remove(o) != null; } 5691 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } 5692 public Iterator<E> iterator() { return s.iterator(); } 5693 public Object[] toArray() { return s.toArray(); } 5694 public <T> T[] toArray(T[] a) { return s.toArray(a); } 5695 public String toString() { return s.toString(); } 5696 public int hashCode() { return s.hashCode(); } 5697 public boolean equals(Object o) { return o == this || s.equals(o); } 5698 public boolean containsAll(Collection<?> c) {return s.containsAll(c);} 5699 public boolean removeAll(Collection<?> c) {return s.removeAll(c);} 5700 public boolean retainAll(Collection<?> c) {return s.retainAll(c);} 5701 // addAll is the only inherited implementation 5702 5703 // Override default methods in Collection 5704 @Override 5705 public void forEach(Consumer<? super E> action) { 5706 s.forEach(action); 5707 } 5708 @Override 5709 public boolean removeIf(Predicate<? super E> filter) { 5710 return s.removeIf(filter); 5711 } 5712 5713 @Override 5714 public Spliterator<E> spliterator() {return s.spliterator();} 5715 5716 private static final long serialVersionUID = 2454657854757543876L; 5717 5718 private void readObject(java.io.ObjectInputStream stream) 5719 throws IOException, ClassNotFoundException 5720 { 5721 stream.defaultReadObject(); 5722 s = m.keySet(); 5723 } 5724 } 5725 5726 /** 5727 * Returns a navigable set backed by the specified map. The resulting 5728 * navigable set displays the same ordering, concurrency, and performance 5729 * characteristics as the backing map. In essence, this factory method 5730 * provides a {@link NavigableSet} implementation corresponding to any 5731 * {@link NavigableMap} implementation. There is no need to use this method 5732 * on a {@link NavigableMap} implementation that already has a corresponding 5733 * {@link Set} implementation (such as {@link TreeMap}). 5734 * 5735 * <p>Each method invocation on the set returned by this method results in 5736 * exactly one method invocation on the backing map or its {@code keySet} 5737 * view, with one exception. The {@code addAll} method is implemented 5738 * as a sequence of {@code put} invocations on the backing map. 5739 * 5740 * <p>The specified map must be empty at the time this method is invoked, 5741 * and should not be accessed directly after this method returns. These 5742 * conditions are ensured if the map is created empty, passed directly 5743 * to this method, and no reference to the map is retained, as illustrated 5744 * in the following code fragment: 5745 * <pre> {@code 5746 * Set<Object> weakHashSet = Collections.newNavigableSetFromNavigableMap( 5747 * new WeakHashMap<Object, Boolean>()); 5748 * }</pre> 5749 * 5750 * @param map the backing navigable map 5751 * @return the navigable set backed by the map 5752 * @throws IllegalArgumentException if {@code map} is not empty 5753 * @since 1.8 5754 */ 5755 public static <E> NavigableSet<E> newNavigableSetFromNavigableMap(NavigableMap<E, Boolean> map) { 5756 return new NavigableSetFromNavigableMap<>(map); 5757 } 5758 5759 /** 5760 * @serial include 5761 */ 5762 private static class NavigableSetFromNavigableMap<E> extends AbstractSet<E> 5763 implements NavigableSet<E>, Serializable 5764 { 5765 private static final long serialVersionUID = -7303807726339382839L; 5766 5767 private final NavigableMap<E, Boolean> m; // The backing map 5768 private transient NavigableSet<E> s; // Its keySet 5769 5770 NavigableSetFromNavigableMap(NavigableMap<E, Boolean> map) { 5771 if (!map.isEmpty()) 5772 throw new IllegalArgumentException("Map is non-empty"); 5773 m = map; 5774 s = map.navigableKeySet(); 5775 } 5776 5777 public void clear() { m.clear(); } 5778 public int size() { return m.size(); } 5779 public boolean isEmpty() { return m.isEmpty(); } 5780 public boolean contains(Object o) { return m.containsKey(o); } 5781 public boolean remove(Object o) { return m.remove(o) != null; } 5782 public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; } 5783 public Iterator<E> iterator() { return s.iterator(); } 5784 public Object[] toArray() { return s.toArray(); } 5785 public <T> T[] toArray(T[] a) { return s.toArray(a); } 5786 public String toString() { return s.toString(); } 5787 public int hashCode() { return s.hashCode(); } 5788 public boolean equals(Object o) { return o == this || s.equals(o); } 5789 public boolean containsAll(Collection<?> c) {return s.containsAll(c);} 5790 public boolean removeAll(Collection<?> c) {return s.removeAll(c);} 5791 public boolean retainAll(Collection<?> c) {return s.retainAll(c);} 5792 // addAll is the only inherited implementation 5793 5794 // Override default methods in Collection 5795 @Override 5796 public void forEach(Consumer<? super E> action) { s.forEach(action); } 5797 @Override 5798 public boolean removeIf(Predicate<? super E> filter) { 5799 return s.removeIf(filter); 5800 } 5801 5802 @Override 5803 public Spliterator<E> spliterator() {return s.spliterator();} 5804 5805 private void readObject(java.io.ObjectInputStream stream) 5806 throws IOException, ClassNotFoundException { 5807 stream.defaultReadObject(); 5808 if (null == m) { 5809 throw new InvalidObjectException("null map"); 5810 } 5811 s = m.navigableKeySet(); 5812 } 5813 5814 public E lower(E e) { return m.lowerKey(e); } 5815 public E floor(E e) { return m.floorKey(e); } 5816 public E ceiling(E e) { return m.ceilingKey(e); } 5817 public E higher(E e) { return m.higherKey(e); } 5818 public E pollFirst() { return s.pollFirst(); } 5819 public E pollLast() { return s.pollLast(); } 5820 public NavigableSet<E> descendingSet() { return s.descendingSet(); } 5821 public Iterator<E> descendingIterator(){return s.descendingIterator();} 5822 5823 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 5824 return s.subSet(fromElement, fromInclusive, toElement, toInclusive); 5825 } 5826 5827 public NavigableSet<E> headSet(E toElement, boolean inclusive) 5828 { return s.headSet(toElement, inclusive); } 5829 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) 5830 { return s.tailSet(fromElement, inclusive); } 5831 public SortedSet<E> subSet(E fromElement, E toElement) 5832 { return s.subSet(fromElement, toElement); } 5833 public SortedSet<E> headSet(E toElement) 5834 { return s.headSet(toElement); } 5835 public SortedSet<E> tailSet(E fromElement) 5836 { return s.tailSet(fromElement); } 5837 public Comparator<? super E> comparator() { return s.comparator(); } 5838 public E first() { return s.first(); } 5839 public E last() { return s.last(); } 5840 } 5841 5842 /** 5843 * Returns a view of a {@link Deque} as a Last-in-first-out (Lifo) 5844 * {@link Queue}. Method <tt>add</tt> is mapped to <tt>push</tt>, 5845 * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This 5846 * view can be useful when you would like to use a method 5847 * requiring a <tt>Queue</tt> but you need Lifo ordering. 5848 * 5849 * <p>Each method invocation on the queue returned by this method 5850 * results in exactly one method invocation on the backing deque, with 5851 * one exception. The {@link Queue#addAll addAll} method is 5852 * implemented as a sequence of {@link Deque#addFirst addFirst} 5853 * invocations on the backing deque. 5854 * 5855 * @param deque the deque 5856 * @return the queue 5857 * @since 1.6 5858 */ 5859 public static <T> Queue<T> asLifoQueue(Deque<T> deque) { 5860 return new AsLIFOQueue<>(deque); 5861 } 5862 5863 /** 5864 * @serial include 5865 */ 5866 static class AsLIFOQueue<E> extends AbstractQueue<E> 5867 implements Queue<E>, Serializable { 5868 private static final long serialVersionUID = 1802017725587941708L; 5869 private final Deque<E> q; 5870 AsLIFOQueue(Deque<E> q) { this.q = q; } 5871 public boolean add(E e) { q.addFirst(e); return true; } 5872 public boolean offer(E e) { return q.offerFirst(e); } 5873 public E poll() { return q.pollFirst(); } 5874 public E remove() { return q.removeFirst(); } 5875 public E peek() { return q.peekFirst(); } 5876 public E element() { return q.getFirst(); } 5877 public void clear() { q.clear(); } 5878 public int size() { return q.size(); } 5879 public boolean isEmpty() { return q.isEmpty(); } 5880 public boolean contains(Object o) { return q.contains(o); } 5881 public boolean remove(Object o) { return q.remove(o); } 5882 public Iterator<E> iterator() { return q.iterator(); } 5883 public Object[] toArray() { return q.toArray(); } 5884 public <T> T[] toArray(T[] a) { return q.toArray(a); } 5885 public String toString() { return q.toString(); } 5886 public boolean containsAll(Collection<?> c) {return q.containsAll(c);} 5887 public boolean removeAll(Collection<?> c) {return q.removeAll(c);} 5888 public boolean retainAll(Collection<?> c) {return q.retainAll(c);} 5889 // We use inherited addAll; forwarding addAll would be wrong 5890 5891 // Override default methods in Collection 5892 @Override 5893 public void forEach(Consumer<? super E> action) {q.forEach(action);} 5894 @Override 5895 public Spliterator<E> spliterator() {return q.spliterator();} 5896 @Override 5897 public boolean removeIf(Predicate<? super E> filter) { 5898 return q.removeIf(filter); 5899 } 5900 } 5901 }