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