001/* Collections.java -- Utility class with methods to operate on collections 002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 003 Free Software Foundation, Inc. 004 005This file is part of GNU Classpath. 006 007GNU Classpath is free software; you can redistribute it and/or modify 008it under the terms of the GNU General Public License as published by 009the Free Software Foundation; either version 2, or (at your option) 010any later version. 011 012GNU Classpath is distributed in the hope that it will be useful, but 013WITHOUT ANY WARRANTY; without even the implied warranty of 014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 015General Public License for more details. 016 017You should have received a copy of the GNU General Public License 018along with GNU Classpath; see the file COPYING. If not, write to the 019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02002110-1301 USA. 021 022Linking this library statically or dynamically with other modules is 023making a combined work based on this library. Thus, the terms and 024conditions of the GNU General Public License cover the whole 025combination. 026 027As a special exception, the copyright holders of this library give you 028permission to link this library with independent modules to produce an 029executable, regardless of the license terms of these independent 030modules, and to copy and distribute the resulting executable under 031terms of your choice, provided that you also meet, for each linked 032independent module, the terms and conditions of the license of that 033module. An independent module is a module which is not derived from 034or based on this library. If you modify this library, you may extend 035this exception to your version of the library, but you are not 036obligated to do so. If you do not wish to do so, delete this 037exception statement from your version. */ 038 039 040package java.util; 041 042import gnu.java.lang.CPStringBuilder; 043 044import java.io.Serializable; 045 046/** 047 * Utility class consisting of static methods that operate on, or return 048 * Collections. Contains methods to sort, search, reverse, fill and shuffle 049 * Collections, methods to facilitate interoperability with legacy APIs that 050 * are unaware of collections, a method to return a list which consists of 051 * multiple copies of one element, and methods which "wrap" collections to give 052 * them extra properties, such as thread-safety and unmodifiability. 053 * <p> 054 * 055 * All methods which take a collection throw a {@link NullPointerException} if 056 * that collection is null. Algorithms which can change a collection may, but 057 * are not required, to throw the {@link UnsupportedOperationException} that 058 * the underlying collection would throw during an attempt at modification. 059 * For example, 060 * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code> 061 * does not throw a exception, even though addAll is an unsupported operation 062 * on a singleton; the reason for this is that addAll did not attempt to 063 * modify the set. 064 * 065 * @author Original author unknown 066 * @author Eric Blake (ebb9@email.byu.edu) 067 * @author Tom Tromey (tromey@redhat.com) 068 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 069 * @see Collection 070 * @see Set 071 * @see List 072 * @see Map 073 * @see Arrays 074 * @since 1.2 075 * @status updated to 1.5 076 */ 077public class Collections 078{ 079 /** 080 * Constant used to decide cutoff for when a non-RandomAccess list should 081 * be treated as sequential-access. Basically, quadratic behavior is 082 * acceptable for small lists when the overhead is so small in the first 083 * place. I arbitrarily set it to 16, so it may need some tuning. 084 */ 085 private static final int LARGE_LIST_SIZE = 16; 086 087 /** 088 * Determines if a list should be treated as a sequential-access one. 089 * Rather than the old method of JDK 1.3 of assuming only instanceof 090 * AbstractSequentialList should be sequential, this uses the new method 091 * of JDK 1.4 of assuming anything that does NOT implement RandomAccess 092 * and exceeds a large (unspecified) size should be sequential. 093 * 094 * @param l the list to check 095 * @return <code>true</code> if it should be treated as sequential-access 096 */ 097 private static boolean isSequential(List<?> l) 098 { 099 return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE; 100 } 101 102 /** 103 * This class is non-instantiable. 104 */ 105 private Collections() 106 { 107 } 108 109 /** 110 * An immutable, serializable, empty Set. 111 * @see Serializable 112 */ 113 public static final Set EMPTY_SET = new EmptySet(); 114 115 /** 116 * Returns an immutable, serializable parameterized empty set. 117 * Unlike the constant <code>EMPTY_SET</code>, the set returned by 118 * this method is type-safe. 119 * 120 * @return an empty parameterized set. 121 * @since 1.5 122 */ 123 @SuppressWarnings("unchecked") 124 public static final <T> Set<T> emptySet() 125 { 126 return (Set<T>) EMPTY_SET; 127 } 128 129 /** 130 * The implementation of {@link #EMPTY_SET}. This class name is required 131 * for compatibility with Sun's JDK serializability. 132 * 133 * @author Eric Blake (ebb9@email.byu.edu) 134 */ 135 private static final class EmptySet<T> extends AbstractSet<T> 136 implements Serializable 137 { 138 /** 139 * Compatible with JDK 1.4. 140 */ 141 private static final long serialVersionUID = 1582296315990362920L; 142 143 /** 144 * A private constructor adds overhead. 145 */ 146 EmptySet() 147 { 148 } 149 150 /** 151 * The size: always 0! 152 * @return 0. 153 */ 154 public int size() 155 { 156 return 0; 157 } 158 159 /** 160 * Returns an iterator that does not iterate. 161 * @return A non-iterating iterator. 162 */ 163 // This is really cheating! I think it's perfectly valid, though. 164 @SuppressWarnings("unchecked") 165 public Iterator<T> iterator() 166 { 167 return (Iterator<T>) EMPTY_LIST.iterator(); 168 } 169 170 // The remaining methods are optional, but provide a performance 171 // advantage by not allocating unnecessary iterators in AbstractSet. 172 /** 173 * The empty set never contains anything. 174 * @param o The object to search for. 175 * @return <code>false</code>. 176 */ 177 public boolean contains(Object o) 178 { 179 return false; 180 } 181 182 /** 183 * This is true only if the given collection is also empty. 184 * @param c The collection of objects which are to be compared 185 * against the members of this set. 186 * @return <code>true</code> if c is empty. 187 */ 188 public boolean containsAll(Collection<?> c) 189 { 190 return c.isEmpty(); 191 } 192 193 /** 194 * Equal only if the other set is empty. 195 * @param o The object to compare with this set. 196 * @return <code>true</code> if o is an empty instance of <code>Set</code>. 197 */ 198 public boolean equals(Object o) 199 { 200 return o instanceof Set<?> && ((Set<?>) o).isEmpty(); 201 } 202 203 /** 204 * The hashcode is always 0. 205 * @return 0. 206 */ 207 public int hashCode() 208 { 209 return 0; 210 } 211 212 /** 213 * Always succeeds with a <code>false</code> result. 214 * @param o The object to remove. 215 * @return <code>false</code>. 216 */ 217 public boolean remove(Object o) 218 { 219 return false; 220 } 221 222 /** 223 * Always succeeds with a <code>false</code> result. 224 * @param c The collection of objects which should 225 * all be removed from this set. 226 * @return <code>false</code>. 227 */ 228 public boolean removeAll(Collection<?> c) 229 { 230 return false; 231 } 232 233 /** 234 * Always succeeds with a <code>false</code> result. 235 * @param c The collection of objects which should 236 * all be retained within this set. 237 * @return <code>false</code>. 238 */ 239 public boolean retainAll(Collection<?> c) 240 { 241 return false; 242 } 243 244 /** 245 * The array is always empty. 246 * @return A new array with a size of 0. 247 */ 248 public Object[] toArray() 249 { 250 return new Object[0]; 251 } 252 253 /** 254 * We don't even need to use reflection! 255 * @param a An existing array, which can be empty. 256 * @return The original array with any existing 257 * initial element set to null. 258 */ 259 public <E> E[] toArray(E[] a) 260 { 261 if (a.length > 0) 262 a[0] = null; 263 return a; 264 } 265 266 /** 267 * The string never changes. 268 * 269 * @return the string "[]". 270 */ 271 public String toString() 272 { 273 return "[]"; 274 } 275 } // class EmptySet 276 277 /** 278 * An immutable, serializable, empty List, which implements RandomAccess. 279 * @see Serializable 280 * @see RandomAccess 281 */ 282 public static final List EMPTY_LIST = new EmptyList(); 283 284 /** 285 * Returns an immutable, serializable parameterized empty list. 286 * Unlike the constant <code>EMPTY_LIST</code>, the list returned by 287 * this method is type-safe. 288 * 289 * @return an empty parameterized list. 290 * @since 1.5 291 */ 292 @SuppressWarnings("unchecked") 293 public static final <T> List<T> emptyList() 294 { 295 return (List<T>) EMPTY_LIST; 296 } 297 298 /** 299 * The implementation of {@link #EMPTY_LIST}. This class name is required 300 * for compatibility with Sun's JDK serializability. 301 * 302 * @author Eric Blake (ebb9@email.byu.edu) 303 */ 304 private static final class EmptyList<T> extends AbstractList<T> 305 implements Serializable, RandomAccess 306 { 307 /** 308 * Compatible with JDK 1.4. 309 */ 310 private static final long serialVersionUID = 8842843931221139166L; 311 312 /** 313 * A private constructor adds overhead. 314 */ 315 EmptyList() 316 { 317 } 318 319 /** 320 * The size is always 0. 321 * @return 0. 322 */ 323 public int size() 324 { 325 return 0; 326 } 327 328 /** 329 * No matter the index, it is out of bounds. This 330 * method never returns, throwing an exception instead. 331 * 332 * @param index The index of the element to retrieve. 333 * @return the object at the specified index. 334 * @throws IndexOutOfBoundsException as any given index 335 * is outside the bounds of an empty array. 336 */ 337 public T get(int index) 338 { 339 throw new IndexOutOfBoundsException(); 340 } 341 342 // The remaining methods are optional, but provide a performance 343 // advantage by not allocating unnecessary iterators in AbstractList. 344 /** 345 * Never contains anything. 346 * @param o The object to search for. 347 * @return <code>false</code>. 348 */ 349 public boolean contains(Object o) 350 { 351 return false; 352 } 353 354 /** 355 * This is true only if the given collection is also empty. 356 * @param c The collection of objects, which should be compared 357 * against the members of this list. 358 * @return <code>true</code> if c is also empty. 359 */ 360 public boolean containsAll(Collection<?> c) 361 { 362 return c.isEmpty(); 363 } 364 365 /** 366 * Equal only if the other list is empty. 367 * @param o The object to compare against this list. 368 * @return <code>true</code> if o is also an empty instance of 369 * <code>List</code>. 370 */ 371 public boolean equals(Object o) 372 { 373 return o instanceof List<?> && ((List<?>) o).isEmpty(); 374 } 375 376 /** 377 * The hashcode is always 1. 378 * @return 1. 379 */ 380 public int hashCode() 381 { 382 return 1; 383 } 384 385 /** 386 * Returns -1. 387 * @param o The object to search for. 388 * @return -1. 389 */ 390 public int indexOf(Object o) 391 { 392 return -1; 393 } 394 395 /** 396 * Returns -1. 397 * @param o The object to search for. 398 * @return -1. 399 */ 400 public int lastIndexOf(Object o) 401 { 402 return -1; 403 } 404 405 /** 406 * Always succeeds with <code>false</code> result. 407 * @param o The object to remove. 408 * @return -1. 409 */ 410 public boolean remove(Object o) 411 { 412 return false; 413 } 414 415 /** 416 * Always succeeds with <code>false</code> result. 417 * @param c The collection of objects which should 418 * all be removed from this list. 419 * @return <code>false</code>. 420 */ 421 public boolean removeAll(Collection<?> c) 422 { 423 return false; 424 } 425 426 /** 427 * Always succeeds with <code>false</code> result. 428 * @param c The collection of objects which should 429 * all be retained within this list. 430 * @return <code>false</code>. 431 */ 432 public boolean retainAll(Collection<?> c) 433 { 434 return false; 435 } 436 437 /** 438 * The array is always empty. 439 * @return A new array with a size of 0. 440 */ 441 public Object[] toArray() 442 { 443 return new Object[0]; 444 } 445 446 /** 447 * We don't even need to use reflection! 448 * @param a An existing array, which can be empty. 449 * @return The original array with any existing 450 * initial element set to null. 451 */ 452 public <E> E[] toArray(E[] a) 453 { 454 if (a.length > 0) 455 a[0] = null; 456 return a; 457 } 458 459 /** 460 * The string never changes. 461 * 462 * @return the string "[]". 463 */ 464 public String toString() 465 { 466 return "[]"; 467 } 468 } // class EmptyList 469 470 /** 471 * An immutable, serializable, empty Map. 472 * @see Serializable 473 */ 474 public static final Map EMPTY_MAP = new EmptyMap(); 475 476 /** 477 * Returns an immutable, serializable parameterized empty map. 478 * Unlike the constant <code>EMPTY_MAP</code>, the map returned by 479 * this method is type-safe. 480 * 481 * @return an empty parameterized map. 482 * @since 1.5 483 */ 484 @SuppressWarnings("unchecked") 485 public static final <K,V> Map<K,V> emptyMap() 486 { 487 return (Map<K,V>) EMPTY_MAP; 488 } 489 490 /** 491 * The implementation of {@link #EMPTY_MAP}. This class name is required 492 * for compatibility with Sun's JDK serializability. 493 * 494 * @author Eric Blake (ebb9@email.byu.edu) 495 */ 496 private static final class EmptyMap<K, V> extends AbstractMap<K, V> 497 implements Serializable 498 { 499 /** 500 * Compatible with JDK 1.4. 501 */ 502 private static final long serialVersionUID = 6428348081105594320L; 503 504 /** 505 * A private constructor adds overhead. 506 */ 507 EmptyMap() 508 { 509 } 510 511 /** 512 * There are no entries. 513 * @return The empty set. 514 */ 515 @SuppressWarnings("unchecked") 516 public Set<Map.Entry<K, V>> entrySet() 517 { 518 return (Set<Map.Entry<K, V>>) EMPTY_SET; 519 } 520 521 // The remaining methods are optional, but provide a performance 522 // advantage by not allocating unnecessary iterators in AbstractMap. 523 /** 524 * No entries! 525 * @param key The key to search for. 526 * @return <code>false</code>. 527 */ 528 public boolean containsKey(Object key) 529 { 530 return false; 531 } 532 533 /** 534 * No entries! 535 * @param value The value to search for. 536 * @return <code>false</code>. 537 */ 538 public boolean containsValue(Object value) 539 { 540 return false; 541 } 542 543 /** 544 * Equal to all empty maps. 545 * @param o The object o to compare against this map. 546 * @return <code>true</code> if o is also an empty instance of 547 * <code>Map</code>. 548 */ 549 public boolean equals(Object o) 550 { 551 return o instanceof Map<?,?> && ((Map<?,?>) o).isEmpty(); 552 } 553 554 /** 555 * No mappings, so this returns null. 556 * @param o The key of the object to retrieve. 557 * @return null. 558 */ 559 public V get(Object o) 560 { 561 return null; 562 } 563 564 /** 565 * The hashcode is always 0. 566 * @return 0. 567 */ 568 public int hashCode() 569 { 570 return 0; 571 } 572 573 /** 574 * No entries. 575 * @return The empty set. 576 */ 577 @SuppressWarnings("unchecked") 578 public Set<K> keySet() 579 { 580 return (Set<K>) EMPTY_SET; 581 } 582 583 /** 584 * Remove always succeeds, with null result. 585 * @param o The key of the mapping to remove. 586 * @return null, as there is never a mapping for o. 587 */ 588 public V remove(Object o) 589 { 590 return null; 591 } 592 593 /** 594 * Size is always 0. 595 * @return 0. 596 */ 597 public int size() 598 { 599 return 0; 600 } 601 602 /** 603 * No entries. Technically, EMPTY_SET, while more specific than a general 604 * Collection, will work. Besides, that's what the JDK uses! 605 * @return The empty set. 606 */ 607 @SuppressWarnings("unchecked") 608 public Collection<V> values() 609 { 610 return (Collection<V>) EMPTY_SET; 611 } 612 613 /** 614 * The string never changes. 615 * 616 * @return the string "[]". 617 */ 618 public String toString() 619 { 620 return "[]"; 621 } 622 } // class EmptyMap 623 624 625 /** 626 * Compare two objects with or without a Comparator. If c is null, uses the 627 * natural ordering. Slightly slower than doing it inline if the JVM isn't 628 * clever, but worth it for removing a duplicate of the search code. 629 * Note: This code is also used in Arrays (for sort as well as search). 630 */ 631 static final <T> int compare(T o1, T o2, Comparator<? super T> c) 632 { 633 return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2); 634 } 635 636 /** 637 * Perform a binary search of a List for a key, using the natural ordering of 638 * the elements. The list must be sorted (as by the sort() method) - if it is 639 * not, the behavior of this method is undefined, and may be an infinite 640 * loop. Further, the key must be comparable with every item in the list. If 641 * the list contains the key more than once, any one of them may be found. 642 * <p> 643 * 644 * This algorithm behaves in log(n) time for {@link RandomAccess} lists, 645 * and uses a linear search with O(n) link traversals and log(n) comparisons 646 * with {@link AbstractSequentialList} lists. Note: although the 647 * specification allows for an infinite loop if the list is unsorted, it will 648 * not happen in this (Classpath) implementation. 649 * 650 * @param l the list to search (must be sorted) 651 * @param key the value to search for 652 * @return the index at which the key was found, or -n-1 if it was not 653 * found, where n is the index of the first value higher than key or 654 * a.length if there is no such value 655 * @throws ClassCastException if key could not be compared with one of the 656 * elements of l 657 * @throws NullPointerException if a null element has compareTo called 658 * @see #sort(List) 659 */ 660 public static <T> int binarySearch(List<? extends Comparable<? super T>> l, 661 T key) 662 { 663 return binarySearch(l, key, null); 664 } 665 666 /** 667 * Perform a binary search of a List for a key, using a supplied Comparator. 668 * The list must be sorted (as by the sort() method with the same Comparator) 669 * - if it is not, the behavior of this method is undefined, and may be an 670 * infinite loop. Further, the key must be comparable with every item in the 671 * list. If the list contains the key more than once, any one of them may be 672 * found. If the comparator is null, the elements' natural ordering is used. 673 * <p> 674 * 675 * This algorithm behaves in log(n) time for {@link RandomAccess} lists, 676 * and uses a linear search with O(n) link traversals and log(n) comparisons 677 * with {@link AbstractSequentialList} lists. Note: although the 678 * specification allows for an infinite loop if the list is unsorted, it will 679 * not happen in this (Classpath) implementation. 680 * 681 * @param l the list to search (must be sorted) 682 * @param key the value to search for 683 * @param c the comparator by which the list is sorted 684 * @return the index at which the key was found, or -n-1 if it was not 685 * found, where n is the index of the first value higher than key or 686 * a.length if there is no such value 687 * @throws ClassCastException if key could not be compared with one of the 688 * elements of l 689 * @throws NullPointerException if a null element is compared with natural 690 * ordering (only possible when c is null) 691 * @see #sort(List, Comparator) 692 */ 693 public static <T> int binarySearch(List<? extends T> l, T key, 694 Comparator<? super T> c) 695 { 696 int pos = 0; 697 int low = 0; 698 int hi = l.size() - 1; 699 700 // We use a linear search with log(n) comparisons using an iterator 701 // if the list is sequential-access. 702 if (isSequential(l)) 703 { 704 ListIterator<T> itr = ((List<T>) l).listIterator(); 705 int i = 0; 706 T o = itr.next(); // Assumes list is not empty (see isSequential) 707 boolean forward = true; 708 while (low <= hi) 709 { 710 pos = (low + hi) >>> 1; 711 if (i < pos) 712 { 713 if (!forward) 714 itr.next(); // Changing direction first. 715 for ( ; i != pos; i++, o = itr.next()) 716 ; 717 forward = true; 718 } 719 else 720 { 721 if (forward) 722 itr.previous(); // Changing direction first. 723 for ( ; i != pos; i--, o = itr.previous()) 724 ; 725 forward = false; 726 } 727 final int d = compare(o, key, c); 728 if (d == 0) 729 return pos; 730 else if (d > 0) 731 hi = pos - 1; 732 else 733 // This gets the insertion point right on the last loop 734 low = ++pos; 735 } 736 } 737 else 738 { 739 while (low <= hi) 740 { 741 pos = (low + hi) >>> 1; 742 final int d = compare(((List<T>) l).get(pos), key, c); 743 if (d == 0) 744 return pos; 745 else if (d > 0) 746 hi = pos - 1; 747 else 748 // This gets the insertion point right on the last loop 749 low = ++pos; 750 } 751 } 752 753 // If we failed to find it, we do the same whichever search we did. 754 return -pos - 1; 755 } 756 757 /** 758 * Copy one list to another. If the destination list is longer than the 759 * source list, the remaining elements are unaffected. This method runs in 760 * linear time. 761 * 762 * @param dest the destination list 763 * @param source the source list 764 * @throws IndexOutOfBoundsException if the destination list is shorter 765 * than the source list (the destination will be unmodified) 766 * @throws UnsupportedOperationException if dest.listIterator() does not 767 * support the set operation 768 */ 769 public static <T> void copy(List<? super T> dest, List<? extends T> source) 770 { 771 int pos = source.size(); 772 if (dest.size() < pos) 773 throw new IndexOutOfBoundsException("Source does not fit in dest"); 774 775 Iterator<? extends T> i1 = source.iterator(); 776 ListIterator<? super T> i2 = dest.listIterator(); 777 778 while (--pos >= 0) 779 { 780 i2.next(); 781 i2.set(i1.next()); 782 } 783 } 784 785 /** 786 * Returns an Enumeration over a collection. This allows interoperability 787 * with legacy APIs that require an Enumeration as input. 788 * 789 * @param c the Collection to iterate over 790 * @return an Enumeration backed by an Iterator over c 791 */ 792 public static <T> Enumeration<T> enumeration(Collection<T> c) 793 { 794 final Iterator<T> i = c.iterator(); 795 return new Enumeration<T>() 796 { 797 /** 798 * Returns <code>true</code> if there are more elements to 799 * be enumerated. 800 * 801 * @return The result of <code>hasNext()</code> 802 * called on the underlying iterator. 803 */ 804 public final boolean hasMoreElements() 805 { 806 return i.hasNext(); 807 } 808 809 /** 810 * Returns the next element to be enumerated. 811 * 812 * @return The result of <code>next()</code> 813 * called on the underlying iterator. 814 */ 815 public final T nextElement() 816 { 817 return i.next(); 818 } 819 }; 820 } 821 822 /** 823 * Replace every element of a list with a given value. This method runs in 824 * linear time. 825 * 826 * @param l the list to fill. 827 * @param val the object to vill the list with. 828 * @throws UnsupportedOperationException if l.listIterator() does not 829 * support the set operation. 830 */ 831 public static <T> void fill(List<? super T> l, T val) 832 { 833 ListIterator<? super T> itr = l.listIterator(); 834 for (int i = l.size() - 1; i >= 0; --i) 835 { 836 itr.next(); 837 itr.set(val); 838 } 839 } 840 841 /** 842 * Returns the starting index where the specified sublist first occurs 843 * in a larger list, or -1 if there is no matching position. If 844 * <code>target.size() > source.size()</code>, this returns -1, 845 * otherwise this implementation uses brute force, checking for 846 * <code>source.sublist(i, i + target.size()).equals(target)</code> 847 * for all possible i. 848 * 849 * @param source the list to search 850 * @param target the sublist to search for 851 * @return the index where found, or -1 852 * @since 1.4 853 */ 854 public static int indexOfSubList(List<?> source, List<?> target) 855 { 856 int ssize = source.size(); 857 for (int i = 0, j = target.size(); j <= ssize; i++, j++) 858 if (source.subList(i, j).equals(target)) 859 return i; 860 return -1; 861 } 862 863 /** 864 * Returns the starting index where the specified sublist last occurs 865 * in a larger list, or -1 if there is no matching position. If 866 * <code>target.size() > source.size()</code>, this returns -1, 867 * otherwise this implementation uses brute force, checking for 868 * <code>source.sublist(i, i + target.size()).equals(target)</code> 869 * for all possible i. 870 * 871 * @param source the list to search 872 * @param target the sublist to search for 873 * @return the index where found, or -1 874 * @since 1.4 875 */ 876 public static int lastIndexOfSubList(List<?> source, List<?> target) 877 { 878 int ssize = source.size(); 879 for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--) 880 if (source.subList(i, j).equals(target)) 881 return i; 882 return -1; 883 } 884 885 /** 886 * Returns an ArrayList holding the elements visited by a given 887 * Enumeration. This method exists for interoperability between legacy 888 * APIs and the new Collection API. 889 * 890 * @param e the enumeration to put in a list 891 * @return a list containing the enumeration elements 892 * @see ArrayList 893 * @since 1.4 894 */ 895 public static <T> ArrayList<T> list(Enumeration<T> e) 896 { 897 ArrayList<T> l = new ArrayList<T>(); 898 while (e.hasMoreElements()) 899 l.add(e.nextElement()); 900 return l; 901 } 902 903 /** 904 * Find the maximum element in a Collection, according to the natural 905 * ordering of the elements. This implementation iterates over the 906 * Collection, so it works in linear time. 907 * 908 * @param c the Collection to find the maximum element of 909 * @return the maximum element of c 910 * @exception NoSuchElementException if c is empty 911 * @exception ClassCastException if elements in c are not mutually comparable 912 * @exception NullPointerException if null.compareTo is called 913 */ 914 public static <T extends Object & Comparable<? super T>> 915 T max(Collection<? extends T> c) 916 { 917 return max(c, null); 918 } 919 920 /** 921 * Find the maximum element in a Collection, according to a specified 922 * Comparator. This implementation iterates over the Collection, so it 923 * works in linear time. 924 * 925 * @param c the Collection to find the maximum element of 926 * @param order the Comparator to order the elements by, or null for natural 927 * ordering 928 * @return the maximum element of c 929 * @throws NoSuchElementException if c is empty 930 * @throws ClassCastException if elements in c are not mutually comparable 931 * @throws NullPointerException if null is compared by natural ordering 932 * (only possible when order is null) 933 */ 934 public static <T> T max(Collection<? extends T> c, 935 Comparator<? super T> order) 936 { 937 Iterator<? extends T> itr = c.iterator(); 938 T max = itr.next(); // throws NoSuchElementException 939 int csize = c.size(); 940 for (int i = 1; i < csize; i++) 941 { 942 T o = itr.next(); 943 if (compare(max, o, order) < 0) 944 max = o; 945 } 946 return max; 947 } 948 949 /** 950 * Find the minimum element in a Collection, according to the natural 951 * ordering of the elements. This implementation iterates over the 952 * Collection, so it works in linear time. 953 * 954 * @param c the Collection to find the minimum element of 955 * @return the minimum element of c 956 * @throws NoSuchElementException if c is empty 957 * @throws ClassCastException if elements in c are not mutually comparable 958 * @throws NullPointerException if null.compareTo is called 959 */ 960 public static <T extends Object & Comparable<? super T>> 961 T min(Collection<? extends T> c) 962 { 963 return min(c, null); 964 } 965 966 /** 967 * Find the minimum element in a Collection, according to a specified 968 * Comparator. This implementation iterates over the Collection, so it 969 * works in linear time. 970 * 971 * @param c the Collection to find the minimum element of 972 * @param order the Comparator to order the elements by, or null for natural 973 * ordering 974 * @return the minimum element of c 975 * @throws NoSuchElementException if c is empty 976 * @throws ClassCastException if elements in c are not mutually comparable 977 * @throws NullPointerException if null is compared by natural ordering 978 * (only possible when order is null) 979 */ 980 public static <T> T min(Collection<? extends T> c, 981 Comparator<? super T> order) 982 { 983 Iterator<? extends T> itr = c.iterator(); 984 T min = itr.next(); // throws NoSuchElementExcception 985 int csize = c.size(); 986 for (int i = 1; i < csize; i++) 987 { 988 T o = itr.next(); 989 if (compare(min, o, order) > 0) 990 min = o; 991 } 992 return min; 993 } 994 995 /** 996 * Creates an immutable list consisting of the same object repeated n times. 997 * The returned object is tiny, consisting of only a single reference to the 998 * object and a count of the number of elements. It is Serializable, and 999 * implements RandomAccess. You can use it in tandem with List.addAll for 1000 * fast list construction. 1001 * 1002 * @param n the number of times to repeat the object 1003 * @param o the object to repeat 1004 * @return a List consisting of n copies of o 1005 * @throws IllegalArgumentException if n < 0 1006 * @see List#addAll(Collection) 1007 * @see Serializable 1008 * @see RandomAccess 1009 */ 1010 public static <T> List<T> nCopies(final int n, final T o) 1011 { 1012 return new CopiesList<T>(n, o); 1013 } 1014 1015 /** 1016 * The implementation of {@link #nCopies(int, Object)}. This class name 1017 * is required for compatibility with Sun's JDK serializability. 1018 * 1019 * @author Eric Blake (ebb9@email.byu.edu) 1020 */ 1021 private static final class CopiesList<T> extends AbstractList<T> 1022 implements Serializable, RandomAccess 1023 { 1024 /** 1025 * Compatible with JDK 1.4. 1026 */ 1027 private static final long serialVersionUID = 2739099268398711800L; 1028 1029 /** 1030 * The count of elements in this list. 1031 * @serial the list size 1032 */ 1033 private final int n; 1034 1035 /** 1036 * The repeated list element. 1037 * @serial the list contents 1038 */ 1039 private final T element; 1040 1041 /** 1042 * Constructs the list. 1043 * 1044 * @param n the count 1045 * @param o the object 1046 * @throws IllegalArgumentException if n < 0 1047 */ 1048 CopiesList(int n, T o) 1049 { 1050 if (n < 0) 1051 throw new IllegalArgumentException(); 1052 this.n = n; 1053 element = o; 1054 } 1055 1056 /** 1057 * The size is fixed. 1058 * @return The size of the list. 1059 */ 1060 public int size() 1061 { 1062 return n; 1063 } 1064 1065 /** 1066 * The same element is returned. 1067 * @param index The index of the element to be returned (irrelevant 1068 * as the list contains only copies of <code>element</code>). 1069 * @return The element used by this list. 1070 */ 1071 public T get(int index) 1072 { 1073 if (index < 0 || index >= n) 1074 throw new IndexOutOfBoundsException(); 1075 return element; 1076 } 1077 1078 // The remaining methods are optional, but provide a performance 1079 // advantage by not allocating unnecessary iterators in AbstractList. 1080 /** 1081 * This list only contains one element. 1082 * @param o The object to search for. 1083 * @return <code>true</code> if o is the element used by this list. 1084 */ 1085 public boolean contains(Object o) 1086 { 1087 return n > 0 && equals(o, element); 1088 } 1089 1090 /** 1091 * The index is either 0 or -1. 1092 * @param o The object to find the index of. 1093 * @return 0 if <code>o == element</code>, -1 if not. 1094 */ 1095 public int indexOf(Object o) 1096 { 1097 return (n > 0 && equals(o, element)) ? 0 : -1; 1098 } 1099 1100 /** 1101 * The index is either n-1 or -1. 1102 * @param o The object to find the last index of. 1103 * @return The last index in the list if <code>o == element</code>, 1104 * -1 if not. 1105 */ 1106 public int lastIndexOf(Object o) 1107 { 1108 return equals(o, element) ? n - 1 : -1; 1109 } 1110 1111 /** 1112 * A subList is just another CopiesList. 1113 * @param from The starting bound of the sublist. 1114 * @param to The ending bound of the sublist. 1115 * @return A list of copies containing <code>from - to</code> 1116 * elements, all of which are equal to the element 1117 * used by this list. 1118 */ 1119 public List<T> subList(int from, int to) 1120 { 1121 if (from < 0 || to > n) 1122 throw new IndexOutOfBoundsException(); 1123 return new CopiesList<T>(to - from, element); 1124 } 1125 1126 /** 1127 * The array is easy. 1128 * @return An array of size n filled with copies of 1129 * the element used by this list. 1130 */ 1131 public Object[] toArray() 1132 { 1133 Object[] a = new Object[n]; 1134 Arrays.fill(a, element); 1135 return a; 1136 } 1137 1138 /** 1139 * The string is easy to generate. 1140 * @return A string representation of the list. 1141 */ 1142 public String toString() 1143 { 1144 CPStringBuilder r = new CPStringBuilder("{"); 1145 for (int i = n - 1; --i > 0; ) 1146 r.append(element).append(", "); 1147 r.append(element).append("}"); 1148 return r.toString(); 1149 } 1150 } // class CopiesList 1151 1152 /** 1153 * Replace all instances of one object with another in the specified list. 1154 * The list does not change size. An element e is replaced if 1155 * <code>oldval == null ? e == null : oldval.equals(e)</code>. 1156 * 1157 * @param list the list to iterate over 1158 * @param oldval the element to replace 1159 * @param newval the new value for the element 1160 * @return <code>true</code> if a replacement occurred. 1161 * @throws UnsupportedOperationException if the list iterator does not allow 1162 * for the set operation 1163 * @throws ClassCastException if newval is of a type which cannot be added 1164 * to the list 1165 * @throws IllegalArgumentException if some other aspect of newval stops 1166 * it being added to the list 1167 * @since 1.4 1168 */ 1169 public static <T> boolean replaceAll(List<T> list, T oldval, T newval) 1170 { 1171 ListIterator<T> itr = list.listIterator(); 1172 boolean replace_occured = false; 1173 for (int i = list.size(); --i >= 0; ) 1174 if (AbstractCollection.equals(oldval, itr.next())) 1175 { 1176 itr.set(newval); 1177 replace_occured = true; 1178 } 1179 return replace_occured; 1180 } 1181 1182 /** 1183 * Reverse a given list. This method works in linear time. 1184 * 1185 * @param l the list to reverse 1186 * @throws UnsupportedOperationException if l.listIterator() does not 1187 * support the set operation 1188 */ 1189 public static void reverse(List<?> l) 1190 { 1191 ListIterator i1 = l.listIterator(); 1192 int pos1 = 1; 1193 int pos2 = l.size(); 1194 ListIterator i2 = l.listIterator(pos2); 1195 while (pos1 < pos2) 1196 { 1197 Object o1 = i1.next(); 1198 Object o2 = i2.previous(); 1199 i1.set(o2); 1200 i2.set(o1); 1201 ++pos1; 1202 --pos2; 1203 } 1204 } 1205 1206 /** 1207 * Get a comparator that implements the reverse of the ordering 1208 * specified by the given Comparator. If the Comparator is null, 1209 * this is equivalent to {@link #reverseOrder()}. The return value 1210 * of this method is Serializable, if the specified Comparator is 1211 * either Serializable or null. 1212 * 1213 * @param c the comparator to invert 1214 * @return a comparator that imposes reverse ordering 1215 * @see Comparable 1216 * @see Serializable 1217 * 1218 * @since 1.5 1219 */ 1220 public static <T> Comparator<T> reverseOrder(final Comparator<T> c) 1221 { 1222 if (c == null) 1223 return (Comparator<T>) rcInstance; 1224 return new ReverseComparator<T> () 1225 { 1226 public int compare(T a, T b) 1227 { 1228 return - c.compare(a, b); 1229 } 1230 }; 1231 } 1232 1233 /** 1234 * Get a comparator that implements the reverse of natural ordering. In 1235 * other words, this sorts Comparable objects opposite of how their 1236 * compareTo method would sort. This makes it easy to sort into reverse 1237 * order, by simply passing Collections.reverseOrder() to the sort method. 1238 * The return value of this method is Serializable. 1239 * 1240 * @return a comparator that imposes reverse natural ordering 1241 * @see Comparable 1242 * @see Serializable 1243 */ 1244 public static <T> Comparator<T> reverseOrder() 1245 { 1246 return (Comparator<T>) rcInstance; 1247 } 1248 1249 /** 1250 * The object for {@link #reverseOrder()}. 1251 */ 1252 private static final ReverseComparator rcInstance = new ReverseComparator(); 1253 1254 /** 1255 * The implementation of {@link #reverseOrder()}. This class name 1256 * is required for compatibility with Sun's JDK serializability. 1257 * 1258 * @author Eric Blake (ebb9@email.byu.edu) 1259 */ 1260 private static class ReverseComparator<T> 1261 implements Comparator<T>, Serializable 1262 { 1263 /** 1264 * Compatible with JDK 1.4. 1265 */ 1266 private static final long serialVersionUID = 7207038068494060240L; 1267 1268 /** 1269 * A private constructor adds overhead. 1270 */ 1271 ReverseComparator() 1272 { 1273 } 1274 1275 /** 1276 * Compare two objects in reverse natural order. 1277 * 1278 * @param a the first object 1279 * @param b the second object 1280 * @return <, ==, or > 0 according to b.compareTo(a) 1281 */ 1282 public int compare(T a, T b) 1283 { 1284 return ((Comparable) b).compareTo(a); 1285 } 1286 } 1287 1288 /** 1289 * Rotate the elements in a list by a specified distance. After calling this 1290 * method, the element now at index <code>i</code> was formerly at index 1291 * <code>(i - distance) mod list.size()</code>. The list size is unchanged. 1292 * <p> 1293 * 1294 * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After 1295 * either <code>Collections.rotate(l, 4)</code> or 1296 * <code>Collections.rotate(l, -1)</code>, the new contents are 1297 * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate 1298 * just a portion of the list. For example, to move element <code>a</code> 1299 * forward two positions in the original example, use 1300 * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will 1301 * result in <code>[t, n, k, a, s]</code>. 1302 * <p> 1303 * 1304 * If the list is small or implements {@link RandomAccess}, the 1305 * implementation exchanges the first element to its destination, then the 1306 * displaced element, and so on until a circuit has been completed. The 1307 * process is repeated if needed on the second element, and so forth, until 1308 * all elements have been swapped. For large non-random lists, the 1309 * implementation breaks the list into two sublists at index 1310 * <code>-distance mod size</code>, calls {@link #reverse(List)} on the 1311 * pieces, then reverses the overall list. 1312 * 1313 * @param list the list to rotate 1314 * @param distance the distance to rotate by; unrestricted in value 1315 * @throws UnsupportedOperationException if the list does not support set 1316 * @since 1.4 1317 */ 1318 public static void rotate(List<?> list, int distance) 1319 { 1320 int size = list.size(); 1321 if (size == 0) 1322 return; 1323 distance %= size; 1324 if (distance == 0) 1325 return; 1326 if (distance < 0) 1327 distance += size; 1328 1329 if (isSequential(list)) 1330 { 1331 reverse(list); 1332 reverse(list.subList(0, distance)); 1333 reverse(list.subList(distance, size)); 1334 } 1335 else 1336 { 1337 // Determine the least common multiple of distance and size, as there 1338 // are (distance / LCM) loops to cycle through. 1339 int a = size; 1340 int lcm = distance; 1341 int b = a % lcm; 1342 while (b != 0) 1343 { 1344 a = lcm; 1345 lcm = b; 1346 b = a % lcm; 1347 } 1348 1349 // Now, make the swaps. We must take the remainder every time through 1350 // the inner loop so that we don't overflow i to negative values. 1351 List<Object> objList = (List<Object>) list; 1352 while (--lcm >= 0) 1353 { 1354 Object o = objList.get(lcm); 1355 for (int i = lcm + distance; i != lcm; i = (i + distance) % size) 1356 o = objList.set(i, o); 1357 objList.set(lcm, o); 1358 } 1359 } 1360 } 1361 1362 /** 1363 * Shuffle a list according to a default source of randomness. The algorithm 1364 * used iterates backwards over the list, swapping each element with an 1365 * element randomly selected from the elements in positions less than or 1366 * equal to it (using r.nextInt(int)). 1367 * <p> 1368 * 1369 * This algorithm would result in a perfectly fair shuffle (that is, each 1370 * element would have an equal chance of ending up in any position) if r were 1371 * a perfect source of randomness. In practice the results are merely very 1372 * close to perfect. 1373 * <p> 1374 * 1375 * This method operates in linear time. To do this on large lists which do 1376 * not implement {@link RandomAccess}, a temporary array is used to acheive 1377 * this speed, since it would be quadratic access otherwise. 1378 * 1379 * @param l the list to shuffle 1380 * @throws UnsupportedOperationException if l.listIterator() does not 1381 * support the set operation 1382 */ 1383 public static void shuffle(List<?> l) 1384 { 1385 if (defaultRandom == null) 1386 { 1387 synchronized (Collections.class) 1388 { 1389 if (defaultRandom == null) 1390 defaultRandom = new Random(); 1391 } 1392 } 1393 shuffle(l, defaultRandom); 1394 } 1395 1396 /** 1397 * Cache a single Random object for use by shuffle(List). This improves 1398 * performance as well as ensuring that sequential calls to shuffle() will 1399 * not result in the same shuffle order occurring: the resolution of 1400 * System.currentTimeMillis() is not sufficient to guarantee a unique seed. 1401 */ 1402 private static Random defaultRandom = null; 1403 1404 /** 1405 * Shuffle a list according to a given source of randomness. The algorithm 1406 * used iterates backwards over the list, swapping each element with an 1407 * element randomly selected from the elements in positions less than or 1408 * equal to it (using r.nextInt(int)). 1409 * <p> 1410 * 1411 * This algorithm would result in a perfectly fair shuffle (that is, each 1412 * element would have an equal chance of ending up in any position) if r were 1413 * a perfect source of randomness. In practise (eg if r = new Random()) the 1414 * results are merely very close to perfect. 1415 * <p> 1416 * 1417 * This method operates in linear time. To do this on large lists which do 1418 * not implement {@link RandomAccess}, a temporary array is used to acheive 1419 * this speed, since it would be quadratic access otherwise. 1420 * 1421 * @param l the list to shuffle 1422 * @param r the source of randomness to use for the shuffle 1423 * @throws UnsupportedOperationException if l.listIterator() does not 1424 * support the set operation 1425 */ 1426 public static void shuffle(List<?> l, Random r) 1427 { 1428 int lsize = l.size(); 1429 List<Object> list = (List<Object>) l; 1430 ListIterator<Object> i = list.listIterator(lsize); 1431 boolean sequential = isSequential(l); 1432 Object[] a = null; // stores a copy of the list for the sequential case 1433 1434 if (sequential) 1435 a = list.toArray(); 1436 1437 for (int pos = lsize - 1; pos > 0; --pos) 1438 { 1439 // Obtain a random position to swap with. pos + 1 is used so that the 1440 // range of the random number includes the current position. 1441 int swap = r.nextInt(pos + 1); 1442 1443 // Swap the desired element. 1444 Object o; 1445 if (sequential) 1446 { 1447 o = a[swap]; 1448 a[swap] = i.previous(); 1449 } 1450 else 1451 o = list.set(swap, i.previous()); 1452 1453 i.set(o); 1454 } 1455 } 1456 1457 /** 1458 * Returns the frequency of the specified object within the supplied 1459 * collection. The frequency represents the number of occurrences of 1460 * elements within the collection which return <code>true</code> when 1461 * compared with the object using the <code>equals</code> method. 1462 * 1463 * @param c the collection to scan for occurrences of the object. 1464 * @param o the object to locate occurrances of within the collection. 1465 * @throws NullPointerException if the collection is <code>null</code>. 1466 * @since 1.5 1467 */ 1468 public static int frequency (Collection<?> c, Object o) 1469 { 1470 int result = 0; 1471 final Iterator<?> it = c.iterator(); 1472 while (it.hasNext()) 1473 { 1474 Object v = it.next(); 1475 if (AbstractCollection.equals(o, v)) 1476 ++result; 1477 } 1478 return result; 1479 } 1480 1481 /** 1482 * Adds all the specified elements to the given collection, in a similar 1483 * way to the <code>addAll</code> method of the <code>Collection</code>. 1484 * However, this is a variable argument method which allows the new elements 1485 * to be specified individually or in array form, as opposed to the list 1486 * required by the collection's <code>addAll</code> method. This has 1487 * benefits in both simplicity (multiple elements can be added without 1488 * having to be wrapped inside a grouping structure) and efficiency 1489 * (as a redundant list doesn't have to be created to add an individual 1490 * set of elements or an array). 1491 * 1492 * @param c the collection to which the elements should be added. 1493 * @param a the elements to be added to the collection. 1494 * @return true if the collection changed its contents as a result. 1495 * @throws UnsupportedOperationException if the collection does not support 1496 * addition. 1497 * @throws NullPointerException if one or more elements in a are null, 1498 * and the collection does not allow null 1499 * elements. This exception is also thrown 1500 * if either <code>c</code> or <code>a</code> 1501 * are null. 1502 * @throws IllegalArgumentException if the collection won't allow an element 1503 * to be added for some other reason. 1504 * @since 1.5 1505 */ 1506 public static <T> boolean addAll(Collection<? super T> c, T... a) 1507 { 1508 boolean overall = false; 1509 1510 for (T element : a) 1511 { 1512 boolean result = c.add(element); 1513 if (result) 1514 overall = true; 1515 } 1516 return overall; 1517 } 1518 1519 /** 1520 * Returns true if the two specified collections have no elements in 1521 * common. This method may give unusual results if one or both collections 1522 * use a non-standard equality test. In the trivial case of comparing 1523 * a collection with itself, this method returns true if, and only if, 1524 * the collection is empty. 1525 * 1526 * @param c1 the first collection to compare. 1527 * @param c2 the second collection to compare. 1528 * @return true if the collections are disjoint. 1529 * @throws NullPointerException if either collection is null. 1530 * @since 1.5 1531 */ 1532 public static boolean disjoint(Collection<?> c1, Collection<?> c2) 1533 { 1534 Collection<Object> oc1 = (Collection<Object>) c1; 1535 final Iterator<Object> it = oc1.iterator(); 1536 while (it.hasNext()) 1537 if (c2.contains(it.next())) 1538 return false; 1539 return true; 1540 } 1541 1542 1543 /** 1544 * Obtain an immutable Set consisting of a single element. The return value 1545 * of this method is Serializable. 1546 * 1547 * @param o the single element 1548 * @return an immutable Set containing only o 1549 * @see Serializable 1550 */ 1551 public static <T> Set<T> singleton(T o) 1552 { 1553 return new SingletonSet<T>(o); 1554 } 1555 1556 /** 1557 * The implementation of {@link #singleton(Object)}. This class name 1558 * is required for compatibility with Sun's JDK serializability. 1559 * 1560 * @author Eric Blake (ebb9@email.byu.edu) 1561 */ 1562 private static final class SingletonSet<T> extends AbstractSet<T> 1563 implements Serializable 1564 { 1565 /** 1566 * Compatible with JDK 1.4. 1567 */ 1568 private static final long serialVersionUID = 3193687207550431679L; 1569 1570 1571 /** 1572 * The single element; package visible for use in nested class. 1573 * @serial the singleton 1574 */ 1575 final T element; 1576 1577 /** 1578 * Construct a singleton. 1579 * @param o the element 1580 */ 1581 SingletonSet(T o) 1582 { 1583 element = o; 1584 } 1585 1586 /** 1587 * The size: always 1! 1588 * @return 1. 1589 */ 1590 public int size() 1591 { 1592 return 1; 1593 } 1594 1595 /** 1596 * Returns an iterator over the lone element. 1597 */ 1598 public Iterator<T> iterator() 1599 { 1600 return new Iterator<T>() 1601 { 1602 /** 1603 * Flag to indicate whether or not the element has 1604 * been retrieved. 1605 */ 1606 private boolean hasNext = true; 1607 1608 /** 1609 * Returns <code>true</code> if elements still remain to be 1610 * iterated through. 1611 * 1612 * @return <code>true</code> if the element has not yet been returned. 1613 */ 1614 public boolean hasNext() 1615 { 1616 return hasNext; 1617 } 1618 1619 /** 1620 * Returns the element. 1621 * 1622 * @return The element used by this singleton. 1623 * @throws NoSuchElementException if the object 1624 * has already been retrieved. 1625 */ 1626 public T next() 1627 { 1628 if (hasNext) 1629 { 1630 hasNext = false; 1631 return element; 1632 } 1633 else 1634 throw new NoSuchElementException(); 1635 } 1636 1637 /** 1638 * Removes the element from the singleton. 1639 * As this set is immutable, this will always 1640 * throw an exception. 1641 * 1642 * @throws UnsupportedOperationException as the 1643 * singleton set doesn't support 1644 * <code>remove()</code>. 1645 */ 1646 public void remove() 1647 { 1648 throw new UnsupportedOperationException(); 1649 } 1650 }; 1651 } 1652 1653 // The remaining methods are optional, but provide a performance 1654 // advantage by not allocating unnecessary iterators in AbstractSet. 1655 /** 1656 * The set only contains one element. 1657 * 1658 * @param o The object to search for. 1659 * @return <code>true</code> if o == the element of the singleton. 1660 */ 1661 public boolean contains(Object o) 1662 { 1663 return equals(o, element); 1664 } 1665 1666 /** 1667 * This is true if the other collection only contains the element. 1668 * 1669 * @param c A collection to compare against this singleton. 1670 * @return <code>true</code> if c only contains either no elements or 1671 * elements equal to the element in this singleton. 1672 */ 1673 public boolean containsAll(Collection<?> c) 1674 { 1675 Iterator<?> i = c.iterator(); 1676 int pos = c.size(); 1677 while (--pos >= 0) 1678 if (! equals(i.next(), element)) 1679 return false; 1680 return true; 1681 } 1682 1683 /** 1684 * The hash is just that of the element. 1685 * 1686 * @return The hashcode of the element. 1687 */ 1688 public int hashCode() 1689 { 1690 return hashCode(element); 1691 } 1692 1693 /** 1694 * Returning an array is simple. 1695 * 1696 * @return An array containing the element. 1697 */ 1698 public Object[] toArray() 1699 { 1700 return new Object[] {element}; 1701 } 1702 1703 /** 1704 * Obvious string. 1705 * 1706 * @return The string surrounded by enclosing 1707 * square brackets. 1708 */ 1709 public String toString() 1710 { 1711 return "[" + element + "]"; 1712 } 1713 } // class SingletonSet 1714 1715 /** 1716 * Obtain an immutable List consisting of a single element. The return value 1717 * of this method is Serializable, and implements RandomAccess. 1718 * 1719 * @param o the single element 1720 * @return an immutable List containing only o 1721 * @see Serializable 1722 * @see RandomAccess 1723 * @since 1.3 1724 */ 1725 public static <T> List<T> singletonList(T o) 1726 { 1727 return new SingletonList<T>(o); 1728 } 1729 1730 /** 1731 * The implementation of {@link #singletonList(Object)}. This class name 1732 * is required for compatibility with Sun's JDK serializability. 1733 * 1734 * @author Eric Blake (ebb9@email.byu.edu) 1735 */ 1736 private static final class SingletonList<T> extends AbstractList<T> 1737 implements Serializable, RandomAccess 1738 { 1739 /** 1740 * Compatible with JDK 1.4. 1741 */ 1742 private static final long serialVersionUID = 3093736618740652951L; 1743 1744 /** 1745 * The single element. 1746 * @serial the singleton 1747 */ 1748 private final T element; 1749 1750 /** 1751 * Construct a singleton. 1752 * @param o the element 1753 */ 1754 SingletonList(T o) 1755 { 1756 element = o; 1757 } 1758 1759 /** 1760 * The size: always 1! 1761 * @return 1. 1762 */ 1763 public int size() 1764 { 1765 return 1; 1766 } 1767 1768 /** 1769 * Only index 0 is valid. 1770 * @param index The index of the element 1771 * to retrieve. 1772 * @return The singleton's element if the 1773 * index is 0. 1774 * @throws IndexOutOfBoundsException if 1775 * index is not 0. 1776 */ 1777 public T get(int index) 1778 { 1779 if (index == 0) 1780 return element; 1781 throw new IndexOutOfBoundsException(); 1782 } 1783 1784 // The remaining methods are optional, but provide a performance 1785 // advantage by not allocating unnecessary iterators in AbstractList. 1786 /** 1787 * The set only contains one element. 1788 * 1789 * @param o The object to search for. 1790 * @return <code>true</code> if o == the singleton element. 1791 */ 1792 public boolean contains(Object o) 1793 { 1794 return equals(o, element); 1795 } 1796 1797 /** 1798 * This is true if the other collection only contains the element. 1799 * 1800 * @param c A collection to compare against this singleton. 1801 * @return <code>true</code> if c only contains either no elements or 1802 * elements equal to the element in this singleton. 1803 */ 1804 public boolean containsAll(Collection<?> c) 1805 { 1806 Iterator<?> i = c.iterator(); 1807 int pos = c.size(); 1808 while (--pos >= 0) 1809 if (! equals(i.next(), element)) 1810 return false; 1811 return true; 1812 } 1813 1814 /** 1815 * Speed up the hashcode computation. 1816 * 1817 * @return The hashcode of the list, based 1818 * on the hashcode of the singleton element. 1819 */ 1820 public int hashCode() 1821 { 1822 return 31 + hashCode(element); 1823 } 1824 1825 /** 1826 * Either the list has it or not. 1827 * 1828 * @param o The object to find the first index of. 1829 * @return 0 if o is the singleton element, -1 if not. 1830 */ 1831 public int indexOf(Object o) 1832 { 1833 return equals(o, element) ? 0 : -1; 1834 } 1835 1836 /** 1837 * Either the list has it or not. 1838 * 1839 * @param o The object to find the last index of. 1840 * @return 0 if o is the singleton element, -1 if not. 1841 */ 1842 public int lastIndexOf(Object o) 1843 { 1844 return equals(o, element) ? 0 : -1; 1845 } 1846 1847 /** 1848 * Sublists are limited in scope. 1849 * 1850 * @param from The starting bound for the sublist. 1851 * @param to The ending bound for the sublist. 1852 * @return Either an empty list if both bounds are 1853 * 0 or 1, or this list if the bounds are 0 and 1. 1854 * @throws IllegalArgumentException if <code>from > to</code> 1855 * @throws IndexOutOfBoundsException if either bound is greater 1856 * than 1. 1857 */ 1858 public List<T> subList(int from, int to) 1859 { 1860 if (from == to && (to == 0 || to == 1)) 1861 return emptyList(); 1862 if (from == 0 && to == 1) 1863 return this; 1864 if (from > to) 1865 throw new IllegalArgumentException(); 1866 throw new IndexOutOfBoundsException(); 1867 } 1868 1869 /** 1870 * Returning an array is simple. 1871 * 1872 * @return An array containing the element. 1873 */ 1874 public Object[] toArray() 1875 { 1876 return new Object[] {element}; 1877 } 1878 1879 /** 1880 * Obvious string. 1881 * 1882 * @return The string surrounded by enclosing 1883 * square brackets. 1884 */ 1885 public String toString() 1886 { 1887 return "[" + element + "]"; 1888 } 1889 } // class SingletonList 1890 1891 /** 1892 * Obtain an immutable Map consisting of a single key-value pair. 1893 * The return value of this method is Serializable. 1894 * 1895 * @param key the single key 1896 * @param value the single value 1897 * @return an immutable Map containing only the single key-value pair 1898 * @see Serializable 1899 * @since 1.3 1900 */ 1901 public static <K, V> Map<K, V> singletonMap(K key, V value) 1902 { 1903 return new SingletonMap<K, V>(key, value); 1904 } 1905 1906 /** 1907 * The implementation of {@link #singletonMap(Object, Object)}. This class 1908 * name is required for compatibility with Sun's JDK serializability. 1909 * 1910 * @author Eric Blake (ebb9@email.byu.edu) 1911 */ 1912 private static final class SingletonMap<K, V> extends AbstractMap<K, V> 1913 implements Serializable 1914 { 1915 /** 1916 * Compatible with JDK 1.4. 1917 */ 1918 private static final long serialVersionUID = -6979724477215052911L; 1919 1920 /** 1921 * The single key. 1922 * @serial the singleton key 1923 */ 1924 private final K k; 1925 1926 /** 1927 * The corresponding value. 1928 * @serial the singleton value 1929 */ 1930 private final V v; 1931 1932 /** 1933 * Cache the entry set. 1934 */ 1935 private transient Set<Map.Entry<K, V>> entries; 1936 1937 /** 1938 * Construct a singleton. 1939 * @param key the key 1940 * @param value the value 1941 */ 1942 SingletonMap(K key, V value) 1943 { 1944 k = key; 1945 v = value; 1946 } 1947 1948 /** 1949 * There is a single immutable entry. 1950 * 1951 * @return A singleton containing the map entry. 1952 */ 1953 public Set<Map.Entry<K, V>> entrySet() 1954 { 1955 if (entries == null) 1956 { 1957 Map.Entry<K,V> entry = new AbstractMap.SimpleEntry<K, V>(k, v) 1958 { 1959 /** 1960 * Sets the value of the map entry to the supplied value. 1961 * An exception is always thrown, as the map is immutable. 1962 * 1963 * @param o The new value. 1964 * @return The old value. 1965 * @throws UnsupportedOperationException as setting the value 1966 * is not supported. 1967 */ 1968 public V setValue(V o) 1969 { 1970 throw new UnsupportedOperationException(); 1971 } 1972 }; 1973 entries = singleton(entry); 1974 } 1975 return entries; 1976 } 1977 1978 // The remaining methods are optional, but provide a performance 1979 // advantage by not allocating unnecessary iterators in AbstractMap. 1980 /** 1981 * Single entry. 1982 * 1983 * @param key The key to look for. 1984 * @return <code>true</code> if the key is the same as the one used by 1985 * this map. 1986 */ 1987 public boolean containsKey(Object key) 1988 { 1989 return equals(key, k); 1990 } 1991 1992 /** 1993 * Single entry. 1994 * 1995 * @param value The value to look for. 1996 * @return <code>true</code> if the value is the same as the one used by 1997 * this map. 1998 */ 1999 public boolean containsValue(Object value) 2000 { 2001 return equals(value, v); 2002 } 2003 2004 /** 2005 * Single entry. 2006 * 2007 * @param key The key of the value to be retrieved. 2008 * @return The singleton value if the key is the same as the 2009 * singleton key, null otherwise. 2010 */ 2011 public V get(Object key) 2012 { 2013 return equals(key, k) ? v : null; 2014 } 2015 2016 /** 2017 * Calculate the hashcode directly. 2018 * 2019 * @return The hashcode computed from the singleton key 2020 * and the singleton value. 2021 */ 2022 public int hashCode() 2023 { 2024 return hashCode(k) ^ hashCode(v); 2025 } 2026 2027 /** 2028 * Return the keyset. 2029 * 2030 * @return A singleton containing the key. 2031 */ 2032 public Set<K> keySet() 2033 { 2034 if (keys == null) 2035 keys = singleton(k); 2036 return keys; 2037 } 2038 2039 /** 2040 * The size: always 1! 2041 * 2042 * @return 1. 2043 */ 2044 public int size() 2045 { 2046 return 1; 2047 } 2048 2049 /** 2050 * Return the values. Technically, a singleton, while more specific than 2051 * a general Collection, will work. Besides, that's what the JDK uses! 2052 * 2053 * @return A singleton containing the value. 2054 */ 2055 public Collection<V> values() 2056 { 2057 if (values == null) 2058 values = singleton(v); 2059 return values; 2060 } 2061 2062 /** 2063 * Obvious string. 2064 * 2065 * @return A string containing the string representations of the key 2066 * and its associated value. 2067 */ 2068 public String toString() 2069 { 2070 return "{" + k + "=" + v + "}"; 2071 } 2072 } // class SingletonMap 2073 2074 /** 2075 * Sort a list according to the natural ordering of its elements. The list 2076 * must be modifiable, but can be of fixed size. The sort algorithm is 2077 * precisely that used by Arrays.sort(Object[]), which offers guaranteed 2078 * nlog(n) performance. This implementation dumps the list into an array, 2079 * sorts the array, and then iterates over the list setting each element from 2080 * the array. 2081 * 2082 * @param l the List to sort (<code>null</code> not permitted) 2083 * @throws ClassCastException if some items are not mutually comparable 2084 * @throws UnsupportedOperationException if the List is not modifiable 2085 * @throws NullPointerException if the list is <code>null</code>, or contains 2086 * some element that is <code>null</code>. 2087 * @see Arrays#sort(Object[]) 2088 */ 2089 public static <T extends Comparable<? super T>> void sort(List<T> l) 2090 { 2091 sort(l, null); 2092 } 2093 2094 /** 2095 * Sort a list according to a specified Comparator. The list must be 2096 * modifiable, but can be of fixed size. The sort algorithm is precisely that 2097 * used by Arrays.sort(Object[], Comparator), which offers guaranteed 2098 * nlog(n) performance. This implementation dumps the list into an array, 2099 * sorts the array, and then iterates over the list setting each element from 2100 * the array. 2101 * 2102 * @param l the List to sort (<code>null</code> not permitted) 2103 * @param c the Comparator specifying the ordering for the elements, or 2104 * <code>null</code> for natural ordering 2105 * @throws ClassCastException if c will not compare some pair of items 2106 * @throws UnsupportedOperationException if the List is not modifiable 2107 * @throws NullPointerException if the List is <code>null</code> or 2108 * <code>null</code> is compared by natural ordering (only possible 2109 * when c is <code>null</code>) 2110 * 2111 * @see Arrays#sort(Object[], Comparator) 2112 */ 2113 public static <T> void sort(List<T> l, Comparator<? super T> c) 2114 { 2115 T[] a = (T[]) l.toArray(); 2116 Arrays.sort(a, c); 2117 ListIterator<T> i = l.listIterator(); 2118 for (int pos = 0, alen = a.length; pos < alen; pos++) 2119 { 2120 i.next(); 2121 i.set(a[pos]); 2122 } 2123 } 2124 2125 /** 2126 * Swaps the elements at the specified positions within the list. Equal 2127 * positions have no effect. 2128 * 2129 * @param l the list to work on 2130 * @param i the first index to swap 2131 * @param j the second index 2132 * @throws UnsupportedOperationException if list.set is not supported 2133 * @throws IndexOutOfBoundsException if either i or j is < 0 or >= 2134 * list.size() 2135 * @since 1.4 2136 */ 2137 public static void swap(List<?> l, int i, int j) 2138 { 2139 List<Object> list = (List<Object>) l; 2140 list.set(i, list.set(j, list.get(i))); 2141 } 2142 2143 2144 /** 2145 * Returns a synchronized (thread-safe) collection wrapper backed by the 2146 * given collection. Notice that element access through the iterators 2147 * is thread-safe, but if the collection can be structurally modified 2148 * (adding or removing elements) then you should synchronize around the 2149 * iteration to avoid non-deterministic behavior:<br> 2150 * <pre> 2151 * Collection c = Collections.synchronizedCollection(new Collection(...)); 2152 * ... 2153 * synchronized (c) 2154 * { 2155 * Iterator i = c.iterator(); 2156 * while (i.hasNext()) 2157 * foo(i.next()); 2158 * } 2159 * </pre><p> 2160 * 2161 * Since the collection might be a List or a Set, and those have incompatible 2162 * equals and hashCode requirements, this relies on Object's implementation 2163 * rather than passing those calls on to the wrapped collection. The returned 2164 * Collection implements Serializable, but can only be serialized if 2165 * the collection it wraps is likewise Serializable. 2166 * 2167 * @param c the collection to wrap 2168 * @return a synchronized view of the collection 2169 * @see Serializable 2170 */ 2171 public static <T> Collection<T> synchronizedCollection(Collection<T> c) 2172 { 2173 return new SynchronizedCollection<T>(c); 2174 } 2175 2176 /** 2177 * The implementation of {@link #synchronizedCollection(Collection)}. This 2178 * class name is required for compatibility with Sun's JDK serializability. 2179 * Package visible, so that collections such as the one for 2180 * Hashtable.values() can specify which object to synchronize on. 2181 * 2182 * @author Eric Blake (ebb9@email.byu.edu) 2183 */ 2184 static class SynchronizedCollection<T> 2185 implements Collection<T>, Serializable 2186 { 2187 /** 2188 * Compatible with JDK 1.4. 2189 */ 2190 private static final long serialVersionUID = 3053995032091335093L; 2191 2192 /** 2193 * The wrapped collection. Package visible for use by subclasses. 2194 * @serial the real collection 2195 */ 2196 final Collection<T> c; 2197 2198 /** 2199 * The object to synchronize on. When an instance is created via public 2200 * methods, it will be this; but other uses like SynchronizedMap.values() 2201 * must specify another mutex. Package visible for use by subclasses. 2202 * @serial the lock 2203 */ 2204 final Object mutex; 2205 2206 /** 2207 * Wrap a given collection. 2208 * @param c the collection to wrap 2209 * @throws NullPointerException if c is null 2210 */ 2211 SynchronizedCollection(Collection<T> c) 2212 { 2213 this.c = c; 2214 mutex = this; 2215 if (c == null) 2216 throw new NullPointerException(); 2217 } 2218 2219 /** 2220 * Called only by trusted code to specify the mutex as well as the 2221 * collection. 2222 * @param sync the mutex 2223 * @param c the collection 2224 */ 2225 SynchronizedCollection(Object sync, Collection<T> c) 2226 { 2227 this.c = c; 2228 mutex = sync; 2229 } 2230 2231 /** 2232 * Adds the object to the underlying collection, first 2233 * obtaining a lock on the mutex. 2234 * 2235 * @param o The object to add. 2236 * @return <code>true</code> if the collection was modified as a result 2237 * of this action. 2238 * @throws UnsupportedOperationException if this collection does not 2239 * support the add operation. 2240 * @throws ClassCastException if o cannot be added to this collection due 2241 * to its type. 2242 * @throws NullPointerException if o is null and this collection doesn't 2243 * support the addition of null values. 2244 * @throws IllegalArgumentException if o cannot be added to this 2245 * collection for some other reason. 2246 */ 2247 public boolean add(T o) 2248 { 2249 synchronized (mutex) 2250 { 2251 return c.add(o); 2252 } 2253 } 2254 2255 /** 2256 * Adds the objects in col to the underlying collection, first 2257 * obtaining a lock on the mutex. 2258 * 2259 * @param col The collection to take the new objects from. 2260 * @return <code>true</code> if the collection was modified as a result 2261 * of this action. 2262 * @throws UnsupportedOperationException if this collection does not 2263 * support the addAll operation. 2264 * @throws ClassCastException if some element of col cannot be added to this 2265 * collection due to its type. 2266 * @throws NullPointerException if some element of col is null and this 2267 * collection does not support the addition of null values. 2268 * @throws NullPointerException if col itself is null. 2269 * @throws IllegalArgumentException if some element of col cannot be added 2270 * to this collection for some other reason. 2271 */ 2272 public boolean addAll(Collection<? extends T> col) 2273 { 2274 synchronized (mutex) 2275 { 2276 return c.addAll(col); 2277 } 2278 } 2279 2280 /** 2281 * Removes all objects from the underlying collection, 2282 * first obtaining a lock on the mutex. 2283 * 2284 * @throws UnsupportedOperationException if this collection does not 2285 * support the clear operation. 2286 */ 2287 public void clear() 2288 { 2289 synchronized (mutex) 2290 { 2291 c.clear(); 2292 } 2293 } 2294 2295 /** 2296 * Checks for the existence of o within the underlying 2297 * collection, first obtaining a lock on the mutex. 2298 * 2299 * @param o the element to look for. 2300 * @return <code>true</code> if this collection contains at least one 2301 * element e such that <code>o == null ? e == null : o.equals(e)</code>. 2302 * @throws ClassCastException if the type of o is not a valid type for this 2303 * collection. 2304 * @throws NullPointerException if o is null and this collection doesn't 2305 * support null values. 2306 */ 2307 public boolean contains(Object o) 2308 { 2309 synchronized (mutex) 2310 { 2311 return c.contains(o); 2312 } 2313 } 2314 2315 /** 2316 * Checks for the existence of each object in cl 2317 * within the underlying collection, first obtaining 2318 * a lock on the mutex. 2319 * 2320 * @param c1 the collection to test for. 2321 * @return <code>true</code> if for every element o in c, contains(o) 2322 * would return <code>true</code>. 2323 * @throws ClassCastException if the type of any element in cl is not a valid 2324 * type for this collection. 2325 * @throws NullPointerException if some element of cl is null and this 2326 * collection does not support null values. 2327 * @throws NullPointerException if cl itself is null. 2328 */ 2329 public boolean containsAll(Collection<?> c1) 2330 { 2331 synchronized (mutex) 2332 { 2333 return c.containsAll(c1); 2334 } 2335 } 2336 2337 /** 2338 * Returns <code>true</code> if there are no objects in the underlying 2339 * collection. A lock on the mutex is obtained before the 2340 * check is performed. 2341 * 2342 * @return <code>true</code> if this collection contains no elements. 2343 */ 2344 public boolean isEmpty() 2345 { 2346 synchronized (mutex) 2347 { 2348 return c.isEmpty(); 2349 } 2350 } 2351 2352 /** 2353 * Returns a synchronized iterator wrapper around the underlying 2354 * collection's iterator. A lock on the mutex is obtained before 2355 * retrieving the collection's iterator. 2356 * 2357 * @return An iterator over the elements in the underlying collection, 2358 * which returns each element in any order. 2359 */ 2360 public Iterator<T> iterator() 2361 { 2362 synchronized (mutex) 2363 { 2364 return new SynchronizedIterator<T>(mutex, c.iterator()); 2365 } 2366 } 2367 2368 /** 2369 * Removes the specified object from the underlying collection, 2370 * first obtaining a lock on the mutex. 2371 * 2372 * @param o The object to remove. 2373 * @return <code>true</code> if the collection changed as a result of this call, that is, 2374 * if the collection contained at least one occurrence of o. 2375 * @throws UnsupportedOperationException if this collection does not 2376 * support the remove operation. 2377 * @throws ClassCastException if the type of o is not a valid type 2378 * for this collection. 2379 * @throws NullPointerException if o is null and the collection doesn't 2380 * support null values. 2381 */ 2382 public boolean remove(Object o) 2383 { 2384 synchronized (mutex) 2385 { 2386 return c.remove(o); 2387 } 2388 } 2389 2390 /** 2391 * Removes all elements, e, of the underlying 2392 * collection for which <code>col.contains(e)</code> 2393 * returns <code>true</code>. A lock on the mutex is obtained 2394 * before the operation proceeds. 2395 * 2396 * @param col The collection of objects to be removed. 2397 * @return <code>true</code> if this collection was modified as a result of this call. 2398 * @throws UnsupportedOperationException if this collection does not 2399 * support the removeAll operation. 2400 * @throws ClassCastException if the type of any element in c is not a valid 2401 * type for this collection. 2402 * @throws NullPointerException if some element of c is null and this 2403 * collection does not support removing null values. 2404 * @throws NullPointerException if c itself is null. 2405 */ 2406 public boolean removeAll(Collection<?> col) 2407 { 2408 synchronized (mutex) 2409 { 2410 return c.removeAll(col); 2411 } 2412 } 2413 2414 /** 2415 * Retains all elements, e, of the underlying 2416 * collection for which <code>col.contains(e)</code> 2417 * returns <code>true</code>. That is, every element that doesn't 2418 * exist in col is removed. A lock on the mutex is obtained 2419 * before the operation proceeds. 2420 * 2421 * @param col The collection of objects to be removed. 2422 * @return <code>true</code> if this collection was modified as a result of this call. 2423 * @throws UnsupportedOperationException if this collection does not 2424 * support the removeAll operation. 2425 * @throws ClassCastException if the type of any element in c is not a valid 2426 * type for this collection. 2427 * @throws NullPointerException if some element of c is null and this 2428 * collection does not support removing null values. 2429 * @throws NullPointerException if c itself is null. 2430 */ 2431 public boolean retainAll(Collection<?> col) 2432 { 2433 synchronized (mutex) 2434 { 2435 return c.retainAll(col); 2436 } 2437 } 2438 2439 /** 2440 * Retrieves the size of the underlying collection. 2441 * A lock on the mutex is obtained before the collection 2442 * is accessed. 2443 * 2444 * @return The size of the collection. 2445 */ 2446 public int size() 2447 { 2448 synchronized (mutex) 2449 { 2450 return c.size(); 2451 } 2452 } 2453 2454 /** 2455 * Returns an array containing each object within the underlying 2456 * collection. A lock is obtained on the mutex before the collection 2457 * is accessed. 2458 * 2459 * @return An array of objects, matching the collection in size. The 2460 * elements occur in any order. 2461 */ 2462 public Object[] toArray() 2463 { 2464 synchronized (mutex) 2465 { 2466 return c.toArray(); 2467 } 2468 } 2469 2470 /** 2471 * Copies the elements in the underlying collection to the supplied 2472 * array. If <code>a.length < size()</code>, a new array of the 2473 * same run-time type is created, with a size equal to that of 2474 * the collection. If <code>a.length > size()</code>, then the 2475 * elements from 0 to <code>size() - 1</code> contain the elements 2476 * from this collection. The following element is set to null 2477 * to indicate the end of the collection objects. However, this 2478 * only makes a difference if null is not a permitted value within 2479 * the collection. 2480 * Before the copying takes place, a lock is obtained on the mutex. 2481 * 2482 * @param a An array to copy elements to. 2483 * @return An array containing the elements of the underlying collection. 2484 * @throws ArrayStoreException if the type of any element of the 2485 * collection is not a subtype of the element type of a. 2486 */ 2487 public <E> E[] toArray(E[] a) 2488 { 2489 synchronized (mutex) 2490 { 2491 return c.toArray(a); 2492 } 2493 } 2494 2495 /** 2496 * Returns a string representation of the underlying collection. 2497 * A lock is obtained on the mutex before the string is created. 2498 * 2499 * @return A string representation of the collection. 2500 */ 2501 public String toString() 2502 { 2503 synchronized (mutex) 2504 { 2505 return c.toString(); 2506 } 2507 } 2508 } // class SynchronizedCollection 2509 2510 /** 2511 * The implementation of the various iterator methods in the 2512 * synchronized classes. These iterators must "sync" on the same object 2513 * as the collection they iterate over. 2514 * 2515 * @author Eric Blake (ebb9@email.byu.edu) 2516 */ 2517 private static class SynchronizedIterator<T> implements Iterator<T> 2518 { 2519 /** 2520 * The object to synchronize on. Package visible for use by subclass. 2521 */ 2522 final Object mutex; 2523 2524 /** 2525 * The wrapped iterator. 2526 */ 2527 private final Iterator<T> i; 2528 2529 /** 2530 * Only trusted code creates a wrapper, with the specified sync. 2531 * @param sync the mutex 2532 * @param i the wrapped iterator 2533 */ 2534 SynchronizedIterator(Object sync, Iterator<T> i) 2535 { 2536 this.i = i; 2537 mutex = sync; 2538 } 2539 2540 /** 2541 * Retrieves the next object in the underlying collection. 2542 * A lock is obtained on the mutex before the collection is accessed. 2543 * 2544 * @return The next object in the collection. 2545 * @throws NoSuchElementException if there are no more elements 2546 */ 2547 public T next() 2548 { 2549 synchronized (mutex) 2550 { 2551 return i.next(); 2552 } 2553 } 2554 2555 /** 2556 * Returns <code>true</code> if objects can still be retrieved from the iterator 2557 * using <code>next()</code>. A lock is obtained on the mutex before 2558 * the collection is accessed. 2559 * 2560 * @return <code>true</code> if at least one element is still to be returned by 2561 * <code>next()</code>. 2562 */ 2563 public boolean hasNext() 2564 { 2565 synchronized (mutex) 2566 { 2567 return i.hasNext(); 2568 } 2569 } 2570 2571 /** 2572 * Removes the object that was last returned by <code>next()</code> 2573 * from the underlying collection. Only one call to this method is 2574 * allowed per call to the <code>next()</code> method, and it does 2575 * not affect the value that will be returned by <code>next()</code>. 2576 * Thus, if element n was retrieved from the collection by 2577 * <code>next()</code>, it is this element that gets removed. 2578 * Regardless of whether this takes place or not, element n+1 is 2579 * still returned on the subsequent <code>next()</code> call. 2580 * 2581 * @throws IllegalStateException if next has not yet been called or remove 2582 * has already been called since the last call to next. 2583 * @throws UnsupportedOperationException if this Iterator does not support 2584 * the remove operation. 2585 */ 2586 public void remove() 2587 { 2588 synchronized (mutex) 2589 { 2590 i.remove(); 2591 } 2592 } 2593 } // class SynchronizedIterator 2594 2595 /** 2596 * Returns a synchronized (thread-safe) list wrapper backed by the 2597 * given list. Notice that element access through the iterators 2598 * is thread-safe, but if the list can be structurally modified 2599 * (adding or removing elements) then you should synchronize around the 2600 * iteration to avoid non-deterministic behavior:<br> 2601 * <pre> 2602 * List l = Collections.synchronizedList(new List(...)); 2603 * ... 2604 * synchronized (l) 2605 * { 2606 * Iterator i = l.iterator(); 2607 * while (i.hasNext()) 2608 * foo(i.next()); 2609 * } 2610 * </pre><p> 2611 * 2612 * The returned List implements Serializable, but can only be serialized if 2613 * the list it wraps is likewise Serializable. In addition, if the wrapped 2614 * list implements RandomAccess, this does too. 2615 * 2616 * @param l the list to wrap 2617 * @return a synchronized view of the list 2618 * @see Serializable 2619 * @see RandomAccess 2620 */ 2621 public static <T> List<T> synchronizedList(List<T> l) 2622 { 2623 if (l instanceof RandomAccess) 2624 return new SynchronizedRandomAccessList<T>(l); 2625 return new SynchronizedList<T>(l); 2626 } 2627 2628 /** 2629 * The implementation of {@link #synchronizedList(List)} for sequential 2630 * lists. This class name is required for compatibility with Sun's JDK 2631 * serializability. Package visible, so that lists such as Vector.subList() 2632 * can specify which object to synchronize on. 2633 * 2634 * @author Eric Blake (ebb9@email.byu.edu) 2635 */ 2636 static class SynchronizedList<T> extends SynchronizedCollection<T> 2637 implements List<T> 2638 { 2639 /** 2640 * Compatible with JDK 1.4. 2641 */ 2642 private static final long serialVersionUID = -7754090372962971524L; 2643 2644 /** 2645 * The wrapped list; stored both here and in the superclass to avoid 2646 * excessive casting. Package visible for use by subclass. 2647 * @serial the wrapped list 2648 */ 2649 final List<T> list; 2650 2651 /** 2652 * Wrap a given list. 2653 * @param l the list to wrap 2654 * @throws NullPointerException if l is null 2655 */ 2656 SynchronizedList(List<T> l) 2657 { 2658 super(l); 2659 list = l; 2660 } 2661 2662 /** 2663 * Called only by trusted code to specify the mutex as well as the list. 2664 * @param sync the mutex 2665 * @param l the list 2666 */ 2667 SynchronizedList(Object sync, List<T> l) 2668 { 2669 super(sync, l); 2670 list = l; 2671 } 2672 2673 /** 2674 * Insert an element into the underlying list at a given position (optional 2675 * operation). This shifts all existing elements from that position to the 2676 * end one index to the right. This version of add has no return, since it is 2677 * assumed to always succeed if there is no exception. Before the 2678 * addition takes place, a lock is obtained on the mutex. 2679 * 2680 * @param index the location to insert the item 2681 * @param o the object to insert 2682 * @throws UnsupportedOperationException if this list does not support the 2683 * add operation 2684 * @throws IndexOutOfBoundsException if index < 0 || index > size() 2685 * @throws ClassCastException if o cannot be added to this list due to its 2686 * type 2687 * @throws IllegalArgumentException if o cannot be added to this list for 2688 * some other reason 2689 * @throws NullPointerException if o is null and this list doesn't support 2690 * the addition of null values. 2691 */ 2692 public void add(int index, T o) 2693 { 2694 synchronized (mutex) 2695 { 2696 list.add(index, o); 2697 } 2698 } 2699 2700 /** 2701 * Add the contents of a collection to the underlying list at the given 2702 * index (optional operation). If the list imposes restraints on what 2703 * can be inserted, such as no null elements, this should be documented. 2704 * A lock is obtained on the mutex before any of the elements are added. 2705 * 2706 * @param index the index at which to insert 2707 * @param c the collection to add 2708 * @return <code>true</code>, as defined by Collection for a modified list 2709 * @throws UnsupportedOperationException if this list does not support the 2710 * add operation 2711 * @throws ClassCastException if o cannot be added to this list due to its 2712 * type 2713 * @throws IllegalArgumentException if o cannot be added to this list for 2714 * some other reason 2715 * @throws NullPointerException if o is null and this list doesn't support 2716 * the addition of null values. 2717 */ 2718 public boolean addAll(int index, Collection<? extends T> c) 2719 { 2720 synchronized (mutex) 2721 { 2722 return list.addAll(index, c); 2723 } 2724 } 2725 2726 /** 2727 * Tests whether the underlying list is equal to the supplied object. 2728 * The object is deemed to be equal if it is also a <code>List</code> 2729 * of equal size and with the same elements (i.e. each element, e1, 2730 * in list, l1, and each element, e2, in l2, must return <code>true</code> for 2731 * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the 2732 * comparison is made, a lock is obtained on the mutex. 2733 * 2734 * @param o The object to test for equality with the underlying list. 2735 * @return <code>true</code> if o is equal to the underlying list under the above 2736 * definition. 2737 */ 2738 public boolean equals(Object o) 2739 { 2740 synchronized (mutex) 2741 { 2742 return list.equals(o); 2743 } 2744 } 2745 2746 /** 2747 * Retrieves the object at the specified index. A lock 2748 * is obtained on the mutex before the list is accessed. 2749 * 2750 * @param index the index of the element to be returned 2751 * @return the element at index index in this list 2752 * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2753 */ 2754 public T get(int index) 2755 { 2756 synchronized (mutex) 2757 { 2758 return list.get(index); 2759 } 2760 } 2761 2762 /** 2763 * Obtains a hashcode for the underlying list, first obtaining 2764 * a lock on the mutex. The calculation of the hashcode is 2765 * detailed in the documentation for the <code>List</code> 2766 * interface. 2767 * 2768 * @return The hashcode of the underlying list. 2769 * @see List#hashCode() 2770 */ 2771 public int hashCode() 2772 { 2773 synchronized (mutex) 2774 { 2775 return list.hashCode(); 2776 } 2777 } 2778 2779 /** 2780 * Obtain the first index at which a given object is to be found in the 2781 * underlying list. A lock is obtained on the mutex before the list is 2782 * accessed. 2783 * 2784 * @param o the object to search for 2785 * @return the least integer n such that <code>o == null ? get(n) == null : 2786 * o.equals(get(n))</code>, or -1 if there is no such index. 2787 * @throws ClassCastException if the type of o is not a valid 2788 * type for this list. 2789 * @throws NullPointerException if o is null and this 2790 * list does not support null values. 2791 */ 2792 2793 public int indexOf(Object o) 2794 { 2795 synchronized (mutex) 2796 { 2797 return list.indexOf(o); 2798 } 2799 } 2800 2801 /** 2802 * Obtain the last index at which a given object is to be found in this 2803 * underlying list. A lock is obtained on the mutex before the list 2804 * is accessed. 2805 * 2806 * @return the greatest integer n such that <code>o == null ? get(n) == null 2807 * : o.equals(get(n))</code>, or -1 if there is no such index. 2808 * @throws ClassCastException if the type of o is not a valid 2809 * type for this list. 2810 * @throws NullPointerException if o is null and this 2811 * list does not support null values. 2812 */ 2813 public int lastIndexOf(Object o) 2814 { 2815 synchronized (mutex) 2816 { 2817 return list.lastIndexOf(o); 2818 } 2819 } 2820 2821 /** 2822 * Retrieves a synchronized wrapper around the underlying list's 2823 * list iterator. A lock is obtained on the mutex before the 2824 * list iterator is retrieved. 2825 * 2826 * @return A list iterator over the elements in the underlying list. 2827 * The list iterator allows additional list-specific operations 2828 * to be performed, in addition to those supplied by the 2829 * standard iterator. 2830 */ 2831 public ListIterator<T> listIterator() 2832 { 2833 synchronized (mutex) 2834 { 2835 return new SynchronizedListIterator<T>(mutex, list.listIterator()); 2836 } 2837 } 2838 2839 /** 2840 * Retrieves a synchronized wrapper around the underlying list's 2841 * list iterator. A lock is obtained on the mutex before the 2842 * list iterator is retrieved. The iterator starts at the 2843 * index supplied, leading to the element at that index being 2844 * the first one returned by <code>next()</code>. Calling 2845 * <code>previous()</code> from this initial position returns 2846 * index - 1. 2847 * 2848 * @param index the position, between 0 and size() inclusive, to begin the 2849 * iteration from 2850 * @return A list iterator over the elements in the underlying list. 2851 * The list iterator allows additional list-specific operations 2852 * to be performed, in addition to those supplied by the 2853 * standard iterator. 2854 * @throws IndexOutOfBoundsException if index < 0 || index > size() 2855 */ 2856 public ListIterator<T> listIterator(int index) 2857 { 2858 synchronized (mutex) 2859 { 2860 return new SynchronizedListIterator<T>(mutex, 2861 list.listIterator(index)); 2862 } 2863 } 2864 2865 /** 2866 * Remove the element at a given position in the underlying list (optional 2867 * operation). All remaining elements are shifted to the left to fill the gap. 2868 * A lock on the mutex is obtained before the element is removed. 2869 * 2870 * @param index the position within the list of the object to remove 2871 * @return the object that was removed 2872 * @throws UnsupportedOperationException if this list does not support the 2873 * remove operation 2874 * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2875 */ 2876 public T remove(int index) 2877 { 2878 synchronized (mutex) 2879 { 2880 return list.remove(index); 2881 } 2882 } 2883 2884 /** 2885 * Replace an element of the underlying list with another object (optional 2886 * operation). A lock is obtained on the mutex before the element is 2887 * replaced. 2888 * 2889 * @param index the position within this list of the element to be replaced 2890 * @param o the object to replace it with 2891 * @return the object that was replaced 2892 * @throws UnsupportedOperationException if this list does not support the 2893 * set operation. 2894 * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2895 * @throws ClassCastException if o cannot be added to this list due to its 2896 * type 2897 * @throws IllegalArgumentException if o cannot be added to this list for 2898 * some other reason 2899 * @throws NullPointerException if o is null and this 2900 * list does not support null values. 2901 */ 2902 public T set(int index, T o) 2903 { 2904 synchronized (mutex) 2905 { 2906 return list.set(index, o); 2907 } 2908 } 2909 2910 /** 2911 * Obtain a List view of a subsection of the underlying list, from fromIndex 2912 * (inclusive) to toIndex (exclusive). If the two indices are equal, the 2913 * sublist is empty. The returned list should be modifiable if and only 2914 * if this list is modifiable. Changes to the returned list should be 2915 * reflected in this list. If this list is structurally modified in 2916 * any way other than through the returned list, the result of any subsequent 2917 * operations on the returned list is undefined. A lock is obtained 2918 * on the mutex before the creation of the sublist. The returned list 2919 * is also synchronized, using the same mutex. 2920 * 2921 * @param fromIndex the index that the returned list should start from 2922 * (inclusive) 2923 * @param toIndex the index that the returned list should go to (exclusive) 2924 * @return a List backed by a subsection of this list 2925 * @throws IndexOutOfBoundsException if fromIndex < 0 2926 * || toIndex > size() || fromIndex > toIndex 2927 */ 2928 public List<T> subList(int fromIndex, int toIndex) 2929 { 2930 synchronized (mutex) 2931 { 2932 return new SynchronizedList<T>(mutex, 2933 list.subList(fromIndex, toIndex)); 2934 } 2935 } 2936 } // class SynchronizedList 2937 2938 /** 2939 * The implementation of {@link #synchronizedList(List)} for random-access 2940 * lists. This class name is required for compatibility with Sun's JDK 2941 * serializability. 2942 * 2943 * @author Eric Blake (ebb9@email.byu.edu) 2944 */ 2945 private static final class SynchronizedRandomAccessList<T> 2946 extends SynchronizedList<T> implements RandomAccess 2947 { 2948 /** 2949 * Compatible with JDK 1.4. 2950 */ 2951 private static final long serialVersionUID = 1530674583602358482L; 2952 2953 /** 2954 * Wrap a given list. 2955 * @param l the list to wrap 2956 * @throws NullPointerException if l is null 2957 */ 2958 SynchronizedRandomAccessList(List<T> l) 2959 { 2960 super(l); 2961 } 2962 2963 /** 2964 * Called only by trusted code to specify the mutex as well as the 2965 * collection. 2966 * @param sync the mutex 2967 * @param l the list 2968 */ 2969 SynchronizedRandomAccessList(Object sync, List<T> l) 2970 { 2971 super(sync, l); 2972 } 2973 2974 /** 2975 * Obtain a List view of a subsection of the underlying list, from fromIndex 2976 * (inclusive) to toIndex (exclusive). If the two indices are equal, the 2977 * sublist is empty. The returned list should be modifiable if and only 2978 * if this list is modifiable. Changes to the returned list should be 2979 * reflected in this list. If this list is structurally modified in 2980 * any way other than through the returned list, the result of any subsequent 2981 * operations on the returned list is undefined. A lock is obtained 2982 * on the mutex before the creation of the sublist. The returned list 2983 * is also synchronized, using the same mutex. Random accessibility 2984 * is also extended to the new list. 2985 * 2986 * @param fromIndex the index that the returned list should start from 2987 * (inclusive) 2988 * @param toIndex the index that the returned list should go to (exclusive) 2989 * @return a List backed by a subsection of this list 2990 * @throws IndexOutOfBoundsException if fromIndex < 0 2991 * || toIndex > size() || fromIndex > toIndex 2992 */ 2993 public List<T> subList(int fromIndex, int toIndex) 2994 { 2995 synchronized (mutex) 2996 { 2997 return new SynchronizedRandomAccessList<T>(mutex, 2998 list.subList(fromIndex, 2999 toIndex)); 3000 } 3001 } 3002 } // class SynchronizedRandomAccessList 3003 3004 /** 3005 * The implementation of {@link SynchronizedList#listIterator()}. This 3006 * iterator must "sync" on the same object as the list it iterates over. 3007 * 3008 * @author Eric Blake (ebb9@email.byu.edu) 3009 */ 3010 private static final class SynchronizedListIterator<T> 3011 extends SynchronizedIterator<T> implements ListIterator<T> 3012 { 3013 /** 3014 * The wrapped iterator, stored both here and in the superclass to 3015 * avoid excessive casting. 3016 */ 3017 private final ListIterator<T> li; 3018 3019 /** 3020 * Only trusted code creates a wrapper, with the specified sync. 3021 * @param sync the mutex 3022 * @param li the wrapped iterator 3023 */ 3024 SynchronizedListIterator(Object sync, ListIterator<T> li) 3025 { 3026 super(sync, li); 3027 this.li = li; 3028 } 3029 3030 /** 3031 * Insert an element into the underlying list at the current position of 3032 * the iterator (optional operation). The element is inserted in between 3033 * the element that would be returned by <code>previous()</code> and the 3034 * element that would be returned by <code>next()</code>. After the 3035 * insertion, a subsequent call to next is unaffected, but 3036 * a call to previous returns the item that was added. The values returned 3037 * by nextIndex() and previousIndex() are incremented. A lock is obtained 3038 * on the mutex before the addition takes place. 3039 * 3040 * @param o the object to insert into the list 3041 * @throws ClassCastException if the object is of a type which cannot be added 3042 * to this list. 3043 * @throws IllegalArgumentException if some other aspect of the object stops 3044 * it being added to this list. 3045 * @throws UnsupportedOperationException if this ListIterator does not 3046 * support the add operation. 3047 */ 3048 public void add(T o) 3049 { 3050 synchronized (mutex) 3051 { 3052 li.add(o); 3053 } 3054 } 3055 3056 /** 3057 * Tests whether there are elements remaining in the underlying list 3058 * in the reverse direction. In other words, <code>previous()</code> 3059 * will not fail with a NoSuchElementException. A lock is obtained 3060 * on the mutex before the check takes place. 3061 * 3062 * @return <code>true</code> if the list continues in the reverse direction 3063 */ 3064 public boolean hasPrevious() 3065 { 3066 synchronized (mutex) 3067 { 3068 return li.hasPrevious(); 3069 } 3070 } 3071 3072 /** 3073 * Find the index of the element that would be returned by a call to 3074 * <code>next()</code>. If hasNext() returns <code>false</code>, this 3075 * returns the list size. A lock is obtained on the mutex before the 3076 * query takes place. 3077 * 3078 * @return the index of the element that would be returned by next() 3079 */ 3080 public int nextIndex() 3081 { 3082 synchronized (mutex) 3083 { 3084 return li.nextIndex(); 3085 } 3086 } 3087 3088 /** 3089 * Obtain the previous element from the underlying list. Repeated 3090 * calls to previous may be used to iterate backwards over the entire list, 3091 * or calls to next and previous may be used together to go forwards and 3092 * backwards. Alternating calls to next and previous will return the same 3093 * element. A lock is obtained on the mutex before the object is retrieved. 3094 * 3095 * @return the next element in the list in the reverse direction 3096 * @throws NoSuchElementException if there are no more elements 3097 */ 3098 public T previous() 3099 { 3100 synchronized (mutex) 3101 { 3102 return li.previous(); 3103 } 3104 } 3105 3106 /** 3107 * Find the index of the element that would be returned by a call to 3108 * previous. If hasPrevious() returns <code>false</code>, this returns -1. 3109 * A lock is obtained on the mutex before the query takes place. 3110 * 3111 * @return the index of the element that would be returned by previous() 3112 */ 3113 public int previousIndex() 3114 { 3115 synchronized (mutex) 3116 { 3117 return li.previousIndex(); 3118 } 3119 } 3120 3121 /** 3122 * Replace the element last returned by a call to <code>next()</code> or 3123 * <code>previous()</code> with a given object (optional operation). This 3124 * method may only be called if neither <code>add()</code> nor 3125 * <code>remove()</code> have been called since the last call to 3126 * <code>next()</code> or <code>previous</code>. A lock is obtained 3127 * on the mutex before the list is modified. 3128 * 3129 * @param o the object to replace the element with 3130 * @throws ClassCastException the object is of a type which cannot be added 3131 * to this list 3132 * @throws IllegalArgumentException some other aspect of the object stops 3133 * it being added to this list 3134 * @throws IllegalStateException if neither next or previous have been 3135 * called, or if add or remove has been called since the last call 3136 * to next or previous 3137 * @throws UnsupportedOperationException if this ListIterator does not 3138 * support the set operation 3139 */ 3140 public void set(T o) 3141 { 3142 synchronized (mutex) 3143 { 3144 li.set(o); 3145 } 3146 } 3147 } // class SynchronizedListIterator 3148 3149 /** 3150 * Returns a synchronized (thread-safe) map wrapper backed by the given 3151 * map. Notice that element access through the collection views and their 3152 * iterators are thread-safe, but if the map can be structurally modified 3153 * (adding or removing elements) then you should synchronize around the 3154 * iteration to avoid non-deterministic behavior:<br> 3155 * <pre> 3156 * Map m = Collections.synchronizedMap(new Map(...)); 3157 * ... 3158 * Set s = m.keySet(); // safe outside a synchronized block 3159 * synchronized (m) // synch on m, not s 3160 * { 3161 * Iterator i = s.iterator(); 3162 * while (i.hasNext()) 3163 * foo(i.next()); 3164 * } 3165 * </pre><p> 3166 * 3167 * The returned Map implements Serializable, but can only be serialized if 3168 * the map it wraps is likewise Serializable. 3169 * 3170 * @param m the map to wrap 3171 * @return a synchronized view of the map 3172 * @see Serializable 3173 */ 3174 public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m) 3175 { 3176 return new SynchronizedMap<K, V>(m); 3177 } 3178 3179 /** 3180 * The implementation of {@link #synchronizedMap(Map)}. This 3181 * class name is required for compatibility with Sun's JDK serializability. 3182 * 3183 * @author Eric Blake (ebb9@email.byu.edu) 3184 */ 3185 private static class SynchronizedMap<K, V> implements Map<K, V>, Serializable 3186 { 3187 /** 3188 * Compatible with JDK 1.4. 3189 */ 3190 private static final long serialVersionUID = 1978198479659022715L; 3191 3192 /** 3193 * The wrapped map. 3194 * @serial the real map 3195 */ 3196 private final Map<K, V> m; 3197 3198 /** 3199 * The object to synchronize on. When an instance is created via public 3200 * methods, it will be this; but other uses like 3201 * SynchronizedSortedMap.subMap() must specify another mutex. Package 3202 * visible for use by subclass. 3203 * @serial the lock 3204 */ 3205 final Object mutex; 3206 3207 /** 3208 * Cache the entry set. 3209 */ 3210 private transient Set<Map.Entry<K, V>> entries; 3211 3212 /** 3213 * Cache the key set. 3214 */ 3215 private transient Set<K> keys; 3216 3217 /** 3218 * Cache the value collection. 3219 */ 3220 private transient Collection<V> values; 3221 3222 /** 3223 * Wrap a given map. 3224 * @param m the map to wrap 3225 * @throws NullPointerException if m is null 3226 */ 3227 SynchronizedMap(Map<K, V> m) 3228 { 3229 this.m = m; 3230 mutex = this; 3231 if (m == null) 3232 throw new NullPointerException(); 3233 } 3234 3235 /** 3236 * Called only by trusted code to specify the mutex as well as the map. 3237 * @param sync the mutex 3238 * @param m the map 3239 */ 3240 SynchronizedMap(Object sync, Map<K, V> m) 3241 { 3242 this.m = m; 3243 mutex = sync; 3244 } 3245 3246 /** 3247 * Clears all the entries from the underlying map. A lock is obtained 3248 * on the mutex before the map is cleared. 3249 * 3250 * @throws UnsupportedOperationException if clear is not supported 3251 */ 3252 public void clear() 3253 { 3254 synchronized (mutex) 3255 { 3256 m.clear(); 3257 } 3258 } 3259 3260 /** 3261 * Returns <code>true</code> if the underlying map contains a entry for the given key. 3262 * A lock is obtained on the mutex before the map is queried. 3263 * 3264 * @param key the key to search for. 3265 * @return <code>true</code> if the underlying map contains the key. 3266 * @throws ClassCastException if the key is of an inappropriate type. 3267 * @throws NullPointerException if key is <code>null</code> but the map 3268 * does not permit null keys. 3269 */ 3270 public boolean containsKey(Object key) 3271 { 3272 synchronized (mutex) 3273 { 3274 return m.containsKey(key); 3275 } 3276 } 3277 3278 /** 3279 * Returns <code>true</code> if the underlying map contains at least one entry with the 3280 * given value. In other words, returns <code>true</code> if a value v exists where 3281 * <code>(value == null ? v == null : value.equals(v))</code>. This usually 3282 * requires linear time. A lock is obtained on the mutex before the map 3283 * is queried. 3284 * 3285 * @param value the value to search for 3286 * @return <code>true</code> if the map contains the value 3287 * @throws ClassCastException if the type of the value is not a valid type 3288 * for this map. 3289 * @throws NullPointerException if the value is null and the map doesn't 3290 * support null values. 3291 */ 3292 public boolean containsValue(Object value) 3293 { 3294 synchronized (mutex) 3295 { 3296 return m.containsValue(value); 3297 } 3298 } 3299 3300 // This is one of the ickiest cases of nesting I've ever seen. It just 3301 // means "return a SynchronizedSet, except that the iterator() method 3302 // returns an SynchronizedIterator whose next() method returns a 3303 // synchronized wrapper around its normal return value". 3304 public Set<Map.Entry<K, V>> entrySet() 3305 { 3306 // Define this here to spare some nesting. 3307 class SynchronizedMapEntry<K, V> implements Map.Entry<K, V> 3308 { 3309 final Map.Entry<K, V> e; 3310 SynchronizedMapEntry(Map.Entry<K, V> o) 3311 { 3312 e = o; 3313 } 3314 3315 /** 3316 * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code> 3317 * with the same key and value as the underlying entry. A lock is 3318 * obtained on the mutex before the comparison takes place. 3319 * 3320 * @param o The object to compare with this entry. 3321 * @return <code>true</code> if o is equivalent to the underlying map entry. 3322 */ 3323 public boolean equals(Object o) 3324 { 3325 synchronized (mutex) 3326 { 3327 return e.equals(o); 3328 } 3329 } 3330 3331 /** 3332 * Returns the key used in the underlying map entry. A lock is obtained 3333 * on the mutex before the key is retrieved. 3334 * 3335 * @return The key of the underlying map entry. 3336 */ 3337 public K getKey() 3338 { 3339 synchronized (mutex) 3340 { 3341 return e.getKey(); 3342 } 3343 } 3344 3345 /** 3346 * Returns the value used in the underlying map entry. A lock is obtained 3347 * on the mutex before the value is retrieved. 3348 * 3349 * @return The value of the underlying map entry. 3350 */ 3351 public V getValue() 3352 { 3353 synchronized (mutex) 3354 { 3355 return e.getValue(); 3356 } 3357 } 3358 3359 /** 3360 * Computes the hash code for the underlying map entry. 3361 * This computation is described in the documentation for the 3362 * <code>Map</code> interface. A lock is obtained on the mutex 3363 * before the underlying map is accessed. 3364 * 3365 * @return The hash code of the underlying map entry. 3366 * @see Map#hashCode() 3367 */ 3368 public int hashCode() 3369 { 3370 synchronized (mutex) 3371 { 3372 return e.hashCode(); 3373 } 3374 } 3375 3376 /** 3377 * Replaces the value in the underlying map entry with the specified 3378 * object (optional operation). A lock is obtained on the mutex 3379 * before the map is altered. The map entry, in turn, will alter 3380 * the underlying map object. The operation is undefined if the 3381 * <code>remove()</code> method of the iterator has been called 3382 * beforehand. 3383 * 3384 * @param value the new value to store 3385 * @return the old value 3386 * @throws UnsupportedOperationException if the operation is not supported. 3387 * @throws ClassCastException if the value is of the wrong type. 3388 * @throws IllegalArgumentException if something about the value 3389 * prevents it from existing in this map. 3390 * @throws NullPointerException if the map forbids null values. 3391 */ 3392 public V setValue(V value) 3393 { 3394 synchronized (mutex) 3395 { 3396 return e.setValue(value); 3397 } 3398 } 3399 3400 /** 3401 * Returns a textual representation of the underlying map entry. 3402 * A lock is obtained on the mutex before the entry is accessed. 3403 * 3404 * @return The contents of the map entry in <code>String</code> form. 3405 */ 3406 public String toString() 3407 { 3408 synchronized (mutex) 3409 { 3410 return e.toString(); 3411 } 3412 } 3413 } // class SynchronizedMapEntry 3414 3415 // Now the actual code. 3416 if (entries == null) 3417 synchronized (mutex) 3418 { 3419 entries = new SynchronizedSet<Map.Entry<K, V>>(mutex, m.entrySet()) 3420 { 3421 /** 3422 * Returns an iterator over the set. The iterator has no specific order, 3423 * unless further specified. A lock is obtained on the set's mutex 3424 * before the iterator is created. The created iterator is also 3425 * thread-safe. 3426 * 3427 * @return A synchronized set iterator. 3428 */ 3429 public Iterator<Map.Entry<K, V>> iterator() 3430 { 3431 synchronized (super.mutex) 3432 { 3433 return new SynchronizedIterator<Map.Entry<K, V>>(super.mutex, 3434 c.iterator()) 3435 { 3436 /** 3437 * Retrieves the next map entry from the iterator. 3438 * A lock is obtained on the iterator's mutex before 3439 * the entry is created. The new map entry is enclosed in 3440 * a thread-safe wrapper. 3441 * 3442 * @return A synchronized map entry. 3443 */ 3444 public Map.Entry<K, V> next() 3445 { 3446 synchronized (super.mutex) 3447 { 3448 return new SynchronizedMapEntry<K, V>(super.next()); 3449 } 3450 } 3451 }; 3452 } 3453 } 3454 }; 3455 } 3456 return entries; 3457 } 3458 3459 /** 3460 * Returns <code>true</code> if the object, o, is also an instance 3461 * of <code>Map</code> and contains an equivalent 3462 * entry set to that of the underlying map. A lock 3463 * is obtained on the mutex before the objects are 3464 * compared. 3465 * 3466 * @param o The object to compare. 3467 * @return <code>true</code> if o and the underlying map are equivalent. 3468 */ 3469 public boolean equals(Object o) 3470 { 3471 synchronized (mutex) 3472 { 3473 return m.equals(o); 3474 } 3475 } 3476 3477 /** 3478 * Returns the value associated with the given key, or null 3479 * if no such mapping exists. An ambiguity exists with maps 3480 * that accept null values as a return value of null could 3481 * be due to a non-existent mapping or simply a null value 3482 * for that key. To resolve this, <code>containsKey</code> 3483 * should be used. A lock is obtained on the mutex before 3484 * the value is retrieved from the underlying map. 3485 * 3486 * @param key The key of the required mapping. 3487 * @return The value associated with the given key, or 3488 * null if no such mapping exists. 3489 * @throws ClassCastException if the key is an inappropriate type. 3490 * @throws NullPointerException if this map does not accept null keys. 3491 */ 3492 public V get(Object key) 3493 { 3494 synchronized (mutex) 3495 { 3496 return m.get(key); 3497 } 3498 } 3499 3500 /** 3501 * Calculates the hash code of the underlying map as the 3502 * sum of the hash codes of all entries. A lock is obtained 3503 * on the mutex before the hash code is computed. 3504 * 3505 * @return The hash code of the underlying map. 3506 */ 3507 public int hashCode() 3508 { 3509 synchronized (mutex) 3510 { 3511 return m.hashCode(); 3512 } 3513 } 3514 3515 /** 3516 * Returns <code>true</code> if the underlying map contains no entries. 3517 * A lock is obtained on the mutex before the map is examined. 3518 * 3519 * @return <code>true</code> if the map is empty. 3520 */ 3521 public boolean isEmpty() 3522 { 3523 synchronized (mutex) 3524 { 3525 return m.isEmpty(); 3526 } 3527 } 3528 3529 /** 3530 * Returns a thread-safe set view of the keys in the underlying map. The 3531 * set is backed by the map, so that changes in one show up in the other. 3532 * Modifications made while an iterator is in progress cause undefined 3533 * behavior. If the set supports removal, these methods remove the 3534 * underlying mapping from the map: <code>Iterator.remove</code>, 3535 * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, 3536 * and <code>clear</code>. Element addition, via <code>add</code> or 3537 * <code>addAll</code>, is not supported via this set. A lock is obtained 3538 * on the mutex before the set is created. 3539 * 3540 * @return A synchronized set containing the keys of the underlying map. 3541 */ 3542 public Set<K> keySet() 3543 { 3544 if (keys == null) 3545 synchronized (mutex) 3546 { 3547 keys = new SynchronizedSet<K>(mutex, m.keySet()); 3548 } 3549 return keys; 3550 } 3551 3552 /** 3553 * Associates the given key to the given value (optional operation). If the 3554 * underlying map already contains the key, its value is replaced. Be aware 3555 * that in a map that permits <code>null</code> values, a null return does not 3556 * always imply that the mapping was created. A lock is obtained on the mutex 3557 * before the modification is made. 3558 * 3559 * @param key the key to map. 3560 * @param value the value to be mapped. 3561 * @return the previous value of the key, or null if there was no mapping 3562 * @throws UnsupportedOperationException if the operation is not supported 3563 * @throws ClassCastException if the key or value is of the wrong type 3564 * @throws IllegalArgumentException if something about this key or value 3565 * prevents it from existing in this map 3566 * @throws NullPointerException if either the key or the value is null, 3567 * and the map forbids null keys or values 3568 * @see #containsKey(Object) 3569 */ 3570 public V put(K key, V value) 3571 { 3572 synchronized (mutex) 3573 { 3574 return m.put(key, value); 3575 } 3576 } 3577 3578 /** 3579 * Copies all entries of the given map to the underlying one (optional 3580 * operation). If the map already contains a key, its value is replaced. 3581 * A lock is obtained on the mutex before the operation proceeds. 3582 * 3583 * @param map the mapping to load into this map 3584 * @throws UnsupportedOperationException if the operation is not supported 3585 * @throws ClassCastException if a key or value is of the wrong type 3586 * @throws IllegalArgumentException if something about a key or value 3587 * prevents it from existing in this map 3588 * @throws NullPointerException if the map forbids null keys or values, or 3589 * if <code>m</code> is null. 3590 * @see #put(Object, Object) 3591 */ 3592 public void putAll(Map<? extends K, ? extends V> map) 3593 { 3594 synchronized (mutex) 3595 { 3596 m.putAll(map); 3597 } 3598 } 3599 3600 /** 3601 * Removes the mapping for the key, o, if present (optional operation). If 3602 * the key is not present, this returns null. Note that maps which permit 3603 * null values may also return null if the key was removed. A prior 3604 * <code>containsKey()</code> check is required to avoid this ambiguity. 3605 * Before the mapping is removed, a lock is obtained on the mutex. 3606 * 3607 * @param o the key to remove 3608 * @return the value the key mapped to, or null if not present 3609 * @throws UnsupportedOperationException if deletion is unsupported 3610 * @throws NullPointerException if the key is null and this map doesn't 3611 * support null keys. 3612 * @throws ClassCastException if the type of the key is not a valid type 3613 * for this map. 3614 */ 3615 public V remove(Object o) 3616 { 3617 synchronized (mutex) 3618 { 3619 return m.remove(o); 3620 } 3621 } 3622 3623 /** 3624 * Retrieves the size of the underlying map. A lock 3625 * is obtained on the mutex before access takes place. 3626 * Maps with a size greater than <code>Integer.MAX_VALUE</code> 3627 * return <code>Integer.MAX_VALUE</code> instead. 3628 * 3629 * @return The size of the underlying map. 3630 */ 3631 public int size() 3632 { 3633 synchronized (mutex) 3634 { 3635 return m.size(); 3636 } 3637 } 3638 3639 /** 3640 * Returns a textual representation of the underlying 3641 * map. A lock is obtained on the mutex before the map 3642 * is accessed. 3643 * 3644 * @return The map in <code>String</code> form. 3645 */ 3646 public String toString() 3647 { 3648 synchronized (mutex) 3649 { 3650 return m.toString(); 3651 } 3652 } 3653 3654 /** 3655 * Returns a synchronized collection view of the values in the underlying 3656 * map. The collection is backed by the map, so that changes in one show up in 3657 * the other. Modifications made while an iterator is in progress cause 3658 * undefined behavior. If the collection supports removal, these methods 3659 * remove the underlying mapping from the map: <code>Iterator.remove</code>, 3660 * <code>Collection.remove</code>, <code>removeAll</code>, 3661 * <code>retainAll</code>, and <code>clear</code>. Element addition, via 3662 * <code>add</code> or <code>addAll</code>, is not supported via this 3663 * collection. A lock is obtained on the mutex before the collection 3664 * is created. 3665 * 3666 * @return the collection of all values in the underlying map. 3667 */ 3668 public Collection<V> values() 3669 { 3670 if (values == null) 3671 synchronized (mutex) 3672 { 3673 values = new SynchronizedCollection<V>(mutex, m.values()); 3674 } 3675 return values; 3676 } 3677 } // class SynchronizedMap 3678 3679 /** 3680 * Returns a synchronized (thread-safe) set wrapper backed by the given 3681 * set. Notice that element access through the iterator is thread-safe, but 3682 * if the set can be structurally modified (adding or removing elements) 3683 * then you should synchronize around the iteration to avoid 3684 * non-deterministic behavior:<br> 3685 * <pre> 3686 * Set s = Collections.synchronizedSet(new Set(...)); 3687 * ... 3688 * synchronized (s) 3689 * { 3690 * Iterator i = s.iterator(); 3691 * while (i.hasNext()) 3692 * foo(i.next()); 3693 * } 3694 * </pre><p> 3695 * 3696 * The returned Set implements Serializable, but can only be serialized if 3697 * the set it wraps is likewise Serializable. 3698 * 3699 * @param s the set to wrap 3700 * @return a synchronized view of the set 3701 * @see Serializable 3702 */ 3703 public static <T> Set<T> synchronizedSet(Set<T> s) 3704 { 3705 return new SynchronizedSet<T>(s); 3706 } 3707 3708 /** 3709 * The implementation of {@link #synchronizedSet(Set)}. This class 3710 * name is required for compatibility with Sun's JDK serializability. 3711 * Package visible, so that sets such as Hashtable.keySet() 3712 * can specify which object to synchronize on. 3713 * 3714 * @author Eric Blake (ebb9@email.byu.edu) 3715 */ 3716 static class SynchronizedSet<T> extends SynchronizedCollection<T> 3717 implements Set<T> 3718 { 3719 /** 3720 * Compatible with JDK 1.4. 3721 */ 3722 private static final long serialVersionUID = 487447009682186044L; 3723 3724 /** 3725 * Wrap a given set. 3726 * @param s the set to wrap 3727 * @throws NullPointerException if s is null 3728 */ 3729 SynchronizedSet(Set<T> s) 3730 { 3731 super(s); 3732 } 3733 3734 /** 3735 * Called only by trusted code to specify the mutex as well as the set. 3736 * @param sync the mutex 3737 * @param s the set 3738 */ 3739 SynchronizedSet(Object sync, Set<T> s) 3740 { 3741 super(sync, s); 3742 } 3743 3744 /** 3745 * Returns <code>true</code> if the object, o, is a <code>Set</code> 3746 * of the same size as the underlying set, and contains 3747 * each element, e, which occurs in the underlying set. 3748 * A lock is obtained on the mutex before the comparison 3749 * takes place. 3750 * 3751 * @param o The object to compare against. 3752 * @return <code>true</code> if o is an equivalent set. 3753 */ 3754 public boolean equals(Object o) 3755 { 3756 synchronized (mutex) 3757 { 3758 return c.equals(o); 3759 } 3760 } 3761 3762 /** 3763 * Computes the hash code for the underlying set as the 3764 * sum of the hash code of all elements within the set. 3765 * A lock is obtained on the mutex before the computation 3766 * occurs. 3767 * 3768 * @return The hash code for the underlying set. 3769 */ 3770 public int hashCode() 3771 { 3772 synchronized (mutex) 3773 { 3774 return c.hashCode(); 3775 } 3776 } 3777 } // class SynchronizedSet 3778 3779 /** 3780 * Returns a synchronized (thread-safe) sorted map wrapper backed by the 3781 * given map. Notice that element access through the collection views, 3782 * subviews, and their iterators are thread-safe, but if the map can be 3783 * structurally modified (adding or removing elements) then you should 3784 * synchronize around the iteration to avoid non-deterministic behavior:<br> 3785 * <pre> 3786 * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...)); 3787 * ... 3788 * Set s = m.keySet(); // safe outside a synchronized block 3789 * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block 3790 * Set s2 = m2.keySet(); // safe outside a synchronized block 3791 * synchronized (m) // synch on m, not m2, s or s2 3792 * { 3793 * Iterator i = s.iterator(); 3794 * while (i.hasNext()) 3795 * foo(i.next()); 3796 * i = s2.iterator(); 3797 * while (i.hasNext()) 3798 * bar(i.next()); 3799 * } 3800 * </pre><p> 3801 * 3802 * The returned SortedMap implements Serializable, but can only be 3803 * serialized if the map it wraps is likewise Serializable. 3804 * 3805 * @param m the sorted map to wrap 3806 * @return a synchronized view of the sorted map 3807 * @see Serializable 3808 */ 3809 public static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> m) 3810 { 3811 return new SynchronizedSortedMap<K, V>(m); 3812 } 3813 3814 /** 3815 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This 3816 * class name is required for compatibility with Sun's JDK serializability. 3817 * 3818 * @author Eric Blake (ebb9@email.byu.edu) 3819 */ 3820 private static final class SynchronizedSortedMap<K, V> 3821 extends SynchronizedMap<K, V> 3822 implements SortedMap<K, V> 3823 { 3824 /** 3825 * Compatible with JDK 1.4. 3826 */ 3827 private static final long serialVersionUID = -8798146769416483793L; 3828 3829 /** 3830 * The wrapped map; stored both here and in the superclass to avoid 3831 * excessive casting. 3832 * @serial the wrapped map 3833 */ 3834 private final SortedMap<K, V> sm; 3835 3836 /** 3837 * Wrap a given map. 3838 * @param sm the map to wrap 3839 * @throws NullPointerException if sm is null 3840 */ 3841 SynchronizedSortedMap(SortedMap<K, V> sm) 3842 { 3843 super(sm); 3844 this.sm = sm; 3845 } 3846 3847 /** 3848 * Called only by trusted code to specify the mutex as well as the map. 3849 * @param sync the mutex 3850 * @param sm the map 3851 */ 3852 SynchronizedSortedMap(Object sync, SortedMap<K, V> sm) 3853 { 3854 super(sync, sm); 3855 this.sm = sm; 3856 } 3857 3858 /** 3859 * Returns the comparator used in sorting the underlying map, or null if 3860 * it is the keys' natural ordering. A lock is obtained on the mutex 3861 * before the comparator is retrieved. 3862 * 3863 * @return the sorting comparator. 3864 */ 3865 public Comparator<? super K> comparator() 3866 { 3867 synchronized (mutex) 3868 { 3869 return sm.comparator(); 3870 } 3871 } 3872 3873 /** 3874 * Returns the first, lowest sorted, key from the underlying map. 3875 * A lock is obtained on the mutex before the map is accessed. 3876 * 3877 * @return the first key. 3878 * @throws NoSuchElementException if this map is empty. 3879 */ 3880 public K firstKey() 3881 { 3882 synchronized (mutex) 3883 { 3884 return sm.firstKey(); 3885 } 3886 } 3887 3888 /** 3889 * Returns a submap containing the keys from the first 3890 * key (as returned by <code>firstKey()</code>) to 3891 * the key before that specified. The submap supports all 3892 * operations supported by the underlying map and all actions 3893 * taking place on the submap are also reflected in the underlying 3894 * map. A lock is obtained on the mutex prior to submap creation. 3895 * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>. 3896 * The submap retains the thread-safe status of this map. 3897 * 3898 * @param toKey the exclusive upper range of the submap. 3899 * @return a submap from <code>firstKey()</code> to the 3900 * the key preceding toKey. 3901 * @throws ClassCastException if toKey is not comparable to the underlying 3902 * map's contents. 3903 * @throws IllegalArgumentException if toKey is outside the map's range. 3904 * @throws NullPointerException if toKey is null. but the map does not allow 3905 * null keys. 3906 */ 3907 public SortedMap<K, V> headMap(K toKey) 3908 { 3909 synchronized (mutex) 3910 { 3911 return new SynchronizedSortedMap<K, V>(mutex, sm.headMap(toKey)); 3912 } 3913 } 3914 3915 /** 3916 * Returns the last, highest sorted, key from the underlying map. 3917 * A lock is obtained on the mutex before the map is accessed. 3918 * 3919 * @return the last key. 3920 * @throws NoSuchElementException if this map is empty. 3921 */ 3922 public K lastKey() 3923 { 3924 synchronized (mutex) 3925 { 3926 return sm.lastKey(); 3927 } 3928 } 3929 3930 /** 3931 * Returns a submap containing the keys from fromKey to 3932 * the key before toKey. The submap supports all 3933 * operations supported by the underlying map and all actions 3934 * taking place on the submap are also reflected in the underlying 3935 * map. A lock is obtained on the mutex prior to submap creation. 3936 * The submap retains the thread-safe status of this map. 3937 * 3938 * @param fromKey the inclusive lower range of the submap. 3939 * @param toKey the exclusive upper range of the submap. 3940 * @return a submap from fromKey to the key preceding toKey. 3941 * @throws ClassCastException if fromKey or toKey is not comparable 3942 * to the underlying map's contents. 3943 * @throws IllegalArgumentException if fromKey or toKey is outside the map's 3944 * range. 3945 * @throws NullPointerException if fromKey or toKey is null. but the map does 3946 * not allow null keys. 3947 */ 3948 public SortedMap<K, V> subMap(K fromKey, K toKey) 3949 { 3950 synchronized (mutex) 3951 { 3952 return new SynchronizedSortedMap<K, V>(mutex, 3953 sm.subMap(fromKey, toKey)); 3954 } 3955 } 3956 3957 /** 3958 * Returns a submap containing all the keys from fromKey onwards. 3959 * The submap supports all operations supported by the underlying 3960 * map and all actions taking place on the submap are also reflected 3961 * in the underlying map. A lock is obtained on the mutex prior to 3962 * submap creation. The submap retains the thread-safe status of 3963 * this map. 3964 * 3965 * @param fromKey the inclusive lower range of the submap. 3966 * @return a submap from fromKey to <code>lastKey()</code>. 3967 * @throws ClassCastException if fromKey is not comparable to the underlying 3968 * map's contents. 3969 * @throws IllegalArgumentException if fromKey is outside the map's range. 3970 * @throws NullPointerException if fromKey is null. but the map does not allow 3971 * null keys. 3972 */ 3973 public SortedMap<K, V> tailMap(K fromKey) 3974 { 3975 synchronized (mutex) 3976 { 3977 return new SynchronizedSortedMap<K, V>(mutex, sm.tailMap(fromKey)); 3978 } 3979 } 3980 } // class SynchronizedSortedMap 3981 3982 /** 3983 * Returns a synchronized (thread-safe) sorted set wrapper backed by the 3984 * given set. Notice that element access through the iterator and through 3985 * subviews are thread-safe, but if the set can be structurally modified 3986 * (adding or removing elements) then you should synchronize around the 3987 * iteration to avoid non-deterministic behavior:<br> 3988 * <pre> 3989 * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...)); 3990 * ... 3991 * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block 3992 * synchronized (s) // synch on s, not s2 3993 * { 3994 * Iterator i = s2.iterator(); 3995 * while (i.hasNext()) 3996 * foo(i.next()); 3997 * } 3998 * </pre><p> 3999 * 4000 * The returned SortedSet implements Serializable, but can only be 4001 * serialized if the set it wraps is likewise Serializable. 4002 * 4003 * @param s the sorted set to wrap 4004 * @return a synchronized view of the sorted set 4005 * @see Serializable 4006 */ 4007 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) 4008 { 4009 return new SynchronizedSortedSet<T>(s); 4010 } 4011 4012 /** 4013 * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This 4014 * class name is required for compatibility with Sun's JDK serializability. 4015 * 4016 * @author Eric Blake (ebb9@email.byu.edu) 4017 */ 4018 private static final class SynchronizedSortedSet<T> 4019 extends SynchronizedSet<T> 4020 implements SortedSet<T> 4021 { 4022 /** 4023 * Compatible with JDK 1.4. 4024 */ 4025 private static final long serialVersionUID = 8695801310862127406L; 4026 4027 /** 4028 * The wrapped set; stored both here and in the superclass to avoid 4029 * excessive casting. 4030 * @serial the wrapped set 4031 */ 4032 private final SortedSet<T> ss; 4033 4034 /** 4035 * Wrap a given set. 4036 * @param ss the set to wrap 4037 * @throws NullPointerException if ss is null 4038 */ 4039 SynchronizedSortedSet(SortedSet<T> ss) 4040 { 4041 super(ss); 4042 this.ss = ss; 4043 } 4044 4045 /** 4046 * Called only by trusted code to specify the mutex as well as the set. 4047 * @param sync the mutex 4048 * @param ss the set 4049 */ 4050 SynchronizedSortedSet(Object sync, SortedSet<T> ss) 4051 { 4052 super(sync, ss); 4053 this.ss = ss; 4054 } 4055 4056 /** 4057 * Returns the comparator used in sorting the underlying set, or null if 4058 * it is the elements' natural ordering. A lock is obtained on the mutex 4059 * before the comparator is retrieved. 4060 * 4061 * @return the sorting comparator. 4062 */ 4063 public Comparator<? super T> comparator() 4064 { 4065 synchronized (mutex) 4066 { 4067 return ss.comparator(); 4068 } 4069 } 4070 4071 /** 4072 * Returns the first, lowest sorted, element from the underlying set. 4073 * A lock is obtained on the mutex before the set is accessed. 4074 * 4075 * @return the first element. 4076 * @throws NoSuchElementException if this set is empty. 4077 */ 4078 public T first() 4079 { 4080 synchronized (mutex) 4081 { 4082 return ss.first(); 4083 } 4084 } 4085 4086 /** 4087 * Returns a subset containing the element from the first 4088 * element (as returned by <code>first()</code>) to 4089 * the element before that specified. The subset supports all 4090 * operations supported by the underlying set and all actions 4091 * taking place on the subset are also reflected in the underlying 4092 * set. A lock is obtained on the mutex prior to subset creation. 4093 * This operation is equivalent to <code>subSet(first(), toElement)</code>. 4094 * The subset retains the thread-safe status of this set. 4095 * 4096 * @param toElement the exclusive upper range of the subset. 4097 * @return a subset from <code>first()</code> to the 4098 * the element preceding toElement. 4099 * @throws ClassCastException if toElement is not comparable to the underlying 4100 * set's contents. 4101 * @throws IllegalArgumentException if toElement is outside the set's range. 4102 * @throws NullPointerException if toElement is null. but the set does not allow 4103 * null elements. 4104 */ 4105 public SortedSet<T> headSet(T toElement) 4106 { 4107 synchronized (mutex) 4108 { 4109 return new SynchronizedSortedSet<T>(mutex, ss.headSet(toElement)); 4110 } 4111 } 4112 4113 /** 4114 * Returns the last, highest sorted, element from the underlying set. 4115 * A lock is obtained on the mutex before the set is accessed. 4116 * 4117 * @return the last element. 4118 * @throws NoSuchElementException if this set is empty. 4119 */ 4120 public T last() 4121 { 4122 synchronized (mutex) 4123 { 4124 return ss.last(); 4125 } 4126 } 4127 4128 /** 4129 * Returns a subset containing the elements from fromElement to 4130 * the element before toElement. The subset supports all 4131 * operations supported by the underlying set and all actions 4132 * taking place on the subset are also reflected in the underlying 4133 * set. A lock is obtained on the mutex prior to subset creation. 4134 * The subset retains the thread-safe status of this set. 4135 * 4136 * @param fromElement the inclusive lower range of the subset. 4137 * @param toElement the exclusive upper range of the subset. 4138 * @return a subset from fromElement to the element preceding toElement. 4139 * @throws ClassCastException if fromElement or toElement is not comparable 4140 * to the underlying set's contents. 4141 * @throws IllegalArgumentException if fromElement or toElement is outside the set's 4142 * range. 4143 * @throws NullPointerException if fromElement or toElement is null. but the set does 4144 * not allow null elements. 4145 */ 4146 public SortedSet<T> subSet(T fromElement, T toElement) 4147 { 4148 synchronized (mutex) 4149 { 4150 return new SynchronizedSortedSet<T>(mutex, 4151 ss.subSet(fromElement, 4152 toElement)); 4153 } 4154 } 4155 4156 /** 4157 * Returns a subset containing all the elements from fromElement onwards. 4158 * The subset supports all operations supported by the underlying 4159 * set and all actions taking place on the subset are also reflected 4160 * in the underlying set. A lock is obtained on the mutex prior to 4161 * subset creation. The subset retains the thread-safe status of 4162 * this set. 4163 * 4164 * @param fromElement the inclusive lower range of the subset. 4165 * @return a subset from fromElement to <code>last()</code>. 4166 * @throws ClassCastException if fromElement is not comparable to the underlying 4167 * set's contents. 4168 * @throws IllegalArgumentException if fromElement is outside the set's range. 4169 * @throws NullPointerException if fromElement is null. but the set does not allow 4170 * null elements. 4171 */ 4172 public SortedSet<T> tailSet(T fromElement) 4173 { 4174 synchronized (mutex) 4175 { 4176 return new SynchronizedSortedSet<T>(mutex, ss.tailSet(fromElement)); 4177 } 4178 } 4179 } // class SynchronizedSortedSet 4180 4181 4182 /** 4183 * Returns an unmodifiable view of the given collection. This allows 4184 * "read-only" access, although changes in the backing collection show up 4185 * in this view. Attempts to modify the collection directly or via iterators 4186 * will fail with {@link UnsupportedOperationException}. Although this view 4187 * prevents changes to the structure of the collection and its elements, the values 4188 * referenced by the objects in the collection can still be modified. 4189 * <p> 4190 * 4191 * Since the collection might be a List or a Set, and those have incompatible 4192 * equals and hashCode requirements, this relies on Object's implementation 4193 * rather than passing those calls on to the wrapped collection. The returned 4194 * Collection implements Serializable, but can only be serialized if 4195 * the collection it wraps is likewise Serializable. 4196 * 4197 * @param c the collection to wrap 4198 * @return a read-only view of the collection 4199 * @see Serializable 4200 */ 4201 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) 4202 { 4203 return new UnmodifiableCollection<T>(c); 4204 } 4205 4206 /** 4207 * The implementation of {@link #unmodifiableCollection(Collection)}. This 4208 * class name is required for compatibility with Sun's JDK serializability. 4209 * 4210 * @author Eric Blake (ebb9@email.byu.edu) 4211 */ 4212 private static class UnmodifiableCollection<T> 4213 implements Collection<T>, Serializable 4214 { 4215 /** 4216 * Compatible with JDK 1.4. 4217 */ 4218 private static final long serialVersionUID = 1820017752578914078L; 4219 4220 /** 4221 * The wrapped collection. Package visible for use by subclasses. 4222 * @serial the real collection 4223 */ 4224 final Collection<? extends T> c; 4225 4226 /** 4227 * Wrap a given collection. 4228 * @param c the collection to wrap 4229 * @throws NullPointerException if c is null 4230 */ 4231 UnmodifiableCollection(Collection<? extends T> c) 4232 { 4233 this.c = c; 4234 if (c == null) 4235 throw new NullPointerException(); 4236 } 4237 4238 /** 4239 * Blocks the addition of elements to the underlying collection. 4240 * This method never returns, throwing an exception instead. 4241 * 4242 * @param o the object to add. 4243 * @return <code>true</code> if the collection was modified as a result of this action. 4244 * @throws UnsupportedOperationException as an unmodifiable collection does not 4245 * support the add operation. 4246 */ 4247 public boolean add(T o) 4248 { 4249 throw new UnsupportedOperationException(); 4250 } 4251 4252 /** 4253 * Blocks the addition of a collection of elements to the underlying 4254 * collection. This method never returns, throwing an exception instead. 4255 * 4256 * @param c the collection to add. 4257 * @return <code>true</code> if the collection was modified as a result of this action. 4258 * @throws UnsupportedOperationException as an unmodifiable collection does not 4259 * support the <code>addAll</code> operation. 4260 */ 4261 public boolean addAll(Collection<? extends T> c) 4262 { 4263 throw new UnsupportedOperationException(); 4264 } 4265 4266 /** 4267 * Blocks the clearing of the underlying collection. This method never 4268 * returns, throwing an exception instead. 4269 * 4270 * @throws UnsupportedOperationException as an unmodifiable collection does 4271 * not support the <code>clear()</code> operation. 4272 */ 4273 public void clear() 4274 { 4275 throw new UnsupportedOperationException(); 4276 } 4277 4278 /** 4279 * Test whether the underlying collection contains a given object as one of its 4280 * elements. 4281 * 4282 * @param o the element to look for. 4283 * @return <code>true</code> if the underlying collection contains at least 4284 * one element e such that 4285 * <code>o == null ? e == null : o.equals(e)</code>. 4286 * @throws ClassCastException if the type of o is not a valid type for the 4287 * underlying collection. 4288 * @throws NullPointerException if o is null and the underlying collection 4289 * doesn't support null values. 4290 */ 4291 public boolean contains(Object o) 4292 { 4293 return c.contains(o); 4294 } 4295 4296 /** 4297 * Test whether the underlying collection contains every element in a given 4298 * collection. 4299 * 4300 * @param c1 the collection to test for. 4301 * @return <code>true</code> if for every element o in c, contains(o) would 4302 * return <code>true</code>. 4303 * @throws ClassCastException if the type of any element in c is not a valid 4304 * type for the underlying collection. 4305 * @throws NullPointerException if some element of c is null and the underlying 4306 * collection does not support null values. 4307 * @throws NullPointerException if c itself is null. 4308 */ 4309 public boolean containsAll(Collection<?> c1) 4310 { 4311 return c.containsAll(c1); 4312 } 4313 4314 /** 4315 * Tests whether the underlying collection is empty, that is, 4316 * if size() == 0. 4317 * 4318 * @return <code>true</code> if this collection contains no elements. 4319 */ 4320 public boolean isEmpty() 4321 { 4322 return c.isEmpty(); 4323 } 4324 4325 /** 4326 * Obtain an Iterator over the underlying collection, which maintains 4327 * its unmodifiable nature. 4328 * 4329 * @return an UnmodifiableIterator over the elements of the underlying 4330 * collection, in any order. 4331 */ 4332 public Iterator<T> iterator() 4333 { 4334 return new UnmodifiableIterator<T>(c.iterator()); 4335 } 4336 4337 /** 4338 * Blocks the removal of an object from the underlying collection. 4339 * This method never returns, throwing an exception instead. 4340 * 4341 * @param o The object to remove. 4342 * @return <code>true</code> if the object was removed (i.e. the underlying 4343 * collection returned 1 or more instances of o). 4344 * @throws UnsupportedOperationException as an unmodifiable collection 4345 * does not support the <code>remove()</code> operation. 4346 */ 4347 public boolean remove(Object o) 4348 { 4349 throw new UnsupportedOperationException(); 4350 } 4351 4352 /** 4353 * Blocks the removal of a collection of objects from the underlying 4354 * collection. This method never returns, throwing an exception 4355 * instead. 4356 * 4357 * @param c The collection of objects to remove. 4358 * @return <code>true</code> if the collection was modified. 4359 * @throws UnsupportedOperationException as an unmodifiable collection 4360 * does not support the <code>removeAll()</code> operation. 4361 */ 4362 public boolean removeAll(Collection<?> c) 4363 { 4364 throw new UnsupportedOperationException(); 4365 } 4366 4367 /** 4368 * Blocks the removal of all elements from the underlying collection, 4369 * except those in the supplied collection. This method never returns, 4370 * throwing an exception instead. 4371 * 4372 * @param c The collection of objects to retain. 4373 * @return <code>true</code> if the collection was modified. 4374 * @throws UnsupportedOperationException as an unmodifiable collection 4375 * does not support the <code>retainAll()</code> operation. 4376 */ 4377 public boolean retainAll(Collection<?> c) 4378 { 4379 throw new UnsupportedOperationException(); 4380 } 4381 4382 /** 4383 * Retrieves the number of elements in the underlying collection. 4384 * 4385 * @return the number of elements in the collection. 4386 */ 4387 public int size() 4388 { 4389 return c.size(); 4390 } 4391 4392 /** 4393 * Copy the current contents of the underlying collection into an array. 4394 * 4395 * @return an array of type Object[] with a length equal to the size of the 4396 * underlying collection and containing the elements currently in 4397 * the underlying collection, in any order. 4398 */ 4399 public Object[] toArray() 4400 { 4401 return c.toArray(); 4402 } 4403 4404 /** 4405 * Copy the current contents of the underlying collection into an array. If 4406 * the array passed as an argument has length less than the size of the 4407 * underlying collection, an array of the same run-time type as a, with a length 4408 * equal to the size of the underlying collection, is allocated using reflection. 4409 * Otherwise, a itself is used. The elements of the underlying collection are 4410 * copied into it, and if there is space in the array, the following element is 4411 * set to null. The resultant array is returned. 4412 * Note: The fact that the following element is set to null is only useful 4413 * if it is known that this collection does not contain any null elements. 4414 * 4415 * @param a the array to copy this collection into. 4416 * @return an array containing the elements currently in the underlying 4417 * collection, in any order. 4418 * @throws ArrayStoreException if the type of any element of the 4419 * collection is not a subtype of the element type of a. 4420 */ 4421 public <S> S[] toArray(S[] a) 4422 { 4423 return c.toArray(a); 4424 } 4425 4426 /** 4427 * A textual representation of the unmodifiable collection. 4428 * 4429 * @return The unmodifiable collection in the form of a <code>String</code>. 4430 */ 4431 public String toString() 4432 { 4433 return c.toString(); 4434 } 4435 } // class UnmodifiableCollection 4436 4437 /** 4438 * The implementation of the various iterator methods in the 4439 * unmodifiable classes. 4440 * 4441 * @author Eric Blake (ebb9@email.byu.edu) 4442 */ 4443 private static class UnmodifiableIterator<T> implements Iterator<T> 4444 { 4445 /** 4446 * The wrapped iterator. 4447 */ 4448 private final Iterator<? extends T> i; 4449 4450 /** 4451 * Only trusted code creates a wrapper. 4452 * @param i the wrapped iterator 4453 */ 4454 UnmodifiableIterator(Iterator<? extends T> i) 4455 { 4456 this.i = i; 4457 } 4458 4459 /** 4460 * Obtains the next element in the underlying collection. 4461 * 4462 * @return the next element in the collection. 4463 * @throws NoSuchElementException if there are no more elements. 4464 */ 4465 public T next() 4466 { 4467 return i.next(); 4468 } 4469 4470 /** 4471 * Tests whether there are still elements to be retrieved from the 4472 * underlying collection by <code>next()</code>. When this method 4473 * returns <code>true</code>, an exception will not be thrown on calling 4474 * <code>next()</code>. 4475 * 4476 * @return <code>true</code> if there is at least one more element in the underlying 4477 * collection. 4478 */ 4479 public boolean hasNext() 4480 { 4481 return i.hasNext(); 4482 } 4483 4484 /** 4485 * Blocks the removal of elements from the underlying collection by the 4486 * iterator. 4487 * 4488 * @throws UnsupportedOperationException as an unmodifiable collection 4489 * does not support the removal of elements by its iterator. 4490 */ 4491 public void remove() 4492 { 4493 throw new UnsupportedOperationException(); 4494 } 4495 } // class UnmodifiableIterator 4496 4497 /** 4498 * Returns an unmodifiable view of the given list. This allows 4499 * "read-only" access, although changes in the backing list show up 4500 * in this view. Attempts to modify the list directly, via iterators, or 4501 * via sublists, will fail with {@link UnsupportedOperationException}. 4502 * Although this view prevents changes to the structure of the list and 4503 * its elements, the values referenced by the objects in the list can 4504 * still be modified. 4505 * <p> 4506 * 4507 * The returned List implements Serializable, but can only be serialized if 4508 * the list it wraps is likewise Serializable. In addition, if the wrapped 4509 * list implements RandomAccess, this does too. 4510 * 4511 * @param l the list to wrap 4512 * @return a read-only view of the list 4513 * @see Serializable 4514 * @see RandomAccess 4515 */ 4516 public static <T> List<T> unmodifiableList(List<? extends T> l) 4517 { 4518 if (l instanceof RandomAccess) 4519 return new UnmodifiableRandomAccessList<T>(l); 4520 return new UnmodifiableList<T>(l); 4521 } 4522 4523 /** 4524 * The implementation of {@link #unmodifiableList(List)} for sequential 4525 * lists. This class name is required for compatibility with Sun's JDK 4526 * serializability. 4527 * 4528 * @author Eric Blake (ebb9@email.byu.edu) 4529 */ 4530 private static class UnmodifiableList<T> extends UnmodifiableCollection<T> 4531 implements List<T> 4532 { 4533 /** 4534 * Compatible with JDK 1.4. 4535 */ 4536 private static final long serialVersionUID = -283967356065247728L; 4537 4538 4539 /** 4540 * The wrapped list; stored both here and in the superclass to avoid 4541 * excessive casting. Package visible for use by subclass. 4542 * @serial the wrapped list 4543 */ 4544 final List<T> list; 4545 4546 /** 4547 * Wrap a given list. 4548 * @param l the list to wrap 4549 * @throws NullPointerException if l is null 4550 */ 4551 UnmodifiableList(List<? extends T> l) 4552 { 4553 super(l); 4554 list = (List<T>) l; 4555 } 4556 4557 /** 4558 * Blocks the addition of an element to the underlying 4559 * list at a specific index. This method never returns, 4560 * throwing an exception instead. 4561 * 4562 * @param index The index at which to place the new element. 4563 * @param o the object to add. 4564 * @throws UnsupportedOperationException as an unmodifiable 4565 * list doesn't support the <code>add()</code> operation. 4566 */ 4567 public void add(int index, T o) 4568 { 4569 throw new UnsupportedOperationException(); 4570 } 4571 4572 /** 4573 * Blocks the addition of a collection of elements to the 4574 * underlying list at a specific index. This method never 4575 * returns, throwing an exception instead. 4576 * 4577 * @param index The index at which to place the new element. 4578 * @param c the collections of objects to add. 4579 * @throws UnsupportedOperationException as an unmodifiable 4580 * list doesn't support the <code>addAll()</code> operation. 4581 */ 4582 public boolean addAll(int index, Collection<? extends T> c) 4583 { 4584 throw new UnsupportedOperationException(); 4585 } 4586 4587 /** 4588 * Returns <code>true</code> if the object, o, is an instance of 4589 * <code>List</code> with the same size and elements 4590 * as the underlying list. 4591 * 4592 * @param o The object to compare. 4593 * @return <code>true</code> if o is equivalent to the underlying list. 4594 */ 4595 public boolean equals(Object o) 4596 { 4597 return list.equals(o); 4598 } 4599 4600 /** 4601 * Retrieves the element at a given index in the underlying list. 4602 * 4603 * @param index the index of the element to be returned 4604 * @return the element at index index in this list 4605 * @throws IndexOutOfBoundsException if index < 0 || index >= size() 4606 */ 4607 public T get(int index) 4608 { 4609 return list.get(index); 4610 } 4611 4612 /** 4613 * Computes the hash code for the underlying list. 4614 * The exact computation is described in the documentation 4615 * of the <code>List</code> interface. 4616 * 4617 * @return The hash code of the underlying list. 4618 * @see List#hashCode() 4619 */ 4620 public int hashCode() 4621 { 4622 return list.hashCode(); 4623 } 4624 4625 /** 4626 * Obtain the first index at which a given object is to be found in the 4627 * underlying list. 4628 * 4629 * @param o the object to search for 4630 * @return the least integer n such that <code>o == null ? get(n) == null : 4631 * o.equals(get(n))</code>, or -1 if there is no such index. 4632 * @throws ClassCastException if the type of o is not a valid 4633 * type for the underlying list. 4634 * @throws NullPointerException if o is null and the underlying 4635 * list does not support null values. 4636 */ 4637 public int indexOf(Object o) 4638 { 4639 return list.indexOf(o); 4640 } 4641 4642 /** 4643 * Obtain the last index at which a given object is to be found in the 4644 * underlying list. 4645 * 4646 * @return the greatest integer n such that <code>o == null ? get(n) == null 4647 * : o.equals(get(n))</code>, or -1 if there is no such index. 4648 * @throws ClassCastException if the type of o is not a valid 4649 * type for the underlying list. 4650 * @throws NullPointerException if o is null and the underlying 4651 * list does not support null values. 4652 */ 4653 public int lastIndexOf(Object o) 4654 { 4655 return list.lastIndexOf(o); 4656 } 4657 4658 /** 4659 * Obtains a list iterator over the underlying list, starting at the beginning 4660 * and maintaining the unmodifiable nature of this list. 4661 * 4662 * @return a <code>UnmodifiableListIterator</code> over the elements of the 4663 * underlying list, in order, starting at the beginning. 4664 */ 4665 public ListIterator<T> listIterator() 4666 { 4667 return new UnmodifiableListIterator<T>(list.listIterator()); 4668 } 4669 4670 /** 4671 * Obtains a list iterator over the underlying list, starting at the specified 4672 * index and maintaining the unmodifiable nature of this list. An initial call 4673 * to <code>next()</code> will retrieve the element at the specified index, 4674 * and an initial call to <code>previous()</code> will retrieve the element 4675 * at index - 1. 4676 * 4677 * 4678 * @param index the position, between 0 and size() inclusive, to begin the 4679 * iteration from. 4680 * @return a <code>UnmodifiableListIterator</code> over the elements of the 4681 * underlying list, in order, starting at the specified index. 4682 * @throws IndexOutOfBoundsException if index < 0 || index > size() 4683 */ 4684 public ListIterator<T> listIterator(int index) 4685 { 4686 return new UnmodifiableListIterator<T>(list.listIterator(index)); 4687 } 4688 4689 /** 4690 * Blocks the removal of the element at the specified index. 4691 * This method never returns, throwing an exception instead. 4692 * 4693 * @param index The index of the element to remove. 4694 * @return the removed element. 4695 * @throws UnsupportedOperationException as an unmodifiable 4696 * list does not support the <code>remove()</code> 4697 * operation. 4698 */ 4699 public T remove(int index) 4700 { 4701 throw new UnsupportedOperationException(); 4702 } 4703 4704 /** 4705 * Blocks the replacement of the element at the specified index. 4706 * This method never returns, throwing an exception instead. 4707 * 4708 * @param index The index of the element to replace. 4709 * @param o The new object to place at the specified index. 4710 * @return the replaced element. 4711 * @throws UnsupportedOperationException as an unmodifiable 4712 * list does not support the <code>set()</code> 4713 * operation. 4714 */ 4715 public T set(int index, T o) 4716 { 4717 throw new UnsupportedOperationException(); 4718 } 4719 4720 /** 4721 * Obtain a List view of a subsection of the underlying list, from 4722 * fromIndex (inclusive) to toIndex (exclusive). If the two indices 4723 * are equal, the sublist is empty. The returned list will be 4724 * unmodifiable, like this list. Changes to the elements of the 4725 * returned list will be reflected in the underlying list. No structural 4726 * modifications can take place in either list. 4727 * 4728 * @param fromIndex the index that the returned list should start from 4729 * (inclusive). 4730 * @param toIndex the index that the returned list should go to (exclusive). 4731 * @return a List backed by a subsection of the underlying list. 4732 * @throws IndexOutOfBoundsException if fromIndex < 0 4733 * || toIndex > size() || fromIndex > toIndex. 4734 */ 4735 public List<T> subList(int fromIndex, int toIndex) 4736 { 4737 return unmodifiableList(list.subList(fromIndex, toIndex)); 4738 } 4739 } // class UnmodifiableList 4740 4741 /** 4742 * The implementation of {@link #unmodifiableList(List)} for random-access 4743 * lists. This class name is required for compatibility with Sun's JDK 4744 * serializability. 4745 * 4746 * @author Eric Blake (ebb9@email.byu.edu) 4747 */ 4748 private static final class UnmodifiableRandomAccessList<T> 4749 extends UnmodifiableList<T> implements RandomAccess 4750 { 4751 /** 4752 * Compatible with JDK 1.4. 4753 */ 4754 private static final long serialVersionUID = -2542308836966382001L; 4755 4756 /** 4757 * Wrap a given list. 4758 * @param l the list to wrap 4759 * @throws NullPointerException if l is null 4760 */ 4761 UnmodifiableRandomAccessList(List<? extends T> l) 4762 { 4763 super(l); 4764 } 4765 } // class UnmodifiableRandomAccessList 4766 4767 /** 4768 * The implementation of {@link UnmodifiableList#listIterator()}. 4769 * 4770 * @author Eric Blake (ebb9@email.byu.edu) 4771 */ 4772 private static final class UnmodifiableListIterator<T> 4773 extends UnmodifiableIterator<T> implements ListIterator<T> 4774 { 4775 /** 4776 * The wrapped iterator, stored both here and in the superclass to 4777 * avoid excessive casting. 4778 */ 4779 private final ListIterator<T> li; 4780 4781 /** 4782 * Only trusted code creates a wrapper. 4783 * @param li the wrapped iterator 4784 */ 4785 UnmodifiableListIterator(ListIterator<T> li) 4786 { 4787 super(li); 4788 this.li = li; 4789 } 4790 4791 /** 4792 * Blocks the addition of an object to the list underlying this iterator. 4793 * This method never returns, throwing an exception instead. 4794 * 4795 * @param o The object to add. 4796 * @throws UnsupportedOperationException as the iterator of an unmodifiable 4797 * list does not support the <code>add()</code> operation. 4798 */ 4799 public void add(T o) 4800 { 4801 throw new UnsupportedOperationException(); 4802 } 4803 4804 /** 4805 * Tests whether there are still elements to be retrieved from the 4806 * underlying collection by <code>previous()</code>. When this method 4807 * returns <code>true</code>, an exception will not be thrown on calling 4808 * <code>previous()</code>. 4809 * 4810 * @return <code>true</code> if there is at least one more element prior to the 4811 * current position in the underlying list. 4812 */ 4813 public boolean hasPrevious() 4814 { 4815 return li.hasPrevious(); 4816 } 4817 4818 /** 4819 * Find the index of the element that would be returned by a call to next. 4820 * If <code>hasNext()</code> returns <code>false</code>, this returns the list size. 4821 * 4822 * @return the index of the element that would be returned by 4823 * <code>next()</code>. 4824 */ 4825 public int nextIndex() 4826 { 4827 return li.nextIndex(); 4828 } 4829 4830 /** 4831 * Obtains the previous element in the underlying list. 4832 * 4833 * @return the previous element in the list. 4834 * @throws NoSuchElementException if there are no more prior elements. 4835 */ 4836 public T previous() 4837 { 4838 return li.previous(); 4839 } 4840 4841 /** 4842 * Find the index of the element that would be returned by a call to 4843 * previous. If <code>hasPrevious()</code> returns <code>false</code>, 4844 * this returns -1. 4845 * 4846 * @return the index of the element that would be returned by 4847 * <code>previous()</code>. 4848 */ 4849 public int previousIndex() 4850 { 4851 return li.previousIndex(); 4852 } 4853 4854 /** 4855 * Blocks the replacement of an element in the list underlying this 4856 * iterator. This method never returns, throwing an exception instead. 4857 * 4858 * @param o The new object to replace the existing one. 4859 * @throws UnsupportedOperationException as the iterator of an unmodifiable 4860 * list does not support the <code>set()</code> operation. 4861 */ 4862 public void set(T o) 4863 { 4864 throw new UnsupportedOperationException(); 4865 } 4866 } // class UnmodifiableListIterator 4867 4868 /** 4869 * Returns an unmodifiable view of the given map. This allows "read-only" 4870 * access, although changes in the backing map show up in this view. 4871 * Attempts to modify the map directly, or via collection views or their 4872 * iterators will fail with {@link UnsupportedOperationException}. 4873 * Although this view prevents changes to the structure of the map and its 4874 * entries, the values referenced by the objects in the map can still be 4875 * modified. 4876 * <p> 4877 * 4878 * The returned Map implements Serializable, but can only be serialized if 4879 * the map it wraps is likewise Serializable. 4880 * 4881 * @param m the map to wrap 4882 * @return a read-only view of the map 4883 * @see Serializable 4884 */ 4885 public static <K, V> Map<K, V> unmodifiableMap(Map<? extends K, 4886 ? extends V> m) 4887 { 4888 return new UnmodifiableMap<K, V>(m); 4889 } 4890 4891 /** 4892 * The implementation of {@link #unmodifiableMap(Map)}. This 4893 * class name is required for compatibility with Sun's JDK serializability. 4894 * 4895 * @author Eric Blake (ebb9@email.byu.edu) 4896 */ 4897 private static class UnmodifiableMap<K, V> implements Map<K, V>, Serializable 4898 { 4899 /** 4900 * Compatible with JDK 1.4. 4901 */ 4902 private static final long serialVersionUID = -1034234728574286014L; 4903 4904 /** 4905 * The wrapped map. 4906 * @serial the real map 4907 */ 4908 private final Map<K, V> m; 4909 4910 /** 4911 * Cache the entry set. 4912 */ 4913 private transient Set<Map.Entry<K, V>> entries; 4914 4915 /** 4916 * Cache the key set. 4917 */ 4918 private transient Set<K> keys; 4919 4920 /** 4921 * Cache the value collection. 4922 */ 4923 private transient Collection<V> values; 4924 4925 /** 4926 * Wrap a given map. 4927 * @param m the map to wrap 4928 * @throws NullPointerException if m is null 4929 */ 4930 UnmodifiableMap(Map<? extends K, ? extends V> m) 4931 { 4932 this.m = (Map<K,V>) m; 4933 if (m == null) 4934 throw new NullPointerException(); 4935 } 4936 4937 /** 4938 * Blocks the clearing of entries from the underlying map. 4939 * This method never returns, throwing an exception instead. 4940 * 4941 * @throws UnsupportedOperationException as an unmodifiable 4942 * map does not support the <code>clear()</code> operation. 4943 */ 4944 public void clear() 4945 { 4946 throw new UnsupportedOperationException(); 4947 } 4948 4949 /** 4950 * Returns <code>true</code> if the underlying map contains a mapping for 4951 * the given key. 4952 * 4953 * @param key the key to search for 4954 * @return <code>true</code> if the map contains the key 4955 * @throws ClassCastException if the key is of an inappropriate type 4956 * @throws NullPointerException if key is <code>null</code> but the map 4957 * does not permit null keys 4958 */ 4959 public boolean containsKey(Object key) 4960 { 4961 return m.containsKey(key); 4962 } 4963 4964 /** 4965 * Returns <code>true</code> if the underlying map contains at least one mapping with 4966 * the given value. In other words, it returns <code>true</code> if a value v exists where 4967 * <code>(value == null ? v == null : value.equals(v))</code>. This usually 4968 * requires linear time. 4969 * 4970 * @param value the value to search for 4971 * @return <code>true</code> if the map contains the value 4972 * @throws ClassCastException if the type of the value is not a valid type 4973 * for this map. 4974 * @throws NullPointerException if the value is null and the map doesn't 4975 * support null values. 4976 */ 4977 public boolean containsValue(Object value) 4978 { 4979 return m.containsValue(value); 4980 } 4981 4982 /** 4983 * Returns a unmodifiable set view of the entries in the underlying map. 4984 * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>. 4985 * The set is backed by the map, so that changes in one show up in the other. 4986 * Modifications made while an iterator is in progress cause undefined 4987 * behavior. These modifications are again limited to the values of 4988 * the objects. 4989 * 4990 * @return the unmodifiable set view of all mapping entries. 4991 * @see Map.Entry 4992 */ 4993 public Set<Map.Entry<K, V>> entrySet() 4994 { 4995 if (entries == null) 4996 entries = new UnmodifiableEntrySet<K,V>(m.entrySet()); 4997 return entries; 4998 } 4999 5000 /** 5001 * The implementation of {@link UnmodifiableMap#entrySet()}. This class 5002 * name is required for compatibility with Sun's JDK serializability. 5003 * 5004 * @author Eric Blake (ebb9@email.byu.edu) 5005 */ 5006 private static final class UnmodifiableEntrySet<K,V> 5007 extends UnmodifiableSet<Map.Entry<K,V>> 5008 implements Serializable 5009 { 5010 // Unmodifiable implementation of Map.Entry used as return value for 5011 // UnmodifiableEntrySet accessors (iterator, toArray, toArray(Object[])) 5012 private static final class UnmodifiableMapEntry<K,V> 5013 implements Map.Entry<K,V> 5014 { 5015 private final Map.Entry<K,V> e; 5016 5017 private UnmodifiableMapEntry(Map.Entry<K,V> e) 5018 { 5019 super(); 5020 this.e = e; 5021 } 5022 5023 /** 5024 * Returns <code>true</code> if the object, o, is also a map entry 5025 * with an identical key and value. 5026 * 5027 * @param o the object to compare. 5028 * @return <code>true</code> if o is an equivalent map entry. 5029 */ 5030 public boolean equals(Object o) 5031 { 5032 return e.equals(o); 5033 } 5034 5035 /** 5036 * Returns the key of this map entry. 5037 * 5038 * @return the key. 5039 */ 5040 public K getKey() 5041 { 5042 return e.getKey(); 5043 } 5044 5045 /** 5046 * Returns the value of this map entry. 5047 * 5048 * @return the value. 5049 */ 5050 public V getValue() 5051 { 5052 return e.getValue(); 5053 } 5054 5055 /** 5056 * Computes the hash code of this map entry. The computation is 5057 * described in the <code>Map</code> interface documentation. 5058 * 5059 * @return the hash code of this entry. 5060 * @see Map#hashCode() 5061 */ 5062 public int hashCode() 5063 { 5064 return e.hashCode(); 5065 } 5066 5067 /** 5068 * Blocks the alteration of the value of this map entry. This method 5069 * never returns, throwing an exception instead. 5070 * 5071 * @param value The new value. 5072 * @throws UnsupportedOperationException as an unmodifiable map entry 5073 * does not support the <code>setValue()</code> operation. 5074 */ 5075 public V setValue(V value) 5076 { 5077 throw new UnsupportedOperationException(); 5078 } 5079 5080 /** 5081 * Returns a textual representation of the map entry. 5082 * 5083 * @return The map entry as a <code>String</code>. 5084 */ 5085 public String toString() 5086 { 5087 return e.toString(); 5088 } 5089 } 5090 5091 /** 5092 * Compatible with JDK 1.4. 5093 */ 5094 private static final long serialVersionUID = 7854390611657943733L; 5095 5096 /** 5097 * Wrap a given set. 5098 * @param s the set to wrap 5099 */ 5100 UnmodifiableEntrySet(Set<Map.Entry<K,V>> s) 5101 { 5102 super(s); 5103 } 5104 5105 // The iterator must return unmodifiable map entries. 5106 public Iterator<Map.Entry<K,V>> iterator() 5107 { 5108 return new UnmodifiableIterator<Map.Entry<K,V>>(c.iterator()) 5109 { 5110 /** 5111 * Obtains the next element from the underlying set of 5112 * map entries. 5113 * 5114 * @return the next element in the collection. 5115 * @throws NoSuchElementException if there are no more elements. 5116 */ 5117 public Map.Entry<K,V> next() 5118 { 5119 final Map.Entry<K,V> e = super.next(); 5120 return new UnmodifiableMapEntry<K,V>(e); 5121 } 5122 }; 5123 } 5124 5125 // The array returned is an array of UnmodifiableMapEntry instead of 5126 // Map.Entry 5127 public Object[] toArray() 5128 { 5129 Object[] mapEntryResult = super.toArray(); 5130 UnmodifiableMapEntry<K,V> result[] = null; 5131 5132 if (mapEntryResult != null) 5133 { 5134 result = (UnmodifiableMapEntry<K,V>[]) 5135 new UnmodifiableMapEntry[mapEntryResult.length]; 5136 for (int i = 0; i < mapEntryResult.length; ++i) 5137 result[i] = new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>)mapEntryResult[i]); 5138 } 5139 return result; 5140 } 5141 5142 // The array returned is an array of UnmodifiableMapEntry instead of 5143 // Map.Entry 5144 public <S> S[] toArray(S[] array) 5145 { 5146 S[] result = super.toArray(array); 5147 5148 if (result != null) 5149 for (int i = 0; i < result.length; i++) 5150 array[i] = 5151 (S) new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>) result[i]); 5152 return array; 5153 } 5154 5155 5156 } // class UnmodifiableEntrySet 5157 5158 /** 5159 * Returns <code>true</code> if the object, o, is also an instance 5160 * of <code>Map</code> with an equal set of map entries. 5161 * 5162 * @param o The object to compare. 5163 * @return <code>true</code> if o is an equivalent map. 5164 */ 5165 public boolean equals(Object o) 5166 { 5167 return m.equals(o); 5168 } 5169 5170 /** 5171 * Returns the value associated with the supplied key or 5172 * null if no such mapping exists. An ambiguity can occur 5173 * if null values are accepted by the underlying map. 5174 * In this case, <code>containsKey()</code> can be used 5175 * to separate the two possible cases of a null result. 5176 * 5177 * @param key The key to look up. 5178 * @return the value associated with the key, or null if key not in map. 5179 * @throws ClassCastException if the key is an inappropriate type. 5180 * @throws NullPointerException if this map does not accept null keys. 5181 * @see #containsKey(Object) 5182 */ 5183 public V get(Object key) 5184 { 5185 return m.get(key); 5186 } 5187 5188 /** 5189 * Blocks the addition of a new entry to the underlying map. 5190 * This method never returns, throwing an exception instead. 5191 * 5192 * @param key The new key. 5193 * @param value The new value. 5194 * @return the previous value of the key, or null if there was no mapping. 5195 * @throws UnsupportedOperationException as an unmodifiable 5196 * map does not support the <code>put()</code> operation. 5197 */ 5198 public V put(K key, V value) 5199 { 5200 throw new UnsupportedOperationException(); 5201 } 5202 5203 /** 5204 * Computes the hash code for the underlying map, as the sum 5205 * of the hash codes of all entries. 5206 * 5207 * @return The hash code of the underlying map. 5208 * @see Map.Entry#hashCode() 5209 */ 5210 public int hashCode() 5211 { 5212 return m.hashCode(); 5213 } 5214 5215 /** 5216 * Returns <code>true</code> if the underlying map contains no entries. 5217 * 5218 * @return <code>true</code> if the map is empty. 5219 */ 5220 public boolean isEmpty() 5221 { 5222 return m.isEmpty(); 5223 } 5224 5225 /** 5226 * Returns a unmodifiable set view of the keys in the underlying map. 5227 * The set is backed by the map, so that changes in one show up in the other. 5228 * Modifications made while an iterator is in progress cause undefined 5229 * behavior. These modifications are again limited to the values of 5230 * the keys. 5231 * 5232 * @return the set view of all keys. 5233 */ 5234 public Set<K> keySet() 5235 { 5236 if (keys == null) 5237 keys = new UnmodifiableSet<K>(m.keySet()); 5238 return keys; 5239 } 5240 5241 /** 5242 * Blocks the addition of the entries in the supplied map. 5243 * This method never returns, throwing an exception instead. 5244 * 5245 * @param m The map, the entries of which should be added 5246 * to the underlying map. 5247 * @throws UnsupportedOperationException as an unmodifiable 5248 * map does not support the <code>putAll</code> operation. 5249 */ 5250 public void putAll(Map<? extends K, ? extends V> m) 5251 { 5252 throw new UnsupportedOperationException(); 5253 } 5254 5255 /** 5256 * Blocks the removal of an entry from the map. 5257 * This method never returns, throwing an exception instead. 5258 * 5259 * @param o The key of the entry to remove. 5260 * @return The value the key was associated with, or null 5261 * if no such mapping existed. Null is also returned 5262 * if the removed entry had a null key. 5263 * @throws UnsupportedOperationException as an unmodifiable 5264 * map does not support the <code>remove</code> operation. 5265 */ 5266 public V remove(Object o) 5267 { 5268 throw new UnsupportedOperationException(); 5269 } 5270 5271 5272 /** 5273 * Returns the number of key-value mappings in the underlying map. 5274 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE 5275 * is returned. 5276 * 5277 * @return the number of mappings. 5278 */ 5279 public int size() 5280 { 5281 return m.size(); 5282 } 5283 5284 /** 5285 * Returns a textual representation of the map. 5286 * 5287 * @return The map in the form of a <code>String</code>. 5288 */ 5289 public String toString() 5290 { 5291 return m.toString(); 5292 } 5293 5294 /** 5295 * Returns a unmodifiable collection view of the values in the underlying map. 5296 * The collection is backed by the map, so that changes in one show up in the other. 5297 * Modifications made while an iterator is in progress cause undefined 5298 * behavior. These modifications are again limited to the values of 5299 * the keys. 5300 * 5301 * @return the collection view of all values. 5302 */ 5303 public Collection<V> values() 5304 { 5305 if (values == null) 5306 values = new UnmodifiableCollection<V>(m.values()); 5307 return values; 5308 } 5309 } // class UnmodifiableMap 5310 5311 /** 5312 * Returns an unmodifiable view of the given set. This allows 5313 * "read-only" access, although changes in the backing set show up 5314 * in this view. Attempts to modify the set directly or via iterators 5315 * will fail with {@link UnsupportedOperationException}. 5316 * Although this view prevents changes to the structure of the set and its 5317 * entries, the values referenced by the objects in the set can still be 5318 * modified. 5319 * <p> 5320 * 5321 * The returned Set implements Serializable, but can only be serialized if 5322 * the set it wraps is likewise Serializable. 5323 * 5324 * @param s the set to wrap 5325 * @return a read-only view of the set 5326 * @see Serializable 5327 */ 5328 public static <T> Set<T> unmodifiableSet(Set<? extends T> s) 5329 { 5330 return new UnmodifiableSet<T>(s); 5331 } 5332 5333 /** 5334 * The implementation of {@link #unmodifiableSet(Set)}. This class 5335 * name is required for compatibility with Sun's JDK serializability. 5336 * 5337 * @author Eric Blake (ebb9@email.byu.edu) 5338 */ 5339 private static class UnmodifiableSet<T> extends UnmodifiableCollection<T> 5340 implements Set<T> 5341 { 5342 /** 5343 * Compatible with JDK 1.4. 5344 */ 5345 private static final long serialVersionUID = -9215047833775013803L; 5346 5347 /** 5348 * Wrap a given set. 5349 * @param s the set to wrap 5350 * @throws NullPointerException if s is null 5351 */ 5352 UnmodifiableSet(Set<? extends T> s) 5353 { 5354 super(s); 5355 } 5356 5357 /** 5358 * Returns <code>true</code> if the object, o, is also an instance of 5359 * <code>Set</code> of the same size and with the same entries. 5360 * 5361 * @return <code>true</code> if o is an equivalent set. 5362 */ 5363 public boolean equals(Object o) 5364 { 5365 return c.equals(o); 5366 } 5367 5368 /** 5369 * Computes the hash code of this set, as the sum of the 5370 * hash codes of all elements within the set. 5371 * 5372 * @return the hash code of the set. 5373 */ 5374 public int hashCode() 5375 { 5376 return c.hashCode(); 5377 } 5378 } // class UnmodifiableSet 5379 5380 /** 5381 * Returns an unmodifiable view of the given sorted map. This allows 5382 * "read-only" access, although changes in the backing map show up in this 5383 * view. Attempts to modify the map directly, via subviews, via collection 5384 * views, or iterators, will fail with {@link UnsupportedOperationException}. 5385 * Although this view prevents changes to the structure of the map and its 5386 * entries, the values referenced by the objects in the map can still be 5387 * modified. 5388 * <p> 5389 * 5390 * The returned SortedMap implements Serializable, but can only be 5391 * serialized if the map it wraps is likewise Serializable. 5392 * 5393 * @param m the map to wrap 5394 * @return a read-only view of the map 5395 * @see Serializable 5396 */ 5397 public static <K, V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, 5398 ? extends V> m) 5399 { 5400 return new UnmodifiableSortedMap<K, V>(m); 5401 } 5402 5403 /** 5404 * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This 5405 * class name is required for compatibility with Sun's JDK serializability. 5406 * 5407 * @author Eric Blake (ebb9@email.byu.edu) 5408 */ 5409 private static class UnmodifiableSortedMap<K, V> 5410 extends UnmodifiableMap<K, V> 5411 implements SortedMap<K, V> 5412 { 5413 /** 5414 * Compatible with JDK 1.4. 5415 */ 5416 private static final long serialVersionUID = -8806743815996713206L; 5417 5418 /** 5419 * The wrapped map; stored both here and in the superclass to avoid 5420 * excessive casting. 5421 * @serial the wrapped map 5422 */ 5423 private final SortedMap<K, V> sm; 5424 5425 /** 5426 * Wrap a given map. 5427 * @param sm the map to wrap 5428 * @throws NullPointerException if sm is null 5429 */ 5430 UnmodifiableSortedMap(SortedMap<K, ? extends V> sm) 5431 { 5432 super(sm); 5433 this.sm = (SortedMap<K,V>) sm; 5434 } 5435 5436 /** 5437 * Returns the comparator used in sorting the underlying map, 5438 * or null if it is the keys' natural ordering. 5439 * 5440 * @return the sorting comparator. 5441 */ 5442 public Comparator<? super K> comparator() 5443 { 5444 return sm.comparator(); 5445 } 5446 5447 /** 5448 * Returns the first (lowest sorted) key in the map. 5449 * 5450 * @return the first key. 5451 * @throws NoSuchElementException if this map is empty. 5452 */ 5453 public K firstKey() 5454 { 5455 return sm.firstKey(); 5456 } 5457 5458 /** 5459 * Returns a unmodifiable view of the portion of the map strictly less 5460 * than toKey. The view is backed by the underlying map, so changes in 5461 * one show up in the other. The submap supports all optional operations 5462 * of the original. This operation is equivalent to 5463 * <code>subMap(firstKey(), toKey)</code>. 5464 * <p> 5465 * 5466 * The returned map throws an IllegalArgumentException any time a key is 5467 * used which is out of the range of toKey. Note that the endpoint, toKey, 5468 * is not included; if you want this value to be included, pass its successor 5469 * object in to toKey. For example, for Integers, you could request 5470 * <code>headMap(new Integer(limit.intValue() + 1))</code>. 5471 * 5472 * @param toKey the exclusive upper range of the submap. 5473 * @return the submap. 5474 * @throws ClassCastException if toKey is not comparable to the map contents. 5475 * @throws IllegalArgumentException if this is a subMap, and toKey is out 5476 * of range. 5477 * @throws NullPointerException if toKey is null but the map does not allow 5478 * null keys. 5479 */ 5480 public SortedMap<K, V> headMap(K toKey) 5481 { 5482 return new UnmodifiableSortedMap<K, V>(sm.headMap(toKey)); 5483 } 5484 5485 /** 5486 * Returns the last (highest sorted) key in the map. 5487 * 5488 * @return the last key. 5489 * @throws NoSuchElementException if this map is empty. 5490 */ 5491 public K lastKey() 5492 { 5493 return sm.lastKey(); 5494 } 5495 5496 /** 5497 * Returns a unmodifiable view of the portion of the map greater than or 5498 * equal to fromKey, and strictly less than toKey. The view is backed by 5499 * the underlying map, so changes in one show up in the other. The submap 5500 * supports all optional operations of the original. 5501 * <p> 5502 * 5503 * The returned map throws an IllegalArgumentException any time a key is 5504 * used which is out of the range of fromKey and toKey. Note that the 5505 * lower endpoint is included, but the upper is not; if you want to 5506 * change the inclusion or exclusion of an endpoint, pass its successor 5507 * object in instead. For example, for Integers, you could request 5508 * <code>subMap(new Integer(lowlimit.intValue() + 1), 5509 * new Integer(highlimit.intValue() + 1))</code> to reverse 5510 * the inclusiveness of both endpoints. 5511 * 5512 * @param fromKey the inclusive lower range of the submap. 5513 * @param toKey the exclusive upper range of the submap. 5514 * @return the submap. 5515 * @throws ClassCastException if fromKey or toKey is not comparable to 5516 * the map contents. 5517 * @throws IllegalArgumentException if this is a subMap, and fromKey or 5518 * toKey is out of range. 5519 * @throws NullPointerException if fromKey or toKey is null but the map 5520 * does not allow null keys. 5521 */ 5522 public SortedMap<K, V> subMap(K fromKey, K toKey) 5523 { 5524 return new UnmodifiableSortedMap<K, V>(sm.subMap(fromKey, toKey)); 5525 } 5526 5527 /** 5528 * Returns a unmodifiable view of the portion of the map greater than or 5529 * equal to fromKey. The view is backed by the underlying map, so changes 5530 * in one show up in the other. The submap supports all optional operations 5531 * of the original. 5532 * <p> 5533 * 5534 * The returned map throws an IllegalArgumentException any time a key is 5535 * used which is out of the range of fromKey. Note that the endpoint, fromKey, is 5536 * included; if you do not want this value to be included, pass its successor object in 5537 * to fromKey. For example, for Integers, you could request 5538 * <code>tailMap(new Integer(limit.intValue() + 1))</code>. 5539 * 5540 * @param fromKey the inclusive lower range of the submap 5541 * @return the submap 5542 * @throws ClassCastException if fromKey is not comparable to the map 5543 * contents 5544 * @throws IllegalArgumentException if this is a subMap, and fromKey is out 5545 * of range 5546 * @throws NullPointerException if fromKey is null but the map does not allow 5547 * null keys 5548 */ 5549 public SortedMap<K, V> tailMap(K fromKey) 5550 { 5551 return new UnmodifiableSortedMap<K, V>(sm.tailMap(fromKey)); 5552 } 5553 } // class UnmodifiableSortedMap 5554 5555 /** 5556 * Returns an unmodifiable view of the given sorted set. This allows 5557 * "read-only" access, although changes in the backing set show up 5558 * in this view. Attempts to modify the set directly, via subsets, or via 5559 * iterators, will fail with {@link UnsupportedOperationException}. 5560 * Although this view prevents changes to the structure of the set and its 5561 * entries, the values referenced by the objects in the set can still be 5562 * modified. 5563 * <p> 5564 * 5565 * The returns SortedSet implements Serializable, but can only be 5566 * serialized if the set it wraps is likewise Serializable. 5567 * 5568 * @param s the set to wrap 5569 * @return a read-only view of the set 5570 * @see Serializable 5571 */ 5572 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) 5573 { 5574 return new UnmodifiableSortedSet<T>(s); 5575 } 5576 5577 /** 5578 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This 5579 * class name is required for compatibility with Sun's JDK serializability. 5580 * 5581 * @author Eric Blake (ebb9@email.byu.edu) 5582 */ 5583 private static class UnmodifiableSortedSet<T> extends UnmodifiableSet<T> 5584 implements SortedSet<T> 5585 { 5586 /** 5587 * Compatible with JDK 1.4. 5588 */ 5589 private static final long serialVersionUID = -4929149591599911165L; 5590 5591 /** 5592 * The wrapped set; stored both here and in the superclass to avoid 5593 * excessive casting. 5594 * @serial the wrapped set 5595 */ 5596 private SortedSet<T> ss; 5597 5598 /** 5599 * Wrap a given set. 5600 * @param ss the set to wrap 5601 * @throws NullPointerException if ss is null 5602 */ 5603 UnmodifiableSortedSet(SortedSet<T> ss) 5604 { 5605 super(ss); 5606 this.ss = ss; 5607 } 5608 5609 /** 5610 * Returns the comparator used in sorting the underlying set, 5611 * or null if it is the elements' natural ordering. 5612 * 5613 * @return the sorting comparator 5614 */ 5615 public Comparator<? super T> comparator() 5616 { 5617 return ss.comparator(); 5618 } 5619 5620 /** 5621 * Returns the first (lowest sorted) element in the underlying 5622 * set. 5623 * 5624 * @return the first element. 5625 * @throws NoSuchElementException if the set is empty. 5626 */ 5627 public T first() 5628 { 5629 return ss.first(); 5630 } 5631 5632 /** 5633 * Returns a unmodifiable view of the portion of the set strictly 5634 * less than toElement. The view is backed by the underlying set, 5635 * so changes in one show up in the other. The subset supports 5636 * all optional operations of the original. This operation 5637 * is equivalent to <code>subSet(first(), toElement)</code>. 5638 * <p> 5639 * 5640 * The returned set throws an IllegalArgumentException any time an element is 5641 * used which is out of the range of toElement. Note that the endpoint, toElement, 5642 * is not included; if you want this value included, pass its successor object in to 5643 * toElement. For example, for Integers, you could request 5644 * <code>headSet(new Integer(limit.intValue() + 1))</code>. 5645 * 5646 * @param toElement the exclusive upper range of the subset 5647 * @return the subset. 5648 * @throws ClassCastException if toElement is not comparable to the set 5649 * contents. 5650 * @throws IllegalArgumentException if this is a subSet, and toElement is out 5651 * of range. 5652 * @throws NullPointerException if toElement is null but the set does not 5653 * allow null elements. 5654 */ 5655 public SortedSet<T> headSet(T toElement) 5656 { 5657 return new UnmodifiableSortedSet<T>(ss.headSet(toElement)); 5658 } 5659 5660 /** 5661 * Returns the last (highest sorted) element in the underlying 5662 * set. 5663 * 5664 * @return the last element. 5665 * @throws NoSuchElementException if the set is empty. 5666 */ 5667 public T last() 5668 { 5669 return ss.last(); 5670 } 5671 5672 /** 5673 * Returns a unmodifiable view of the portion of the set greater than or 5674 * equal to fromElement, and strictly less than toElement. The view is backed by 5675 * the underlying set, so changes in one show up in the other. The subset 5676 * supports all optional operations of the original. 5677 * <p> 5678 * 5679 * The returned set throws an IllegalArgumentException any time an element is 5680 * used which is out of the range of fromElement and toElement. Note that the 5681 * lower endpoint is included, but the upper is not; if you want to 5682 * change the inclusion or exclusion of an endpoint, pass its successor 5683 * object in instead. For example, for Integers, you can request 5684 * <code>subSet(new Integer(lowlimit.intValue() + 1), 5685 * new Integer(highlimit.intValue() + 1))</code> to reverse 5686 * the inclusiveness of both endpoints. 5687 * 5688 * @param fromElement the inclusive lower range of the subset. 5689 * @param toElement the exclusive upper range of the subset. 5690 * @return the subset. 5691 * @throws ClassCastException if fromElement or toElement is not comparable 5692 * to the set contents. 5693 * @throws IllegalArgumentException if this is a subSet, and fromElement or 5694 * toElement is out of range. 5695 * @throws NullPointerException if fromElement or toElement is null but the 5696 * set does not allow null elements. 5697 */ 5698 public SortedSet<T> subSet(T fromElement, T toElement) 5699 { 5700 return new UnmodifiableSortedSet<T>(ss.subSet(fromElement, toElement)); 5701 } 5702 5703 /** 5704 * Returns a unmodifiable view of the portion of the set greater than or equal to 5705 * fromElement. The view is backed by the underlying set, so changes in one show up 5706 * in the other. The subset supports all optional operations of the original. 5707 * <p> 5708 * 5709 * The returned set throws an IllegalArgumentException any time an element is 5710 * used which is out of the range of fromElement. Note that the endpoint, 5711 * fromElement, is included; if you do not want this value to be included, pass its 5712 * successor object in to fromElement. For example, for Integers, you could request 5713 * <code>tailSet(new Integer(limit.intValue() + 1))</code>. 5714 * 5715 * @param fromElement the inclusive lower range of the subset 5716 * @return the subset. 5717 * @throws ClassCastException if fromElement is not comparable to the set 5718 * contents. 5719 * @throws IllegalArgumentException if this is a subSet, and fromElement is 5720 * out of range. 5721 * @throws NullPointerException if fromElement is null but the set does not 5722 * allow null elements. 5723 */ 5724 public SortedSet<T> tailSet(T fromElement) 5725 { 5726 return new UnmodifiableSortedSet<T>(ss.tailSet(fromElement)); 5727 } 5728 } // class UnmodifiableSortedSet 5729 5730 /** 5731 * <p> 5732 * Returns a dynamically typesafe view of the given collection, 5733 * where any modification is first checked to ensure that the type 5734 * of the new data is appropriate. Although the addition of 5735 * generics and parametrically-typed collections prevents an 5736 * incorrect type of element being added to a collection at 5737 * compile-time, via static type checking, this can be overridden by 5738 * casting. In contrast, wrapping the collection within a 5739 * dynamically-typesafe wrapper, using this and associated methods, 5740 * <emph>guarantees</emph> that the collection will only contain 5741 * elements of an appropriate type (provided it only contains such 5742 * at the type of wrapping, and all subsequent access is via the 5743 * wrapper). This can be useful for debugging the cause of a 5744 * <code>ClassCastException</code> caused by erroneous casting, or 5745 * for protecting collections from corruption by external libraries. 5746 * </p> 5747 * <p> 5748 * Since the collection might be a List or a Set, and those 5749 * have incompatible equals and hashCode requirements, this relies 5750 * on Object's implementation rather than passing those calls on to 5751 * the wrapped collection. The returned Collection implements 5752 * Serializable, but can only be serialized if the collection it 5753 * wraps is likewise Serializable. 5754 * </p> 5755 * 5756 * @param c the collection to wrap in a dynamically typesafe wrapper 5757 * @param type the type of elements the collection should hold. 5758 * @return a dynamically typesafe view of the collection. 5759 * @see Serializable 5760 * @since 1.5 5761 */ 5762 public static <E> Collection<E> checkedCollection(Collection<E> c, 5763 Class<E> type) 5764 { 5765 return new CheckedCollection<E>(c, type); 5766 } 5767 5768 /** 5769 * The implementation of {@link #checkedCollection(Collection,Class)}. This 5770 * class name is required for compatibility with Sun's JDK serializability. 5771 * 5772 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 5773 * @since 1.5 5774 */ 5775 private static class CheckedCollection<E> 5776 implements Collection<E>, Serializable 5777 { 5778 /** 5779 * Compatible with JDK 1.5. 5780 */ 5781 private static final long serialVersionUID = 1578914078182001775L; 5782 5783 /** 5784 * The wrapped collection. Package visible for use by subclasses. 5785 * @serial the real collection 5786 */ 5787 final Collection<E> c; 5788 5789 /** 5790 * The type of the elements of this collection. 5791 * @serial the element type. 5792 */ 5793 final Class<E> type; 5794 5795 /** 5796 * Wrap a given collection. 5797 * @param c the collection to wrap 5798 * @param type the type to wrap 5799 * @throws NullPointerException if c is null 5800 */ 5801 CheckedCollection(Collection<E> c, Class<E> type) 5802 { 5803 this.c = c; 5804 this.type = type; 5805 if (c == null) 5806 throw new NullPointerException(); 5807 } 5808 5809 /** 5810 * Adds the supplied object to the collection, on the condition that 5811 * it is of the correct type. 5812 * 5813 * @param o the object to add. 5814 * @return <code>true</code> if the collection was modified as a result 5815 * of this action. 5816 * @throws ClassCastException if the object is not of the correct type. 5817 */ 5818 public boolean add(E o) 5819 { 5820 if (type.isInstance(o)) 5821 return c.add(o); 5822 else 5823 throw new ClassCastException("The element is of the incorrect type."); 5824 } 5825 5826 /** 5827 * Adds the elements of the specified collection to the backing collection, 5828 * provided they are all of the correct type. 5829 * 5830 * @param coll the collection to add. 5831 * @return <code>true</code> if the collection was modified as a result 5832 * of this action. 5833 * @throws ClassCastException if <code>c</code> contained elements of an 5834 * incorrect type. 5835 */ 5836 public boolean addAll(Collection<? extends E> coll) 5837 { 5838 Collection<E> typedColl = (Collection<E>) c; 5839 final Iterator<E> it = typedColl.iterator(); 5840 while (it.hasNext()) 5841 { 5842 final E element = it.next(); 5843 if (!type.isInstance(element)) 5844 throw new ClassCastException("A member of the collection is not of the correct type."); 5845 } 5846 return c.addAll(typedColl); 5847 } 5848 5849 /** 5850 * Removes all elements from the underlying collection. 5851 */ 5852 public void clear() 5853 { 5854 c.clear(); 5855 } 5856 5857 /** 5858 * Test whether the underlying collection contains a given object as one 5859 * of its elements. 5860 * 5861 * @param o the element to look for. 5862 * @return <code>true</code> if the underlying collection contains at least 5863 * one element e such that 5864 * <code>o == null ? e == null : o.equals(e)</code>. 5865 * @throws ClassCastException if the type of o is not a valid type for the 5866 * underlying collection. 5867 * @throws NullPointerException if o is null and the underlying collection 5868 * doesn't support null values. 5869 */ 5870 public boolean contains(Object o) 5871 { 5872 return c.contains(o); 5873 } 5874 5875 /** 5876 * Test whether the underlying collection contains every element in a given 5877 * collection. 5878 * 5879 * @param coll the collection to test for. 5880 * @return <code>true</code> if for every element o in c, contains(o) would 5881 * return <code>true</code>. 5882 * @throws ClassCastException if the type of any element in c is not a 5883 * valid type for the underlying collection. 5884 * @throws NullPointerException if some element of c is null and the 5885 * underlying collection does not support 5886 * null values. 5887 * @throws NullPointerException if c itself is null. 5888 */ 5889 public boolean containsAll(Collection<?> coll) 5890 { 5891 return c.containsAll(coll); 5892 } 5893 5894 /** 5895 * Tests whether the underlying collection is empty, that is, 5896 * if size() == 0. 5897 * 5898 * @return <code>true</code> if this collection contains no elements. 5899 */ 5900 public boolean isEmpty() 5901 { 5902 return c.isEmpty(); 5903 } 5904 5905 /** 5906 * Obtain an Iterator over the underlying collection, which maintains 5907 * its checked nature. 5908 * 5909 * @return a Iterator over the elements of the underlying 5910 * collection, in any order. 5911 */ 5912 public Iterator<E> iterator() 5913 { 5914 return new CheckedIterator<E>(c.iterator(), type); 5915 } 5916 5917 /** 5918 * Removes the supplied object from the collection, if it exists. 5919 * 5920 * @param o The object to remove. 5921 * @return <code>true</code> if the object was removed (i.e. the underlying 5922 * collection returned 1 or more instances of o). 5923 */ 5924 public boolean remove(Object o) 5925 { 5926 return c.remove(o); 5927 } 5928 5929 /** 5930 * Removes all objects in the supplied collection from the backing 5931 * collection, if they exist within it. 5932 * 5933 * @param coll the collection of objects to remove. 5934 * @return <code>true</code> if the collection was modified. 5935 */ 5936 public boolean removeAll(Collection<?> coll) 5937 { 5938 return c.removeAll(coll); 5939 } 5940 5941 /** 5942 * Retains all objects specified by the supplied collection which exist 5943 * within the backing collection, and removes all others. 5944 * 5945 * @param coll the collection of objects to retain. 5946 * @return <code>true</code> if the collection was modified. 5947 */ 5948 public boolean retainAll(Collection<?> coll) 5949 { 5950 return c.retainAll(coll); 5951 } 5952 5953 /** 5954 * Retrieves the number of elements in the underlying collection. 5955 * 5956 * @return the number of elements in the collection. 5957 */ 5958 public int size() 5959 { 5960 return c.size(); 5961 } 5962 5963 /** 5964 * Copy the current contents of the underlying collection into an array. 5965 * 5966 * @return an array of type Object[] with a length equal to the size of the 5967 * underlying collection and containing the elements currently in 5968 * the underlying collection, in any order. 5969 */ 5970 public Object[] toArray() 5971 { 5972 return c.toArray(); 5973 } 5974 5975 /** 5976 * <p> 5977 * Copy the current contents of the underlying collection into an array. If 5978 * the array passed as an argument has length less than the size of the 5979 * underlying collection, an array of the same run-time type as a, with a 5980 * length equal to the size of the underlying collection, is allocated 5981 * using reflection. 5982 * </p> 5983 * <p> 5984 * Otherwise, a itself is used. The elements of the underlying collection 5985 * are copied into it, and if there is space in the array, the following 5986 * element is set to null. The resultant array is returned. 5987 * </p> 5988 * <p> 5989 * <emph>Note</emph>: The fact that the following element is set to null 5990 * is only useful if it is known that this collection does not contain 5991 * any null elements. 5992 * 5993 * @param a the array to copy this collection into. 5994 * @return an array containing the elements currently in the underlying 5995 * collection, in any order. 5996 * @throws ArrayStoreException if the type of any element of the 5997 * collection is not a subtype of the element type of a. 5998 */ 5999 public <S> S[] toArray(S[] a) 6000 { 6001 return c.toArray(a); 6002 } 6003 6004 /** 6005 * A textual representation of the unmodifiable collection. 6006 * 6007 * @return The checked collection in the form of a <code>String</code>. 6008 */ 6009 public String toString() 6010 { 6011 return c.toString(); 6012 } 6013 } // class CheckedCollection 6014 6015 /** 6016 * The implementation of the various iterator methods in the 6017 * checked classes. 6018 * 6019 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6020 * @since 1.5 6021 */ 6022 private static class CheckedIterator<E> 6023 implements Iterator<E> 6024 { 6025 /** 6026 * The wrapped iterator. 6027 */ 6028 private final Iterator<E> i; 6029 6030 /** 6031 * The type of the elements of this collection. 6032 * @serial the element type. 6033 */ 6034 final Class<E> type; 6035 6036 /** 6037 * Only trusted code creates a wrapper. 6038 * @param i the wrapped iterator 6039 * @param type the type of the elements within the checked list. 6040 */ 6041 CheckedIterator(Iterator<E> i, Class<E> type) 6042 { 6043 this.i = i; 6044 this.type = type; 6045 } 6046 6047 /** 6048 * Obtains the next element in the underlying collection. 6049 * 6050 * @return the next element in the collection. 6051 * @throws NoSuchElementException if there are no more elements. 6052 */ 6053 public E next() 6054 { 6055 return i.next(); 6056 } 6057 6058 /** 6059 * Tests whether there are still elements to be retrieved from the 6060 * underlying collection by <code>next()</code>. When this method 6061 * returns <code>true</code>, an exception will not be thrown on calling 6062 * <code>next()</code>. 6063 * 6064 * @return <code>true</code> if there is at least one more element in the 6065 * underlying collection. 6066 */ 6067 public boolean hasNext() 6068 { 6069 return i.hasNext(); 6070 } 6071 6072 /** 6073 * Removes the next element from the collection. 6074 */ 6075 public void remove() 6076 { 6077 i.remove(); 6078 } 6079 } // class CheckedIterator 6080 6081 /** 6082 * <p> 6083 * Returns a dynamically typesafe view of the given list, 6084 * where any modification is first checked to ensure that the type 6085 * of the new data is appropriate. Although the addition of 6086 * generics and parametrically-typed collections prevents an 6087 * incorrect type of element being added to a collection at 6088 * compile-time, via static type checking, this can be overridden by 6089 * casting. In contrast, wrapping the collection within a 6090 * dynamically-typesafe wrapper, using this and associated methods, 6091 * <emph>guarantees</emph> that the collection will only contain 6092 * elements of an appropriate type (provided it only contains such 6093 * at the type of wrapping, and all subsequent access is via the 6094 * wrapper). This can be useful for debugging the cause of a 6095 * <code>ClassCastException</code> caused by erroneous casting, or 6096 * for protecting collections from corruption by external libraries. 6097 * </p> 6098 * <p> 6099 * The returned List implements Serializable, but can only be serialized if 6100 * the list it wraps is likewise Serializable. In addition, if the wrapped 6101 * list implements RandomAccess, this does too. 6102 * </p> 6103 * 6104 * @param l the list to wrap 6105 * @param type the type of the elements within the checked list. 6106 * @return a dynamically typesafe view of the list 6107 * @see Serializable 6108 * @see RandomAccess 6109 */ 6110 public static <E> List<E> checkedList(List<E> l, Class<E> type) 6111 { 6112 if (l instanceof RandomAccess) 6113 return new CheckedRandomAccessList<E>(l, type); 6114 return new CheckedList<E>(l, type); 6115 } 6116 6117 /** 6118 * The implementation of {@link #checkedList(List,Class)} for sequential 6119 * lists. This class name is required for compatibility with Sun's JDK 6120 * serializability. 6121 * 6122 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6123 * @since 1.5 6124 */ 6125 private static class CheckedList<E> 6126 extends CheckedCollection<E> 6127 implements List<E> 6128 { 6129 /** 6130 * Compatible with JDK 1.5. 6131 */ 6132 private static final long serialVersionUID = 65247728283967356L; 6133 6134 /** 6135 * The wrapped list; stored both here and in the superclass to avoid 6136 * excessive casting. Package visible for use by subclass. 6137 * @serial the wrapped list 6138 */ 6139 final List<E> list; 6140 6141 /** 6142 * Wrap a given list. 6143 * @param l the list to wrap 6144 * @param type the type of the elements within the checked list. 6145 * @throws NullPointerException if l is null 6146 */ 6147 CheckedList(List<E> l, Class<E> type) 6148 { 6149 super(l, type); 6150 list = l; 6151 } 6152 6153 /** 6154 * Adds the supplied element to the underlying list at the specified 6155 * index, provided it is of the right type. 6156 * 6157 * @param index The index at which to place the new element. 6158 * @param o the object to add. 6159 * @throws ClassCastException if the type of the object is not a 6160 * valid type for the underlying collection. 6161 */ 6162 public void add(int index, E o) 6163 { 6164 if (type.isInstance(o)) 6165 list.add(index, o); 6166 else 6167 throw new ClassCastException("The object is of the wrong type."); 6168 } 6169 6170 /** 6171 * Adds the members of the supplied collection to the underlying 6172 * collection at the specified index, provided they are all of the 6173 * correct type. 6174 * 6175 * @param index the index at which to place the new element. 6176 * @param coll the collections of objects to add. 6177 * @throws ClassCastException if the type of any element in c is not a 6178 * valid type for the underlying collection. 6179 */ 6180 public boolean addAll(int index, Collection<? extends E> coll) 6181 { 6182 Collection<E> typedColl = (Collection<E>) coll; 6183 final Iterator<E> it = typedColl.iterator(); 6184 while (it.hasNext()) 6185 { 6186 if (!type.isInstance(it.next())) 6187 throw new ClassCastException("A member of the collection is not of the correct type."); 6188 } 6189 return list.addAll(index, coll); 6190 } 6191 6192 /** 6193 * Returns <code>true</code> if the object, o, is an instance of 6194 * <code>List</code> with the same size and elements 6195 * as the underlying list. 6196 * 6197 * @param o The object to compare. 6198 * @return <code>true</code> if o is equivalent to the underlying list. 6199 */ 6200 public boolean equals(Object o) 6201 { 6202 return list.equals(o); 6203 } 6204 6205 /** 6206 * Retrieves the element at a given index in the underlying list. 6207 * 6208 * @param index the index of the element to be returned 6209 * @return the element at the specified index in the underlying list 6210 * @throws IndexOutOfBoundsException if index < 0 || index >= size() 6211 */ 6212 public E get(int index) 6213 { 6214 return list.get(index); 6215 } 6216 6217 /** 6218 * Computes the hash code for the underlying list. 6219 * The exact computation is described in the documentation 6220 * of the <code>List</code> interface. 6221 * 6222 * @return The hash code of the underlying list. 6223 * @see List#hashCode() 6224 */ 6225 public int hashCode() 6226 { 6227 return list.hashCode(); 6228 } 6229 6230 /** 6231 * Obtain the first index at which a given object is to be found in the 6232 * underlying list. 6233 * 6234 * @param o the object to search for 6235 * @return the least integer n such that <code>o == null ? get(n) == null : 6236 * o.equals(get(n))</code>, or -1 if there is no such index. 6237 * @throws ClassCastException if the type of o is not a valid 6238 * type for the underlying list. 6239 * @throws NullPointerException if o is null and the underlying 6240 * list does not support null values. 6241 */ 6242 public int indexOf(Object o) 6243 { 6244 return list.indexOf(o); 6245 } 6246 6247 /** 6248 * Obtain the last index at which a given object is to be found in the 6249 * underlying list. 6250 * 6251 * @return the greatest integer n such that 6252 * <code>o == null ? get(n) == null : o.equals(get(n))</code>, 6253 * or -1 if there is no such index. 6254 * @throws ClassCastException if the type of o is not a valid 6255 * type for the underlying list. 6256 * @throws NullPointerException if o is null and the underlying 6257 * list does not support null values. 6258 */ 6259 public int lastIndexOf(Object o) 6260 { 6261 return list.lastIndexOf(o); 6262 } 6263 6264 /** 6265 * Obtains a list iterator over the underlying list, starting at the 6266 * beginning and maintaining the checked nature of this list. 6267 * 6268 * @return a <code>CheckedListIterator</code> over the elements of the 6269 * underlying list, in order, starting at the beginning. 6270 */ 6271 public ListIterator<E> listIterator() 6272 { 6273 return new CheckedListIterator<E>(list.listIterator(), type); 6274 } 6275 6276 /** 6277 * Obtains a list iterator over the underlying list, starting at the 6278 * specified index and maintaining the checked nature of this list. An 6279 * initial call to <code>next()</code> will retrieve the element at the 6280 * specified index, and an initial call to <code>previous()</code> will 6281 * retrieve the element at index - 1. 6282 * 6283 * @param index the position, between 0 and size() inclusive, to begin the 6284 * iteration from. 6285 * @return a <code>CheckedListIterator</code> over the elements of the 6286 * underlying list, in order, starting at the specified index. 6287 * @throws IndexOutOfBoundsException if index < 0 || index > size() 6288 */ 6289 public ListIterator<E> listIterator(int index) 6290 { 6291 return new CheckedListIterator<E>(list.listIterator(index), type); 6292 } 6293 6294 /** 6295 * Removes the element at the specified index. 6296 * 6297 * @param index The index of the element to remove. 6298 * @return the removed element. 6299 */ 6300 public E remove(int index) 6301 { 6302 return list.remove(index); 6303 } 6304 6305 /** 6306 * Replaces the element at the specified index in the underlying list 6307 * with that supplied. 6308 * 6309 * @param index the index of the element to replace. 6310 * @param o the new object to place at the specified index. 6311 * @return the replaced element. 6312 */ 6313 public E set(int index, E o) 6314 { 6315 return list.set(index, o); 6316 } 6317 6318 /** 6319 * Obtain a List view of a subsection of the underlying list, from 6320 * fromIndex (inclusive) to toIndex (exclusive). If the two indices 6321 * are equal, the sublist is empty. The returned list will be 6322 * checked, like this list. Changes to the elements of the 6323 * returned list will be reflected in the underlying list. The effect 6324 * of structural modifications is undefined. 6325 * 6326 * @param fromIndex the index that the returned list should start from 6327 * (inclusive). 6328 * @param toIndex the index that the returned list should go 6329 * to (exclusive). 6330 * @return a List backed by a subsection of the underlying list. 6331 * @throws IndexOutOfBoundsException if fromIndex < 0 6332 * || toIndex > size() || fromIndex > toIndex. 6333 */ 6334 public List<E> subList(int fromIndex, int toIndex) 6335 { 6336 return checkedList(list.subList(fromIndex, toIndex), type); 6337 } 6338 } // class CheckedList 6339 6340 /** 6341 * The implementation of {@link #checkedList(List)} for random-access 6342 * lists. This class name is required for compatibility with Sun's JDK 6343 * serializability. 6344 * 6345 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6346 * @since 1.5 6347 */ 6348 private static final class CheckedRandomAccessList<E> 6349 extends CheckedList<E> 6350 implements RandomAccess 6351 { 6352 /** 6353 * Compatible with JDK 1.5. 6354 */ 6355 private static final long serialVersionUID = 1638200125423088369L; 6356 6357 /** 6358 * Wrap a given list. 6359 * @param l the list to wrap 6360 * @param type the type of the elements within the checked list. 6361 * @throws NullPointerException if l is null 6362 */ 6363 CheckedRandomAccessList(List<E> l, Class<E> type) 6364 { 6365 super(l, type); 6366 } 6367 } // class CheckedRandomAccessList 6368 6369 /** 6370 * The implementation of {@link CheckedList#listIterator()}. 6371 * 6372 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6373 * @since 1.5 6374 */ 6375 private static final class CheckedListIterator<E> 6376 extends CheckedIterator<E> 6377 implements ListIterator<E> 6378 { 6379 /** 6380 * The wrapped iterator, stored both here and in the superclass to 6381 * avoid excessive casting. 6382 */ 6383 private final ListIterator<E> li; 6384 6385 /** 6386 * Only trusted code creates a wrapper. 6387 * @param li the wrapped iterator 6388 */ 6389 CheckedListIterator(ListIterator<E> li, Class<E> type) 6390 { 6391 super(li, type); 6392 this.li = li; 6393 } 6394 6395 /** 6396 * Adds the supplied object at the current iterator position, provided 6397 * it is of the correct type. 6398 * 6399 * @param o the object to add. 6400 * @throws ClassCastException if the type of the object is not a 6401 * valid type for the underlying collection. 6402 */ 6403 public void add(E o) 6404 { 6405 if (type.isInstance(o)) 6406 li.add(o); 6407 else 6408 throw new ClassCastException("The object is of the wrong type."); 6409 } 6410 6411 /** 6412 * Tests whether there are still elements to be retrieved from the 6413 * underlying collection by <code>previous()</code>. When this method 6414 * returns <code>true</code>, an exception will not be thrown on calling 6415 * <code>previous()</code>. 6416 * 6417 * @return <code>true</code> if there is at least one more element prior 6418 * to the current position in the underlying list. 6419 */ 6420 public boolean hasPrevious() 6421 { 6422 return li.hasPrevious(); 6423 } 6424 6425 /** 6426 * Find the index of the element that would be returned by a call to next. 6427 * If <code>hasNext()</code> returns <code>false</code>, this returns the 6428 * list size. 6429 * 6430 * @return the index of the element that would be returned by 6431 * <code>next()</code>. 6432 */ 6433 public int nextIndex() 6434 { 6435 return li.nextIndex(); 6436 } 6437 6438 /** 6439 * Obtains the previous element in the underlying list. 6440 * 6441 * @return the previous element in the list. 6442 * @throws NoSuchElementException if there are no more prior elements. 6443 */ 6444 public E previous() 6445 { 6446 return li.previous(); 6447 } 6448 6449 /** 6450 * Find the index of the element that would be returned by a call to 6451 * previous. If <code>hasPrevious()</code> returns <code>false</code>, 6452 * this returns -1. 6453 * 6454 * @return the index of the element that would be returned by 6455 * <code>previous()</code>. 6456 */ 6457 public int previousIndex() 6458 { 6459 return li.previousIndex(); 6460 } 6461 6462 /** 6463 * Sets the next element to that supplied, provided that it is of the 6464 * correct type. 6465 * 6466 * @param o The new object to replace the existing one. 6467 * @throws ClassCastException if the type of the object is not a 6468 * valid type for the underlying collection. 6469 */ 6470 public void set(E o) 6471 { 6472 if (type.isInstance(o)) 6473 li.set(o); 6474 else 6475 throw new ClassCastException("The object is of the wrong type."); 6476 } 6477 } // class CheckedListIterator 6478 6479 /** 6480 * <p> 6481 * Returns a dynamically typesafe view of the given map, 6482 * where any modification is first checked to ensure that the type 6483 * of the new data is appropriate. Although the addition of 6484 * generics and parametrically-typed collections prevents an 6485 * incorrect type of element being added to a collection at 6486 * compile-time, via static type checking, this can be overridden by 6487 * casting. In contrast, wrapping the collection within a 6488 * dynamically-typesafe wrapper, using this and associated methods, 6489 * <emph>guarantees</emph> that the collection will only contain 6490 * elements of an appropriate type (provided it only contains such 6491 * at the type of wrapping, and all subsequent access is via the 6492 * wrapper). This can be useful for debugging the cause of a 6493 * <code>ClassCastException</code> caused by erroneous casting, or 6494 * for protecting collections from corruption by external libraries. 6495 * </p> 6496 * <p> 6497 * The returned Map implements Serializable, but can only be serialized if 6498 * the map it wraps is likewise Serializable. 6499 * </p> 6500 * 6501 * @param m the map to wrap 6502 * @param keyType the dynamic type of the map's keys. 6503 * @param valueType the dynamic type of the map's values. 6504 * @return a dynamically typesafe view of the map 6505 * @see Serializable 6506 */ 6507 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, 6508 Class<V> valueType) 6509 { 6510 return new CheckedMap<K, V>(m, keyType, valueType); 6511 } 6512 6513 /** 6514 * The implementation of {@link #checkedMap(Map)}. This 6515 * class name is required for compatibility with Sun's JDK serializability. 6516 * 6517 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6518 * @since 1.5 6519 */ 6520 private static class CheckedMap<K, V> 6521 implements Map<K, V>, Serializable 6522 { 6523 /** 6524 * Compatible with JDK 1.5. 6525 */ 6526 private static final long serialVersionUID = 5742860141034234728L; 6527 6528 /** 6529 * The wrapped map. 6530 * @serial the real map 6531 */ 6532 private final Map<K, V> m; 6533 6534 /** 6535 * The type of the map's keys. 6536 * @serial the key type. 6537 */ 6538 final Class<K> keyType; 6539 6540 /** 6541 * The type of the map's values. 6542 * @serial the value type. 6543 */ 6544 final Class<V> valueType; 6545 6546 /** 6547 * Cache the entry set. 6548 */ 6549 private transient Set<Map.Entry<K, V>> entries; 6550 6551 /** 6552 * Cache the key set. 6553 */ 6554 private transient Set<K> keys; 6555 6556 /** 6557 * Cache the value collection. 6558 */ 6559 private transient Collection<V> values; 6560 6561 /** 6562 * Wrap a given map. 6563 * @param m the map to wrap 6564 * @param keyType the dynamic type of the map's keys. 6565 * @param valueType the dynamic type of the map's values. 6566 * @throws NullPointerException if m is null 6567 */ 6568 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) 6569 { 6570 this.m = m; 6571 this.keyType = keyType; 6572 this.valueType = valueType; 6573 if (m == null) 6574 throw new NullPointerException(); 6575 } 6576 6577 /** 6578 * Clears all pairs from the map. 6579 */ 6580 public void clear() 6581 { 6582 m.clear(); 6583 } 6584 6585 /** 6586 * Returns <code>true</code> if the underlying map contains a mapping for 6587 * the given key. 6588 * 6589 * @param key the key to search for 6590 * @return <code>true</code> if the map contains the key 6591 * @throws ClassCastException if the key is of an inappropriate type 6592 * @throws NullPointerException if key is <code>null</code> but the map 6593 * does not permit null keys 6594 */ 6595 public boolean containsKey(Object key) 6596 { 6597 return m.containsKey(key); 6598 } 6599 6600 /** 6601 * Returns <code>true</code> if the underlying map contains at least one 6602 * mapping with the given value. In other words, it returns 6603 * <code>true</code> if a value v exists where 6604 * <code>(value == null ? v == null : value.equals(v))</code>. 6605 * This usually requires linear time. 6606 * 6607 * @param value the value to search for 6608 * @return <code>true</code> if the map contains the value 6609 * @throws ClassCastException if the type of the value is not a valid type 6610 * for this map. 6611 * @throws NullPointerException if the value is null and the map doesn't 6612 * support null values. 6613 */ 6614 public boolean containsValue(Object value) 6615 { 6616 return m.containsValue(value); 6617 } 6618 6619 /** 6620 * <p> 6621 * Returns a checked set view of the entries in the underlying map. 6622 * Each element in the set is a unmodifiable variant of 6623 * <code>Map.Entry</code>. 6624 * </p> 6625 * <p> 6626 * The set is backed by the map, so that changes in one show up in the 6627 * other. Modifications made while an iterator is in progress cause 6628 * undefined behavior. 6629 * </p> 6630 * 6631 * @return the checked set view of all mapping entries. 6632 * @see Map.Entry 6633 */ 6634 public Set<Map.Entry<K, V>> entrySet() 6635 { 6636 if (entries == null) 6637 { 6638 Class<Map.Entry<K,V>> klass = 6639 (Class<Map.Entry<K,V>>) (Class) Map.Entry.class; 6640 entries = new CheckedEntrySet<Map.Entry<K,V>,K,V>(m.entrySet(), 6641 klass, 6642 keyType, 6643 valueType); 6644 } 6645 return entries; 6646 } 6647 6648 /** 6649 * The implementation of {@link CheckedMap#entrySet()}. This class 6650 * is <emph>not</emph> serializable. 6651 * 6652 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6653 * @since 1.5 6654 */ 6655 private static final class CheckedEntrySet<E,SK,SV> 6656 extends CheckedSet<E> 6657 { 6658 /** 6659 * The type of the map's keys. 6660 * @serial the key type. 6661 */ 6662 private final Class<SK> keyType; 6663 6664 /** 6665 * The type of the map's values. 6666 * @serial the value type. 6667 */ 6668 private final Class<SV> valueType; 6669 6670 /** 6671 * Wrap a given set of map entries. 6672 * 6673 * @param s the set to wrap. 6674 * @param type the type of the set's entries. 6675 * @param keyType the type of the map's keys. 6676 * @param valueType the type of the map's values. 6677 */ 6678 CheckedEntrySet(Set<E> s, Class<E> type, Class<SK> keyType, 6679 Class<SV> valueType) 6680 { 6681 super(s, type); 6682 this.keyType = keyType; 6683 this.valueType = valueType; 6684 } 6685 6686 // The iterator must return checked map entries. 6687 public Iterator<E> iterator() 6688 { 6689 return new CheckedIterator<E>(c.iterator(), type) 6690 { 6691 /** 6692 * Obtains the next element from the underlying set of 6693 * map entries. 6694 * 6695 * @return the next element in the collection. 6696 * @throws NoSuchElementException if there are no more elements. 6697 */ 6698 public E next() 6699 { 6700 final Map.Entry e = (Map.Entry) super.next(); 6701 return (E) new Map.Entry() 6702 { 6703 /** 6704 * Returns <code>true</code> if the object, o, is also a map 6705 * entry with an identical key and value. 6706 * 6707 * @param o the object to compare. 6708 * @return <code>true</code> if o is an equivalent map entry. 6709 */ 6710 public boolean equals(Object o) 6711 { 6712 return e.equals(o); 6713 } 6714 6715 /** 6716 * Returns the key of this map entry. 6717 * 6718 * @return the key. 6719 */ 6720 public Object getKey() 6721 { 6722 return e.getKey(); 6723 } 6724 6725 /** 6726 * Returns the value of this map entry. 6727 * 6728 * @return the value. 6729 */ 6730 public Object getValue() 6731 { 6732 return e.getValue(); 6733 } 6734 6735 /** 6736 * Computes the hash code of this map entry. 6737 * The computation is described in the <code>Map</code> 6738 * interface documentation. 6739 * 6740 * @return the hash code of this entry. 6741 * @see Map#hashCode() 6742 */ 6743 public int hashCode() 6744 { 6745 return e.hashCode(); 6746 } 6747 6748 /** 6749 * Sets the value of this map entry, provided it is of the 6750 * right type. 6751 * 6752 * @param value The new value. 6753 * @throws ClassCastException if the type of the value is not 6754 * a valid type for the underlying 6755 * map. 6756 */ 6757 public Object setValue(Object value) 6758 { 6759 if (valueType.isInstance(value)) 6760 return e.setValue(value); 6761 else 6762 throw new ClassCastException("The value is of the wrong type."); 6763 } 6764 6765 /** 6766 * Returns a textual representation of the map entry. 6767 * 6768 * @return The map entry as a <code>String</code>. 6769 */ 6770 public String toString() 6771 { 6772 return e.toString(); 6773 } 6774 }; 6775 } 6776 }; 6777 } 6778 } // class CheckedEntrySet 6779 6780 /** 6781 * Returns <code>true</code> if the object, o, is also an instance 6782 * of <code>Map</code> with an equal set of map entries. 6783 * 6784 * @param o The object to compare. 6785 * @return <code>true</code> if o is an equivalent map. 6786 */ 6787 public boolean equals(Object o) 6788 { 6789 return m.equals(o); 6790 } 6791 6792 /** 6793 * Returns the value associated with the supplied key or 6794 * null if no such mapping exists. An ambiguity can occur 6795 * if null values are accepted by the underlying map. 6796 * In this case, <code>containsKey()</code> can be used 6797 * to separate the two possible cases of a null result. 6798 * 6799 * @param key The key to look up. 6800 * @return the value associated with the key, or null if key not in map. 6801 * @throws ClassCastException if the key is an inappropriate type. 6802 * @throws NullPointerException if this map does not accept null keys. 6803 * @see #containsKey(Object) 6804 */ 6805 public V get(Object key) 6806 { 6807 return m.get(key); 6808 } 6809 6810 /** 6811 * Adds a new pair to the map, provided both the key and the value are 6812 * of the correct types. 6813 * 6814 * @param key The new key. 6815 * @param value The new value. 6816 * @return the previous value of the key, or null if there was no mapping. 6817 * @throws ClassCastException if the type of the key or the value is 6818 * not a valid type for the underlying map. 6819 */ 6820 public V put(K key, V value) 6821 { 6822 if (keyType.isInstance(key)) 6823 { 6824 if (valueType.isInstance(value)) 6825 return m.put(key,value); 6826 else 6827 throw new ClassCastException("The value is of the wrong type."); 6828 } 6829 throw new ClassCastException("The key is of the wrong type."); 6830 } 6831 6832 /** 6833 * Computes the hash code for the underlying map, as the sum 6834 * of the hash codes of all entries. 6835 * 6836 * @return The hash code of the underlying map. 6837 * @see Map.Entry#hashCode() 6838 */ 6839 public int hashCode() 6840 { 6841 return m.hashCode(); 6842 } 6843 6844 /** 6845 * Returns <code>true</code> if the underlying map contains no entries. 6846 * 6847 * @return <code>true</code> if the map is empty. 6848 */ 6849 public boolean isEmpty() 6850 { 6851 return m.isEmpty(); 6852 } 6853 6854 /** 6855 * <p> 6856 * Returns a checked set view of the keys in the underlying map. 6857 * The set is backed by the map, so that changes in one show up in the 6858 * other. 6859 * </p> 6860 * <p> 6861 * Modifications made while an iterator is in progress cause undefined 6862 * behavior. These modifications are again limited to the values of 6863 * the keys. 6864 * </p> 6865 * 6866 * @return the set view of all keys. 6867 */ 6868 public Set<K> keySet() 6869 { 6870 if (keys == null) 6871 keys = new CheckedSet<K>(m.keySet(), keyType); 6872 return keys; 6873 } 6874 6875 /** 6876 * Adds all pairs within the supplied map to the underlying map, 6877 * provided they are all have the correct key and value types. 6878 * 6879 * @param map the map, the entries of which should be added 6880 * to the underlying map. 6881 * @throws ClassCastException if the type of a key or value is 6882 * not a valid type for the underlying map. 6883 */ 6884 public void putAll(Map<? extends K, ? extends V> map) 6885 { 6886 Map<K,V> typedMap = (Map<K,V>) map; 6887 final Iterator<Map.Entry<K,V>> it = typedMap.entrySet().iterator(); 6888 while (it.hasNext()) 6889 { 6890 final Map.Entry<K,V> entry = it.next(); 6891 if (!keyType.isInstance(entry.getKey())) 6892 throw new ClassCastException("A key is of the wrong type."); 6893 if (!valueType.isInstance(entry.getValue())) 6894 throw new ClassCastException("A value is of the wrong type."); 6895 } 6896 m.putAll(typedMap); 6897 } 6898 6899 /** 6900 * Removes a pair from the map. 6901 * 6902 * @param o The key of the entry to remove. 6903 * @return The value the key was associated with, or null 6904 * if no such mapping existed. Null is also returned 6905 * if the removed entry had a null key. 6906 * @throws UnsupportedOperationException as an unmodifiable 6907 * map does not support the <code>remove</code> operation. 6908 */ 6909 public V remove(Object o) 6910 { 6911 return m.remove(o); 6912 } 6913 6914 6915 /** 6916 * Returns the number of key-value mappings in the underlying map. 6917 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE 6918 * is returned. 6919 * 6920 * @return the number of mappings. 6921 */ 6922 public int size() 6923 { 6924 return m.size(); 6925 } 6926 6927 /** 6928 * Returns a textual representation of the map. 6929 * 6930 * @return The map in the form of a <code>String</code>. 6931 */ 6932 public String toString() 6933 { 6934 return m.toString(); 6935 } 6936 6937 /** 6938 * <p> 6939 * Returns a unmodifiable collection view of the values in the underlying 6940 * map. The collection is backed by the map, so that changes in one show 6941 * up in the other. 6942 * </p> 6943 * <p> 6944 * Modifications made while an iterator is in progress cause undefined 6945 * behavior. These modifications are again limited to the values of 6946 * the keys. 6947 * </p> 6948 * 6949 * @return the collection view of all values. 6950 */ 6951 public Collection<V> values() 6952 { 6953 if (values == null) 6954 values = new CheckedCollection<V>(m.values(), valueType); 6955 return values; 6956 } 6957 } // class CheckedMap 6958 6959 /** 6960 * <p> 6961 * Returns a dynamically typesafe view of the given set, 6962 * where any modification is first checked to ensure that the type 6963 * of the new data is appropriate. Although the addition of 6964 * generics and parametrically-typed collections prevents an 6965 * incorrect type of element being added to a collection at 6966 * compile-time, via static type checking, this can be overridden by 6967 * casting. In contrast, wrapping the collection within a 6968 * dynamically-typesafe wrapper, using this and associated methods, 6969 * <emph>guarantees</emph> that the collection will only contain 6970 * elements of an appropriate type (provided it only contains such 6971 * at the type of wrapping, and all subsequent access is via the 6972 * wrapper). This can be useful for debugging the cause of a 6973 * <code>ClassCastException</code> caused by erroneous casting, or 6974 * for protecting collections from corruption by external libraries. 6975 * </p> 6976 * <p> 6977 * The returned Set implements Serializable, but can only be serialized if 6978 * the set it wraps is likewise Serializable. 6979 * </p> 6980 * 6981 * @param s the set to wrap. 6982 * @param type the type of the elements within the checked list. 6983 * @return a dynamically typesafe view of the set 6984 * @see Serializable 6985 */ 6986 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) 6987 { 6988 return new CheckedSet<E>(s, type); 6989 } 6990 6991 /** 6992 * The implementation of {@link #checkedSet(Set)}. This class 6993 * name is required for compatibility with Sun's JDK serializability. 6994 * 6995 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 6996 * @since 1.5 6997 */ 6998 private static class CheckedSet<E> 6999 extends CheckedCollection<E> 7000 implements Set<E> 7001 { 7002 /** 7003 * Compatible with JDK 1.5. 7004 */ 7005 private static final long serialVersionUID = 4694047833775013803L; 7006 7007 /** 7008 * Wrap a given set. 7009 * 7010 * @param s the set to wrap 7011 * @throws NullPointerException if s is null 7012 */ 7013 CheckedSet(Set<E> s, Class<E> type) 7014 { 7015 super(s, type); 7016 } 7017 7018 /** 7019 * Returns <code>true</code> if the object, o, is also an instance of 7020 * <code>Set</code> of the same size and with the same entries. 7021 * 7022 * @return <code>true</code> if o is an equivalent set. 7023 */ 7024 public boolean equals(Object o) 7025 { 7026 return c.equals(o); 7027 } 7028 7029 /** 7030 * Computes the hash code of this set, as the sum of the 7031 * hash codes of all elements within the set. 7032 * 7033 * @return the hash code of the set. 7034 */ 7035 public int hashCode() 7036 { 7037 return c.hashCode(); 7038 } 7039 } // class CheckedSet 7040 7041 /** 7042 * <p> 7043 * Returns a dynamically typesafe view of the given sorted map, 7044 * where any modification is first checked to ensure that the type 7045 * of the new data is appropriate. Although the addition of 7046 * generics and parametrically-typed collections prevents an 7047 * incorrect type of element being added to a collection at 7048 * compile-time, via static type checking, this can be overridden by 7049 * casting. In contrast, wrapping the collection within a 7050 * dynamically-typesafe wrapper, using this and associated methods, 7051 * <emph>guarantees</emph> that the collection will only contain 7052 * elements of an appropriate type (provided it only contains such 7053 * at the type of wrapping, and all subsequent access is via the 7054 * wrapper). This can be useful for debugging the cause of a 7055 * <code>ClassCastException</code> caused by erroneous casting, or 7056 * for protecting collections from corruption by external libraries. 7057 * </p> 7058 * <p> 7059 * The returned SortedMap implements Serializable, but can only be 7060 * serialized if the map it wraps is likewise Serializable. 7061 * </p> 7062 * 7063 * @param m the map to wrap. 7064 * @param keyType the dynamic type of the map's keys. 7065 * @param valueType the dynamic type of the map's values. 7066 * @return a dynamically typesafe view of the map 7067 * @see Serializable 7068 */ 7069 public static <K, V> SortedMap<K, V> checkedSortedMap(SortedMap<K, V> m, 7070 Class<K> keyType, 7071 Class<V> valueType) 7072 { 7073 return new CheckedSortedMap<K, V>(m, keyType, valueType); 7074 } 7075 7076 /** 7077 * The implementation of {@link #checkedSortedMap(SortedMap,Class,Class)}. 7078 * This class name is required for compatibility with Sun's JDK 7079 * serializability. 7080 * 7081 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 7082 */ 7083 private static class CheckedSortedMap<K, V> 7084 extends CheckedMap<K, V> 7085 implements SortedMap<K, V> 7086 { 7087 /** 7088 * Compatible with JDK 1.5. 7089 */ 7090 private static final long serialVersionUID = 1599671320688067438L; 7091 7092 /** 7093 * The wrapped map; stored both here and in the superclass to avoid 7094 * excessive casting. 7095 * @serial the wrapped map 7096 */ 7097 private final SortedMap<K, V> sm; 7098 7099 /** 7100 * Wrap a given map. 7101 * 7102 * @param sm the map to wrap 7103 * @param keyType the dynamic type of the map's keys. 7104 * @param valueType the dynamic type of the map's values. 7105 * @throws NullPointerException if sm is null 7106 */ 7107 CheckedSortedMap(SortedMap<K, V> sm, Class<K> keyType, Class<V> valueType) 7108 { 7109 super(sm, keyType, valueType); 7110 this.sm = sm; 7111 } 7112 7113 /** 7114 * Returns the comparator used in sorting the underlying map, 7115 * or null if it is the keys' natural ordering. 7116 * 7117 * @return the sorting comparator. 7118 */ 7119 public Comparator<? super K> comparator() 7120 { 7121 return sm.comparator(); 7122 } 7123 7124 /** 7125 * Returns the first (lowest sorted) key in the map. 7126 * 7127 * @return the first key. 7128 * @throws NoSuchElementException if this map is empty. 7129 */ 7130 public K firstKey() 7131 { 7132 return sm.firstKey(); 7133 } 7134 7135 /** 7136 * <p> 7137 * Returns a checked view of the portion of the map strictly less 7138 * than toKey. The view is backed by the underlying map, so changes in 7139 * one show up in the other. The submap supports all optional operations 7140 * of the original. This operation is equivalent to 7141 * <code>subMap(firstKey(), toKey)</code>. 7142 * </p> 7143 * <p> 7144 * The returned map throws an IllegalArgumentException any time a key is 7145 * used which is out of the range of toKey. Note that the endpoint, toKey, 7146 * is not included; if you want this value to be included, pass its 7147 * successor object in to toKey. For example, for Integers, you could 7148 * request <code>headMap(new Integer(limit.intValue() + 1))</code>. 7149 * </p> 7150 * 7151 * @param toKey the exclusive upper range of the submap. 7152 * @return the submap. 7153 * @throws ClassCastException if toKey is not comparable to the map 7154 * contents. 7155 * @throws IllegalArgumentException if this is a subMap, and toKey is out 7156 * of range. 7157 * @throws NullPointerException if toKey is null but the map does not allow 7158 * null keys. 7159 */ 7160 public SortedMap<K, V> headMap(K toKey) 7161 { 7162 return new CheckedSortedMap<K, V>(sm.headMap(toKey), keyType, valueType); 7163 } 7164 7165 /** 7166 * Returns the last (highest sorted) key in the map. 7167 * 7168 * @return the last key. 7169 * @throws NoSuchElementException if this map is empty. 7170 */ 7171 public K lastKey() 7172 { 7173 return sm.lastKey(); 7174 } 7175 7176 /** 7177 * <p> 7178 * Returns a checked view of the portion of the map greater than or 7179 * equal to fromKey, and strictly less than toKey. The view is backed by 7180 * the underlying map, so changes in one show up in the other. The submap 7181 * supports all optional operations of the original. 7182 * </p> 7183 * <p> 7184 * The returned map throws an IllegalArgumentException any time a key is 7185 * used which is out of the range of fromKey and toKey. Note that the 7186 * lower endpoint is included, but the upper is not; if you want to 7187 * change the inclusion or exclusion of an endpoint, pass its successor 7188 * object in instead. For example, for Integers, you could request 7189 * <code>subMap(new Integer(lowlimit.intValue() + 1), 7190 * new Integer(highlimit.intValue() + 1))</code> to reverse 7191 * the inclusiveness of both endpoints. 7192 * </p> 7193 * 7194 * @param fromKey the inclusive lower range of the submap. 7195 * @param toKey the exclusive upper range of the submap. 7196 * @return the submap. 7197 * @throws ClassCastException if fromKey or toKey is not comparable to 7198 * the map contents. 7199 * @throws IllegalArgumentException if this is a subMap, and fromKey or 7200 * toKey is out of range. 7201 * @throws NullPointerException if fromKey or toKey is null but the map 7202 * does not allow null keys. 7203 */ 7204 public SortedMap<K, V> subMap(K fromKey, K toKey) 7205 { 7206 return new CheckedSortedMap<K, V>(sm.subMap(fromKey, toKey), keyType, 7207 valueType); 7208 } 7209 7210 /** 7211 * <p> 7212 * Returns a checked view of the portion of the map greater than or 7213 * equal to fromKey. The view is backed by the underlying map, so changes 7214 * in one show up in the other. The submap supports all optional operations 7215 * of the original. 7216 * </p> 7217 * <p> 7218 * The returned map throws an IllegalArgumentException any time a key is 7219 * used which is out of the range of fromKey. Note that the endpoint, 7220 * fromKey, is included; if you do not want this value to be included, 7221 * pass its successor object in to fromKey. For example, for Integers, 7222 * you could request 7223 * <code>tailMap(new Integer(limit.intValue() + 1))</code>. 7224 * </p> 7225 * 7226 * @param fromKey the inclusive lower range of the submap 7227 * @return the submap 7228 * @throws ClassCastException if fromKey is not comparable to the map 7229 * contents 7230 * @throws IllegalArgumentException if this is a subMap, and fromKey is out 7231 * of range 7232 * @throws NullPointerException if fromKey is null but the map does not 7233 * allow null keys 7234 */ 7235 public SortedMap<K, V> tailMap(K fromKey) 7236 { 7237 return new CheckedSortedMap<K, V>(sm.tailMap(fromKey), keyType, 7238 valueType); 7239 } 7240 } // class CheckedSortedMap 7241 7242 /** 7243 * <p> 7244 * Returns a dynamically typesafe view of the given sorted set, 7245 * where any modification is first checked to ensure that the type 7246 * of the new data is appropriate. Although the addition of 7247 * generics and parametrically-typed collections prevents an 7248 * incorrect type of element being added to a collection at 7249 * compile-time, via static type checking, this can be overridden by 7250 * casting. In contrast, wrapping the collection within a 7251 * dynamically-typesafe wrapper, using this and associated methods, 7252 * <emph>guarantees</emph> that the collection will only contain 7253 * elements of an appropriate type (provided it only contains such 7254 * at the type of wrapping, and all subsequent access is via the 7255 * wrapper). This can be useful for debugging the cause of a 7256 * <code>ClassCastException</code> caused by erroneous casting, or 7257 * for protecting collections from corruption by external libraries. 7258 * </p> 7259 * <p> 7260 * The returned SortedSet implements Serializable, but can only be 7261 * serialized if the set it wraps is likewise Serializable. 7262 * </p> 7263 * 7264 * @param s the set to wrap. 7265 * @param type the type of the set's elements. 7266 * @return a dynamically typesafe view of the set 7267 * @see Serializable 7268 */ 7269 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, 7270 Class<E> type) 7271 { 7272 return new CheckedSortedSet<E>(s, type); 7273 } 7274 7275 /** 7276 * The implementation of {@link #checkedSortedSet(SortedSet,Class)}. This 7277 * class name is required for compatibility with Sun's JDK serializability. 7278 * 7279 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 7280 * @since 1.5 7281 */ 7282 private static class CheckedSortedSet<E> 7283 extends CheckedSet<E> 7284 implements SortedSet<E> 7285 { 7286 /** 7287 * Compatible with JDK 1.4. 7288 */ 7289 private static final long serialVersionUID = 1599911165492914959L; 7290 7291 /** 7292 * The wrapped set; stored both here and in the superclass to avoid 7293 * excessive casting. 7294 * 7295 * @serial the wrapped set 7296 */ 7297 private SortedSet<E> ss; 7298 7299 /** 7300 * Wrap a given set. 7301 * 7302 * @param ss the set to wrap. 7303 * @param type the type of the set's elements. 7304 * @throws NullPointerException if ss is null 7305 */ 7306 CheckedSortedSet(SortedSet<E> ss, Class<E> type) 7307 { 7308 super(ss, type); 7309 this.ss = ss; 7310 } 7311 7312 /** 7313 * Returns the comparator used in sorting the underlying set, 7314 * or null if it is the elements' natural ordering. 7315 * 7316 * @return the sorting comparator 7317 */ 7318 public Comparator<? super E> comparator() 7319 { 7320 return ss.comparator(); 7321 } 7322 7323 /** 7324 * Returns the first (lowest sorted) element in the underlying 7325 * set. 7326 * 7327 * @return the first element. 7328 * @throws NoSuchElementException if the set is empty. 7329 */ 7330 public E first() 7331 { 7332 return ss.first(); 7333 } 7334 7335 /** 7336 * <p> 7337 * Returns a checked view of the portion of the set strictly 7338 * less than toElement. The view is backed by the underlying set, 7339 * so changes in one show up in the other. The subset supports 7340 * all optional operations of the original. This operation 7341 * is equivalent to <code>subSet(first(), toElement)</code>. 7342 * </p> 7343 * <p> 7344 * The returned set throws an IllegalArgumentException any time an 7345 * element is used which is out of the range of toElement. Note that 7346 * the endpoint, toElement, is not included; if you want this value 7347 * included, pass its successor object in to toElement. For example, 7348 * for Integers, you could request 7349 * <code>headSet(new Integer(limit.intValue() + 1))</code>. 7350 * </p> 7351 * 7352 * @param toElement the exclusive upper range of the subset 7353 * @return the subset. 7354 * @throws ClassCastException if toElement is not comparable to the set 7355 * contents. 7356 * @throws IllegalArgumentException if this is a subSet, and toElement is 7357 * out of range. 7358 * @throws NullPointerException if toElement is null but the set does not 7359 * allow null elements. 7360 */ 7361 public SortedSet<E> headSet(E toElement) 7362 { 7363 return new CheckedSortedSet<E>(ss.headSet(toElement), type); 7364 } 7365 7366 /** 7367 * Returns the last (highest sorted) element in the underlying 7368 * set. 7369 * 7370 * @return the last element. 7371 * @throws NoSuchElementException if the set is empty. 7372 */ 7373 public E last() 7374 { 7375 return ss.last(); 7376 } 7377 7378 /** 7379 * <p> 7380 * Returns a checked view of the portion of the set greater than or 7381 * equal to fromElement, and strictly less than toElement. The view is 7382 * backed by the underlying set, so changes in one show up in the other. 7383 * The subset supports all optional operations of the original. 7384 * </p> 7385 * <p> 7386 * The returned set throws an IllegalArgumentException any time an 7387 * element is used which is out of the range of fromElement and toElement. 7388 * Note that the lower endpoint is included, but the upper is not; if you 7389 * want to change the inclusion or exclusion of an endpoint, pass its 7390 * successor object in instead. For example, for Integers, you can request 7391 * <code>subSet(new Integer(lowlimit.intValue() + 1), 7392 * new Integer(highlimit.intValue() + 1))</code> to reverse 7393 * the inclusiveness of both endpoints. 7394 * </p> 7395 * 7396 * @param fromElement the inclusive lower range of the subset. 7397 * @param toElement the exclusive upper range of the subset. 7398 * @return the subset. 7399 * @throws ClassCastException if fromElement or toElement is not comparable 7400 * to the set contents. 7401 * @throws IllegalArgumentException if this is a subSet, and fromElement or 7402 * toElement is out of range. 7403 * @throws NullPointerException if fromElement or toElement is null but the 7404 * set does not allow null elements. 7405 */ 7406 public SortedSet<E> subSet(E fromElement, E toElement) 7407 { 7408 return new CheckedSortedSet<E>(ss.subSet(fromElement, toElement), type); 7409 } 7410 7411 /** 7412 * <p> 7413 * Returns a checked view of the portion of the set greater than or equal 7414 * to fromElement. The view is backed by the underlying set, so changes in 7415 * one show up in the other. The subset supports all optional operations 7416 * of the original. 7417 * </p> 7418 * <p> 7419 * The returned set throws an IllegalArgumentException any time an 7420 * element is used which is out of the range of fromElement. Note that 7421 * the endpoint, fromElement, is included; if you do not want this value 7422 * to be included, pass its successor object in to fromElement. For 7423 * example, for Integers, you could request 7424 * <code>tailSet(new Integer(limit.intValue() + 1))</code>. 7425 * </p> 7426 * 7427 * @param fromElement the inclusive lower range of the subset 7428 * @return the subset. 7429 * @throws ClassCastException if fromElement is not comparable to the set 7430 * contents. 7431 * @throws IllegalArgumentException if this is a subSet, and fromElement is 7432 * out of range. 7433 * @throws NullPointerException if fromElement is null but the set does not 7434 * allow null elements. 7435 */ 7436 public SortedSet<E> tailSet(E fromElement) 7437 { 7438 return new CheckedSortedSet<E>(ss.tailSet(fromElement), type); 7439 } 7440 } // class CheckedSortedSet 7441 7442 /** 7443 * Returns a view of a {@link Deque} as a stack or LIFO (Last-In-First-Out) 7444 * {@link Queue}. Each call to the LIFO queue corresponds to one 7445 * equivalent method call to the underlying deque, with the exception 7446 * of {@link Collection#addAll(Collection)}, which is emulated by a series 7447 * of {@link Deque#push(E)} calls. 7448 * 7449 * @param deque the deque to convert to a LIFO queue. 7450 * @return a LIFO queue. 7451 * @since 1.6 7452 */ 7453 public static <T> Queue<T> asLifoQueue(Deque<T> deque) 7454 { 7455 return new LIFOQueue<T>(deque); 7456 } 7457 7458 /** 7459 * Returns a set backed by the supplied map. The resulting set 7460 * has the same performance, concurrency and ordering characteristics 7461 * as the original map. The supplied map must be empty and should not 7462 * be used after the set is created. Each call to the set corresponds 7463 * to one equivalent method call to the underlying map, with the exception 7464 * of {@link Set#addAll(Collection)} which is emulated by a series of 7465 * calls to <code>put</code>. 7466 * 7467 * @param map the map to convert to a set. 7468 * @return a set backed by the supplied map. 7469 * @throws IllegalArgumentException if the map is not empty. 7470 * @since 1.6 7471 */ 7472 public static <E> Set<E> newSetFromMap(Map<E,Boolean> map) 7473 { 7474 return new MapSet<E>(map); 7475 } 7476 7477 /** 7478 * The implementation of {@link #asLIFOQueue(Deque)}. 7479 * 7480 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 7481 * @since 1.6 7482 */ 7483 private static class LIFOQueue<T> 7484 extends AbstractQueue<T> 7485 { 7486 7487 /** 7488 * The backing deque. 7489 */ 7490 private Deque<T> deque; 7491 7492 /** 7493 * Constructs a new {@link LIFOQueue} with the specified 7494 * backing {@link Deque}. 7495 * 7496 * @param deque the backing deque. 7497 */ 7498 public LIFOQueue(Deque<T> deque) 7499 { 7500 this.deque = deque; 7501 } 7502 7503 public boolean add(T e) 7504 { 7505 return deque.offerFirst(e); 7506 } 7507 7508 public boolean addAll(Collection<? extends T> c) 7509 { 7510 boolean result = false; 7511 final Iterator<? extends T> it = c.iterator(); 7512 while (it.hasNext()) 7513 result |= deque.offerFirst(it.next()); 7514 return result; 7515 } 7516 7517 public void clear() 7518 { 7519 deque.clear(); 7520 } 7521 7522 public boolean isEmpty() 7523 { 7524 return deque.isEmpty(); 7525 } 7526 7527 public Iterator<T> iterator() 7528 { 7529 return deque.iterator(); 7530 } 7531 7532 public boolean offer(T e) 7533 { 7534 return deque.offerFirst(e); 7535 } 7536 7537 public T peek() 7538 { 7539 return deque.peek(); 7540 } 7541 7542 public T poll() 7543 { 7544 return deque.poll(); 7545 } 7546 7547 public int size() 7548 { 7549 return deque.size(); 7550 } 7551 } // class LIFOQueue 7552 7553 /** 7554 * The implementation of {@link #newSetFromMap(Map)}. 7555 * 7556 * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 7557 * @since 1.6 7558 */ 7559 private static class MapSet<E> 7560 extends AbstractSet<E> 7561 { 7562 7563 /** 7564 * The backing map. 7565 */ 7566 private Map<E,Boolean> map; 7567 7568 /** 7569 * Constructs a new {@link MapSet} using the specified 7570 * backing {@link Map}. 7571 * 7572 * @param map the backing map. 7573 * @throws IllegalArgumentException if the map is not empty. 7574 */ 7575 public MapSet(Map<E,Boolean> map) 7576 { 7577 if (!map.isEmpty()) 7578 throw new IllegalArgumentException("The map must be empty."); 7579 this.map = map; 7580 } 7581 7582 public boolean add(E e) 7583 { 7584 return map.put(e, true) == null; 7585 } 7586 7587 public boolean addAll(Collection<? extends E> c) 7588 { 7589 boolean result = false; 7590 final Iterator<? extends E> it = c.iterator(); 7591 while (it.hasNext()) 7592 result |= (map.put(it.next(), true) == null); 7593 return result; 7594 } 7595 7596 public void clear() 7597 { 7598 map.clear(); 7599 } 7600 7601 public boolean contains(Object o) 7602 { 7603 return map.containsKey(o); 7604 } 7605 7606 public boolean isEmpty() 7607 { 7608 return map.isEmpty(); 7609 } 7610 7611 public Iterator<E> iterator() 7612 { 7613 return map.keySet().iterator(); 7614 } 7615 7616 public boolean remove(Object o) 7617 { 7618 return map.remove(o) != null; 7619 } 7620 7621 public int size() 7622 { 7623 return map.size(); 7624 } 7625 } // class MapSet 7626 7627} // class Collections