001 package railo.commons.collections; 002 003 import java.io.Serializable; 004 import java.util.AbstractList; 005 import java.util.AbstractMap; 006 import java.util.AbstractSet; 007 import java.util.ArrayList; 008 import java.util.Arrays; 009 import java.util.Collection; 010 import java.util.Comparator; 011 import java.util.Enumeration; 012 import java.util.Iterator; 013 import java.util.List; 014 import java.util.ListIterator; 015 import java.util.Map; 016 import java.util.NoSuchElementException; 017 import java.util.Random; 018 import java.util.RandomAccess; 019 import java.util.Set; 020 import java.util.SortedMap; 021 import java.util.SortedSet; 022 023 public final class Collections { 024 // Suppresses default constructor, ensuring non-instantiability. 025 private Collections() { 026 } 027 028 // Algorithms 029 030 /* 031 * Tuning parameters for algorithms - Many of the List algorithms have 032 * two implementations, one of which is appropriate for RandomAccess 033 * lists, the other for "sequential." Often, the random access variant 034 * yields better performance on small sequential access lists. The 035 * tuning parameters below determine the cutoff point for what constitutes 036 * a "small" sequential access list for each algorithm. The values below 037 * were empirically determined to work well for LinkedList. Hopefully 038 * they should be reasonable for other sequential access List 039 * implementations. Those doing performance work on this code would 040 * do well to validate the values of these parameters from time to time. 041 * (The first word of each tuning parameter name is the algorithm to which 042 * it applies.) 043 */ 044 private static final int BINARYSEARCH_THRESHOLD = 5000; 045 private static final int REVERSE_THRESHOLD = 18; 046 private static final int SHUFFLE_THRESHOLD = 5; 047 private static final int FILL_THRESHOLD = 25; 048 private static final int ROTATE_THRESHOLD = 100; 049 private static final int COPY_THRESHOLD = 10; 050 private static final int REPLACEALL_THRESHOLD = 11; 051 private static final int INDEXOFSUBLIST_THRESHOLD = 35; 052 053 public static void sort(List list) { 054 Object a[] = list.toArray(); 055 Arrays.sort(a); 056 ListIterator i = list.listIterator(); 057 for (int j=0; j<a.length; j++) { 058 i.next(); 059 i.set(a[j]); 060 } 061 } 062 063 public static void sort(List list, Comparator c) { 064 Object a[] = list.toArray(); 065 Arrays.sort(a, c); 066 ListIterator i = list.listIterator(); 067 for (int j=0; j<a.length; j++) { 068 i.next(); 069 i.set(a[j]); 070 } 071 } 072 073 074 public static int binarySearch(List list, Object key) { 075 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 076 return indexedBinarySearch(list, key); 077 return iteratorBinarySearch(list, key); 078 } 079 080 private static int indexedBinarySearch(List list, Object key) { 081 int low = 0; 082 int high = list.size()-1; 083 084 while (low <= high) { 085 int mid = (low + high) >> 1; 086 Object midVal = list.get(mid); 087 int cmp = ((Comparable)midVal).compareTo(key); 088 089 if (cmp < 0) 090 low = mid + 1; 091 else if (cmp > 0) 092 high = mid - 1; 093 else 094 return mid; // key found 095 } 096 return -(low + 1); // key not found 097 } 098 099 private static int iteratorBinarySearch(List list, Object key) { 100 int low = 0; 101 int high = list.size()-1; 102 ListIterator i = list.listIterator(); 103 104 while (low <= high) { 105 int mid = (low + high) >> 1; 106 Object midVal = get(i, mid); 107 int cmp = ((Comparable)midVal).compareTo(key); 108 109 if (cmp < 0) 110 low = mid + 1; 111 else if (cmp > 0) 112 high = mid - 1; 113 else 114 return mid; // key found 115 } 116 return -(low + 1); // key not found 117 } 118 119 /** 120 * Gets the ith element from the given list by repositioning the specified 121 * list listIterator. 122 * @param i 123 * @param index 124 * @return Object 125 */ 126 private static Object get(ListIterator i, int index) { 127 Object obj = null; 128 int pos = i.nextIndex(); 129 if (pos <= index) { 130 do { 131 obj = i.next(); 132 } while (pos++ < index); 133 } else { 134 do { 135 obj = i.previous(); 136 } while (--pos > index); 137 } 138 return obj; 139 } 140 141 public static int binarySearch(List list, Object key, Comparator c) { 142 if (c==null) 143 return binarySearch(list, key); 144 145 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 146 return indexedBinarySearch(list, key, c); 147 return iteratorBinarySearch(list, key, c); 148 } 149 150 private static int indexedBinarySearch(List l, Object key, Comparator c) { 151 int low = 0; 152 int high = l.size()-1; 153 154 while (low <= high) { 155 int mid = (low + high) >> 1; 156 Object midVal = l.get(mid); 157 int cmp = c.compare(midVal, key); 158 159 if (cmp < 0) 160 low = mid + 1; 161 else if (cmp > 0) 162 high = mid - 1; 163 else 164 return mid; // key found 165 } 166 return -(low + 1); // key not found 167 } 168 169 private static int iteratorBinarySearch(List l, Object key, Comparator c) { 170 int low = 0; 171 int high = l.size()-1; 172 ListIterator i = l.listIterator(); 173 174 while (low <= high) { 175 int mid = (low + high) >> 1; 176 Object midVal = get(i, mid); 177 int cmp = c.compare(midVal, key); 178 179 if (cmp < 0) 180 low = mid + 1; 181 else if (cmp > 0) 182 high = mid - 1; 183 else 184 return mid; // key found 185 } 186 return -(low + 1); // key not found 187 } 188 189 /** 190 * Reverses the order of the elements in the specified list.<p> 191 * 192 * This method runs in linear time. 193 * 194 * @param list the list whose elements are to be reversed. 195 * @throws UnsupportedOperationException if the specified list or 196 * its list-iterator does not support the <tt>set</tt> method. 197 */ 198 public static void reverse(List list) { 199 int size = list.size(); 200 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { 201 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) 202 swap(list, i, j); 203 } else { 204 ListIterator fwd = list.listIterator(); 205 ListIterator rev = list.listIterator(size); 206 for (int i=0, mid=list.size()>>1; i<mid; i++) { 207 Object tmp = fwd.next(); 208 fwd.set(rev.previous()); 209 rev.set(tmp); 210 } 211 } 212 } 213 214 /** 215 * Randomly permutes the specified list using a default source of 216 * randomness. All permutations occur with approximately equal 217 * likelihood.<p> 218 * 219 * The hedge "approximately" is used in the foregoing description because 220 * default source of randomenss is only approximately an unbiased source 221 * of independently chosen bits. If it were a perfect source of randomly 222 * chosen bits, then the algorithm would choose permutations with perfect 223 * uniformity.<p> 224 * 225 * This implementation traverses the list backwards, from the last element 226 * up to the second, repeatedly swapping a randomly selected element into 227 * the "current position". Elements are randomly selected from the 228 * portion of the list that runs from the first element to the current 229 * position, inclusive.<p> 230 * 231 * This method runs in linear time. If the specified list does not 232 * implement the {@link RandomAccess} interface and is large, this 233 * implementation dumps the specified list into an array before shuffling 234 * it, and dumps the shuffled array back into the list. This avoids the 235 * quadratic behavior that would result from shuffling a "sequential 236 * access" list in place. 237 * 238 * @param list the list to be shuffled. 239 * @throws UnsupportedOperationException if the specified list or 240 * its list-iterator does not support the <tt>set</tt> method. 241 */ 242 public static void shuffle(List list) { 243 shuffle(list, r); 244 } 245 private static Random r = new Random(); 246 247 /** 248 * Randomly permute the specified list using the specified source of 249 * randomness. All permutations occur with equal likelihood 250 * assuming that the source of randomness is fair.<p> 251 * 252 * This implementation traverses the list backwards, from the last element 253 * up to the second, repeatedly swapping a randomly selected element into 254 * the "current position". Elements are randomly selected from the 255 * portion of the list that runs from the first element to the current 256 * position, inclusive.<p> 257 * 258 * This method runs in linear time. If the specified list does not 259 * implement the {@link RandomAccess} interface and is large, this 260 * implementation dumps the specified list into an array before shuffling 261 * it, and dumps the shuffled array back into the list. This avoids the 262 * quadratic behavior that would result from shuffling a "sequential 263 * access" list in place. 264 * 265 * @param list the list to be shuffled. 266 * @param rnd the source of randomness to use to shuffle the list. 267 * @throws UnsupportedOperationException if the specified list or its 268 * list-iterator does not support the <tt>set</tt> operation. 269 */ 270 public static void shuffle(List list, Random rnd) { 271 int size = list.size(); 272 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 273 for (int i=size; i>1; i--) 274 swap(list, i-1, rnd.nextInt(i)); 275 } else { 276 Object arr[] = list.toArray(); 277 278 // Shuffle array 279 for (int i=size; i>1; i--) 280 swap(arr, i-1, rnd.nextInt(i)); 281 282 // Dump array back into list 283 ListIterator it = list.listIterator(); 284 for (int i=0; i<arr.length; i++) { 285 it.next(); 286 it.set(arr[i]); 287 } 288 } 289 } 290 291 /** 292 * Swaps the elements at the specified positions in the specified list. 293 * (If the specified positions are equal, invoking this method leaves 294 * the list unchanged.) 295 * 296 * @param list The list in which to swap elements. 297 * @param i the index of one element to be swapped. 298 * @param j the index of the other element to be swapped. 299 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt> 300 * is out of range (i < 0 || i >= list.size() 301 * || j < 0 || j >= list.size()). 302 */ 303 public static void swap(List list, int i, int j) { 304 list.set(i, list.set(j, list.get(i))); 305 } 306 307 /** 308 * Swaps the two specified elements in the specified array. 309 * @param arr 310 * @param i 311 * @param j 312 */ 313 private static void swap(Object[] arr, int i, int j) { 314 Object tmp = arr[i]; 315 arr[i] = arr[j]; 316 arr[j] = tmp; 317 } 318 319 /** 320 * Replaces all of the elements of the specified list with the specified 321 * element. <p> 322 * 323 * This method runs in linear time. 324 * 325 * @param list the list to be filled with the specified element. 326 * @param obj The element with which to fill the specified list. 327 * @throws UnsupportedOperationException if the specified list or its 328 * list-iterator does not support the <tt>set</tt> operation. 329 */ 330 public static void fill(List list, Object obj) { 331 int size = list.size(); 332 333 if (size < FILL_THRESHOLD || list instanceof RandomAccess) { 334 for (int i=0; i<size; i++) 335 list.set(i, obj); 336 } else { 337 ListIterator itr = list.listIterator(); 338 for (int i=0; i<size; i++) { 339 itr.next(); 340 itr.set(obj); 341 } 342 } 343 } 344 345 /** 346 * Copies all of the elements from one list into another. After the 347 * operation, the index of each copied element in the destination list 348 * will be identical to its index in the source list. The destination 349 * list must be at least as long as the source list. If it is longer, the 350 * remaining elements in the destination list are unaffected. <p> 351 * 352 * This method runs in linear time. 353 * 354 * @param dest The destination list. 355 * @param src The source list. 356 * @throws IndexOutOfBoundsException if the destination list is too small 357 * to contain the entire source List. 358 * @throws UnsupportedOperationException if the destination list's 359 * list-iterator does not support the <tt>set</tt> operation. 360 */ 361 public static void copy(List dest, List src) { 362 int srcSize = src.size(); 363 if (srcSize > dest.size()) 364 throw new IndexOutOfBoundsException("Source does not fit in dest"); 365 366 if (srcSize < COPY_THRESHOLD || 367 (src instanceof RandomAccess && dest instanceof RandomAccess)) { 368 for (int i=0; i<srcSize; i++) 369 dest.set(i, src.get(i)); 370 } else { 371 ListIterator di=dest.listIterator(), si=src.listIterator(); 372 for (int i=0; i<srcSize; i++) { 373 di.next(); 374 di.set(si.next()); 375 } 376 } 377 } 378 379 public static Object min(Collection coll) { 380 Iterator i = coll.iterator(); 381 Comparable candidate = (Comparable)(i.next()); 382 383 while(i.hasNext()) { 384 Comparable next = (Comparable)(i.next()); 385 if (next.compareTo(candidate) < 0) 386 candidate = next; 387 } 388 return candidate; 389 } 390 391 public static Object min(Collection coll, Comparator comp) { 392 if (comp==null) 393 return min(coll); 394 395 Iterator i = coll.iterator(); 396 Object candidate = i.next(); 397 398 while(i.hasNext()) { 399 Object next = i.next(); 400 if (comp.compare(next, candidate) < 0) 401 candidate = next; 402 } 403 return candidate; 404 } 405 406 public static Object max(Collection coll) { 407 Iterator i = coll.iterator(); 408 Comparable candidate = (Comparable)(i.next()); 409 410 while(i.hasNext()) { 411 Comparable next = (Comparable)(i.next()); 412 if (next.compareTo(candidate) > 0) 413 candidate = next; 414 } 415 return candidate; 416 } 417 418 public static Object max(Collection coll, Comparator comp) { 419 if (comp==null) 420 return max(coll); 421 422 Iterator i = coll.iterator(); 423 Object candidate = i.next(); 424 425 while(i.hasNext()) { 426 Object next = i.next(); 427 if (comp.compare(next, candidate) > 0) 428 candidate = next; 429 } 430 return candidate; 431 } 432 433 /** 434 * Rotates the elements in the specified list by the specified distance. 435 * After calling this method, the element at index <tt>i</tt> will be 436 * the element previously at index <tt>(i - distance)</tt> mod 437 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt> 438 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on 439 * the size of the list.) 440 * 441 * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>. 442 * After invoking <tt>Collections.rotate(list, 1)</tt> (or 443 * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise 444 * <tt>[s, t, a, n, k]</tt>. 445 * 446 * <p>Note that this method can usefully be applied to sublists to 447 * move one or more elements within a list while preserving the 448 * order of the remaining elements. For example, the following idiom 449 * moves the element at index <tt>j</tt> forward to position 450 * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>): 451 * <pre> 452 * Collections.rotate(list.subList(j, k+1), -1); 453 * </pre> 454 * To make this concrete, suppose <tt>list</tt> comprises 455 * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt> 456 * (<tt>b</tt>) forward two positions, perform the following invocation: 457 * <pre> 458 * Collections.rotate(l.subList(1, 4), -1); 459 * </pre> 460 * The resulting list is <tt>[a, c, d, b, e]</tt>. 461 * 462 * <p>To move more than one element forward, increase the absolute value 463 * of the rotation distance. To move elements backward, use a positive 464 * shift distance. 465 * 466 * <p>If the specified list is small or implements the {@link 467 * RandomAccess} interface, this implementation exchanges the first 468 * element into the location it should go, and then repeatedly exchanges 469 * the displaced element into the location it should go until a displaced 470 * element is swapped into the first element. If necessary, the process 471 * is repeated on the second and successive elements, until the rotation 472 * is complete. If the specified list is large and doesn't implement the 473 * <tt>RandomAccess</tt> interface, this implementation breaks the 474 * list into two sublist views around index <tt>-distance mod size</tt>. 475 * Then the {@link #reverse(List)} method is invoked on each sublist view, 476 * and finally it is invoked on the entire list. For a more complete 477 * description of both algorithms, see Section 2.3 of Jon Bentley's 478 * <i>Programming Pearls</i> (Addison-Wesley, 1986). 479 * 480 * @param list the list to be rotated. 481 * @param distance the distance to rotate the list. There are no 482 * constraints on this value; it may be zero, negative, or 483 * greater than <tt>list.size()</tt>. 484 * @throws UnsupportedOperationException if the specified list or 485 * its list-iterator does not support the <tt>set</tt> method. 486 */ 487 public static void rotate(List list, int distance) { 488 if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) 489 rotate1(list, distance); 490 else 491 rotate2(list, distance); 492 } 493 494 private static void rotate1(List list, int distance) { 495 int size = list.size(); 496 if (size == 0) 497 return; 498 distance = distance % size; 499 if (distance < 0) 500 distance += size; 501 if (distance == 0) 502 return; 503 504 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { 505 Object displaced = list.get(cycleStart); 506 int i = cycleStart; 507 do { 508 i += distance; 509 if (i >= size) 510 i -= size; 511 displaced = list.set(i, displaced); 512 nMoved ++; 513 } while(i != cycleStart); 514 } 515 } 516 517 private static void rotate2(List list, int distance) { 518 int size = list.size(); 519 if (size == 0) 520 return; 521 int mid = -distance % size; 522 if (mid < 0) 523 mid += size; 524 if (mid == 0) 525 return; 526 527 Collections.reverse(list.subList(0, mid)); 528 Collections.reverse(list.subList(mid, size)); 529 Collections.reverse(list); 530 } 531 532 /** 533 * Replaces all occurrences of one specified value in a list with another. 534 * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt> 535 * in <tt>list</tt> such that 536 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>. 537 * (This method has no effect on the size of the list.) 538 * 539 * @param list the list in which replacement is to occur. 540 * @param oldVal the old value to be replaced. 541 * @param newVal the new value with which <tt>oldVal</tt> is to be 542 * replaced. 543 * @return <tt>true</tt> if <tt>list</tt> contained one or more elements 544 * <tt>e</tt> such that 545 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>. 546 * @throws UnsupportedOperationException if the specified list or 547 * its list-iterator does not support the <tt>set</tt> method. 548 */ 549 public static boolean replaceAll(List list, Object oldVal, Object newVal) { 550 boolean result = false; 551 int size = list.size(); 552 if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { 553 if (oldVal==null) { 554 for (int i=0; i<size; i++) { 555 if (list.get(i)==null) { 556 list.set(i, newVal); 557 result = true; 558 } 559 } 560 } else { 561 for (int i=0; i<size; i++) { 562 if (oldVal.equals(list.get(i))) { 563 list.set(i, newVal); 564 result = true; 565 } 566 } 567 } 568 } else { 569 ListIterator itr=list.listIterator(); 570 if (oldVal==null) { 571 for (int i=0; i<size; i++) { 572 if (itr.next()==null) { 573 itr.set(newVal); 574 result = true; 575 } 576 } 577 } else { 578 for (int i=0; i<size; i++) { 579 if (oldVal.equals(itr.next())) { 580 itr.set(newVal); 581 result = true; 582 } 583 } 584 } 585 } 586 return result; 587 } 588 589 /** 590 * Returns the starting position of the first occurrence of the specified 591 * target list within the specified source list, or -1 if there is no 592 * such occurrence. More formally, returns the the lowest index <tt>i</tt> 593 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>, 594 * or -1 if there is no such index. (Returns -1 if 595 * <tt>target.size() > source.size()</tt>.) 596 * 597 * <p>This implementation uses the "brute force" technique of scanning 598 * over the source list, looking for a match with the target at each 599 * location in turn. 600 * 601 * @param source the list in which to search for the first occurrence 602 * of <tt>target</tt>. 603 * @param target the list to search for as a subList of <tt>source</tt>. 604 * @return the starting position of the first occurrence of the specified 605 * target list within the specified source list, or -1 if there 606 * is no such occurrence. 607 */ 608 public static int indexOfSubList(List source, List target) { 609 int sourceSize = source.size(); 610 int targetSize = target.size(); 611 int maxCandidate = sourceSize - targetSize; 612 613 if (sourceSize < INDEXOFSUBLIST_THRESHOLD || 614 (source instanceof RandomAccess&&target instanceof RandomAccess)) { 615 nextCand: 616 for (int candidate = 0; candidate <= maxCandidate; candidate++) { 617 for (int i=0, j=candidate; i<targetSize; i++, j++) 618 if (!eq(target.get(i), source.get(j))) 619 continue nextCand; // Element mismatch, try next cand 620 return candidate; // All elements of candidate matched target 621 } 622 } else { // Iterator version of above algorithm 623 ListIterator si = source.listIterator(); 624 nextCand: 625 for (int candidate = 0; candidate <= maxCandidate; candidate++) { 626 ListIterator ti = target.listIterator(); 627 for (int i=0; i<targetSize; i++) { 628 if (!eq(ti.next(), si.next())) { 629 // Back up source iterator to next candidate 630 for (int j=0; j<i; j++) 631 si.previous(); 632 continue nextCand; 633 } 634 } 635 return candidate; 636 } 637 } 638 return -1; // No candidate matched the target 639 } 640 641 /** 642 * Returns the starting position of the last occurrence of the specified 643 * target list within the specified source list, or -1 if there is no such 644 * occurrence. More formally, returns the the highest index <tt>i</tt> 645 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>, 646 * or -1 if there is no such index. (Returns -1 if 647 * <tt>target.size() > source.size()</tt>.) 648 * 649 * <p>This implementation uses the "brute force" technique of iterating 650 * over the source list, looking for a match with the target at each 651 * location in turn. 652 * 653 * @param source the list in which to search for the last occurrence 654 * of <tt>target</tt>. 655 * @param target the list to search for as a subList of <tt>source</tt>. 656 * @return the starting position of the last occurrence of the specified 657 * target list within the specified source list, or -1 if there 658 * is no such occurrence. 659 */ 660 public static int lastIndexOfSubList(List source, List target) { 661 int sourceSize = source.size(); 662 int targetSize = target.size(); 663 int maxCandidate = sourceSize - targetSize; 664 665 if (sourceSize < INDEXOFSUBLIST_THRESHOLD || 666 source instanceof RandomAccess) { // Index access version 667 nextCand: 668 for (int candidate = maxCandidate; candidate >= 0; candidate--) { 669 for (int i=0, j=candidate; i<targetSize; i++, j++) 670 if (!eq(target.get(i), source.get(j))) 671 continue nextCand; // Element mismatch, try next cand 672 return candidate; // All elements of candidate matched target 673 } 674 } else { // Iterator version of above algorithm 675 if (maxCandidate < 0) 676 return -1; 677 ListIterator si = source.listIterator(maxCandidate); 678 nextCand: 679 for (int candidate = maxCandidate; candidate >= 0; candidate--) { 680 ListIterator ti = target.listIterator(); 681 for (int i=0; i<targetSize; i++) { 682 if (!eq(ti.next(), si.next())) { 683 if (candidate != 0) { 684 // Back up source iterator to next candidate 685 for (int j=0; j<=i+1; j++) 686 si.previous(); 687 } 688 continue nextCand; 689 } 690 } 691 return candidate; 692 } 693 } 694 return -1; // No candidate matched the target 695 } 696 697 698 // Unmodifiable Wrappers 699 700 /** 701 * Returns an unmodifiable view of the specified collection. This method 702 * allows modules to provide users with "read-only" access to internal 703 * collections. Query operations on the returned collection "read through" 704 * to the specified collection, and attempts to modify the returned 705 * collection, whether direct or via its iterator, result in an 706 * <tt>UnsupportedOperationException</tt>.<p> 707 * 708 * The returned collection does <i>not</i> pass the hashCode and equals 709 * operations through to the backing collection, but relies on 710 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This 711 * is necessary to preserve the contracts of these operations in the case 712 * that the backing collection is a set or a list.<p> 713 * 714 * The returned collection will be serializable if the specified collection 715 * is serializable. 716 * 717 * @param c the collection for which an unmodifiable view is to be 718 * returned. 719 * @return an unmodifiable view of the specified collection. 720 */ 721 public static Collection unmodifiableCollection(Collection c) { 722 return new UnmodifiableCollection(c); 723 } 724 725 /** 726 * @serial include 727 */ 728 static class UnmodifiableCollection implements Collection, Serializable { 729 // use serialVersionUID from JDK 1.2.2 for interoperability 730 private static final long serialVersionUID = 1820017752578914078L; 731 732 Collection c; 733 734 UnmodifiableCollection(Collection c) { 735 if (c==null) 736 throw new NullPointerException(); 737 this.c = c; 738 } 739 740 @Override 741 public int size() {return c.size();} 742 @Override 743 public boolean isEmpty() {return c.isEmpty();} 744 @Override 745 public boolean contains(Object o) {return c.contains(o);} 746 @Override 747 public Object[] toArray() {return c.toArray();} 748 @Override 749 public Object[] toArray(Object[] a) {return c.toArray(a);} 750 @Override 751 public String toString() {return c.toString();} 752 753 @Override 754 public Iterator iterator() { 755 return new Iterator() { 756 Iterator i = c.iterator(); 757 758 public boolean hasNext() {return i.hasNext();} 759 public Object next() {return i.next();} 760 public void remove() { 761 throw new UnsupportedOperationException(); 762 } 763 }; 764 } 765 766 @Override 767 public boolean add(Object o){ 768 throw new UnsupportedOperationException(); 769 } 770 @Override 771 public boolean remove(Object o) { 772 throw new UnsupportedOperationException(); 773 } 774 775 @Override 776 public boolean containsAll(Collection coll) { 777 return c.containsAll(coll); 778 } 779 @Override 780 public boolean addAll(Collection coll) { 781 throw new UnsupportedOperationException(); 782 } 783 @Override 784 public boolean removeAll(Collection coll) { 785 throw new UnsupportedOperationException(); 786 } 787 @Override 788 public boolean retainAll(Collection coll) { 789 throw new UnsupportedOperationException(); 790 } 791 @Override 792 public void clear() { 793 throw new UnsupportedOperationException(); 794 } 795 } 796 797 /** 798 * Returns an unmodifiable view of the specified set. This method allows 799 * modules to provide users with "read-only" access to internal sets. 800 * Query operations on the returned set "read through" to the specified 801 * set, and attempts to modify the returned set, whether direct or via its 802 * iterator, result in an <tt>UnsupportedOperationException</tt>.<p> 803 * 804 * The returned set will be serializable if the specified set 805 * is serializable. 806 * 807 * @param s the set for which an unmodifiable view is to be returned. 808 * @return an unmodifiable view of the specified set. 809 */ 810 811 public static Set unmodifiableSet(Set s) { 812 return new UnmodifiableSet(s); 813 } 814 815 /** 816 * @serial include 817 */ 818 static class UnmodifiableSet extends UnmodifiableCollection 819 implements Set, Serializable { 820 UnmodifiableSet(Set s) {super(s);} 821 822 @Override 823 public boolean equals(Object o) {return c.equals(o);} 824 @Override 825 public int hashCode() {return c.hashCode();} 826 } 827 828 /** 829 * Returns an unmodifiable view of the specified sorted set. This method 830 * allows modules to provide users with "read-only" access to internal 831 * sorted sets. Query operations on the returned sorted set "read 832 * through" to the specified sorted set. Attempts to modify the returned 833 * sorted set, whether direct, via its iterator, or via its 834 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in 835 * an <tt>UnsupportedOperationException</tt>.<p> 836 * 837 * The returned sorted set will be serializable if the specified sorted set 838 * is serializable. 839 * 840 * @param s the sorted set for which an unmodifiable view is to be 841 * returned. 842 * @return an unmodifiable view of the specified sorted set. 843 */ 844 public static SortedSet unmodifiableSortedSet(SortedSet s) { 845 return new UnmodifiableSortedSet(s); 846 } 847 848 /** 849 * @serial include 850 */ 851 static class UnmodifiableSortedSet extends UnmodifiableSet 852 implements SortedSet, Serializable { 853 private SortedSet ss; 854 855 UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;} 856 857 @Override 858 public Comparator comparator() {return ss.comparator();} 859 860 @Override 861 public SortedSet subSet(Object fromElement, Object toElement) { 862 return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement)); 863 } 864 @Override 865 public SortedSet headSet(Object toElement) { 866 return new UnmodifiableSortedSet(ss.headSet(toElement)); 867 } 868 @Override 869 public SortedSet tailSet(Object fromElement) { 870 return new UnmodifiableSortedSet(ss.tailSet(fromElement)); 871 } 872 873 @Override 874 public Object first() {return ss.first();} 875 @Override 876 public Object last() {return ss.last();} 877 } 878 879 /** 880 * Returns an unmodifiable view of the specified list. This method allows 881 * modules to provide users with "read-only" access to internal 882 * lists. Query operations on the returned list "read through" to the 883 * specified list, and attempts to modify the returned list, whether 884 * direct or via its iterator, result in an 885 * <tt>UnsupportedOperationException</tt>.<p> 886 * 887 * The returned list will be serializable if the specified list 888 * is serializable. Similarly, the returned list will implement 889 * {@link RandomAccess} if the specified list does. 890 * the 891 * 892 * @param list the list for which an unmodifiable view is to be returned. 893 * @return an unmodifiable view of the specified list. 894 */ 895 public static List unmodifiableList(List list) { 896 return (list instanceof RandomAccess ? 897 new UnmodifiableRandomAccessList(list) : 898 new UnmodifiableList(list)); 899 } 900 901 /** 902 * @serial include 903 */ 904 static class UnmodifiableList extends UnmodifiableCollection 905 implements List { 906 static final long serialVersionUID = -283967356065247728L; 907 List list; 908 909 UnmodifiableList(List list) { 910 super(list); 911 this.list = list; 912 } 913 914 @Override 915 public boolean equals(Object o) {return list.equals(o);} 916 @Override 917 public int hashCode() {return list.hashCode();} 918 919 @Override 920 public Object get(int index) {return list.get(index);} 921 @Override 922 public Object set(int index, Object element) { 923 throw new UnsupportedOperationException(); 924 } 925 @Override 926 public void add(int index, Object element) { 927 throw new UnsupportedOperationException(); 928 } 929 @Override 930 public Object remove(int index) { 931 throw new UnsupportedOperationException(); 932 } 933 @Override 934 public int indexOf(Object o) {return list.indexOf(o);} 935 @Override 936 public int lastIndexOf(Object o) {return list.lastIndexOf(o);} 937 @Override 938 public boolean addAll(int index, Collection c) { 939 throw new UnsupportedOperationException(); 940 } 941 @Override 942 public ListIterator listIterator() {return listIterator(0);} 943 944 @Override 945 public ListIterator listIterator(final int index) { 946 return new ListIterator() { 947 ListIterator i = list.listIterator(index); 948 949 public boolean hasNext() {return i.hasNext();} 950 public Object next() {return i.next();} 951 public boolean hasPrevious() {return i.hasPrevious();} 952 public Object previous() {return i.previous();} 953 public int nextIndex() {return i.nextIndex();} 954 public int previousIndex() {return i.previousIndex();} 955 956 public void remove() { 957 throw new UnsupportedOperationException(); 958 } 959 public void set(Object o) { 960 throw new UnsupportedOperationException(); 961 } 962 public void add(Object o) { 963 throw new UnsupportedOperationException(); 964 } 965 }; 966 } 967 968 @Override 969 public List subList(int fromIndex, int toIndex) { 970 return new UnmodifiableList(list.subList(fromIndex, toIndex)); 971 } 972 } 973 974 /** 975 * @serial include 976 */ 977 static class UnmodifiableRandomAccessList extends UnmodifiableList 978 implements RandomAccess 979 { 980 UnmodifiableRandomAccessList(List list) { 981 super(list); 982 } 983 984 @Override 985 public List subList(int fromIndex, int toIndex) { 986 return new UnmodifiableRandomAccessList( 987 list.subList(fromIndex, toIndex)); 988 } 989 } 990 991 /** 992 * Returns an unmodifiable view of the specified map. This method 993 * allows modules to provide users with "read-only" access to internal 994 * maps. Query operations on the returned map "read through" 995 * to the specified map, and attempts to modify the returned 996 * map, whether direct or via its collection views, result in an 997 * <tt>UnsupportedOperationException</tt>.<p> 998 * 999 * The returned map will be serializable if the specified map 1000 * is serializable. 1001 * 1002 * @param m the map for which an unmodifiable view is to be returned. 1003 * @return an unmodifiable view of the specified map. 1004 */ 1005 public static Map unmodifiableMap(Map m) { 1006 return new UnmodifiableMap(m); 1007 } 1008 1009 /** 1010 * @serial include 1011 */ 1012 private static class UnmodifiableMap implements Map, Serializable { 1013 // use serialVersionUID from JDK 1.2.2 for interoperability 1014 private static final long serialVersionUID = -1034234728574286014L; 1015 1016 private final Map m; 1017 1018 UnmodifiableMap(Map m) { 1019 if (m==null) 1020 throw new NullPointerException(); 1021 this.m = m; 1022 } 1023 1024 @Override 1025 public int size() {return m.size();} 1026 @Override 1027 public boolean isEmpty() {return m.isEmpty();} 1028 @Override 1029 public boolean containsKey(Object key) {return m.containsKey(key);} 1030 @Override 1031 public boolean containsValue(Object val) {return m.containsValue(val);} 1032 @Override 1033 public Object get(Object key) {return m.get(key);} 1034 1035 @Override 1036 public Object put(Object key, Object value) { 1037 throw new UnsupportedOperationException(); 1038 } 1039 @Override 1040 public Object remove(Object key) { 1041 throw new UnsupportedOperationException(); 1042 } 1043 @Override 1044 public void putAll(Map t) { 1045 throw new UnsupportedOperationException(); 1046 } 1047 @Override 1048 public void clear() { 1049 throw new UnsupportedOperationException(); 1050 } 1051 1052 private transient Set keySet = null; 1053 private transient Set entrySet = null; 1054 private transient Collection values = null; 1055 1056 @Override 1057 public Set keySet() { 1058 if (keySet==null) 1059 keySet = unmodifiableSet(m.keySet()); 1060 return keySet; 1061 } 1062 1063 @Override 1064 public Set entrySet() { 1065 if (entrySet==null) 1066 entrySet = new UnmodifiableEntrySet(m.entrySet()); 1067 return entrySet; 1068 } 1069 1070 @Override 1071 public Collection values() { 1072 if (values==null) 1073 values = unmodifiableCollection(m.values()); 1074 return values; 1075 } 1076 1077 @Override 1078 public boolean equals(Object o) {return m.equals(o);} 1079 @Override 1080 public int hashCode() {return m.hashCode();} 1081 @Override 1082 public String toString() {return m.toString();} 1083 1084 /** 1085 * We need this class in addition to UnmodifiableSet as 1086 * Map.Entries themselves permit modification of the backing Map 1087 * via their setValue operation. This class is subtle: there are 1088 * many possible attacks that must be thwarted. 1089 * 1090 * @serial include 1091 */ 1092 static class UnmodifiableEntrySet extends UnmodifiableSet { 1093 UnmodifiableEntrySet(Set s) { 1094 super(s); 1095 } 1096 1097 @Override 1098 public Iterator iterator() { 1099 return new Iterator() { 1100 Iterator i = c.iterator(); 1101 1102 public boolean hasNext() { 1103 return i.hasNext(); 1104 } 1105 public Object next() { 1106 return new UnmodifiableEntry((Map.Entry)i.next()); 1107 } 1108 public void remove() { 1109 throw new UnsupportedOperationException(); 1110 } 1111 }; 1112 } 1113 1114 @Override 1115 public Object[] toArray() { 1116 Object[] a = c.toArray(); 1117 for (int i=0; i<a.length; i++) 1118 a[i] = new UnmodifiableEntry((Map.Entry)a[i]); 1119 return a; 1120 } 1121 1122 @Override 1123 public Object[] toArray(Object a[]) { 1124 // We don't pass a to c.toArray, to avoid window of 1125 // vulnerability wherein an unscrupulous multithreaded client 1126 // could get his hands on raw (unwrapped) Entries from c. 1127 Object[] arr = c.toArray(a.length==0 ? a : 1128 (Object[])java.lang.reflect.Array.newInstance( 1129 a.getClass().getComponentType(), 0)); 1130 for (int i=0; i<arr.length; i++) 1131 arr[i] = new UnmodifiableEntry((Map.Entry)arr[i]); 1132 1133 if (arr.length > a.length) 1134 return arr; 1135 1136 System.arraycopy(arr, 0, a, 0, arr.length); 1137 if (a.length > arr.length) 1138 a[arr.length] = null; 1139 return a; 1140 } 1141 1142 /** 1143 * This method is overridden to protect the backing set against 1144 * an object with a nefarious equals function that senses 1145 * that the equality-candidate is Map.Entry and calls its 1146 * setValue method. 1147 * @param o 1148 * @return contains or not 1149 */ 1150 public boolean contains(Object o) { 1151 if (!(o instanceof Map.Entry)) 1152 return false; 1153 return c.contains(new UnmodifiableEntry((Map.Entry)o)); 1154 } 1155 1156 /** 1157 * The next two methods are overridden to protect against 1158 * an unscrupulous List whose contains(Object o) method senses 1159 * when o is a Map.Entry, and calls o.setValue. 1160 * @param coll 1161 * @return boolean 1162 */ 1163 public boolean containsAll(Collection coll) { 1164 Iterator e = coll.iterator(); 1165 while (e.hasNext()) 1166 if(!contains(e.next())) // Invokes safe contains() above 1167 return false; 1168 return true; 1169 } 1170 @Override 1171 public boolean equals(Object o) { 1172 if (o == this) 1173 return true; 1174 1175 if (!(o instanceof Set)) 1176 return false; 1177 Set s = (Set) o; 1178 if (s.size() != c.size()) 1179 return false; 1180 return containsAll(s); // Invokes safe containsAll() above 1181 } 1182 1183 /** 1184 * This "wrapper class" serves two purposes: it prevents 1185 * the client from modifying the backing Map, by short-circuiting 1186 * the setValue method, and it protects the backing Map against 1187 * an ill-behaved Map.Entry that attempts to modify another 1188 * Map Entry when asked to perform an equality check. 1189 */ 1190 private static class UnmodifiableEntry implements Map.Entry { 1191 private Map.Entry e; 1192 1193 UnmodifiableEntry(Map.Entry e) {this.e = e;} 1194 1195 @Override 1196 public Object getKey() {return e.getKey();} 1197 @Override 1198 public Object getValue() {return e.getValue();} 1199 @Override 1200 public Object setValue(Object value) { 1201 throw new UnsupportedOperationException(); 1202 } 1203 @Override 1204 public int hashCode() {return e.hashCode();} 1205 @Override 1206 public boolean equals(Object o) { 1207 if (!(o instanceof Map.Entry)) 1208 return false; 1209 Map.Entry t = (Map.Entry)o; 1210 return eq(e.getKey(), t.getKey()) && 1211 eq(e.getValue(), t.getValue()); 1212 } 1213 @Override 1214 public String toString() {return e.toString();} 1215 } 1216 } 1217 } 1218 1219 /** 1220 * Returns an unmodifiable view of the specified sorted map. This method 1221 * allows modules to provide users with "read-only" access to internal 1222 * sorted maps. Query operations on the returned sorted map "read through" 1223 * to the specified sorted map. Attempts to modify the returned 1224 * sorted map, whether direct, via its collection views, or via its 1225 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in 1226 * an <tt>UnsupportedOperationException</tt>.<p> 1227 * 1228 * The returned sorted map will be serializable if the specified sorted map 1229 * is serializable. 1230 * 1231 * @param m the sorted map for which an unmodifiable view is to be 1232 * returned. 1233 * @return an unmodifiable view of the specified sorted map. 1234 */ 1235 public static SortedMap unmodifiableSortedMap(SortedMap m) { 1236 return new UnmodifiableSortedMap(m); 1237 } 1238 1239 /** 1240 * @serial include 1241 */ 1242 static class UnmodifiableSortedMap extends UnmodifiableMap 1243 implements SortedMap, Serializable { 1244 private SortedMap sm; 1245 1246 UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;} 1247 1248 @Override 1249 public Comparator comparator() {return sm.comparator();} 1250 1251 @Override 1252 public SortedMap subMap(Object fromKey, Object toKey) { 1253 return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey)); 1254 } 1255 @Override 1256 public SortedMap headMap(Object toKey) { 1257 return new UnmodifiableSortedMap(sm.headMap(toKey)); 1258 } 1259 @Override 1260 public SortedMap tailMap(Object fromKey) { 1261 return new UnmodifiableSortedMap(sm.tailMap(fromKey)); 1262 } 1263 1264 @Override 1265 public Object firstKey() {return sm.firstKey();} 1266 @Override 1267 public Object lastKey() {return sm.lastKey();} 1268 } 1269 1270 1271 // Synch Wrappers 1272 1273 /** 1274 * Returns a synchronized (thread-safe) collection backed by the specified 1275 * collection. In order to guarantee serial access, it is critical that 1276 * <strong>all</strong> access to the backing collection is accomplished 1277 * through the returned collection.<p> 1278 * 1279 * It is imperative that the user manually synchronize on the returned 1280 * collection when iterating over it: 1281 * <pre> 1282 * Collection c = Collections.synchronizedCollection(myCollection); 1283 * ... 1284 * synchronized(c) { 1285 * Iterator i = c.iterator(); // Must be in the synchronized block 1286 * while (i.hasNext()) 1287 * foo(i.next()); 1288 * } 1289 * </pre> 1290 * Failure to follow this advice may result in non-deterministic behavior. 1291 * 1292 * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt> 1293 * and <tt>equals</tt> operations through to the backing collection, but 1294 * relies on <tt>Object</tt>'s equals and hashCode methods. This is 1295 * necessary to preserve the contracts of these operations in the case 1296 * that the backing collection is a set or a list.<p> 1297 * 1298 * The returned collection will be serializable if the specified collection 1299 * is serializable. 1300 * 1301 * @param c the collection to be "wrapped" in a synchronized collection. 1302 * @return a synchronized view of the specified collection. 1303 */ 1304 public static Collection synchronizedCollection(Collection c) { 1305 return new SynchronizedCollection(c); 1306 } 1307 1308 static Collection synchronizedCollection(Collection c, Object mutex) { 1309 return new SynchronizedCollection(c, mutex); 1310 } 1311 1312 /** 1313 * @serial include 1314 */ 1315 static class SynchronizedCollection implements Collection, Serializable { 1316 // use serialVersionUID from JDK 1.2.2 for interoperability 1317 private static final long serialVersionUID = 3053995032091335093L; 1318 1319 Collection c; // Backing Collection 1320 Object mutex; // Object on which to synchronize 1321 1322 SynchronizedCollection(Collection c) { 1323 if (c==null) 1324 throw new NullPointerException(); 1325 this.c = c; 1326 mutex = this; 1327 } 1328 SynchronizedCollection(Collection c, Object mutex) { 1329 this.c = c; 1330 this.mutex = mutex; 1331 } 1332 1333 @Override 1334 public int size() { 1335 synchronized(mutex) {return c.size();} 1336 } 1337 @Override 1338 public boolean isEmpty() { 1339 synchronized(mutex) {return c.isEmpty();} 1340 } 1341 @Override 1342 public boolean contains(Object o) { 1343 synchronized(mutex) {return c.contains(o);} 1344 } 1345 @Override 1346 public Object[] toArray() { 1347 synchronized(mutex) {return c.toArray();} 1348 } 1349 @Override 1350 public Object[] toArray(Object[] a) { 1351 synchronized(mutex) {return c.toArray(a);} 1352 } 1353 1354 @Override 1355 public Iterator iterator() { 1356 return c.iterator(); // Must be manually synched by user! 1357 } 1358 1359 @Override 1360 public boolean add(Object o) { 1361 synchronized(mutex) {return c.add(o);} 1362 } 1363 @Override 1364 public boolean remove(Object o) { 1365 synchronized(mutex) {return c.remove(o);} 1366 } 1367 1368 @Override 1369 public boolean containsAll(Collection coll) { 1370 synchronized(mutex) {return c.containsAll(coll);} 1371 } 1372 @Override 1373 public boolean addAll(Collection coll) { 1374 synchronized(mutex) {return c.addAll(coll);} 1375 } 1376 @Override 1377 public boolean removeAll(Collection coll) { 1378 synchronized(mutex) {return c.removeAll(coll);} 1379 } 1380 @Override 1381 public boolean retainAll(Collection coll) { 1382 synchronized(mutex) {return c.retainAll(coll);} 1383 } 1384 @Override 1385 public void clear() { 1386 synchronized(mutex) {c.clear();} 1387 } 1388 @Override 1389 public String toString() { 1390 synchronized(mutex) {return c.toString();} 1391 } 1392 } 1393 1394 /** 1395 * Returns a synchronized (thread-safe) set backed by the specified 1396 * set. In order to guarantee serial access, it is critical that 1397 * <strong>all</strong> access to the backing set is accomplished 1398 * through the returned set.<p> 1399 * 1400 * It is imperative that the user manually synchronize on the returned 1401 * set when iterating over it: 1402 * <pre> 1403 * Set s = Collections.synchronizedSet(new HashSet()); 1404 * ... 1405 * synchronized(s) { 1406 * Iterator i = s.iterator(); // Must be in the synchronized block 1407 * while (i.hasNext()) 1408 * foo(i.next()); 1409 * } 1410 * </pre> 1411 * Failure to follow this advice may result in non-deterministic behavior. 1412 * 1413 * <p>The returned set will be serializable if the specified set is 1414 * serializable. 1415 * 1416 * @param s the set to be "wrapped" in a synchronized set. 1417 * @return a synchronized view of the specified set. 1418 */ 1419 public static Set synchronizedSet(Set s) { 1420 return new SynchronizedSet(s); 1421 } 1422 1423 static Set synchronizedSet(Set s, Object mutex) { 1424 return new SynchronizedSet(s, mutex); 1425 } 1426 1427 /** 1428 * @serial include 1429 */ 1430 static class SynchronizedSet extends SynchronizedCollection 1431 implements Set { 1432 SynchronizedSet(Set s) { 1433 super(s); 1434 } 1435 SynchronizedSet(Set s, Object mutex) { 1436 super(s, mutex); 1437 } 1438 1439 @Override 1440 public boolean equals(Object o) { 1441 synchronized(mutex) {return c.equals(o);} 1442 } 1443 @Override 1444 public int hashCode() { 1445 synchronized(mutex) {return c.hashCode();} 1446 } 1447 } 1448 1449 /** 1450 * Returns a synchronized (thread-safe) sorted set backed by the specified 1451 * sorted set. In order to guarantee serial access, it is critical that 1452 * <strong>all</strong> access to the backing sorted set is accomplished 1453 * through the returned sorted set (or its views).<p> 1454 * 1455 * It is imperative that the user manually synchronize on the returned 1456 * sorted set when iterating over it or any of its <tt>subSet</tt>, 1457 * <tt>headSet</tt>, or <tt>tailSet</tt> views. 1458 * <pre> 1459 * SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet()); 1460 * ... 1461 * synchronized(s) { 1462 * Iterator i = s.iterator(); // Must be in the synchronized block 1463 * while (i.hasNext()) 1464 * foo(i.next()); 1465 * } 1466 * </pre> 1467 * or: 1468 * <pre> 1469 * SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet()); 1470 * SortedSet s2 = s.headSet(foo); 1471 * ... 1472 * synchronized(s) { // Note: s, not s2!!! 1473 * Iterator i = s2.iterator(); // Must be in the synchronized block 1474 * while (i.hasNext()) 1475 * foo(i.next()); 1476 * } 1477 * </pre> 1478 * Failure to follow this advice may result in non-deterministic behavior. 1479 * 1480 * <p>The returned sorted set will be serializable if the specified 1481 * sorted set is serializable. 1482 * 1483 * @param s the sorted set to be "wrapped" in a synchronized sorted set. 1484 * @return a synchronized view of the specified sorted set. 1485 */ 1486 public static SortedSet synchronizedSortedSet(SortedSet s) { 1487 return new SynchronizedSortedSet(s); 1488 } 1489 1490 /** 1491 * @serial include 1492 */ 1493 static class SynchronizedSortedSet extends SynchronizedSet 1494 implements SortedSet 1495 { 1496 private SortedSet ss; 1497 1498 SynchronizedSortedSet(SortedSet s) { 1499 super(s); 1500 ss = s; 1501 } 1502 SynchronizedSortedSet(SortedSet s, Object mutex) { 1503 super(s, mutex); 1504 ss = s; 1505 } 1506 1507 @Override 1508 public Comparator comparator() { 1509 synchronized(mutex) {return ss.comparator();} 1510 } 1511 1512 @Override 1513 public SortedSet subSet(Object fromElement, Object toElement) { 1514 synchronized(mutex) { 1515 return new SynchronizedSortedSet( 1516 ss.subSet(fromElement, toElement), mutex); 1517 } 1518 } 1519 @Override 1520 public SortedSet headSet(Object toElement) { 1521 synchronized(mutex) { 1522 return new SynchronizedSortedSet(ss.headSet(toElement), mutex); 1523 } 1524 } 1525 @Override 1526 public SortedSet tailSet(Object fromElement) { 1527 synchronized(mutex) { 1528 return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex); 1529 } 1530 } 1531 1532 @Override 1533 public Object first() { 1534 synchronized(mutex) {return ss.first();} 1535 } 1536 @Override 1537 public Object last() { 1538 synchronized(mutex) {return ss.last();} 1539 } 1540 } 1541 1542 /** 1543 * Returns a synchronized (thread-safe) list backed by the specified 1544 * list. In order to guarantee serial access, it is critical that 1545 * <strong>all</strong> access to the backing list is accomplished 1546 * through the returned list.<p> 1547 * 1548 * It is imperative that the user manually synchronize on the returned 1549 * list when iterating over it: 1550 * <pre> 1551 * List list = Collections.synchronizedList(new ArrayList()); 1552 * ... 1553 * synchronized(list) { 1554 * Iterator i = list.iterator(); // Must be in synchronized block 1555 * while (i.hasNext()) 1556 * foo(i.next()); 1557 * } 1558 * </pre> 1559 * Failure to follow this advice may result in non-deterministic behavior. 1560 * 1561 * <p>The returned list will be serializable if the specified list is 1562 * serializable. 1563 * 1564 * @param list the list to be "wrapped" in a synchronized list. 1565 * @return a synchronized view of the specified list. 1566 */ 1567 public static List synchronizedList(List list) { 1568 return (list instanceof RandomAccess ? 1569 new SynchronizedRandomAccessList(list) : 1570 new SynchronizedList(list)); 1571 } 1572 1573 static List synchronizedList(List list, Object mutex) { 1574 return (list instanceof RandomAccess ? 1575 new SynchronizedRandomAccessList(list, mutex) : 1576 new SynchronizedList(list, mutex)); 1577 } 1578 1579 /** 1580 * @serial include 1581 */ 1582 static class SynchronizedList extends SynchronizedCollection 1583 implements List { 1584 static final long serialVersionUID = -7754090372962971524L; 1585 1586 List list; 1587 1588 SynchronizedList(List list) { 1589 super(list); 1590 this.list = list; 1591 } 1592 SynchronizedList(List list, Object mutex) { 1593 super(list, mutex); 1594 this.list = list; 1595 } 1596 1597 @Override 1598 public boolean equals(Object o) { 1599 synchronized(mutex) {return list.equals(o);} 1600 } 1601 @Override 1602 public int hashCode() { 1603 synchronized(mutex) {return list.hashCode();} 1604 } 1605 1606 @Override 1607 public Object get(int index) { 1608 synchronized(mutex) {return list.get(index);} 1609 } 1610 @Override 1611 public Object set(int index, Object element) { 1612 synchronized(mutex) {return list.set(index, element);} 1613 } 1614 @Override 1615 public void add(int index, Object element) { 1616 synchronized(mutex) {list.add(index, element);} 1617 } 1618 @Override 1619 public Object remove(int index) { 1620 synchronized(mutex) {return list.remove(index);} 1621 } 1622 1623 @Override 1624 public int indexOf(Object o) { 1625 synchronized(mutex) {return list.indexOf(o);} 1626 } 1627 @Override 1628 public int lastIndexOf(Object o) { 1629 synchronized(mutex) {return list.lastIndexOf(o);} 1630 } 1631 1632 @Override 1633 public boolean addAll(int index, Collection c) { 1634 synchronized(mutex) {return list.addAll(index, c);} 1635 } 1636 1637 @Override 1638 public ListIterator listIterator() { 1639 return list.listIterator(); // Must be manually synched by user 1640 } 1641 1642 @Override 1643 public ListIterator listIterator(int index) { 1644 return list.listIterator(index); // Must be manually synched by usr 1645 } 1646 1647 @Override 1648 public List subList(int fromIndex, int toIndex) { 1649 synchronized(mutex) { 1650 return new SynchronizedList(list.subList(fromIndex, toIndex), 1651 mutex); 1652 } 1653 } 1654 } 1655 1656 /** 1657 * @serial include 1658 */ 1659 static class SynchronizedRandomAccessList extends SynchronizedList 1660 implements RandomAccess 1661 { 1662 SynchronizedRandomAccessList(List list) { 1663 super(list); 1664 } 1665 1666 SynchronizedRandomAccessList(List list, Object mutex) { 1667 super(list, mutex); 1668 } 1669 1670 @Override 1671 public List subList(int fromIndex, int toIndex) { 1672 synchronized(mutex) { 1673 return new SynchronizedRandomAccessList( 1674 list.subList(fromIndex, toIndex), mutex); 1675 } 1676 } 1677 } 1678 1679 /** 1680 * Returns a synchronized (thread-safe) map backed by the specified 1681 * map. In order to guarantee serial access, it is critical that 1682 * <strong>all</strong> access to the backing map is accomplished 1683 * through the returned map.<p> 1684 * 1685 * It is imperative that the user manually synchronize on the returned 1686 * map when iterating over any of its collection views: 1687 * <pre> 1688 * Map m = Collections.synchronizedMap(new HashMap()); 1689 * ... 1690 * Set s = m.keySet(); // Needn't be in synchronized block 1691 * ... 1692 * synchronized(m) { // Synchronizing on m, not s! 1693 * Iterator i = s.iterator(); // Must be in synchronized block 1694 * while (i.hasNext()) 1695 * foo(i.next()); 1696 * } 1697 * </pre> 1698 * Failure to follow this advice may result in non-deterministic behavior. 1699 * 1700 * <p>The returned map will be serializable if the specified map is 1701 * serializable. 1702 * 1703 * @param m the map to be "wrapped" in a synchronized map. 1704 * @return a synchronized view of the specified map. 1705 */ 1706 public static Map synchronizedMap(Map m) { 1707 return new SynchronizedMap(m); 1708 } 1709 1710 /** 1711 * @serial include 1712 */ 1713 private static class SynchronizedMap implements Map, Serializable { 1714 // use serialVersionUID from JDK 1.2.2 for interoperability 1715 private static final long serialVersionUID = 1978198479659022715L; 1716 1717 private Map m; // Backing Map 1718 Object mutex; // Object on which to synchronize 1719 1720 SynchronizedMap(Map m) { 1721 if (m==null) 1722 throw new NullPointerException(); 1723 this.m = m; 1724 mutex = this; 1725 } 1726 1727 SynchronizedMap(Map m, Object mutex) { 1728 this.m = m; 1729 this.mutex = mutex; 1730 } 1731 1732 @Override 1733 public int size() { 1734 synchronized(mutex) {return m.size();} 1735 } 1736 @Override 1737 public boolean isEmpty(){ 1738 synchronized(mutex) {return m.isEmpty();} 1739 } 1740 @Override 1741 public boolean containsKey(Object key) { 1742 synchronized(mutex) {return m.containsKey(key);} 1743 } 1744 @Override 1745 public boolean containsValue(Object value){ 1746 synchronized(mutex) {return m.containsValue(value);} 1747 } 1748 @Override 1749 public Object get(Object key) { 1750 synchronized(mutex) {return m.get(key);} 1751 } 1752 1753 @Override 1754 public Object put(Object key, Object value) { 1755 synchronized(mutex) {return m.put(key, value);} 1756 } 1757 @Override 1758 public Object remove(Object key) { 1759 synchronized(mutex) {return m.remove(key);} 1760 } 1761 @Override 1762 public void putAll(Map map) { 1763 synchronized(mutex) {m.putAll(map);} 1764 } 1765 @Override 1766 public void clear() { 1767 synchronized(mutex) {m.clear();} 1768 } 1769 1770 private transient Set keySet = null; 1771 private transient Set entrySet = null; 1772 private transient Collection values = null; 1773 1774 @Override 1775 public Set keySet() { 1776 synchronized(mutex) { 1777 if (keySet==null) 1778 keySet = new SynchronizedSet(m.keySet(), mutex); 1779 return keySet; 1780 } 1781 } 1782 1783 @Override 1784 public Set entrySet() { 1785 synchronized(mutex) { 1786 if (entrySet==null) 1787 entrySet = new SynchronizedSet(m.entrySet(), mutex); 1788 return entrySet; 1789 } 1790 } 1791 1792 @Override 1793 public Collection values() { 1794 synchronized(mutex) { 1795 if (values==null) 1796 values = new SynchronizedCollection(m.values(), mutex); 1797 return values; 1798 } 1799 } 1800 1801 @Override 1802 public boolean equals(Object o) { 1803 synchronized(mutex) {return m.equals(o);} 1804 } 1805 @Override 1806 public int hashCode() { 1807 synchronized(mutex) {return m.hashCode();} 1808 } 1809 @Override 1810 public String toString() { 1811 synchronized(mutex) {return m.toString();} 1812 } 1813 } 1814 1815 /** 1816 * Returns a synchronized (thread-safe) sorted map backed by the specified 1817 * sorted map. In order to guarantee serial access, it is critical that 1818 * <strong>all</strong> access to the backing sorted map is accomplished 1819 * through the returned sorted map (or its views).<p> 1820 * 1821 * It is imperative that the user manually synchronize on the returned 1822 * sorted map when iterating over any of its collection views, or the 1823 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or 1824 * <tt>tailMap</tt> views. 1825 * <pre> 1826 * SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap()); 1827 * ... 1828 * Set s = m.keySet(); // Needn't be in synchronized block 1829 * ... 1830 * synchronized(m) { // Synchronizing on m, not s! 1831 * Iterator i = s.iterator(); // Must be in synchronized block 1832 * while (i.hasNext()) 1833 * foo(i.next()); 1834 * } 1835 * </pre> 1836 * or: 1837 * <pre> 1838 * SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap()); 1839 * SortedMap m2 = m.subMap(foo, bar); 1840 * ... 1841 * Set s2 = m2.keySet(); // Needn't be in synchronized block 1842 * ... 1843 * synchronized(m) { // Synchronizing on m, not m2 or s2! 1844 * Iterator i = s.iterator(); // Must be in synchronized block 1845 * while (i.hasNext()) 1846 * foo(i.next()); 1847 * } 1848 * </pre> 1849 * Failure to follow this advice may result in non-deterministic behavior. 1850 * 1851 * <p>The returned sorted map will be serializable if the specified 1852 * sorted map is serializable. 1853 * 1854 * @param m the sorted map to be "wrapped" in a synchronized sorted map. 1855 * @return a synchronized view of the specified sorted map. 1856 */ 1857 public static SortedMap synchronizedSortedMap(SortedMap m) { 1858 return new SynchronizedSortedMap(m); 1859 } 1860 1861 1862 /** 1863 * @serial include 1864 */ 1865 static class SynchronizedSortedMap extends SynchronizedMap 1866 implements SortedMap 1867 { 1868 private SortedMap sm; 1869 1870 SynchronizedSortedMap(SortedMap m) { 1871 super(m); 1872 sm = m; 1873 } 1874 SynchronizedSortedMap(SortedMap m, Object mutex) { 1875 super(m, mutex); 1876 sm = m; 1877 } 1878 1879 @Override 1880 public Comparator comparator() { 1881 synchronized(mutex) {return sm.comparator();} 1882 } 1883 1884 @Override 1885 public SortedMap subMap(Object fromKey, Object toKey) { 1886 synchronized(mutex) { 1887 return new SynchronizedSortedMap( 1888 sm.subMap(fromKey, toKey), mutex); 1889 } 1890 } 1891 @Override 1892 public SortedMap headMap(Object toKey) { 1893 synchronized(mutex) { 1894 return new SynchronizedSortedMap(sm.headMap(toKey), mutex); 1895 } 1896 } 1897 @Override 1898 public SortedMap tailMap(Object fromKey) { 1899 synchronized(mutex) { 1900 return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex); 1901 } 1902 } 1903 1904 @Override 1905 public Object firstKey() { 1906 synchronized(mutex) {return sm.firstKey();} 1907 } 1908 @Override 1909 public Object lastKey() { 1910 synchronized(mutex) {return sm.lastKey();} 1911 } 1912 } 1913 1914 1915 // Miscellaneous 1916 1917 /** 1918 * The empty set (immutable). This set is serializable. 1919 */ 1920 public static final Set EMPTY_SET = new EmptySet(); 1921 1922 /** 1923 * @serial include 1924 */ 1925 private static class EmptySet extends AbstractSet implements Serializable { 1926 // use serialVersionUID from JDK 1.2.2 for interoperability 1927 private static final long serialVersionUID = 1582296315990362920L; 1928 1929 @Override 1930 public Iterator iterator() { 1931 return new Iterator() { 1932 public boolean hasNext() { 1933 return false; 1934 } 1935 public Object next() { 1936 throw new NoSuchElementException(); 1937 } 1938 public void remove() { 1939 throw new UnsupportedOperationException(); 1940 } 1941 }; 1942 } 1943 1944 @Override 1945 public int size() {return 0;} 1946 1947 @Override 1948 public boolean contains(Object obj) {return false;} 1949 } 1950 1951 /** 1952 * The empty list (immutable). This list is serializable. 1953 */ 1954 public static final List EMPTY_LIST = new EmptyList(); 1955 1956 /** 1957 * @serial include 1958 */ 1959 private static class EmptyList extends AbstractList 1960 implements RandomAccess, Serializable { 1961 // use serialVersionUID from JDK 1.2.2 for interoperability 1962 private static final long serialVersionUID = 8842843931221139166L; 1963 1964 @Override 1965 public int size() {return 0;} 1966 1967 @Override 1968 public boolean contains(Object obj) {return false;} 1969 1970 @Override 1971 public Object get(int index) { 1972 throw new IndexOutOfBoundsException("Index: "+index); 1973 } 1974 } 1975 1976 /** 1977 * The empty map (immutable). This map is serializable. 1978 */ 1979 public static final Map EMPTY_MAP = new EmptyMap(); 1980 1981 private static class EmptyMap extends AbstractMap implements Serializable { 1982 @Override 1983 public int size() {return 0;} 1984 1985 @Override 1986 public boolean isEmpty() {return true;} 1987 1988 @Override 1989 public boolean containsKey(Object key) {return false;} 1990 1991 @Override 1992 public boolean containsValue(Object value) {return false;} 1993 1994 @Override 1995 public Object get(Object key) {return null;} 1996 1997 @Override 1998 public Set keySet() {return EMPTY_SET;} 1999 2000 @Override 2001 public Collection values() {return EMPTY_SET;} 2002 2003 @Override 2004 public Set entrySet() {return EMPTY_SET;} 2005 2006 @Override 2007 public boolean equals(Object o) { 2008 return (o instanceof Map) && ((Map)o).size()==0; 2009 } 2010 2011 @Override 2012 public int hashCode() {return 0;} 2013 } 2014 2015 /** 2016 * Returns an immutable set containing only the specified object. 2017 * The returned set is serializable. 2018 * 2019 * @param o the sole object to be stored in the returned set. 2020 * @return an immutable set containing only the specified object. 2021 */ 2022 public static Set singleton(Object o) { 2023 return new SingletonSet(o); 2024 } 2025 2026 /** 2027 * @serial include 2028 */ 2029 private static class SingletonSet extends AbstractSet 2030 implements Serializable 2031 { 2032 // use serialVersionUID from JDK 1.2.2 for interoperability 2033 private static final long serialVersionUID = 3193687207550431679L; 2034 2035 private Object element; 2036 2037 SingletonSet(Object o) {element = o;} 2038 2039 @Override 2040 public Iterator iterator() { 2041 return new Iterator() { 2042 private boolean hasNext = true; 2043 public boolean hasNext() { 2044 return hasNext; 2045 } 2046 public Object next() { 2047 if (hasNext) { 2048 hasNext = false; 2049 return element; 2050 } 2051 throw new NoSuchElementException(); 2052 } 2053 public void remove() { 2054 throw new UnsupportedOperationException(); 2055 } 2056 }; 2057 } 2058 2059 @Override 2060 public int size() {return 1;} 2061 2062 @Override 2063 public boolean contains(Object o) {return eq(o, element);} 2064 } 2065 2066 /** 2067 * Returns an immutable list containing only the specified object. 2068 * The returned list is serializable. 2069 * 2070 * @param o the sole object to be stored in the returned list. 2071 * @return an immutable list containing only the specified object. 2072 */ 2073 public static List singletonList(Object o) { 2074 return new SingletonList(o); 2075 } 2076 2077 private static class SingletonList extends AbstractList 2078 implements RandomAccess, Serializable { 2079 static final long serialVersionUID = 3093736618740652951L; 2080 2081 private final Object element; 2082 2083 SingletonList(Object obj) {element = obj;} 2084 2085 @Override 2086 public int size() {return 1;} 2087 2088 @Override 2089 public boolean contains(Object obj) {return eq(obj, element);} 2090 2091 @Override 2092 public Object get(int index) { 2093 if (index != 0) 2094 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); 2095 return element; 2096 } 2097 } 2098 2099 /** 2100 * Returns an immutable map, mapping only the specified key to the 2101 * specified value. The returned map is serializable. 2102 * 2103 * @param key the sole key to be stored in the returned map. 2104 * @param value the value to which the returned map maps <tt>key</tt>. 2105 * @return an immutable map containing only the specified key-value 2106 * mapping. 2107 */ 2108 public static Map singletonMap(Object key, Object value) { 2109 return new SingletonMap(key, value); 2110 } 2111 2112 private static class SingletonMap extends AbstractMap 2113 implements Serializable { 2114 private final Object k, v; 2115 2116 SingletonMap(Object key, Object value) { 2117 k = key; 2118 v = value; 2119 } 2120 2121 @Override 2122 public int size() {return 1;} 2123 2124 @Override 2125 public boolean isEmpty() {return false;} 2126 2127 @Override 2128 public boolean containsKey(Object key) {return eq(key, k);} 2129 2130 @Override 2131 public boolean containsValue(Object value) {return eq(value, v);} 2132 2133 @Override 2134 public Object get(Object key) {return (eq(key, k) ? v : null);} 2135 2136 private transient Set keySet = null; 2137 private transient Set entrySet = null; 2138 private transient Collection values = null; 2139 2140 @Override 2141 public Set keySet() { 2142 if (keySet==null) 2143 keySet = singleton(k); 2144 return keySet; 2145 } 2146 2147 @Override 2148 public Set entrySet() { 2149 if (entrySet==null) 2150 entrySet = singleton(new ImmutableEntry(k, v)); 2151 return entrySet; 2152 } 2153 2154 @Override 2155 public Collection values() { 2156 if (values==null) 2157 values = singleton(v); 2158 return values; 2159 } 2160 2161 private static class ImmutableEntry implements Map.Entry { 2162 final Object k; 2163 final Object v; 2164 2165 ImmutableEntry(Object key, Object value) { 2166 k = key; 2167 v = value; 2168 } 2169 2170 @Override 2171 public Object getKey() {return k;} 2172 2173 @Override 2174 public Object getValue() {return v;} 2175 2176 @Override 2177 public Object setValue(Object value) { 2178 throw new UnsupportedOperationException(); 2179 } 2180 2181 @Override 2182 public boolean equals(Object o) { 2183 if (!(o instanceof Map.Entry)) 2184 return false; 2185 Map.Entry e = (Map.Entry)o; 2186 return eq(e.getKey(), k) && eq(e.getValue(), v); 2187 } 2188 2189 @Override 2190 public int hashCode() { 2191 return ((k==null ? 0 : k.hashCode()) ^ 2192 (v==null ? 0 : v.hashCode())); 2193 } 2194 2195 @Override 2196 public String toString() { 2197 return k+"="+v; 2198 } 2199 } 2200 } 2201 2202 public static List nCopies(int n, Object o) { 2203 return new CopiesList(n, o); 2204 } 2205 2206 /** 2207 * @serial include 2208 */ 2209 private static class CopiesList extends AbstractList 2210 implements RandomAccess, Serializable 2211 { 2212 static final long serialVersionUID = 2739099268398711800L; 2213 2214 int n; 2215 Object element; 2216 2217 CopiesList(int n, Object o) { 2218 if (n < 0) 2219 throw new IllegalArgumentException("List length = " + n); 2220 this.n = n; 2221 element = o; 2222 } 2223 2224 @Override 2225 public int size() { 2226 return n; 2227 } 2228 2229 @Override 2230 public boolean contains(Object obj) { 2231 return n != 0 && eq(obj, element); 2232 } 2233 2234 @Override 2235 public Object get(int index) { 2236 if (index<0 || index>=n) 2237 throw new IndexOutOfBoundsException("Index: "+index+ 2238 ", Size: "+n); 2239 return element; 2240 } 2241 } 2242 2243 public static Comparator reverseOrder() { 2244 return REVERSE_ORDER; 2245 } 2246 2247 private static final Comparator REVERSE_ORDER = new ReverseComparator(); 2248 2249 /** 2250 * @serial include 2251 */ 2252 private static class ReverseComparator implements Comparator,Serializable { 2253 // use serialVersionUID from JDK 1.2.2 for interoperability 2254 private static final long serialVersionUID = 7207038068494060240L; 2255 2256 @Override 2257 public int compare(Object o1, Object o2) { 2258 Comparable c1 = (Comparable)o1; 2259 Comparable c2 = (Comparable)o2; 2260 return -c1.compareTo(c2); 2261 } 2262 } 2263 2264 public static Enumeration enumeration(final Collection c) { 2265 return new Enumeration() { 2266 Iterator i = c.iterator(); 2267 2268 public boolean hasMoreElements() { 2269 return i.hasNext(); 2270 } 2271 2272 public Object nextElement() { 2273 return i.next(); 2274 } 2275 }; 2276 } 2277 2278 public static ArrayList list(Enumeration e) { 2279 ArrayList l = new ArrayList(); 2280 while (e.hasMoreElements()) 2281 l.add(e.nextElement()); 2282 return l; 2283 } 2284 2285 /** 2286 * Returns true if the specified arguments are equal, or both null. 2287 * @param o1 2288 * @param o2 2289 * @return is equal 2290 */ 2291 private static boolean eq(Object o1, Object o2) { 2292 return (o1==null ? o2==null : o1.equals(o2)); 2293 } 2294 }