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