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 java.io.Serializable; 43: 44: /** 45: * Utility class consisting of static methods that operate on, or return 46: * Collections. Contains methods to sort, search, reverse, fill and shuffle 47: * Collections, methods to facilitate interoperability with legacy APIs that 48: * are unaware of collections, a method to return a list which consists of 49: * multiple copies of one element, and methods which "wrap" collections to give 50: * them extra properties, such as thread-safety and unmodifiability. 51: * <p> 52: * 53: * All methods which take a collection throw a {@link NullPointerException} if 54: * that collection is null. Algorithms which can change a collection may, but 55: * are not required, to throw the {@link UnsupportedOperationException} that 56: * the underlying collection would throw during an attempt at modification. 57: * For example, 58: * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code> 59: * does not throw a exception, even though addAll is an unsupported operation 60: * on a singleton; the reason for this is that addAll did not attempt to 61: * modify the set. 62: * 63: * @author Original author unknown 64: * @author Eric Blake (ebb9@email.byu.edu) 65: * @see Collection 66: * @see Set 67: * @see List 68: * @see Map 69: * @see Arrays 70: * @since 1.2 71: * @status updated to 1.4 72: */ 73: public class Collections 74: { 75: /** 76: * Constant used to decide cutoff for when a non-RandomAccess list should 77: * be treated as sequential-access. Basically, quadratic behavior is 78: * acceptable for small lists when the overhead is so small in the first 79: * place. I arbitrarily set it to 16, so it may need some tuning. 80: */ 81: private static final int LARGE_LIST_SIZE = 16; 82: 83: /** 84: * Determines if a list should be treated as a sequential-access one. 85: * Rather than the old method of JDK 1.3 of assuming only instanceof 86: * AbstractSequentialList should be sequential, this uses the new method 87: * of JDK 1.4 of assuming anything that does NOT implement RandomAccess 88: * and exceeds a large (unspecified) size should be sequential. 89: * 90: * @param l the list to check 91: * @return <code>true</code> if it should be treated as sequential-access 92: */ 93: private static boolean isSequential(List l) 94: { 95: return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE; 96: } 97: 98: /** 99: * This class is non-instantiable. 100: */ 101: private Collections() 102: { 103: } 104: 105: /** 106: * An immutable, serializable, empty Set. 107: * @see Serializable 108: */ 109: public static final Set EMPTY_SET = new EmptySet(); 110: 111: /** 112: * The implementation of {@link #EMPTY_SET}. This class name is required 113: * for compatibility with Sun's JDK serializability. 114: * 115: * @author Eric Blake (ebb9@email.byu.edu) 116: */ 117: private static final class EmptySet extends AbstractSet 118: implements Serializable 119: { 120: /** 121: * Compatible with JDK 1.4. 122: */ 123: private static final long serialVersionUID = 1582296315990362920L; 124: 125: /** 126: * A private constructor adds overhead. 127: */ 128: EmptySet() 129: { 130: } 131: 132: /** 133: * The size: always 0! 134: * @return 0. 135: */ 136: public int size() 137: { 138: return 0; 139: } 140: 141: /** 142: * Returns an iterator that does not iterate. 143: * @return A non-iterating iterator. 144: */ 145: // This is really cheating! I think it's perfectly valid, though. 146: public Iterator iterator() 147: { 148: return EMPTY_LIST.iterator(); 149: } 150: 151: // The remaining methods are optional, but provide a performance 152: // advantage by not allocating unnecessary iterators in AbstractSet. 153: /** 154: * The empty set never contains anything. 155: * @param o The object to search for. 156: * @return <code>false</code>. 157: */ 158: public boolean contains(Object o) 159: { 160: return false; 161: } 162: 163: /** 164: * This is true only if the given collection is also empty. 165: * @param c The collection of objects which are to be compared 166: * against the members of this set. 167: * @return <code>true</code> if c is empty. 168: */ 169: public boolean containsAll(Collection c) 170: { 171: return c.isEmpty(); 172: } 173: 174: /** 175: * Equal only if the other set is empty. 176: * @param o The object to compare with this set. 177: * @return <code>true</code> if o is an empty instance of <code>Set</code>. 178: */ 179: public boolean equals(Object o) 180: { 181: return o instanceof Set && ((Set) o).isEmpty(); 182: } 183: 184: /** 185: * The hashcode is always 0. 186: * @return 0. 187: */ 188: public int hashCode() 189: { 190: return 0; 191: } 192: 193: /** 194: * Always succeeds with a <code>false</code> result. 195: * @param o The object to remove. 196: * @return <code>false</code>. 197: */ 198: public boolean remove(Object o) 199: { 200: return false; 201: } 202: 203: /** 204: * Always succeeds with a <code>false</code> result. 205: * @param c The collection of objects which should 206: * all be removed from this set. 207: * @return <code>false</code>. 208: */ 209: public boolean removeAll(Collection c) 210: { 211: return false; 212: } 213: 214: /** 215: * Always succeeds with a <code>false</code> result. 216: * @param c The collection of objects which should 217: * all be retained within this set. 218: * @return <code>false</code>. 219: */ 220: public boolean retainAll(Collection c) 221: { 222: return false; 223: } 224: 225: /** 226: * The array is always empty. 227: * @return A new array with a size of 0. 228: */ 229: public Object[] toArray() 230: { 231: return new Object[0]; 232: } 233: 234: /** 235: * We don't even need to use reflection! 236: * @param a An existing array, which can be empty. 237: * @return The original array with any existing 238: * initial element set to null. 239: */ 240: public Object[] toArray(Object[] a) 241: { 242: if (a.length > 0) 243: a[0] = null; 244: return a; 245: } 246: 247: /** 248: * The string never changes. 249: * 250: * @return the string "[]". 251: */ 252: public String toString() 253: { 254: return "[]"; 255: } 256: } // class EmptySet 257: 258: /** 259: * An immutable, serializable, empty List, which implements RandomAccess. 260: * @see Serializable 261: * @see RandomAccess 262: */ 263: public static final List EMPTY_LIST = new EmptyList(); 264: 265: /** 266: * The implementation of {@link #EMPTY_LIST}. This class name is required 267: * for compatibility with Sun's JDK serializability. 268: * 269: * @author Eric Blake (ebb9@email.byu.edu) 270: */ 271: private static final class EmptyList extends AbstractList 272: implements Serializable, RandomAccess 273: { 274: /** 275: * Compatible with JDK 1.4. 276: */ 277: private static final long serialVersionUID = 8842843931221139166L; 278: 279: /** 280: * A private constructor adds overhead. 281: */ 282: EmptyList() 283: { 284: } 285: 286: /** 287: * The size is always 0. 288: * @return 0. 289: */ 290: public int size() 291: { 292: return 0; 293: } 294: 295: /** 296: * No matter the index, it is out of bounds. This 297: * method never returns, throwing an exception instead. 298: * 299: * @param index The index of the element to retrieve. 300: * @return the object at the specified index. 301: * @throws IndexOutOfBoundsException as any given index 302: * is outside the bounds of an empty array. 303: */ 304: public Object get(int index) 305: { 306: throw new IndexOutOfBoundsException(); 307: } 308: 309: // The remaining methods are optional, but provide a performance 310: // advantage by not allocating unnecessary iterators in AbstractList. 311: /** 312: * Never contains anything. 313: * @param o The object to search for. 314: * @return <code>false</code>. 315: */ 316: public boolean contains(Object o) 317: { 318: return false; 319: } 320: 321: /** 322: * This is true only if the given collection is also empty. 323: * @param c The collection of objects, which should be compared 324: * against the members of this list. 325: * @return <code>true</code> if c is also empty. 326: */ 327: public boolean containsAll(Collection c) 328: { 329: return c.isEmpty(); 330: } 331: 332: /** 333: * Equal only if the other list is empty. 334: * @param o The object to compare against this list. 335: * @return <code>true</code> if o is also an empty instance of 336: * <code>List</code>. 337: */ 338: public boolean equals(Object o) 339: { 340: return o instanceof List && ((List) o).isEmpty(); 341: } 342: 343: /** 344: * The hashcode is always 1. 345: * @return 1. 346: */ 347: public int hashCode() 348: { 349: return 1; 350: } 351: 352: /** 353: * Returns -1. 354: * @param o The object to search for. 355: * @return -1. 356: */ 357: public int indexOf(Object o) 358: { 359: return -1; 360: } 361: 362: /** 363: * Returns -1. 364: * @param o The object to search for. 365: * @return -1. 366: */ 367: public int lastIndexOf(Object o) 368: { 369: return -1; 370: } 371: 372: /** 373: * Always succeeds with <code>false</code> result. 374: * @param o The object to remove. 375: * @return -1. 376: */ 377: public boolean remove(Object o) 378: { 379: return false; 380: } 381: 382: /** 383: * Always succeeds with <code>false</code> result. 384: * @param c The collection of objects which should 385: * all be removed from this list. 386: * @return <code>false</code>. 387: */ 388: public boolean removeAll(Collection c) 389: { 390: return false; 391: } 392: 393: /** 394: * Always succeeds with <code>false</code> result. 395: * @param c The collection of objects which should 396: * all be retained within this list. 397: * @return <code>false</code>. 398: */ 399: public boolean retainAll(Collection c) 400: { 401: return false; 402: } 403: 404: /** 405: * The array is always empty. 406: * @return A new array with a size of 0. 407: */ 408: public Object[] toArray() 409: { 410: return new Object[0]; 411: } 412: 413: /** 414: * We don't even need to use reflection! 415: * @param a An existing array, which can be empty. 416: * @return The original array with any existing 417: * initial element set to null. 418: */ 419: public Object[] toArray(Object[] a) 420: { 421: if (a.length > 0) 422: a[0] = null; 423: return a; 424: } 425: 426: /** 427: * The string never changes. 428: * 429: * @return the string "[]". 430: */ 431: public String toString() 432: { 433: return "[]"; 434: } 435: } // class EmptyList 436: 437: /** 438: * An immutable, serializable, empty Map. 439: * @see Serializable 440: */ 441: public static final Map EMPTY_MAP = new EmptyMap(); 442: 443: /** 444: * The implementation of {@link #EMPTY_MAP}. This class name is required 445: * for compatibility with Sun's JDK serializability. 446: * 447: * @author Eric Blake (ebb9@email.byu.edu) 448: */ 449: private static final class EmptyMap extends AbstractMap 450: implements Serializable 451: { 452: /** 453: * Compatible with JDK 1.4. 454: */ 455: private static final long serialVersionUID = 6428348081105594320L; 456: 457: /** 458: * A private constructor adds overhead. 459: */ 460: EmptyMap() 461: { 462: } 463: 464: /** 465: * There are no entries. 466: * @return The empty set. 467: */ 468: public Set entrySet() 469: { 470: return EMPTY_SET; 471: } 472: 473: // The remaining methods are optional, but provide a performance 474: // advantage by not allocating unnecessary iterators in AbstractMap. 475: /** 476: * No entries! 477: * @param key The key to search for. 478: * @return <code>false</code>. 479: */ 480: public boolean containsKey(Object key) 481: { 482: return false; 483: } 484: 485: /** 486: * No entries! 487: * @param value The value to search for. 488: * @return <code>false</code>. 489: */ 490: public boolean containsValue(Object value) 491: { 492: return false; 493: } 494: 495: /** 496: * Equal to all empty maps. 497: * @param o The object o to compare against this map. 498: * @return <code>true</code> if o is also an empty instance of 499: * <code>Map</code>. 500: */ 501: public boolean equals(Object o) 502: { 503: return o instanceof Map && ((Map) o).isEmpty(); 504: } 505: 506: /** 507: * No mappings, so this returns null. 508: * @param o The key of the object to retrieve. 509: * @return null. 510: */ 511: public Object get(Object o) 512: { 513: return null; 514: } 515: 516: /** 517: * The hashcode is always 0. 518: * @return 0. 519: */ 520: public int hashCode() 521: { 522: return 0; 523: } 524: 525: /** 526: * No entries. 527: * @return The empty set. 528: */ 529: public Set keySet() 530: { 531: return EMPTY_SET; 532: } 533: 534: /** 535: * Remove always succeeds, with null result. 536: * @param o The key of the mapping to remove. 537: * @return null, as there is never a mapping for o. 538: */ 539: public Object remove(Object o) 540: { 541: return null; 542: } 543: 544: /** 545: * Size is always 0. 546: * @return 0. 547: */ 548: public int size() 549: { 550: return 0; 551: } 552: 553: /** 554: * No entries. Technically, EMPTY_SET, while more specific than a general 555: * Collection, will work. Besides, that's what the JDK uses! 556: * @return The empty set. 557: */ 558: public Collection values() 559: { 560: return EMPTY_SET; 561: } 562: 563: /** 564: * The string never changes. 565: * 566: * @return the string "[]". 567: */ 568: public String toString() 569: { 570: return "[]"; 571: } 572: } // class EmptyMap 573: 574: 575: /** 576: * Compare two objects with or without a Comparator. If c is null, uses the 577: * natural ordering. Slightly slower than doing it inline if the JVM isn't 578: * clever, but worth it for removing a duplicate of the search code. 579: * Note: This code is also used in Arrays (for sort as well as search). 580: */ 581: static final int compare(Object o1, Object o2, Comparator c) 582: { 583: return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2); 584: } 585: 586: /** 587: * Perform a binary search of a List for a key, using the natural ordering of 588: * the elements. The list must be sorted (as by the sort() method) - if it is 589: * not, the behavior of this method is undefined, and may be an infinite 590: * loop. Further, the key must be comparable with every item in the list. If 591: * the list contains the key more than once, any one of them may be found. 592: * <p> 593: * 594: * This algorithm behaves in log(n) time for {@link RandomAccess} lists, 595: * and uses a linear search with O(n) link traversals and log(n) comparisons 596: * with {@link AbstractSequentialList} lists. Note: although the 597: * specification allows for an infinite loop if the list is unsorted, it will 598: * not happen in this (Classpath) implementation. 599: * 600: * @param l the list to search (must be sorted) 601: * @param key the value to search for 602: * @return the index at which the key was found, or -n-1 if it was not 603: * found, where n is the index of the first value higher than key or 604: * a.length if there is no such value 605: * @throws ClassCastException if key could not be compared with one of the 606: * elements of l 607: * @throws NullPointerException if a null element has compareTo called 608: * @see #sort(List) 609: */ 610: public static int binarySearch(List l, Object key) 611: { 612: return binarySearch(l, key, null); 613: } 614: 615: /** 616: * Perform a binary search of a List for a key, using a supplied Comparator. 617: * The list must be sorted (as by the sort() method with the same Comparator) 618: * - if it is not, the behavior of this method is undefined, and may be an 619: * infinite loop. Further, the key must be comparable with every item in the 620: * list. If the list contains the key more than once, any one of them may be 621: * found. If the comparator is null, the elements' natural ordering is used. 622: * <p> 623: * 624: * This algorithm behaves in log(n) time for {@link RandomAccess} lists, 625: * and uses a linear search with O(n) link traversals and log(n) comparisons 626: * with {@link AbstractSequentialList} lists. Note: although the 627: * specification allows for an infinite loop if the list is unsorted, it will 628: * not happen in this (Classpath) implementation. 629: * 630: * @param l the list to search (must be sorted) 631: * @param key the value to search for 632: * @param c the comparator by which the list is sorted 633: * @return the index at which the key was found, or -n-1 if it was not 634: * found, where n is the index of the first value higher than key or 635: * a.length if there is no such value 636: * @throws ClassCastException if key could not be compared with one of the 637: * elements of l 638: * @throws NullPointerException if a null element is compared with natural 639: * ordering (only possible when c is null) 640: * @see #sort(List, Comparator) 641: */ 642: public static int binarySearch(List l, Object key, Comparator c) 643: { 644: int pos = 0; 645: int low = 0; 646: int hi = l.size() - 1; 647: 648: // We use a linear search with log(n) comparisons using an iterator 649: // if the list is sequential-access. 650: if (isSequential(l)) 651: { 652: ListIterator itr = l.listIterator(); 653: int i = 0; 654: Object o = itr.next(); // Assumes list is not empty (see isSequential) 655: boolean forward = true; 656: while (low <= hi) 657: { 658: pos = (low + hi) >>> 1; 659: if (i < pos) 660: { 661: if (!forward) 662: itr.next(); // Changing direction first. 663: for ( ; i != pos; i++, o = itr.next()); 664: forward = true; 665: } 666: else 667: { 668: if (forward) 669: itr.previous(); // Changing direction first. 670: for ( ; i != pos; i--, o = itr.previous()); 671: forward = false; 672: } 673: final int d = compare(o, key, c); 674: if (d == 0) 675: return pos; 676: else if (d > 0) 677: hi = pos - 1; 678: else 679: // This gets the insertion point right on the last loop 680: low = ++pos; 681: } 682: } 683: else 684: { 685: while (low <= hi) 686: { 687: pos = (low + hi) >>> 1; 688: final int d = compare(l.get(pos), key, c); 689: if (d == 0) 690: return pos; 691: else if (d > 0) 692: hi = pos - 1; 693: else 694: // This gets the insertion point right on the last loop 695: low = ++pos; 696: } 697: } 698: 699: // If we failed to find it, we do the same whichever search we did. 700: return -pos - 1; 701: } 702: 703: /** 704: * Copy one list to another. If the destination list is longer than the 705: * source list, the remaining elements are unaffected. This method runs in 706: * linear time. 707: * 708: * @param dest the destination list 709: * @param source the source list 710: * @throws IndexOutOfBoundsException if the destination list is shorter 711: * than the source list (the destination will be unmodified) 712: * @throws UnsupportedOperationException if dest.listIterator() does not 713: * support the set operation 714: */ 715: public static void copy(List dest, List source) 716: { 717: int pos = source.size(); 718: if (dest.size() < pos) 719: throw new IndexOutOfBoundsException("Source does not fit in dest"); 720: 721: Iterator i1 = source.iterator(); 722: ListIterator i2 = dest.listIterator(); 723: 724: while (--pos >= 0) 725: { 726: i2.next(); 727: i2.set(i1.next()); 728: } 729: } 730: 731: /** 732: * Returns an Enumeration over a collection. This allows interoperability 733: * with legacy APIs that require an Enumeration as input. 734: * 735: * @param c the Collection to iterate over 736: * @return an Enumeration backed by an Iterator over c 737: */ 738: public static Enumeration enumeration(Collection c) 739: { 740: final Iterator i = c.iterator(); 741: return new Enumeration() 742: { 743: /** 744: * Returns <code>true</code> if there are more elements to 745: * be enumerated. 746: * 747: * @return The result of <code>hasNext()</code> 748: * called on the underlying iterator. 749: */ 750: public final boolean hasMoreElements() 751: { 752: return i.hasNext(); 753: } 754: 755: /** 756: * Returns the next element to be enumerated. 757: * 758: * @return The result of <code>next()</code> 759: * called on the underlying iterator. 760: */ 761: public final Object nextElement() 762: { 763: return i.next(); 764: } 765: }; 766: } 767: 768: /** 769: * Replace every element of a list with a given value. This method runs in 770: * linear time. 771: * 772: * @param l the list to fill. 773: * @param val the object to vill the list with. 774: * @throws UnsupportedOperationException if l.listIterator() does not 775: * support the set operation. 776: */ 777: public static void fill(List l, Object val) 778: { 779: ListIterator itr = l.listIterator(); 780: for (int i = l.size() - 1; i >= 0; --i) 781: { 782: itr.next(); 783: itr.set(val); 784: } 785: } 786: 787: /** 788: * Returns the starting index where the specified sublist first occurs 789: * in a larger list, or -1 if there is no matching position. If 790: * <code>target.size() > source.size()</code>, this returns -1, 791: * otherwise this implementation uses brute force, checking for 792: * <code>source.sublist(i, i + target.size()).equals(target)</code> 793: * for all possible i. 794: * 795: * @param source the list to search 796: * @param target the sublist to search for 797: * @return the index where found, or -1 798: * @since 1.4 799: */ 800: public static int indexOfSubList(List source, List target) 801: { 802: int ssize = source.size(); 803: for (int i = 0, j = target.size(); j <= ssize; i++, j++) 804: if (source.subList(i, j).equals(target)) 805: return i; 806: return -1; 807: } 808: 809: /** 810: * Returns the starting index where the specified sublist last occurs 811: * in a larger list, or -1 if there is no matching position. If 812: * <code>target.size() > source.size()</code>, this returns -1, 813: * otherwise this implementation uses brute force, checking for 814: * <code>source.sublist(i, i + target.size()).equals(target)</code> 815: * for all possible i. 816: * 817: * @param source the list to search 818: * @param target the sublist to search for 819: * @return the index where found, or -1 820: * @since 1.4 821: */ 822: public static int lastIndexOfSubList(List source, List target) 823: { 824: int ssize = source.size(); 825: for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--) 826: if (source.subList(i, j).equals(target)) 827: return i; 828: return -1; 829: } 830: 831: /** 832: * Returns an ArrayList holding the elements visited by a given 833: * Enumeration. This method exists for interoperability between legacy 834: * APIs and the new Collection API. 835: * 836: * @param e the enumeration to put in a list 837: * @return a list containing the enumeration elements 838: * @see ArrayList 839: * @since 1.4 840: */ 841: public static ArrayList list(Enumeration e) 842: { 843: ArrayList l = new ArrayList(); 844: while (e.hasMoreElements()) 845: l.add(e.nextElement()); 846: return l; 847: } 848: 849: /** 850: * Find the maximum element in a Collection, according to the natural 851: * ordering of the elements. This implementation iterates over the 852: * Collection, so it works in linear time. 853: * 854: * @param c the Collection to find the maximum element of 855: * @return the maximum element of c 856: * @exception NoSuchElementException if c is empty 857: * @exception ClassCastException if elements in c are not mutually comparable 858: * @exception NullPointerException if null.compareTo is called 859: */ 860: public static Object max(Collection c) 861: { 862: return max(c, null); 863: } 864: 865: /** 866: * Find the maximum element in a Collection, according to a specified 867: * Comparator. This implementation iterates over the Collection, so it 868: * works in linear time. 869: * 870: * @param c the Collection to find the maximum element of 871: * @param order the Comparator to order the elements by, or null for natural 872: * ordering 873: * @return the maximum element of c 874: * @throws NoSuchElementException if c is empty 875: * @throws ClassCastException if elements in c are not mutually comparable 876: * @throws NullPointerException if null is compared by natural ordering 877: * (only possible when order is null) 878: */ 879: public static Object max(Collection c, Comparator order) 880: { 881: Iterator itr = c.iterator(); 882: Object max = itr.next(); // throws NoSuchElementException 883: int csize = c.size(); 884: for (int i = 1; i < csize; i++) 885: { 886: Object o = itr.next(); 887: if (compare(max, o, order) < 0) 888: max = o; 889: } 890: return max; 891: } 892: 893: /** 894: * Find the minimum element in a Collection, according to the natural 895: * ordering of the elements. This implementation iterates over the 896: * Collection, so it works in linear time. 897: * 898: * @param c the Collection to find the minimum element of 899: * @return the minimum element of c 900: * @throws NoSuchElementException if c is empty 901: * @throws ClassCastException if elements in c are not mutually comparable 902: * @throws NullPointerException if null.compareTo is called 903: */ 904: public static Object min(Collection c) 905: { 906: return min(c, null); 907: } 908: 909: /** 910: * Find the minimum element in a Collection, according to a specified 911: * Comparator. This implementation iterates over the Collection, so it 912: * works in linear time. 913: * 914: * @param c the Collection to find the minimum element of 915: * @param order the Comparator to order the elements by, or null for natural 916: * ordering 917: * @return the minimum element of c 918: * @throws NoSuchElementException if c is empty 919: * @throws ClassCastException if elements in c are not mutually comparable 920: * @throws NullPointerException if null is compared by natural ordering 921: * (only possible when order is null) 922: */ 923: public static Object min(Collection c, Comparator order) 924: { 925: Iterator itr = c.iterator(); 926: Object min = itr.next(); // throws NoSuchElementExcception 927: int csize = c.size(); 928: for (int i = 1; i < csize; i++) 929: { 930: Object o = itr.next(); 931: if (compare(min, o, order) > 0) 932: min = o; 933: } 934: return min; 935: } 936: 937: /** 938: * Creates an immutable list consisting of the same object repeated n times. 939: * The returned object is tiny, consisting of only a single reference to the 940: * object and a count of the number of elements. It is Serializable, and 941: * implements RandomAccess. You can use it in tandem with List.addAll for 942: * fast list construction. 943: * 944: * @param n the number of times to repeat the object 945: * @param o the object to repeat 946: * @return a List consisting of n copies of o 947: * @throws IllegalArgumentException if n < 0 948: * @see List#addAll(Collection) 949: * @see Serializable 950: * @see RandomAccess 951: */ 952: public static List nCopies(final int n, final Object o) 953: { 954: return new CopiesList(n, o); 955: } 956: 957: /** 958: * The implementation of {@link #nCopies(int, Object)}. This class name 959: * is required for compatibility with Sun's JDK serializability. 960: * 961: * @author Eric Blake (ebb9@email.byu.edu) 962: */ 963: private static final class CopiesList extends AbstractList 964: implements Serializable, RandomAccess 965: { 966: /** 967: * Compatible with JDK 1.4. 968: */ 969: private static final long serialVersionUID = 2739099268398711800L; 970: 971: /** 972: * The count of elements in this list. 973: * @serial the list size 974: */ 975: private final int n; 976: 977: /** 978: * The repeated list element. 979: * @serial the list contents 980: */ 981: private final Object element; 982: 983: /** 984: * Constructs the list. 985: * 986: * @param n the count 987: * @param o the object 988: * @throws IllegalArgumentException if n < 0 989: */ 990: CopiesList(int n, Object o) 991: { 992: if (n < 0) 993: throw new IllegalArgumentException(); 994: this.n = n; 995: element = o; 996: } 997: 998: /** 999: * The size is fixed. 1000: * @return The size of the list. 1001: */ 1002: public int size() 1003: { 1004: return n; 1005: } 1006: 1007: /** 1008: * The same element is returned. 1009: * @param index The index of the element to be returned (irrelevant 1010: * as the list contains only copies of <code>element</code>). 1011: * @return The element used by this list. 1012: */ 1013: public Object get(int index) 1014: { 1015: if (index < 0 || index >= n) 1016: throw new IndexOutOfBoundsException(); 1017: return element; 1018: } 1019: 1020: // The remaining methods are optional, but provide a performance 1021: // advantage by not allocating unnecessary iterators in AbstractList. 1022: /** 1023: * This list only contains one element. 1024: * @param o The object to search for. 1025: * @return <code>true</code> if o is the element used by this list. 1026: */ 1027: public boolean contains(Object o) 1028: { 1029: return n > 0 && equals(o, element); 1030: } 1031: 1032: /** 1033: * The index is either 0 or -1. 1034: * @param o The object to find the index of. 1035: * @return 0 if <code>o == element</code>, -1 if not. 1036: */ 1037: public int indexOf(Object o) 1038: { 1039: return (n > 0 && equals(o, element)) ? 0 : -1; 1040: } 1041: 1042: /** 1043: * The index is either n-1 or -1. 1044: * @param o The object to find the last index of. 1045: * @return The last index in the list if <code>o == element</code>, 1046: * -1 if not. 1047: */ 1048: public int lastIndexOf(Object o) 1049: { 1050: return equals(o, element) ? n - 1 : -1; 1051: } 1052: 1053: /** 1054: * A subList is just another CopiesList. 1055: * @param from The starting bound of the sublist. 1056: * @param to The ending bound of the sublist. 1057: * @return A list of copies containing <code>from - to</code> 1058: * elements, all of which are equal to the element 1059: * used by this list. 1060: */ 1061: public List subList(int from, int to) 1062: { 1063: if (from < 0 || to > n) 1064: throw new IndexOutOfBoundsException(); 1065: return new CopiesList(to - from, element); 1066: } 1067: 1068: /** 1069: * The array is easy. 1070: * @return An array of size n filled with copies of 1071: * the element used by this list. 1072: */ 1073: public Object[] toArray() 1074: { 1075: Object[] a = new Object[n]; 1076: Arrays.fill(a, element); 1077: return a; 1078: } 1079: 1080: /** 1081: * The string is easy to generate. 1082: * @return A string representation of the list. 1083: */ 1084: public String toString() 1085: { 1086: StringBuffer r = new StringBuffer("{"); 1087: for (int i = n - 1; --i > 0; ) 1088: r.append(element).append(", "); 1089: r.append(element).append("}"); 1090: return r.toString(); 1091: } 1092: } // class CopiesList 1093: 1094: /** 1095: * Replace all instances of one object with another in the specified list. 1096: * The list does not change size. An element e is replaced if 1097: * <code>oldval == null ? e == null : oldval.equals(e)</code>. 1098: * 1099: * @param list the list to iterate over 1100: * @param oldval the element to replace 1101: * @param newval the new value for the element 1102: * @return <code>true</code> if a replacement occurred. 1103: * @throws UnsupportedOperationException if the list iterator does not allow 1104: * for the set operation 1105: * @throws ClassCastException if newval is of a type which cannot be added 1106: * to the list 1107: * @throws IllegalArgumentException if some other aspect of newval stops 1108: * it being added to the list 1109: * @since 1.4 1110: */ 1111: public static boolean replaceAll(List list, Object oldval, Object newval) 1112: { 1113: ListIterator itr = list.listIterator(); 1114: boolean replace_occured = false; 1115: for (int i = list.size(); --i >= 0; ) 1116: if (AbstractCollection.equals(oldval, itr.next())) 1117: { 1118: itr.set(newval); 1119: replace_occured = true; 1120: } 1121: return replace_occured; 1122: } 1123: 1124: /** 1125: * Reverse a given list. This method works in linear time. 1126: * 1127: * @param l the list to reverse 1128: * @throws UnsupportedOperationException if l.listIterator() does not 1129: * support the set operation 1130: */ 1131: public static void reverse(List l) 1132: { 1133: ListIterator i1 = l.listIterator(); 1134: int pos1 = 1; 1135: int pos2 = l.size(); 1136: ListIterator i2 = l.listIterator(pos2); 1137: while (pos1 < pos2) 1138: { 1139: Object o = i1.next(); 1140: i1.set(i2.previous()); 1141: i2.set(o); 1142: ++pos1; 1143: --pos2; 1144: } 1145: } 1146: 1147: /** 1148: * Get a comparator that implements the reverse of natural ordering. In 1149: * other words, this sorts Comparable objects opposite of how their 1150: * compareTo method would sort. This makes it easy to sort into reverse 1151: * order, by simply passing Collections.reverseOrder() to the sort method. 1152: * The return value of this method is Serializable. 1153: * 1154: * @return a comparator that imposes reverse natural ordering 1155: * @see Comparable 1156: * @see Serializable 1157: */ 1158: public static Comparator reverseOrder() 1159: { 1160: return rcInstance; 1161: } 1162: 1163: /** 1164: * The object for {@link #reverseOrder()}. 1165: */ 1166: private static final ReverseComparator rcInstance = new ReverseComparator(); 1167: 1168: /** 1169: * The implementation of {@link #reverseOrder()}. This class name 1170: * is required for compatibility with Sun's JDK serializability. 1171: * 1172: * @author Eric Blake (ebb9@email.byu.edu) 1173: */ 1174: private static final class ReverseComparator 1175: implements Comparator, Serializable 1176: { 1177: /** 1178: * Compatible with JDK 1.4. 1179: */ 1180: private static final long serialVersionUID = 7207038068494060240L; 1181: 1182: /** 1183: * A private constructor adds overhead. 1184: */ 1185: ReverseComparator() 1186: { 1187: } 1188: 1189: /** 1190: * Compare two objects in reverse natural order. 1191: * 1192: * @param a the first object 1193: * @param b the second object 1194: * @return <, ==, or > 0 according to b.compareTo(a) 1195: */ 1196: public int compare(Object a, Object b) 1197: { 1198: return ((Comparable) b).compareTo(a); 1199: } 1200: } 1201: 1202: /** 1203: * Rotate the elements in a list by a specified distance. After calling this 1204: * method, the element now at index <code>i</code> was formerly at index 1205: * <code>(i - distance) mod list.size()</code>. The list size is unchanged. 1206: * <p> 1207: * 1208: * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After 1209: * either <code>Collections.rotate(l, 4)</code> or 1210: * <code>Collections.rotate(l, -1)</code>, the new contents are 1211: * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate 1212: * just a portion of the list. For example, to move element <code>a</code> 1213: * forward two positions in the original example, use 1214: * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will 1215: * result in <code>[t, n, k, a, s]</code>. 1216: * <p> 1217: * 1218: * If the list is small or implements {@link RandomAccess}, the 1219: * implementation exchanges the first element to its destination, then the 1220: * displaced element, and so on until a circuit has been completed. The 1221: * process is repeated if needed on the second element, and so forth, until 1222: * all elements have been swapped. For large non-random lists, the 1223: * implementation breaks the list into two sublists at index 1224: * <code>-distance mod size</code>, calls {@link #reverse(List)} on the 1225: * pieces, then reverses the overall list. 1226: * 1227: * @param list the list to rotate 1228: * @param distance the distance to rotate by; unrestricted in value 1229: * @throws UnsupportedOperationException if the list does not support set 1230: * @since 1.4 1231: */ 1232: public static void rotate(List list, int distance) 1233: { 1234: int size = list.size(); 1235: if (size == 0) 1236: return; 1237: distance %= size; 1238: if (distance == 0) 1239: return; 1240: if (distance < 0) 1241: distance += size; 1242: 1243: if (isSequential(list)) 1244: { 1245: reverse(list); 1246: reverse(list.subList(0, distance)); 1247: reverse(list.subList(distance, size)); 1248: } 1249: else 1250: { 1251: // Determine the least common multiple of distance and size, as there 1252: // are (distance / LCM) loops to cycle through. 1253: int a = size; 1254: int lcm = distance; 1255: int b = a % lcm; 1256: while (b != 0) 1257: { 1258: a = lcm; 1259: lcm = b; 1260: b = a % lcm; 1261: } 1262: 1263: // Now, make the swaps. We must take the remainder every time through 1264: // the inner loop so that we don't overflow i to negative values. 1265: while (--lcm >= 0) 1266: { 1267: Object o = list.get(lcm); 1268: for (int i = lcm + distance; i != lcm; i = (i + distance) % size) 1269: o = list.set(i, o); 1270: list.set(lcm, o); 1271: } 1272: } 1273: } 1274: 1275: /** 1276: * Shuffle a list according to a default source of randomness. The algorithm 1277: * used iterates backwards over the list, swapping each element with an 1278: * element randomly selected from the elements in positions less than or 1279: * equal to it (using r.nextInt(int)). 1280: * <p> 1281: * 1282: * This algorithm would result in a perfectly fair shuffle (that is, each 1283: * element would have an equal chance of ending up in any position) if r were 1284: * a perfect source of randomness. In practice the results are merely very 1285: * close to perfect. 1286: * <p> 1287: * 1288: * This method operates in linear time. To do this on large lists which do 1289: * not implement {@link RandomAccess}, a temporary array is used to acheive 1290: * this speed, since it would be quadratic access otherwise. 1291: * 1292: * @param l the list to shuffle 1293: * @throws UnsupportedOperationException if l.listIterator() does not 1294: * support the set operation 1295: */ 1296: public static void shuffle(List l) 1297: { 1298: if (defaultRandom == null) 1299: { 1300: synchronized (Collections.class) 1301: { 1302: if (defaultRandom == null) 1303: defaultRandom = new Random(); 1304: } 1305: } 1306: shuffle(l, defaultRandom); 1307: } 1308: 1309: /** 1310: * Cache a single Random object for use by shuffle(List). This improves 1311: * performance as well as ensuring that sequential calls to shuffle() will 1312: * not result in the same shuffle order occurring: the resolution of 1313: * System.currentTimeMillis() is not sufficient to guarantee a unique seed. 1314: */ 1315: private static Random defaultRandom = null; 1316: 1317: /** 1318: * Shuffle a list according to a given source of randomness. The algorithm 1319: * used iterates backwards over the list, swapping each element with an 1320: * element randomly selected from the elements in positions less than or 1321: * equal to it (using r.nextInt(int)). 1322: * <p> 1323: * 1324: * This algorithm would result in a perfectly fair shuffle (that is, each 1325: * element would have an equal chance of ending up in any position) if r were 1326: * a perfect source of randomness. In practise (eg if r = new Random()) the 1327: * results are merely very close to perfect. 1328: * <p> 1329: * 1330: * This method operates in linear time. To do this on large lists which do 1331: * not implement {@link RandomAccess}, a temporary array is used to acheive 1332: * this speed, since it would be quadratic access otherwise. 1333: * 1334: * @param l the list to shuffle 1335: * @param r the source of randomness to use for the shuffle 1336: * @throws UnsupportedOperationException if l.listIterator() does not 1337: * support the set operation 1338: */ 1339: public static void shuffle(List l, Random r) 1340: { 1341: int lsize = l.size(); 1342: ListIterator i = l.listIterator(lsize); 1343: boolean sequential = isSequential(l); 1344: Object[] a = null; // stores a copy of the list for the sequential case 1345: 1346: if (sequential) 1347: a = l.toArray(); 1348: 1349: for (int pos = lsize - 1; pos > 0; --pos) 1350: { 1351: // Obtain a random position to swap with. pos + 1 is used so that the 1352: // range of the random number includes the current position. 1353: int swap = r.nextInt(pos + 1); 1354: 1355: // Swap the desired element. 1356: Object o; 1357: if (sequential) 1358: { 1359: o = a[swap]; 1360: a[swap] = i.previous(); 1361: } 1362: else 1363: o = l.set(swap, i.previous()); 1364: 1365: i.set(o); 1366: } 1367: } 1368: 1369: 1370: /** 1371: * Obtain an immutable Set consisting of a single element. The return value 1372: * of this method is Serializable. 1373: * 1374: * @param o the single element 1375: * @return an immutable Set containing only o 1376: * @see Serializable 1377: */ 1378: public static Set singleton(Object o) 1379: { 1380: return new SingletonSet(o); 1381: } 1382: 1383: /** 1384: * The implementation of {@link #singleton(Object)}. This class name 1385: * is required for compatibility with Sun's JDK serializability. 1386: * 1387: * @author Eric Blake (ebb9@email.byu.edu) 1388: */ 1389: private static final class SingletonSet extends AbstractSet 1390: implements Serializable 1391: { 1392: /** 1393: * Compatible with JDK 1.4. 1394: */ 1395: private static final long serialVersionUID = 3193687207550431679L; 1396: 1397: 1398: /** 1399: * The single element; package visible for use in nested class. 1400: * @serial the singleton 1401: */ 1402: final Object element; 1403: 1404: /** 1405: * Construct a singleton. 1406: * @param o the element 1407: */ 1408: SingletonSet(Object o) 1409: { 1410: element = o; 1411: } 1412: 1413: /** 1414: * The size: always 1! 1415: * @return 1. 1416: */ 1417: public int size() 1418: { 1419: return 1; 1420: } 1421: 1422: /** 1423: * Returns an iterator over the lone element. 1424: */ 1425: public Iterator iterator() 1426: { 1427: return new Iterator() 1428: { 1429: /** 1430: * Flag to indicate whether or not the element has 1431: * been retrieved. 1432: */ 1433: private boolean hasNext = true; 1434: 1435: /** 1436: * Returns <code>true</code> if elements still remain to be 1437: * iterated through. 1438: * 1439: * @return <code>true</code> if the element has not yet been returned. 1440: */ 1441: public boolean hasNext() 1442: { 1443: return hasNext; 1444: } 1445: 1446: /** 1447: * Returns the element. 1448: * 1449: * @return The element used by this singleton. 1450: * @throws NoSuchElementException if the object 1451: * has already been retrieved. 1452: */ 1453: public Object next() 1454: { 1455: if (hasNext) 1456: { 1457: hasNext = false; 1458: return element; 1459: } 1460: else 1461: throw new NoSuchElementException(); 1462: } 1463: 1464: /** 1465: * Removes the element from the singleton. 1466: * As this set is immutable, this will always 1467: * throw an exception. 1468: * 1469: * @throws UnsupportedOperationException as the 1470: * singleton set doesn't support 1471: * <code>remove()</code>. 1472: */ 1473: public void remove() 1474: { 1475: throw new UnsupportedOperationException(); 1476: } 1477: }; 1478: } 1479: 1480: // The remaining methods are optional, but provide a performance 1481: // advantage by not allocating unnecessary iterators in AbstractSet. 1482: /** 1483: * The set only contains one element. 1484: * 1485: * @param o The object to search for. 1486: * @return <code>true</code> if o == the element of the singleton. 1487: */ 1488: public boolean contains(Object o) 1489: { 1490: return equals(o, element); 1491: } 1492: 1493: /** 1494: * This is true if the other collection only contains the element. 1495: * 1496: * @param c A collection to compare against this singleton. 1497: * @return <code>true</code> if c only contains either no elements or 1498: * elements equal to the element in this singleton. 1499: */ 1500: public boolean containsAll(Collection c) 1501: { 1502: Iterator i = c.iterator(); 1503: int pos = c.size(); 1504: while (--pos >= 0) 1505: if (! equals(i.next(), element)) 1506: return false; 1507: return true; 1508: } 1509: 1510: /** 1511: * The hash is just that of the element. 1512: * 1513: * @return The hashcode of the element. 1514: */ 1515: public int hashCode() 1516: { 1517: return hashCode(element); 1518: } 1519: 1520: /** 1521: * Returning an array is simple. 1522: * 1523: * @return An array containing the element. 1524: */ 1525: public Object[] toArray() 1526: { 1527: return new Object[] {element}; 1528: } 1529: 1530: /** 1531: * Obvious string. 1532: * 1533: * @return The string surrounded by enclosing 1534: * square brackets. 1535: */ 1536: public String toString() 1537: { 1538: return "[" + element + "]"; 1539: } 1540: } // class SingletonSet 1541: 1542: /** 1543: * Obtain an immutable List consisting of a single element. The return value 1544: * of this method is Serializable, and implements RandomAccess. 1545: * 1546: * @param o the single element 1547: * @return an immutable List containing only o 1548: * @see Serializable 1549: * @see RandomAccess 1550: * @since 1.3 1551: */ 1552: public static List singletonList(Object o) 1553: { 1554: return new SingletonList(o); 1555: } 1556: 1557: /** 1558: * The implementation of {@link #singletonList(Object)}. This class name 1559: * is required for compatibility with Sun's JDK serializability. 1560: * 1561: * @author Eric Blake (ebb9@email.byu.edu) 1562: */ 1563: private static final class SingletonList extends AbstractList 1564: implements Serializable, RandomAccess 1565: { 1566: /** 1567: * Compatible with JDK 1.4. 1568: */ 1569: private static final long serialVersionUID = 3093736618740652951L; 1570: 1571: /** 1572: * The single element. 1573: * @serial the singleton 1574: */ 1575: private final Object element; 1576: 1577: /** 1578: * Construct a singleton. 1579: * @param o the element 1580: */ 1581: SingletonList(Object o) 1582: { 1583: element = o; 1584: } 1585: 1586: /** 1587: * The size: always 1! 1588: * @return 1. 1589: */ 1590: public int size() 1591: { 1592: return 1; 1593: } 1594: 1595: /** 1596: * Only index 0 is valid. 1597: * @param index The index of the element 1598: * to retrieve. 1599: * @return The singleton's element if the 1600: * index is 0. 1601: * @throws IndexOutOfBoundsException if 1602: * index is not 0. 1603: */ 1604: public Object get(int index) 1605: { 1606: if (index == 0) 1607: return element; 1608: throw new IndexOutOfBoundsException(); 1609: } 1610: 1611: // The remaining methods are optional, but provide a performance 1612: // advantage by not allocating unnecessary iterators in AbstractList. 1613: /** 1614: * The set only contains one element. 1615: * 1616: * @param o The object to search for. 1617: * @return <code>true</code> if o == the singleton element. 1618: */ 1619: public boolean contains(Object o) 1620: { 1621: return equals(o, element); 1622: } 1623: 1624: /** 1625: * This is true if the other collection only contains the element. 1626: * 1627: * @param c A collection to compare against this singleton. 1628: * @return <code>true</code> if c only contains either no elements or 1629: * elements equal to the element in this singleton. 1630: */ 1631: public boolean containsAll(Collection c) 1632: { 1633: Iterator i = c.iterator(); 1634: int pos = c.size(); 1635: while (--pos >= 0) 1636: if (! equals(i.next(), element)) 1637: return false; 1638: return true; 1639: } 1640: 1641: /** 1642: * Speed up the hashcode computation. 1643: * 1644: * @return The hashcode of the list, based 1645: * on the hashcode of the singleton element. 1646: */ 1647: public int hashCode() 1648: { 1649: return 31 + hashCode(element); 1650: } 1651: 1652: /** 1653: * Either the list has it or not. 1654: * 1655: * @param o The object to find the first index of. 1656: * @return 0 if o is the singleton element, -1 if not. 1657: */ 1658: public int indexOf(Object o) 1659: { 1660: return equals(o, element) ? 0 : -1; 1661: } 1662: 1663: /** 1664: * Either the list has it or not. 1665: * 1666: * @param o The object to find the last index of. 1667: * @return 0 if o is the singleton element, -1 if not. 1668: */ 1669: public int lastIndexOf(Object o) 1670: { 1671: return equals(o, element) ? 0 : -1; 1672: } 1673: 1674: /** 1675: * Sublists are limited in scope. 1676: * 1677: * @param from The starting bound for the sublist. 1678: * @param to The ending bound for the sublist. 1679: * @return Either an empty list if both bounds are 1680: * 0 or 1, or this list if the bounds are 0 and 1. 1681: * @throws IllegalArgumentException if <code>from > to</code> 1682: * @throws IndexOutOfBoundsException if either bound is greater 1683: * than 1. 1684: */ 1685: public List subList(int from, int to) 1686: { 1687: if (from == to && (to == 0 || to == 1)) 1688: return EMPTY_LIST; 1689: if (from == 0 && to == 1) 1690: return this; 1691: if (from > to) 1692: throw new IllegalArgumentException(); 1693: throw new IndexOutOfBoundsException(); 1694: } 1695: 1696: /** 1697: * Returning an array is simple. 1698: * 1699: * @return An array containing the element. 1700: */ 1701: public Object[] toArray() 1702: { 1703: return new Object[] {element}; 1704: } 1705: 1706: /** 1707: * Obvious string. 1708: * 1709: * @return The string surrounded by enclosing 1710: * square brackets. 1711: */ 1712: public String toString() 1713: { 1714: return "[" + element + "]"; 1715: } 1716: } // class SingletonList 1717: 1718: /** 1719: * Obtain an immutable Map consisting of a single key-value pair. 1720: * The return value of this method is Serializable. 1721: * 1722: * @param key the single key 1723: * @param value the single value 1724: * @return an immutable Map containing only the single key-value pair 1725: * @see Serializable 1726: * @since 1.3 1727: */ 1728: public static Map singletonMap(Object key, Object value) 1729: { 1730: return new SingletonMap(key, value); 1731: } 1732: 1733: /** 1734: * The implementation of {@link #singletonMap(Object, Object)}. This class 1735: * name is required for compatibility with Sun's JDK serializability. 1736: * 1737: * @author Eric Blake (ebb9@email.byu.edu) 1738: */ 1739: private static final class SingletonMap extends AbstractMap 1740: implements Serializable 1741: { 1742: /** 1743: * Compatible with JDK 1.4. 1744: */ 1745: private static final long serialVersionUID = -6979724477215052911L; 1746: 1747: /** 1748: * The single key. 1749: * @serial the singleton key 1750: */ 1751: private final Object k; 1752: 1753: /** 1754: * The corresponding value. 1755: * @serial the singleton value 1756: */ 1757: private final Object v; 1758: 1759: /** 1760: * Cache the entry set. 1761: */ 1762: private transient Set entries; 1763: 1764: /** 1765: * Construct a singleton. 1766: * @param key the key 1767: * @param value the value 1768: */ 1769: SingletonMap(Object key, Object value) 1770: { 1771: k = key; 1772: v = value; 1773: } 1774: 1775: /** 1776: * There is a single immutable entry. 1777: * 1778: * @return A singleton containing the map entry. 1779: */ 1780: public Set entrySet() 1781: { 1782: if (entries == null) 1783: entries = singleton(new AbstractMap.BasicMapEntry(k, v) 1784: { 1785: /** 1786: * Sets the value of the map entry to the supplied value. 1787: * An exception is always thrown, as the map is immutable. 1788: * 1789: * @param o The new value. 1790: * @return The old value. 1791: * @throws UnsupportedOperationException as setting the value 1792: * is not supported. 1793: */ 1794: public Object setValue(Object o) 1795: { 1796: throw new UnsupportedOperationException(); 1797: } 1798: }); 1799: return entries; 1800: } 1801: 1802: // The remaining methods are optional, but provide a performance 1803: // advantage by not allocating unnecessary iterators in AbstractMap. 1804: /** 1805: * Single entry. 1806: * 1807: * @param key The key to look for. 1808: * @return <code>true</code> if the key is the same as the one used by 1809: * this map. 1810: */ 1811: public boolean containsKey(Object key) 1812: { 1813: return equals(key, k); 1814: } 1815: 1816: /** 1817: * Single entry. 1818: * 1819: * @param value The value to look for. 1820: * @return <code>true</code> if the value is the same as the one used by 1821: * this map. 1822: */ 1823: public boolean containsValue(Object value) 1824: { 1825: return equals(value, v); 1826: } 1827: 1828: /** 1829: * Single entry. 1830: * 1831: * @param key The key of the value to be retrieved. 1832: * @return The singleton value if the key is the same as the 1833: * singleton key, null otherwise. 1834: */ 1835: public Object get(Object key) 1836: { 1837: return equals(key, k) ? v : null; 1838: } 1839: 1840: /** 1841: * Calculate the hashcode directly. 1842: * 1843: * @return The hashcode computed from the singleton key 1844: * and the singleton value. 1845: */ 1846: public int hashCode() 1847: { 1848: return hashCode(k) ^ hashCode(v); 1849: } 1850: 1851: /** 1852: * Return the keyset. 1853: * 1854: * @return A singleton containing the key. 1855: */ 1856: public Set keySet() 1857: { 1858: if (keys == null) 1859: keys = singleton(k); 1860: return keys; 1861: } 1862: 1863: /** 1864: * The size: always 1! 1865: * 1866: * @return 1. 1867: */ 1868: public int size() 1869: { 1870: return 1; 1871: } 1872: 1873: /** 1874: * Return the values. Technically, a singleton, while more specific than 1875: * a general Collection, will work. Besides, that's what the JDK uses! 1876: * 1877: * @return A singleton containing the value. 1878: */ 1879: public Collection values() 1880: { 1881: if (values == null) 1882: values = singleton(v); 1883: return values; 1884: } 1885: 1886: /** 1887: * Obvious string. 1888: * 1889: * @return A string containing the string representations of the key 1890: * and its associated value. 1891: */ 1892: public String toString() 1893: { 1894: return "{" + k + "=" + v + "}"; 1895: } 1896: } // class SingletonMap 1897: 1898: /** 1899: * Sort a list according to the natural ordering of its elements. The list 1900: * must be modifiable, but can be of fixed size. The sort algorithm is 1901: * precisely that used by Arrays.sort(Object[]), which offers guaranteed 1902: * nlog(n) performance. This implementation dumps the list into an array, 1903: * sorts the array, and then iterates over the list setting each element from 1904: * the array. 1905: * 1906: * @param l the List to sort 1907: * @throws ClassCastException if some items are not mutually comparable 1908: * @throws UnsupportedOperationException if the List is not modifiable 1909: * @throws NullPointerException if some element is null 1910: * @see Arrays#sort(Object[]) 1911: */ 1912: public static void sort(List l) 1913: { 1914: sort(l, null); 1915: } 1916: 1917: /** 1918: * Sort a list according to a specified Comparator. The list must be 1919: * modifiable, but can be of fixed size. The sort algorithm is precisely that 1920: * used by Arrays.sort(Object[], Comparator), which offers guaranteed 1921: * nlog(n) performance. This implementation dumps the list into an array, 1922: * sorts the array, and then iterates over the list setting each element from 1923: * the array. 1924: * 1925: * @param l the List to sort 1926: * @param c the Comparator specifying the ordering for the elements, or 1927: * null for natural ordering 1928: * @throws ClassCastException if c will not compare some pair of items 1929: * @throws UnsupportedOperationException if the List is not modifiable 1930: * @throws NullPointerException if null is compared by natural ordering 1931: * (only possible when c is null) 1932: * @see Arrays#sort(Object[], Comparator) 1933: */ 1934: public static void sort(List l, Comparator c) 1935: { 1936: Object[] a = l.toArray(); 1937: Arrays.sort(a, c); 1938: ListIterator i = l.listIterator(); 1939: for (int pos = 0, alen = a.length; pos < alen; pos++) 1940: { 1941: i.next(); 1942: i.set(a[pos]); 1943: } 1944: } 1945: 1946: /** 1947: * Swaps the elements at the specified positions within the list. Equal 1948: * positions have no effect. 1949: * 1950: * @param l the list to work on 1951: * @param i the first index to swap 1952: * @param j the second index 1953: * @throws UnsupportedOperationException if list.set is not supported 1954: * @throws IndexOutOfBoundsException if either i or j is < 0 or >= 1955: * list.size() 1956: * @since 1.4 1957: */ 1958: public static void swap(List l, int i, int j) 1959: { 1960: l.set(i, l.set(j, l.get(i))); 1961: } 1962: 1963: 1964: /** 1965: * Returns a synchronized (thread-safe) collection wrapper backed by the 1966: * given collection. Notice that element access through the iterators 1967: * is thread-safe, but if the collection can be structurally modified 1968: * (adding or removing elements) then you should synchronize around the 1969: * iteration to avoid non-deterministic behavior:<br> 1970: * <pre> 1971: * Collection c = Collections.synchronizedCollection(new Collection(...)); 1972: * ... 1973: * synchronized (c) 1974: * { 1975: * Iterator i = c.iterator(); 1976: * while (i.hasNext()) 1977: * foo(i.next()); 1978: * } 1979: * </pre><p> 1980: * 1981: * Since the collection might be a List or a Set, and those have incompatible 1982: * equals and hashCode requirements, this relies on Object's implementation 1983: * rather than passing those calls on to the wrapped collection. The returned 1984: * Collection implements Serializable, but can only be serialized if 1985: * the collection it wraps is likewise Serializable. 1986: * 1987: * @param c the collection to wrap 1988: * @return a synchronized view of the collection 1989: * @see Serializable 1990: */ 1991: public static Collection synchronizedCollection(Collection c) 1992: { 1993: return new SynchronizedCollection(c); 1994: } 1995: 1996: /** 1997: * The implementation of {@link #synchronizedCollection(Collection)}. This 1998: * class name is required for compatibility with Sun's JDK serializability. 1999: * Package visible, so that collections such as the one for 2000: * Hashtable.values() can specify which object to synchronize on. 2001: * 2002: * @author Eric Blake (ebb9@email.byu.edu) 2003: */ 2004: static class SynchronizedCollection 2005: implements Collection, Serializable 2006: { 2007: /** 2008: * Compatible with JDK 1.4. 2009: */ 2010: private static final long serialVersionUID = 3053995032091335093L; 2011: 2012: /** 2013: * The wrapped collection. Package visible for use by subclasses. 2014: * @serial the real collection 2015: */ 2016: final Collection c; 2017: 2018: /** 2019: * The object to synchronize on. When an instance is created via public 2020: * methods, it will be this; but other uses like SynchronizedMap.values() 2021: * must specify another mutex. Package visible for use by subclasses. 2022: * @serial the lock 2023: */ 2024: final Object mutex; 2025: 2026: /** 2027: * Wrap a given collection. 2028: * @param c the collection to wrap 2029: * @throws NullPointerException if c is null 2030: */ 2031: SynchronizedCollection(Collection c) 2032: { 2033: this.c = c; 2034: mutex = this; 2035: if (c == null) 2036: throw new NullPointerException(); 2037: } 2038: 2039: /** 2040: * Called only by trusted code to specify the mutex as well as the 2041: * collection. 2042: * @param sync the mutex 2043: * @param c the collection 2044: */ 2045: SynchronizedCollection(Object sync, Collection c) 2046: { 2047: this.c = c; 2048: mutex = sync; 2049: } 2050: 2051: /** 2052: * Adds the object to the underlying collection, first 2053: * obtaining a lock on the mutex. 2054: * 2055: * @param o The object to add. 2056: * @return <code>true</code> if the collection was modified as a result 2057: * of this action. 2058: * @throws UnsupportedOperationException if this collection does not 2059: * support the add operation. 2060: * @throws ClassCastException if o cannot be added to this collection due 2061: * to its type. 2062: * @throws NullPointerException if o is null and this collection doesn't 2063: * support the addition of null values. 2064: * @throws IllegalArgumentException if o cannot be added to this 2065: * collection for some other reason. 2066: */ 2067: public boolean add(Object o) 2068: { 2069: synchronized (mutex) 2070: { 2071: return c.add(o); 2072: } 2073: } 2074: 2075: /** 2076: * Adds the objects in col to the underlying collection, first 2077: * obtaining a lock on the mutex. 2078: * 2079: * @param col The collection to take the new objects from. 2080: * @return <code>true</code> if the collection was modified as a result 2081: * of this action. 2082: * @throws UnsupportedOperationException if this collection does not 2083: * support the addAll operation. 2084: * @throws ClassCastException if some element of col cannot be added to this 2085: * collection due to its type. 2086: * @throws NullPointerException if some element of col is null and this 2087: * collection does not support the addition of null values. 2088: * @throws NullPointerException if col itself is null. 2089: * @throws IllegalArgumentException if some element of col cannot be added 2090: * to this collection for some other reason. 2091: */ 2092: public boolean addAll(Collection col) 2093: { 2094: synchronized (mutex) 2095: { 2096: return c.addAll(col); 2097: } 2098: } 2099: 2100: /** 2101: * Removes all objects from the underlying collection, 2102: * first obtaining a lock on the mutex. 2103: * 2104: * @throws UnsupportedOperationException if this collection does not 2105: * support the clear operation. 2106: */ 2107: public void clear() 2108: { 2109: synchronized (mutex) 2110: { 2111: c.clear(); 2112: } 2113: } 2114: 2115: /** 2116: * Checks for the existence of o within the underlying 2117: * collection, first obtaining a lock on the mutex. 2118: * 2119: * @param o the element to look for. 2120: * @return <code>true</code> if this collection contains at least one 2121: * element e such that <code>o == null ? e == null : o.equals(e)</code>. 2122: * @throws ClassCastException if the type of o is not a valid type for this 2123: * collection. 2124: * @throws NullPointerException if o is null and this collection doesn't 2125: * support null values. 2126: */ 2127: public boolean contains(Object o) 2128: { 2129: synchronized (mutex) 2130: { 2131: return c.contains(o); 2132: } 2133: } 2134: 2135: /** 2136: * Checks for the existence of each object in cl 2137: * within the underlying collection, first obtaining 2138: * a lock on the mutex. 2139: * 2140: * @param c1 the collection to test for. 2141: * @return <code>true</code> if for every element o in c, contains(o) 2142: * would return <code>true</code>. 2143: * @throws ClassCastException if the type of any element in cl is not a valid 2144: * type for this collection. 2145: * @throws NullPointerException if some element of cl is null and this 2146: * collection does not support null values. 2147: * @throws NullPointerException if cl itself is null. 2148: */ 2149: public boolean containsAll(Collection c1) 2150: { 2151: synchronized (mutex) 2152: { 2153: return c.containsAll(c1); 2154: } 2155: } 2156: 2157: /** 2158: * Returns <code>true</code> if there are no objects in the underlying 2159: * collection. A lock on the mutex is obtained before the 2160: * check is performed. 2161: * 2162: * @return <code>true</code> if this collection contains no elements. 2163: */ 2164: public boolean isEmpty() 2165: { 2166: synchronized (mutex) 2167: { 2168: return c.isEmpty(); 2169: } 2170: } 2171: 2172: /** 2173: * Returns a synchronized iterator wrapper around the underlying 2174: * collection's iterator. A lock on the mutex is obtained before 2175: * retrieving the collection's iterator. 2176: * 2177: * @return An iterator over the elements in the underlying collection, 2178: * which returns each element in any order. 2179: */ 2180: public Iterator iterator() 2181: { 2182: synchronized (mutex) 2183: { 2184: return new SynchronizedIterator(mutex, c.iterator()); 2185: } 2186: } 2187: 2188: /** 2189: * Removes the specified object from the underlying collection, 2190: * first obtaining a lock on the mutex. 2191: * 2192: * @param o The object to remove. 2193: * @return <code>true</code> if the collection changed as a result of this call, that is, 2194: * if the collection contained at least one occurrence of o. 2195: * @throws UnsupportedOperationException if this collection does not 2196: * support the remove operation. 2197: * @throws ClassCastException if the type of o is not a valid type 2198: * for this collection. 2199: * @throws NullPointerException if o is null and the collection doesn't 2200: * support null values. 2201: */ 2202: public boolean remove(Object o) 2203: { 2204: synchronized (mutex) 2205: { 2206: return c.remove(o); 2207: } 2208: } 2209: 2210: /** 2211: * Removes all elements, e, of the underlying 2212: * collection for which <code>col.contains(e)</code> 2213: * returns <code>true</code>. A lock on the mutex is obtained 2214: * before the operation proceeds. 2215: * 2216: * @param col The collection of objects to be removed. 2217: * @return <code>true</code> if this collection was modified as a result of this call. 2218: * @throws UnsupportedOperationException if this collection does not 2219: * support the removeAll operation. 2220: * @throws ClassCastException if the type of any element in c is not a valid 2221: * type for this collection. 2222: * @throws NullPointerException if some element of c is null and this 2223: * collection does not support removing null values. 2224: * @throws NullPointerException if c itself is null. 2225: */ 2226: public boolean removeAll(Collection col) 2227: { 2228: synchronized (mutex) 2229: { 2230: return c.removeAll(col); 2231: } 2232: } 2233: 2234: /** 2235: * Retains all elements, e, of the underlying 2236: * collection for which <code>col.contains(e)</code> 2237: * returns <code>true</code>. That is, every element that doesn't 2238: * exist in col is removed. A lock on the mutex is obtained 2239: * before the operation proceeds. 2240: * 2241: * @param col The collection of objects to be removed. 2242: * @return <code>true</code> if this collection was modified as a result of this call. 2243: * @throws UnsupportedOperationException if this collection does not 2244: * support the removeAll operation. 2245: * @throws ClassCastException if the type of any element in c is not a valid 2246: * type for this collection. 2247: * @throws NullPointerException if some element of c is null and this 2248: * collection does not support removing null values. 2249: * @throws NullPointerException if c itself is null. 2250: */ 2251: public boolean retainAll(Collection col) 2252: { 2253: synchronized (mutex) 2254: { 2255: return c.retainAll(col); 2256: } 2257: } 2258: 2259: /** 2260: * Retrieves the size of the underlying collection. 2261: * A lock on the mutex is obtained before the collection 2262: * is accessed. 2263: * 2264: * @return The size of the collection. 2265: */ 2266: public int size() 2267: { 2268: synchronized (mutex) 2269: { 2270: return c.size(); 2271: } 2272: } 2273: 2274: /** 2275: * Returns an array containing each object within the underlying 2276: * collection. A lock is obtained on the mutex before the collection 2277: * is accessed. 2278: * 2279: * @return An array of objects, matching the collection in size. The 2280: * elements occur in any order. 2281: */ 2282: public Object[] toArray() 2283: { 2284: synchronized (mutex) 2285: { 2286: return c.toArray(); 2287: } 2288: } 2289: 2290: /** 2291: * Copies the elements in the underlying collection to the supplied 2292: * array. If <code>a.length < size()</code>, a new array of the 2293: * same run-time type is created, with a size equal to that of 2294: * the collection. If <code>a.length > size()</code>, then the 2295: * elements from 0 to <code>size() - 1</code> contain the elements 2296: * from this collection. The following element is set to null 2297: * to indicate the end of the collection objects. However, this 2298: * only makes a difference if null is not a permitted value within 2299: * the collection. 2300: * Before the copying takes place, a lock is obtained on the mutex. 2301: * 2302: * @param a An array to copy elements to. 2303: * @return An array containing the elements of the underlying collection. 2304: * @throws ArrayStoreException if the type of any element of the 2305: * collection is not a subtype of the element type of a. 2306: */ 2307: public Object[] toArray(Object[] a) 2308: { 2309: synchronized (mutex) 2310: { 2311: return c.toArray(a); 2312: } 2313: } 2314: 2315: /** 2316: * Returns a string representation of the underlying collection. 2317: * A lock is obtained on the mutex before the string is created. 2318: * 2319: * @return A string representation of the collection. 2320: */ 2321: public String toString() 2322: { 2323: synchronized (mutex) 2324: { 2325: return c.toString(); 2326: } 2327: } 2328: } // class SynchronizedCollection 2329: 2330: /** 2331: * The implementation of the various iterator methods in the 2332: * synchronized classes. These iterators must "sync" on the same object 2333: * as the collection they iterate over. 2334: * 2335: * @author Eric Blake (ebb9@email.byu.edu) 2336: */ 2337: private static class SynchronizedIterator implements Iterator 2338: { 2339: /** 2340: * The object to synchronize on. Package visible for use by subclass. 2341: */ 2342: final Object mutex; 2343: 2344: /** 2345: * The wrapped iterator. 2346: */ 2347: private final Iterator i; 2348: 2349: /** 2350: * Only trusted code creates a wrapper, with the specified sync. 2351: * @param sync the mutex 2352: * @param i the wrapped iterator 2353: */ 2354: SynchronizedIterator(Object sync, Iterator i) 2355: { 2356: this.i = i; 2357: mutex = sync; 2358: } 2359: 2360: /** 2361: * Retrieves the next object in the underlying collection. 2362: * A lock is obtained on the mutex before the collection is accessed. 2363: * 2364: * @return The next object in the collection. 2365: * @throws NoSuchElementException if there are no more elements 2366: */ 2367: public Object next() 2368: { 2369: synchronized (mutex) 2370: { 2371: return i.next(); 2372: } 2373: } 2374: 2375: /** 2376: * Returns <code>true</code> if objects can still be retrieved from the iterator 2377: * using <code>next()</code>. A lock is obtained on the mutex before 2378: * the collection is accessed. 2379: * 2380: * @return <code>true</code> if at least one element is still to be returned by 2381: * <code>next()</code>. 2382: */ 2383: public boolean hasNext() 2384: { 2385: synchronized (mutex) 2386: { 2387: return i.hasNext(); 2388: } 2389: } 2390: 2391: /** 2392: * Removes the object that was last returned by <code>next()</code> 2393: * from the underlying collection. Only one call to this method is 2394: * allowed per call to the <code>next()</code> method, and it does 2395: * not affect the value that will be returned by <code>next()</code>. 2396: * Thus, if element n was retrieved from the collection by 2397: * <code>next()</code>, it is this element that gets removed. 2398: * Regardless of whether this takes place or not, element n+1 is 2399: * still returned on the subsequent <code>next()</code> call. 2400: * 2401: * @throws IllegalStateException if next has not yet been called or remove 2402: * has already been called since the last call to next. 2403: * @throws UnsupportedOperationException if this Iterator does not support 2404: * the remove operation. 2405: */ 2406: public void remove() 2407: { 2408: synchronized (mutex) 2409: { 2410: i.remove(); 2411: } 2412: } 2413: } // class SynchronizedIterator 2414: 2415: /** 2416: * Returns a synchronized (thread-safe) list wrapper backed by the 2417: * given list. Notice that element access through the iterators 2418: * is thread-safe, but if the list can be structurally modified 2419: * (adding or removing elements) then you should synchronize around the 2420: * iteration to avoid non-deterministic behavior:<br> 2421: * <pre> 2422: * List l = Collections.synchronizedList(new List(...)); 2423: * ... 2424: * synchronized (l) 2425: * { 2426: * Iterator i = l.iterator(); 2427: * while (i.hasNext()) 2428: * foo(i.next()); 2429: * } 2430: * </pre><p> 2431: * 2432: * The returned List implements Serializable, but can only be serialized if 2433: * the list it wraps is likewise Serializable. In addition, if the wrapped 2434: * list implements RandomAccess, this does too. 2435: * 2436: * @param l the list to wrap 2437: * @return a synchronized view of the list 2438: * @see Serializable 2439: * @see RandomAccess 2440: */ 2441: public static List synchronizedList(List l) 2442: { 2443: if (l instanceof RandomAccess) 2444: return new SynchronizedRandomAccessList(l); 2445: return new SynchronizedList(l); 2446: } 2447: 2448: /** 2449: * The implementation of {@link #synchronizedList(List)} for sequential 2450: * lists. This class name is required for compatibility with Sun's JDK 2451: * serializability. Package visible, so that lists such as Vector.subList() 2452: * can specify which object to synchronize on. 2453: * 2454: * @author Eric Blake (ebb9@email.byu.edu) 2455: */ 2456: static class SynchronizedList extends SynchronizedCollection 2457: implements List 2458: { 2459: /** 2460: * Compatible with JDK 1.4. 2461: */ 2462: private static final long serialVersionUID = -7754090372962971524L; 2463: 2464: /** 2465: * The wrapped list; stored both here and in the superclass to avoid 2466: * excessive casting. Package visible for use by subclass. 2467: * @serial the wrapped list 2468: */ 2469: final List list; 2470: 2471: /** 2472: * Wrap a given list. 2473: * @param l the list to wrap 2474: * @throws NullPointerException if l is null 2475: */ 2476: SynchronizedList(List l) 2477: { 2478: super(l); 2479: list = l; 2480: } 2481: 2482: /** 2483: * Called only by trusted code to specify the mutex as well as the list. 2484: * @param sync the mutex 2485: * @param l the list 2486: */ 2487: SynchronizedList(Object sync, List l) 2488: { 2489: super(sync, l); 2490: list = l; 2491: } 2492: 2493: /** 2494: * Insert an element into the underlying list at a given position (optional 2495: * operation). This shifts all existing elements from that position to the 2496: * end one index to the right. This version of add has no return, since it is 2497: * assumed to always succeed if there is no exception. Before the 2498: * addition takes place, a lock is obtained on the mutex. 2499: * 2500: * @param index the location to insert the item 2501: * @param o the object to insert 2502: * @throws UnsupportedOperationException if this list does not support the 2503: * add operation 2504: * @throws IndexOutOfBoundsException if index < 0 || index > size() 2505: * @throws ClassCastException if o cannot be added to this list due to its 2506: * type 2507: * @throws IllegalArgumentException if o cannot be added to this list for 2508: * some other reason 2509: * @throws NullPointerException if o is null and this list doesn't support 2510: * the addition of null values. 2511: */ 2512: public void add(int index, Object o) 2513: { 2514: synchronized (mutex) 2515: { 2516: list.add(index, o); 2517: } 2518: } 2519: 2520: /** 2521: * Add the contents of a collection to the underlying list at the given 2522: * index (optional operation). If the list imposes restraints on what 2523: * can be inserted, such as no null elements, this should be documented. 2524: * A lock is obtained on the mutex before any of the elements are added. 2525: * 2526: * @param index the index at which to insert 2527: * @param c the collection to add 2528: * @return <code>true</code>, as defined by Collection for a modified list 2529: * @throws UnsupportedOperationException if this list does not support the 2530: * add operation 2531: * @throws ClassCastException if o cannot be added to this list due to its 2532: * type 2533: * @throws IllegalArgumentException if o cannot be added to this list for 2534: * some other reason 2535: * @throws NullPointerException if o is null and this list doesn't support 2536: * the addition of null values. 2537: */ 2538: public boolean addAll(int index, Collection c) 2539: { 2540: synchronized (mutex) 2541: { 2542: return list.addAll(index, c); 2543: } 2544: } 2545: 2546: /** 2547: * Tests whether the underlying list is equal to the supplied object. 2548: * The object is deemed to be equal if it is also a <code>List</code> 2549: * of equal size and with the same elements (i.e. each element, e1, 2550: * in list, l1, and each element, e2, in l2, must return <code>true</code> for 2551: * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the 2552: * comparison is made, a lock is obtained on the mutex. 2553: * 2554: * @param o The object to test for equality with the underlying list. 2555: * @return <code>true</code> if o is equal to the underlying list under the above 2556: * definition. 2557: */ 2558: public boolean equals(Object o) 2559: { 2560: synchronized (mutex) 2561: { 2562: return list.equals(o); 2563: } 2564: } 2565: 2566: /** 2567: * Retrieves the object at the specified index. A lock 2568: * is obtained on the mutex before the list is accessed. 2569: * 2570: * @param index the index of the element to be returned 2571: * @return the element at index index in this list 2572: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2573: */ 2574: public Object get(int index) 2575: { 2576: synchronized (mutex) 2577: { 2578: return list.get(index); 2579: } 2580: } 2581: 2582: /** 2583: * Obtains a hashcode for the underlying list, first obtaining 2584: * a lock on the mutex. The calculation of the hashcode is 2585: * detailed in the documentation for the <code>List</code> 2586: * interface. 2587: * 2588: * @return The hashcode of the underlying list. 2589: * @see List#hashCode() 2590: */ 2591: public int hashCode() 2592: { 2593: synchronized (mutex) 2594: { 2595: return list.hashCode(); 2596: } 2597: } 2598: 2599: /** 2600: * Obtain the first index at which a given object is to be found in the 2601: * underlying list. A lock is obtained on the mutex before the list is 2602: * accessed. 2603: * 2604: * @param o the object to search for 2605: * @return the least integer n such that <code>o == null ? get(n) == null : 2606: * o.equals(get(n))</code>, or -1 if there is no such index. 2607: * @throws ClassCastException if the type of o is not a valid 2608: * type for this list. 2609: * @throws NullPointerException if o is null and this 2610: * list does not support null values. 2611: */ 2612: 2613: public int indexOf(Object o) 2614: { 2615: synchronized (mutex) 2616: { 2617: return list.indexOf(o); 2618: } 2619: } 2620: 2621: /** 2622: * Obtain the last index at which a given object is to be found in this 2623: * underlying list. A lock is obtained on the mutex before the list 2624: * is accessed. 2625: * 2626: * @return the greatest integer n such that <code>o == null ? get(n) == null 2627: * : o.equals(get(n))</code>, or -1 if there is no such index. 2628: * @throws ClassCastException if the type of o is not a valid 2629: * type for this list. 2630: * @throws NullPointerException if o is null and this 2631: * list does not support null values. 2632: */ 2633: public int lastIndexOf(Object o) 2634: { 2635: synchronized (mutex) 2636: { 2637: return list.lastIndexOf(o); 2638: } 2639: } 2640: 2641: /** 2642: * Retrieves a synchronized wrapper around the underlying list's 2643: * list iterator. A lock is obtained on the mutex before the 2644: * list iterator is retrieved. 2645: * 2646: * @return A list iterator over the elements in the underlying list. 2647: * The list iterator allows additional list-specific operations 2648: * to be performed, in addition to those supplied by the 2649: * standard iterator. 2650: */ 2651: public ListIterator listIterator() 2652: { 2653: synchronized (mutex) 2654: { 2655: return new SynchronizedListIterator(mutex, list.listIterator()); 2656: } 2657: } 2658: 2659: /** 2660: * Retrieves a synchronized wrapper around the underlying list's 2661: * list iterator. A lock is obtained on the mutex before the 2662: * list iterator is retrieved. The iterator starts at the 2663: * index supplied, leading to the element at that index being 2664: * the first one returned by <code>next()</code>. Calling 2665: * <code>previous()</code> from this initial position returns 2666: * index - 1. 2667: * 2668: * @param index the position, between 0 and size() inclusive, to begin the 2669: * iteration from 2670: * @return A list iterator over the elements in the underlying list. 2671: * The list iterator allows additional list-specific operations 2672: * to be performed, in addition to those supplied by the 2673: * standard iterator. 2674: * @throws IndexOutOfBoundsException if index < 0 || index > size() 2675: */ 2676: public ListIterator listIterator(int index) 2677: { 2678: synchronized (mutex) 2679: { 2680: return new SynchronizedListIterator(mutex, list.listIterator(index)); 2681: } 2682: } 2683: 2684: /** 2685: * Remove the element at a given position in the underlying list (optional 2686: * operation). All remaining elements are shifted to the left to fill the gap. 2687: * A lock on the mutex is obtained before the element is removed. 2688: * 2689: * @param index the position within the list of the object to remove 2690: * @return the object that was removed 2691: * @throws UnsupportedOperationException if this list does not support the 2692: * remove operation 2693: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2694: */ 2695: public Object remove(int index) 2696: { 2697: synchronized (mutex) 2698: { 2699: return list.remove(index); 2700: } 2701: } 2702: 2703: /** 2704: * Replace an element of the underlying list with another object (optional 2705: * operation). A lock is obtained on the mutex before the element is 2706: * replaced. 2707: * 2708: * @param index the position within this list of the element to be replaced 2709: * @param o the object to replace it with 2710: * @return the object that was replaced 2711: * @throws UnsupportedOperationException if this list does not support the 2712: * set operation. 2713: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2714: * @throws ClassCastException if o cannot be added to this list due to its 2715: * type 2716: * @throws IllegalArgumentException if o cannot be added to this list for 2717: * some other reason 2718: * @throws NullPointerException if o is null and this 2719: * list does not support null values. 2720: */ 2721: public Object set(int index, Object o) 2722: { 2723: synchronized (mutex) 2724: { 2725: return list.set(index, o); 2726: } 2727: } 2728: 2729: /** 2730: * Obtain a List view of a subsection of the underlying list, from fromIndex 2731: * (inclusive) to toIndex (exclusive). If the two indices are equal, the 2732: * sublist is empty. The returned list should be modifiable if and only 2733: * if this list is modifiable. Changes to the returned list should be 2734: * reflected in this list. If this list is structurally modified in 2735: * any way other than through the returned list, the result of any subsequent 2736: * operations on the returned list is undefined. A lock is obtained 2737: * on the mutex before the creation of the sublist. The returned list 2738: * is also synchronized, using the same mutex. 2739: * 2740: * @param fromIndex the index that the returned list should start from 2741: * (inclusive) 2742: * @param toIndex the index that the returned list should go to (exclusive) 2743: * @return a List backed by a subsection of this list 2744: * @throws IndexOutOfBoundsException if fromIndex < 0 2745: * || toIndex > size() || fromIndex > toIndex 2746: */ 2747: public List subList(int fromIndex, int toIndex) 2748: { 2749: synchronized (mutex) 2750: { 2751: return new SynchronizedList(mutex, list.subList(fromIndex, toIndex)); 2752: } 2753: } 2754: } // class SynchronizedList 2755: 2756: /** 2757: * The implementation of {@link #synchronizedList(List)} for random-access 2758: * lists. This class name is required for compatibility with Sun's JDK 2759: * serializability. 2760: * 2761: * @author Eric Blake (ebb9@email.byu.edu) 2762: */ 2763: private static final class SynchronizedRandomAccessList 2764: extends SynchronizedList implements RandomAccess 2765: { 2766: /** 2767: * Compatible with JDK 1.4. 2768: */ 2769: private static final long serialVersionUID = 1530674583602358482L; 2770: 2771: /** 2772: * Wrap a given list. 2773: * @param l the list to wrap 2774: * @throws NullPointerException if l is null 2775: */ 2776: SynchronizedRandomAccessList(List l) 2777: { 2778: super(l); 2779: } 2780: 2781: /** 2782: * Called only by trusted code to specify the mutex as well as the 2783: * collection. 2784: * @param sync the mutex 2785: * @param l the list 2786: */ 2787: SynchronizedRandomAccessList(Object sync, List l) 2788: { 2789: super(sync, l); 2790: } 2791: 2792: /** 2793: * Obtain a List view of a subsection of the underlying list, from fromIndex 2794: * (inclusive) to toIndex (exclusive). If the two indices are equal, the 2795: * sublist is empty. The returned list should be modifiable if and only 2796: * if this list is modifiable. Changes to the returned list should be 2797: * reflected in this list. If this list is structurally modified in 2798: * any way other than through the returned list, the result of any subsequent 2799: * operations on the returned list is undefined. A lock is obtained 2800: * on the mutex before the creation of the sublist. The returned list 2801: * is also synchronized, using the same mutex. Random accessibility 2802: * is also extended to the new list. 2803: * 2804: * @param fromIndex the index that the returned list should start from 2805: * (inclusive) 2806: * @param toIndex the index that the returned list should go to (exclusive) 2807: * @return a List backed by a subsection of this list 2808: * @throws IndexOutOfBoundsException if fromIndex < 0 2809: * || toIndex > size() || fromIndex > toIndex 2810: */ 2811: public List subList(int fromIndex, int toIndex) 2812: { 2813: synchronized (mutex) 2814: { 2815: return new SynchronizedRandomAccessList(mutex, 2816: list.subList(fromIndex, 2817: toIndex)); 2818: } 2819: } 2820: } // class SynchronizedRandomAccessList 2821: 2822: /** 2823: * The implementation of {@link SynchronizedList#listIterator()}. This 2824: * iterator must "sync" on the same object as the list it iterates over. 2825: * 2826: * @author Eric Blake (ebb9@email.byu.edu) 2827: */ 2828: private static final class SynchronizedListIterator 2829: extends SynchronizedIterator implements ListIterator 2830: { 2831: /** 2832: * The wrapped iterator, stored both here and in the superclass to 2833: * avoid excessive casting. 2834: */ 2835: private final ListIterator li; 2836: 2837: /** 2838: * Only trusted code creates a wrapper, with the specified sync. 2839: * @param sync the mutex 2840: * @param li the wrapped iterator 2841: */ 2842: SynchronizedListIterator(Object sync, ListIterator li) 2843: { 2844: super(sync, li); 2845: this.li = li; 2846: } 2847: 2848: /** 2849: * Insert an element into the underlying list at the current position of 2850: * the iterator (optional operation). The element is inserted in between 2851: * the element that would be returned by <code>previous()</code> and the 2852: * element that would be returned by <code>next()</code>. After the 2853: * insertion, a subsequent call to next is unaffected, but 2854: * a call to previous returns the item that was added. The values returned 2855: * by nextIndex() and previousIndex() are incremented. A lock is obtained 2856: * on the mutex before the addition takes place. 2857: * 2858: * @param o the object to insert into the list 2859: * @throws ClassCastException if the object is of a type which cannot be added 2860: * to this list. 2861: * @throws IllegalArgumentException if some other aspect of the object stops 2862: * it being added to this list. 2863: * @throws UnsupportedOperationException if this ListIterator does not 2864: * support the add operation. 2865: */ 2866: public void add(Object o) 2867: { 2868: synchronized (mutex) 2869: { 2870: li.add(o); 2871: } 2872: } 2873: 2874: /** 2875: * Tests whether there are elements remaining in the underlying list 2876: * in the reverse direction. In other words, <code>previous()</code> 2877: * will not fail with a NoSuchElementException. A lock is obtained 2878: * on the mutex before the check takes place. 2879: * 2880: * @return <code>true</code> if the list continues in the reverse direction 2881: */ 2882: public boolean hasPrevious() 2883: { 2884: synchronized (mutex) 2885: { 2886: return li.hasPrevious(); 2887: } 2888: } 2889: 2890: /** 2891: * Find the index of the element that would be returned by a call to 2892: * <code>next()</code>. If hasNext() returns <code>false</code>, this 2893: * returns the list size. A lock is obtained on the mutex before the 2894: * query takes place. 2895: * 2896: * @return the index of the element that would be returned by next() 2897: */ 2898: public int nextIndex() 2899: { 2900: synchronized (mutex) 2901: { 2902: return li.nextIndex(); 2903: } 2904: } 2905: 2906: /** 2907: * Obtain the previous element from the underlying list. Repeated 2908: * calls to previous may be used to iterate backwards over the entire list, 2909: * or calls to next and previous may be used together to go forwards and 2910: * backwards. Alternating calls to next and previous will return the same 2911: * element. A lock is obtained on the mutex before the object is retrieved. 2912: * 2913: * @return the next element in the list in the reverse direction 2914: * @throws NoSuchElementException if there are no more elements 2915: */ 2916: public Object previous() 2917: { 2918: synchronized (mutex) 2919: { 2920: return li.previous(); 2921: } 2922: } 2923: 2924: /** 2925: * Find the index of the element that would be returned by a call to 2926: * previous. If hasPrevious() returns <code>false</code>, this returns -1. 2927: * A lock is obtained on the mutex before the query takes place. 2928: * 2929: * @return the index of the element that would be returned by previous() 2930: */ 2931: public int previousIndex() 2932: { 2933: synchronized (mutex) 2934: { 2935: return li.previousIndex(); 2936: } 2937: } 2938: 2939: /** 2940: * Replace the element last returned by a call to <code>next()</code> or 2941: * <code>previous()</code> with a given object (optional operation). This 2942: * method may only be called if neither <code>add()</code> nor 2943: * <code>remove()</code> have been called since the last call to 2944: * <code>next()</code> or <code>previous</code>. A lock is obtained 2945: * on the mutex before the list is modified. 2946: * 2947: * @param o the object to replace the element with 2948: * @throws ClassCastException the object is of a type which cannot be added 2949: * to this list 2950: * @throws IllegalArgumentException some other aspect of the object stops 2951: * it being added to this list 2952: * @throws IllegalStateException if neither next or previous have been 2953: * called, or if add or remove has been called since the last call 2954: * to next or previous 2955: * @throws UnsupportedOperationException if this ListIterator does not 2956: * support the set operation 2957: */ 2958: public void set(Object o) 2959: { 2960: synchronized (mutex) 2961: { 2962: li.set(o); 2963: } 2964: } 2965: } // class SynchronizedListIterator 2966: 2967: /** 2968: * Returns a synchronized (thread-safe) map wrapper backed by the given 2969: * map. Notice that element access through the collection views and their 2970: * iterators are thread-safe, but if the map can be structurally modified 2971: * (adding or removing elements) then you should synchronize around the 2972: * iteration to avoid non-deterministic behavior:<br> 2973: * <pre> 2974: * Map m = Collections.synchronizedMap(new Map(...)); 2975: * ... 2976: * Set s = m.keySet(); // safe outside a synchronized block 2977: * synchronized (m) // synch on m, not s 2978: * { 2979: * Iterator i = s.iterator(); 2980: * while (i.hasNext()) 2981: * foo(i.next()); 2982: * } 2983: * </pre><p> 2984: * 2985: * The returned Map implements Serializable, but can only be serialized if 2986: * the map it wraps is likewise Serializable. 2987: * 2988: * @param m the map to wrap 2989: * @return a synchronized view of the map 2990: * @see Serializable 2991: */ 2992: public static Map synchronizedMap(Map m) 2993: { 2994: return new SynchronizedMap(m); 2995: } 2996: 2997: /** 2998: * The implementation of {@link #synchronizedMap(Map)}. This 2999: * class name is required for compatibility with Sun's JDK serializability. 3000: * 3001: * @author Eric Blake (ebb9@email.byu.edu) 3002: */ 3003: private static class SynchronizedMap implements Map, Serializable 3004: { 3005: /** 3006: * Compatible with JDK 1.4. 3007: */ 3008: private static final long serialVersionUID = 1978198479659022715L; 3009: 3010: /** 3011: * The wrapped map. 3012: * @serial the real map 3013: */ 3014: private final Map m; 3015: 3016: /** 3017: * The object to synchronize on. When an instance is created via public 3018: * methods, it will be this; but other uses like 3019: * SynchronizedSortedMap.subMap() must specify another mutex. Package 3020: * visible for use by subclass. 3021: * @serial the lock 3022: */ 3023: final Object mutex; 3024: 3025: /** 3026: * Cache the entry set. 3027: */ 3028: private transient Set entries; 3029: 3030: /** 3031: * Cache the key set. 3032: */ 3033: private transient Set keys; 3034: 3035: /** 3036: * Cache the value collection. 3037: */ 3038: private transient Collection values; 3039: 3040: /** 3041: * Wrap a given map. 3042: * @param m the map to wrap 3043: * @throws NullPointerException if m is null 3044: */ 3045: SynchronizedMap(Map m) 3046: { 3047: this.m = m; 3048: mutex = this; 3049: if (m == null) 3050: throw new NullPointerException(); 3051: } 3052: 3053: /** 3054: * Called only by trusted code to specify the mutex as well as the map. 3055: * @param sync the mutex 3056: * @param m the map 3057: */ 3058: SynchronizedMap(Object sync, Map m) 3059: { 3060: this.m = m; 3061: mutex = sync; 3062: } 3063: 3064: /** 3065: * Clears all the entries from the underlying map. A lock is obtained 3066: * on the mutex before the map is cleared. 3067: * 3068: * @throws UnsupportedOperationException if clear is not supported 3069: */ 3070: public void clear() 3071: { 3072: synchronized (mutex) 3073: { 3074: m.clear(); 3075: } 3076: } 3077: 3078: /** 3079: * Returns <code>true</code> if the underlying map contains a entry for the given key. 3080: * A lock is obtained on the mutex before the map is queried. 3081: * 3082: * @param key the key to search for. 3083: * @return <code>true</code> if the underlying map contains the key. 3084: * @throws ClassCastException if the key is of an inappropriate type. 3085: * @throws NullPointerException if key is <code>null</code> but the map 3086: * does not permit null keys. 3087: */ 3088: public boolean containsKey(Object key) 3089: { 3090: synchronized (mutex) 3091: { 3092: return m.containsKey(key); 3093: } 3094: } 3095: 3096: /** 3097: * Returns <code>true</code> if the underlying map contains at least one entry with the 3098: * given value. In other words, returns <code>true</code> if a value v exists where 3099: * <code>(value == null ? v == null : value.equals(v))</code>. This usually 3100: * requires linear time. A lock is obtained on the mutex before the map 3101: * is queried. 3102: * 3103: * @param value the value to search for 3104: * @return <code>true</code> if the map contains the value 3105: * @throws ClassCastException if the type of the value is not a valid type 3106: * for this map. 3107: * @throws NullPointerException if the value is null and the map doesn't 3108: * support null values. 3109: */ 3110: public boolean containsValue(Object value) 3111: { 3112: synchronized (mutex) 3113: { 3114: return m.containsValue(value); 3115: } 3116: } 3117: 3118: // This is one of the ickiest cases of nesting I've ever seen. It just 3119: // means "return a SynchronizedSet, except that the iterator() method 3120: // returns an SynchronizedIterator whose next() method returns a 3121: // synchronized wrapper around its normal return value". 3122: public Set entrySet() 3123: { 3124: // Define this here to spare some nesting. 3125: class SynchronizedMapEntry implements Map.Entry 3126: { 3127: final Map.Entry e; 3128: SynchronizedMapEntry(Object o) 3129: { 3130: e = (Map.Entry) o; 3131: } 3132: 3133: /** 3134: * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code> 3135: * with the same key and value as the underlying entry. A lock is 3136: * obtained on the mutex before the comparison takes place. 3137: * 3138: * @param o The object to compare with this entry. 3139: * @return <code>true</code> if o is equivalent to the underlying map entry. 3140: */ 3141: public boolean equals(Object o) 3142: { 3143: synchronized (mutex) 3144: { 3145: return e.equals(o); 3146: } 3147: } 3148: 3149: /** 3150: * Returns the key used in the underlying map entry. A lock is obtained 3151: * on the mutex before the key is retrieved. 3152: * 3153: * @return The key of the underlying map entry. 3154: */ 3155: public Object getKey() 3156: { 3157: synchronized (mutex) 3158: { 3159: return e.getKey(); 3160: } 3161: } 3162: 3163: /** 3164: * Returns the value used in the underlying map entry. A lock is obtained 3165: * on the mutex before the value is retrieved. 3166: * 3167: * @return The value of the underlying map entry. 3168: */ 3169: public Object getValue() 3170: { 3171: synchronized (mutex) 3172: { 3173: return e.getValue(); 3174: } 3175: } 3176: 3177: /** 3178: * Computes the hash code for the underlying map entry. 3179: * This computation is described in the documentation for the 3180: * <code>Map</code> interface. A lock is obtained on the mutex 3181: * before the underlying map is accessed. 3182: * 3183: * @return The hash code of the underlying map entry. 3184: * @see Map#hashCode() 3185: */ 3186: public int hashCode() 3187: { 3188: synchronized (mutex) 3189: { 3190: return e.hashCode(); 3191: } 3192: } 3193: 3194: /** 3195: * Replaces the value in the underlying map entry with the specified 3196: * object (optional operation). A lock is obtained on the mutex 3197: * before the map is altered. The map entry, in turn, will alter 3198: * the underlying map object. The operation is undefined if the 3199: * <code>remove()</code> method of the iterator has been called 3200: * beforehand. 3201: * 3202: * @param value the new value to store 3203: * @return the old value 3204: * @throws UnsupportedOperationException if the operation is not supported. 3205: * @throws ClassCastException if the value is of the wrong type. 3206: * @throws IllegalArgumentException if something about the value 3207: * prevents it from existing in this map. 3208: * @throws NullPointerException if the map forbids null values. 3209: */ 3210: public Object setValue(Object value) 3211: { 3212: synchronized (mutex) 3213: { 3214: return e.setValue(value); 3215: } 3216: } 3217: 3218: /** 3219: * Returns a textual representation of the underlying map entry. 3220: * A lock is obtained on the mutex before the entry is accessed. 3221: * 3222: * @return The contents of the map entry in <code>String</code> form. 3223: */ 3224: public String toString() 3225: { 3226: synchronized (mutex) 3227: { 3228: return e.toString(); 3229: } 3230: } 3231: } // class SynchronizedMapEntry 3232: 3233: // Now the actual code. 3234: if (entries == null) 3235: synchronized (mutex) 3236: { 3237: entries = new SynchronizedSet(mutex, m.entrySet()) 3238: { 3239: /** 3240: * Returns an iterator over the set. The iterator has no specific order, 3241: * unless further specified. A lock is obtained on the set's mutex 3242: * before the iterator is created. The created iterator is also 3243: * thread-safe. 3244: * 3245: * @return A synchronized set iterator. 3246: */ 3247: public Iterator iterator() 3248: { 3249: synchronized (super.mutex) 3250: { 3251: return new SynchronizedIterator(super.mutex, c.iterator()) 3252: { 3253: /** 3254: * Retrieves the next map entry from the iterator. 3255: * A lock is obtained on the iterator's mutex before 3256: * the entry is created. The new map entry is enclosed in 3257: * a thread-safe wrapper. 3258: * 3259: * @return A synchronized map entry. 3260: */ 3261: public Object next() 3262: { 3263: synchronized (super.mutex) 3264: { 3265: return new SynchronizedMapEntry(super.next()); 3266: } 3267: } 3268: }; 3269: } 3270: } 3271: }; 3272: } 3273: return entries; 3274: } 3275: 3276: /** 3277: * Returns <code>true</code> if the object, o, is also an instance 3278: * of <code>Map</code> and contains an equivalent 3279: * entry set to that of the underlying map. A lock 3280: * is obtained on the mutex before the objects are 3281: * compared. 3282: * 3283: * @param o The object to compare. 3284: * @return <code>true</code> if o and the underlying map are equivalent. 3285: */ 3286: public boolean equals(Object o) 3287: { 3288: synchronized (mutex) 3289: { 3290: return m.equals(o); 3291: } 3292: } 3293: 3294: /** 3295: * Returns the value associated with the given key, or null 3296: * if no such mapping exists. An ambiguity exists with maps 3297: * that accept null values as a return value of null could 3298: * be due to a non-existent mapping or simply a null value 3299: * for that key. To resolve this, <code>containsKey</code> 3300: * should be used. A lock is obtained on the mutex before 3301: * the value is retrieved from the underlying map. 3302: * 3303: * @param key The key of the required mapping. 3304: * @return The value associated with the given key, or 3305: * null if no such mapping exists. 3306: * @throws ClassCastException if the key is an inappropriate type. 3307: * @throws NullPointerException if this map does not accept null keys. 3308: */ 3309: public Object get(Object key) 3310: { 3311: synchronized (mutex) 3312: { 3313: return m.get(key); 3314: } 3315: } 3316: 3317: /** 3318: * Calculates the hash code of the underlying map as the 3319: * sum of the hash codes of all entries. A lock is obtained 3320: * on the mutex before the hash code is computed. 3321: * 3322: * @return The hash code of the underlying map. 3323: */ 3324: public int hashCode() 3325: { 3326: synchronized (mutex) 3327: { 3328: return m.hashCode(); 3329: } 3330: } 3331: 3332: /** 3333: * Returns <code>true</code> if the underlying map contains no entries. 3334: * A lock is obtained on the mutex before the map is examined. 3335: * 3336: * @return <code>true</code> if the map is empty. 3337: */ 3338: public boolean isEmpty() 3339: { 3340: synchronized (mutex) 3341: { 3342: return m.isEmpty(); 3343: } 3344: } 3345: 3346: /** 3347: * Returns a thread-safe set view of the keys in the underlying map. The 3348: * set is backed by the map, so that changes in one show up in the other. 3349: * Modifications made while an iterator is in progress cause undefined 3350: * behavior. If the set supports removal, these methods remove the 3351: * underlying mapping from the map: <code>Iterator.remove</code>, 3352: * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, 3353: * and <code>clear</code>. Element addition, via <code>add</code> or 3354: * <code>addAll</code>, is not supported via this set. A lock is obtained 3355: * on the mutex before the set is created. 3356: * 3357: * @return A synchronized set containing the keys of the underlying map. 3358: */ 3359: public Set keySet() 3360: { 3361: if (keys == null) 3362: synchronized (mutex) 3363: { 3364: keys = new SynchronizedSet(mutex, m.keySet()); 3365: } 3366: return keys; 3367: } 3368: 3369: /** 3370: * Associates the given key to the given value (optional operation). If the 3371: * underlying map already contains the key, its value is replaced. Be aware 3372: * that in a map that permits <code>null</code> values, a null return does not 3373: * always imply that the mapping was created. A lock is obtained on the mutex 3374: * before the modification is made. 3375: * 3376: * @param key the key to map. 3377: * @param value the value to be mapped. 3378: * @return the previous value of the key, or null if there was no mapping 3379: * @throws UnsupportedOperationException if the operation is not supported 3380: * @throws ClassCastException if the key or value is of the wrong type 3381: * @throws IllegalArgumentException if something about this key or value 3382: * prevents it from existing in this map 3383: * @throws NullPointerException if either the key or the value is null, 3384: * and the map forbids null keys or values 3385: * @see #containsKey(Object) 3386: */ 3387: public Object put(Object key, Object value) 3388: { 3389: synchronized (mutex) 3390: { 3391: return m.put(key, value); 3392: } 3393: } 3394: 3395: /** 3396: * Copies all entries of the given map to the underlying one (optional 3397: * operation). If the map already contains a key, its value is replaced. 3398: * A lock is obtained on the mutex before the operation proceeds. 3399: * 3400: * @param map the mapping to load into this map 3401: * @throws UnsupportedOperationException if the operation is not supported 3402: * @throws ClassCastException if a key or value is of the wrong type 3403: * @throws IllegalArgumentException if something about a key or value 3404: * prevents it from existing in this map 3405: * @throws NullPointerException if the map forbids null keys or values, or 3406: * if <code>m</code> is null. 3407: * @see #put(Object, Object) 3408: */ 3409: public void putAll(Map map) 3410: { 3411: synchronized (mutex) 3412: { 3413: m.putAll(map); 3414: } 3415: } 3416: 3417: /** 3418: * Removes the mapping for the key, o, if present (optional operation). If 3419: * the key is not present, this returns null. Note that maps which permit 3420: * null values may also return null if the key was removed. A prior 3421: * <code>containsKey()</code> check is required to avoid this ambiguity. 3422: * Before the mapping is removed, a lock is obtained on the mutex. 3423: * 3424: * @param o the key to remove 3425: * @return the value the key mapped to, or null if not present 3426: * @throws UnsupportedOperationException if deletion is unsupported 3427: * @throws NullPointerException if the key is null and this map doesn't 3428: * support null keys. 3429: * @throws ClassCastException if the type of the key is not a valid type 3430: * for this map. 3431: */ 3432: public Object remove(Object o) 3433: { 3434: synchronized (mutex) 3435: { 3436: return m.remove(o); 3437: } 3438: } 3439: 3440: /** 3441: * Retrieves the size of the underlying map. A lock 3442: * is obtained on the mutex before access takes place. 3443: * Maps with a size greater than <code>Integer.MAX_VALUE</code> 3444: * return <code>Integer.MAX_VALUE</code> instead. 3445: * 3446: * @return The size of the underlying map. 3447: */ 3448: public int size() 3449: { 3450: synchronized (mutex) 3451: { 3452: return m.size(); 3453: } 3454: } 3455: 3456: /** 3457: * Returns a textual representation of the underlying 3458: * map. A lock is obtained on the mutex before the map 3459: * is accessed. 3460: * 3461: * @return The map in <code>String</code> form. 3462: */ 3463: public String toString() 3464: { 3465: synchronized (mutex) 3466: { 3467: return m.toString(); 3468: } 3469: } 3470: 3471: /** 3472: * Returns a synchronized collection view of the values in the underlying 3473: * map. The collection is backed by the map, so that changes in one show up in 3474: * the other. Modifications made while an iterator is in progress cause 3475: * undefined behavior. If the collection supports removal, these methods 3476: * remove the underlying mapping from the map: <code>Iterator.remove</code>, 3477: * <code>Collection.remove</code>, <code>removeAll</code>, 3478: * <code>retainAll</code>, and <code>clear</code>. Element addition, via 3479: * <code>add</code> or <code>addAll</code>, is not supported via this 3480: * collection. A lock is obtained on the mutex before the collection 3481: * is created. 3482: * 3483: * @return the collection of all values in the underlying map. 3484: */ 3485: public Collection values() 3486: { 3487: if (values == null) 3488: synchronized (mutex) 3489: { 3490: values = new SynchronizedCollection(mutex, m.values()); 3491: } 3492: return values; 3493: } 3494: } // class SynchronizedMap 3495: 3496: /** 3497: * Returns a synchronized (thread-safe) set wrapper backed by the given 3498: * set. Notice that element access through the iterator is thread-safe, but 3499: * if the set can be structurally modified (adding or removing elements) 3500: * then you should synchronize around the iteration to avoid 3501: * non-deterministic behavior:<br> 3502: * <pre> 3503: * Set s = Collections.synchronizedSet(new Set(...)); 3504: * ... 3505: * synchronized (s) 3506: * { 3507: * Iterator i = s.iterator(); 3508: * while (i.hasNext()) 3509: * foo(i.next()); 3510: * } 3511: * </pre><p> 3512: * 3513: * The returned Set implements Serializable, but can only be serialized if 3514: * the set it wraps is likewise Serializable. 3515: * 3516: * @param s the set to wrap 3517: * @return a synchronized view of the set 3518: * @see Serializable 3519: */ 3520: public static Set synchronizedSet(Set s) 3521: { 3522: return new SynchronizedSet(s); 3523: } 3524: 3525: /** 3526: * The implementation of {@link #synchronizedSet(Set)}. This class 3527: * name is required for compatibility with Sun's JDK serializability. 3528: * Package visible, so that sets such as Hashtable.keySet() 3529: * can specify which object to synchronize on. 3530: * 3531: * @author Eric Blake (ebb9@email.byu.edu) 3532: */ 3533: static class SynchronizedSet extends SynchronizedCollection 3534: implements Set 3535: { 3536: /** 3537: * Compatible with JDK 1.4. 3538: */ 3539: private static final long serialVersionUID = 487447009682186044L; 3540: 3541: /** 3542: * Wrap a given set. 3543: * @param s the set to wrap 3544: * @throws NullPointerException if s is null 3545: */ 3546: SynchronizedSet(Set s) 3547: { 3548: super(s); 3549: } 3550: 3551: /** 3552: * Called only by trusted code to specify the mutex as well as the set. 3553: * @param sync the mutex 3554: * @param s the set 3555: */ 3556: SynchronizedSet(Object sync, Set s) 3557: { 3558: super(sync, s); 3559: } 3560: 3561: /** 3562: * Returns <code>true</code> if the object, o, is a <code>Set</code> 3563: * of the same size as the underlying set, and contains 3564: * each element, e, which occurs in the underlying set. 3565: * A lock is obtained on the mutex before the comparison 3566: * takes place. 3567: * 3568: * @param o The object to compare against. 3569: * @return <code>true</code> if o is an equivalent set. 3570: */ 3571: public boolean equals(Object o) 3572: { 3573: synchronized (mutex) 3574: { 3575: return c.equals(o); 3576: } 3577: } 3578: 3579: /** 3580: * Computes the hash code for the underlying set as the 3581: * sum of the hash code of all elements within the set. 3582: * A lock is obtained on the mutex before the computation 3583: * occurs. 3584: * 3585: * @return The hash code for the underlying set. 3586: */ 3587: public int hashCode() 3588: { 3589: synchronized (mutex) 3590: { 3591: return c.hashCode(); 3592: } 3593: } 3594: } // class SynchronizedSet 3595: 3596: /** 3597: * Returns a synchronized (thread-safe) sorted map wrapper backed by the 3598: * given map. Notice that element access through the collection views, 3599: * subviews, and their iterators are thread-safe, but if the map can be 3600: * structurally modified (adding or removing elements) then you should 3601: * synchronize around the iteration to avoid non-deterministic behavior:<br> 3602: * <pre> 3603: * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...)); 3604: * ... 3605: * Set s = m.keySet(); // safe outside a synchronized block 3606: * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block 3607: * Set s2 = m2.keySet(); // safe outside a synchronized block 3608: * synchronized (m) // synch on m, not m2, s or s2 3609: * { 3610: * Iterator i = s.iterator(); 3611: * while (i.hasNext()) 3612: * foo(i.next()); 3613: * i = s2.iterator(); 3614: * while (i.hasNext()) 3615: * bar(i.next()); 3616: * } 3617: * </pre><p> 3618: * 3619: * The returned SortedMap implements Serializable, but can only be 3620: * serialized if the map it wraps is likewise Serializable. 3621: * 3622: * @param m the sorted map to wrap 3623: * @return a synchronized view of the sorted map 3624: * @see Serializable 3625: */ 3626: public static SortedMap synchronizedSortedMap(SortedMap m) 3627: { 3628: return new SynchronizedSortedMap(m); 3629: } 3630: 3631: /** 3632: * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This 3633: * class name is required for compatibility with Sun's JDK serializability. 3634: * 3635: * @author Eric Blake (ebb9@email.byu.edu) 3636: */ 3637: private static final class SynchronizedSortedMap extends SynchronizedMap 3638: implements SortedMap 3639: { 3640: /** 3641: * Compatible with JDK 1.4. 3642: */ 3643: private static final long serialVersionUID = -8798146769416483793L; 3644: 3645: /** 3646: * The wrapped map; stored both here and in the superclass to avoid 3647: * excessive casting. 3648: * @serial the wrapped map 3649: */ 3650: private final SortedMap sm; 3651: 3652: /** 3653: * Wrap a given map. 3654: * @param sm the map to wrap 3655: * @throws NullPointerException if sm is null 3656: */ 3657: SynchronizedSortedMap(SortedMap sm) 3658: { 3659: super(sm); 3660: this.sm = sm; 3661: } 3662: 3663: /** 3664: * Called only by trusted code to specify the mutex as well as the map. 3665: * @param sync the mutex 3666: * @param sm the map 3667: */ 3668: SynchronizedSortedMap(Object sync, SortedMap sm) 3669: { 3670: super(sync, sm); 3671: this.sm = sm; 3672: } 3673: 3674: /** 3675: * Returns the comparator used in sorting the underlying map, or null if 3676: * it is the keys' natural ordering. A lock is obtained on the mutex 3677: * before the comparator is retrieved. 3678: * 3679: * @return the sorting comparator. 3680: */ 3681: public Comparator comparator() 3682: { 3683: synchronized (mutex) 3684: { 3685: return sm.comparator(); 3686: } 3687: } 3688: 3689: /** 3690: * Returns the first, lowest sorted, key from the underlying map. 3691: * A lock is obtained on the mutex before the map is accessed. 3692: * 3693: * @return the first key. 3694: * @throws NoSuchElementException if this map is empty. 3695: */ 3696: public Object firstKey() 3697: { 3698: synchronized (mutex) 3699: { 3700: return sm.firstKey(); 3701: } 3702: } 3703: 3704: /** 3705: * Returns a submap containing the keys from the first 3706: * key (as returned by <code>firstKey()</code>) to 3707: * the key before that specified. The submap supports all 3708: * operations supported by the underlying map and all actions 3709: * taking place on the submap are also reflected in the underlying 3710: * map. A lock is obtained on the mutex prior to submap creation. 3711: * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>. 3712: * The submap retains the thread-safe status of this map. 3713: * 3714: * @param toKey the exclusive upper range of the submap. 3715: * @return a submap from <code>firstKey()</code> to the 3716: * the key preceding toKey. 3717: * @throws ClassCastException if toKey is not comparable to the underlying 3718: * map's contents. 3719: * @throws IllegalArgumentException if toKey is outside the map's range. 3720: * @throws NullPointerException if toKey is null. but the map does not allow 3721: * null keys. 3722: */ 3723: public SortedMap headMap(Object toKey) 3724: { 3725: synchronized (mutex) 3726: { 3727: return new SynchronizedSortedMap(mutex, sm.headMap(toKey)); 3728: } 3729: } 3730: 3731: /** 3732: * Returns the last, highest sorted, key from the underlying map. 3733: * A lock is obtained on the mutex before the map is accessed. 3734: * 3735: * @return the last key. 3736: * @throws NoSuchElementException if this map is empty. 3737: */ 3738: public Object lastKey() 3739: { 3740: synchronized (mutex) 3741: { 3742: return sm.lastKey(); 3743: } 3744: } 3745: 3746: /** 3747: * Returns a submap containing the keys from fromKey to 3748: * the key before toKey. The submap supports all 3749: * operations supported by the underlying map and all actions 3750: * taking place on the submap are also reflected in the underlying 3751: * map. A lock is obtained on the mutex prior to submap creation. 3752: * The submap retains the thread-safe status of this map. 3753: * 3754: * @param fromKey the inclusive lower range of the submap. 3755: * @param toKey the exclusive upper range of the submap. 3756: * @return a submap from fromKey to the key preceding toKey. 3757: * @throws ClassCastException if fromKey or toKey is not comparable 3758: * to the underlying map's contents. 3759: * @throws IllegalArgumentException if fromKey or toKey is outside the map's 3760: * range. 3761: * @throws NullPointerException if fromKey or toKey is null. but the map does 3762: * not allow null keys. 3763: */ 3764: public SortedMap subMap(Object fromKey, Object toKey) 3765: { 3766: synchronized (mutex) 3767: { 3768: return new SynchronizedSortedMap(mutex, sm.subMap(fromKey, toKey)); 3769: } 3770: } 3771: 3772: /** 3773: * Returns a submap containing all the keys from fromKey onwards. 3774: * The submap supports all operations supported by the underlying 3775: * map and all actions taking place on the submap are also reflected 3776: * in the underlying map. A lock is obtained on the mutex prior to 3777: * submap creation. The submap retains the thread-safe status of 3778: * this map. 3779: * 3780: * @param fromKey the inclusive lower range of the submap. 3781: * @return a submap from fromKey to <code>lastKey()</code>. 3782: * @throws ClassCastException if fromKey is not comparable to the underlying 3783: * map's contents. 3784: * @throws IllegalArgumentException if fromKey is outside the map's range. 3785: * @throws NullPointerException if fromKey is null. but the map does not allow 3786: * null keys. 3787: */ 3788: public SortedMap tailMap(Object fromKey) 3789: { 3790: synchronized (mutex) 3791: { 3792: return new SynchronizedSortedMap(mutex, sm.tailMap(fromKey)); 3793: } 3794: } 3795: } // class SynchronizedSortedMap 3796: 3797: /** 3798: * Returns a synchronized (thread-safe) sorted set wrapper backed by the 3799: * given set. Notice that element access through the iterator and through 3800: * subviews are thread-safe, but if the set can be structurally modified 3801: * (adding or removing elements) then you should synchronize around the 3802: * iteration to avoid non-deterministic behavior:<br> 3803: * <pre> 3804: * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...)); 3805: * ... 3806: * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block 3807: * synchronized (s) // synch on s, not s2 3808: * { 3809: * Iterator i = s2.iterator(); 3810: * while (i.hasNext()) 3811: * foo(i.next()); 3812: * } 3813: * </pre><p> 3814: * 3815: * The returned SortedSet implements Serializable, but can only be 3816: * serialized if the set it wraps is likewise Serializable. 3817: * 3818: * @param s the sorted set to wrap 3819: * @return a synchronized view of the sorted set 3820: * @see Serializable 3821: */ 3822: public static SortedSet synchronizedSortedSet(SortedSet s) 3823: { 3824: return new SynchronizedSortedSet(s); 3825: } 3826: 3827: /** 3828: * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This 3829: * class name is required for compatibility with Sun's JDK serializability. 3830: * 3831: * @author Eric Blake (ebb9@email.byu.edu) 3832: */ 3833: private static final class SynchronizedSortedSet extends SynchronizedSet 3834: implements SortedSet 3835: { 3836: /** 3837: * Compatible with JDK 1.4. 3838: */ 3839: private static final long serialVersionUID = 8695801310862127406L; 3840: 3841: /** 3842: * The wrapped set; stored both here and in the superclass to avoid 3843: * excessive casting. 3844: * @serial the wrapped set 3845: */ 3846: private final SortedSet ss; 3847: 3848: /** 3849: * Wrap a given set. 3850: * @param ss the set to wrap 3851: * @throws NullPointerException if ss is null 3852: */ 3853: SynchronizedSortedSet(SortedSet ss) 3854: { 3855: super(ss); 3856: this.ss = ss; 3857: } 3858: 3859: /** 3860: * Called only by trusted code to specify the mutex as well as the set. 3861: * @param sync the mutex 3862: * @param ss the set 3863: */ 3864: SynchronizedSortedSet(Object sync, SortedSet ss) 3865: { 3866: super(sync, ss); 3867: this.ss = ss; 3868: } 3869: 3870: /** 3871: * Returns the comparator used in sorting the underlying set, or null if 3872: * it is the elements' natural ordering. A lock is obtained on the mutex 3873: * before the comparator is retrieved. 3874: * 3875: * @return the sorting comparator. 3876: */ 3877: public Comparator comparator() 3878: { 3879: synchronized (mutex) 3880: { 3881: return ss.comparator(); 3882: } 3883: } 3884: 3885: /** 3886: * Returns the first, lowest sorted, element from the underlying set. 3887: * A lock is obtained on the mutex before the set is accessed. 3888: * 3889: * @return the first element. 3890: * @throws NoSuchElementException if this set is empty. 3891: */ 3892: public Object first() 3893: { 3894: synchronized (mutex) 3895: { 3896: return ss.first(); 3897: } 3898: } 3899: 3900: /** 3901: * Returns a subset containing the element from the first 3902: * element (as returned by <code>first()</code>) to 3903: * the element before that specified. The subset supports all 3904: * operations supported by the underlying set and all actions 3905: * taking place on the subset are also reflected in the underlying 3906: * set. A lock is obtained on the mutex prior to subset creation. 3907: * This operation is equivalent to <code>subSet(first(), toElement)</code>. 3908: * The subset retains the thread-safe status of this set. 3909: * 3910: * @param toElement the exclusive upper range of the subset. 3911: * @return a subset from <code>first()</code> to the 3912: * the element preceding toElement. 3913: * @throws ClassCastException if toElement is not comparable to the underlying 3914: * set's contents. 3915: * @throws IllegalArgumentException if toElement is outside the set's range. 3916: * @throws NullPointerException if toElement is null. but the set does not allow 3917: * null elements. 3918: */ 3919: public SortedSet headSet(Object toElement) 3920: { 3921: synchronized (mutex) 3922: { 3923: return new SynchronizedSortedSet(mutex, ss.headSet(toElement)); 3924: } 3925: } 3926: 3927: /** 3928: * Returns the last, highest sorted, element from the underlying set. 3929: * A lock is obtained on the mutex before the set is accessed. 3930: * 3931: * @return the last element. 3932: * @throws NoSuchElementException if this set is empty. 3933: */ 3934: public Object last() 3935: { 3936: synchronized (mutex) 3937: { 3938: return ss.last(); 3939: } 3940: } 3941: 3942: /** 3943: * Returns a subset containing the elements from fromElement to 3944: * the element before toElement. The subset supports all 3945: * operations supported by the underlying set and all actions 3946: * taking place on the subset are also reflected in the underlying 3947: * set. A lock is obtained on the mutex prior to subset creation. 3948: * The subset retains the thread-safe status of this set. 3949: * 3950: * @param fromElement the inclusive lower range of the subset. 3951: * @param toElement the exclusive upper range of the subset. 3952: * @return a subset from fromElement to the element preceding toElement. 3953: * @throws ClassCastException if fromElement or toElement is not comparable 3954: * to the underlying set's contents. 3955: * @throws IllegalArgumentException if fromElement or toElement is outside the set's 3956: * range. 3957: * @throws NullPointerException if fromElement or toElement is null. but the set does 3958: * not allow null elements. 3959: */ 3960: public SortedSet subSet(Object fromElement, Object toElement) 3961: { 3962: synchronized (mutex) 3963: { 3964: return new SynchronizedSortedSet(mutex, 3965: ss.subSet(fromElement, toElement)); 3966: } 3967: } 3968: 3969: /** 3970: * Returns a subset containing all the elements from fromElement onwards. 3971: * The subset supports all operations supported by the underlying 3972: * set and all actions taking place on the subset are also reflected 3973: * in the underlying set. A lock is obtained on the mutex prior to 3974: * subset creation. The subset retains the thread-safe status of 3975: * this set. 3976: * 3977: * @param fromElement the inclusive lower range of the subset. 3978: * @return a subset from fromElement to <code>last()</code>. 3979: * @throws ClassCastException if fromElement is not comparable to the underlying 3980: * set's contents. 3981: * @throws IllegalArgumentException if fromElement is outside the set's range. 3982: * @throws NullPointerException if fromElement is null. but the set does not allow 3983: * null elements. 3984: */ 3985: public SortedSet tailSet(Object fromElement) 3986: { 3987: synchronized (mutex) 3988: { 3989: return new SynchronizedSortedSet(mutex, ss.tailSet(fromElement)); 3990: } 3991: } 3992: } // class SynchronizedSortedSet 3993: 3994: 3995: /** 3996: * Returns an unmodifiable view of the given collection. This allows 3997: * "read-only" access, although changes in the backing collection show up 3998: * in this view. Attempts to modify the collection directly or via iterators 3999: * will fail with {@link UnsupportedOperationException}. Although this view 4000: * prevents changes to the structure of the collection and its elements, the values 4001: * referenced by the objects in the collection can still be modified. 4002: * <p> 4003: * 4004: * Since the collection might be a List or a Set, and those have incompatible 4005: * equals and hashCode requirements, this relies on Object's implementation 4006: * rather than passing those calls on to the wrapped collection. The returned 4007: * Collection implements Serializable, but can only be serialized if 4008: * the collection it wraps is likewise Serializable. 4009: * 4010: * @param c the collection to wrap 4011: * @return a read-only view of the collection 4012: * @see Serializable 4013: */ 4014: public static Collection unmodifiableCollection(Collection c) 4015: { 4016: return new UnmodifiableCollection(c); 4017: } 4018: 4019: /** 4020: * The implementation of {@link #unmodifiableCollection(Collection)}. This 4021: * class name is required for compatibility with Sun's JDK serializability. 4022: * 4023: * @author Eric Blake (ebb9@email.byu.edu) 4024: */ 4025: private static class UnmodifiableCollection 4026: implements Collection, Serializable 4027: { 4028: /** 4029: * Compatible with JDK 1.4. 4030: */ 4031: private static final long serialVersionUID = 1820017752578914078L; 4032: 4033: /** 4034: * The wrapped collection. Package visible for use by subclasses. 4035: * @serial the real collection 4036: */ 4037: final Collection c; 4038: 4039: /** 4040: * Wrap a given collection. 4041: * @param c the collection to wrap 4042: * @throws NullPointerException if c is null 4043: */ 4044: UnmodifiableCollection(Collection c) 4045: { 4046: this.c = c; 4047: if (c == null) 4048: throw new NullPointerException(); 4049: } 4050: 4051: /** 4052: * Blocks the addition of elements to the underlying collection. 4053: * This method never returns, throwing an exception instead. 4054: * 4055: * @param o the object to add. 4056: * @return <code>true</code> if the collection was modified as a result of this action. 4057: * @throws UnsupportedOperationException as an unmodifiable collection does not 4058: * support the add operation. 4059: */ 4060: public boolean add(Object o) 4061: { 4062: throw new UnsupportedOperationException(); 4063: } 4064: 4065: /** 4066: * Blocks the addition of a collection of elements to the underlying 4067: * collection. This method never returns, throwing an exception instead. 4068: * 4069: * @param c the collection to add. 4070: * @return <code>true</code> if the collection was modified as a result of this action. 4071: * @throws UnsupportedOperationException as an unmodifiable collection does not 4072: * support the <code>addAll</code> operation. 4073: */ 4074: public boolean addAll(Collection c) 4075: { 4076: throw new UnsupportedOperationException(); 4077: } 4078: 4079: /** 4080: * Blocks the clearing of the underlying collection. This method never 4081: * returns, throwing an exception instead. 4082: * 4083: * @throws UnsupportedOperationException as an unmodifiable collection does 4084: * not support the <code>clear()</code> operation. 4085: */ 4086: public void clear() 4087: { 4088: throw new UnsupportedOperationException(); 4089: } 4090: 4091: /** 4092: * Test whether the underlying collection contains a given object as one of its 4093: * elements. 4094: * 4095: * @param o the element to look for. 4096: * @return <code>true</code> if the underlying collection contains at least 4097: * one element e such that 4098: * <code>o == null ? e == null : o.equals(e)</code>. 4099: * @throws ClassCastException if the type of o is not a valid type for the 4100: * underlying collection. 4101: * @throws NullPointerException if o is null and the underlying collection 4102: * doesn't support null values. 4103: */ 4104: public boolean contains(Object o) 4105: { 4106: return c.contains(o); 4107: } 4108: 4109: /** 4110: * Test whether the underlying collection contains every element in a given 4111: * collection. 4112: * 4113: * @param c1 the collection to test for. 4114: * @return <code>true</code> if for every element o in c, contains(o) would 4115: * return <code>true</code>. 4116: * @throws ClassCastException if the type of any element in c is not a valid 4117: * type for the underlying collection. 4118: * @throws NullPointerException if some element of c is null and the underlying 4119: * collection does not support null values. 4120: * @throws NullPointerException if c itself is null. 4121: */ 4122: public boolean containsAll(Collection c1) 4123: { 4124: return c.containsAll(c1); 4125: } 4126: 4127: /** 4128: * Tests whether the underlying collection is empty, that is, 4129: * if size() == 0. 4130: * 4131: * @return <code>true</code> if this collection contains no elements. 4132: */ 4133: public boolean isEmpty() 4134: { 4135: return c.isEmpty(); 4136: } 4137: 4138: /** 4139: * Obtain an Iterator over the underlying collection, which maintains 4140: * its unmodifiable nature. 4141: * 4142: * @return an UnmodifiableIterator over the elements of the underlying 4143: * collection, in any order. 4144: */ 4145: public Iterator iterator() 4146: { 4147: return new UnmodifiableIterator(c.iterator()); 4148: } 4149: 4150: /** 4151: * Blocks the removal of an object from the underlying collection. 4152: * This method never returns, throwing an exception instead. 4153: * 4154: * @param o The object to remove. 4155: * @return <code>true</code> if the object was removed (i.e. the underlying 4156: * collection returned 1 or more instances of o). 4157: * @throws UnsupportedOperationException as an unmodifiable collection 4158: * does not support the <code>remove()</code> operation. 4159: */ 4160: public boolean remove(Object o) 4161: { 4162: throw new UnsupportedOperationException(); 4163: } 4164: 4165: /** 4166: * Blocks the removal of a collection of objects from the underlying 4167: * collection. This method never returns, throwing an exception 4168: * instead. 4169: * 4170: * @param c The collection of objects to remove. 4171: * @return <code>true</code> if the collection was modified. 4172: * @throws UnsupportedOperationException as an unmodifiable collection 4173: * does not support the <code>removeAll()</code> operation. 4174: */ 4175: public boolean removeAll(Collection c) 4176: { 4177: throw new UnsupportedOperationException(); 4178: } 4179: 4180: /** 4181: * Blocks the removal of all elements from the underlying collection, 4182: * except those in the supplied collection. This method never returns, 4183: * throwing an exception instead. 4184: * 4185: * @param c The collection of objects to retain. 4186: * @return <code>true</code> if the collection was modified. 4187: * @throws UnsupportedOperationException as an unmodifiable collection 4188: * does not support the <code>retainAll()</code> operation. 4189: */ 4190: public boolean retainAll(Collection c) 4191: { 4192: throw new UnsupportedOperationException(); 4193: } 4194: 4195: /** 4196: * Retrieves the number of elements in the underlying collection. 4197: * 4198: * @return the number of elements in the collection. 4199: */ 4200: public int size() 4201: { 4202: return c.size(); 4203: } 4204: 4205: /** 4206: * Copy the current contents of the underlying collection into an array. 4207: * 4208: * @return an array of type Object[] with a length equal to the size of the 4209: * underlying collection and containing the elements currently in 4210: * the underlying collection, in any order. 4211: */ 4212: public Object[] toArray() 4213: { 4214: return c.toArray(); 4215: } 4216: 4217: /** 4218: * Copy the current contents of the underlying collection into an array. If 4219: * the array passed as an argument has length less than the size of the 4220: * underlying collection, an array of the same run-time type as a, with a length 4221: * equal to the size of the underlying collection, is allocated using reflection. 4222: * Otherwise, a itself is used. The elements of the underlying collection are 4223: * copied into it, and if there is space in the array, the following element is 4224: * set to null. The resultant array is returned. 4225: * Note: The fact that the following element is set to null is only useful 4226: * if it is known that this collection does not contain any null elements. 4227: * 4228: * @param a the array to copy this collection into. 4229: * @return an array containing the elements currently in the underlying 4230: * collection, in any order. 4231: * @throws ArrayStoreException if the type of any element of the 4232: * collection is not a subtype of the element type of a. 4233: */ 4234: public Object[] toArray(Object[] a) 4235: { 4236: return c.toArray(a); 4237: } 4238: 4239: /** 4240: * A textual representation of the unmodifiable collection. 4241: * 4242: * @return The unmodifiable collection in the form of a <code>String</code>. 4243: */ 4244: public String toString() 4245: { 4246: return c.toString(); 4247: } 4248: } // class UnmodifiableCollection 4249: 4250: /** 4251: * The implementation of the various iterator methods in the 4252: * unmodifiable classes. 4253: * 4254: * @author Eric Blake (ebb9@email.byu.edu) 4255: */ 4256: private static class UnmodifiableIterator implements Iterator 4257: { 4258: /** 4259: * The wrapped iterator. 4260: */ 4261: private final Iterator i; 4262: 4263: /** 4264: * Only trusted code creates a wrapper. 4265: * @param i the wrapped iterator 4266: */ 4267: UnmodifiableIterator(Iterator i) 4268: { 4269: this.i = i; 4270: } 4271: 4272: /** 4273: * Obtains the next element in the underlying collection. 4274: * 4275: * @return the next element in the collection. 4276: * @throws NoSuchElementException if there are no more elements. 4277: */ 4278: public Object next() 4279: { 4280: return i.next(); 4281: } 4282: /** 4283: * Tests whether there are still elements to be retrieved from the 4284: * underlying collection by <code>next()</code>. When this method 4285: * returns <code>true</code>, an exception will not be thrown on calling 4286: * <code>next()</code>. 4287: * 4288: * @return <code>true</code> if there is at least one more element in the underlying 4289: * collection. 4290: */ 4291: public boolean hasNext() 4292: { 4293: return i.hasNext(); 4294: } 4295: 4296: /** 4297: * Blocks the removal of elements from the underlying collection by the 4298: * iterator. 4299: * 4300: * @throws UnsupportedOperationException as an unmodifiable collection 4301: * does not support the removal of elements by its iterator. 4302: */ 4303: public void remove() 4304: { 4305: throw new UnsupportedOperationException(); 4306: } 4307: } // class UnmodifiableIterator 4308: 4309: /** 4310: * Returns an unmodifiable view of the given list. This allows 4311: * "read-only" access, although changes in the backing list show up 4312: * in this view. Attempts to modify the list directly, via iterators, or 4313: * via sublists, will fail with {@link UnsupportedOperationException}. 4314: * Although this view prevents changes to the structure of the list and 4315: * its elements, the values referenced by the objects in the list can 4316: * still be modified. 4317: * <p> 4318: * 4319: * The returned List implements Serializable, but can only be serialized if 4320: * the list it wraps is likewise Serializable. In addition, if the wrapped 4321: * list implements RandomAccess, this does too. 4322: * 4323: * @param l the list to wrap 4324: * @return a read-only view of the list 4325: * @see Serializable 4326: * @see RandomAccess 4327: */ 4328: public static List unmodifiableList(List l) 4329: { 4330: if (l instanceof RandomAccess) 4331: return new UnmodifiableRandomAccessList(l); 4332: return new UnmodifiableList(l); 4333: } 4334: 4335: /** 4336: * The implementation of {@link #unmodifiableList(List)} for sequential 4337: * lists. This class name is required for compatibility with Sun's JDK 4338: * serializability. 4339: * 4340: * @author Eric Blake (ebb9@email.byu.edu) 4341: */ 4342: private static class UnmodifiableList extends UnmodifiableCollection 4343: implements List 4344: { 4345: /** 4346: * Compatible with JDK 1.4. 4347: */ 4348: private static final long serialVersionUID = -283967356065247728L; 4349: 4350: 4351: /** 4352: * The wrapped list; stored both here and in the superclass to avoid 4353: * excessive casting. Package visible for use by subclass. 4354: * @serial the wrapped list 4355: */ 4356: final List list; 4357: 4358: /** 4359: * Wrap a given list. 4360: * @param l the list to wrap 4361: * @throws NullPointerException if l is null 4362: */ 4363: UnmodifiableList(List l) 4364: { 4365: super(l); 4366: list = l; 4367: } 4368: 4369: /** 4370: * Blocks the addition of an element to the underlying 4371: * list at a specific index. This method never returns, 4372: * throwing an exception instead. 4373: * 4374: * @param index The index at which to place the new element. 4375: * @param o the object to add. 4376: * @throws UnsupportedOperationException as an unmodifiable 4377: * list doesn't support the <code>add()</code> operation. 4378: */ 4379: public void add(int index, Object o) 4380: { 4381: throw new UnsupportedOperationException(); 4382: } 4383: 4384: /** 4385: * Blocks the addition of a collection of elements to the 4386: * underlying list at a specific index. This method never 4387: * returns, throwing an exception instead. 4388: * 4389: * @param index The index at which to place the new element. 4390: * @param c the collections of objects to add. 4391: * @throws UnsupportedOperationException as an unmodifiable 4392: * list doesn't support the <code>addAll()</code> operation. 4393: */ 4394: public boolean addAll(int index, Collection c) 4395: { 4396: throw new UnsupportedOperationException(); 4397: } 4398: 4399: /** 4400: * Returns <code>true</code> if the object, o, is an instance of 4401: * <code>List</code> with the same size and elements 4402: * as the underlying list. 4403: * 4404: * @param o The object to compare. 4405: * @return <code>true</code> if o is equivalent to the underlying list. 4406: */ 4407: public boolean equals(Object o) 4408: { 4409: return list.equals(o); 4410: } 4411: 4412: /** 4413: * Retrieves the element at a given index in the underlying list. 4414: * 4415: * @param index the index of the element to be returned 4416: * @return the element at index index in this list 4417: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 4418: */ 4419: public Object get(int index) 4420: { 4421: return list.get(index); 4422: } 4423: 4424: /** 4425: * Computes the hash code for the underlying list. 4426: * The exact computation is described in the documentation 4427: * of the <code>List</code> interface. 4428: * 4429: * @return The hash code of the underlying list. 4430: * @see List#hashCode() 4431: */ 4432: public int hashCode() 4433: { 4434: return list.hashCode(); 4435: } 4436: 4437: /** 4438: * Obtain the first index at which a given object is to be found in the 4439: * underlying list. 4440: * 4441: * @param o the object to search for 4442: * @return the least integer n such that <code>o == null ? get(n) == null : 4443: * o.equals(get(n))</code>, or -1 if there is no such index. 4444: * @throws ClassCastException if the type of o is not a valid 4445: * type for the underlying list. 4446: * @throws NullPointerException if o is null and the underlying 4447: * list does not support null values. 4448: */ 4449: public int indexOf(Object o) 4450: { 4451: return list.indexOf(o); 4452: } 4453: 4454: /** 4455: * Obtain the last index at which a given object is to be found in the 4456: * underlying list. 4457: * 4458: * @return the greatest integer n such that <code>o == null ? get(n) == null 4459: * : o.equals(get(n))</code>, or -1 if there is no such index. 4460: * @throws ClassCastException if the type of o is not a valid 4461: * type for the underlying list. 4462: * @throws NullPointerException if o is null and the underlying 4463: * list does not support null values. 4464: */ 4465: public int lastIndexOf(Object o) 4466: { 4467: return list.lastIndexOf(o); 4468: } 4469: 4470: /** 4471: * Obtains a list iterator over the underlying list, starting at the beginning 4472: * and maintaining the unmodifiable nature of this list. 4473: * 4474: * @return a <code>UnmodifiableListIterator</code> over the elements of the 4475: * underlying list, in order, starting at the beginning. 4476: */ 4477: public ListIterator listIterator() 4478: { 4479: return new UnmodifiableListIterator(list.listIterator()); 4480: } 4481: 4482: /** 4483: * Obtains a list iterator over the underlying list, starting at the specified 4484: * index and maintaining the unmodifiable nature of this list. An initial call 4485: * to <code>next()</code> will retrieve the element at the specified index, 4486: * and an initial call to <code>previous()</code> will retrieve the element 4487: * at index - 1. 4488: * 4489: * 4490: * @param index the position, between 0 and size() inclusive, to begin the 4491: * iteration from. 4492: * @return a <code>UnmodifiableListIterator</code> over the elements of the 4493: * underlying list, in order, starting at the specified index. 4494: * @throws IndexOutOfBoundsException if index < 0 || index > size() 4495: */ 4496: public ListIterator listIterator(int index) 4497: { 4498: return new UnmodifiableListIterator(list.listIterator(index)); 4499: } 4500: 4501: /** 4502: * Blocks the removal of the element at the specified index. 4503: * This method never returns, throwing an exception instead. 4504: * 4505: * @param index The index of the element to remove. 4506: * @return the removed element. 4507: * @throws UnsupportedOperationException as an unmodifiable 4508: * list does not support the <code>remove()</code> 4509: * operation. 4510: */ 4511: public Object remove(int index) 4512: { 4513: throw new UnsupportedOperationException(); 4514: } 4515: 4516: /** 4517: * Blocks the replacement of the element at the specified index. 4518: * This method never returns, throwing an exception instead. 4519: * 4520: * @param index The index of the element to replace. 4521: * @param o The new object to place at the specified index. 4522: * @return the replaced element. 4523: * @throws UnsupportedOperationException as an unmodifiable 4524: * list does not support the <code>set()</code> 4525: * operation. 4526: */ 4527: public Object set(int index, Object o) 4528: { 4529: throw new UnsupportedOperationException(); 4530: } 4531: 4532: /** 4533: * Obtain a List view of a subsection of the underlying list, from 4534: * fromIndex (inclusive) to toIndex (exclusive). If the two indices 4535: * are equal, the sublist is empty. The returned list will be 4536: * unmodifiable, like this list. Changes to the elements of the 4537: * returned list will be reflected in the underlying list. No structural 4538: * modifications can take place in either list. 4539: * 4540: * @param fromIndex the index that the returned list should start from 4541: * (inclusive). 4542: * @param toIndex the index that the returned list should go to (exclusive). 4543: * @return a List backed by a subsection of the underlying list. 4544: * @throws IndexOutOfBoundsException if fromIndex < 0 4545: * || toIndex > size() || fromIndex > toIndex. 4546: */ 4547: public List subList(int fromIndex, int toIndex) 4548: { 4549: return unmodifiableList(list.subList(fromIndex, toIndex)); 4550: } 4551: } // class UnmodifiableList 4552: 4553: /** 4554: * The implementation of {@link #unmodifiableList(List)} for random-access 4555: * lists. This class name is required for compatibility with Sun's JDK 4556: * serializability. 4557: * 4558: * @author Eric Blake (ebb9@email.byu.edu) 4559: */ 4560: private static final class UnmodifiableRandomAccessList 4561: extends UnmodifiableList implements RandomAccess 4562: { 4563: /** 4564: * Compatible with JDK 1.4. 4565: */ 4566: private static final long serialVersionUID = -2542308836966382001L; 4567: 4568: /** 4569: * Wrap a given list. 4570: * @param l the list to wrap 4571: * @throws NullPointerException if l is null 4572: */ 4573: UnmodifiableRandomAccessList(List l) 4574: { 4575: super(l); 4576: } 4577: } // class UnmodifiableRandomAccessList 4578: 4579: /** 4580: * The implementation of {@link UnmodifiableList#listIterator()}. 4581: * 4582: * @author Eric Blake (ebb9@email.byu.edu) 4583: */ 4584: private static final class UnmodifiableListIterator 4585: extends UnmodifiableIterator implements ListIterator 4586: { 4587: /** 4588: * The wrapped iterator, stored both here and in the superclass to 4589: * avoid excessive casting. 4590: */ 4591: private final ListIterator li; 4592: 4593: /** 4594: * Only trusted code creates a wrapper. 4595: * @param li the wrapped iterator 4596: */ 4597: UnmodifiableListIterator(ListIterator li) 4598: { 4599: super(li); 4600: this.li = li; 4601: } 4602: 4603: /** 4604: * Blocks the addition of an object to the list underlying this iterator. 4605: * This method never returns, throwing an exception instead. 4606: * 4607: * @param o The object to add. 4608: * @throws UnsupportedOperationException as the iterator of an unmodifiable 4609: * list does not support the <code>add()</code> operation. 4610: */ 4611: public void add(Object o) 4612: { 4613: throw new UnsupportedOperationException(); 4614: } 4615: 4616: /** 4617: * Tests whether there are still elements to be retrieved from the 4618: * underlying collection by <code>previous()</code>. When this method 4619: * returns <code>true</code>, an exception will not be thrown on calling 4620: * <code>previous()</code>. 4621: * 4622: * @return <code>true</code> if there is at least one more element prior to the 4623: * current position in the underlying list. 4624: */ 4625: public boolean hasPrevious() 4626: { 4627: return li.hasPrevious(); 4628: } 4629: 4630: /** 4631: * Find the index of the element that would be returned by a call to next. 4632: * If <code>hasNext()</code> returns <code>false</code>, this returns the list size. 4633: * 4634: * @return the index of the element that would be returned by 4635: * <code>next()</code>. 4636: */ 4637: public int nextIndex() 4638: { 4639: return li.nextIndex(); 4640: } 4641: 4642: /** 4643: * Obtains the previous element in the underlying list. 4644: * 4645: * @return the previous element in the list. 4646: * @throws NoSuchElementException if there are no more prior elements. 4647: */ 4648: public Object previous() 4649: { 4650: return li.previous(); 4651: } 4652: 4653: /** 4654: * Find the index of the element that would be returned by a call to 4655: * previous. If <code>hasPrevious()</code> returns <code>false</code>, 4656: * this returns -1. 4657: * 4658: * @return the index of the element that would be returned by 4659: * <code>previous()</code>. 4660: */ 4661: public int previousIndex() 4662: { 4663: return li.previousIndex(); 4664: } 4665: 4666: /** 4667: * Blocks the replacement of an element in the list underlying this 4668: * iterator. This method never returns, throwing an exception instead. 4669: * 4670: * @param o The new object to replace the existing one. 4671: * @throws UnsupportedOperationException as the iterator of an unmodifiable 4672: * list does not support the <code>set()</code> operation. 4673: */ 4674: public void set(Object o) 4675: { 4676: throw new UnsupportedOperationException(); 4677: } 4678: } // class UnmodifiableListIterator 4679: 4680: /** 4681: * Returns an unmodifiable view of the given map. This allows "read-only" 4682: * access, although changes in the backing map show up in this view. 4683: * Attempts to modify the map directly, or via collection views or their 4684: * iterators will fail with {@link UnsupportedOperationException}. 4685: * Although this view prevents changes to the structure of the map and its 4686: * entries, the values referenced by the objects in the map can still be 4687: * modified. 4688: * <p> 4689: * 4690: * The returned Map implements Serializable, but can only be serialized if 4691: * the map it wraps is likewise Serializable. 4692: * 4693: * @param m the map to wrap 4694: * @return a read-only view of the map 4695: * @see Serializable 4696: */ 4697: public static Map unmodifiableMap(Map m) 4698: { 4699: return new UnmodifiableMap(m); 4700: } 4701: 4702: /** 4703: * The implementation of {@link #unmodifiableMap(Map)}. This 4704: * class name is required for compatibility with Sun's JDK serializability. 4705: * 4706: * @author Eric Blake (ebb9@email.byu.edu) 4707: */ 4708: private static class UnmodifiableMap implements Map, Serializable 4709: { 4710: /** 4711: * Compatible with JDK 1.4. 4712: */ 4713: private static final long serialVersionUID = -1034234728574286014L; 4714: 4715: /** 4716: * The wrapped map. 4717: * @serial the real map 4718: */ 4719: private final Map m; 4720: 4721: /** 4722: * Cache the entry set. 4723: */ 4724: private transient Set entries; 4725: 4726: /** 4727: * Cache the key set. 4728: */ 4729: private transient Set keys; 4730: 4731: /** 4732: * Cache the value collection. 4733: */ 4734: private transient Collection values; 4735: 4736: /** 4737: * Wrap a given map. 4738: * @param m the map to wrap 4739: * @throws NullPointerException if m is null 4740: */ 4741: UnmodifiableMap(Map m) 4742: { 4743: this.m = m; 4744: if (m == null) 4745: throw new NullPointerException(); 4746: } 4747: 4748: /** 4749: * Blocks the clearing of entries from the underlying map. 4750: * This method never returns, throwing an exception instead. 4751: * 4752: * @throws UnsupportedOperationException as an unmodifiable 4753: * map does not support the <code>clear()</code> operation. 4754: */ 4755: public void clear() 4756: { 4757: throw new UnsupportedOperationException(); 4758: } 4759: 4760: /** 4761: * Returns <code>true</code> if the underlying map contains a mapping for 4762: * the given key. 4763: * 4764: * @param key the key to search for 4765: * @return <code>true</code> if the map contains the key 4766: * @throws ClassCastException if the key is of an inappropriate type 4767: * @throws NullPointerException if key is <code>null</code> but the map 4768: * does not permit null keys 4769: */ 4770: public boolean containsKey(Object key) 4771: { 4772: return m.containsKey(key); 4773: } 4774: 4775: /** 4776: * Returns <code>true</code> if the underlying map contains at least one mapping with 4777: * the given value. In other words, it returns <code>true</code> if a value v exists where 4778: * <code>(value == null ? v == null : value.equals(v))</code>. This usually 4779: * requires linear time. 4780: * 4781: * @param value the value to search for 4782: * @return <code>true</code> if the map contains the value 4783: * @throws ClassCastException if the type of the value is not a valid type 4784: * for this map. 4785: * @throws NullPointerException if the value is null and the map doesn't 4786: * support null values. 4787: */ 4788: public boolean containsValue(Object value) 4789: { 4790: return m.containsValue(value); 4791: } 4792: 4793: /** 4794: * Returns a unmodifiable set view of the entries in the underlying map. 4795: * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>. 4796: * The set is backed by the map, so that changes in one show up in the other. 4797: * Modifications made while an iterator is in progress cause undefined 4798: * behavior. These modifications are again limited to the values of 4799: * the objects. 4800: * 4801: * @return the unmodifiable set view of all mapping entries. 4802: * @see Map.Entry 4803: */ 4804: public Set entrySet() 4805: { 4806: if (entries == null) 4807: entries = new UnmodifiableEntrySet(m.entrySet()); 4808: return entries; 4809: } 4810: 4811: /** 4812: * The implementation of {@link UnmodifiableMap#entrySet()}. This class 4813: * name is required for compatibility with Sun's JDK serializability. 4814: * 4815: * @author Eric Blake (ebb9@email.byu.edu) 4816: */ 4817: private static final class UnmodifiableEntrySet extends UnmodifiableSet 4818: implements Serializable 4819: { 4820: // Unmodifiable implementation of Map.Entry used as return value for 4821: // UnmodifiableEntrySet accessors (iterator, toArray, toArray(Object[])) 4822: private static final class UnmodifiableMapEntry 4823: implements Map.Entry 4824: { 4825: private final Map.Entry e; 4826: 4827: private UnmodifiableMapEntry(Map.Entry e) 4828: { 4829: super(); 4830: this.e = e; 4831: } 4832: 4833: /** 4834: * Returns <code>true</code> if the object, o, is also a map entry 4835: * with an identical key and value. 4836: * 4837: * @param o the object to compare. 4838: * @return <code>true</code> if o is an equivalent map entry. 4839: */ 4840: public boolean equals(Object o) 4841: { 4842: return e.equals(o); 4843: } 4844: 4845: /** 4846: * Returns the key of this map entry. 4847: * 4848: * @return the key. 4849: */ 4850: public Object getKey() 4851: { 4852: return e.getKey(); 4853: } 4854: 4855: /** 4856: * Returns the value of this map entry. 4857: * 4858: * @return the value. 4859: */ 4860: public Object getValue() 4861: { 4862: return e.getValue(); 4863: } 4864: 4865: /** 4866: * Computes the hash code of this map entry. The computation is 4867: * described in the <code>Map</code> interface documentation. 4868: * 4869: * @return the hash code of this entry. 4870: * @see Map#hashCode() 4871: */ 4872: public int hashCode() 4873: { 4874: return e.hashCode(); 4875: } 4876: 4877: /** 4878: * Blocks the alteration of the value of this map entry. This method 4879: * never returns, throwing an exception instead. 4880: * 4881: * @param value The new value. 4882: * @throws UnsupportedOperationException as an unmodifiable map entry 4883: * does not support the <code>setValue()</code> operation. 4884: */ 4885: public Object setValue(Object value) 4886: { 4887: throw new UnsupportedOperationException(); 4888: } 4889: 4890: /** 4891: * Returns a textual representation of the map entry. 4892: * 4893: * @return The map entry as a <code>String</code>. 4894: */ 4895: public String toString() 4896: { 4897: return e.toString(); 4898: } 4899: } 4900: 4901: /** 4902: * Compatible with JDK 1.4. 4903: */ 4904: private static final long serialVersionUID = 7854390611657943733L; 4905: 4906: /** 4907: * Wrap a given set. 4908: * @param s the set to wrap 4909: */ 4910: UnmodifiableEntrySet(Set s) 4911: { 4912: super(s); 4913: } 4914: 4915: // The iterator must return unmodifiable map entries. 4916: public Iterator iterator() 4917: { 4918: return new UnmodifiableIterator(c.iterator()) 4919: { 4920: /** 4921: * Obtains the next element from the underlying set of 4922: * map entries. 4923: * 4924: * @return the next element in the collection. 4925: * @throws NoSuchElementException if there are no more elements. 4926: */ 4927: public Object next() 4928: { 4929: final Map.Entry e = (Map.Entry) super.next(); 4930: return new UnmodifiableMapEntry(e); 4931: } 4932: }; 4933: } 4934: 4935: // The array returned is an array of UnmodifiableMapEntry instead of 4936: // Map.Entry 4937: public Object[] toArray() 4938: { 4939: Object[] mapEntryResult = super.toArray(); 4940: UnmodifiableMapEntry result[] = null; 4941: 4942: if (mapEntryResult != null) 4943: { 4944: result = new UnmodifiableMapEntry[mapEntryResult.length]; 4945: for (int i = 0; i < mapEntryResult.length; i++) 4946: { 4947: Map.Entry r = (Map.Entry) mapEntryResult[i]; 4948: result[i] = new UnmodifiableMapEntry(r); 4949: } 4950: } 4951: return result; 4952: } 4953: 4954: // The array returned is an array of UnmodifiableMapEntry instead of 4955: // Map.Entry 4956: public Object[] toArray(Object[] array) 4957: { 4958: super.toArray(array); 4959: 4960: if (array != null) 4961: { 4962: for (int i = 0; i < array.length; i++) 4963: { 4964: array[i] = new UnmodifiableMapEntry((Map.Entry) array[i]); 4965: } 4966: } 4967: return array; 4968: } 4969: 4970: } // class UnmodifiableEntrySet 4971: 4972: /** 4973: * Returns <code>true</code> if the object, o, is also an instance 4974: * of <code>Map</code> with an equal set of map entries. 4975: * 4976: * @param o The object to compare. 4977: * @return <code>true</code> if o is an equivalent map. 4978: */ 4979: public boolean equals(Object o) 4980: { 4981: return m.equals(o); 4982: } 4983: 4984: /** 4985: * Returns the value associated with the supplied key or 4986: * null if no such mapping exists. An ambiguity can occur 4987: * if null values are accepted by the underlying map. 4988: * In this case, <code>containsKey()</code> can be used 4989: * to separate the two possible cases of a null result. 4990: * 4991: * @param key The key to look up. 4992: * @return the value associated with the key, or null if key not in map. 4993: * @throws ClassCastException if the key is an inappropriate type. 4994: * @throws NullPointerException if this map does not accept null keys. 4995: * @see #containsKey(Object) 4996: */ 4997: public Object get(Object key) 4998: { 4999: return m.get(key); 5000: } 5001: 5002: /** 5003: * Blocks the addition of a new entry to the underlying map. 5004: * This method never returns, throwing an exception instead. 5005: * 5006: * @param key The new key. 5007: * @param value The new value. 5008: * @return the previous value of the key, or null if there was no mapping. 5009: * @throws UnsupportedOperationException as an unmodifiable 5010: * map does not support the <code>put()</code> operation. 5011: */ 5012: public Object put(Object key, Object value) 5013: { 5014: throw new UnsupportedOperationException(); 5015: } 5016: 5017: /** 5018: * Computes the hash code for the underlying map, as the sum 5019: * of the hash codes of all entries. 5020: * 5021: * @return The hash code of the underlying map. 5022: * @see Map.Entry#hashCode() 5023: */ 5024: public int hashCode() 5025: { 5026: return m.hashCode(); 5027: } 5028: 5029: /** 5030: * Returns <code>true</code> if the underlying map contains no entries. 5031: * 5032: * @return <code>true</code> if the map is empty. 5033: */ 5034: public boolean isEmpty() 5035: { 5036: return m.isEmpty(); 5037: } 5038: 5039: /** 5040: * Returns a unmodifiable set view of the keys in the underlying map. 5041: * The set is backed by the map, so that changes in one show up in the other. 5042: * Modifications made while an iterator is in progress cause undefined 5043: * behavior. These modifications are again limited to the values of 5044: * the keys. 5045: * 5046: * @return the set view of all keys. 5047: */ 5048: public Set keySet() 5049: { 5050: if (keys == null) 5051: keys = new UnmodifiableSet(m.keySet()); 5052: return keys; 5053: } 5054: 5055: /** 5056: * Blocks the addition of the entries in the supplied map. 5057: * This method never returns, throwing an exception instead. 5058: * 5059: * @param m The map, the entries of which should be added 5060: * to the underlying map. 5061: * @throws UnsupportedOperationException as an unmodifiable 5062: * map does not support the <code>putAll</code> operation. 5063: */ 5064: public void putAll(Map m) 5065: { 5066: throw new UnsupportedOperationException(); 5067: } 5068: 5069: /** 5070: * Blocks the removal of an entry from the map. 5071: * This method never returns, throwing an exception instead. 5072: * 5073: * @param o The key of the entry to remove. 5074: * @return The value the key was associated with, or null 5075: * if no such mapping existed. Null is also returned 5076: * if the removed entry had a null key. 5077: * @throws UnsupportedOperationException as an unmodifiable 5078: * map does not support the <code>remove</code> operation. 5079: */ 5080: public Object remove(Object o) 5081: { 5082: throw new UnsupportedOperationException(); 5083: } 5084: 5085: 5086: /** 5087: * Returns the number of key-value mappings in the underlying map. 5088: * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE 5089: * is returned. 5090: * 5091: * @return the number of mappings. 5092: */ 5093: public int size() 5094: { 5095: return m.size(); 5096: } 5097: 5098: /** 5099: * Returns a textual representation of the map. 5100: * 5101: * @return The map in the form of a <code>String</code>. 5102: */ 5103: public String toString() 5104: { 5105: return m.toString(); 5106: } 5107: 5108: /** 5109: * Returns a unmodifiable collection view of the values in the underlying map. 5110: * The collection is backed by the map, so that changes in one show up in the other. 5111: * Modifications made while an iterator is in progress cause undefined 5112: * behavior. These modifications are again limited to the values of 5113: * the keys. 5114: * 5115: * @return the collection view of all values. 5116: */ 5117: public Collection values() 5118: { 5119: if (values == null) 5120: values = new UnmodifiableCollection(m.values()); 5121: return values; 5122: } 5123: } // class UnmodifiableMap 5124: 5125: /** 5126: * Returns an unmodifiable view of the given set. This allows 5127: * "read-only" access, although changes in the backing set show up 5128: * in this view. Attempts to modify the set directly or via iterators 5129: * will fail with {@link UnsupportedOperationException}. 5130: * Although this view prevents changes to the structure of the set and its 5131: * entries, the values referenced by the objects in the set can still be 5132: * modified. 5133: * <p> 5134: * 5135: * The returned Set implements Serializable, but can only be serialized if 5136: * the set it wraps is likewise Serializable. 5137: * 5138: * @param s the set to wrap 5139: * @return a read-only view of the set 5140: * @see Serializable 5141: */ 5142: public static Set unmodifiableSet(Set s) 5143: { 5144: return new UnmodifiableSet(s); 5145: } 5146: 5147: /** 5148: * The implementation of {@link #unmodifiableSet(Set)}. This class 5149: * name is required for compatibility with Sun's JDK serializability. 5150: * 5151: * @author Eric Blake (ebb9@email.byu.edu) 5152: */ 5153: private static class UnmodifiableSet extends UnmodifiableCollection 5154: implements Set 5155: { 5156: /** 5157: * Compatible with JDK 1.4. 5158: */ 5159: private static final long serialVersionUID = -9215047833775013803L; 5160: 5161: /** 5162: * Wrap a given set. 5163: * @param s the set to wrap 5164: * @throws NullPointerException if s is null 5165: */ 5166: UnmodifiableSet(Set s) 5167: { 5168: super(s); 5169: } 5170: 5171: /** 5172: * Returns <code>true</code> if the object, o, is also an instance of 5173: * <code>Set</code> of the same size and with the same entries. 5174: * 5175: * @return <code>true</code> if o is an equivalent set. 5176: */ 5177: public boolean equals(Object o) 5178: { 5179: return c.equals(o); 5180: } 5181: 5182: /** 5183: * Computes the hash code of this set, as the sum of the 5184: * hash codes of all elements within the set. 5185: * 5186: * @return the hash code of the set. 5187: */ 5188: public int hashCode() 5189: { 5190: return c.hashCode(); 5191: } 5192: } // class UnmodifiableSet 5193: 5194: /** 5195: * Returns an unmodifiable view of the given sorted map. This allows 5196: * "read-only" access, although changes in the backing map show up in this 5197: * view. Attempts to modify the map directly, via subviews, via collection 5198: * views, or iterators, will fail with {@link UnsupportedOperationException}. 5199: * Although this view prevents changes to the structure of the map and its 5200: * entries, the values referenced by the objects in the map can still be 5201: * modified. 5202: * <p> 5203: * 5204: * The returned SortedMap implements Serializable, but can only be 5205: * serialized if the map it wraps is likewise Serializable. 5206: * 5207: * @param m the map to wrap 5208: * @return a read-only view of the map 5209: * @see Serializable 5210: */ 5211: public static SortedMap unmodifiableSortedMap(SortedMap m) 5212: { 5213: return new UnmodifiableSortedMap(m); 5214: } 5215: 5216: /** 5217: * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This 5218: * class name is required for compatibility with Sun's JDK serializability. 5219: * 5220: * @author Eric Blake (ebb9@email.byu.edu) 5221: */ 5222: private static class UnmodifiableSortedMap extends UnmodifiableMap 5223: implements SortedMap 5224: { 5225: /** 5226: * Compatible with JDK 1.4. 5227: */ 5228: private static final long serialVersionUID = -8806743815996713206L; 5229: 5230: /** 5231: * The wrapped map; stored both here and in the superclass to avoid 5232: * excessive casting. 5233: * @serial the wrapped map 5234: */ 5235: private final SortedMap sm; 5236: 5237: /** 5238: * Wrap a given map. 5239: * @param sm the map to wrap 5240: * @throws NullPointerException if sm is null 5241: */ 5242: UnmodifiableSortedMap(SortedMap sm) 5243: { 5244: super(sm); 5245: this.sm = sm; 5246: } 5247: 5248: /** 5249: * Returns the comparator used in sorting the underlying map, 5250: * or null if it is the keys' natural ordering. 5251: * 5252: * @return the sorting comparator. 5253: */ 5254: public Comparator comparator() 5255: { 5256: return sm.comparator(); 5257: } 5258: 5259: /** 5260: * Returns the first (lowest sorted) key in the map. 5261: * 5262: * @return the first key. 5263: * @throws NoSuchElementException if this map is empty. 5264: */ 5265: public Object firstKey() 5266: { 5267: return sm.firstKey(); 5268: } 5269: 5270: /** 5271: * Returns a unmodifiable view of the portion of the map strictly less 5272: * than toKey. The view is backed by the underlying map, so changes in 5273: * one show up in the other. The submap supports all optional operations 5274: * of the original. This operation is equivalent to 5275: * <code>subMap(firstKey(), toKey)</code>. 5276: * <p> 5277: * 5278: * The returned map throws an IllegalArgumentException any time a key is 5279: * used which is out of the range of toKey. Note that the endpoint, toKey, 5280: * is not included; if you want this value to be included, pass its successor 5281: * object in to toKey. For example, for Integers, you could request 5282: * <code>headMap(new Integer(limit.intValue() + 1))</code>. 5283: * 5284: * @param toKey the exclusive upper range of the submap. 5285: * @return the submap. 5286: * @throws ClassCastException if toKey is not comparable to the map contents. 5287: * @throws IllegalArgumentException if this is a subMap, and toKey is out 5288: * of range. 5289: * @throws NullPointerException if toKey is null but the map does not allow 5290: * null keys. 5291: */ 5292: public SortedMap headMap(Object toKey) 5293: { 5294: return new UnmodifiableSortedMap(sm.headMap(toKey)); 5295: } 5296: 5297: /** 5298: * Returns the last (highest sorted) key in the map. 5299: * 5300: * @return the last key. 5301: * @throws NoSuchElementException if this map is empty. 5302: */ 5303: public Object lastKey() 5304: { 5305: return sm.lastKey(); 5306: } 5307: 5308: /** 5309: * Returns a unmodifiable view of the portion of the map greater than or 5310: * equal to fromKey, and strictly less than toKey. The view is backed by 5311: * the underlying map, so changes in one show up in the other. The submap 5312: * supports all optional operations of the original. 5313: * <p> 5314: * 5315: * The returned map throws an IllegalArgumentException any time a key is 5316: * used which is out of the range of fromKey and toKey. Note that the 5317: * lower endpoint is included, but the upper is not; if you want to 5318: * change the inclusion or exclusion of an endpoint, pass its successor 5319: * object in instead. For example, for Integers, you could request 5320: * <code>subMap(new Integer(lowlimit.intValue() + 1), 5321: * new Integer(highlimit.intValue() + 1))</code> to reverse 5322: * the inclusiveness of both endpoints. 5323: * 5324: * @param fromKey the inclusive lower range of the submap. 5325: * @param toKey the exclusive upper range of the submap. 5326: * @return the submap. 5327: * @throws ClassCastException if fromKey or toKey is not comparable to 5328: * the map contents. 5329: * @throws IllegalArgumentException if this is a subMap, and fromKey or 5330: * toKey is out of range. 5331: * @throws NullPointerException if fromKey or toKey is null but the map 5332: * does not allow null keys. 5333: */ 5334: public SortedMap subMap(Object fromKey, Object toKey) 5335: { 5336: return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey)); 5337: } 5338: 5339: /** 5340: * Returns a unmodifiable view of the portion of the map greater than or 5341: * equal to fromKey. The view is backed by the underlying map, so changes 5342: * in one show up in the other. The submap supports all optional operations 5343: * of the original. 5344: * <p> 5345: * 5346: * The returned map throws an IllegalArgumentException any time a key is 5347: * used which is out of the range of fromKey. Note that the endpoint, fromKey, is 5348: * included; if you do not want this value to be included, pass its successor object in 5349: * to fromKey. For example, for Integers, you could request 5350: * <code>tailMap(new Integer(limit.intValue() + 1))</code>. 5351: * 5352: * @param fromKey the inclusive lower range of the submap 5353: * @return the submap 5354: * @throws ClassCastException if fromKey is not comparable to the map 5355: * contents 5356: * @throws IllegalArgumentException if this is a subMap, and fromKey is out 5357: * of range 5358: * @throws NullPointerException if fromKey is null but the map does not allow 5359: * null keys 5360: */ 5361: public SortedMap tailMap(Object fromKey) 5362: { 5363: return new UnmodifiableSortedMap(sm.tailMap(fromKey)); 5364: } 5365: } // class UnmodifiableSortedMap 5366: 5367: /** 5368: * Returns an unmodifiable view of the given sorted set. This allows 5369: * "read-only" access, although changes in the backing set show up 5370: * in this view. Attempts to modify the set directly, via subsets, or via 5371: * iterators, will fail with {@link UnsupportedOperationException}. 5372: * Although this view prevents changes to the structure of the set and its 5373: * entries, the values referenced by the objects in the set can still be 5374: * modified. 5375: * <p> 5376: * 5377: * The returns SortedSet implements Serializable, but can only be 5378: * serialized if the set it wraps is likewise Serializable. 5379: * 5380: * @param s the set to wrap 5381: * @return a read-only view of the set 5382: * @see Serializable 5383: */ 5384: public static SortedSet unmodifiableSortedSet(SortedSet s) 5385: { 5386: return new UnmodifiableSortedSet(s); 5387: } 5388: 5389: /** 5390: * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This 5391: * class name is required for compatibility with Sun's JDK serializability. 5392: * 5393: * @author Eric Blake (ebb9@email.byu.edu) 5394: */ 5395: private static class UnmodifiableSortedSet extends UnmodifiableSet 5396: implements SortedSet 5397: { 5398: /** 5399: * Compatible with JDK 1.4. 5400: */ 5401: private static final long serialVersionUID = -4929149591599911165L; 5402: 5403: /** 5404: * The wrapped set; stored both here and in the superclass to avoid 5405: * excessive casting. 5406: * @serial the wrapped set 5407: */ 5408: private SortedSet ss; 5409: 5410: /** 5411: * Wrap a given set. 5412: * @param ss the set to wrap 5413: * @throws NullPointerException if ss is null 5414: */ 5415: UnmodifiableSortedSet(SortedSet ss) 5416: { 5417: super(ss); 5418: this.ss = ss; 5419: } 5420: 5421: /** 5422: * Returns the comparator used in sorting the underlying set, 5423: * or null if it is the elements' natural ordering. 5424: * 5425: * @return the sorting comparator 5426: */ 5427: public Comparator comparator() 5428: { 5429: return ss.comparator(); 5430: } 5431: 5432: /** 5433: * Returns the first (lowest sorted) element in the underlying 5434: * set. 5435: * 5436: * @return the first element. 5437: * @throws NoSuchElementException if the set is empty. 5438: */ 5439: public Object first() 5440: { 5441: return ss.first(); 5442: } 5443: 5444: /** 5445: * Returns a unmodifiable view of the portion of the set strictly 5446: * less than toElement. The view is backed by the underlying set, 5447: * so changes in one show up in the other. The subset supports 5448: * all optional operations of the original. This operation 5449: * is equivalent to <code>subSet(first(), toElement)</code>. 5450: * <p> 5451: * 5452: * The returned set throws an IllegalArgumentException any time an element is 5453: * used which is out of the range of toElement. Note that the endpoint, toElement, 5454: * is not included; if you want this value included, pass its successor object in to 5455: * toElement. For example, for Integers, you could request 5456: * <code>headSet(new Integer(limit.intValue() + 1))</code>. 5457: * 5458: * @param toElement the exclusive upper range of the subset 5459: * @return the subset. 5460: * @throws ClassCastException if toElement is not comparable to the set 5461: * contents. 5462: * @throws IllegalArgumentException if this is a subSet, and toElement is out 5463: * of range. 5464: * @throws NullPointerException if toElement is null but the set does not 5465: * allow null elements. 5466: */ 5467: public SortedSet headSet(Object toElement) 5468: { 5469: return new UnmodifiableSortedSet(ss.headSet(toElement)); 5470: } 5471: 5472: /** 5473: * Returns the last (highest sorted) element in the underlying 5474: * set. 5475: * 5476: * @return the last element. 5477: * @throws NoSuchElementException if the set is empty. 5478: */ 5479: public Object last() 5480: { 5481: return ss.last(); 5482: } 5483: 5484: /** 5485: * Returns a unmodifiable view of the portion of the set greater than or 5486: * equal to fromElement, and strictly less than toElement. The view is backed by 5487: * the underlying set, so changes in one show up in the other. The subset 5488: * supports all optional operations of the original. 5489: * <p> 5490: * 5491: * The returned set throws an IllegalArgumentException any time an element is 5492: * used which is out of the range of fromElement and toElement. Note that the 5493: * lower endpoint is included, but the upper is not; if you want to 5494: * change the inclusion or exclusion of an endpoint, pass its successor 5495: * object in instead. For example, for Integers, you can request 5496: * <code>subSet(new Integer(lowlimit.intValue() + 1), 5497: * new Integer(highlimit.intValue() + 1))</code> to reverse 5498: * the inclusiveness of both endpoints. 5499: * 5500: * @param fromElement the inclusive lower range of the subset. 5501: * @param toElement the exclusive upper range of the subset. 5502: * @return the subset. 5503: * @throws ClassCastException if fromElement or toElement is not comparable 5504: * to the set contents. 5505: * @throws IllegalArgumentException if this is a subSet, and fromElement or 5506: * toElement is out of range. 5507: * @throws NullPointerException if fromElement or toElement is null but the 5508: * set does not allow null elements. 5509: */ 5510: public SortedSet subSet(Object fromElement, Object toElement) 5511: { 5512: return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement)); 5513: } 5514: 5515: /** 5516: * Returns a unmodifiable view of the portion of the set greater than or equal to 5517: * fromElement. The view is backed by the underlying set, so changes in one show up 5518: * in the other. The subset supports all optional operations of the original. 5519: * <p> 5520: * 5521: * The returned set throws an IllegalArgumentException any time an element is 5522: * used which is out of the range of fromElement. Note that the endpoint, 5523: * fromElement, is included; if you do not want this value to be included, pass its 5524: * successor object in to fromElement. For example, for Integers, you could request 5525: * <code>tailSet(new Integer(limit.intValue() + 1))</code>. 5526: * 5527: * @param fromElement the inclusive lower range of the subset 5528: * @return the subset. 5529: * @throws ClassCastException if fromElement is not comparable to the set 5530: * contents. 5531: * @throws IllegalArgumentException if this is a subSet, and fromElement is 5532: * out of range. 5533: * @throws NullPointerException if fromElement is null but the set does not 5534: * allow null elements. 5535: */ 5536: public SortedSet tailSet(Object fromElement) 5537: { 5538: return new UnmodifiableSortedSet(ss.tailSet(fromElement)); 5539: } 5540: } // class UnmodifiableSortedSet 5541: } // class Collections