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