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 /** 054 * Sorts the specified list into ascending order, according to the 055 * <i>natural ordering</i> of its elements. All elements in the list must 056 * implement the <tt>Comparable</tt> interface. Furthermore, all elements 057 * in the list must be <i>mutually comparable</i> (that is, 058 * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt> 059 * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> 060 * 061 * This sort is guaranteed to be <i>stable</i>: equal elements will 062 * not be reordered as a result of the sort.<p> 063 * 064 * The specified list must be modifiable, but need not be resizable.<p> 065 * 066 * The sorting algorithm is a modified mergesort (in which the merge is 067 * omitted if the highest element in the low sublist is less than the 068 * lowest element in the high sublist). This algorithm offers guaranteed 069 * n log(n) performance, and can approach linear performance on nearly 070 * sorted lists.<p> 071 * 072 * This implementation dumps the specified list into an array, sorts 073 * the array, and iterates over the list resetting each element 074 * from the corresponding position in the array. This avoids the 075 * n<sup>2</sup> log(n) performance that would result from attempting 076 * to sort a linked list in place. 077 * 078 * @param list the list to be sorted. 079 * @throws ClassCastException if the list contains elements that are not 080 * <i>mutually comparable</i> (for example, strings and integers). 081 * @throws UnsupportedOperationException if the specified list's 082 * list-iterator does not support the <tt>set</tt> operation. 083 * @see Comparable 084 */ 085 public static void sort(List list) { 086 Object a[] = list.toArray(); 087 Arrays.sort(a); 088 ListIterator i = list.listIterator(); 089 for (int j=0; j<a.length; j++) { 090 i.next(); 091 i.set(a[j]); 092 } 093 } 094 095 /** 096 * Sorts the specified list according to the order induced by the 097 * specified comparator. All elements in the list must be <i>mutually 098 * comparable</i> using the specified comparator (that is, 099 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt> 100 * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> 101 * 102 * This sort is guaranteed to be <i>stable</i>: equal elements will 103 * not be reordered as a result of the sort.<p> 104 * 105 * The sorting algorithm is a modified mergesort (in which the merge is 106 * omitted if the highest element in the low sublist is less than the 107 * lowest element in the high sublist). This algorithm offers guaranteed 108 * n log(n) performance, and can approach linear performance on nearly 109 * sorted lists.<p> 110 * 111 * The specified list must be modifiable, but need not be resizable. 112 * This implementation dumps the specified list into an array, sorts 113 * the array, and iterates over the list resetting each element 114 * from the corresponding position in the array. This avoids the 115 * n<sup>2</sup> log(n) performance that would result from attempting 116 * to sort a linked list in place. 117 * 118 * @param list the list to be sorted. 119 * @param c the comparator to determine the order of the list. A 120 * <tt>null</tt> value indicates that the elements' <i>natural 121 * ordering</i> should be used. 122 * @throws ClassCastException if the list contains elements that are not 123 * <i>mutually comparable</i> using the specified comparator. 124 * @throws UnsupportedOperationException if the specified list's 125 * list-iterator does not support the <tt>set</tt> operation. 126 * @see Comparator 127 */ 128 public static void sort(List list, Comparator c) { 129 Object a[] = list.toArray(); 130 Arrays.sort(a, c); 131 ListIterator i = list.listIterator(); 132 for (int j=0; j<a.length; j++) { 133 i.next(); 134 i.set(a[j]); 135 } 136 } 137 138 139 /** 140 * Searches the specified list for the specified object using the binary 141 * search algorithm. The list must be sorted into ascending order 142 * according to the <i>natural ordering</i> of its elements (as by the 143 * <tt>sort(List)</tt> method, above) prior to making this call. If it is 144 * not sorted, the results are undefined. If the list contains multiple 145 * elements equal to the specified object, there is no guarantee which one 146 * will be found.<p> 147 * 148 * This method runs in log(n) time for a "random access" list (which 149 * provides near-constant-time positional access). If the specified list 150 * does not implement the {@link RandomAccess} and is large, this method 151 * will do an iterator-based binary search that performs O(n) link 152 * traversals and O(log n) element comparisons. 153 * 154 * @param list the list to be searched. 155 * @param key the key to be searched for. 156 * @return index of the search key, if it is contained in the list; 157 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 158 * <i>insertion point</i> is defined as the point at which the 159 * key would be inserted into the list: the index of the first 160 * element greater than the key, or <tt>list.size()</tt>, if all 161 * elements in the list are less than the specified key. Note 162 * that this guarantees that the return value will be >= 0 if 163 * and only if the key is found. 164 * @throws ClassCastException if the list contains elements that are not 165 * <i>mutually comparable</i> (for example, strings and 166 * integers), or the search key in not mutually comparable 167 * with the elements of the list. 168 * @see Comparable 169 * @see #sort(List) 170 */ 171 public static int binarySearch(List list, Object key) { 172 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 173 return indexedBinarySearch(list, key); 174 return iteratorBinarySearch(list, key); 175 } 176 177 private static int indexedBinarySearch(List list, Object key) { 178 int low = 0; 179 int high = list.size()-1; 180 181 while (low <= high) { 182 int mid = (low + high) >> 1; 183 Object midVal = list.get(mid); 184 int cmp = ((Comparable)midVal).compareTo(key); 185 186 if (cmp < 0) 187 low = mid + 1; 188 else if (cmp > 0) 189 high = mid - 1; 190 else 191 return mid; // key found 192 } 193 return -(low + 1); // key not found 194 } 195 196 private static int iteratorBinarySearch(List list, Object key) { 197 int low = 0; 198 int high = list.size()-1; 199 ListIterator i = list.listIterator(); 200 201 while (low <= high) { 202 int mid = (low + high) >> 1; 203 Object midVal = get(i, mid); 204 int cmp = ((Comparable)midVal).compareTo(key); 205 206 if (cmp < 0) 207 low = mid + 1; 208 else if (cmp > 0) 209 high = mid - 1; 210 else 211 return mid; // key found 212 } 213 return -(low + 1); // key not found 214 } 215 216 /** 217 * Gets the ith element from the given list by repositioning the specified 218 * list listIterator. 219 * @param i 220 * @param index 221 * @return Object 222 */ 223 private static Object get(ListIterator i, int index) { 224 Object obj = null; 225 int pos = i.nextIndex(); 226 if (pos <= index) { 227 do { 228 obj = i.next(); 229 } while (pos++ < index); 230 } else { 231 do { 232 obj = i.previous(); 233 } while (--pos > index); 234 } 235 return obj; 236 } 237 238 /** 239 * Searches the specified list for the specified object using the binary 240 * search algorithm. The list must be sorted into ascending order 241 * according to the specified comparator (as by the <tt>Sort(List, 242 * Comparator)</tt> method, above), prior to making this call. If it is 243 * not sorted, the results are undefined. If the list contains multiple 244 * elements equal to the specified object, there is no guarantee which one 245 * will be found.<p> 246 * 247 * This method runs in log(n) time for a "random access" list (which 248 * provides near-constant-time positional access). If the specified list 249 * does not implement the {@link RandomAccess} and is large, this 250 * this method will do an iterator-based binary search that performs 251 * O(n) link traversals and O(log n) element comparisons. 252 * 253 * @param list the list to be searched. 254 * @param key the key to be searched for. 255 * @param c the comparator by which the list is ordered. A 256 * <tt>null</tt> value indicates that the elements' <i>natural 257 * ordering</i> should be used. 258 * @return index of the search key, if it is contained in the list; 259 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The 260 * <i>insertion point</i> is defined as the point at which the 261 * key would be inserted into the list: the index of the first 262 * element greater than the key, or <tt>list.size()</tt>, if all 263 * elements in the list are less than the specified key. Note 264 * that this guarantees that the return value will be >= 0 if 265 * and only if the key is found. 266 * @throws ClassCastException if the list contains elements that are not 267 * <i>mutually comparable</i> using the specified comparator, 268 * or the search key in not mutually comparable with the 269 * elements of the list using this comparator. 270 * @see Comparable 271 * @see #sort(List, Comparator) 272 */ 273 public static int binarySearch(List list, Object key, Comparator c) { 274 if (c==null) 275 return binarySearch(list, key); 276 277 if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) 278 return indexedBinarySearch(list, key, c); 279 return iteratorBinarySearch(list, key, c); 280 } 281 282 private static int indexedBinarySearch(List l, Object key, Comparator c) { 283 int low = 0; 284 int high = l.size()-1; 285 286 while (low <= high) { 287 int mid = (low + high) >> 1; 288 Object midVal = l.get(mid); 289 int cmp = c.compare(midVal, key); 290 291 if (cmp < 0) 292 low = mid + 1; 293 else if (cmp > 0) 294 high = mid - 1; 295 else 296 return mid; // key found 297 } 298 return -(low + 1); // key not found 299 } 300 301 private static int iteratorBinarySearch(List l, Object key, Comparator c) { 302 int low = 0; 303 int high = l.size()-1; 304 ListIterator i = l.listIterator(); 305 306 while (low <= high) { 307 int mid = (low + high) >> 1; 308 Object midVal = get(i, mid); 309 int cmp = c.compare(midVal, key); 310 311 if (cmp < 0) 312 low = mid + 1; 313 else if (cmp > 0) 314 high = mid - 1; 315 else 316 return mid; // key found 317 } 318 return -(low + 1); // key not found 319 } 320 321 /** 322 * Reverses the order of the elements in the specified list.<p> 323 * 324 * This method runs in linear time. 325 * 326 * @param list the list whose elements are to be reversed. 327 * @throws UnsupportedOperationException if the specified list or 328 * its list-iterator does not support the <tt>set</tt> method. 329 */ 330 public static void reverse(List list) { 331 int size = list.size(); 332 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { 333 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) 334 swap(list, i, j); 335 } else { 336 ListIterator fwd = list.listIterator(); 337 ListIterator rev = list.listIterator(size); 338 for (int i=0, mid=list.size()>>1; i<mid; i++) { 339 Object tmp = fwd.next(); 340 fwd.set(rev.previous()); 341 rev.set(tmp); 342 } 343 } 344 } 345 346 /** 347 * Randomly permutes the specified list using a default source of 348 * randomness. All permutations occur with approximately equal 349 * likelihood.<p> 350 * 351 * The hedge "approximately" is used in the foregoing description because 352 * default source of randomenss is only approximately an unbiased source 353 * of independently chosen bits. If it were a perfect source of randomly 354 * chosen bits, then the algorithm would choose permutations with perfect 355 * uniformity.<p> 356 * 357 * This implementation traverses the list backwards, from the last element 358 * up to the second, repeatedly swapping a randomly selected element into 359 * the "current position". Elements are randomly selected from the 360 * portion of the list that runs from the first element to the current 361 * position, inclusive.<p> 362 * 363 * This method runs in linear time. If the specified list does not 364 * implement the {@link RandomAccess} interface and is large, this 365 * implementation dumps the specified list into an array before shuffling 366 * it, and dumps the shuffled array back into the list. This avoids the 367 * quadratic behavior that would result from shuffling a "sequential 368 * access" list in place. 369 * 370 * @param list the list to be shuffled. 371 * @throws UnsupportedOperationException if the specified list or 372 * its list-iterator does not support the <tt>set</tt> method. 373 */ 374 public static void shuffle(List list) { 375 shuffle(list, r); 376 } 377 private static Random r = new Random(); 378 379 /** 380 * Randomly permute the specified list using the specified source of 381 * randomness. All permutations occur with equal likelihood 382 * assuming that the source of randomness is fair.<p> 383 * 384 * This implementation traverses the list backwards, from the last element 385 * up to the second, repeatedly swapping a randomly selected element into 386 * the "current position". Elements are randomly selected from the 387 * portion of the list that runs from the first element to the current 388 * position, inclusive.<p> 389 * 390 * This method runs in linear time. If the specified list does not 391 * implement the {@link RandomAccess} interface and is large, this 392 * implementation dumps the specified list into an array before shuffling 393 * it, and dumps the shuffled array back into the list. This avoids the 394 * quadratic behavior that would result from shuffling a "sequential 395 * access" list in place. 396 * 397 * @param list the list to be shuffled. 398 * @param rnd the source of randomness to use to shuffle the list. 399 * @throws UnsupportedOperationException if the specified list or its 400 * list-iterator does not support the <tt>set</tt> operation. 401 */ 402 public static void shuffle(List list, Random rnd) { 403 int size = list.size(); 404 if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 405 for (int i=size; i>1; i--) 406 swap(list, i-1, rnd.nextInt(i)); 407 } else { 408 Object arr[] = list.toArray(); 409 410 // Shuffle array 411 for (int i=size; i>1; i--) 412 swap(arr, i-1, rnd.nextInt(i)); 413 414 // Dump array back into list 415 ListIterator it = list.listIterator(); 416 for (int i=0; i<arr.length; i++) { 417 it.next(); 418 it.set(arr[i]); 419 } 420 } 421 } 422 423 /** 424 * Swaps the elements at the specified positions in the specified list. 425 * (If the specified positions are equal, invoking this method leaves 426 * the list unchanged.) 427 * 428 * @param list The list in which to swap elements. 429 * @param i the index of one element to be swapped. 430 * @param j the index of the other element to be swapped. 431 * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt> 432 * is out of range (i < 0 || i >= list.size() 433 * || j < 0 || j >= list.size()). 434 */ 435 public static void swap(List list, int i, int j) { 436 list.set(i, list.set(j, list.get(i))); 437 } 438 439 /** 440 * Swaps the two specified elements in the specified array. 441 * @param arr 442 * @param i 443 * @param j 444 */ 445 private static void swap(Object[] arr, int i, int j) { 446 Object tmp = arr[i]; 447 arr[i] = arr[j]; 448 arr[j] = tmp; 449 } 450 451 /** 452 * Replaces all of the elements of the specified list with the specified 453 * element. <p> 454 * 455 * This method runs in linear time. 456 * 457 * @param list the list to be filled with the specified element. 458 * @param obj The element with which to fill the specified list. 459 * @throws UnsupportedOperationException if the specified list or its 460 * list-iterator does not support the <tt>set</tt> operation. 461 */ 462 public static void fill(List list, Object obj) { 463 int size = list.size(); 464 465 if (size < FILL_THRESHOLD || list instanceof RandomAccess) { 466 for (int i=0; i<size; i++) 467 list.set(i, obj); 468 } else { 469 ListIterator itr = list.listIterator(); 470 for (int i=0; i<size; i++) { 471 itr.next(); 472 itr.set(obj); 473 } 474 } 475 } 476 477 /** 478 * Copies all of the elements from one list into another. After the 479 * operation, the index of each copied element in the destination list 480 * will be identical to its index in the source list. The destination 481 * list must be at least as long as the source list. If it is longer, the 482 * remaining elements in the destination list are unaffected. <p> 483 * 484 * This method runs in linear time. 485 * 486 * @param dest The destination list. 487 * @param src The source list. 488 * @throws IndexOutOfBoundsException if the destination list is too small 489 * to contain the entire source List. 490 * @throws UnsupportedOperationException if the destination list's 491 * list-iterator does not support the <tt>set</tt> operation. 492 */ 493 public static void copy(List dest, List src) { 494 int srcSize = src.size(); 495 if (srcSize > dest.size()) 496 throw new IndexOutOfBoundsException("Source does not fit in dest"); 497 498 if (srcSize < COPY_THRESHOLD || 499 (src instanceof RandomAccess && dest instanceof RandomAccess)) { 500 for (int i=0; i<srcSize; i++) 501 dest.set(i, src.get(i)); 502 } else { 503 ListIterator di=dest.listIterator(), si=src.listIterator(); 504 for (int i=0; i<srcSize; i++) { 505 di.next(); 506 di.set(si.next()); 507 } 508 } 509 } 510 511 /** 512 * Returns the minimum element of the given collection, according to the 513 * <i>natural ordering</i> of its elements. All elements in the 514 * collection must implement the <tt>Comparable</tt> interface. 515 * Furthermore, all elements in the collection must be <i>mutually 516 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a 517 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 518 * <tt>e2</tt> in the collection).<p> 519 * 520 * This method iterates over the entire collection, hence it requires 521 * time proportional to the size of the collection. 522 * 523 * @param coll the collection whose minimum element is to be determined. 524 * @return the minimum element of the given collection, according 525 * to the <i>natural ordering</i> of its elements. 526 * @throws ClassCastException if the collection contains elements that are 527 * not <i>mutually comparable</i> (for example, strings and 528 * integers). 529 * @throws NoSuchElementException if the collection is empty. 530 * @see Comparable 531 */ 532 public static Object min(Collection coll) { 533 Iterator i = coll.iterator(); 534 Comparable candidate = (Comparable)(i.next()); 535 536 while(i.hasNext()) { 537 Comparable next = (Comparable)(i.next()); 538 if (next.compareTo(candidate) < 0) 539 candidate = next; 540 } 541 return candidate; 542 } 543 544 /** 545 * Returns the minimum element of the given collection, according to the 546 * order induced by the specified comparator. All elements in the 547 * collection must be <i>mutually comparable</i> by the specified 548 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a 549 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 550 * <tt>e2</tt> in the collection).<p> 551 * 552 * This method iterates over the entire collection, hence it requires 553 * time proportional to the size of the collection. 554 * 555 * @param coll the collection whose minimum element is to be determined. 556 * @param comp the comparator with which to determine the minimum element. 557 * A <tt>null</tt> value indicates that the elements' <i>natural 558 * ordering</i> should be used. 559 * @return the minimum element of the given collection, according 560 * to the specified comparator. 561 * @throws ClassCastException if the collection contains elements that are 562 * not <i>mutually comparable</i> using the specified comparator. 563 * @throws NoSuchElementException if the collection is empty. 564 * @see Comparable 565 */ 566 public static Object min(Collection coll, Comparator comp) { 567 if (comp==null) 568 return min(coll); 569 570 Iterator i = coll.iterator(); 571 Object candidate = i.next(); 572 573 while(i.hasNext()) { 574 Object next = i.next(); 575 if (comp.compare(next, candidate) < 0) 576 candidate = next; 577 } 578 return candidate; 579 } 580 581 /** 582 * Returns the maximum element of the given collection, according to the 583 * <i>natural ordering</i> of its elements. All elements in the 584 * collection must implement the <tt>Comparable</tt> interface. 585 * Furthermore, all elements in the collection must be <i>mutually 586 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a 587 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 588 * <tt>e2</tt> in the collection).<p> 589 * 590 * This method iterates over the entire collection, hence it requires 591 * time proportional to the size of the collection. 592 * 593 * @param coll the collection whose maximum element is to be determined. 594 * @return the maximum element of the given collection, according 595 * to the <i>natural ordering</i> of its elements. 596 * @throws ClassCastException if the collection contains elements that are 597 * not <i>mutually comparable</i> (for example, strings and 598 * integers). 599 * @throws NoSuchElementException if the collection is empty. 600 * @see Comparable 601 */ 602 public static Object max(Collection coll) { 603 Iterator i = coll.iterator(); 604 Comparable candidate = (Comparable)(i.next()); 605 606 while(i.hasNext()) { 607 Comparable next = (Comparable)(i.next()); 608 if (next.compareTo(candidate) > 0) 609 candidate = next; 610 } 611 return candidate; 612 } 613 614 /** 615 * Returns the maximum element of the given collection, according to the 616 * order induced by the specified comparator. All elements in the 617 * collection must be <i>mutually comparable</i> by the specified 618 * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a 619 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and 620 * <tt>e2</tt> in the collection).<p> 621 * 622 * This method iterates over the entire collection, hence it requires 623 * time proportional to the size of the collection. 624 * 625 * @param coll the collection whose maximum element is to be determined. 626 * @param comp the comparator with which to determine the maximum element. 627 * A <tt>null</tt> value indicates that the elements' <i>natural 628 * ordering</i> should be used. 629 * @return the maximum element of the given collection, according 630 * to the specified comparator. 631 * @throws ClassCastException if the collection contains elements that are 632 * not <i>mutually comparable</i> using the specified comparator. 633 * @throws NoSuchElementException if the collection is empty. 634 * @see Comparable 635 */ 636 public static Object max(Collection coll, Comparator comp) { 637 if (comp==null) 638 return max(coll); 639 640 Iterator i = coll.iterator(); 641 Object candidate = i.next(); 642 643 while(i.hasNext()) { 644 Object next = i.next(); 645 if (comp.compare(next, candidate) > 0) 646 candidate = next; 647 } 648 return candidate; 649 } 650 651 /** 652 * Rotates the elements in the specified list by the specified distance. 653 * After calling this method, the element at index <tt>i</tt> will be 654 * the element previously at index <tt>(i - distance)</tt> mod 655 * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt> 656 * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on 657 * the size of the list.) 658 * 659 * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>. 660 * After invoking <tt>Collections.rotate(list, 1)</tt> (or 661 * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise 662 * <tt>[s, t, a, n, k]</tt>. 663 * 664 * <p>Note that this method can usefully be applied to sublists to 665 * move one or more elements within a list while preserving the 666 * order of the remaining elements. For example, the following idiom 667 * moves the element at index <tt>j</tt> forward to position 668 * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>): 669 * <pre> 670 * Collections.rotate(list.subList(j, k+1), -1); 671 * </pre> 672 * To make this concrete, suppose <tt>list</tt> comprises 673 * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt> 674 * (<tt>b</tt>) forward two positions, perform the following invocation: 675 * <pre> 676 * Collections.rotate(l.subList(1, 4), -1); 677 * </pre> 678 * The resulting list is <tt>[a, c, d, b, e]</tt>. 679 * 680 * <p>To move more than one element forward, increase the absolute value 681 * of the rotation distance. To move elements backward, use a positive 682 * shift distance. 683 * 684 * <p>If the specified list is small or implements the {@link 685 * RandomAccess} interface, this implementation exchanges the first 686 * element into the location it should go, and then repeatedly exchanges 687 * the displaced element into the location it should go until a displaced 688 * element is swapped into the first element. If necessary, the process 689 * is repeated on the second and successive elements, until the rotation 690 * is complete. If the specified list is large and doesn't implement the 691 * <tt>RandomAccess</tt> interface, this implementation breaks the 692 * list into two sublist views around index <tt>-distance mod size</tt>. 693 * Then the {@link #reverse(List)} method is invoked on each sublist view, 694 * and finally it is invoked on the entire list. For a more complete 695 * description of both algorithms, see Section 2.3 of Jon Bentley's 696 * <i>Programming Pearls</i> (Addison-Wesley, 1986). 697 * 698 * @param list the list to be rotated. 699 * @param distance the distance to rotate the list. There are no 700 * constraints on this value; it may be zero, negative, or 701 * greater than <tt>list.size()</tt>. 702 * @throws UnsupportedOperationException if the specified list or 703 * its list-iterator does not support the <tt>set</tt> method. 704 */ 705 public static void rotate(List list, int distance) { 706 if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) 707 rotate1(list, distance); 708 else 709 rotate2(list, distance); 710 } 711 712 private static void rotate1(List list, int distance) { 713 int size = list.size(); 714 if (size == 0) 715 return; 716 distance = distance % size; 717 if (distance < 0) 718 distance += size; 719 if (distance == 0) 720 return; 721 722 for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { 723 Object displaced = list.get(cycleStart); 724 int i = cycleStart; 725 do { 726 i += distance; 727 if (i >= size) 728 i -= size; 729 displaced = list.set(i, displaced); 730 nMoved ++; 731 } while(i != cycleStart); 732 } 733 } 734 735 private static void rotate2(List list, int distance) { 736 int size = list.size(); 737 if (size == 0) 738 return; 739 int mid = -distance % size; 740 if (mid < 0) 741 mid += size; 742 if (mid == 0) 743 return; 744 745 Collections.reverse(list.subList(0, mid)); 746 Collections.reverse(list.subList(mid, size)); 747 Collections.reverse(list); 748 } 749 750 /** 751 * Replaces all occurrences of one specified value in a list with another. 752 * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt> 753 * in <tt>list</tt> such that 754 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>. 755 * (This method has no effect on the size of the list.) 756 * 757 * @param list the list in which replacement is to occur. 758 * @param oldVal the old value to be replaced. 759 * @param newVal the new value with which <tt>oldVal</tt> is to be 760 * replaced. 761 * @return <tt>true</tt> if <tt>list</tt> contained one or more elements 762 * <tt>e</tt> such that 763 * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>. 764 * @throws UnsupportedOperationException if the specified list or 765 * its list-iterator does not support the <tt>set</tt> method. 766 */ 767 public static boolean replaceAll(List list, Object oldVal, Object newVal) { 768 boolean result = false; 769 int size = list.size(); 770 if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { 771 if (oldVal==null) { 772 for (int i=0; i<size; i++) { 773 if (list.get(i)==null) { 774 list.set(i, newVal); 775 result = true; 776 } 777 } 778 } else { 779 for (int i=0; i<size; i++) { 780 if (oldVal.equals(list.get(i))) { 781 list.set(i, newVal); 782 result = true; 783 } 784 } 785 } 786 } else { 787 ListIterator itr=list.listIterator(); 788 if (oldVal==null) { 789 for (int i=0; i<size; i++) { 790 if (itr.next()==null) { 791 itr.set(newVal); 792 result = true; 793 } 794 } 795 } else { 796 for (int i=0; i<size; i++) { 797 if (oldVal.equals(itr.next())) { 798 itr.set(newVal); 799 result = true; 800 } 801 } 802 } 803 } 804 return result; 805 } 806 807 /** 808 * Returns the starting position of the first occurrence of the specified 809 * target list within the specified source list, or -1 if there is no 810 * such occurrence. More formally, returns the the lowest index <tt>i</tt> 811 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>, 812 * or -1 if there is no such index. (Returns -1 if 813 * <tt>target.size() > source.size()</tt>.) 814 * 815 * <p>This implementation uses the "brute force" technique of scanning 816 * over the source list, looking for a match with the target at each 817 * location in turn. 818 * 819 * @param source the list in which to search for the first occurrence 820 * of <tt>target</tt>. 821 * @param target the list to search for as a subList of <tt>source</tt>. 822 * @return the starting position of the first occurrence of the specified 823 * target list within the specified source list, or -1 if there 824 * is no such occurrence. 825 */ 826 public static int indexOfSubList(List source, List target) { 827 int sourceSize = source.size(); 828 int targetSize = target.size(); 829 int maxCandidate = sourceSize - targetSize; 830 831 if (sourceSize < INDEXOFSUBLIST_THRESHOLD || 832 (source instanceof RandomAccess&&target instanceof RandomAccess)) { 833 nextCand: 834 for (int candidate = 0; candidate <= maxCandidate; candidate++) { 835 for (int i=0, j=candidate; i<targetSize; i++, j++) 836 if (!eq(target.get(i), source.get(j))) 837 continue nextCand; // Element mismatch, try next cand 838 return candidate; // All elements of candidate matched target 839 } 840 } else { // Iterator version of above algorithm 841 ListIterator si = source.listIterator(); 842 nextCand: 843 for (int candidate = 0; candidate <= maxCandidate; candidate++) { 844 ListIterator ti = target.listIterator(); 845 for (int i=0; i<targetSize; i++) { 846 if (!eq(ti.next(), si.next())) { 847 // Back up source iterator to next candidate 848 for (int j=0; j<i; j++) 849 si.previous(); 850 continue nextCand; 851 } 852 } 853 return candidate; 854 } 855 } 856 return -1; // No candidate matched the target 857 } 858 859 /** 860 * Returns the starting position of the last occurrence of the specified 861 * target list within the specified source list, or -1 if there is no such 862 * occurrence. More formally, returns the the highest index <tt>i</tt> 863 * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>, 864 * or -1 if there is no such index. (Returns -1 if 865 * <tt>target.size() > source.size()</tt>.) 866 * 867 * <p>This implementation uses the "brute force" technique of iterating 868 * over the source list, looking for a match with the target at each 869 * location in turn. 870 * 871 * @param source the list in which to search for the last occurrence 872 * of <tt>target</tt>. 873 * @param target the list to search for as a subList of <tt>source</tt>. 874 * @return the starting position of the last occurrence of the specified 875 * target list within the specified source list, or -1 if there 876 * is no such occurrence. 877 */ 878 public static int lastIndexOfSubList(List source, List target) { 879 int sourceSize = source.size(); 880 int targetSize = target.size(); 881 int maxCandidate = sourceSize - targetSize; 882 883 if (sourceSize < INDEXOFSUBLIST_THRESHOLD || 884 source instanceof RandomAccess) { // Index access version 885 nextCand: 886 for (int candidate = maxCandidate; candidate >= 0; candidate--) { 887 for (int i=0, j=candidate; i<targetSize; i++, j++) 888 if (!eq(target.get(i), source.get(j))) 889 continue nextCand; // Element mismatch, try next cand 890 return candidate; // All elements of candidate matched target 891 } 892 } else { // Iterator version of above algorithm 893 if (maxCandidate < 0) 894 return -1; 895 ListIterator si = source.listIterator(maxCandidate); 896 nextCand: 897 for (int candidate = maxCandidate; candidate >= 0; candidate--) { 898 ListIterator ti = target.listIterator(); 899 for (int i=0; i<targetSize; i++) { 900 if (!eq(ti.next(), si.next())) { 901 if (candidate != 0) { 902 // Back up source iterator to next candidate 903 for (int j=0; j<=i+1; j++) 904 si.previous(); 905 } 906 continue nextCand; 907 } 908 } 909 return candidate; 910 } 911 } 912 return -1; // No candidate matched the target 913 } 914 915 916 // Unmodifiable Wrappers 917 918 /** 919 * Returns an unmodifiable view of the specified collection. This method 920 * allows modules to provide users with "read-only" access to internal 921 * collections. Query operations on the returned collection "read through" 922 * to the specified collection, and attempts to modify the returned 923 * collection, whether direct or via its iterator, result in an 924 * <tt>UnsupportedOperationException</tt>.<p> 925 * 926 * The returned collection does <i>not</i> pass the hashCode and equals 927 * operations through to the backing collection, but relies on 928 * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This 929 * is necessary to preserve the contracts of these operations in the case 930 * that the backing collection is a set or a list.<p> 931 * 932 * The returned collection will be serializable if the specified collection 933 * is serializable. 934 * 935 * @param c the collection for which an unmodifiable view is to be 936 * returned. 937 * @return an unmodifiable view of the specified collection. 938 */ 939 public static Collection unmodifiableCollection(Collection c) { 940 return new UnmodifiableCollection(c); 941 } 942 943 /** 944 * @serial include 945 */ 946 static class UnmodifiableCollection implements Collection, Serializable { 947 // use serialVersionUID from JDK 1.2.2 for interoperability 948 private static final long serialVersionUID = 1820017752578914078L; 949 950 Collection c; 951 952 UnmodifiableCollection(Collection c) { 953 if (c==null) 954 throw new NullPointerException(); 955 this.c = c; 956 } 957 958 /** 959 * @see java.util.Collection#size() 960 */ 961 public int size() {return c.size();} 962 /** 963 * @see java.util.Collection#isEmpty() 964 */ 965 public boolean isEmpty() {return c.isEmpty();} 966 /** 967 * @see java.util.Collection#contains(java.lang.Object) 968 */ 969 public boolean contains(Object o) {return c.contains(o);} 970 /** 971 * @see java.util.Collection#toArray() 972 */ 973 public Object[] toArray() {return c.toArray();} 974 /** 975 * @see java.util.Collection#toArray(java.lang.Object[]) 976 */ 977 public Object[] toArray(Object[] a) {return c.toArray(a);} 978 /** 979 * @see java.lang.Object#toString() 980 */ 981 public String toString() {return c.toString();} 982 983 /** 984 * @see java.util.Collection#iterator() 985 */ 986 public Iterator iterator() { 987 return new Iterator() { 988 Iterator i = c.iterator(); 989 990 public boolean hasNext() {return i.hasNext();} 991 public Object next() {return i.next();} 992 public void remove() { 993 throw new UnsupportedOperationException(); 994 } 995 }; 996 } 997 998 /** 999 * @see java.util.Collection#add(java.lang.Object) 1000 */ 1001 public boolean add(Object o){ 1002 throw new UnsupportedOperationException(); 1003 } 1004 /** 1005 * @see java.util.Collection#remove(java.lang.Object) 1006 */ 1007 public boolean remove(Object o) { 1008 throw new UnsupportedOperationException(); 1009 } 1010 1011 /** 1012 * @see java.util.Collection#containsAll(java.util.Collection) 1013 */ 1014 public boolean containsAll(Collection coll) { 1015 return c.containsAll(coll); 1016 } 1017 /** 1018 * @see java.util.Collection#addAll(java.util.Collection) 1019 */ 1020 public boolean addAll(Collection coll) { 1021 throw new UnsupportedOperationException(); 1022 } 1023 /** 1024 * @see java.util.Collection#removeAll(java.util.Collection) 1025 */ 1026 public boolean removeAll(Collection coll) { 1027 throw new UnsupportedOperationException(); 1028 } 1029 /** 1030 * @see java.util.Collection#retainAll(java.util.Collection) 1031 */ 1032 public boolean retainAll(Collection coll) { 1033 throw new UnsupportedOperationException(); 1034 } 1035 /** 1036 * @see java.util.Collection#clear() 1037 */ 1038 public void clear() { 1039 throw new UnsupportedOperationException(); 1040 } 1041 } 1042 1043 /** 1044 * Returns an unmodifiable view of the specified set. This method allows 1045 * modules to provide users with "read-only" access to internal sets. 1046 * Query operations on the returned set "read through" to the specified 1047 * set, and attempts to modify the returned set, whether direct or via its 1048 * iterator, result in an <tt>UnsupportedOperationException</tt>.<p> 1049 * 1050 * The returned set will be serializable if the specified set 1051 * is serializable. 1052 * 1053 * @param s the set for which an unmodifiable view is to be returned. 1054 * @return an unmodifiable view of the specified set. 1055 */ 1056 1057 public static Set unmodifiableSet(Set s) { 1058 return new UnmodifiableSet(s); 1059 } 1060 1061 /** 1062 * @serial include 1063 */ 1064 static class UnmodifiableSet extends UnmodifiableCollection 1065 implements Set, Serializable { 1066 UnmodifiableSet(Set s) {super(s);} 1067 1068 /** 1069 * @see java.util.Set#equals(java.lang.Object) 1070 */ 1071 public boolean equals(Object o) {return c.equals(o);} 1072 /** 1073 * @see java.util.Set#hashCode() 1074 */ 1075 public int hashCode() {return c.hashCode();} 1076 } 1077 1078 /** 1079 * Returns an unmodifiable view of the specified sorted set. This method 1080 * allows modules to provide users with "read-only" access to internal 1081 * sorted sets. Query operations on the returned sorted set "read 1082 * through" to the specified sorted set. Attempts to modify the returned 1083 * sorted set, whether direct, via its iterator, or via its 1084 * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in 1085 * an <tt>UnsupportedOperationException</tt>.<p> 1086 * 1087 * The returned sorted set will be serializable if the specified sorted set 1088 * is serializable. 1089 * 1090 * @param s the sorted set for which an unmodifiable view is to be 1091 * returned. 1092 * @return an unmodifiable view of the specified sorted set. 1093 */ 1094 public static SortedSet unmodifiableSortedSet(SortedSet s) { 1095 return new UnmodifiableSortedSet(s); 1096 } 1097 1098 /** 1099 * @serial include 1100 */ 1101 static class UnmodifiableSortedSet extends UnmodifiableSet 1102 implements SortedSet, Serializable { 1103 private SortedSet ss; 1104 1105 UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;} 1106 1107 /** 1108 * @see java.util.SortedSet#comparator() 1109 */ 1110 public Comparator comparator() {return ss.comparator();} 1111 1112 /** 1113 * @see java.util.SortedSet#subSet(java.lang.Object, java.lang.Object) 1114 */ 1115 public SortedSet subSet(Object fromElement, Object toElement) { 1116 return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement)); 1117 } 1118 /** 1119 * @see java.util.SortedSet#headSet(java.lang.Object) 1120 */ 1121 public SortedSet headSet(Object toElement) { 1122 return new UnmodifiableSortedSet(ss.headSet(toElement)); 1123 } 1124 /** 1125 * @see java.util.SortedSet#tailSet(java.lang.Object) 1126 */ 1127 public SortedSet tailSet(Object fromElement) { 1128 return new UnmodifiableSortedSet(ss.tailSet(fromElement)); 1129 } 1130 1131 /** 1132 * @see java.util.SortedSet#first() 1133 */ 1134 public Object first() {return ss.first();} 1135 /** 1136 * @see java.util.SortedSet#last() 1137 */ 1138 public Object last() {return ss.last();} 1139 } 1140 1141 /** 1142 * Returns an unmodifiable view of the specified list. This method allows 1143 * modules to provide users with "read-only" access to internal 1144 * lists. Query operations on the returned list "read through" to the 1145 * specified list, and attempts to modify the returned list, whether 1146 * direct or via its iterator, result in an 1147 * <tt>UnsupportedOperationException</tt>.<p> 1148 * 1149 * The returned list will be serializable if the specified list 1150 * is serializable. Similarly, the returned list will implement 1151 * {@link RandomAccess} if the specified list does. 1152 * the 1153 * 1154 * @param list the list for which an unmodifiable view is to be returned. 1155 * @return an unmodifiable view of the specified list. 1156 */ 1157 public static List unmodifiableList(List list) { 1158 return (list instanceof RandomAccess ? 1159 new UnmodifiableRandomAccessList(list) : 1160 new UnmodifiableList(list)); 1161 } 1162 1163 /** 1164 * @serial include 1165 */ 1166 static class UnmodifiableList extends UnmodifiableCollection 1167 implements List { 1168 static final long serialVersionUID = -283967356065247728L; 1169 List list; 1170 1171 UnmodifiableList(List list) { 1172 super(list); 1173 this.list = list; 1174 } 1175 1176 /** 1177 * @see java.util.List#equals(java.lang.Object) 1178 */ 1179 public boolean equals(Object o) {return list.equals(o);} 1180 /** 1181 * @see java.util.List#hashCode() 1182 */ 1183 public int hashCode() {return list.hashCode();} 1184 1185 /** 1186 * @see java.util.List#get(int) 1187 */ 1188 public Object get(int index) {return list.get(index);} 1189 /** 1190 * @see java.util.List#set(int, java.lang.Object) 1191 */ 1192 public Object set(int index, Object element) { 1193 throw new UnsupportedOperationException(); 1194 } 1195 /** 1196 * @see java.util.List#add(int, java.lang.Object) 1197 */ 1198 public void add(int index, Object element) { 1199 throw new UnsupportedOperationException(); 1200 } 1201 /** 1202 * @see java.util.List#remove(int) 1203 */ 1204 public Object remove(int index) { 1205 throw new UnsupportedOperationException(); 1206 } 1207 /** 1208 * @see java.util.List#indexOf(java.lang.Object) 1209 */ 1210 public int indexOf(Object o) {return list.indexOf(o);} 1211 /** 1212 * @see java.util.List#lastIndexOf(java.lang.Object) 1213 */ 1214 public int lastIndexOf(Object o) {return list.lastIndexOf(o);} 1215 /** 1216 * @see java.util.List#addAll(int, java.util.Collection) 1217 */ 1218 public boolean addAll(int index, Collection c) { 1219 throw new UnsupportedOperationException(); 1220 } 1221 /** 1222 * @see java.util.List#listIterator() 1223 */ 1224 public ListIterator listIterator() {return listIterator(0);} 1225 1226 /** 1227 * @see java.util.List#listIterator(int) 1228 */ 1229 public ListIterator listIterator(final int index) { 1230 return new ListIterator() { 1231 ListIterator i = list.listIterator(index); 1232 1233 public boolean hasNext() {return i.hasNext();} 1234 public Object next() {return i.next();} 1235 public boolean hasPrevious() {return i.hasPrevious();} 1236 public Object previous() {return i.previous();} 1237 public int nextIndex() {return i.nextIndex();} 1238 public int previousIndex() {return i.previousIndex();} 1239 1240 public void remove() { 1241 throw new UnsupportedOperationException(); 1242 } 1243 public void set(Object o) { 1244 throw new UnsupportedOperationException(); 1245 } 1246 public void add(Object o) { 1247 throw new UnsupportedOperationException(); 1248 } 1249 }; 1250 } 1251 1252 /** 1253 * @see java.util.List#subList(int, int) 1254 */ 1255 public List subList(int fromIndex, int toIndex) { 1256 return new UnmodifiableList(list.subList(fromIndex, toIndex)); 1257 } 1258 } 1259 1260 /** 1261 * @serial include 1262 */ 1263 static class UnmodifiableRandomAccessList extends UnmodifiableList 1264 implements RandomAccess 1265 { 1266 UnmodifiableRandomAccessList(List list) { 1267 super(list); 1268 } 1269 1270 /** 1271 * @see railo.commons.collections.Collections.UnmodifiableList#subList(int, int) 1272 */ 1273 public List subList(int fromIndex, int toIndex) { 1274 return new UnmodifiableRandomAccessList( 1275 list.subList(fromIndex, toIndex)); 1276 } 1277 } 1278 1279 /** 1280 * Returns an unmodifiable view of the specified map. This method 1281 * allows modules to provide users with "read-only" access to internal 1282 * maps. Query operations on the returned map "read through" 1283 * to the specified map, and attempts to modify the returned 1284 * map, whether direct or via its collection views, result in an 1285 * <tt>UnsupportedOperationException</tt>.<p> 1286 * 1287 * The returned map will be serializable if the specified map 1288 * is serializable. 1289 * 1290 * @param m the map for which an unmodifiable view is to be returned. 1291 * @return an unmodifiable view of the specified map. 1292 */ 1293 public static Map unmodifiableMap(Map m) { 1294 return new UnmodifiableMap(m); 1295 } 1296 1297 /** 1298 * @serial include 1299 */ 1300 private static class UnmodifiableMap implements Map, Serializable { 1301 // use serialVersionUID from JDK 1.2.2 for interoperability 1302 private static final long serialVersionUID = -1034234728574286014L; 1303 1304 private final Map m; 1305 1306 UnmodifiableMap(Map m) { 1307 if (m==null) 1308 throw new NullPointerException(); 1309 this.m = m; 1310 } 1311 1312 /** 1313 * @see java.util.Map#size() 1314 */ 1315 public int size() {return m.size();} 1316 /** 1317 * @see java.util.Map#isEmpty() 1318 */ 1319 public boolean isEmpty() {return m.isEmpty();} 1320 /** 1321 * @see java.util.Map#containsKey(java.lang.Object) 1322 */ 1323 public boolean containsKey(Object key) {return m.containsKey(key);} 1324 /** 1325 * @see java.util.Map#containsValue(java.lang.Object) 1326 */ 1327 public boolean containsValue(Object val) {return m.containsValue(val);} 1328 /** 1329 * @see java.util.Map#get(java.lang.Object) 1330 */ 1331 public Object get(Object key) {return m.get(key);} 1332 1333 /** 1334 * @see java.util.Map#put(java.lang.Object, java.lang.Object) 1335 */ 1336 public Object put(Object key, Object value) { 1337 throw new UnsupportedOperationException(); 1338 } 1339 /** 1340 * @see java.util.Map#remove(java.lang.Object) 1341 */ 1342 public Object remove(Object key) { 1343 throw new UnsupportedOperationException(); 1344 } 1345 /** 1346 * @see java.util.Map#putAll(java.util.Map) 1347 */ 1348 public void putAll(Map t) { 1349 throw new UnsupportedOperationException(); 1350 } 1351 /** 1352 * @see java.util.Map#clear() 1353 */ 1354 public void clear() { 1355 throw new UnsupportedOperationException(); 1356 } 1357 1358 private transient Set keySet = null; 1359 private transient Set entrySet = null; 1360 private transient Collection values = null; 1361 1362 /** 1363 * @see java.util.Map#keySet() 1364 */ 1365 public Set keySet() { 1366 if (keySet==null) 1367 keySet = unmodifiableSet(m.keySet()); 1368 return keySet; 1369 } 1370 1371 /** 1372 * @see java.util.Map#entrySet() 1373 */ 1374 public Set entrySet() { 1375 if (entrySet==null) 1376 entrySet = new UnmodifiableEntrySet(m.entrySet()); 1377 return entrySet; 1378 } 1379 1380 /** 1381 * @see java.util.Map#values() 1382 */ 1383 public Collection values() { 1384 if (values==null) 1385 values = unmodifiableCollection(m.values()); 1386 return values; 1387 } 1388 1389 /** 1390 * @see java.util.Map#equals(java.lang.Object) 1391 */ 1392 public boolean equals(Object o) {return m.equals(o);} 1393 /** 1394 * @see java.util.Map#hashCode() 1395 */ 1396 public int hashCode() {return m.hashCode();} 1397 /** 1398 * @see java.lang.Object#toString() 1399 */ 1400 public String toString() {return m.toString();} 1401 1402 /** 1403 * We need this class in addition to UnmodifiableSet as 1404 * Map.Entries themselves permit modification of the backing Map 1405 * via their setValue operation. This class is subtle: there are 1406 * many possible attacks that must be thwarted. 1407 * 1408 * @serial include 1409 */ 1410 static class UnmodifiableEntrySet extends UnmodifiableSet { 1411 UnmodifiableEntrySet(Set s) { 1412 super(s); 1413 } 1414 1415 /** 1416 * @see java.util.Set#iterator() 1417 */ 1418 public Iterator iterator() { 1419 return new Iterator() { 1420 Iterator i = c.iterator(); 1421 1422 public boolean hasNext() { 1423 return i.hasNext(); 1424 } 1425 public Object next() { 1426 return new UnmodifiableEntry((Map.Entry)i.next()); 1427 } 1428 public void remove() { 1429 throw new UnsupportedOperationException(); 1430 } 1431 }; 1432 } 1433 1434 /** 1435 * @see java.util.Set#toArray() 1436 */ 1437 public Object[] toArray() { 1438 Object[] a = c.toArray(); 1439 for (int i=0; i<a.length; i++) 1440 a[i] = new UnmodifiableEntry((Map.Entry)a[i]); 1441 return a; 1442 } 1443 1444 /** 1445 * @see java.util.Set#toArray(java.lang.Object[]) 1446 */ 1447 public Object[] toArray(Object a[]) { 1448 // We don't pass a to c.toArray, to avoid window of 1449 // vulnerability wherein an unscrupulous multithreaded client 1450 // could get his hands on raw (unwrapped) Entries from c. 1451 Object[] arr = c.toArray(a.length==0 ? a : 1452 (Object[])java.lang.reflect.Array.newInstance( 1453 a.getClass().getComponentType(), 0)); 1454 for (int i=0; i<arr.length; i++) 1455 arr[i] = new UnmodifiableEntry((Map.Entry)arr[i]); 1456 1457 if (arr.length > a.length) 1458 return arr; 1459 1460 System.arraycopy(arr, 0, a, 0, arr.length); 1461 if (a.length > arr.length) 1462 a[arr.length] = null; 1463 return a; 1464 } 1465 1466 /** 1467 * This method is overridden to protect the backing set against 1468 * an object with a nefarious equals function that senses 1469 * that the equality-candidate is Map.Entry and calls its 1470 * setValue method. 1471 * @param o 1472 * @return contains or not 1473 */ 1474 public boolean contains(Object o) { 1475 if (!(o instanceof Map.Entry)) 1476 return false; 1477 return c.contains(new UnmodifiableEntry((Map.Entry)o)); 1478 } 1479 1480 /** 1481 * The next two methods are overridden to protect against 1482 * an unscrupulous List whose contains(Object o) method senses 1483 * when o is a Map.Entry, and calls o.setValue. 1484 * @param coll 1485 * @return boolean 1486 */ 1487 public boolean containsAll(Collection coll) { 1488 Iterator e = coll.iterator(); 1489 while (e.hasNext()) 1490 if(!contains(e.next())) // Invokes safe contains() above 1491 return false; 1492 return true; 1493 } 1494 /** 1495 * @see railo.commons.collections.Collections.UnmodifiableSet#equals(java.lang.Object) 1496 */ 1497 public boolean equals(Object o) { 1498 if (o == this) 1499 return true; 1500 1501 if (!(o instanceof Set)) 1502 return false; 1503 Set s = (Set) o; 1504 if (s.size() != c.size()) 1505 return false; 1506 return containsAll(s); // Invokes safe containsAll() above 1507 } 1508 1509 /** 1510 * This "wrapper class" serves two purposes: it prevents 1511 * the client from modifying the backing Map, by short-circuiting 1512 * the setValue method, and it protects the backing Map against 1513 * an ill-behaved Map.Entry that attempts to modify another 1514 * Map Entry when asked to perform an equality check. 1515 */ 1516 private static class UnmodifiableEntry implements Map.Entry { 1517 private Map.Entry e; 1518 1519 UnmodifiableEntry(Map.Entry e) {this.e = e;} 1520 1521 /** 1522 * @see java.util.Map.Entry#getKey() 1523 */ 1524 public Object getKey() {return e.getKey();} 1525 /** 1526 * @see java.util.Map.Entry#getValue() 1527 */ 1528 public Object getValue() {return e.getValue();} 1529 /** 1530 * @see java.util.Map.Entry#setValue(java.lang.Object) 1531 */ 1532 public Object setValue(Object value) { 1533 throw new UnsupportedOperationException(); 1534 } 1535 /** 1536 * @see java.util.Map.Entry#hashCode() 1537 */ 1538 public int hashCode() {return e.hashCode();} 1539 /** 1540 * @see java.util.Map.Entry#equals(java.lang.Object) 1541 */ 1542 public boolean equals(Object o) { 1543 if (!(o instanceof Map.Entry)) 1544 return false; 1545 Map.Entry t = (Map.Entry)o; 1546 return eq(e.getKey(), t.getKey()) && 1547 eq(e.getValue(), t.getValue()); 1548 } 1549 /** 1550 * @see java.lang.Object#toString() 1551 */ 1552 public String toString() {return e.toString();} 1553 } 1554 } 1555 } 1556 1557 /** 1558 * Returns an unmodifiable view of the specified sorted map. This method 1559 * allows modules to provide users with "read-only" access to internal 1560 * sorted maps. Query operations on the returned sorted map "read through" 1561 * to the specified sorted map. Attempts to modify the returned 1562 * sorted map, whether direct, via its collection views, or via its 1563 * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in 1564 * an <tt>UnsupportedOperationException</tt>.<p> 1565 * 1566 * The returned sorted map will be serializable if the specified sorted map 1567 * is serializable. 1568 * 1569 * @param m the sorted map for which an unmodifiable view is to be 1570 * returned. 1571 * @return an unmodifiable view of the specified sorted map. 1572 */ 1573 public static SortedMap unmodifiableSortedMap(SortedMap m) { 1574 return new UnmodifiableSortedMap(m); 1575 } 1576 1577 /** 1578 * @serial include 1579 */ 1580 static class UnmodifiableSortedMap extends UnmodifiableMap 1581 implements SortedMap, Serializable { 1582 private SortedMap sm; 1583 1584 UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;} 1585 1586 /** 1587 * @see java.util.SortedMap#comparator() 1588 */ 1589 public Comparator comparator() {return sm.comparator();} 1590 1591 /** 1592 * @see java.util.SortedMap#subMap(java.lang.Object, java.lang.Object) 1593 */ 1594 public SortedMap subMap(Object fromKey, Object toKey) { 1595 return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey)); 1596 } 1597 /** 1598 * @see java.util.SortedMap#headMap(java.lang.Object) 1599 */ 1600 public SortedMap headMap(Object toKey) { 1601 return new UnmodifiableSortedMap(sm.headMap(toKey)); 1602 } 1603 /** 1604 * @see java.util.SortedMap#tailMap(java.lang.Object) 1605 */ 1606 public SortedMap tailMap(Object fromKey) { 1607 return new UnmodifiableSortedMap(sm.tailMap(fromKey)); 1608 } 1609 1610 /** 1611 * @see java.util.SortedMap#firstKey() 1612 */ 1613 public Object firstKey() {return sm.firstKey();} 1614 /** 1615 * @see java.util.SortedMap#lastKey() 1616 */ 1617 public Object lastKey() {return sm.lastKey();} 1618 } 1619 1620 1621 // Synch Wrappers 1622 1623 /** 1624 * Returns a synchronized (thread-safe) collection backed by the specified 1625 * collection. In order to guarantee serial access, it is critical that 1626 * <strong>all</strong> access to the backing collection is accomplished 1627 * through the returned collection.<p> 1628 * 1629 * It is imperative that the user manually synchronize on the returned 1630 * collection when iterating over it: 1631 * <pre> 1632 * Collection c = Collections.synchronizedCollection(myCollection); 1633 * ... 1634 * synchronized(c) { 1635 * Iterator i = c.iterator(); // Must be in the synchronized block 1636 * while (i.hasNext()) 1637 * foo(i.next()); 1638 * } 1639 * </pre> 1640 * Failure to follow this advice may result in non-deterministic behavior. 1641 * 1642 * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt> 1643 * and <tt>equals</tt> operations through to the backing collection, but 1644 * relies on <tt>Object</tt>'s equals and hashCode methods. This is 1645 * necessary to preserve the contracts of these operations in the case 1646 * that the backing collection is a set or a list.<p> 1647 * 1648 * The returned collection will be serializable if the specified collection 1649 * is serializable. 1650 * 1651 * @param c the collection to be "wrapped" in a synchronized collection. 1652 * @return a synchronized view of the specified collection. 1653 */ 1654 public static Collection synchronizedCollection(Collection c) { 1655 return new SynchronizedCollection(c); 1656 } 1657 1658 static Collection synchronizedCollection(Collection c, Object mutex) { 1659 return new SynchronizedCollection(c, mutex); 1660 } 1661 1662 /** 1663 * @serial include 1664 */ 1665 static class SynchronizedCollection implements Collection, Serializable { 1666 // use serialVersionUID from JDK 1.2.2 for interoperability 1667 private static final long serialVersionUID = 3053995032091335093L; 1668 1669 Collection c; // Backing Collection 1670 Object mutex; // Object on which to synchronize 1671 1672 SynchronizedCollection(Collection c) { 1673 if (c==null) 1674 throw new NullPointerException(); 1675 this.c = c; 1676 mutex = this; 1677 } 1678 SynchronizedCollection(Collection c, Object mutex) { 1679 this.c = c; 1680 this.mutex = mutex; 1681 } 1682 1683 /** 1684 * @see java.util.Collection#size() 1685 */ 1686 public int size() { 1687 synchronized(mutex) {return c.size();} 1688 } 1689 /** 1690 * @see java.util.Collection#isEmpty() 1691 */ 1692 public boolean isEmpty() { 1693 synchronized(mutex) {return c.isEmpty();} 1694 } 1695 /** 1696 * @see java.util.Collection#contains(java.lang.Object) 1697 */ 1698 public boolean contains(Object o) { 1699 synchronized(mutex) {return c.contains(o);} 1700 } 1701 /** 1702 * @see java.util.Collection#toArray() 1703 */ 1704 public Object[] toArray() { 1705 synchronized(mutex) {return c.toArray();} 1706 } 1707 /** 1708 * @see java.util.Collection#toArray(java.lang.Object[]) 1709 */ 1710 public Object[] toArray(Object[] a) { 1711 synchronized(mutex) {return c.toArray(a);} 1712 } 1713 1714 /** 1715 * @see java.util.Collection#iterator() 1716 */ 1717 public Iterator iterator() { 1718 return c.iterator(); // Must be manually synched by user! 1719 } 1720 1721 /** 1722 * @see java.util.Collection#add(java.lang.Object) 1723 */ 1724 public boolean add(Object o) { 1725 synchronized(mutex) {return c.add(o);} 1726 } 1727 /** 1728 * @see java.util.Collection#remove(java.lang.Object) 1729 */ 1730 public boolean remove(Object o) { 1731 synchronized(mutex) {return c.remove(o);} 1732 } 1733 1734 /** 1735 * @see java.util.Collection#containsAll(java.util.Collection) 1736 */ 1737 public boolean containsAll(Collection coll) { 1738 synchronized(mutex) {return c.containsAll(coll);} 1739 } 1740 /** 1741 * @see java.util.Collection#addAll(java.util.Collection) 1742 */ 1743 public boolean addAll(Collection coll) { 1744 synchronized(mutex) {return c.addAll(coll);} 1745 } 1746 /** 1747 * @see java.util.Collection#removeAll(java.util.Collection) 1748 */ 1749 public boolean removeAll(Collection coll) { 1750 synchronized(mutex) {return c.removeAll(coll);} 1751 } 1752 /** 1753 * @see java.util.Collection#retainAll(java.util.Collection) 1754 */ 1755 public boolean retainAll(Collection coll) { 1756 synchronized(mutex) {return c.retainAll(coll);} 1757 } 1758 /** 1759 * @see java.util.Collection#clear() 1760 */ 1761 public void clear() { 1762 synchronized(mutex) {c.clear();} 1763 } 1764 /** 1765 * @see java.lang.Object#toString() 1766 */ 1767 public String toString() { 1768 synchronized(mutex) {return c.toString();} 1769 } 1770 } 1771 1772 /** 1773 * Returns a synchronized (thread-safe) set backed by the specified 1774 * set. In order to guarantee serial access, it is critical that 1775 * <strong>all</strong> access to the backing set is accomplished 1776 * through the returned set.<p> 1777 * 1778 * It is imperative that the user manually synchronize on the returned 1779 * set when iterating over it: 1780 * <pre> 1781 * Set s = Collections.synchronizedSet(new HashSet()); 1782 * ... 1783 * synchronized(s) { 1784 * Iterator i = s.iterator(); // Must be in the synchronized block 1785 * while (i.hasNext()) 1786 * foo(i.next()); 1787 * } 1788 * </pre> 1789 * Failure to follow this advice may result in non-deterministic behavior. 1790 * 1791 * <p>The returned set will be serializable if the specified set is 1792 * serializable. 1793 * 1794 * @param s the set to be "wrapped" in a synchronized set. 1795 * @return a synchronized view of the specified set. 1796 */ 1797 public static Set synchronizedSet(Set s) { 1798 return new SynchronizedSet(s); 1799 } 1800 1801 static Set synchronizedSet(Set s, Object mutex) { 1802 return new SynchronizedSet(s, mutex); 1803 } 1804 1805 /** 1806 * @serial include 1807 */ 1808 static class SynchronizedSet extends SynchronizedCollection 1809 implements Set { 1810 SynchronizedSet(Set s) { 1811 super(s); 1812 } 1813 SynchronizedSet(Set s, Object mutex) { 1814 super(s, mutex); 1815 } 1816 1817 /** 1818 * @see java.util.Set#equals(java.lang.Object) 1819 */ 1820 public boolean equals(Object o) { 1821 synchronized(mutex) {return c.equals(o);} 1822 } 1823 /** 1824 * @see java.util.Set#hashCode() 1825 */ 1826 public int hashCode() { 1827 synchronized(mutex) {return c.hashCode();} 1828 } 1829 } 1830 1831 /** 1832 * Returns a synchronized (thread-safe) sorted set backed by the specified 1833 * sorted set. In order to guarantee serial access, it is critical that 1834 * <strong>all</strong> access to the backing sorted set is accomplished 1835 * through the returned sorted set (or its views).<p> 1836 * 1837 * It is imperative that the user manually synchronize on the returned 1838 * sorted set when iterating over it or any of its <tt>subSet</tt>, 1839 * <tt>headSet</tt>, or <tt>tailSet</tt> views. 1840 * <pre> 1841 * SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet()); 1842 * ... 1843 * synchronized(s) { 1844 * Iterator i = s.iterator(); // Must be in the synchronized block 1845 * while (i.hasNext()) 1846 * foo(i.next()); 1847 * } 1848 * </pre> 1849 * or: 1850 * <pre> 1851 * SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet()); 1852 * SortedSet s2 = s.headSet(foo); 1853 * ... 1854 * synchronized(s) { // Note: s, not s2!!! 1855 * Iterator i = s2.iterator(); // Must be in the synchronized block 1856 * while (i.hasNext()) 1857 * foo(i.next()); 1858 * } 1859 * </pre> 1860 * Failure to follow this advice may result in non-deterministic behavior. 1861 * 1862 * <p>The returned sorted set will be serializable if the specified 1863 * sorted set is serializable. 1864 * 1865 * @param s the sorted set to be "wrapped" in a synchronized sorted set. 1866 * @return a synchronized view of the specified sorted set. 1867 */ 1868 public static SortedSet synchronizedSortedSet(SortedSet s) { 1869 return new SynchronizedSortedSet(s); 1870 } 1871 1872 /** 1873 * @serial include 1874 */ 1875 static class SynchronizedSortedSet extends SynchronizedSet 1876 implements SortedSet 1877 { 1878 private SortedSet ss; 1879 1880 SynchronizedSortedSet(SortedSet s) { 1881 super(s); 1882 ss = s; 1883 } 1884 SynchronizedSortedSet(SortedSet s, Object mutex) { 1885 super(s, mutex); 1886 ss = s; 1887 } 1888 1889 /** 1890 * @see java.util.SortedSet#comparator() 1891 */ 1892 public Comparator comparator() { 1893 synchronized(mutex) {return ss.comparator();} 1894 } 1895 1896 /** 1897 * @see java.util.SortedSet#subSet(java.lang.Object, java.lang.Object) 1898 */ 1899 public SortedSet subSet(Object fromElement, Object toElement) { 1900 synchronized(mutex) { 1901 return new SynchronizedSortedSet( 1902 ss.subSet(fromElement, toElement), mutex); 1903 } 1904 } 1905 /** 1906 * @see java.util.SortedSet#headSet(java.lang.Object) 1907 */ 1908 public SortedSet headSet(Object toElement) { 1909 synchronized(mutex) { 1910 return new SynchronizedSortedSet(ss.headSet(toElement), mutex); 1911 } 1912 } 1913 /** 1914 * @see java.util.SortedSet#tailSet(java.lang.Object) 1915 */ 1916 public SortedSet tailSet(Object fromElement) { 1917 synchronized(mutex) { 1918 return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex); 1919 } 1920 } 1921 1922 /** 1923 * @see java.util.SortedSet#first() 1924 */ 1925 public Object first() { 1926 synchronized(mutex) {return ss.first();} 1927 } 1928 /** 1929 * @see java.util.SortedSet#last() 1930 */ 1931 public Object last() { 1932 synchronized(mutex) {return ss.last();} 1933 } 1934 } 1935 1936 /** 1937 * Returns a synchronized (thread-safe) list backed by the specified 1938 * list. In order to guarantee serial access, it is critical that 1939 * <strong>all</strong> access to the backing list is accomplished 1940 * through the returned list.<p> 1941 * 1942 * It is imperative that the user manually synchronize on the returned 1943 * list when iterating over it: 1944 * <pre> 1945 * List list = Collections.synchronizedList(new ArrayList()); 1946 * ... 1947 * synchronized(list) { 1948 * Iterator i = list.iterator(); // Must be in synchronized block 1949 * while (i.hasNext()) 1950 * foo(i.next()); 1951 * } 1952 * </pre> 1953 * Failure to follow this advice may result in non-deterministic behavior. 1954 * 1955 * <p>The returned list will be serializable if the specified list is 1956 * serializable. 1957 * 1958 * @param list the list to be "wrapped" in a synchronized list. 1959 * @return a synchronized view of the specified list. 1960 */ 1961 public static List synchronizedList(List list) { 1962 return (list instanceof RandomAccess ? 1963 new SynchronizedRandomAccessList(list) : 1964 new SynchronizedList(list)); 1965 } 1966 1967 static List synchronizedList(List list, Object mutex) { 1968 return (list instanceof RandomAccess ? 1969 new SynchronizedRandomAccessList(list, mutex) : 1970 new SynchronizedList(list, mutex)); 1971 } 1972 1973 /** 1974 * @serial include 1975 */ 1976 static class SynchronizedList extends SynchronizedCollection 1977 implements List { 1978 static final long serialVersionUID = -7754090372962971524L; 1979 1980 List list; 1981 1982 SynchronizedList(List list) { 1983 super(list); 1984 this.list = list; 1985 } 1986 SynchronizedList(List list, Object mutex) { 1987 super(list, mutex); 1988 this.list = list; 1989 } 1990 1991 /** 1992 * @see java.util.List#equals(java.lang.Object) 1993 */ 1994 public boolean equals(Object o) { 1995 synchronized(mutex) {return list.equals(o);} 1996 } 1997 /** 1998 * @see java.util.List#hashCode() 1999 */ 2000 public int hashCode() { 2001 synchronized(mutex) {return list.hashCode();} 2002 } 2003 2004 /** 2005 * @see java.util.List#get(int) 2006 */ 2007 public Object get(int index) { 2008 synchronized(mutex) {return list.get(index);} 2009 } 2010 /** 2011 * @see java.util.List#set(int, java.lang.Object) 2012 */ 2013 public Object set(int index, Object element) { 2014 synchronized(mutex) {return list.set(index, element);} 2015 } 2016 /** 2017 * @see java.util.List#add(int, java.lang.Object) 2018 */ 2019 public void add(int index, Object element) { 2020 synchronized(mutex) {list.add(index, element);} 2021 } 2022 /** 2023 * @see java.util.List#remove(int) 2024 */ 2025 public Object remove(int index) { 2026 synchronized(mutex) {return list.remove(index);} 2027 } 2028 2029 /** 2030 * @see java.util.List#indexOf(java.lang.Object) 2031 */ 2032 public int indexOf(Object o) { 2033 synchronized(mutex) {return list.indexOf(o);} 2034 } 2035 /** 2036 * @see java.util.List#lastIndexOf(java.lang.Object) 2037 */ 2038 public int lastIndexOf(Object o) { 2039 synchronized(mutex) {return list.lastIndexOf(o);} 2040 } 2041 2042 /** 2043 * @see java.util.List#addAll(int, java.util.Collection) 2044 */ 2045 public boolean addAll(int index, Collection c) { 2046 synchronized(mutex) {return list.addAll(index, c);} 2047 } 2048 2049 /** 2050 * @see java.util.List#listIterator() 2051 */ 2052 public ListIterator listIterator() { 2053 return list.listIterator(); // Must be manually synched by user 2054 } 2055 2056 /** 2057 * @see java.util.List#listIterator(int) 2058 */ 2059 public ListIterator listIterator(int index) { 2060 return list.listIterator(index); // Must be manually synched by usr 2061 } 2062 2063 /** 2064 * @see java.util.List#subList(int, int) 2065 */ 2066 public List subList(int fromIndex, int toIndex) { 2067 synchronized(mutex) { 2068 return new SynchronizedList(list.subList(fromIndex, toIndex), 2069 mutex); 2070 } 2071 } 2072 } 2073 2074 /** 2075 * @serial include 2076 */ 2077 static class SynchronizedRandomAccessList extends SynchronizedList 2078 implements RandomAccess 2079 { 2080 SynchronizedRandomAccessList(List list) { 2081 super(list); 2082 } 2083 2084 SynchronizedRandomAccessList(List list, Object mutex) { 2085 super(list, mutex); 2086 } 2087 2088 /** 2089 * @see railo.commons.collections.Collections.SynchronizedList#subList(int, int) 2090 */ 2091 public List subList(int fromIndex, int toIndex) { 2092 synchronized(mutex) { 2093 return new SynchronizedRandomAccessList( 2094 list.subList(fromIndex, toIndex), mutex); 2095 } 2096 } 2097 } 2098 2099 /** 2100 * Returns a synchronized (thread-safe) map backed by the specified 2101 * map. In order to guarantee serial access, it is critical that 2102 * <strong>all</strong> access to the backing map is accomplished 2103 * through the returned map.<p> 2104 * 2105 * It is imperative that the user manually synchronize on the returned 2106 * map when iterating over any of its collection views: 2107 * <pre> 2108 * Map m = Collections.synchronizedMap(new HashMap()); 2109 * ... 2110 * Set s = m.keySet(); // Needn't be in synchronized block 2111 * ... 2112 * synchronized(m) { // Synchronizing on m, not s! 2113 * Iterator i = s.iterator(); // Must be in synchronized block 2114 * while (i.hasNext()) 2115 * foo(i.next()); 2116 * } 2117 * </pre> 2118 * Failure to follow this advice may result in non-deterministic behavior. 2119 * 2120 * <p>The returned map will be serializable if the specified map is 2121 * serializable. 2122 * 2123 * @param m the map to be "wrapped" in a synchronized map. 2124 * @return a synchronized view of the specified map. 2125 */ 2126 public static Map synchronizedMap(Map m) { 2127 return new SynchronizedMap(m); 2128 } 2129 2130 /** 2131 * @serial include 2132 */ 2133 private static class SynchronizedMap implements Map, Serializable { 2134 // use serialVersionUID from JDK 1.2.2 for interoperability 2135 private static final long serialVersionUID = 1978198479659022715L; 2136 2137 private Map m; // Backing Map 2138 Object mutex; // Object on which to synchronize 2139 2140 SynchronizedMap(Map m) { 2141 if (m==null) 2142 throw new NullPointerException(); 2143 this.m = m; 2144 mutex = this; 2145 } 2146 2147 SynchronizedMap(Map m, Object mutex) { 2148 this.m = m; 2149 this.mutex = mutex; 2150 } 2151 2152 /** 2153 * @see java.util.Map#size() 2154 */ 2155 public int size() { 2156 synchronized(mutex) {return m.size();} 2157 } 2158 /** 2159 * @see java.util.Map#isEmpty() 2160 */ 2161 public boolean isEmpty(){ 2162 synchronized(mutex) {return m.isEmpty();} 2163 } 2164 /** 2165 * @see java.util.Map#containsKey(java.lang.Object) 2166 */ 2167 public boolean containsKey(Object key) { 2168 synchronized(mutex) {return m.containsKey(key);} 2169 } 2170 /** 2171 * @see java.util.Map#containsValue(java.lang.Object) 2172 */ 2173 public boolean containsValue(Object value){ 2174 synchronized(mutex) {return m.containsValue(value);} 2175 } 2176 /** 2177 * @see java.util.Map#get(java.lang.Object) 2178 */ 2179 public Object get(Object key) { 2180 synchronized(mutex) {return m.get(key);} 2181 } 2182 2183 /** 2184 * @see java.util.Map#put(java.lang.Object, java.lang.Object) 2185 */ 2186 public Object put(Object key, Object value) { 2187 synchronized(mutex) {return m.put(key, value);} 2188 } 2189 /** 2190 * @see java.util.Map#remove(java.lang.Object) 2191 */ 2192 public Object remove(Object key) { 2193 synchronized(mutex) {return m.remove(key);} 2194 } 2195 /** 2196 * @see java.util.Map#putAll(java.util.Map) 2197 */ 2198 public void putAll(Map map) { 2199 synchronized(mutex) {m.putAll(map);} 2200 } 2201 /** 2202 * @see java.util.Map#clear() 2203 */ 2204 public void clear() { 2205 synchronized(mutex) {m.clear();} 2206 } 2207 2208 private transient Set keySet = null; 2209 private transient Set entrySet = null; 2210 private transient Collection values = null; 2211 2212 /** 2213 * @see java.util.Map#keySet() 2214 */ 2215 public Set keySet() { 2216 synchronized(mutex) { 2217 if (keySet==null) 2218 keySet = new SynchronizedSet(m.keySet(), mutex); 2219 return keySet; 2220 } 2221 } 2222 2223 /** 2224 * @see java.util.Map#entrySet() 2225 */ 2226 public Set entrySet() { 2227 synchronized(mutex) { 2228 if (entrySet==null) 2229 entrySet = new SynchronizedSet(m.entrySet(), mutex); 2230 return entrySet; 2231 } 2232 } 2233 2234 /** 2235 * @see java.util.Map#values() 2236 */ 2237 public Collection values() { 2238 synchronized(mutex) { 2239 if (values==null) 2240 values = new SynchronizedCollection(m.values(), mutex); 2241 return values; 2242 } 2243 } 2244 2245 /** 2246 * @see java.util.Map#equals(java.lang.Object) 2247 */ 2248 public boolean equals(Object o) { 2249 synchronized(mutex) {return m.equals(o);} 2250 } 2251 /** 2252 * @see java.util.Map#hashCode() 2253 */ 2254 public int hashCode() { 2255 synchronized(mutex) {return m.hashCode();} 2256 } 2257 /** 2258 * @see java.lang.Object#toString() 2259 */ 2260 public String toString() { 2261 synchronized(mutex) {return m.toString();} 2262 } 2263 } 2264 2265 /** 2266 * Returns a synchronized (thread-safe) sorted map backed by the specified 2267 * sorted map. In order to guarantee serial access, it is critical that 2268 * <strong>all</strong> access to the backing sorted map is accomplished 2269 * through the returned sorted map (or its views).<p> 2270 * 2271 * It is imperative that the user manually synchronize on the returned 2272 * sorted map when iterating over any of its collection views, or the 2273 * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or 2274 * <tt>tailMap</tt> views. 2275 * <pre> 2276 * SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap()); 2277 * ... 2278 * Set s = m.keySet(); // Needn't be in synchronized block 2279 * ... 2280 * synchronized(m) { // Synchronizing on m, not s! 2281 * Iterator i = s.iterator(); // Must be in synchronized block 2282 * while (i.hasNext()) 2283 * foo(i.next()); 2284 * } 2285 * </pre> 2286 * or: 2287 * <pre> 2288 * SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap()); 2289 * SortedMap m2 = m.subMap(foo, bar); 2290 * ... 2291 * Set s2 = m2.keySet(); // Needn't be in synchronized block 2292 * ... 2293 * synchronized(m) { // Synchronizing on m, not m2 or s2! 2294 * Iterator i = s.iterator(); // Must be in synchronized block 2295 * while (i.hasNext()) 2296 * foo(i.next()); 2297 * } 2298 * </pre> 2299 * Failure to follow this advice may result in non-deterministic behavior. 2300 * 2301 * <p>The returned sorted map will be serializable if the specified 2302 * sorted map is serializable. 2303 * 2304 * @param m the sorted map to be "wrapped" in a synchronized sorted map. 2305 * @return a synchronized view of the specified sorted map. 2306 */ 2307 public static SortedMap synchronizedSortedMap(SortedMap m) { 2308 return new SynchronizedSortedMap(m); 2309 } 2310 2311 2312 /** 2313 * @serial include 2314 */ 2315 static class SynchronizedSortedMap extends SynchronizedMap 2316 implements SortedMap 2317 { 2318 private SortedMap sm; 2319 2320 SynchronizedSortedMap(SortedMap m) { 2321 super(m); 2322 sm = m; 2323 } 2324 SynchronizedSortedMap(SortedMap m, Object mutex) { 2325 super(m, mutex); 2326 sm = m; 2327 } 2328 2329 /** 2330 * @see java.util.SortedMap#comparator() 2331 */ 2332 public Comparator comparator() { 2333 synchronized(mutex) {return sm.comparator();} 2334 } 2335 2336 /** 2337 * @see java.util.SortedMap#subMap(java.lang.Object, java.lang.Object) 2338 */ 2339 public SortedMap subMap(Object fromKey, Object toKey) { 2340 synchronized(mutex) { 2341 return new SynchronizedSortedMap( 2342 sm.subMap(fromKey, toKey), mutex); 2343 } 2344 } 2345 /** 2346 * @see java.util.SortedMap#headMap(java.lang.Object) 2347 */ 2348 public SortedMap headMap(Object toKey) { 2349 synchronized(mutex) { 2350 return new SynchronizedSortedMap(sm.headMap(toKey), mutex); 2351 } 2352 } 2353 /** 2354 * @see java.util.SortedMap#tailMap(java.lang.Object) 2355 */ 2356 public SortedMap tailMap(Object fromKey) { 2357 synchronized(mutex) { 2358 return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex); 2359 } 2360 } 2361 2362 /** 2363 * @see java.util.SortedMap#firstKey() 2364 */ 2365 public Object firstKey() { 2366 synchronized(mutex) {return sm.firstKey();} 2367 } 2368 /** 2369 * @see java.util.SortedMap#lastKey() 2370 */ 2371 public Object lastKey() { 2372 synchronized(mutex) {return sm.lastKey();} 2373 } 2374 } 2375 2376 2377 // Miscellaneous 2378 2379 /** 2380 * The empty set (immutable). This set is serializable. 2381 */ 2382 public static final Set EMPTY_SET = new EmptySet(); 2383 2384 /** 2385 * @serial include 2386 */ 2387 private static class EmptySet extends AbstractSet implements Serializable { 2388 // use serialVersionUID from JDK 1.2.2 for interoperability 2389 private static final long serialVersionUID = 1582296315990362920L; 2390 2391 /** 2392 * @see java.util.Set#iterator() 2393 */ 2394 public Iterator iterator() { 2395 return new Iterator() { 2396 public boolean hasNext() { 2397 return false; 2398 } 2399 public Object next() { 2400 throw new NoSuchElementException(); 2401 } 2402 public void remove() { 2403 throw new UnsupportedOperationException(); 2404 } 2405 }; 2406 } 2407 2408 /** 2409 * @see java.util.Set#size() 2410 */ 2411 public int size() {return 0;} 2412 2413 /** 2414 * @see java.util.Set#contains(java.lang.Object) 2415 */ 2416 public boolean contains(Object obj) {return false;} 2417 } 2418 2419 /** 2420 * The empty list (immutable). This list is serializable. 2421 */ 2422 public static final List EMPTY_LIST = new EmptyList(); 2423 2424 /** 2425 * @serial include 2426 */ 2427 private static class EmptyList extends AbstractList 2428 implements RandomAccess, Serializable { 2429 // use serialVersionUID from JDK 1.2.2 for interoperability 2430 private static final long serialVersionUID = 8842843931221139166L; 2431 2432 /** 2433 * @see java.util.List#size() 2434 */ 2435 public int size() {return 0;} 2436 2437 /** 2438 * @see java.util.List#contains(java.lang.Object) 2439 */ 2440 public boolean contains(Object obj) {return false;} 2441 2442 /** 2443 * @see java.util.AbstractList#get(int) 2444 */ 2445 public Object get(int index) { 2446 throw new IndexOutOfBoundsException("Index: "+index); 2447 } 2448 } 2449 2450 /** 2451 * The empty map (immutable). This map is serializable. 2452 */ 2453 public static final Map EMPTY_MAP = new EmptyMap(); 2454 2455 private static class EmptyMap extends AbstractMap implements Serializable { 2456 /** 2457 * @see java.util.AbstractMap#size() 2458 */ 2459 public int size() {return 0;} 2460 2461 /** 2462 * @see java.util.AbstractMap#isEmpty() 2463 */ 2464 public boolean isEmpty() {return true;} 2465 2466 /** 2467 * @see java.util.AbstractMap#containsKey(java.lang.Object) 2468 */ 2469 public boolean containsKey(Object key) {return false;} 2470 2471 /** 2472 * @see java.util.AbstractMap#containsValue(java.lang.Object) 2473 */ 2474 public boolean containsValue(Object value) {return false;} 2475 2476 /** 2477 * @see java.util.AbstractMap#get(java.lang.Object) 2478 */ 2479 public Object get(Object key) {return null;} 2480 2481 /** 2482 * @see java.util.AbstractMap#keySet() 2483 */ 2484 public Set keySet() {return EMPTY_SET;} 2485 2486 /** 2487 * @see java.util.AbstractMap#values() 2488 */ 2489 public Collection values() {return EMPTY_SET;} 2490 2491 /** 2492 * @see java.util.AbstractMap#entrySet() 2493 */ 2494 public Set entrySet() {return EMPTY_SET;} 2495 2496 /** 2497 * @see java.util.AbstractMap#equals(java.lang.Object) 2498 */ 2499 public boolean equals(Object o) { 2500 return (o instanceof Map) && ((Map)o).size()==0; 2501 } 2502 2503 /** 2504 * @see java.util.AbstractMap#hashCode() 2505 */ 2506 public int hashCode() {return 0;} 2507 } 2508 2509 /** 2510 * Returns an immutable set containing only the specified object. 2511 * The returned set is serializable. 2512 * 2513 * @param o the sole object to be stored in the returned set. 2514 * @return an immutable set containing only the specified object. 2515 */ 2516 public static Set singleton(Object o) { 2517 return new SingletonSet(o); 2518 } 2519 2520 /** 2521 * @serial include 2522 */ 2523 private static class SingletonSet extends AbstractSet 2524 implements Serializable 2525 { 2526 // use serialVersionUID from JDK 1.2.2 for interoperability 2527 private static final long serialVersionUID = 3193687207550431679L; 2528 2529 private Object element; 2530 2531 SingletonSet(Object o) {element = o;} 2532 2533 /** 2534 * @see java.util.Set#iterator() 2535 */ 2536 public Iterator iterator() { 2537 return new Iterator() { 2538 private boolean hasNext = true; 2539 public boolean hasNext() { 2540 return hasNext; 2541 } 2542 public Object next() { 2543 if (hasNext) { 2544 hasNext = false; 2545 return element; 2546 } 2547 throw new NoSuchElementException(); 2548 } 2549 public void remove() { 2550 throw new UnsupportedOperationException(); 2551 } 2552 }; 2553 } 2554 2555 /** 2556 * @see java.util.Set#size() 2557 */ 2558 public int size() {return 1;} 2559 2560 /** 2561 * @see java.util.Set#contains(java.lang.Object) 2562 */ 2563 public boolean contains(Object o) {return eq(o, element);} 2564 } 2565 2566 /** 2567 * Returns an immutable list containing only the specified object. 2568 * The returned list is serializable. 2569 * 2570 * @param o the sole object to be stored in the returned list. 2571 * @return an immutable list containing only the specified object. 2572 */ 2573 public static List singletonList(Object o) { 2574 return new SingletonList(o); 2575 } 2576 2577 private static class SingletonList extends AbstractList 2578 implements RandomAccess, Serializable { 2579 static final long serialVersionUID = 3093736618740652951L; 2580 2581 private final Object element; 2582 2583 SingletonList(Object obj) {element = obj;} 2584 2585 /** 2586 * @see java.util.List#size() 2587 */ 2588 public int size() {return 1;} 2589 2590 /** 2591 * @see java.util.List#contains(java.lang.Object) 2592 */ 2593 public boolean contains(Object obj) {return eq(obj, element);} 2594 2595 /** 2596 * @see java.util.AbstractList#get(int) 2597 */ 2598 public Object get(int index) { 2599 if (index != 0) 2600 throw new IndexOutOfBoundsException("Index: "+index+", Size: 1"); 2601 return element; 2602 } 2603 } 2604 2605 /** 2606 * Returns an immutable map, mapping only the specified key to the 2607 * specified value. The returned map is serializable. 2608 * 2609 * @param key the sole key to be stored in the returned map. 2610 * @param value the value to which the returned map maps <tt>key</tt>. 2611 * @return an immutable map containing only the specified key-value 2612 * mapping. 2613 */ 2614 public static Map singletonMap(Object key, Object value) { 2615 return new SingletonMap(key, value); 2616 } 2617 2618 private static class SingletonMap extends AbstractMap 2619 implements Serializable { 2620 private final Object k, v; 2621 2622 SingletonMap(Object key, Object value) { 2623 k = key; 2624 v = value; 2625 } 2626 2627 /** 2628 * @see java.util.AbstractMap#size() 2629 */ 2630 public int size() {return 1;} 2631 2632 /** 2633 * @see java.util.AbstractMap#isEmpty() 2634 */ 2635 public boolean isEmpty() {return false;} 2636 2637 /** 2638 * @see java.util.AbstractMap#containsKey(java.lang.Object) 2639 */ 2640 public boolean containsKey(Object key) {return eq(key, k);} 2641 2642 /** 2643 * @see java.util.AbstractMap#containsValue(java.lang.Object) 2644 */ 2645 public boolean containsValue(Object value) {return eq(value, v);} 2646 2647 /** 2648 * @see java.util.AbstractMap#get(java.lang.Object) 2649 */ 2650 public Object get(Object key) {return (eq(key, k) ? v : null);} 2651 2652 private transient Set keySet = null; 2653 private transient Set entrySet = null; 2654 private transient Collection values = null; 2655 2656 /** 2657 * @see java.util.AbstractMap#keySet() 2658 */ 2659 public Set keySet() { 2660 if (keySet==null) 2661 keySet = singleton(k); 2662 return keySet; 2663 } 2664 2665 /** 2666 * @see java.util.AbstractMap#entrySet() 2667 */ 2668 public Set entrySet() { 2669 if (entrySet==null) 2670 entrySet = singleton(new ImmutableEntry(k, v)); 2671 return entrySet; 2672 } 2673 2674 /** 2675 * @see java.util.AbstractMap#values() 2676 */ 2677 public Collection values() { 2678 if (values==null) 2679 values = singleton(v); 2680 return values; 2681 } 2682 2683 private static class ImmutableEntry implements Map.Entry { 2684 final Object k; 2685 final Object v; 2686 2687 ImmutableEntry(Object key, Object value) { 2688 k = key; 2689 v = value; 2690 } 2691 2692 /** 2693 * @see java.util.Map.Entry#getKey() 2694 */ 2695 public Object getKey() {return k;} 2696 2697 /** 2698 * @see java.util.Map.Entry#getValue() 2699 */ 2700 public Object getValue() {return v;} 2701 2702 /** 2703 * @see java.util.Map.Entry#setValue(java.lang.Object) 2704 */ 2705 public Object setValue(Object value) { 2706 throw new UnsupportedOperationException(); 2707 } 2708 2709 /** 2710 * @see java.util.Map.Entry#equals(java.lang.Object) 2711 */ 2712 public boolean equals(Object o) { 2713 if (!(o instanceof Map.Entry)) 2714 return false; 2715 Map.Entry e = (Map.Entry)o; 2716 return eq(e.getKey(), k) && eq(e.getValue(), v); 2717 } 2718 2719 /** 2720 * @see java.util.Map.Entry#hashCode() 2721 */ 2722 public int hashCode() { 2723 return ((k==null ? 0 : k.hashCode()) ^ 2724 (v==null ? 0 : v.hashCode())); 2725 } 2726 2727 /** 2728 * @see java.lang.Object#toString() 2729 */ 2730 public String toString() { 2731 return k+"="+v; 2732 } 2733 } 2734 } 2735 2736 /** 2737 * Returns an immutable list consisting of <tt>n</tt> copies of the 2738 * specified object. The newly allocated data object is tiny (it contains 2739 * a single reference to the data object). This method is useful in 2740 * combination with the <tt>List.addAll</tt> method to grow lists. 2741 * The returned list is serializable. 2742 * 2743 * @param n the number of elements in the returned list. 2744 * @param o the element to appear repeatedly in the returned list. 2745 * @return an immutable list consisting of <tt>n</tt> copies of the 2746 * specified object. 2747 * @throws IllegalArgumentException if n < 0. 2748 * @see List#addAll(Collection) 2749 * @see List#addAll(int, Collection) 2750 */ 2751 public static List nCopies(int n, Object o) { 2752 return new CopiesList(n, o); 2753 } 2754 2755 /** 2756 * @serial include 2757 */ 2758 private static class CopiesList extends AbstractList 2759 implements RandomAccess, Serializable 2760 { 2761 static final long serialVersionUID = 2739099268398711800L; 2762 2763 int n; 2764 Object element; 2765 2766 CopiesList(int n, Object o) { 2767 if (n < 0) 2768 throw new IllegalArgumentException("List length = " + n); 2769 this.n = n; 2770 element = o; 2771 } 2772 2773 /** 2774 * @see java.util.List#size() 2775 */ 2776 public int size() { 2777 return n; 2778 } 2779 2780 /** 2781 * @see java.util.List#contains(java.lang.Object) 2782 */ 2783 public boolean contains(Object obj) { 2784 return n != 0 && eq(obj, element); 2785 } 2786 2787 /** 2788 * @see java.util.AbstractList#get(int) 2789 */ 2790 public Object get(int index) { 2791 if (index<0 || index>=n) 2792 throw new IndexOutOfBoundsException("Index: "+index+ 2793 ", Size: "+n); 2794 return element; 2795 } 2796 } 2797 2798 /** 2799 * Returns a comparator that imposes the reverse of the <i>natural 2800 * ordering</i> on a collection of objects that implement the 2801 * <tt>Comparable</tt> interface. (The natural ordering is the ordering 2802 * imposed by the objects' own <tt>compareTo</tt> method.) This enables a 2803 * simple idiom for sorting (or maintaining) collections (or arrays) of 2804 * objects that implement the <tt>Comparable</tt> interface in 2805 * reverse-natural-order. For example, suppose a is an array of 2806 * strings. Then: <pre> 2807 * Arrays.sort(a, Collections.reverseOrder()); 2808 * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p> 2809 * 2810 * The returned comparator is serializable. 2811 * 2812 * @return a comparator that imposes the reverse of the <i>natural 2813 * ordering</i> on a collection of objects that implement 2814 * the <tt>Comparable</tt> interface. 2815 * @see Comparable 2816 */ 2817 public static Comparator reverseOrder() { 2818 return REVERSE_ORDER; 2819 } 2820 2821 private static final Comparator REVERSE_ORDER = new ReverseComparator(); 2822 2823 /** 2824 * @serial include 2825 */ 2826 private static class ReverseComparator implements Comparator,Serializable { 2827 // use serialVersionUID from JDK 1.2.2 for interoperability 2828 private static final long serialVersionUID = 7207038068494060240L; 2829 2830 /** 2831 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object) 2832 */ 2833 public int compare(Object o1, Object o2) { 2834 Comparable c1 = (Comparable)o1; 2835 Comparable c2 = (Comparable)o2; 2836 return -c1.compareTo(c2); 2837 } 2838 } 2839 2840 /** 2841 * Returns an enumeration over the specified collection. This provides 2842 * interoperatbility with legacy APIs that require an enumeration 2843 * as input. 2844 * 2845 * @param c the collection for which an enumeration is to be returned. 2846 * @return an enumeration over the specified collection. 2847 * @see Enumeration 2848 */ 2849 public static Enumeration enumeration(final Collection c) { 2850 return new Enumeration() { 2851 Iterator i = c.iterator(); 2852 2853 public boolean hasMoreElements() { 2854 return i.hasNext(); 2855 } 2856 2857 public Object nextElement() { 2858 return i.next(); 2859 } 2860 }; 2861 } 2862 2863 /** 2864 * Returns an array list containing the elements returned by the 2865 * specified enumeration in the order they are returned by the 2866 * enumeration. This method provides interoperatbility between 2867 * legacy APIs that return enumerations and new APIs that require 2868 * collections. 2869 * 2870 * @param e enumeration providing elements for the returned 2871 * array list 2872 * @return an array list containing the elements returned 2873 * by the specified enumeration. 2874 * @see Enumeration 2875 * @see ArrayList 2876 */ 2877 public static ArrayList list(Enumeration e) { 2878 ArrayList l = new ArrayList(); 2879 while (e.hasMoreElements()) 2880 l.add(e.nextElement()); 2881 return l; 2882 } 2883 2884 /** 2885 * Returns true if the specified arguments are equal, or both null. 2886 * @param o1 2887 * @param o2 2888 * @return is equal 2889 */ 2890 private static boolean eq(Object o1, Object o2) { 2891 return (o1==null ? o2==null : o1.equals(o2)); 2892 } 2893 }