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