GNU Classpath (0.17) | ||
Frames | No Frames |
1: /* Collections.java -- Utility class with methods to operate on collections 2: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 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(key, o, 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(key, l.get(pos), 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)}. This class name 1735: * 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 an element to the end of the underlying list (optional operation). 2522: * If the list imposes restraints on what can be inserted, such as no null 2523: * elements, this should be documented. A lock is obtained on the mutex before 2524: * any of the elements are added. 2525: * 2526: * @param o the object to add 2527: * @return <code>true</code>, as defined by Collection for a modified list 2528: * @throws UnsupportedOperationException if this list does not support the 2529: * add operation 2530: * @throws ClassCastException if o cannot be added to this list due to its 2531: * type 2532: * @throws IllegalArgumentException if o cannot be added to this list for 2533: * some other reason 2534: * @throws NullPointerException if o is null and this list doesn't support 2535: * the addition of null values. 2536: */ 2537: public boolean addAll(int index, Collection c) 2538: { 2539: synchronized (mutex) 2540: { 2541: return list.addAll(index, c); 2542: } 2543: } 2544: 2545: /** 2546: * Tests whether the underlying list is equal to the supplied object. 2547: * The object is deemed to be equal if it is also a <code>List</code> 2548: * of equal size and with the same elements (i.e. each element, e1, 2549: * in list, l1, and each element, e2, in l2, must return <code>true</code> for 2550: * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the 2551: * comparison is made, a lock is obtained on the mutex. 2552: * 2553: * @param o The object to test for equality with the underlying list. 2554: * @return <code>true</code> if o is equal to the underlying list under the above 2555: * definition. 2556: */ 2557: public boolean equals(Object o) 2558: { 2559: synchronized (mutex) 2560: { 2561: return list.equals(o); 2562: } 2563: } 2564: 2565: /** 2566: * Retrieves the object at the specified index. A lock 2567: * is obtained on the mutex before the list is accessed. 2568: * 2569: * @param index the index of the element to be returned 2570: * @return the element at index index in this list 2571: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2572: */ 2573: public Object get(int index) 2574: { 2575: synchronized (mutex) 2576: { 2577: return list.get(index); 2578: } 2579: } 2580: 2581: /** 2582: * Obtains a hashcode for the underlying list, first obtaining 2583: * a lock on the mutex. The calculation of the hashcode is 2584: * detailed in the documentation for the <code>List</code> 2585: * interface. 2586: * 2587: * @return The hashcode of the underlying list. 2588: * @see List#hashCode() 2589: */ 2590: public int hashCode() 2591: { 2592: synchronized (mutex) 2593: { 2594: return list.hashCode(); 2595: } 2596: } 2597: 2598: /** 2599: * Obtain the first index at which a given object is to be found in the 2600: * underlying list. A lock is obtained on the mutex before the list is 2601: * accessed. 2602: * 2603: * @param o the object to search for 2604: * @return the least integer n such that <code>o == null ? get(n) == null : 2605: * o.equals(get(n))</code>, or -1 if there is no such index. 2606: * @throws ClassCastException if the type of o is not a valid 2607: * type for this list. 2608: * @throws NullPointerException if o is null and this 2609: * list does not support null values. 2610: */ 2611: 2612: public int indexOf(Object o) 2613: { 2614: synchronized (mutex) 2615: { 2616: return list.indexOf(o); 2617: } 2618: } 2619: 2620: /** 2621: * Obtain the last index at which a given object is to be found in this 2622: * underlying list. A lock is obtained on the mutex before the list 2623: * is accessed. 2624: * 2625: * @return the greatest integer n such that <code>o == null ? get(n) == null 2626: * : o.equals(get(n))</code>, or -1 if there is no such index. 2627: * @throws ClassCastException if the type of o is not a valid 2628: * type for this list. 2629: * @throws NullPointerException if o is null and this 2630: * list does not support null values. 2631: */ 2632: public int lastIndexOf(Object o) 2633: { 2634: synchronized (mutex) 2635: { 2636: return list.lastIndexOf(o); 2637: } 2638: } 2639: 2640: /** 2641: * Retrieves a synchronized wrapper around the underlying list's 2642: * list iterator. A lock is obtained on the mutex before the 2643: * list iterator is retrieved. 2644: * 2645: * @return A list iterator over the elements in the underlying list. 2646: * The list iterator allows additional list-specific operations 2647: * to be performed, in addition to those supplied by the 2648: * standard iterator. 2649: */ 2650: public ListIterator listIterator() 2651: { 2652: synchronized (mutex) 2653: { 2654: return new SynchronizedListIterator(mutex, list.listIterator()); 2655: } 2656: } 2657: 2658: /** 2659: * Retrieves a synchronized wrapper around the underlying list's 2660: * list iterator. A lock is obtained on the mutex before the 2661: * list iterator is retrieved. The iterator starts at the 2662: * index supplied, leading to the element at that index being 2663: * the first one returned by <code>next()</code>. Calling 2664: * <code>previous()</code> from this initial position returns 2665: * index - 1. 2666: * 2667: * @param index the position, between 0 and size() inclusive, to begin the 2668: * iteration from 2669: * @return A list iterator over the elements in the underlying list. 2670: * The list iterator allows additional list-specific operations 2671: * to be performed, in addition to those supplied by the 2672: * standard iterator. 2673: * @throws IndexOutOfBoundsException if index < 0 || index > size() 2674: */ 2675: public ListIterator listIterator(int index) 2676: { 2677: synchronized (mutex) 2678: { 2679: return new SynchronizedListIterator(mutex, list.listIterator(index)); 2680: } 2681: } 2682: 2683: /** 2684: * Remove the element at a given position in the underlying list (optional 2685: * operation). All remaining elements are shifted to the left to fill the gap. 2686: * A lock on the mutex is obtained before the element is removed. 2687: * 2688: * @param index the position within the list of the object to remove 2689: * @return the object that was removed 2690: * @throws UnsupportedOperationException if this list does not support the 2691: * remove operation 2692: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2693: */ 2694: public Object remove(int index) 2695: { 2696: synchronized (mutex) 2697: { 2698: return list.remove(index); 2699: } 2700: } 2701: 2702: /** 2703: * Replace an element of the underlying list with another object (optional 2704: * operation). A lock is obtained on the mutex before the element is 2705: * replaced. 2706: * 2707: * @param index the position within this list of the element to be replaced 2708: * @param o the object to replace it with 2709: * @return the object that was replaced 2710: * @throws UnsupportedOperationException if this list does not support the 2711: * set operation. 2712: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 2713: * @throws ClassCastException if o cannot be added to this list due to its 2714: * type 2715: * @throws IllegalArgumentException if o cannot be added to this list for 2716: * some other reason 2717: * @throws NullPointerException if o is null and this 2718: * list does not support null values. 2719: */ 2720: public Object set(int index, Object o) 2721: { 2722: synchronized (mutex) 2723: { 2724: return list.set(index, o); 2725: } 2726: } 2727: 2728: /** 2729: * Obtain a List view of a subsection of the underlying list, from fromIndex 2730: * (inclusive) to toIndex (exclusive). If the two indices are equal, the 2731: * sublist is empty. The returned list should be modifiable if and only 2732: * if this list is modifiable. Changes to the returned list should be 2733: * reflected in this list. If this list is structurally modified in 2734: * any way other than through the returned list, the result of any subsequent 2735: * operations on the returned list is undefined. A lock is obtained 2736: * on the mutex before the creation of the sublist. The returned list 2737: * is also synchronized, using the same mutex. 2738: * 2739: * @param fromIndex the index that the returned list should start from 2740: * (inclusive) 2741: * @param toIndex the index that the returned list should go to (exclusive) 2742: * @return a List backed by a subsection of this list 2743: * @throws IndexOutOfBoundsException if fromIndex < 0 2744: * || toIndex > size() || fromIndex > toIndex 2745: */ 2746: public List subList(int fromIndex, int toIndex) 2747: { 2748: synchronized (mutex) 2749: { 2750: return new SynchronizedList(mutex, list.subList(fromIndex, toIndex)); 2751: } 2752: } 2753: } // class SynchronizedList 2754: 2755: /** 2756: * The implementation of {@link #synchronizedList(List)} for random-access 2757: * lists. This class name is required for compatibility with Sun's JDK 2758: * serializability. 2759: * 2760: * @author Eric Blake (ebb9@email.byu.edu) 2761: */ 2762: private static final class SynchronizedRandomAccessList 2763: extends SynchronizedList implements RandomAccess 2764: { 2765: /** 2766: * Compatible with JDK 1.4. 2767: */ 2768: private static final long serialVersionUID = 1530674583602358482L; 2769: 2770: /** 2771: * Wrap a given list. 2772: * @param l the list to wrap 2773: * @throws NullPointerException if l is null 2774: */ 2775: SynchronizedRandomAccessList(List l) 2776: { 2777: super(l); 2778: } 2779: 2780: /** 2781: * Called only by trusted code to specify the mutex as well as the 2782: * collection. 2783: * @param sync the mutex 2784: * @param l the list 2785: */ 2786: SynchronizedRandomAccessList(Object sync, List l) 2787: { 2788: super(sync, l); 2789: } 2790: 2791: /** 2792: * Obtain a List view of a subsection of the underlying list, from fromIndex 2793: * (inclusive) to toIndex (exclusive). If the two indices are equal, the 2794: * sublist is empty. The returned list should be modifiable if and only 2795: * if this list is modifiable. Changes to the returned list should be 2796: * reflected in this list. If this list is structurally modified in 2797: * any way other than through the returned list, the result of any subsequent 2798: * operations on the returned list is undefined. A lock is obtained 2799: * on the mutex before the creation of the sublist. The returned list 2800: * is also synchronized, using the same mutex. Random accessibility 2801: * is also extended to the new list. 2802: * 2803: * @param fromIndex the index that the returned list should start from 2804: * (inclusive) 2805: * @param toIndex the index that the returned list should go to (exclusive) 2806: * @return a List backed by a subsection of this list 2807: * @throws IndexOutOfBoundsException if fromIndex < 0 2808: * || toIndex > size() || fromIndex > toIndex 2809: */ 2810: public List subList(int fromIndex, int toIndex) 2811: { 2812: synchronized (mutex) 2813: { 2814: return new SynchronizedRandomAccessList(mutex, 2815: list.subList(fromIndex, 2816: toIndex)); 2817: } 2818: } 2819: } // class SynchronizedRandomAccessList 2820: 2821: /** 2822: * The implementation of {@link SynchronizedList#listIterator()}. This 2823: * iterator must "sync" on the same object as the list it iterates over. 2824: * 2825: * @author Eric Blake (ebb9@email.byu.edu) 2826: */ 2827: private static final class SynchronizedListIterator 2828: extends SynchronizedIterator implements ListIterator 2829: { 2830: /** 2831: * The wrapped iterator, stored both here and in the superclass to 2832: * avoid excessive casting. 2833: */ 2834: private final ListIterator li; 2835: 2836: /** 2837: * Only trusted code creates a wrapper, with the specified sync. 2838: * @param sync the mutex 2839: * @param li the wrapped iterator 2840: */ 2841: SynchronizedListIterator(Object sync, ListIterator li) 2842: { 2843: super(sync, li); 2844: this.li = li; 2845: } 2846: 2847: /** 2848: * Insert an element into the underlying list at the current position of 2849: * the iterator (optional operation). The element is inserted in between 2850: * the element that would be returned by <code>previous()</code> and the 2851: * element that would be returned by <code>next()</code>. After the 2852: * insertion, a subsequent call to next is unaffected, but 2853: * a call to previous returns the item that was added. The values returned 2854: * by nextIndex() and previousIndex() are incremented. A lock is obtained 2855: * on the mutex before the addition takes place. 2856: * 2857: * @param o the object to insert into the list 2858: * @throws ClassCastException if the object is of a type which cannot be added 2859: * to this list. 2860: * @throws IllegalArgumentException if some other aspect of the object stops 2861: * it being added to this list. 2862: * @throws UnsupportedOperationException if this ListIterator does not 2863: * support the add operation. 2864: */ 2865: public void add(Object o) 2866: { 2867: synchronized (mutex) 2868: { 2869: li.add(o); 2870: } 2871: } 2872: 2873: /** 2874: * Tests whether there are elements remaining in the underlying list 2875: * in the reverse direction. In other words, <code>previous()</code> 2876: * will not fail with a NoSuchElementException. A lock is obtained 2877: * on the mutex before the check takes place. 2878: * 2879: * @return <code>true</code> if the list continues in the reverse direction 2880: */ 2881: public boolean hasPrevious() 2882: { 2883: synchronized (mutex) 2884: { 2885: return li.hasPrevious(); 2886: } 2887: } 2888: 2889: /** 2890: * Find the index of the element that would be returned by a call to 2891: * <code>next()</code>. If hasNext() returns <code>false</code>, this 2892: * returns the list size. A lock is obtained on the mutex before the 2893: * query takes place. 2894: * 2895: * @return the index of the element that would be returned by next() 2896: */ 2897: public int nextIndex() 2898: { 2899: synchronized (mutex) 2900: { 2901: return li.nextIndex(); 2902: } 2903: } 2904: 2905: /** 2906: * Obtain the previous element from the underlying list. Repeated 2907: * calls to previous may be used to iterate backwards over the entire list, 2908: * or calls to next and previous may be used together to go forwards and 2909: * backwards. Alternating calls to next and previous will return the same 2910: * element. A lock is obtained on the mutex before the object is retrieved. 2911: * 2912: * @return the next element in the list in the reverse direction 2913: * @throws NoSuchElementException if there are no more elements 2914: */ 2915: public Object previous() 2916: { 2917: synchronized (mutex) 2918: { 2919: return li.previous(); 2920: } 2921: } 2922: 2923: /** 2924: * Find the index of the element that would be returned by a call to 2925: * previous. If hasPrevious() returns <code>false</code>, this returns -1. 2926: * A lock is obtained on the mutex before the query takes place. 2927: * 2928: * @return the index of the element that would be returned by previous() 2929: */ 2930: public int previousIndex() 2931: { 2932: synchronized (mutex) 2933: { 2934: return li.previousIndex(); 2935: } 2936: } 2937: 2938: /** 2939: * Replace the element last returned by a call to <code>next()</code> or 2940: * <code>previous()</code> with a given object (optional operation). This 2941: * method may only be called if neither <code>add()</code> nor 2942: * <code>remove()</code> have been called since the last call to 2943: * <code>next()</code> or <code>previous</code>. A lock is obtained 2944: * on the mutex before the list is modified. 2945: * 2946: * @param o the object to replace the element with 2947: * @throws ClassCastException the object is of a type which cannot be added 2948: * to this list 2949: * @throws IllegalArgumentException some other aspect of the object stops 2950: * it being added to this list 2951: * @throws IllegalStateException if neither next or previous have been 2952: * called, or if add or remove has been called since the last call 2953: * to next or previous 2954: * @throws UnsupportedOperationException if this ListIterator does not 2955: * support the set operation 2956: */ 2957: public void set(Object o) 2958: { 2959: synchronized (mutex) 2960: { 2961: li.set(o); 2962: } 2963: } 2964: } // class SynchronizedListIterator 2965: 2966: /** 2967: * Returns a synchronized (thread-safe) map wrapper backed by the given 2968: * map. Notice that element access through the collection views and their 2969: * iterators are thread-safe, but if the map can be structurally modified 2970: * (adding or removing elements) then you should synchronize around the 2971: * iteration to avoid non-deterministic behavior:<br> 2972: * <pre> 2973: * Map m = Collections.synchronizedMap(new Map(...)); 2974: * ... 2975: * Set s = m.keySet(); // safe outside a synchronized block 2976: * synchronized (m) // synch on m, not s 2977: * { 2978: * Iterator i = s.iterator(); 2979: * while (i.hasNext()) 2980: * foo(i.next()); 2981: * } 2982: * </pre><p> 2983: * 2984: * The returned Map implements Serializable, but can only be serialized if 2985: * the map it wraps is likewise Serializable. 2986: * 2987: * @param m the map to wrap 2988: * @return a synchronized view of the map 2989: * @see Serializable 2990: */ 2991: public static Map synchronizedMap(Map m) 2992: { 2993: return new SynchronizedMap(m); 2994: } 2995: 2996: /** 2997: * The implementation of {@link #synchronizedMap(Map)}. This 2998: * class name is required for compatibility with Sun's JDK serializability. 2999: * 3000: * @author Eric Blake (ebb9@email.byu.edu) 3001: */ 3002: private static class SynchronizedMap implements Map, Serializable 3003: { 3004: /** 3005: * Compatible with JDK 1.4. 3006: */ 3007: private static final long serialVersionUID = 1978198479659022715L; 3008: 3009: /** 3010: * The wrapped map. 3011: * @serial the real map 3012: */ 3013: private final Map m; 3014: 3015: /** 3016: * The object to synchronize on. When an instance is created via public 3017: * methods, it will be this; but other uses like 3018: * SynchronizedSortedMap.subMap() must specify another mutex. Package 3019: * visible for use by subclass. 3020: * @serial the lock 3021: */ 3022: final Object mutex; 3023: 3024: /** 3025: * Cache the entry set. 3026: */ 3027: private transient Set entries; 3028: 3029: /** 3030: * Cache the key set. 3031: */ 3032: private transient Set keys; 3033: 3034: /** 3035: * Cache the value collection. 3036: */ 3037: private transient Collection values; 3038: 3039: /** 3040: * Wrap a given map. 3041: * @param m the map to wrap 3042: * @throws NullPointerException if m is null 3043: */ 3044: SynchronizedMap(Map m) 3045: { 3046: this.m = m; 3047: mutex = this; 3048: if (m == null) 3049: throw new NullPointerException(); 3050: } 3051: 3052: /** 3053: * Called only by trusted code to specify the mutex as well as the map. 3054: * @param sync the mutex 3055: * @param m the map 3056: */ 3057: SynchronizedMap(Object sync, Map m) 3058: { 3059: this.m = m; 3060: mutex = sync; 3061: } 3062: 3063: /** 3064: * Clears all the entries from the underlying map. A lock is obtained 3065: * on the mutex before the map is cleared. 3066: * 3067: * @throws UnsupportedOperationException if clear is not supported 3068: */ 3069: public void clear() 3070: { 3071: synchronized (mutex) 3072: { 3073: m.clear(); 3074: } 3075: } 3076: 3077: /** 3078: * Returns <code>true</code> if the underlying map contains a entry for the given key. 3079: * A lock is obtained on the mutex before the map is queried. 3080: * 3081: * @param key the key to search for. 3082: * @return <code>true</code> if the underlying map contains the key. 3083: * @throws ClassCastException if the key is of an inappropriate type. 3084: * @throws NullPointerException if key is <code>null</code> but the map 3085: * does not permit null keys. 3086: */ 3087: public boolean containsKey(Object key) 3088: { 3089: synchronized (mutex) 3090: { 3091: return m.containsKey(key); 3092: } 3093: } 3094: 3095: /** 3096: * Returns <code>true</code> if the underlying map contains at least one entry with the 3097: * given value. In other words, returns <code>true</code> if a value v exists where 3098: * <code>(value == null ? v == null : value.equals(v))</code>. This usually 3099: * requires linear time. A lock is obtained on the mutex before the map 3100: * is queried. 3101: * 3102: * @param value the value to search for 3103: * @return <code>true</code> if the map contains the value 3104: * @throws ClassCastException if the type of the value is not a valid type 3105: * for this map. 3106: * @throws NullPointerException if the value is null and the map doesn't 3107: * support null values. 3108: */ 3109: public boolean containsValue(Object value) 3110: { 3111: synchronized (mutex) 3112: { 3113: return m.containsValue(value); 3114: } 3115: } 3116: 3117: // This is one of the ickiest cases of nesting I've ever seen. It just 3118: // means "return a SynchronizedSet, except that the iterator() method 3119: // returns an SynchronizedIterator whose next() method returns a 3120: // synchronized wrapper around its normal return value". 3121: public Set entrySet() 3122: { 3123: // Define this here to spare some nesting. 3124: class SynchronizedMapEntry implements Map.Entry 3125: { 3126: final Map.Entry e; 3127: SynchronizedMapEntry(Object o) 3128: { 3129: e = (Map.Entry) o; 3130: } 3131: 3132: /** 3133: * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code> 3134: * with the same key and value as the underlying entry. A lock is 3135: * obtained on the mutex before the comparison takes place. 3136: * 3137: * @param o The object to compare with this entry. 3138: * @return <code>true</code> if o is equivalent to the underlying map entry. 3139: */ 3140: public boolean equals(Object o) 3141: { 3142: synchronized (mutex) 3143: { 3144: return e.equals(o); 3145: } 3146: } 3147: 3148: /** 3149: * Returns the key used in the underlying map entry. A lock is obtained 3150: * on the mutex before the key is retrieved. 3151: * 3152: * @return The key of the underlying map entry. 3153: */ 3154: public Object getKey() 3155: { 3156: synchronized (mutex) 3157: { 3158: return e.getKey(); 3159: } 3160: } 3161: 3162: /** 3163: * Returns the value used in the underlying map entry. A lock is obtained 3164: * on the mutex before the value is retrieved. 3165: * 3166: * @return The value of the underlying map entry. 3167: */ 3168: public Object getValue() 3169: { 3170: synchronized (mutex) 3171: { 3172: return e.getValue(); 3173: } 3174: } 3175: 3176: /** 3177: * Computes the hash code for the underlying map entry. 3178: * This computation is described in the documentation for the 3179: * <code>Map</code> interface. A lock is obtained on the mutex 3180: * before the underlying map is accessed. 3181: * 3182: * @return The hash code of the underlying map entry. 3183: * @see Map#hashCode() 3184: */ 3185: public int hashCode() 3186: { 3187: synchronized (mutex) 3188: { 3189: return e.hashCode(); 3190: } 3191: } 3192: 3193: /** 3194: * Replaces the value in the underlying map entry with the specified 3195: * object (optional operation). A lock is obtained on the mutex 3196: * before the map is altered. The map entry, in turn, will alter 3197: * the underlying map object. The operation is undefined if the 3198: * <code>remove()</code> method of the iterator has been called 3199: * beforehand. 3200: * 3201: * @param value the new value to store 3202: * @return the old value 3203: * @throws UnsupportedOperationException if the operation is not supported. 3204: * @throws ClassCastException if the value is of the wrong type. 3205: * @throws IllegalArgumentException if something about the value 3206: * prevents it from existing in this map. 3207: * @throws NullPointerException if the map forbids null values. 3208: */ 3209: public Object setValue(Object value) 3210: { 3211: synchronized (mutex) 3212: { 3213: return e.setValue(value); 3214: } 3215: } 3216: 3217: /** 3218: * Returns a textual representation of the underlying map entry. 3219: * A lock is obtained on the mutex before the entry is accessed. 3220: * 3221: * @return The contents of the map entry in <code>String</code> form. 3222: */ 3223: public String toString() 3224: { 3225: synchronized (mutex) 3226: { 3227: return e.toString(); 3228: } 3229: } 3230: } // class SynchronizedMapEntry 3231: 3232: // Now the actual code. 3233: if (entries == null) 3234: synchronized (mutex) 3235: { 3236: entries = new SynchronizedSet(mutex, m.entrySet()) 3237: { 3238: /** 3239: * Returns an iterator over the set. The iterator has no specific order, 3240: * unless further specified. A lock is obtained on the set's mutex 3241: * before the iterator is created. The created iterator is also 3242: * thread-safe. 3243: * 3244: * @return A synchronized set iterator. 3245: */ 3246: public Iterator iterator() 3247: { 3248: synchronized (super.mutex) 3249: { 3250: return new SynchronizedIterator(super.mutex, c.iterator()) 3251: { 3252: /** 3253: * Retrieves the next map entry from the iterator. 3254: * A lock is obtained on the iterator's mutex before 3255: * the entry is created. The new map entry is enclosed in 3256: * a thread-safe wrapper. 3257: * 3258: * @return A synchronized map entry. 3259: */ 3260: public Object next() 3261: { 3262: synchronized (super.mutex) 3263: { 3264: return new SynchronizedMapEntry(super.next()); 3265: } 3266: } 3267: }; 3268: } 3269: } 3270: }; 3271: } 3272: return entries; 3273: } 3274: 3275: /** 3276: * Returns <code>true</code> if the object, o, is also an instance 3277: * of <code>Map</code> and contains an equivalent 3278: * entry set to that of the underlying map. A lock 3279: * is obtained on the mutex before the objects are 3280: * compared. 3281: * 3282: * @param o The object to compare. 3283: * @return <code>true</code> if o and the underlying map are equivalent. 3284: */ 3285: public boolean equals(Object o) 3286: { 3287: synchronized (mutex) 3288: { 3289: return m.equals(o); 3290: } 3291: } 3292: 3293: /** 3294: * Returns the value associated with the given key, or null 3295: * if no such mapping exists. An ambiguity exists with maps 3296: * that accept null values as a return value of null could 3297: * be due to a non-existent mapping or simply a null value 3298: * for that key. To resolve this, <code>containsKey</code> 3299: * should be used. A lock is obtained on the mutex before 3300: * the value is retrieved from the underlying map. 3301: * 3302: * @param key The key of the required mapping. 3303: * @return The value associated with the given key, or 3304: * null if no such mapping exists. 3305: * @throws ClassCastException if the key is an inappropriate type. 3306: * @throws NullPointerException if this map does not accept null keys. 3307: */ 3308: public Object get(Object key) 3309: { 3310: synchronized (mutex) 3311: { 3312: return m.get(key); 3313: } 3314: } 3315: 3316: /** 3317: * Calculates the hash code of the underlying map as the 3318: * sum of the hash codes of all entries. A lock is obtained 3319: * on the mutex before the hash code is computed. 3320: * 3321: * @return The hash code of the underlying map. 3322: */ 3323: public int hashCode() 3324: { 3325: synchronized (mutex) 3326: { 3327: return m.hashCode(); 3328: } 3329: } 3330: 3331: /** 3332: * Returns <code>true</code> if the underlying map contains no entries. 3333: * A lock is obtained on the mutex before the map is examined. 3334: * 3335: * @return <code>true</code> if the map is empty. 3336: */ 3337: public boolean isEmpty() 3338: { 3339: synchronized (mutex) 3340: { 3341: return m.isEmpty(); 3342: } 3343: } 3344: 3345: /** 3346: * Returns a thread-safe set view of the keys in the underlying map. The 3347: * set is backed by the map, so that changes in one show up in the other. 3348: * Modifications made while an iterator is in progress cause undefined 3349: * behavior. If the set supports removal, these methods remove the 3350: * underlying mapping from the map: <code>Iterator.remove</code>, 3351: * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, 3352: * and <code>clear</code>. Element addition, via <code>add</code> or 3353: * <code>addAll</code>, is not supported via this set. A lock is obtained 3354: * on the mutex before the set is created. 3355: * 3356: * @return A synchronized set containing the keys of the underlying map. 3357: */ 3358: public Set keySet() 3359: { 3360: if (keys == null) 3361: synchronized (mutex) 3362: { 3363: keys = new SynchronizedSet(mutex, m.keySet()); 3364: } 3365: return keys; 3366: } 3367: 3368: /** 3369: * Associates the given key to the given value (optional operation). If the 3370: * underlying map already contains the key, its value is replaced. Be aware 3371: * that in a map that permits <code>null</code> values, a null return does not 3372: * always imply that the mapping was created. A lock is obtained on the mutex 3373: * before the modification is made. 3374: * 3375: * @param key the key to map. 3376: * @param value the value to be mapped. 3377: * @return the previous value of the key, or null if there was no mapping 3378: * @throws UnsupportedOperationException if the operation is not supported 3379: * @throws ClassCastException if the key or value is of the wrong type 3380: * @throws IllegalArgumentException if something about this key or value 3381: * prevents it from existing in this map 3382: * @throws NullPointerException if either the key or the value is null, 3383: * and the map forbids null keys or values 3384: * @see #containsKey(Object) 3385: */ 3386: public Object put(Object key, Object value) 3387: { 3388: synchronized (mutex) 3389: { 3390: return m.put(key, value); 3391: } 3392: } 3393: 3394: /** 3395: * Copies all entries of the given map to the underlying one (optional 3396: * operation). If the map already contains a key, its value is replaced. 3397: * A lock is obtained on the mutex before the operation proceeds. 3398: * 3399: * @param map the mapping to load into this map 3400: * @throws UnsupportedOperationException if the operation is not supported 3401: * @throws ClassCastException if a key or value is of the wrong type 3402: * @throws IllegalArgumentException if something about a key or value 3403: * prevents it from existing in this map 3404: * @throws NullPointerException if the map forbids null keys or values, or 3405: * if <code>m</code> is null. 3406: * @see #put(Object, Object) 3407: */ 3408: public void putAll(Map map) 3409: { 3410: synchronized (mutex) 3411: { 3412: m.putAll(map); 3413: } 3414: } 3415: 3416: /** 3417: * Removes the mapping for the key, o, if present (optional operation). If 3418: * the key is not present, this returns null. Note that maps which permit 3419: * null values may also return null if the key was removed. A prior 3420: * <code>containsKey()</code> check is required to avoid this ambiguity. 3421: * Before the mapping is removed, a lock is obtained on the mutex. 3422: * 3423: * @param o the key to remove 3424: * @return the value the key mapped to, or null if not present 3425: * @throws UnsupportedOperationException if deletion is unsupported 3426: * @throws NullPointerException if the key is null and this map doesn't 3427: * support null keys. 3428: * @throws ClassCastException if the type of the key is not a valid type 3429: * for this map. 3430: */ 3431: public Object remove(Object o) 3432: { 3433: synchronized (mutex) 3434: { 3435: return m.remove(o); 3436: } 3437: } 3438: 3439: /** 3440: * Retrieves the size of the underlying map. A lock 3441: * is obtained on the mutex before access takes place. 3442: * Maps with a size greater than <code>Integer.MAX_VALUE</code> 3443: * return <code>Integer.MAX_VALUE</code> instead. 3444: * 3445: * @return The size of the underlying map. 3446: */ 3447: public int size() 3448: { 3449: synchronized (mutex) 3450: { 3451: return m.size(); 3452: } 3453: } 3454: 3455: /** 3456: * Returns a textual representation of the underlying 3457: * map. A lock is obtained on the mutex before the map 3458: * is accessed. 3459: * 3460: * @return The map in <code>String</code> form. 3461: */ 3462: public String toString() 3463: { 3464: synchronized (mutex) 3465: { 3466: return m.toString(); 3467: } 3468: } 3469: 3470: /** 3471: * Returns a synchronized collection view of the values in the underlying 3472: * map. The collection is backed by the map, so that changes in one show up in 3473: * the other. Modifications made while an iterator is in progress cause 3474: * undefined behavior. If the collection supports removal, these methods 3475: * remove the underlying mapping from the map: <code>Iterator.remove</code>, 3476: * <code>Collection.remove</code>, <code>removeAll</code>, 3477: * <code>retainAll</code>, and <code>clear</code>. Element addition, via 3478: * <code>add</code> or <code>addAll</code>, is not supported via this 3479: * collection. A lock is obtained on the mutex before the collection 3480: * is created. 3481: * 3482: * @return the collection of all values in the underlying map. 3483: */ 3484: public Collection values() 3485: { 3486: if (values == null) 3487: synchronized (mutex) 3488: { 3489: values = new SynchronizedCollection(mutex, m.values()); 3490: } 3491: return values; 3492: } 3493: } // class SynchronizedMap 3494: 3495: /** 3496: * Returns a synchronized (thread-safe) set wrapper backed by the given 3497: * set. Notice that element access through the iterator is thread-safe, but 3498: * if the set can be structurally modified (adding or removing elements) 3499: * then you should synchronize around the iteration to avoid 3500: * non-deterministic behavior:<br> 3501: * <pre> 3502: * Set s = Collections.synchronizedSet(new Set(...)); 3503: * ... 3504: * synchronized (s) 3505: * { 3506: * Iterator i = s.iterator(); 3507: * while (i.hasNext()) 3508: * foo(i.next()); 3509: * } 3510: * </pre><p> 3511: * 3512: * The returned Set implements Serializable, but can only be serialized if 3513: * the set it wraps is likewise Serializable. 3514: * 3515: * @param s the set to wrap 3516: * @return a synchronized view of the set 3517: * @see Serializable 3518: */ 3519: public static Set synchronizedSet(Set s) 3520: { 3521: return new SynchronizedSet(s); 3522: } 3523: 3524: /** 3525: * The implementation of {@link #synchronizedSet(Set)}. This class 3526: * name is required for compatibility with Sun's JDK serializability. 3527: * Package visible, so that sets such as Hashtable.keySet() 3528: * can specify which object to synchronize on. 3529: * 3530: * @author Eric Blake (ebb9@email.byu.edu) 3531: */ 3532: static class SynchronizedSet extends SynchronizedCollection 3533: implements Set 3534: { 3535: /** 3536: * Compatible with JDK 1.4. 3537: */ 3538: private static final long serialVersionUID = 487447009682186044L; 3539: 3540: /** 3541: * Wrap a given set. 3542: * @param s the set to wrap 3543: * @throws NullPointerException if s is null 3544: */ 3545: SynchronizedSet(Set s) 3546: { 3547: super(s); 3548: } 3549: 3550: /** 3551: * Called only by trusted code to specify the mutex as well as the set. 3552: * @param sync the mutex 3553: * @param s the set 3554: */ 3555: SynchronizedSet(Object sync, Set s) 3556: { 3557: super(sync, s); 3558: } 3559: 3560: /** 3561: * Returns <code>true</code> if the object, o, is a <code>Set</code> 3562: * of the same size as the underlying set, and contains 3563: * each element, e, which occurs in the underlying set. 3564: * A lock is obtained on the mutex before the comparison 3565: * takes place. 3566: * 3567: * @param o The object to compare against. 3568: * @return <code>true</code> if o is an equivalent set. 3569: */ 3570: public boolean equals(Object o) 3571: { 3572: synchronized (mutex) 3573: { 3574: return c.equals(o); 3575: } 3576: } 3577: 3578: /** 3579: * Computes the hash code for the underlying set as the 3580: * sum of the hash code of all elements within the set. 3581: * A lock is obtained on the mutex before the computation 3582: * occurs. 3583: * 3584: * @return The hash code for the underlying set. 3585: */ 3586: public int hashCode() 3587: { 3588: synchronized (mutex) 3589: { 3590: return c.hashCode(); 3591: } 3592: } 3593: } // class SynchronizedSet 3594: 3595: /** 3596: * Returns a synchronized (thread-safe) sorted map wrapper backed by the 3597: * given map. Notice that element access through the collection views, 3598: * subviews, and their iterators are thread-safe, but if the map can be 3599: * structurally modified (adding or removing elements) then you should 3600: * synchronize around the iteration to avoid non-deterministic behavior:<br> 3601: * <pre> 3602: * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...)); 3603: * ... 3604: * Set s = m.keySet(); // safe outside a synchronized block 3605: * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block 3606: * Set s2 = m2.keySet(); // safe outside a synchronized block 3607: * synchronized (m) // synch on m, not m2, s or s2 3608: * { 3609: * Iterator i = s.iterator(); 3610: * while (i.hasNext()) 3611: * foo(i.next()); 3612: * i = s2.iterator(); 3613: * while (i.hasNext()) 3614: * bar(i.next()); 3615: * } 3616: * </pre><p> 3617: * 3618: * The returned SortedMap implements Serializable, but can only be 3619: * serialized if the map it wraps is likewise Serializable. 3620: * 3621: * @param m the sorted map to wrap 3622: * @return a synchronized view of the sorted map 3623: * @see Serializable 3624: */ 3625: public static SortedMap synchronizedSortedMap(SortedMap m) 3626: { 3627: return new SynchronizedSortedMap(m); 3628: } 3629: 3630: /** 3631: * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This 3632: * class name is required for compatibility with Sun's JDK serializability. 3633: * 3634: * @author Eric Blake (ebb9@email.byu.edu) 3635: */ 3636: private static final class SynchronizedSortedMap extends SynchronizedMap 3637: implements SortedMap 3638: { 3639: /** 3640: * Compatible with JDK 1.4. 3641: */ 3642: private static final long serialVersionUID = -8798146769416483793L; 3643: 3644: /** 3645: * The wrapped map; stored both here and in the superclass to avoid 3646: * excessive casting. 3647: * @serial the wrapped map 3648: */ 3649: private final SortedMap sm; 3650: 3651: /** 3652: * Wrap a given map. 3653: * @param sm the map to wrap 3654: * @throws NullPointerException if sm is null 3655: */ 3656: SynchronizedSortedMap(SortedMap sm) 3657: { 3658: super(sm); 3659: this.sm = sm; 3660: } 3661: 3662: /** 3663: * Called only by trusted code to specify the mutex as well as the map. 3664: * @param sync the mutex 3665: * @param sm the map 3666: */ 3667: SynchronizedSortedMap(Object sync, SortedMap sm) 3668: { 3669: super(sync, sm); 3670: this.sm = sm; 3671: } 3672: 3673: /** 3674: * Returns the comparator used in sorting the underlying map, or null if 3675: * it is the keys' natural ordering. A lock is obtained on the mutex 3676: * before the comparator is retrieved. 3677: * 3678: * @return the sorting comparator. 3679: */ 3680: public Comparator comparator() 3681: { 3682: synchronized (mutex) 3683: { 3684: return sm.comparator(); 3685: } 3686: } 3687: 3688: /** 3689: * Returns the first, lowest sorted, key from the underlying map. 3690: * A lock is obtained on the mutex before the map is accessed. 3691: * 3692: * @return the first key. 3693: * @throws NoSuchElementException if this map is empty. 3694: */ 3695: public Object firstKey() 3696: { 3697: synchronized (mutex) 3698: { 3699: return sm.firstKey(); 3700: } 3701: } 3702: 3703: /** 3704: * Returns a submap containing the keys from the first 3705: * key (as returned by <code>firstKey()</code>) to 3706: * the key before that specified. The submap supports all 3707: * operations supported by the underlying map and all actions 3708: * taking place on the submap are also reflected in the underlying 3709: * map. A lock is obtained on the mutex prior to submap creation. 3710: * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>. 3711: * The submap retains the thread-safe status of this map. 3712: * 3713: * @param toKey the exclusive upper range of the submap. 3714: * @return a submap from <code>firstKey()</code> to the 3715: * the key preceding toKey. 3716: * @throws ClassCastException if toKey is not comparable to the underlying 3717: * map's contents. 3718: * @throws IllegalArgumentException if toKey is outside the map's range. 3719: * @throws NullPointerException if toKey is null. but the map does not allow 3720: * null keys. 3721: */ 3722: public SortedMap headMap(Object toKey) 3723: { 3724: synchronized (mutex) 3725: { 3726: return new SynchronizedSortedMap(mutex, sm.headMap(toKey)); 3727: } 3728: } 3729: 3730: /** 3731: * Returns the last, highest sorted, key from the underlying map. 3732: * A lock is obtained on the mutex before the map is accessed. 3733: * 3734: * @return the last key. 3735: * @throws NoSuchElementException if this map is empty. 3736: */ 3737: public Object lastKey() 3738: { 3739: synchronized (mutex) 3740: { 3741: return sm.lastKey(); 3742: } 3743: } 3744: 3745: /** 3746: * Returns a submap containing the keys from fromKey to 3747: * the key before toKey. The submap supports all 3748: * operations supported by the underlying map and all actions 3749: * taking place on the submap are also reflected in the underlying 3750: * map. A lock is obtained on the mutex prior to submap creation. 3751: * The submap retains the thread-safe status of this map. 3752: * 3753: * @param fromKey the inclusive lower range of the submap. 3754: * @param toKey the exclusive upper range of the submap. 3755: * @return a submap from fromKey to the key preceding toKey. 3756: * @throws ClassCastException if fromKey or toKey is not comparable 3757: * to the underlying map's contents. 3758: * @throws IllegalArgumentException if fromKey or toKey is outside the map's 3759: * range. 3760: * @throws NullPointerException if fromKey or toKey is null. but the map does 3761: * not allow null keys. 3762: */ 3763: public SortedMap subMap(Object fromKey, Object toKey) 3764: { 3765: synchronized (mutex) 3766: { 3767: return new SynchronizedSortedMap(mutex, sm.subMap(fromKey, toKey)); 3768: } 3769: } 3770: 3771: /** 3772: * Returns a submap containing all the keys from fromKey onwards. 3773: * The submap supports all operations supported by the underlying 3774: * map and all actions taking place on the submap are also reflected 3775: * in the underlying map. A lock is obtained on the mutex prior to 3776: * submap creation. The submap retains the thread-safe status of 3777: * this map. 3778: * 3779: * @param fromKey the inclusive lower range of the submap. 3780: * @return a submap from fromKey to <code>lastKey()</code>. 3781: * @throws ClassCastException if fromKey is not comparable to the underlying 3782: * map's contents. 3783: * @throws IllegalArgumentException if fromKey is outside the map's range. 3784: * @throws NullPointerException if fromKey is null. but the map does not allow 3785: * null keys. 3786: */ 3787: public SortedMap tailMap(Object fromKey) 3788: { 3789: synchronized (mutex) 3790: { 3791: return new SynchronizedSortedMap(mutex, sm.tailMap(fromKey)); 3792: } 3793: } 3794: } // class SynchronizedSortedMap 3795: 3796: /** 3797: * Returns a synchronized (thread-safe) sorted set wrapper backed by the 3798: * given set. Notice that element access through the iterator and through 3799: * subviews are thread-safe, but if the set can be structurally modified 3800: * (adding or removing elements) then you should synchronize around the 3801: * iteration to avoid non-deterministic behavior:<br> 3802: * <pre> 3803: * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...)); 3804: * ... 3805: * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block 3806: * synchronized (s) // synch on s, not s2 3807: * { 3808: * Iterator i = s2.iterator(); 3809: * while (i.hasNext()) 3810: * foo(i.next()); 3811: * } 3812: * </pre><p> 3813: * 3814: * The returned SortedSet implements Serializable, but can only be 3815: * serialized if the set it wraps is likewise Serializable. 3816: * 3817: * @param s the sorted set to wrap 3818: * @return a synchronized view of the sorted set 3819: * @see Serializable 3820: */ 3821: public static SortedSet synchronizedSortedSet(SortedSet s) 3822: { 3823: return new SynchronizedSortedSet(s); 3824: } 3825: 3826: /** 3827: * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This 3828: * class name is required for compatibility with Sun's JDK serializability. 3829: * 3830: * @author Eric Blake (ebb9@email.byu.edu) 3831: */ 3832: private static final class SynchronizedSortedSet extends SynchronizedSet 3833: implements SortedSet 3834: { 3835: /** 3836: * Compatible with JDK 1.4. 3837: */ 3838: private static final long serialVersionUID = 8695801310862127406L; 3839: 3840: /** 3841: * The wrapped set; stored both here and in the superclass to avoid 3842: * excessive casting. 3843: * @serial the wrapped set 3844: */ 3845: private final SortedSet ss; 3846: 3847: /** 3848: * Wrap a given set. 3849: * @param ss the set to wrap 3850: * @throws NullPointerException if ss is null 3851: */ 3852: SynchronizedSortedSet(SortedSet ss) 3853: { 3854: super(ss); 3855: this.ss = ss; 3856: } 3857: 3858: /** 3859: * Called only by trusted code to specify the mutex as well as the set. 3860: * @param sync the mutex 3861: * @param l the list 3862: */ 3863: SynchronizedSortedSet(Object sync, SortedSet ss) 3864: { 3865: super(sync, ss); 3866: this.ss = ss; 3867: } 3868: 3869: /** 3870: * Returns the comparator used in sorting the underlying set, or null if 3871: * it is the elements' natural ordering. A lock is obtained on the mutex 3872: * before the comparator is retrieved. 3873: * 3874: * @return the sorting comparator. 3875: */ 3876: public Comparator comparator() 3877: { 3878: synchronized (mutex) 3879: { 3880: return ss.comparator(); 3881: } 3882: } 3883: 3884: /** 3885: * Returns the first, lowest sorted, element from the underlying set. 3886: * A lock is obtained on the mutex before the set is accessed. 3887: * 3888: * @return the first element. 3889: * @throws NoSuchElementException if this set is empty. 3890: */ 3891: public Object first() 3892: { 3893: synchronized (mutex) 3894: { 3895: return ss.first(); 3896: } 3897: } 3898: 3899: /** 3900: * Returns a subset containing the element from the first 3901: * element (as returned by <code>first()</code>) to 3902: * the element before that specified. The subset supports all 3903: * operations supported by the underlying set and all actions 3904: * taking place on the subset are also reflected in the underlying 3905: * set. A lock is obtained on the mutex prior to subset creation. 3906: * This operation is equivalent to <code>subSet(first(), toElement)</code>. 3907: * The subset retains the thread-safe status of this set. 3908: * 3909: * @param toElement the exclusive upper range of the subset. 3910: * @return a subset from <code>first()</code> to the 3911: * the element preceding toElement. 3912: * @throws ClassCastException if toElement is not comparable to the underlying 3913: * set's contents. 3914: * @throws IllegalArgumentException if toElement is outside the set's range. 3915: * @throws NullPointerException if toElement is null. but the set does not allow 3916: * null elements. 3917: */ 3918: public SortedSet headSet(Object toElement) 3919: { 3920: synchronized (mutex) 3921: { 3922: return new SynchronizedSortedSet(mutex, ss.headSet(toElement)); 3923: } 3924: } 3925: 3926: /** 3927: * Returns the last, highest sorted, element from the underlying set. 3928: * A lock is obtained on the mutex before the set is accessed. 3929: * 3930: * @return the last element. 3931: * @throws NoSuchElementException if this set is empty. 3932: */ 3933: public Object last() 3934: { 3935: synchronized (mutex) 3936: { 3937: return ss.last(); 3938: } 3939: } 3940: 3941: /** 3942: * Returns a subset containing the elements from fromElement to 3943: * the element before toElement. The subset supports all 3944: * operations supported by the underlying set and all actions 3945: * taking place on the subset are also reflected in the underlying 3946: * set. A lock is obtained on the mutex prior to subset creation. 3947: * The subset retains the thread-safe status of this set. 3948: * 3949: * @param fromElement the inclusive lower range of the subset. 3950: * @param toElement the exclusive upper range of the subset. 3951: * @return a subset from fromElement to the element preceding toElement. 3952: * @throws ClassCastException if fromElement or toElement is not comparable 3953: * to the underlying set's contents. 3954: * @throws IllegalArgumentException if fromElement or toElement is outside the set's 3955: * range. 3956: * @throws NullPointerException if fromElement or toElement is null. but the set does 3957: * not allow null elements. 3958: */ 3959: public SortedSet subSet(Object fromElement, Object toElement) 3960: { 3961: synchronized (mutex) 3962: { 3963: return new SynchronizedSortedSet(mutex, 3964: ss.subSet(fromElement, toElement)); 3965: } 3966: } 3967: 3968: /** 3969: * Returns a subset containing all the elements from fromElement onwards. 3970: * The subset supports all operations supported by the underlying 3971: * set and all actions taking place on the subset are also reflected 3972: * in the underlying set. A lock is obtained on the mutex prior to 3973: * subset creation. The subset retains the thread-safe status of 3974: * this set. 3975: * 3976: * @param fromElement the inclusive lower range of the subset. 3977: * @return a subset from fromElement to <code>last()</code>. 3978: * @throws ClassCastException if fromElement is not comparable to the underlying 3979: * set's contents. 3980: * @throws IllegalArgumentException if fromElement is outside the set's range. 3981: * @throws NullPointerException if fromElement is null. but the set does not allow 3982: * null elements. 3983: */ 3984: public SortedSet tailSet(Object fromElement) 3985: { 3986: synchronized (mutex) 3987: { 3988: return new SynchronizedSortedSet(mutex, ss.tailSet(fromElement)); 3989: } 3990: } 3991: } // class SynchronizedSortedSet 3992: 3993: 3994: /** 3995: * Returns an unmodifiable view of the given collection. This allows 3996: * "read-only" access, although changes in the backing collection show up 3997: * in this view. Attempts to modify the collection directly or via iterators 3998: * will fail with {@link UnsupportedOperationException}. Although this view 3999: * prevents changes to the structure of the collection and its elements, the values 4000: * referenced by the objects in the collection can still be modified. 4001: * <p> 4002: * 4003: * Since the collection might be a List or a Set, and those have incompatible 4004: * equals and hashCode requirements, this relies on Object's implementation 4005: * rather than passing those calls on to the wrapped collection. The returned 4006: * Collection implements Serializable, but can only be serialized if 4007: * the collection it wraps is likewise Serializable. 4008: * 4009: * @param c the collection to wrap 4010: * @return a read-only view of the collection 4011: * @see Serializable 4012: */ 4013: public static Collection unmodifiableCollection(Collection c) 4014: { 4015: return new UnmodifiableCollection(c); 4016: } 4017: 4018: /** 4019: * The implementation of {@link #unmodifiableCollection(Collection)}. This 4020: * class name is required for compatibility with Sun's JDK serializability. 4021: * 4022: * @author Eric Blake (ebb9@email.byu.edu) 4023: */ 4024: private static class UnmodifiableCollection 4025: implements Collection, Serializable 4026: { 4027: /** 4028: * Compatible with JDK 1.4. 4029: */ 4030: private static final long serialVersionUID = 1820017752578914078L; 4031: 4032: /** 4033: * The wrapped collection. Package visible for use by subclasses. 4034: * @serial the real collection 4035: */ 4036: final Collection c; 4037: 4038: /** 4039: * Wrap a given collection. 4040: * @param c the collection to wrap 4041: * @throws NullPointerException if c is null 4042: */ 4043: UnmodifiableCollection(Collection c) 4044: { 4045: this.c = c; 4046: if (c == null) 4047: throw new NullPointerException(); 4048: } 4049: 4050: /** 4051: * Blocks the addition of elements to the underlying collection. 4052: * This method never returns, throwing an exception instead. 4053: * 4054: * @param o the object to add. 4055: * @return <code>true</code> if the collection was modified as a result of this action. 4056: * @throws UnsupportedOperationException as an unmodifiable collection does not 4057: * support the add operation. 4058: */ 4059: public boolean add(Object o) 4060: { 4061: throw new UnsupportedOperationException(); 4062: } 4063: 4064: /** 4065: * Blocks the addition of a collection of elements to the underlying 4066: * collection. This method never returns, throwing an exception instead. 4067: * 4068: * @param c the collection to add. 4069: * @return <code>true</code> if the collection was modified as a result of this action. 4070: * @throws UnsupportedOperationException as an unmodifiable collection does not 4071: * support the <code>addAll</code> operation. 4072: */ 4073: public boolean addAll(Collection c) 4074: { 4075: throw new UnsupportedOperationException(); 4076: } 4077: 4078: /** 4079: * Blocks the clearing of the underlying collection. This method never 4080: * returns, throwing an exception instead. 4081: * 4082: * @throws UnsupportedOperationException as an unmodifiable collection does 4083: * not support the <code>clear()</code> operation. 4084: */ 4085: public void clear() 4086: { 4087: throw new UnsupportedOperationException(); 4088: } 4089: 4090: /** 4091: * Test whether the underlying collection contains a given object as one of its 4092: * elements. 4093: * 4094: * @param o the element to look for. 4095: * @return <code>true</code> if the underlying collection contains at least 4096: * one element e such that 4097: * <code>o == null ? e == null : o.equals(e)</code>. 4098: * @throws ClassCastException if the type of o is not a valid type for the 4099: * underlying collection. 4100: * @throws NullPointerException if o is null and the underlying collection 4101: * doesn't support null values. 4102: */ 4103: public boolean contains(Object o) 4104: { 4105: return c.contains(o); 4106: } 4107: 4108: /** 4109: * Test whether the underlying collection contains every element in a given 4110: * collection. 4111: * 4112: * @param c1 the collection to test for. 4113: * @return <code>true</code> if for every element o in c, contains(o) would 4114: * return <code>true</code>. 4115: * @throws ClassCastException if the type of any element in c is not a valid 4116: * type for the underlying collection. 4117: * @throws NullPointerException if some element of c is null and the underlying 4118: * collection does not support null values. 4119: * @throws NullPointerException if c itself is null. 4120: */ 4121: public boolean containsAll(Collection c1) 4122: { 4123: return c.containsAll(c1); 4124: } 4125: 4126: /** 4127: * Tests whether the underlying collection is empty, that is, 4128: * if size() == 0. 4129: * 4130: * @return <code>true</code> if this collection contains no elements. 4131: */ 4132: public boolean isEmpty() 4133: { 4134: return c.isEmpty(); 4135: } 4136: 4137: /** 4138: * Obtain an Iterator over the underlying collection, which maintains 4139: * its unmodifiable nature. 4140: * 4141: * @return an UnmodifiableIterator over the elements of the underlying 4142: * collection, in any order. 4143: */ 4144: public Iterator iterator() 4145: { 4146: return new UnmodifiableIterator(c.iterator()); 4147: } 4148: 4149: /** 4150: * Blocks the removal of an object from the underlying collection. 4151: * This method never returns, throwing an exception instead. 4152: * 4153: * @param o The object to remove. 4154: * @return <code>true</code> if the object was removed (i.e. the underlying 4155: * collection returned 1 or more instances of o). 4156: * @throws UnsupportedOperationException as an unmodifiable collection 4157: * does not support the <code>remove()</code> operation. 4158: */ 4159: public boolean remove(Object o) 4160: { 4161: throw new UnsupportedOperationException(); 4162: } 4163: 4164: /** 4165: * Blocks the removal of a collection of objects from the underlying 4166: * collection. This method never returns, throwing an exception 4167: * instead. 4168: * 4169: * @param c The collection of objects to remove. 4170: * @return <code>true</code> if the collection was modified. 4171: * @throws UnsupportedOperationException as an unmodifiable collection 4172: * does not support the <code>removeAll()</code> operation. 4173: */ 4174: public boolean removeAll(Collection c) 4175: { 4176: throw new UnsupportedOperationException(); 4177: } 4178: 4179: /** 4180: * Blocks the removal of all elements from the underlying collection, 4181: * except those in the supplied collection. This method never returns, 4182: * throwing an exception instead. 4183: * 4184: * @param c The collection of objects to retain. 4185: * @return <code>true</code> if the collection was modified. 4186: * @throws UnsupportedOperationException as an unmodifiable collection 4187: * does not support the <code>retainAll()</code> operation. 4188: */ 4189: public boolean retainAll(Collection c) 4190: { 4191: throw new UnsupportedOperationException(); 4192: } 4193: 4194: /** 4195: * Retrieves the number of elements in the underlying collection. 4196: * 4197: * @return the number of elements in the collection. 4198: */ 4199: public int size() 4200: { 4201: return c.size(); 4202: } 4203: 4204: /** 4205: * Copy the current contents of the underlying collection into an array. 4206: * 4207: * @return an array of type Object[] with a length equal to the size of the 4208: * underlying collection and containing the elements currently in 4209: * the underlying collection, in any order. 4210: */ 4211: public Object[] toArray() 4212: { 4213: return c.toArray(); 4214: } 4215: 4216: /** 4217: * Copy the current contents of the underlying collection into an array. If 4218: * the array passed as an argument has length less than the size of the 4219: * underlying collection, an array of the same run-time type as a, with a length 4220: * equal to the size of the underlying collection, is allocated using reflection. 4221: * Otherwise, a itself is used. The elements of the underlying collection are 4222: * copied into it, and if there is space in the array, the following element is 4223: * set to null. The resultant array is returned. 4224: * Note: The fact that the following element is set to null is only useful 4225: * if it is known that this collection does not contain any null elements. 4226: * 4227: * @param a the array to copy this collection into. 4228: * @return an array containing the elements currently in the underlying 4229: * collection, in any order. 4230: * @throws ArrayStoreException if the type of any element of the 4231: * collection is not a subtype of the element type of a. 4232: */ 4233: public Object[] toArray(Object[] a) 4234: { 4235: return c.toArray(a); 4236: } 4237: 4238: /** 4239: * A textual representation of the unmodifiable collection. 4240: * 4241: * @return The unmodifiable collection in the form of a <code>String</code>. 4242: */ 4243: public String toString() 4244: { 4245: return c.toString(); 4246: } 4247: } // class UnmodifiableCollection 4248: 4249: /** 4250: * The implementation of the various iterator methods in the 4251: * unmodifiable classes. 4252: * 4253: * @author Eric Blake (ebb9@email.byu.edu) 4254: */ 4255: private static class UnmodifiableIterator implements Iterator 4256: { 4257: /** 4258: * The wrapped iterator. 4259: */ 4260: private final Iterator i; 4261: 4262: /** 4263: * Only trusted code creates a wrapper. 4264: * @param i the wrapped iterator 4265: */ 4266: UnmodifiableIterator(Iterator i) 4267: { 4268: this.i = i; 4269: } 4270: 4271: /** 4272: * Obtains the next element in the underlying collection. 4273: * 4274: * @return the next element in the collection. 4275: * @throws NoSuchElementException if there are no more elements. 4276: */ 4277: public Object next() 4278: { 4279: return i.next(); 4280: } 4281: /** 4282: * Tests whether there are still elements to be retrieved from the 4283: * underlying collection by <code>next()</code>. When this method 4284: * returns <code>true</code>, an exception will not be thrown on calling 4285: * <code>next()</code>. 4286: * 4287: * @return <code>true</code> if there is at least one more element in the underlying 4288: * collection. 4289: */ 4290: public boolean hasNext() 4291: { 4292: return i.hasNext(); 4293: } 4294: 4295: /** 4296: * Blocks the removal of elements from the underlying collection by the 4297: * iterator. 4298: * 4299: * @throws UnsupportedOperationException as an unmodifiable collection 4300: * does not support the removal of elements by its iterator. 4301: */ 4302: public void remove() 4303: { 4304: throw new UnsupportedOperationException(); 4305: } 4306: } // class UnmodifiableIterator 4307: 4308: /** 4309: * Returns an unmodifiable view of the given list. This allows 4310: * "read-only" access, although changes in the backing list show up 4311: * in this view. Attempts to modify the list directly, via iterators, or 4312: * via sublists, will fail with {@link UnsupportedOperationException}. 4313: * Although this view prevents changes to the structure of the list and 4314: * its elements, the values referenced by the objects in the list can 4315: * still be modified. 4316: * <p> 4317: * 4318: * The returned List implements Serializable, but can only be serialized if 4319: * the list it wraps is likewise Serializable. In addition, if the wrapped 4320: * list implements RandomAccess, this does too. 4321: * 4322: * @param l the list to wrap 4323: * @return a read-only view of the list 4324: * @see Serializable 4325: * @see RandomAccess 4326: */ 4327: public static List unmodifiableList(List l) 4328: { 4329: if (l instanceof RandomAccess) 4330: return new UnmodifiableRandomAccessList(l); 4331: return new UnmodifiableList(l); 4332: } 4333: 4334: /** 4335: * The implementation of {@link #unmodifiableList(List)} for sequential 4336: * lists. This class name is required for compatibility with Sun's JDK 4337: * serializability. 4338: * 4339: * @author Eric Blake (ebb9@email.byu.edu) 4340: */ 4341: private static class UnmodifiableList extends UnmodifiableCollection 4342: implements List 4343: { 4344: /** 4345: * Compatible with JDK 1.4. 4346: */ 4347: private static final long serialVersionUID = -283967356065247728L; 4348: 4349: 4350: /** 4351: * The wrapped list; stored both here and in the superclass to avoid 4352: * excessive casting. Package visible for use by subclass. 4353: * @serial the wrapped list 4354: */ 4355: final List list; 4356: 4357: /** 4358: * Wrap a given list. 4359: * @param l the list to wrap 4360: * @throws NullPointerException if l is null 4361: */ 4362: UnmodifiableList(List l) 4363: { 4364: super(l); 4365: list = l; 4366: } 4367: 4368: /** 4369: * Blocks the addition of an element to the underlying 4370: * list at a specific index. This method never returns, 4371: * throwing an exception instead. 4372: * 4373: * @param index The index at which to place the new element. 4374: * @param o the object to add. 4375: * @throws UnsupportedOperationException as an unmodifiable 4376: * list doesn't support the <code>add()</code> operation. 4377: */ 4378: public void add(int index, Object o) 4379: { 4380: throw new UnsupportedOperationException(); 4381: } 4382: 4383: /** 4384: * Blocks the addition of a collection of elements to the 4385: * underlying list at a specific index. This method never 4386: * returns, throwing an exception instead. 4387: * 4388: * @param index The index at which to place the new element. 4389: * @param c the collections of objects to add. 4390: * @throws UnsupportedOperationException as an unmodifiable 4391: * list doesn't support the <code>addAll()</code> operation. 4392: */ 4393: public boolean addAll(int index, Collection c) 4394: { 4395: throw new UnsupportedOperationException(); 4396: } 4397: 4398: /** 4399: * Returns <code>true</code> if the object, o, is an instance of 4400: * <code>List</code> with the same size and elements 4401: * as the underlying list. 4402: * 4403: * @param o The object to compare. 4404: * @return <code>true</code> if o is equivalent to the underlying list. 4405: */ 4406: public boolean equals(Object o) 4407: { 4408: return list.equals(o); 4409: } 4410: 4411: /** 4412: * Retrieves the element at a given index in the underlying list. 4413: * 4414: * @param index the index of the element to be returned 4415: * @return the element at index index in this list 4416: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 4417: */ 4418: public Object get(int index) 4419: { 4420: return list.get(index); 4421: } 4422: 4423: /** 4424: * Computes the hash code for the underlying list. 4425: * The exact computation is described in the documentation 4426: * of the <code>List</code> interface. 4427: * 4428: * @return The hash code of the underlying list. 4429: * @see List#hashCode() 4430: */ 4431: public int hashCode() 4432: { 4433: return list.hashCode(); 4434: } 4435: 4436: /** 4437: * Obtain the first index at which a given object is to be found in the 4438: * underlying list. 4439: * 4440: * @param o the object to search for 4441: * @return the least integer n such that <code>o == null ? get(n) == null : 4442: * o.equals(get(n))</code>, or -1 if there is no such index. 4443: * @throws ClassCastException if the type of o is not a valid 4444: * type for the underlying list. 4445: * @throws NullPointerException if o is null and the underlying 4446: * list does not support null values. 4447: */ 4448: public int indexOf(Object o) 4449: { 4450: return list.indexOf(o); 4451: } 4452: 4453: /** 4454: * Obtain the last index at which a given object is to be found in the 4455: * underlying list. 4456: * 4457: * @return the greatest integer n such that <code>o == null ? get(n) == null 4458: * : o.equals(get(n))</code>, or -1 if there is no such index. 4459: * @throws ClassCastException if the type of o is not a valid 4460: * type for the underlying list. 4461: * @throws NullPointerException if o is null and the underlying 4462: * list does not support null values. 4463: */ 4464: public int lastIndexOf(Object o) 4465: { 4466: return list.lastIndexOf(o); 4467: } 4468: 4469: /** 4470: * Obtains a list iterator over the underlying list, starting at the beginning 4471: * and maintaining the unmodifiable nature of this list. 4472: * 4473: * @return a <code>UnmodifiableListIterator</code> over the elements of the 4474: * underlying list, in order, starting at the beginning. 4475: */ 4476: public ListIterator listIterator() 4477: { 4478: return new UnmodifiableListIterator(list.listIterator()); 4479: } 4480: 4481: /** 4482: * Obtains a list iterator over the underlying list, starting at the specified 4483: * index and maintaining the unmodifiable nature of this list. An initial call 4484: * to <code>next()</code> will retrieve the element at the specified index, 4485: * and an initial call to <code>previous()</code> will retrieve the element 4486: * at index - 1. 4487: * 4488: * 4489: * @param index the position, between 0 and size() inclusive, to begin the 4490: * iteration from. 4491: * @return a <code>UnmodifiableListIterator</code> over the elements of the 4492: * underlying list, in order, starting at the specified index. 4493: * @throws IndexOutOfBoundsException if index < 0 || index > size() 4494: */ 4495: public ListIterator listIterator(int index) 4496: { 4497: return new UnmodifiableListIterator(list.listIterator(index)); 4498: } 4499: 4500: /** 4501: * Blocks the removal of the element at the specified index. 4502: * This method never returns, throwing an exception instead. 4503: * 4504: * @param index The index of the element to remove. 4505: * @return the removed element. 4506: * @throws UnsupportedOperationException as an unmodifiable 4507: * list does not support the <code>remove()</code> 4508: * operation. 4509: */ 4510: public Object remove(int index) 4511: { 4512: throw new UnsupportedOperationException(); 4513: } 4514: 4515: /** 4516: * Blocks the replacement of the element at the specified index. 4517: * This method never returns, throwing an exception instead. 4518: * 4519: * @param index The index of the element to replace. 4520: * @param o The new object to place at the specified index. 4521: * @return the replaced element. 4522: * @throws UnsupportedOperationException as an unmodifiable 4523: * list does not support the <code>set()</code> 4524: * operation. 4525: */ 4526: public Object set(int index, Object o) 4527: { 4528: throw new UnsupportedOperationException(); 4529: } 4530: 4531: /** 4532: * Obtain a List view of a subsection of the underlying list, from 4533: * fromIndex (inclusive) to toIndex (exclusive). If the two indices 4534: * are equal, the sublist is empty. The returned list will be 4535: * unmodifiable, like this list. Changes to the elements of the 4536: * returned list will be reflected in the underlying list. No structural 4537: * modifications can take place in either list. 4538: * 4539: * @param fromIndex the index that the returned list should start from 4540: * (inclusive). 4541: * @param toIndex the index that the returned list should go to (exclusive). 4542: * @return a List backed by a subsection of the underlying list. 4543: * @throws IndexOutOfBoundsException if fromIndex < 0 4544: * || toIndex > size() || fromIndex > toIndex. 4545: */ 4546: public List subList(int fromIndex, int toIndex) 4547: { 4548: return unmodifiableList(list.subList(fromIndex, toIndex)); 4549: } 4550: } // class UnmodifiableList 4551: 4552: /** 4553: * The implementation of {@link #unmodifiableList(List)} for random-access 4554: * lists. This class name is required for compatibility with Sun's JDK 4555: * serializability. 4556: * 4557: * @author Eric Blake (ebb9@email.byu.edu) 4558: */ 4559: private static final class UnmodifiableRandomAccessList 4560: extends UnmodifiableList implements RandomAccess 4561: { 4562: /** 4563: * Compatible with JDK 1.4. 4564: */ 4565: private static final long serialVersionUID = -2542308836966382001L; 4566: 4567: /** 4568: * Wrap a given list. 4569: * @param l the list to wrap 4570: * @throws NullPointerException if l is null 4571: */ 4572: UnmodifiableRandomAccessList(List l) 4573: { 4574: super(l); 4575: } 4576: } // class UnmodifiableRandomAccessList 4577: 4578: /** 4579: * The implementation of {@link UnmodifiableList#listIterator()}. 4580: * 4581: * @author Eric Blake (ebb9@email.byu.edu) 4582: */ 4583: private static final class UnmodifiableListIterator 4584: extends UnmodifiableIterator implements ListIterator 4585: { 4586: /** 4587: * The wrapped iterator, stored both here and in the superclass to 4588: * avoid excessive casting. 4589: */ 4590: private final ListIterator li; 4591: 4592: /** 4593: * Only trusted code creates a wrapper. 4594: * @param li the wrapped iterator 4595: */ 4596: UnmodifiableListIterator(ListIterator li) 4597: { 4598: super(li); 4599: this.li = li; 4600: } 4601: 4602: /** 4603: * Blocks the addition of an object to the list underlying this iterator. 4604: * This method never returns, throwing an exception instead. 4605: * 4606: * @param o The object to add. 4607: * @throws UnsupportedOperationException as the iterator of an unmodifiable 4608: * list does not support the <code>add()</code> operation. 4609: */ 4610: public void add(Object o) 4611: { 4612: throw new UnsupportedOperationException(); 4613: } 4614: 4615: /** 4616: * Tests whether there are still elements to be retrieved from the 4617: * underlying collection by <code>previous()</code>. When this method 4618: * returns <code>true</code>, an exception will not be thrown on calling 4619: * <code>previous()</code>. 4620: * 4621: * @return <code>true</code> if there is at least one more element prior to the 4622: * current position in the underlying list. 4623: */ 4624: public boolean hasPrevious() 4625: { 4626: return li.hasPrevious(); 4627: } 4628: 4629: /** 4630: * Find the index of the element that would be returned by a call to next. 4631: * If <code>hasNext()</code> returns <code>false</code>, this returns the list size. 4632: * 4633: * @return the index of the element that would be returned by 4634: * <code>next()</code>. 4635: */ 4636: public int nextIndex() 4637: { 4638: return li.nextIndex(); 4639: } 4640: 4641: /** 4642: * Obtains the previous element in the underlying list. 4643: * 4644: * @return the previous element in the list. 4645: * @throws NoSuchElementException if there are no more prior elements. 4646: */ 4647: public Object previous() 4648: { 4649: return li.previous(); 4650: } 4651: 4652: /** 4653: * Find the index of the element that would be returned by a call to 4654: * previous. If <code>hasPrevious()</code> returns <code>false</code>, 4655: * this returns -1. 4656: * 4657: * @return the index of the element that would be returned by 4658: * <code>previous()</code>. 4659: */ 4660: public int previousIndex() 4661: { 4662: return li.previousIndex(); 4663: } 4664: 4665: /** 4666: * Blocks the replacement of an element in the list underlying this 4667: * iterator. This method never returns, throwing an exception instead. 4668: * 4669: * @param o The new object to replace the existing one. 4670: * @throws UnsupportedOperationException as the iterator of an unmodifiable 4671: * list does not support the <code>set()</code> operation. 4672: */ 4673: public void set(Object o) 4674: { 4675: throw new UnsupportedOperationException(); 4676: } 4677: } // class UnmodifiableListIterator 4678: 4679: /** 4680: * Returns an unmodifiable view of the given map. This allows "read-only" 4681: * access, although changes in the backing map show up in this view. 4682: * Attempts to modify the map directly, or via collection views or their 4683: * iterators will fail with {@link UnsupportedOperationException}. 4684: * Although this view prevents changes to the structure of the map and its 4685: * entries, the values referenced by the objects in the map can still be 4686: * modified. 4687: * <p> 4688: * 4689: * The returned Map implements Serializable, but can only be serialized if 4690: * the map it wraps is likewise Serializable. 4691: * 4692: * @param m the map to wrap 4693: * @return a read-only view of the map 4694: * @see Serializable 4695: */ 4696: public static Map unmodifiableMap(Map m) 4697: { 4698: return new UnmodifiableMap(m); 4699: } 4700: 4701: /** 4702: * The implementation of {@link #unmodifiableMap(Map)}. This 4703: * class name is required for compatibility with Sun's JDK serializability. 4704: * 4705: * @author Eric Blake (ebb9@email.byu.edu) 4706: */ 4707: private static class UnmodifiableMap implements Map, Serializable 4708: { 4709: /** 4710: * Compatible with JDK 1.4. 4711: */ 4712: private static final long serialVersionUID = -1034234728574286014L; 4713: 4714: /** 4715: * The wrapped map. 4716: * @serial the real map 4717: */ 4718: private final Map m; 4719: 4720: /** 4721: * Cache the entry set. 4722: */ 4723: private transient Set entries; 4724: 4725: /** 4726: * Cache the key set. 4727: */ 4728: private transient Set keys; 4729: 4730: /** 4731: * Cache the value collection. 4732: */ 4733: private transient Collection values; 4734: 4735: /** 4736: * Wrap a given map. 4737: * @param m the map to wrap 4738: * @throws NullPointerException if m is null 4739: */ 4740: UnmodifiableMap(Map m) 4741: { 4742: this.m = m; 4743: if (m == null) 4744: throw new NullPointerException(); 4745: } 4746: 4747: /** 4748: * Blocks the clearing of entries from the underlying map. 4749: * This method never returns, throwing an exception instead. 4750: * 4751: * @throws UnsupportedOperationException as an unmodifiable 4752: * map does not support the <code>clear()</code> operation. 4753: */ 4754: public void clear() 4755: { 4756: throw new UnsupportedOperationException(); 4757: } 4758: 4759: /** 4760: * Returns <code>true</code> if the underlying map contains a mapping for 4761: * the given key. 4762: * 4763: * @param key the key to search for 4764: * @return <code>true</code> if the map contains the key 4765: * @throws ClassCastException if the key is of an inappropriate type 4766: * @throws NullPointerException if key is <code>null</code> but the map 4767: * does not permit null keys 4768: */ 4769: public boolean containsKey(Object key) 4770: { 4771: return m.containsKey(key); 4772: } 4773: 4774: /** 4775: * Returns <code>true</code> if the underlying map contains at least one mapping with 4776: * the given value. In other words, it returns <code>true</code> if a value v exists where 4777: * <code>(value == null ? v == null : value.equals(v))</code>. This usually 4778: * requires linear time. 4779: * 4780: * @param value the value to search for 4781: * @return <code>true</code> if the map contains the value 4782: * @throws ClassCastException if the type of the value is not a valid type 4783: * for this map. 4784: * @throws NullPointerException if the value is null and the map doesn't 4785: * support null values. 4786: */ 4787: public boolean containsValue(Object value) 4788: { 4789: return m.containsValue(value); 4790: } 4791: 4792: /** 4793: * Returns a unmodifiable set view of the entries in the underlying map. 4794: * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>. 4795: * The set is backed by the map, so that changes in one show up in the other. 4796: * Modifications made while an iterator is in progress cause undefined 4797: * behavior. These modifications are again limited to the values of 4798: * the objects. 4799: * 4800: * @return the unmodifiable set view of all mapping entries. 4801: * @see Map.Entry 4802: */ 4803: public Set entrySet() 4804: { 4805: if (entries == null) 4806: entries = new UnmodifiableEntrySet(m.entrySet()); 4807: return entries; 4808: } 4809: 4810: /** 4811: * The implementation of {@link UnmodifiableMap#entrySet()}. This class 4812: * name is required for compatibility with Sun's JDK serializability. 4813: * 4814: * @author Eric Blake (ebb9@email.byu.edu) 4815: */ 4816: private static final class UnmodifiableEntrySet extends UnmodifiableSet 4817: implements Serializable 4818: { 4819: /** 4820: * Compatible with JDK 1.4. 4821: */ 4822: private static final long serialVersionUID = 7854390611657943733L; 4823: 4824: /** 4825: * Wrap a given set. 4826: * @param s the set to wrap 4827: */ 4828: UnmodifiableEntrySet(Set s) 4829: { 4830: super(s); 4831: } 4832: 4833: // The iterator must return unmodifiable map entries. 4834: public Iterator iterator() 4835: { 4836: return new UnmodifiableIterator(c.iterator()) 4837: { 4838: /** 4839: * Obtains the next element from the underlying set of 4840: * map entries. 4841: * 4842: * @return the next element in the collection. 4843: * @throws NoSuchElementException if there are no more elements. 4844: */ 4845: public Object next() 4846: { 4847: final Map.Entry e = (Map.Entry) super.next(); 4848: return new Map.Entry() 4849: { 4850: /** 4851: * Returns <code>true</code> if the object, o, is also a map entry with an 4852: * identical key and value. 4853: * 4854: * @param o the object to compare. 4855: * @return <code>true</code> if o is an equivalent map entry. 4856: */ 4857: public boolean equals(Object o) 4858: { 4859: return e.equals(o); 4860: } 4861: 4862: /** 4863: * Returns the key of this map entry. 4864: * 4865: * @return the key. 4866: */ 4867: public Object getKey() 4868: { 4869: return e.getKey(); 4870: } 4871: 4872: /** 4873: * Returns the value of this map entry. 4874: * 4875: * @return the value. 4876: */ 4877: public Object getValue() 4878: { 4879: return e.getValue(); 4880: } 4881: 4882: /** 4883: * Computes the hash code of this map entry. 4884: * The computation is described in the <code>Map</code> 4885: * interface documentation. 4886: * 4887: * @return the hash code of this entry. 4888: * @see Map#hashCode() 4889: */ 4890: public int hashCode() 4891: { 4892: return e.hashCode(); 4893: } 4894: 4895: /** 4896: * Blocks the alteration of the value of this map entry. 4897: * This method never returns, throwing an exception instead. 4898: * 4899: * @param value The new value. 4900: * @throws UnsupportedOperationException as an unmodifiable 4901: * map entry does not support the <code>setValue()</code> 4902: * operation. 4903: */ 4904: public Object setValue(Object value) 4905: { 4906: throw new UnsupportedOperationException(); 4907: } 4908: 4909: /** 4910: * Returns a textual representation of the map entry. 4911: * 4912: * @return The map entry as a <code>String</code>. 4913: */ 4914: public String toString() 4915: { 4916: return e.toString(); 4917: } 4918: }; 4919: } 4920: }; 4921: } 4922: } // class UnmodifiableEntrySet 4923: 4924: /** 4925: * Returns <code>true</code> if the object, o, is also an instance 4926: * of <code>Map</code> with an equal set of map entries. 4927: * 4928: * @param o The object to compare. 4929: * @return <code>true</code> if o is an equivalent map. 4930: */ 4931: public boolean equals(Object o) 4932: { 4933: return m.equals(o); 4934: } 4935: 4936: /** 4937: * Returns the value associated with the supplied key or 4938: * null if no such mapping exists. An ambiguity can occur 4939: * if null values are accepted by the underlying map. 4940: * In this case, <code>containsKey()</code> can be used 4941: * to separate the two possible cases of a null result. 4942: * 4943: * @param key The key to look up. 4944: * @return the value associated with the key, or null if key not in map. 4945: * @throws ClassCastException if the key is an inappropriate type. 4946: * @throws NullPointerException if this map does not accept null keys. 4947: * @see #containsKey(Object) 4948: */ 4949: public Object get(Object key) 4950: { 4951: return m.get(key); 4952: } 4953: 4954: /** 4955: * Blocks the addition of a new entry to the underlying map. 4956: * This method never returns, throwing an exception instead. 4957: * 4958: * @param key The new key. 4959: * @param value The new value. 4960: * @return the previous value of the key, or null if there was no mapping. 4961: * @throws UnsupportedOperationException as an unmodifiable 4962: * map does not support the <code>put()</code> operation. 4963: */ 4964: public Object put(Object key, Object value) 4965: { 4966: throw new UnsupportedOperationException(); 4967: } 4968: 4969: /** 4970: * Computes the hash code for the underlying map, as the sum 4971: * of the hash codes of all entries. 4972: * 4973: * @return The hash code of the underlying map. 4974: * @see Map.Entry#hashCode() 4975: */ 4976: public int hashCode() 4977: { 4978: return m.hashCode(); 4979: } 4980: 4981: /** 4982: * Returns <code>true</code> if the underlying map contains no entries. 4983: * 4984: * @return <code>true</code> if the map is empty. 4985: */ 4986: public boolean isEmpty() 4987: { 4988: return m.isEmpty(); 4989: } 4990: 4991: /** 4992: * Returns a unmodifiable set view of the keys in the underlying map. 4993: * The set is backed by the map, so that changes in one show up in the other. 4994: * Modifications made while an iterator is in progress cause undefined 4995: * behavior. These modifications are again limited to the values of 4996: * the keys. 4997: * 4998: * @return the set view of all keys. 4999: */ 5000: public Set keySet() 5001: { 5002: if (keys == null) 5003: keys = new UnmodifiableSet(m.keySet()); 5004: return keys; 5005: } 5006: 5007: /** 5008: * Blocks the addition of the entries in the supplied map. 5009: * This method never returns, throwing an exception instead. 5010: * 5011: * @param m The map, the entries of which should be added 5012: * to the underlying map. 5013: * @throws UnsupportedOperationException as an unmodifiable 5014: * map does not support the <code>putAll</code> operation. 5015: */ 5016: public void putAll(Map m) 5017: { 5018: throw new UnsupportedOperationException(); 5019: } 5020: 5021: /** 5022: * Blocks the removal of an entry from the map. 5023: * This method never returns, throwing an exception instead. 5024: * 5025: * @param o The key of the entry to remove. 5026: * @return The value the key was associated with, or null 5027: * if no such mapping existed. Null is also returned 5028: * if the removed entry had a null key. 5029: * @throws UnsupportedOperationException as an unmodifiable 5030: * map does not support the <code>remove</code> operation. 5031: */ 5032: public Object remove(Object o) 5033: { 5034: throw new UnsupportedOperationException(); 5035: } 5036: 5037: 5038: /** 5039: * Returns the number of key-value mappings in the underlying map. 5040: * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE 5041: * is returned. 5042: * 5043: * @return the number of mappings. 5044: */ 5045: public int size() 5046: { 5047: return m.size(); 5048: } 5049: 5050: /** 5051: * Returns a textual representation of the map. 5052: * 5053: * @return The map in the form of a <code>String</code>. 5054: */ 5055: public String toString() 5056: { 5057: return m.toString(); 5058: } 5059: 5060: /** 5061: * Returns a unmodifiable collection view of the values in the underlying map. 5062: * The collection is backed by the map, so that changes in one show up in the other. 5063: * Modifications made while an iterator is in progress cause undefined 5064: * behavior. These modifications are again limited to the values of 5065: * the keys. 5066: * 5067: * @return the collection view of all values. 5068: */ 5069: public Collection values() 5070: { 5071: if (values == null) 5072: values = new UnmodifiableCollection(m.values()); 5073: return values; 5074: } 5075: } // class UnmodifiableMap 5076: 5077: /** 5078: * Returns an unmodifiable view of the given set. This allows 5079: * "read-only" access, although changes in the backing set show up 5080: * in this view. Attempts to modify the set directly or via iterators 5081: * will fail with {@link UnsupportedOperationException}. 5082: * Although this view prevents changes to the structure of the set and its 5083: * entries, the values referenced by the objects in the set can still be 5084: * modified. 5085: * <p> 5086: * 5087: * The returned Set implements Serializable, but can only be serialized if 5088: * the set it wraps is likewise Serializable. 5089: * 5090: * @param s the set to wrap 5091: * @return a read-only view of the set 5092: * @see Serializable 5093: */ 5094: public static Set unmodifiableSet(Set s) 5095: { 5096: return new UnmodifiableSet(s); 5097: } 5098: 5099: /** 5100: * The implementation of {@link #unmodifiableSet(Set)}. This class 5101: * name is required for compatibility with Sun's JDK serializability. 5102: * 5103: * @author Eric Blake (ebb9@email.byu.edu) 5104: */ 5105: private static class UnmodifiableSet extends UnmodifiableCollection 5106: implements Set 5107: { 5108: /** 5109: * Compatible with JDK 1.4. 5110: */ 5111: private static final long serialVersionUID = -9215047833775013803L; 5112: 5113: /** 5114: * Wrap a given set. 5115: * @param s the set to wrap 5116: * @throws NullPointerException if s is null 5117: */ 5118: UnmodifiableSet(Set s) 5119: { 5120: super(s); 5121: } 5122: 5123: /** 5124: * Returns <code>true</code> if the object, o, is also an instance of 5125: * <code>Set</code> of the same size and with the same entries. 5126: * 5127: * @return <code>true</code> if o is an equivalent set. 5128: */ 5129: public boolean equals(Object o) 5130: { 5131: return c.equals(o); 5132: } 5133: 5134: /** 5135: * Computes the hash code of this set, as the sum of the 5136: * hash codes of all elements within the set. 5137: * 5138: * @return the hash code of the set. 5139: */ 5140: public int hashCode() 5141: { 5142: return c.hashCode(); 5143: } 5144: } // class UnmodifiableSet 5145: 5146: /** 5147: * Returns an unmodifiable view of the given sorted map. This allows 5148: * "read-only" access, although changes in the backing map show up in this 5149: * view. Attempts to modify the map directly, via subviews, via collection 5150: * views, or iterators, will fail with {@link UnsupportedOperationException}. 5151: * Although this view prevents changes to the structure of the map and its 5152: * entries, the values referenced by the objects in the map can still be 5153: * modified. 5154: * <p> 5155: * 5156: * The returned SortedMap implements Serializable, but can only be 5157: * serialized if the map it wraps is likewise Serializable. 5158: * 5159: * @param m the map to wrap 5160: * @return a read-only view of the map 5161: * @see Serializable 5162: */ 5163: public static SortedMap unmodifiableSortedMap(SortedMap m) 5164: { 5165: return new UnmodifiableSortedMap(m); 5166: } 5167: 5168: /** 5169: * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This 5170: * class name is required for compatibility with Sun's JDK serializability. 5171: * 5172: * @author Eric Blake (ebb9@email.byu.edu) 5173: */ 5174: private static class UnmodifiableSortedMap extends UnmodifiableMap 5175: implements SortedMap 5176: { 5177: /** 5178: * Compatible with JDK 1.4. 5179: */ 5180: private static final long serialVersionUID = -8806743815996713206L; 5181: 5182: /** 5183: * The wrapped map; stored both here and in the superclass to avoid 5184: * excessive casting. 5185: * @serial the wrapped map 5186: */ 5187: private final SortedMap sm; 5188: 5189: /** 5190: * Wrap a given map. 5191: * @param sm the map to wrap 5192: * @throws NullPointerException if sm is null 5193: */ 5194: UnmodifiableSortedMap(SortedMap sm) 5195: { 5196: super(sm); 5197: this.sm = sm; 5198: } 5199: 5200: /** 5201: * Returns the comparator used in sorting the underlying map, 5202: * or null if it is the keys' natural ordering. 5203: * 5204: * @return the sorting comparator. 5205: */ 5206: public Comparator comparator() 5207: { 5208: return sm.comparator(); 5209: } 5210: 5211: /** 5212: * Returns the first (lowest sorted) key in the map. 5213: * 5214: * @return the first key. 5215: * @throws NoSuchElementException if this map is empty. 5216: */ 5217: public Object firstKey() 5218: { 5219: return sm.firstKey(); 5220: } 5221: 5222: /** 5223: * Returns a unmodifiable view of the portion of the map strictly less 5224: * than toKey. The view is backed by the underlying map, so changes in 5225: * one show up in the other. The submap supports all optional operations 5226: * of the original. This operation is equivalent to 5227: * <code>subMap(firstKey(), toKey)</code>. 5228: * <p> 5229: * 5230: * The returned map throws an IllegalArgumentException any time a key is 5231: * used which is out of the range of toKey. Note that the endpoint, toKey, 5232: * is not included; if you want this value to be included, pass its successor 5233: * object in to toKey. For example, for Integers, you could request 5234: * <code>headMap(new Integer(limit.intValue() + 1))</code>. 5235: * 5236: * @param toKey the exclusive upper range of the submap. 5237: * @return the submap. 5238: * @throws ClassCastException if toKey is not comparable to the map contents. 5239: * @throws IllegalArgumentException if this is a subMap, and toKey is out 5240: * of range. 5241: * @throws NullPointerException if toKey is null but the map does not allow 5242: * null keys. 5243: */ 5244: public SortedMap headMap(Object toKey) 5245: { 5246: return new UnmodifiableSortedMap(sm.headMap(toKey)); 5247: } 5248: 5249: /** 5250: * Returns the last (highest sorted) key in the map. 5251: * 5252: * @return the last key. 5253: * @throws NoSuchElementException if this map is empty. 5254: */ 5255: public Object lastKey() 5256: { 5257: return sm.lastKey(); 5258: } 5259: 5260: /** 5261: * Returns a unmodifiable view of the portion of the map greater than or 5262: * equal to fromKey, and strictly less than toKey. The view is backed by 5263: * the underlying map, so changes in one show up in the other. The submap 5264: * supports all optional operations of the original. 5265: * <p> 5266: * 5267: * The returned map throws an IllegalArgumentException any time a key is 5268: * used which is out of the range of fromKey and toKey. Note that the 5269: * lower endpoint is included, but the upper is not; if you want to 5270: * change the inclusion or exclusion of an endpoint, pass its successor 5271: * object in instead. For example, for Integers, you could request 5272: * <code>subMap(new Integer(lowlimit.intValue() + 1), 5273: * new Integer(highlimit.intValue() + 1))</code> to reverse 5274: * the inclusiveness of both endpoints. 5275: * 5276: * @param fromKey the inclusive lower range of the submap. 5277: * @param toKey the exclusive upper range of the submap. 5278: * @return the submap. 5279: * @throws ClassCastException if fromKey or toKey is not comparable to 5280: * the map contents. 5281: * @throws IllegalArgumentException if this is a subMap, and fromKey or 5282: * toKey is out of range. 5283: * @throws NullPointerException if fromKey or toKey is null but the map 5284: * does not allow null keys. 5285: */ 5286: public SortedMap subMap(Object fromKey, Object toKey) 5287: { 5288: return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey)); 5289: } 5290: 5291: /** 5292: * Returns a unmodifiable view of the portion of the map greater than or 5293: * equal to fromKey. The view is backed by the underlying map, so changes 5294: * in one show up in the other. The submap supports all optional operations 5295: * of the original. 5296: * <p> 5297: * 5298: * The returned map throws an IllegalArgumentException any time a key is 5299: * used which is out of the range of fromKey. Note that the endpoint, fromKey, is 5300: * included; if you do not want this value to be included, pass its successor object in 5301: * to fromKey. For example, for Integers, you could request 5302: * <code>tailMap(new Integer(limit.intValue() + 1))</code>. 5303: * 5304: * @param fromKey the inclusive lower range of the submap 5305: * @return the submap 5306: * @throws ClassCastException if fromKey is not comparable to the map 5307: * contents 5308: * @throws IllegalArgumentException if this is a subMap, and fromKey is out 5309: * of range 5310: * @throws NullPointerException if fromKey is null but the map does not allow 5311: * null keys 5312: */ 5313: public SortedMap tailMap(Object fromKey) 5314: { 5315: return new UnmodifiableSortedMap(sm.tailMap(fromKey)); 5316: } 5317: } // class UnmodifiableSortedMap 5318: 5319: /** 5320: * Returns an unmodifiable view of the given sorted set. This allows 5321: * "read-only" access, although changes in the backing set show up 5322: * in this view. Attempts to modify the set directly, via subsets, or via 5323: * iterators, will fail with {@link UnsupportedOperationException}. 5324: * Although this view prevents changes to the structure of the set and its 5325: * entries, the values referenced by the objects in the set can still be 5326: * modified. 5327: * <p> 5328: * 5329: * The returns SortedSet implements Serializable, but can only be 5330: * serialized if the set it wraps is likewise Serializable. 5331: * 5332: * @param s the set to wrap 5333: * @return a read-only view of the set 5334: * @see Serializable 5335: */ 5336: public static SortedSet unmodifiableSortedSet(SortedSet s) 5337: { 5338: return new UnmodifiableSortedSet(s); 5339: } 5340: 5341: /** 5342: * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This 5343: * class name is required for compatibility with Sun's JDK serializability. 5344: * 5345: * @author Eric Blake (ebb9@email.byu.edu) 5346: */ 5347: private static class UnmodifiableSortedSet extends UnmodifiableSet 5348: implements SortedSet 5349: { 5350: /** 5351: * Compatible with JDK 1.4. 5352: */ 5353: private static final long serialVersionUID = -4929149591599911165L; 5354: 5355: /** 5356: * The wrapped set; stored both here and in the superclass to avoid 5357: * excessive casting. 5358: * @serial the wrapped set 5359: */ 5360: private SortedSet ss; 5361: 5362: /** 5363: * Wrap a given set. 5364: * @param ss the set to wrap 5365: * @throws NullPointerException if ss is null 5366: */ 5367: UnmodifiableSortedSet(SortedSet ss) 5368: { 5369: super(ss); 5370: this.ss = ss; 5371: } 5372: 5373: /** 5374: * Returns the comparator used in sorting the underlying set, 5375: * or null if it is the elements' natural ordering. 5376: * 5377: * @return the sorting comparator 5378: */ 5379: public Comparator comparator() 5380: { 5381: return ss.comparator(); 5382: } 5383: 5384: /** 5385: * Returns the first (lowest sorted) element in the underlying 5386: * set. 5387: * 5388: * @return the first element. 5389: * @throws NoSuchElementException if the set is empty. 5390: */ 5391: public Object first() 5392: { 5393: return ss.first(); 5394: } 5395: 5396: /** 5397: * Returns a unmodifiable view of the portion of the set strictly 5398: * less than toElement. The view is backed by the underlying set, 5399: * so changes in one show up in the other. The subset supports 5400: * all optional operations of the original. This operation 5401: * is equivalent to <code>subSet(first(), toElement)</code>. 5402: * <p> 5403: * 5404: * The returned set throws an IllegalArgumentException any time an element is 5405: * used which is out of the range of toElement. Note that the endpoint, toElement, 5406: * is not included; if you want this value included, pass its successor object in to 5407: * toElement. For example, for Integers, you could request 5408: * <code>headSet(new Integer(limit.intValue() + 1))</code>. 5409: * 5410: * @param toElement the exclusive upper range of the subset 5411: * @return the subset. 5412: * @throws ClassCastException if toElement is not comparable to the set 5413: * contents. 5414: * @throws IllegalArgumentException if this is a subSet, and toElement is out 5415: * of range. 5416: * @throws NullPointerException if toElement is null but the set does not 5417: * allow null elements. 5418: */ 5419: public SortedSet headSet(Object toElement) 5420: { 5421: return new UnmodifiableSortedSet(ss.headSet(toElement)); 5422: } 5423: 5424: /** 5425: * Returns the last (highest sorted) element in the underlying 5426: * set. 5427: * 5428: * @return the last element. 5429: * @throws NoSuchElementException if the set is empty. 5430: */ 5431: public Object last() 5432: { 5433: return ss.last(); 5434: } 5435: 5436: /** 5437: * Returns a unmodifiable view of the portion of the set greater than or 5438: * equal to fromElement, and strictly less than toElement. The view is backed by 5439: * the underlying set, so changes in one show up in the other. The subset 5440: * supports all optional operations of the original. 5441: * <p> 5442: * 5443: * The returned set throws an IllegalArgumentException any time an element is 5444: * used which is out of the range of fromElement and toElement. Note that the 5445: * lower endpoint is included, but the upper is not; if you want to 5446: * change the inclusion or exclusion of an endpoint, pass its successor 5447: * object in instead. For example, for Integers, you can request 5448: * <code>subSet(new Integer(lowlimit.intValue() + 1), 5449: * new Integer(highlimit.intValue() + 1))</code> to reverse 5450: * the inclusiveness of both endpoints. 5451: * 5452: * @param fromElement the inclusive lower range of the subset. 5453: * @param toElement the exclusive upper range of the subset. 5454: * @return the subset. 5455: * @throws ClassCastException if fromElement or toElement is not comparable 5456: * to the set contents. 5457: * @throws IllegalArgumentException if this is a subSet, and fromElement or 5458: * toElement is out of range. 5459: * @throws NullPointerException if fromElement or toElement is null but the 5460: * set does not allow null elements. 5461: */ 5462: public SortedSet subSet(Object fromElement, Object toElement) 5463: { 5464: return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement)); 5465: } 5466: 5467: /** 5468: * Returns a unmodifiable view of the portion of the set greater than or equal to 5469: * fromElement. The view is backed by the underlying set, so changes in one show up 5470: * in the other. The subset supports all optional operations of the original. 5471: * <p> 5472: * 5473: * The returned set throws an IllegalArgumentException any time an element is 5474: * used which is out of the range of fromElement. Note that the endpoint, 5475: * fromElement, is included; if you do not want this value to be included, pass its 5476: * successor object in to fromElement. For example, for Integers, you could request 5477: * <code>tailSet(new Integer(limit.intValue() + 1))</code>. 5478: * 5479: * @param fromElement the inclusive lower range of the subset 5480: * @return the subset. 5481: * @throws ClassCastException if fromElement is not comparable to the set 5482: * contents. 5483: * @throws IllegalArgumentException if this is a subSet, and fromElement is 5484: * out of range. 5485: * @throws NullPointerException if fromElement is null but the set does not 5486: * allow null elements. 5487: */ 5488: public SortedSet tailSet(Object fromElement) 5489: { 5490: return new UnmodifiableSortedSet(ss.tailSet(fromElement)); 5491: } 5492: } // class UnmodifiableSortedSet 5493: } // class Collections
GNU Classpath (0.17) |