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