Collections drop from Classpath:

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of
	the bitset.
	(andNot): Likewise.
	(xor): Likewise.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/LinkedList.java (LinkedListItr.add): Don't skip the next
	entry.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/TreeMap.java (removeNode): Fix bug in node removal.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractCollection.java (containsAll): Use size of the
	correct collection for loop bound.
	* java/util/AbstractList.java (iterator.next): Increment pos after
	calling get on backing list.
	(listIterator.next): Likewise.
	* java/util/LinkedList.java (addLastEntry): Don't increment size before
	checking for size == 0.
	(addFirstEntry): Rearrange to match addLastEntry.
	(add): Do not increment size before inserting the new entry.

	* java/util/AbstractCollection.java (addAll): Use size of the
	correct collection for loop bound.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractSet.java (removeAll): Fix scoping thinko.
	* java/util/HashMap.java (putAllInternal): Set size here.
	* java/util/Hashtable.java (putAllInternal): New method. Copy contents
	of a map efficiently without calling put() or putAll().
	(Hashtable (map)): Use putAllInternal.
	(clone): Likewise.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/Collections.java:
	* java/util/Vector.java:
	* java/util/WeakHashMap.java: Fix spelling errors.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java (removeAllInternal),
	(retainAllInternal): Add hooks for use by ArrayList.
	* java/util/AbstractList.java: Minor code updates. Fix some
	scoping.
	* java/util/AbstractMap.java: ditto
	* java/util/ArrayList.java (readObject, writeObject): ditto
	(removeAllInternal, retainAllInternal): Optimize.
	* java/util/Arrays.java: ditto
	* java/util/Collections.java: ditto. Change order of parameters
	to equals(Object, Object) to match specs.
	* java/util/Dictionary.java: Improve javadoc.
	(Dictionary): Add explicit constructor.
	* java/util/HashMap.java: Improve javadoc. Rearrange methods to
	follow order in JDK. Cleanups related to recent code migration to
	AbstractMap. Fix some scoping.
	(entrySet): Cache the result.
	(modCount): Ensure that this is updated correctly.
	* java/util/HashSet.java: Improve javadoc. Fix some scoping.
	(init): Add hooks for LinkedHashSet.
	(map): Use "" instead of Boolean.TRUE in backing map. Use
	package-private API where possible for less overhead.
	(readObject, writeObject): Fix serialization.
	* java/util/Hashtable.java: Improve javadoc. Fix some scoping.
	(entrySet, keySet, values): Cache the result.
	(modCount): Ensure that this is updated correctly.
	(contains, remove): Fix NullPointer checking to match specs.
	(class Enumeration): Make more like HashIterator.
	* java/util/IdentityHashMap.java: Minor code updates.
	(modCount): Ensure that this is updated correctly.
	(readObject, writeObject): Fix serialization.
	* java/util/LinkedHashMap.java: Minor code updates. Cleanups
	related to recent code migration to AbstractMap.
	* java/util/LinkedHashSet.java: New file.
	* java/util/LinkedList.java:
	(readObject, writeObject): Fix serialization.
	* java/util/Makefile.am: List recently added files.
	* java/util/Stack.java: Minor code updates.
	* java/util/TreeMap.java: Improve javadoc. Overhaul the class to
	be more efficient. Fix some scoping. Rearrange the methods.
	(nil): Ensure that this can be thread-safe, and make it a static
	final. Initialize it to be more useful as a sentinal node.
	(Node): Specify color in constructor.
	(deleteFixup, insertFixup): Improve comments and algorithm.
	(fabricateTree): Redesign with less overhead.
	(lowestGreaterThan): Add parameter first to make SubMap easier.
	(removeNode): Patch hole where nil was being modified. Choose
	predecessor instead of successor so in-place swap works.
	(class VerifyResult, verifyTree, verifySub, verifyError): Remove
	this dead code after verifying the class works.
	(class SubMap): Rewrite several algorithms to avoid problems with
	comparing nil.
	* java/util/TreeSet.java: Improve javadoc. Fix some scoping.
	(clone): Fix ClassCastException when cloning subSet().
	(readObject, writeObject): Fix serialization.
	* java/util/WeakHashMap.java: Improve javadoc. Fix some scoping.
	(NULL_KEY): Make it compare as null, for ease elsewhere.
	(Class WeakEntry): Rename from Entry, to avoid shadowing
	Map.Entry. Add missing toString.
	(modCount): Ensure that this is updated correctly.
	(clear, containsValue, keySet, putAll, values, WeakHashMap(Map)):
	Add missing methods and constructor.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/ArrayList.java (checkBoundExclusive),
	(checkBoundInclusive): Rename from range??clusive, to match
	AbstractList.
	* java/util/LinkedList.java (checkBoundsExclusive),
	(checkBoundsInclusive): ditto
	* java/util/Vector.java (checkBoundExclusive),
	(checkBoundInclusive): Move bounds checking into common methods.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractList.java:
	(modCount): Make sure it is updated in all needed places.
	* java/util/ArrayList.java: Improve javadoc. Implements
	RandomAccess. Add serialVersionUID. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	(isEmpty): Add missing method.
	* java/util/Collections.java: (class SynchronizedList): Make
	package visible.
	* java/util/ConcurrentModificationException.java: Improve
	javadoc.
	* java/util/EmptyStackException.java: Improve javadoc.
	* java/util/LinkedList.java: Improve javadoc.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	* java/util/NoSuchElementException.java: Improve javadoc.
	* java/util/Stack.java: Improve javadoc. Fix synchronization
	issues.
	(modCount): Make sure it is updated in all needed places.
	* java/util/Vector.java: Improve javadoc. Fix synchronization
	issues. Implements RandomAccess. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(setSize): Fix according to specifications: this does not dictate
	the backing array size.
	(removeAll, retainAll): Faster implementations.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/BitSet.java: Improve javadoc.
	(cardinality(), clear(), clear(int, int), flip(int)),
	(flip(int, int), get(int, int), intersects(BitSet), isEmpty()),
	(nextClearBit(int), nextSetBit(int), set(int, boolean)),
	(set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods.
	(clone): Fix so subclasses clone correctly.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java: Improve javadoc.
	(AbstractCollection()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	* java/util/AbstractList.java: Improve javadoc.
	(AbstractList()): Make constructor protected.
	(indexOf(Object)): Call listIterator(), not listIterator(int).
	(iterator()): Follow Sun's requirement to not use listIterator(0).
	(listIterator(int)): Make AbstractListItr anonymous.
	(subList(int, int)): Add support for RandomAccess.
	(SubList.add(int, Object), SubList.remove(Object)): Fix bug with
	modCount tracking.
	(SubList.addAll(Collection)): Add missing method.
	(SubList.listIterator(int)): Fix bugs in indexing, modCount
	tracking.
	(class RandomAccessSubList): Add new class.
	* java/util/AbstractMap.java: Improve javadoc.
	(keys, values, KEYS, VALUES, ENTRIES): Consolidate common map
	fields.
	(AbstractMap()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	(equals(Object)): Change algorithm to
	entrySet().equals(m.entrySet()), as documented by Sun.
	(keySet(), values()): Cache the collections.
	* java/util/AbstractSequentialList.java: Improve javadoc.
	(AbstractSequentialList()): Make constructor protected.
	* java/util/AbstractSet.java: Improve javadoc.
	(AbstractSet()): Make constructor protected.
	(removeAll(Collection)): Add missing method.
	* java/util/Arrays.java: Improve javadoc, rearrange method orders.
	(defaultComparator): Remove, in favor of
	Collections.compare(Object, Object, Comparator).
	(binarySearch, equals, sort): Fix natural order comparison of
	floats and doubles. Also improve Object comparison - when
	comparator is null, use natural order.
	(fill, sort): Add missing checks for IllegalArgumentException.
	(sort, qsort): Fix sorting bugs, rework the code for more
	legibility.
	(mergeSort): Inline into sort(Object[], int, int, Comparator).
	(class ArrayList): Rename from ListImpl, and make compatible with
	JDK serialization. Add methods which more efficiently override
	those of AbstractList.
	* java/util/Collections: Improve javadoc.
	(isSequential(List)): Add and use a method for deciding between
	RandomAccess and sequential algorithms on lists.
	(class Empty*, class Synchronized*, class Unmodifiable*): Make
	compliant with JDK serializability.
	(class Singleton*, class CopiesList, class RevereseComparator),
	(class UnmodifiableMap.UnmodifiableEntrySet),
	(class *RandomAccessList): New classes for serial compatibility.
	(class Empty*, class Singleton*, class CopiesList): Add methods
	which more efficiently override those of Abstract*.
	(search): Inline into binarySearch(List, Object, Comparator).
	(binarySearch): Make sequential search only do log(n) comparisons,
	instead of n.
	(copy(List, List)): Do bounds checking before starting.
	(indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate),
	(swap):	Add new JDK 1.4 methods.
	(binarySearch, max, min, sort): Allow null comparator to represent
	natural ordering.
	(reverse(List)): Avoid unnecessary swap.
	(shuffle(List, Random)): Do shuffle in-place for RandomAccess
	lists.
	(SingletonList.get): Fix logic bug.
	(SingletonMap.entrySet): Make the entry immutable, and cache the
	returned set.
	(SynchronizedCollection, SynchronizedMap, UnmodifiableCollection),
	(UnmodifiableMap): Detect null pointer in construction.
	(SynchronizedMap, UnmodifiableMap): Cache collection views.
	* java/util/BasicMapEntry: Improve javadoc.

From-SVN: r48035

1 files changed, 2658 insertions, 1057 deletions

diff --git a/libjava/java/util/Collections.java b/libjava/java/util/Collections.java
index 8e77a80..2f54502 100644
--- a/libjava/java/util/Collections.java
+++ b/libjava/java/util/Collections.java
@@ -25,10 +25,6 @@ This exception does not however invalidate any other reasons why the
 executable file might be covered by the GNU General Public License. */
 
 
-// TO DO:
-// ~ Serialization is very much broken. Blame Sun for not specifying it.
-// ~ The synchronized* and unmodifiable* methods don't have doc-comments.
-
 package java.util;
 
 import java.io.Serializable;
@@ -40,10 +36,55 @@ import java.io.Serializable;
  * are unaware of collections, a method to return a list which consists of
  * multiple copies of one element, and methods which "wrap" collections to give
  * them extra properties, such as thread-safety and unmodifiability.
+ * <p>
+ *
+ * All methods which take a collection throw a {@link NullPointerException} if
+ * that collection is null. Algorithms which can change a collection may, but
+ * are not required, to throw the {@link UnsupportedOperationException} that
+ * the underlying collection would throw during an attempt at modification.
+ * For example,
+ * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)<code>
+ * does not throw a exception, even though addAll is an unsupported operation
+ * on a singleton; the reason for this is that addAll did not attempt to
+ * modify the set.
+ *
+ * @author Original author unknown
+ * @author Bryce McKinlay
+ * @author Eric Blake <ebb9@email.byu.edu>
+ * @see Collection
+ * @see Set
+ * @see List
+ * @see Map
+ * @see Arrays
+ * @since 1.2
+ * @status updated to 1.4
  */
 public class Collections
 {
   /**
+   * Constant used to decide cutoff for when a non-RandomAccess list should
+   * be treated as sequential-access. Basically, quadratic behavior is
+   * acceptible for small lists when the overhead is so small in the first
+   * place. I arbitrarily set it to 16, so it may need some tuning.
+   */
+  private static final int LARGE_LIST_SIZE = 16;
+
+  /**
+   * Determines if a list should be treated as a sequential-access one.
+   * Rather than the old method of JDK 1.3 of assuming only instanceof
+   * AbstractSequentialList should be sequential, this uses the new method
+   * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
+   * and exceeds a large (unspecified) size should be sequential.
+   *
+   * @param l the list to check
+   * @return true if it should be treated as sequential-access
+   */
+  private static boolean isSequential(List l)
+  {
+    return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
+  }
+
+  /**
    * This class is non-instantiable.
    */
   private Collections()
@@ -51,200 +92,288 @@ public class Collections
   }
 
   /**
-   * An immutable, empty Set.
-   * Note: This implementation isn't Serializable, although it should be by the
-   * spec.
+   * An immutable, serializable, empty Set.
+   * @see Serializable
    */
-  public static final Set EMPTY_SET = new AbstractSet()
+  public static final Set EMPTY_SET = new EmptySet();
+
+  private static final Iterator EMPTY_ITERATOR = new Iterator()
+    {
+      public boolean hasNext()
+      {
+	return false;
+      }
+
+      public Object next()
+      {
+	throw new NoSuchElementException();
+      }
+
+      public void remove()
+      {
+	throw new UnsupportedOperationException();
+      }
+    };
+
+  /**
+   * The implementation of {@link #EMPTY_SET}. This class name is required
+   * for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class EmptySet extends AbstractSet
+    implements Serializable
   {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 1582296315990362920L;
+
+    /**
+     * A private constructor adds overhead.
+     */
+    EmptySet()
+    {
+    }
+
+    /**
+     * The size: always 0!
+     */
     public int size()
     {
       return 0;
     }
 
-    // This is really cheating! I think it's perfectly valid, though - the
-    // more conventional code is here, commented out, in case anyone disagrees.
+    /**
+     * Returns an iterator that does not iterate.
+     */
     public Iterator iterator()
     {
-      return EMPTY_LIST.iterator();
+      return EMPTY_ITERATOR;
     }
+  } // class EmptySet
 
-    // public Iterator iterator() {
-    //   return new Iterator() {
-    // 
-    //     public boolean hasNext() {
-    //       return false;
-    //     }
-    // 
-    //     public Object next() {
-    //       throw new NoSuchElementException();
-    //     }
-    // 
-    //     public void remove() {
-    //       throw new UnsupportedOperationException();
-    //     }
-    //   };
-    // }
-
-  };
+  /**
+   * An immutable, serializable, empty List, which implements RandomAccess.
+   * @see Serializable
+   * @see RandomAccess
+   */
+  public static final List EMPTY_LIST = new EmptyList();
 
   /**
-   * An immutable, empty List.
-   * Note: This implementation isn't serializable, although it should be by the
-   * spec.
+   * The implementation of {@link #EMPTY_LIST}. This class name is required
+   * for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
    */
-  public static final List EMPTY_LIST = new AbstractList()
+  private static final class EmptyList extends AbstractList
+    implements Serializable, RandomAccess
   {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 8842843931221139166L;
+
+    /**
+     * A private constructor adds overhead.
+     */
+    EmptyList()
+    {
+    }
+
+    /**
+     * The size is always 0.
+     */
     public int size()
     {
       return 0;
     }
 
+    /**
+     * No matter the index, it is out of bounds.
+     */
     public Object get(int index)
     {
       throw new IndexOutOfBoundsException();
     }
-  };
+    
+    /**
+     * Returns an iterator that does not iterate. Optional, but avoids 
+     * allocation of an iterator in AbstractList.
+     */
+    public Iterator iterator()
+    {
+      return EMPTY_ITERATOR;
+    }    
+  } // class EmptyList
+
+  /**
+   * An immutable, serializable, empty Map.
+   * @see Serializable
+   */
+  public static final Map EMPTY_MAP = new EmptyMap();
 
   /**
-   * An immutable, empty Map.
-   * Note: This implementation isn't serializable, although it should be by the
-   * spec.
+   * The implementation of {@link #EMPTY_MAP}. This class name is required
+   * for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
    */
-  public static final Map EMPTY_MAP = new AbstractMap()
+  private static final class EmptyMap extends AbstractMap
+    implements Serializable
   {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 6428348081105594320L;
+
+    /**
+     * A private constructor adds overhead.
+     */
+    EmptyMap()
+    {
+    }
+
+    /**
+     * There are no entries.
+     */
     public Set entrySet()
     {
       return EMPTY_SET;
     }
-  };
+
+    /**
+     * Size is always 0.
+     */
+    public int size()
+    {
+      return 0;
+    }
+
+    /**
+     * No entries. Technically, EMPTY_SET, while more specific than a general
+     * Collection, will work. Besides, that's what the JDK uses!
+     */
+    public Collection values()
+    {
+      return EMPTY_SET;
+    }
+  } // class EmptyMap
 
   /**
    * Compare two objects with or without a Comparator. If c is null, uses the
    * natural ordering. Slightly slower than doing it inline if the JVM isn't
    * clever, but worth it for removing a duplicate of the search code.
-   * Note: This same code is used in Arrays (for sort as well as search)
+   * Note: This code is also used in Arrays (for sort as well as search).
    */
-  private static int compare(Object o1, Object o2, Comparator c)
+  static final int compare(Object o1, Object o2, Comparator c)
   {
-    if (c == null)
-      {
-	return ((Comparable) o1).compareTo(o2);
-      }
-    else
-      {
-	return c.compare(o1, o2);
-      }
-  }
-
-  /**
-   * The hard work for the search routines. If the Comparator given is null,
-   * uses the natural ordering of the elements.
-   */
-  private static int search(List l, Object key, final Comparator c)
-  {
-    int pos = 0;
-
-    // We use a linear search using an iterator if we can guess that the list
-    // is sequential-access.
-    if (l instanceof AbstractSequentialList)
-      {
-	ListIterator itr = l.listIterator();
-    	for (int i = l.size() - 1; i >= 0; --i)
-	  {
-	    final int d = compare(key, itr.next(), c);
-	    if (d == 0)
-	      {
-		return pos;
-	      }
-	    else if (d < 0)
-	      {
-		return -pos - 1;
-	      }
-	    pos++;
-	  }
-
-	// We assume the list is random-access, and use a binary search
-      }
-    else
-      {
-	int low = 0;
-	int hi = l.size() - 1;
-	while (low <= hi)
-	  {
-	    pos = (low + hi) >> 1;
-	    final int d = compare(key, l.get(pos), c);
-	    if (d == 0)
-	      {
-		return pos;
-	      }
-	    else if (d < 0)
-	      {
-		hi = pos - 1;
-	      }
-	    else
-	      {
-		low = ++pos;	// This gets the insertion point right on the last loop
-	      }
-	  }
-      }
-
-    // If we failed to find it, we do the same whichever search we did.
-    return -pos - 1;
+    return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
   }
 
   /**
    * Perform a binary search of a List for a key, using the natural ordering of
    * the elements. The list must be sorted (as by the sort() method) - if it is
-   * not, the behaviour of this method is undefined, and may be an infinite
+   * not, the behavior of this method is undefined, and may be an infinite
    * loop. Further, the key must be comparable with every item in the list. If
-   * the list contains the key more than once, any one of them may be found. To
-   * avoid pathological behaviour on sequential-access lists, a linear search
-   * is used if (l instanceof AbstractSequentialList). Note: although the
+   * the list contains the key more than once, any one of them may be found.
+   * <p>
+   *
+   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
+   * and uses a linear search with O(n) link traversals and log(n) comparisons
+   * with {@link AbstractSequentialList} lists. Note: although the
    * specification allows for an infinite loop if the list is unsorted, it will
    * not happen in this (Classpath) implementation.
    *
    * @param l the list to search (must be sorted)
    * @param key the value to search for
-   * @returns the index at which the key was found, or -n-1 if it was not
-   *   found, where n is the index of the first value higher than key or
-   *   a.length if there is no such value.
-   * @exception ClassCastException if key could not be compared with one of the
-   *   elements of l
-   * @exception NullPointerException if a null element has compareTo called
+   * @return the index at which the key was found, or -n-1 if it was not
+   *         found, where n is the index of the first value higher than key or
+   *         a.length if there is no such value
+   * @throws ClassCastException if key could not be compared with one of the
+   *         elements of l
+   * @throws NullPointerException if a null element has compareTo called
+   * @see #sort(List)
    */
   public static int binarySearch(List l, Object key)
   {
-    return search(l, key, null);
+    return binarySearch(l, key, null);
   }
 
   /**
    * Perform a binary search of a List for a key, using a supplied Comparator.
    * The list must be sorted (as by the sort() method with the same Comparator)
-   * - if it is not, the behaviour of this method is undefined, and may be an
+   * - if it is not, the behavior of this method is undefined, and may be an
    * infinite loop. Further, the key must be comparable with every item in the
    * list. If the list contains the key more than once, any one of them may be
-   * found. To avoid pathological behaviour on sequential-access lists, a
-   * linear search is used if (l instanceof AbstractSequentialList). Note:
-   * although the specification allows for an infinite loop if the list is
-   * unsorted, it will not happen in this (Classpath) implementation.
+   * found. If the comparator is null, the elements' natural ordering is used.
+   * <p>
+   *
+   * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
+   * and uses a linear search with O(n) link traversals and log(n) comparisons
+   * with {@link AbstractSequentialList} lists. Note: although the
+   * specification allows for an infinite loop if the list is unsorted, it will
+   * not happen in this (Classpath) implementation.
    *
    * @param l the list to search (must be sorted)
    * @param key the value to search for
    * @param c the comparator by which the list is sorted
-   * @returns the index at which the key was found, or -n-1 if it was not
-   *   found, where n is the index of the first value higher than key or
-   *   a.length if there is no such value.
-   * @exception ClassCastException if key could not be compared with one of the
-   *   elements of l
+   * @return the index at which the key was found, or -n-1 if it was not
+   *         found, where n is the index of the first value higher than key or
+   *         a.length if there is no such value
+   * @throws ClassCastException if key could not be compared with one of the
+   *         elements of l
+   * @throws NullPointerException if a null element is compared with natural
+   *         ordering (only possible when c is null)
+   * @see #sort(List, Comparator)
    */
   public static int binarySearch(List l, Object key, Comparator c)
   {
-    if (c == null)
+    int pos = 0;
+    int low = 0;
+    int hi = l.size() - 1;
+
+    // We use a linear search with log(n) comparisons using an iterator
+    // if the list is sequential-access.
+    if (isSequential(l))
       {
-	throw new NullPointerException();
+	ListIterator itr = l.listIterator();
+        int i = 0;
+        while (low <= hi)
+          {
+            pos = (low + hi) >> 1;
+            if (i < pos)
+              for ( ; i != pos; i++, itr.next());
+            else
+              for ( ; i != pos; i--, itr.previous());
+	    final int d = compare(key, itr.next(), c);
+	    if (d == 0)
+              return pos;
+	    else if (d < 0)
+              hi = pos - 1;
+	    else
+              // This gets the insertion point right on the last loop
+              low = ++pos;
+          }
+      }
+    else
+      {
+	while (low <= hi)
+	  {
+	    pos = (low + hi) >> 1;
+	    final int d = compare(key, l.get(pos), c);
+	    if (d == 0)
+              return pos;
+	    else if (d < 0)
+              hi = pos - 1;
+	    else
+              // This gets the insertion point right on the last loop
+              low = ++pos;
+	  }
       }
-    return search(l, key, c);
+
+    // If we failed to find it, we do the same whichever search we did.
+    return -pos - 1;
   }
 
   /**
@@ -252,30 +381,26 @@ public class Collections
    * source list, the remaining elements are unaffected. This method runs in
    * linear time.
    *
-   * @param dest the destination list.
-   * @param source the source list.
-   * @exception IndexOutOfBoundsException if the destination list is shorter
-   *   than the source list (the elements that can be copied will be, prior to
-   *   the exception being thrown).
-   * @exception UnsupportedOperationException if dest.listIterator() does not
-   *   support the set operation.
+   * @param dest the destination list
+   * @param source the source list
+   * @throws IndexOutOfBoundsException if the destination list is shorter
+   *         than the source list (the destination will be unmodified)
+   * @throws UnsupportedOperationException if dest.listIterator() does not
+   *         support the set operation
    */
   public static void copy(List dest, List source)
   {
+    int pos = source.size();
+    if (dest.size() < pos)
+      throw new IndexOutOfBoundsException("Source does not fit in dest");
+
     Iterator i1 = source.iterator();
     ListIterator i2 = dest.listIterator();
 
-    try
+    while (--pos >= 0)
       {
-	for (int i = source.size() - 1; i >= 0; --i)
-	  {
-	    i2.next();
-	    i2.set(i1.next());
-	  }
-      }
-    catch (NoSuchElementException x)
-      {
-	throw new IndexOutOfBoundsException("Source doesn't fit in dest.");      
+        i2.next();
+        i2.set(i1.next());
       }
   }
 
@@ -284,7 +409,7 @@ public class Collections
    * with legacy APIs that require an Enumeration as input.
    *
    * @param c the Collection to iterate over
-   * @returns an Enumeration backed by an Iterator over c
+   * @return an Enumeration backed by an Iterator over c
    */
   public static Enumeration enumeration(Collection c)
   {
@@ -308,8 +433,8 @@ public class Collections
    *
    * @param l the list to fill.
    * @param val the object to vill the list with.
-   * @exception UnsupportedOperationException if l.listIterator() does not
-   *   support the set operation.
+   * @throws UnsupportedOperationException if l.listIterator() does not
+   *         support the set operation.
    */
   public static void fill(List l, Object val)
   {
@@ -322,30 +447,81 @@ public class Collections
   }
 
   /**
+   * Returns the starting index where the specified sublist first occurs
+   * in a larger list, or -1 if there is no matching position. If
+   * <code>target.size() &gt; source.size()</code>, this returns -1,
+   * otherwise this implementation uses brute force, checking for
+   * <code>source.sublist(i, i + target.size()).equals(target)</code>
+   * for all possible i.
+   *
+   * @param source the list to search
+   * @param target the sublist to search for
+   * @return the index where found, or -1
+   * @since 1.4
+   */
+  public static int indexOfSubList(List source, List target)
+  {
+    int ssize = source.size();
+    for (int i = 0, j = target.size(); j <= ssize; i++, j++)
+      if (source.subList(i, j).equals(target))
+        return i;
+    return -1;
+  }
+
+  /**
+   * Returns the starting index where the specified sublist last occurs
+   * in a larger list, or -1 if there is no matching position. If
+   * <code>target.size() &gt; source.size()</code>, this returns -1,
+   * otherwise this implementation uses brute force, checking for
+   * <code>source.sublist(i, i + target.size()).equals(target)</code>
+   * for all possible i.
+   *
+   * @param source the list to search
+   * @param target the sublist to search for
+   * @return the index where found, or -1
+   * @since 1.4
+   */
+  public static int lastIndexOfSubList(List source, List target)
+  {
+    int ssize = source.size();
+    for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--)
+      if (source.subList(i, j).equals(target))
+        return i;
+    return -1;
+  }
+
+  /**
+   * Returns an array list holding the elements visited by a given
+   * Enumeration. This method exists for interoperability between legacy
+   * APIs and the new Collection API.
+   *
+   * @param e the enumeration to put in a list
+   * @return a list containing the enumeration elements
+   * @see ArrayList
+   * @since 1.4
+   */
+  public static List list(Enumeration e)
+  {
+    List l = new ArrayList();
+    while (e.hasMoreElements())
+      l.add(e.nextElement());
+    return l;
+  }
+
+  /**
    * Find the maximum element in a Collection, according to the natural
    * ordering of the elements. This implementation iterates over the
    * Collection, so it works in linear time.
    *
    * @param c the Collection to find the maximum element of
-   * @returns the maximum element of c
+   * @return the maximum element of c
    * @exception NoSuchElementException if c is empty
    * @exception ClassCastException if elements in c are not mutually comparable
    * @exception NullPointerException if null.compareTo is called
    */
   public static Object max(Collection c)
   {
-    Iterator itr = c.iterator();
-    Comparable max = (Comparable) itr.next();	// throws NoSuchElementException
-    int csize = c.size();
-    for (int i = 1; i < csize; i++)
-      {
-	Object o = itr.next();
-	if (max.compareTo(o) < 0)
-	  {
-	    max = (Comparable) o;
-	  }
-      }
-    return max;
+    return max(c, null);
   }
 
   /**
@@ -354,20 +530,23 @@ public class Collections
    * works in linear time.
    *
    * @param c the Collection to find the maximum element of
-   * @param order the Comparator to order the elements by
-   * @returns the maximum element of c
-   * @exception NoSuchElementException if c is empty
-   * @exception ClassCastException if elements in c are not mutually comparable
+   * @param order the Comparator to order the elements by, or null for natural
+   *        ordering
+   * @return the maximum element of c
+   * @throws NoSuchElementException if c is empty
+   * @throws ClassCastException if elements in c are not mutually comparable
+   * @throws NullPointerException if null is compared by natural ordering
+   *        (only possible when order is null)
    */
   public static Object max(Collection c, Comparator order)
   {
     Iterator itr = c.iterator();
-    Object max = itr.next();	// throws NoSuchElementException
+    Object max = itr.next(); // throws NoSuchElementException
     int csize = c.size();
     for (int i = 1; i < csize; i++)
       {
 	Object o = itr.next();
-	if (order.compare(max, o) < 0)
+	if (compare(max, o, order) < 0)
 	  max = o;
       }
     return max;
@@ -379,23 +558,14 @@ public class Collections
    * Collection, so it works in linear time.
    *
    * @param c the Collection to find the minimum element of
-   * @returns the minimum element of c
-   * @exception NoSuchElementException if c is empty
-   * @exception ClassCastException if elements in c are not mutually comparable
-   * @exception NullPointerException if null.compareTo is called
+   * @return the minimum element of c
+   * @throws NoSuchElementException if c is empty
+   * @throws ClassCastException if elements in c are not mutually comparable
+   * @throws NullPointerException if null.compareTo is called
    */
   public static Object min(Collection c)
   {
-    Iterator itr = c.iterator();
-    Comparable min = (Comparable) itr.next();	// throws NoSuchElementException
-    int csize = c.size();
-    for (int i = 1; i < csize; i++)
-      {
-	Object o = itr.next();
-	if (min.compareTo(o) > 0)
-	  min = (Comparable) o;
-      }
-    return min;
+    return min(c, null);
   }
 
   /**
@@ -404,10 +574,13 @@ public class Collections
    * works in linear time.
    *
    * @param c the Collection to find the minimum element of
-   * @param order the Comparator to order the elements by
-   * @returns the minimum element of c
-   * @exception NoSuchElementException if c is empty
-   * @exception ClassCastException if elements in c are not mutually comparable
+   * @param order the Comparator to order the elements by, or null for natural
+   *        ordering
+   * @return the minimum element of c
+   * @throws NoSuchElementException if c is empty
+   * @throws ClassCastException if elements in c are not mutually comparable
+   * @throws NullPointerException if null is compared by natural ordering
+   *        (only possible when order is null)
    */
   public static Object min(Collection c, Comparator order)
   {
@@ -417,7 +590,7 @@ public class Collections
     for (int i = 1; i < csize; i++)
       {
 	Object o = itr.next();
-	if (order.compare(min, o) > 0)
+	if (compare(min, o, order) > 0)
 	  min = o;
       }
     return min;
@@ -426,54 +599,182 @@ public class Collections
   /**
    * Creates an immutable list consisting of the same object repeated n times.
    * The returned object is tiny, consisting of only a single reference to the
-   * object and a count of the number of elements. It is Serializable.
+   * object and a count of the number of elements. It is Serializable, and
+   * implements RandomAccess. You can use it in tandem with List.addAll for
+   * fast list construction.
    *
    * @param n the number of times to repeat the object
    * @param o the object to repeat
-   * @returns a List consisting of n copies of o
-   * @throws IllegalArgumentException if n < 0
+   * @return a List consisting of n copies of o
+   * @throws IllegalArgumentException if n &lt; 0
+   * @see List#addAll(Collection)
+   * @see Serializable
+   * @see RandomAccess
    */
-  // It's not Serializable, because the serialized form is unspecced.
-  // Also I'm only assuming that it should be because I don't think it's
-  // stated - I just would be amazed if it isn't...
   public static List nCopies(final int n, final Object o)
   {
-    // Check for insane arguments
-    if (n < 0)
-      {
+    return new CopiesList(n, o);
+  }
+
+  /**
+   * The implementation of {@link #nCopies(int, Object)}. This class name
+   * is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class CopiesList extends AbstractList
+    implements Serializable, RandomAccess
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 2739099268398711800L;
+
+    /**
+     * The count of elements in this list.
+     * @serial the list size
+     */
+    private final int n;
+
+    /**
+     * The repeated list element.
+     * @serial the list contents
+     */
+    private final Object element;
+
+    /**
+     * Constructs the list.
+     *
+     * @param n the count
+     * @param o the object
+     * @throws IllegalArgumentException if n &lt; 0
+     */
+    CopiesList(int n, Object o)
+    {
+      if (n < 0)
 	throw new IllegalArgumentException();
-      }
+      this.n = n;
+      element = o;
+    }
 
-    // Create a minimal implementation of List
-    return new AbstractList()
+    /**
+     * The size is fixed.
+     */
+    public int size()
     {
-      public int size()
-      {
-	return n;
-      }
+      return n;
+    }
 
-      public Object get(int index)
-      {
-	if (index < 0 || index >= n)
-	  {
-	    throw new IndexOutOfBoundsException();
-	  }
-	return o;
-      }
-    };
+    /**
+     * The same element is returned.
+     */
+    public Object get(int index)
+    {
+      if (index < 0 || index >= n)
+        throw new IndexOutOfBoundsException();
+      return element;
+    }
+
+    // The remaining methods are optional, but provide a performance
+    // advantage by not allocating unnecessary iterators in AbstractList.
+    /**
+     * This list only contains one element.
+     */
+    public boolean contains(Object o)
+    {
+      return n > 0 && equals(o, element);
+    }
+
+    /**
+     * The index is either 0 or -1.
+     */
+    public int indexOf(Object o)
+    {
+      return (n > 0 && equals(o, element)) ? 0 : -1;
+    }
+
+    /**
+     * The index is either n-1 or -1.
+     */
+    public int lastIndexOf(Object o)
+    {
+      return equals(o, element) ? n - 1 : -1;
+    }
+
+    /**
+     * A subList is just another CopiesList.
+     */
+    public List subList(int from, int to)
+    {
+      if (from < 0 || to > n)
+        throw new IndexOutOfBoundsException();
+      return new CopiesList(to - from, element);
+    }
+
+    /**
+     * The array is easy.
+     */
+    public Object[] toArray()
+    {
+      Object[] a = new Object[n];
+      Arrays.fill(a, element);
+      return a;
+    }
+
+    /**
+     * The string is easy to generate.
+     */
+    public String toString()
+    {
+      StringBuffer r = new StringBuffer("{");
+      for (int i = n - 1; --i > 0; )
+        r.append(element).append(", ");
+      r.append(element).append("}");
+      return r.toString();
+    }
+  } // class CopiesList
+
+  /**
+   * Replace all instances of one object with another in the specified list.
+   * The list does not change size. An element e is replaced if
+   * <code>oldval == null ? e == null : oldval.equals(e)</code>.
+   *
+   * @param list the list to iterate over
+   * @param oldval the element to replace
+   * @param newval the new value for the element
+   * @return true if a replacement occurred
+   * @throws UnsupportedOperationException if the list iterator does not allow
+   *         for the set operation
+   * @throws ClassCastException newval is of a type which cannot be added
+   *         to the list
+   * @throws IllegalArgumentException some other aspect of newval stops
+   *         it being added to the list
+   * @since 1.4
+   */
+  public static boolean replaceAll(List list, Object oldval, Object newval)
+  {
+    ListIterator itr = list.listIterator();
+    boolean replace_occured = false;
+    for (int i = list.size(); --i >= 0; )
+      if (AbstractCollection.equals(oldval, itr.next()))
+        {
+          itr.set(newval);
+          replace_occured = true;
+        }
+    return replace_occured;
   }
 
   /**
    * Reverse a given list. This method works in linear time.
    *
-   * @param l the list to reverse.
-   * @exception UnsupportedOperationException if l.listIterator() does not
-   *   support the set operation.
+   * @param l the list to reverse
+   * @throws UnsupportedOperationException if l.listIterator() does not
+   *         support the set operation
    */
   public static void reverse(List l)
   {
     ListIterator i1 = l.listIterator();
-    int pos1 = 0;
+    int pos1 = 1;
     int pos2 = l.size();
     ListIterator i2 = l.listIterator(pos2);
     while (pos1 < pos2)
@@ -486,42 +787,152 @@ public class Collections
       }
   }
 
-  static class ReverseComparator implements Comparator, Serializable
+  /**
+   * Get a comparator that implements the reverse of natural ordering. In
+   * other words, this sorts Comparable objects opposite of how their
+   * compareTo method would sort. This makes it easy to sort into reverse
+   * order, by simply passing Collections.reverseOrder() to the sort method.
+   * The return value of this method is Serializable.
+   *
+   * @return a comparator that imposes reverse natural ordering
+   * @see Comparable
+   * @see Serializable
+   */
+  public static Comparator reverseOrder()
   {
+    return rcInstance;
+  }
+
+  /**
+   * The object for {@link #reverseOrder()}.
+   */
+  static private final ReverseComparator rcInstance = new ReverseComparator();
+
+  /**
+   * The implementation of {@link #reverseOrder()}. This class name
+   * is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class ReverseComparator
+    implements Comparator, Serializable
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    static private final long serialVersionUID = 7207038068494060240L;
+
+    /**
+     * A private constructor adds overhead.
+     */
+    ReverseComparator()
+    {
+    }
+
+    /**
+     * Compare two objects in reverse natural order.
+     *
+     * @param a the first object
+     * @param b the second object
+     * @return &lt;, ==, or &gt; 0 according to b.compareTo(a)
+     */
     public int compare(Object a, Object b)
     {
-      return -((Comparable) a).compareTo(b);
+      return ((Comparable) b).compareTo(a);
     }
   }
-  
-  static ReverseComparator rcInstance = new ReverseComparator();
-  
+
   /**
-   * Get a comparator that implements the reverse of natural ordering. This is
-   * intended to make it easy to sort into reverse order, by simply passing
-   * Collections.reverseOrder() to the sort method. The return value of this
-   * method is Serializable.
+   * Rotate the elements in a list by a specified distance. After calling this
+   * method, the element now at index <code>i</code> was formerly at index
+   * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
+   * <p>
+   *
+   * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
+   * either <code>Collections.rotate(l, 4)</code> or
+   * <code>Collections.rotate(l, -1)</code>, the new contents are
+   * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
+   * just a portion of the list. For example, to move element <code>a</code>
+   * forward two positions in the original example, use
+   * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
+   * result in <code>[t, n, k, a, s]</code>.
+   * <p>
+   *
+   * If the list is small or implements {@link RandomAccess}, the
+   * implementation exchanges the first element to its destination, then the
+   * displaced element, and so on until a circuit has been completed. The
+   * process is repeated if needed on the second element, and so forth, until
+   * all elements have been swapped.  For large non-random lists, the
+   * implementation breaks the list into two sublists at index
+   * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
+   * pieces, then reverses the overall list.
+   *
+   * @param list the list to rotate
+   * @param distance the distance to rotate by; unrestricted in value
+   * @throws UnsupportedOperationException if the list does not support set
+   * @since 1.4
    */
-  public static Comparator reverseOrder()
+  public static void rotate(List list, int distance)
   {
-    return rcInstance;
+    int size = list.size();
+    distance %= size;
+    if (distance == 0)
+      return;
+    if (distance < 0)
+      distance += size;
+
+    if (isSequential(list))
+      {
+        reverse(list);
+        reverse(list.subList(0, distance));
+        reverse(list.subList(distance, size));
+      }
+    else
+      {
+        // Determine the least common multiple of distance and size, as there
+        // are (distance / LCM) loops to cycle through.
+        int a = size;
+        int lcm = distance;
+        int b = a % lcm;
+        while (b != 0)
+          {
+            a = lcm;
+            lcm = b;
+            b = a % lcm;
+          }
+
+        // Now, make the swaps. We must take the remainder every time through
+        // the inner loop so that we don't overflow i to negative values.
+        while (--lcm >= 0)
+          {
+            Object o = list.get(lcm);
+            for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
+              o = list.set(i, o);
+            list.set(lcm, o);
+          }
+      }
   }
 
   /**
    * Shuffle a list according to a default source of randomness. The algorithm
-   * used would result in a perfectly fair shuffle (that is, each element would
-   * have an equal chance of ending up in any position) with a perfect source
-   * of randomness; in practice the results are merely very close to perfect.
+   * used iterates backwards over the list, swapping each element with an
+   * element randomly selected from the elements in positions less than or
+   * equal to it (using r.nextInt(int)).
    * <p>
-   * This method operates in linear time on a random-access list, but may take
-   * quadratic time on a sequential-access list.
-   * Note: this (classpath) implementation will never take quadratic time, but
-   * it does make a copy of the list. This is in line with the behaviour of the
-   * sort methods and seems preferable.
    *
-   * @param l the list to shuffle.
-   * @exception UnsupportedOperationException if l.listIterator() does not
-   *   support the set operation.
+   * This algorithm would result in a perfectly fair shuffle (that is, each
+   * element would have an equal chance of ending up in any position) if r were
+   * a perfect source of randomness. In practice the results are merely very
+   * close to perfect.
+   * <p>
+   *
+   * This method operates in linear time. To do this on large lists which do
+   * not implement {@link RandomAccess}, a temporary array is used to acheive
+   * this speed, since it would be quadratic access otherwise.
+   *
+   * @param l the list to shuffle
+   * @throws UnsupportedOperationException if l.listIterator() does not
+   *         support the set operation
    */
   public static void shuffle(List l)
   {
@@ -536,11 +947,12 @@ public class Collections
     shuffle(l, defaultRandom);
   }
 
-  /** Cache a single Random object for use by shuffle(List). This improves
-    * performance as well as ensuring that sequential calls to shuffle() will
-    * not result in the same shuffle order occurring: the resolution of 
-    * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
-    */
+  /**
+   * Cache a single Random object for use by shuffle(List). This improves
+   * performance as well as ensuring that sequential calls to shuffle() will
+   * not result in the same shuffle order occurring: the resolution of
+   * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
+   */
   private static Random defaultRandom = null;
 
   /**
@@ -549,149 +961,470 @@ public class Collections
    * element randomly selected from the elements in positions less than or
    * equal to it (using r.nextInt(int)).
    * <p>
+   *
    * This algorithm would result in a perfectly fair shuffle (that is, each
    * element would have an equal chance of ending up in any position) if r were
    * a perfect source of randomness. In practise (eg if r = new Random()) the
    * results are merely very close to perfect.
    * <p>
-   * This method operates in linear time on a random-access list, but may take
-   * quadratic time on a sequential-access list.
-   * Note: this (classpath) implementation will never take quadratic time, but
-   * it does make a copy of the list. This is in line with the behaviour of the
-   * sort methods and seems preferable.
    *
-   * @param l the list to shuffle.
-   * @param r the source of randomness to use for the shuffle.
-   * @exception UnsupportedOperationException if l.listIterator() does not
-   *   support the set operation.
+   * This method operates in linear time. To do this on large lists which do
+   * not implement {@link RandomAccess}, a temporary array is used to acheive
+   * this speed, since it would be quadratic access otherwise.
+   *
+   * @param l the list to shuffle
+   * @param r the source of randomness to use for the shuffle
+   * @throws UnsupportedOperationException if l.listIterator() does not
+   *         support the set operation
    */
   public static void shuffle(List l, Random r)
   {
-    Object[] a = l.toArray();	// Dump l into an array
     int lsize = l.size();
     ListIterator i = l.listIterator(lsize);
+    boolean sequential = isSequential(l);
+    Object[] a = null; // stores a copy of the list for the sequential case
 
-    // Iterate backwards over l
-    for (int pos = lsize - 1; pos >= 0; --pos)
+    if (sequential)
+      a = l.toArray();
+
+    for (int pos = lsize - 1; pos > 0; --pos)
       {
 	// Obtain a random position to swap with. pos + 1 is used so that the
 	// range of the random number includes the current position.
 	int swap = r.nextInt(pos + 1);
 
-	// Swap the swapth element of the array with the next element of the
-	// list.
-	Object o = a[swap];
-	a[swap] = a[pos];
-	a[pos] = o;
+	// Swap the desired element.
+	Object o;
+        if (sequential)
+          {
+            o = a[swap];
+            a[swap] = i.previous();
+          }
+        else
+          o = l.set(swap, i.previous());
 
-	// Set the element in the original list accordingly.
-	i.previous();
 	i.set(o);
       }
   }
 
+
   /**
    * Obtain an immutable Set consisting of a single element. The return value
    * of this method is Serializable.
    *
-   * @param o the single element.
-   * @return an immutable Set containing only o.
+   * @param o the single element
+   * @return an immutable Set containing only o
+   * @see Serializable
    */
-  // It's not serializable because the spec is broken.
-  public static Set singleton(final Object o)
+  public static Set singleton(Object o)
   {
-    return new AbstractSet()
+    return new SingletonSet(o);
+  }
+
+  /**
+   * The implementation of {@link #singleton(Object)}. This class name
+   * is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class SingletonSet extends AbstractSet
+    implements Serializable
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 3193687207550431679L;
+
+
+    /**
+     * The single element; package visible for use in nested class.
+     * @serial the singleton
+     */
+    final Object element;
+
+    /**
+     * Construct a singleton.
+     * @param o the element
+     */
+    SingletonSet(Object o)
     {
-      public int size()
-      {
-	return 1;
-      }
+      element = o;
+    }
 
-      public Iterator iterator()
-      {
-	return new Iterator()
-	{
-	  private boolean hasNext = true;
+    /**
+     * The size: always 1!
+     */
+    public int size()
+    {
+      return 1;
+    }
 
-	  public boolean hasNext()
-	  {
-	    return hasNext;
-	  }
+    /**
+     * Returns an iterator over the lone element.
+     */
+    public Iterator iterator()
+    {
+      return new Iterator()
+      {
+        private boolean hasNext = true;
+
+        public boolean hasNext()
+        {
+          return hasNext;
+        }
+
+        public Object next()
+        {
+          if (hasNext)
+          {
+            hasNext = false;
+            return element;
+          }
+          else
+            throw new NoSuchElementException();
+        }
+
+        public void remove()
+        {
+          throw new UnsupportedOperationException();
+        }
+      };
+    }
 
-	  public Object next()
-	  {
-	    if (hasNext)
-	      {
-		hasNext = false;
-		return o;
-	      }
-	    else
-	      {
-		throw new NoSuchElementException();
-	      }
-	  }
+    // The remaining methods are optional, but provide a performance
+    // advantage by not allocating unnecessary iterators in AbstractSet.
+    /**
+     * The set only contains one element.
+     */
+    public boolean contains(Object o)
+    {
+      return equals(o, element);
+    }
 
-	  public void remove()
-	  {
-	    throw new UnsupportedOperationException();
-	  }
-	};
-      }
-    };
-  }
+    /**
+     * This is true if the other collection only contains the element.
+     */
+    public boolean containsAll(Collection c)
+    {
+      Iterator i = c.iterator();
+      int pos = c.size();
+      while (--pos >= 0)
+        if (! equals(i.next(), element))
+          return false;
+      return true;
+    }
+
+    /**
+     * The hash is just that of the element.
+     */
+    public int hashCode()
+    {
+      return hashCode(element);
+    }
+
+    /**
+     * Returning an array is simple.
+     */
+    public Object[] toArray()
+    {
+      return new Object[] {element};
+    }
+
+    /**
+     * Obvious string.
+     */
+    public String toString()
+    {
+      return "[" + element + "]";
+    }
+  } // class SingletonSet
 
   /**
    * Obtain an immutable List consisting of a single element. The return value
-   * of this method is Serializable.
+   * of this method is Serializable, and implements RandomAccess.
+   *
+   * @param o the single element
+   * @return an immutable List containing only o
+   * @see Serializable
+   * @see RandomAccess
+   * @since 1.3
+   */
+  public static List singletonList(Object o)
+  {
+    return new SingletonList(o);
+  }
+
+  /**
+   * The implementation of {@link #singletonList(Object)}. This class name
+   * is required for compatibility with Sun's JDK serializability.
    *
-   * @param o the single element.
-   * @return an immutable List containing only o.
+   * @author Eric Blake <ebb9@email.byu.edu>
    */
-  // It's not serializable because the spec is broken.
-  public static List singletonList(final Object o)
+  private static final class SingletonList extends AbstractList
+    implements Serializable, RandomAccess
   {
-    return new AbstractList()
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 3093736618740652951L;
+
+    /**
+     * The single element.
+     * @serial the singleton
+     */
+    private final Object element;
+
+    /**
+     * Construct a singleton.
+     * @param o the element
+     */
+    SingletonList(Object o)
     {
-      public int size()
-      {
-	return 1;
-      }
+      element = o;
+    }
 
-      public Object get(int index)
-      {
-	if (index == 0)
-	  {
-	    throw new IndexOutOfBoundsException();
-	  }
-	else
-	  {
-	    return o;
-	  }
-      }
-    };
-  }
+    /**
+     * The size: always 1!
+     */
+    public int size()
+    {
+      return 1;
+    }
+
+    /**
+     * Only index 0 is valid.
+     */
+    public Object get(int index)
+    {
+      if (index == 0)
+        return element;
+      throw new IndexOutOfBoundsException();
+    }
+
+    // The remaining methods are optional, but provide a performance
+    // advantage by not allocating unnecessary iterators in AbstractList.
+    /**
+     * The set only contains one element.
+     */
+    public boolean contains(Object o)
+    {
+      return equals(o, element);
+    }
+
+    /**
+     * This is true if the other collection only contains the element.
+     */
+    public boolean containsAll(Collection c)
+    {
+      Iterator i = c.iterator();
+      int pos = c.size();
+      while (--pos >= 0)
+        if (! equals(i.next(), element))
+          return false;
+      return true;
+    }
+
+    /**
+     * Speed up the hashcode computation.
+     */
+    public int hashCode()
+    {
+      return 31 + hashCode(element);
+    }
+
+    /**
+     * Either the list has it or not.
+     */
+    public int indexOf(Object o)
+    {
+      return equals(o, element) ? 0 : -1;
+    }
+
+    /**
+     * Either the list has it or not.
+     */
+    public int lastIndexOf(Object o)
+    {
+      return equals(o, element) ? 0 : -1;
+    }
+
+    /**
+     * Sublists are limited in scope.
+     */
+    public List subList(int from, int to)
+    {
+      if (from == to && (to == 0 || to == 1))
+        return EMPTY_LIST;
+      if (from == 0 && to == 1)
+        return this;
+      if (from > to)
+        throw new IllegalArgumentException();
+      throw new IndexOutOfBoundsException();
+    }
+
+    /**
+     * Returning an array is simple.
+     */
+    public Object[] toArray()
+    {
+      return new Object[] {element};
+    }
+
+    /**
+     * Obvious string.
+     */
+    public String toString()
+    {
+      return "[" + element + "]";
+    }
+  } // class SingletonList
 
   /**
-   * Obtain an immutable Map consisting of a single key value pair.
+   * Obtain an immutable Map consisting of a single key-value pair.
    * The return value of this method is Serializable.
    *
-   * @param key the single key.
-   * @param value the single value.
-   * @return an immutable Map containing only the single key value pair.
+   * @param key the single key
+   * @param value the single value
+   * @return an immutable Map containing only the single key-value pair
+   * @see Serializable
+   * @since 1.3
    */
-  // It's not serializable because the spec is broken.
-  public static Map singletonMap(final Object key, final Object value)
+  public static Map singletonMap(Object key, Object value)
   {
-    return new AbstractMap()
-    {
-      public Set entrySet()
-      {
-	return singleton(new BasicMapEntry(key, value));
-      }
-    };
+    return new SingletonMap(key, value);
   }
 
   /**
+   * The implementation of {@link #singletonMap(Object)}. This class name
+   * is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class SingletonMap extends AbstractMap
+    implements Serializable
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -6979724477215052911L;
+
+    /**
+     * The single key.
+     * @serial the singleton key
+     */
+    private final Object k;
+
+    /**
+     * The corresponding value.
+     * @serial the singleton value
+     */
+    private final Object v;
+
+    /**
+     * Cache the entry set.
+     */
+    private transient Set entries;
+
+    /**
+     * Construct a singleton.
+     * @param key the key
+     * @param value the value
+     */
+    SingletonMap(Object key, Object value)
+    {
+      k = key;
+      v = value;
+    }
+
+    /**
+     * There is a single immutable entry.
+     */
+    public Set entrySet()
+    {
+      if (entries == null)
+        entries = singleton(new BasicMapEntry(k, v)
+        {
+          public Object setValue(Object o)
+          {
+            throw new UnsupportedOperationException();
+          }
+        });
+      return entries;
+    }
+
+    // The remaining methods are optional, but provide a performance
+    // advantage by not allocating unnecessary iterators in AbstractMap.
+    /**
+     * Single entry.
+     */
+    public boolean containsKey(Object key)
+    {
+      return equals(key, k);
+    }
+
+    /**
+     * Single entry.
+     */
+    public boolean containsValue(Object value)
+    {
+      return equals(value, v);
+    }
+
+    /**
+     * Single entry.
+     */
+    public Object get(Object key)
+    {
+      return equals(key, k) ? v : null;
+    }
+
+    /**
+     * Calculate the hashcode directly.
+     */
+    public int hashCode()
+    {
+      return hashCode(k) ^ hashCode(v);
+    }
+
+    /**
+     * Return the keyset.
+     */
+    public Set keySet()
+    {
+      if (keys == null)
+        keys = singleton(k);
+      return keys;
+    }
+
+    /**
+     * The size: always 1!
+     */
+    public int size()
+    {
+      return 1;
+    }
+
+    /**
+     * Return the values. Technically, a singleton, while more specific than
+     * a general Collection, will work. Besides, that's what the JDK uses!
+     */
+    public Collection values()
+    {
+      if (values == null)
+        values = singleton(v);
+      return values;
+    }
+
+    /**
+     * Obvious string.
+     */
+    public String toString()
+    {
+      return "{" + k + "=" + v + "}";
+    }
+  } // class SingletonMap
+
+  /**
    * Sort a list according to the natural ordering of its elements. The list
    * must be modifiable, but can be of fixed size. The sort algorithm is
    * precisely that used by Arrays.sort(Object[]), which offers guaranteed
@@ -700,19 +1433,14 @@ public class Collections
    * the array.
    *
    * @param l the List to sort
-   * @exception ClassCastException if some items are not mutually comparable
-   * @exception UnsupportedOperationException if the List is not modifiable
+   * @throws ClassCastException if some items are not mutually comparable
+   * @throws UnsupportedOperationException if the List is not modifiable
+   * @throws NullPointerException if some element is null
+   * @see Arrays#sort(Object[])
    */
   public static void sort(List l)
   {
-    Object[] a = l.toArray();
-    Arrays.sort(a);
-    ListIterator i = l.listIterator();
-    for (int pos = 0; pos < a.length; pos++)
-      {
-	i.next();
-	i.set(a[pos]);
-      }
+    sort(l, null);
   }
 
   /**
@@ -724,1102 +1452,1897 @@ public class Collections
    * the array.
    *
    * @param l the List to sort
-   * @param c the Comparator specifying the ordering for the elements
-   * @exception ClassCastException if c will not compare some pair of items
-   * @exception UnsupportedOperationException if the List is not modifiable
+   * @param c the Comparator specifying the ordering for the elements, or
+   *        null for natural ordering
+   * @throws ClassCastException if c will not compare some pair of items
+   * @throws UnsupportedOperationException if the List is not modifiable
+   * @throws NullPointerException if null is compared by natural ordering
+   *        (only possible when c is null)
+   * @see Arrays#sort(Object[], Comparator)
    */
   public static void sort(List l, Comparator c)
   {
     Object[] a = l.toArray();
     Arrays.sort(a, c);
-    ListIterator i = l.listIterator();
-    for (int pos = 0; pos < a.length; pos++)
+    ListIterator i = l.listIterator(a.length);
+    for (int pos = a.length; --pos >= 0; )
       {
-	i.next();
+	i.previous();
 	i.set(a[pos]);
       }
   }
 
-  // All the methods from here on in require doc-comments.
-
-  public static Collection synchronizedCollection(Collection c)
-  {
-    return new SynchronizedCollection(c);
-  }
-  public static List synchronizedList(List l)
-  {
-    return new SynchronizedList(l);
-  }
-  public static Map synchronizedMap(Map m)
-  {
-    return new SynchronizedMap(m);
-  }
-  public static Set synchronizedSet(Set s)
-  {
-    return new SynchronizedSet(s);
-  }
-  public static SortedMap synchronizedSortedMap(SortedMap m)
-  {
-    return new SynchronizedSortedMap(m);
-  }
-  public static SortedSet synchronizedSortedSet(SortedSet s)
-  {
-    return new SynchronizedSortedSet(s);
-  }
-  public static Collection unmodifiableCollection(Collection c)
-  {
-    return new UnmodifiableCollection(c);
-  }
-  public static List unmodifiableList(List l)
-  {
-    return new UnmodifiableList(l);
-  }
-  public static Map unmodifiableMap(Map m)
-  {
-    return new UnmodifiableMap(m);
-  }
-  public static Set unmodifiableSet(Set s)
-  {
-    return new UnmodifiableSet(s);
-  }
-  public static SortedMap unmodifiableSortedMap(SortedMap m)
-  {
-    return new UnmodifiableSortedMap(m);
-  }
-  public static SortedSet unmodifiableSortedSet(SortedSet s)
+  /**
+   * Swaps the elements at the specified positions within the list. Equal
+   * positions have no effect.
+   *
+   * @param l the list to work on
+   * @param i the first index to swap
+   * @param j the second index
+   * @throws UnsupportedOperationException if list.set is not supported
+   * @throws IndexOutOfBoundsException if either i or j is &lt; 0 or &gt;=
+   *         list.size()
+   * @since 1.4
+   */
+  public static void swap(List l, int i, int j)
   {
-    return new UnmodifiableSortedSet(s);
+    l.set(i, l.set(j, l.get(i)));
   }
 
-  // Sun's spec will need to be checked for the precise names of these
-  // classes, for serializability's sake. However, from what I understand,
-  // serialization is broken for these classes anyway.
-
-  // Note: although this code is largely uncommented, it is all very
-  // mechanical and there's nothing really worth commenting.
-  // When serialization of these classes works, we'll need doc-comments on
-  // them to document the serialized form.
-
-  private static class UnmodifiableIterator implements Iterator
+  /**
+   * Returns a synchronized (thread-safe) collection wrapper backed by the
+   * given collection. Notice that element access through the iterators
+   * is thread-safe, but if the collection can be structurally modified
+   * (adding or removing elements) then you should synchronize around the
+   * iteration to avoid non-deterministic behavior:<br>
+   * <pre>
+   * Collection c = Collections.synchronizedCollection(new Collection(...));
+   * ...
+   * synchronized (c)
+   *   {
+   *     Iterator i = c.iterator();
+   *     while (i.hasNext())
+   *       foo(i.next());
+   *   }
+   * </pre><p>
+   *
+   * Since the collection might be a List or a Set, and those have incompatible
+   * equals and hashCode requirements, this relies on Object's implementation
+   * rather than passing those calls on to the wrapped collection. The returned
+   * Collection implements Serializable, but can only be serialized if
+   * the collection it wraps is likewise Serializable.
+   *
+   * @param c the collection to wrap
+   * @return a synchronized view of the collection
+   * @see Serializable
+   */
+  public static Collection synchronizedCollection(Collection c)
   {
-    private Iterator i;
-
-    public UnmodifiableIterator(Iterator i)
-    {
-      this.i = i;
-    }
-
-    public Object next()
-    {
-      return i.next();
-    }
-    public boolean hasNext()
-    {
-      return i.hasNext();
-    }
-    public void remove()
-    {
-      throw new UnsupportedOperationException();
-    }
+    return new SynchronizedCollection(c);
   }
 
-  private static class UnmodifiableListIterator extends UnmodifiableIterator
-    implements ListIterator
+  /**
+   * The implementation of {@link #synchronizedCollection(Collection)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   * Package visible, so that collections such as the one for
+   * Hashtable.values() can specify which object to synchronize on.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  static class SynchronizedCollection
+    implements Collection, Serializable
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    private ListIterator li;
-
-    public UnmodifiableListIterator(ListIterator li)
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 3053995032091335093L;
+
+    /**
+     * The wrapped collection. Package visible for use by subclasses.
+     * @serial the real collection
+     */
+    final Collection c;
+
+    /**
+     * The object to synchronize on.  When an instance is created via public
+     * methods, it will be this; but other uses like SynchronizedMap.values()
+     * must specify another mutex. Package visible for use by subclasses.
+     * @serial the lock
+     */
+    final Object mutex;
+
+    /**
+     * Wrap a given collection.
+     * @param c the collection to wrap
+     * @throws NullPointerException if c is null
+     */
+    SynchronizedCollection(Collection c)
     {
-      super(li);
-      this.li = li;
-    }
-
-    public boolean hasPrevious()
-    {
-      return li.hasPrevious();
-    }
-    public Object previous()
-    {
-      return li.previous();
-    }
-    public int nextIndex()
-    {
-      return li.nextIndex();
-    }
-    public int previousIndex()
-    {
-      return li.previousIndex();
-    }
-    public void add(Object o)
-    {
-      throw new UnsupportedOperationException();
-    }
-    public void set(Object o)
-    {
-      throw new UnsupportedOperationException();
+      this.c = c;
+      mutex = this;
+      if (c == null)
+        throw new NullPointerException();
     }
-  }
-
-  private static class UnmodifiableCollection implements Collection,
-    Serializable
-  {
-    Collection c;
 
-    public UnmodifiableCollection(Collection c)
+    /**
+     * Called only by trusted code to specify the mutex as well as the
+     * collection.
+     * @param sync the mutex
+     * @param c the collection
+     */
+    SynchronizedCollection(Object sync, Collection c)
     {
       this.c = c;
+      mutex = sync;
     }
 
     public boolean add(Object o)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return c.add(o);
+        }
     }
-    public boolean addAll(Collection c)
+
+    public boolean addAll(Collection col)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return c.addAll(col);
+        }
     }
+
     public void clear()
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          c.clear();
+        }
     }
+
     public boolean contains(Object o)
     {
-      return c.contains(o);
+      synchronized (mutex)
+        {
+          return c.contains(o);
+        }
     }
+
     public boolean containsAll(Collection c1)
     {
-      return c.containsAll(c1);
+      synchronized (mutex)
+        {
+          return c.containsAll(c1);
+        }
     }
+
     public boolean isEmpty()
     {
-      return c.isEmpty();
+      synchronized (mutex)
+        {
+          return c.isEmpty();
+        }
     }
+
     public Iterator iterator()
     {
-      return new UnmodifiableIterator(c.iterator());
+      synchronized (mutex)
+        {
+          return new SynchronizedIterator(mutex, c.iterator());
+        }
     }
+
     public boolean remove(Object o)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return c.remove(o);
+        }
     }
-    public boolean removeAll(Collection c)
+
+    public boolean removeAll(Collection col)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return c.removeAll(col);
+        }
     }
-    public boolean retainAll(Collection c)
+
+    public boolean retainAll(Collection col)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return c.retainAll(col);
+        }
     }
+
     public int size()
     {
-      return c.size();
+      synchronized (mutex)
+        {
+          return c.size();
+        }
     }
+
     public Object[] toArray()
     {
-      return c.toArray();
+      synchronized (mutex)
+        {
+          return c.toArray();
+        }
     }
-    public Object[] toArray(Object[]a)
+
+    public Object[] toArray(Object[] a)
     {
-      return c.toArray(a);
+      synchronized (mutex)
+        {
+          return c.toArray(a);
+        }
     }
+
     public String toString()
     {
-      return c.toString();
+      synchronized (mutex)
+        {
+          return c.toString();
+        }
+    }
+  } // class SynchronizedCollection
+
+  /**
+   * The implementation of the various iterator methods in the
+   * synchronized classes. These iterators must "sync" on the same object
+   * as the collection they iterate over.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class SynchronizedIterator implements Iterator
+  {
+    /**
+     * The object to synchronize on. Package visible for use by subclass.
+     */
+    final Object mutex;
+
+    /**
+     * The wrapped iterator.
+     */
+    private final Iterator i;
+
+    /**
+     * Only trusted code creates a wrapper, with the specified sync.
+     * @param sync the mutex
+     * @param i the wrapped iterator
+     */
+    SynchronizedIterator(Object sync, Iterator i)
+    {
+      this.i = i;
+      mutex = sync;
+    }
+
+    public Object next()
+    {
+      synchronized (mutex)
+        {
+          return i.next();
+        }
     }
+
+    public boolean hasNext()
+    {
+      synchronized (mutex)
+        {
+          return i.hasNext();
+        }
+    }
+
+    public void remove()
+    {
+      synchronized (mutex)
+        {
+          i.remove();
+        }
+    }
+  } // class SynchronizedIterator
+
+  /**
+   * Returns a synchronized (thread-safe) list wrapper backed by the
+   * given list. Notice that element access through the iterators
+   * is thread-safe, but if the list can be structurally modified
+   * (adding or removing elements) then you should synchronize around the
+   * iteration to avoid non-deterministic behavior:<br>
+   * <pre>
+   * List l = Collections.synchronizedList(new List(...));
+   * ...
+   * synchronized (l)
+   *   {
+   *     Iterator i = l.iterator();
+   *     while (i.hasNext())
+   *       foo(i.next());
+   *   }
+   * </pre><p>
+   *
+   * The returned List implements Serializable, but can only be serialized if
+   * the list it wraps is likewise Serializable. In addition, if the wrapped
+   * list implements RandomAccess, this does too.
+   *
+   * @param l the list to wrap
+   * @return a synchronized view of the list
+   * @see Serializable
+   * @see RandomAccess
+   */
+  public static List synchronizedList(List l)
+  {
+    if (l instanceof RandomAccess)
+      return new SynchronizedRandomAccessList(l);
+    return new SynchronizedList(l);
   }
 
-  private static class UnmodifiableList extends UnmodifiableCollection
+  /**
+   * The implementation of {@link #synchronizedList(List)} for sequential
+   * lists. This class name is required for compatibility with Sun's JDK
+   * serializability. Package visible, so that lists such as Vector.subList()
+   * can specify which object to synchronize on.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  static class SynchronizedList extends SynchronizedCollection
     implements List
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    List l;
-
-    public UnmodifiableList(List l)
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -7754090372962971524L;
+
+    /**
+     * The wrapped list; stored both here and in the superclass to avoid
+     * excessive casting. Package visible for use by subclass.
+     * @serial the wrapped list
+     */
+    final List list;
+
+    /**
+     * Wrap a given list.
+     * @param l the list to wrap
+     * @throws NullPointerException if l is null
+     */
+    SynchronizedList(List l)
     {
       super(l);
-      this.l = l;
+      list = l;
+    }
+
+    /**
+     * Called only by trusted code to specify the mutex as well as the list.
+     * @param sync the mutex
+     * @param l the list
+     */
+    SynchronizedList(Object sync, List l)
+    {
+      super(sync, l);
+      list = l;
     }
 
     public void add(int index, Object o)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          list.add(index, o);
+        }
     }
+
     public boolean addAll(int index, Collection c)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return list.addAll(index, c);
+        }
     }
+
     public boolean equals(Object o)
     {
-      return l.equals(o);
+      synchronized (mutex)
+        {
+          return list.equals(o);
+        }
     }
+
     public Object get(int index)
     {
-      return l.get(index);
+      synchronized (mutex)
+        {
+          return list.get(index);
+        }
     }
+
     public int hashCode()
     {
-      return l.hashCode();
+      synchronized (mutex)
+        {
+          return list.hashCode();
+        }
     }
+
     public int indexOf(Object o)
     {
-      return l.indexOf(o);
+      synchronized (mutex)
+        {
+          return list.indexOf(o);
+        }
     }
+
     public int lastIndexOf(Object o)
     {
-      return l.lastIndexOf(o);
+      synchronized (mutex)
+        {
+          return list.lastIndexOf(o);
+        }
     }
+
     public ListIterator listIterator()
     {
-      return new UnmodifiableListIterator(l.listIterator());
+      synchronized (mutex)
+        {
+          return new SynchronizedListIterator(mutex, list.listIterator());
+        }
     }
+
     public ListIterator listIterator(int index)
     {
-      return new UnmodifiableListIterator(l.listIterator(index));
+      synchronized (mutex)
+        {
+          return new SynchronizedListIterator(mutex, list.listIterator(index));
+        }
     }
+
     public Object remove(int index)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return list.remove(index);
+        }
     }
+
     public Object set(int index, Object o)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return list.set(index, o);
+        }
     }
+
     public List subList(int fromIndex, int toIndex)
     {
-      return new UnmodifiableList(l.subList(fromIndex, toIndex));
+      synchronized (mutex)
+        {
+          return new SynchronizedList(mutex, list.subList(fromIndex, toIndex));
+        }
     }
-  }
+  } // class SynchronizedList
 
-  private static class UnmodifiableSet extends UnmodifiableCollection
-    implements Set
+  /**
+   * The implementation of {@link #synchronizedList(List)} for random-access
+   * lists. This class name is required for compatibility with Sun's JDK
+   * serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class SynchronizedRandomAccessList
+    extends SynchronizedList implements RandomAccess
   {
-    public UnmodifiableSet(Set s)
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 1530674583602358482L;
+
+    /**
+     * Wrap a given list.
+     * @param l the list to wrap
+     * @throws NullPointerException if l is null
+     */
+    SynchronizedRandomAccessList(List l)
     {
-      super(s);
+      super(l);
     }
-    public boolean equals(Object o)
+
+    /**
+     * Called only by trusted code to specify the mutex as well as the
+     * collection.
+     * @param sync the mutex
+     * @param l the list
+     */
+    SynchronizedRandomAccessList(Object sync, List l)
     {
-      return c.equals(o);
+      super(sync, l);
     }
-    public int hashCode()
+
+    public List subList(int fromIndex, int toIndex)
     {
-      return c.hashCode();
+      synchronized (mutex)
+        {
+          return new SynchronizedRandomAccessList(mutex,
+                                                  list.subList(fromIndex,
+                                                               toIndex));
+        }
     }
-  }
+  } // class SynchronizedRandomAccessList
 
-  private static class UnmodifiableSortedSet extends UnmodifiableSet
-    implements SortedSet
+  /**
+   * The implementation of {@link SynchronizedList#listIterator()}. This
+   * iterator must "sync" on the same object as the list it iterates over.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class SynchronizedListIterator
+    extends SynchronizedIterator implements ListIterator
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    private SortedSet ss;
-
-    public UnmodifiableSortedSet(SortedSet ss)
+    /**
+     * The wrapped iterator, stored both here and in the superclass to
+     * avoid excessive casting.
+     */
+    private final ListIterator li;
+
+    /**
+     * Only trusted code creates a wrapper, with the specified sync.
+     * @param sync the mutex
+     * @param li the wrapped iterator
+     */
+    SynchronizedListIterator(Object sync, ListIterator li)
     {
-      super(ss);
-      this.ss = ss;
+      super(sync, li);
+      this.li = li;
     }
 
-    public Comparator comparator()
+    public void add(Object o)
     {
-      return ss.comparator();
+      synchronized (mutex)
+        {
+          li.add(o);
+        }
     }
-    public Object first()
+    public boolean hasPrevious()
     {
-      return ss.first();
+      synchronized (mutex)
+        {
+          return li.hasPrevious();
+        }
     }
-    public Object last()
+
+    public int nextIndex()
     {
-      return ss.last();
+      synchronized (mutex)
+        {
+          return li.nextIndex();
+        }
     }
-    public SortedSet headSet(Object toElement)
+
+    public Object previous()
     {
-      return new UnmodifiableSortedSet(ss.headSet(toElement));
+      synchronized (mutex)
+        {
+          return li.previous();
+        }
     }
-    public SortedSet tailSet(Object fromElement)
+
+    public int previousIndex()
     {
-      return new UnmodifiableSortedSet(ss.tailSet(fromElement));
+      synchronized (mutex)
+        {
+          return li.previousIndex();
+        }
     }
-    public SortedSet subSet(Object fromElement, Object toElement)
+
+    public void set(Object o)
     {
-      return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement));
+      synchronized (mutex)
+        {
+          li.set(o);
+        }
     }
+  } // class SynchronizedListIterator
+
+  /**
+   * Returns a synchronized (thread-safe) map wrapper backed by the given
+   * map. Notice that element access through the collection views and their
+   * iterators are thread-safe, but if the map can be structurally modified
+   * (adding or removing elements) then you should synchronize around the
+   * iteration to avoid non-deterministic behavior:<br>
+   * <pre>
+   * Map m = Collections.synchronizedMap(new Map(...));
+   * ...
+   * Set s = m.keySet(); // safe outside a synchronized block
+   * synchronized (m) // synch on m, not s
+   *   {
+   *     Iterator i = s.iterator();
+   *     while (i.hasNext())
+   *       foo(i.next());
+   *   }
+   * </pre><p>
+   *
+   * The returned Map implements Serializable, but can only be serialized if
+   * the map it wraps is likewise Serializable.
+   *
+   * @param m the map to wrap
+   * @return a synchronized view of the map
+   * @see Serializable
+   */
+  public static Map synchronizedMap(Map m)
+  {
+    return new SynchronizedMap(m);
   }
 
-  private static class UnmodifiableMap implements Map, Serializable
+  /**
+   * The implementation of {@link #synchronizedMap(Map)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class SynchronizedMap implements Map, Serializable
   {
-    Map m;
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 1978198479659022715L;
+
+    /**
+     * The wrapped map.
+     * @serial the real map
+     */
+    private final Map m;
+
+    /**
+     * The object to synchronize on.  When an instance is created via public
+     * methods, it will be this; but other uses like
+     * SynchronizedSortedMap.subMap() must specify another mutex. Package
+     * visible for use by subclass.
+     * @serial the lock
+     */
+    final Object mutex;
+
+    /**
+     * Cache the entry set.
+     */
+    private transient Set entries;
+
+    /**
+     * Cache the key set.
+     */
+    private transient Set keys;
+
+    /**
+     * Cache the value collection.
+     */
+    private transient Collection values;
+
+    /**
+     * Wrap a given map.
+     * @param m the map to wrap
+     * @throws NullPointerException if m is null
+     */
+    SynchronizedMap(Map m)
+    {
+      this.m = m;
+      mutex = this;
+      if (m == null)
+        throw new NullPointerException();
+    }
 
-    public UnmodifiableMap(Map m)
+    /**
+     * Called only by trusted code to specify the mutex as well as the map.
+     * @param sync the mutex
+     * @param m the map
+     */
+    SynchronizedMap(Object sync, Map m)
     {
       this.m = m;
+      mutex = sync;
     }
 
     public void clear()
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          m.clear();
+        }
     }
+
     public boolean containsKey(Object key)
     {
-      return m.containsKey(key);
+      synchronized (mutex)
+        {
+          return m.containsKey(key);
+        }
     }
+
     public boolean containsValue(Object value)
     {
-      return m.containsValue(value);
+      synchronized (mutex)
+        {
+          return m.containsValue(value);
+        }
     }
 
     // This is one of the ickiest cases of nesting I've ever seen. It just
-    // means "return an UnmodifiableSet, except that the iterator() method
-    // returns an UnmodifiableIterator whos next() method returns an
-    // unmodifiable wrapper around its normal return value".
+    // means "return a SynchronizedSet, except that the iterator() method
+    // returns an SynchronizedIterator whose next() method returns a
+    // synchronized wrapper around its normal return value".
     public Set entrySet()
     {
-      return new UnmodifiableSet(m.entrySet())
-      {
-	public Iterator iterator()
-	{
-	  return new UnmodifiableIterator(c.iterator())
-	  {
-	    public Object next()
-	    {
-	      final Map.Entry e = (Map.Entry) super.next();
-	      return new Map.Entry()
-	      {
-		public Object getKey()
-		{
-		  return e.getKey();
-		}
-		public Object getValue()
-		{
-		  return e.getValue();
-		}
-		public Object setValue(Object value)
-		{
-		  throw new UnsupportedOperationException();
-		}
-		public int hashCode()
-		{
-		  return e.hashCode();
-		}
-		public boolean equals(Object o)
-		{
-		  return e.equals(o);
-		}
-	      };
-	    }
-	  };
-	}
-      };
+      // Define this here to spare some nesting.
+      class SynchronizedMapEntry implements Map.Entry
+      {
+        final Map.Entry e;
+        SynchronizedMapEntry(Object o)
+        {
+          e = (Map.Entry) o;
+        }
+        public boolean equals(Object o)
+        {
+          synchronized (mutex)
+            {
+              return e.equals(o);
+            }
+        }
+        public Object getKey()
+        {
+          synchronized (mutex)
+            {
+              return e.getKey();
+            }
+        }
+        public Object getValue()
+        {
+          synchronized (mutex)
+            {
+              return e.getValue();
+            }
+        }
+        public int hashCode()
+        {
+          synchronized (mutex)
+            {
+              return e.hashCode();
+            }
+        }
+        public Object setValue(Object value)
+        {
+          synchronized (mutex)
+            {
+              return e.setValue(value);
+            }
+        }
+        public String toString()
+        {
+          synchronized (mutex)
+            {
+              return e.toString();
+            }
+        }
+      } // class SynchronizedMapEntry
+
+      // Now the actual code.
+      if (entries == null)
+        synchronized (mutex)
+          {
+            entries = new SynchronizedSet(mutex, m.entrySet())
+            {
+              public Iterator iterator()
+              {
+                synchronized (super.mutex)
+                  {
+                    return new SynchronizedIterator(super.mutex, c.iterator())
+                    {
+                      public Object next()
+                      {
+                        synchronized (super.mutex)
+                          {
+                            return new SynchronizedMapEntry(super.next());
+                          }
+                      }
+                    };
+                  }
+              }
+            };
+          }
+      return entries;
     }
+
     public boolean equals(Object o)
     {
-      return m.equals(o);
+      synchronized (mutex)
+        {
+          return m.equals(o);
+        }
     }
+
     public Object get(Object key)
     {
-      return m.get(key);
-    }
-    public Object put(Object key, Object value)
-    {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return m.get(key);
+        }
     }
+
     public int hashCode()
     {
-      return m.hashCode();
+      synchronized (mutex)
+        {
+          return m.hashCode();
+        }
     }
+
     public boolean isEmpty()
     {
-      return m.isEmpty();
+      synchronized (mutex)
+        {
+          return m.isEmpty();
+        }
     }
+
     public Set keySet()
     {
-      return new UnmodifiableSet(m.keySet());
+      if (keys == null)
+        synchronized (mutex)
+          {
+            keys = new SynchronizedSet(mutex, m.keySet());
+          }
+      return keys;
     }
-    public void putAll(Map m)
+
+    public Object put(Object key, Object value)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return m.put(key, value);
+        }
     }
+
+    public void putAll(Map map)
+    {
+      synchronized (mutex)
+        {
+          m.putAll(map);
+        }
+    }
+
     public Object remove(Object o)
     {
-      throw new UnsupportedOperationException();
+      synchronized (mutex)
+        {
+          return m.remove(o);
+        }
     }
+
     public int size()
     {
-      return m.size();
+      synchronized (mutex)
+        {
+          return m.size();
+        }
     }
-    public Collection values()
+
+    public String toString()
     {
-      return new UnmodifiableCollection(m.values());
+      synchronized (mutex)
+        {
+          return m.toString();
+        }
     }
-    public String toString()
+
+    public Collection values()
     {
-      return m.toString();
+      if (values == null)
+        synchronized (mutex)
+          {
+            values = new SynchronizedCollection(mutex, m.values());
+          }
+      return values;
     }
-  }
+  } // class SynchronizedMap
 
-  private static class UnmodifiableSortedMap extends UnmodifiableMap
-    implements SortedMap
+  /**
+   * Returns a synchronized (thread-safe) set wrapper backed by the given
+   * set. Notice that element access through the iterator is thread-safe, but
+   * if the set can be structurally modified (adding or removing elements)
+   * then you should synchronize around the iteration to avoid
+   * non-deterministic behavior:<br>
+   * <pre>
+   * Set s = Collections.synchronizedSet(new Set(...));
+   * ...
+   * synchronized (s)
+   *   {
+   *     Iterator i = s.iterator();
+   *     while (i.hasNext())
+   *       foo(i.next());
+   *   }
+   * </pre><p>
+   *
+   * The returned Set implements Serializable, but can only be serialized if
+   * the set it wraps is likewise Serializable.
+   *
+   * @param s the set to wrap
+   * @return a synchronized view of the set
+   * @see Serializable
+   */
+  public static Set synchronizedSet(Set s)
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    private SortedMap sm;
+    return new SynchronizedSet(s);
+  }
 
-    public UnmodifiableSortedMap(SortedMap sm)
+  /**
+   * The implementation of {@link #synchronizedSet(Set)}. This class
+   * name is required for compatibility with Sun's JDK serializability.
+   * Package visible, so that sets such as Hashtable.keySet()
+   * can specify which object to synchronize on.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  static class SynchronizedSet extends SynchronizedCollection
+    implements Set
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 487447009682186044L;
+
+    /**
+     * Wrap a given set.
+     * @param s the set to wrap
+     * @throws NullPointerException if s is null
+     */
+    SynchronizedSet(Set s)
     {
-      super(sm);
-      this.sm = sm;
+      super(s);
     }
 
-    public Comparator comparator()
+    /**
+     * Called only by trusted code to specify the mutex as well as the set.
+     * @param sync the mutex
+     * @param s the set
+     */
+    SynchronizedSet(Object sync, Set s)
     {
-      return sm.comparator();
+      super(sync, s);
     }
-    public Object firstKey()
+
+    public boolean equals(Object o)
     {
-      return sm.firstKey();
+      synchronized (mutex)
+        {
+          return c.equals(o);
+        }
     }
-    public Object lastKey()
+
+    public int hashCode()
     {
-      return sm.lastKey();
+      synchronized (mutex)
+        {
+          return c.hashCode();
+        }
     }
-    public SortedMap headMap(Object toKey)
+  } // class SynchronizedSet
+
+  /**
+   * Returns a synchronized (thread-safe) sorted map wrapper backed by the
+   * given map. Notice that element access through the collection views,
+   * subviews, and their iterators are thread-safe, but if the map can be
+   * structurally modified (adding or removing elements) then you should
+   * synchronize around the iteration to avoid non-deterministic behavior:<br>
+   * <pre>
+   * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
+   * ...
+   * Set s = m.keySet(); // safe outside a synchronized block
+   * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
+   * Set s2 = m2.keySet(); // safe outside a synchronized block
+   * synchronized (m) // synch on m, not m2, s or s2
+   *   {
+   *     Iterator i = s.iterator();
+   *     while (i.hasNext())
+   *       foo(i.next());
+   *     i = s2.iterator();
+   *     while (i.hasNext())
+   *       bar(i.next());
+   *   }
+   * </pre><p>
+   *
+   * The returned SortedMap implements Serializable, but can only be
+   * serialized if the map it wraps is likewise Serializable.
+   *
+   * @param m the sorted map to wrap
+   * @return a synchronized view of the sorted map
+   * @see Serializable
+   */
+  public static SortedMap synchronizedSortedMap(SortedMap m)
+  {
+    return new SynchronizedSortedMap(m);
+  }
+
+  /**
+   * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class SynchronizedSortedMap extends SynchronizedMap
+    implements SortedMap
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -8798146769416483793L;
+
+    /**
+     * The wrapped map; stored both here and in the superclass to avoid
+     * excessive casting.
+     * @serial the wrapped map
+     */
+    private final SortedMap sm;
+
+    /**
+     * Wrap a given map.
+     * @param sm the map to wrap
+     * @throws NullPointerException if sm is null
+     */
+    SynchronizedSortedMap(SortedMap sm)
     {
-      return new UnmodifiableSortedMap(sm.headMap(toKey));
+      super(sm);
+      this.sm = sm;
     }
-    public SortedMap tailMap(Object fromKey)
+
+    /**
+     * Called only by trusted code to specify the mutex as well as the map.
+     * @param sync the mutex
+     * @param sm the map
+     */
+    SynchronizedSortedMap(Object sync, SortedMap sm)
     {
-      return new UnmodifiableSortedMap(sm.tailMap(fromKey));
+      super(sync, sm);
+      this.sm = sm;
     }
-    public SortedMap subMap(Object fromKey, Object toKey)
+
+    public Comparator comparator()
     {
-      return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
+      synchronized (mutex)
+        {
+          return sm.comparator();
+        }
     }
-  }
-
-  // All the "Synchronized" wrapper objects include a "sync" field which
-  // specifies what object to synchronize on. That way, nested wrappers such as
-  // UnmodifiableMap.keySet synchronize on the right things.
 
-  private static class SynchronizedIterator implements Iterator
-  {
-    Object sync;
-    private Iterator i;
+    public Object firstKey()
+    {
+      synchronized (mutex)
+        {
+          return sm.firstKey();
+        }
+    }
 
-    public SynchronizedIterator(Object sync, Iterator i)
+    public SortedMap headMap(Object toKey)
     {
-      this.sync = sync;
-      this.i = i;
+      synchronized (mutex)
+        {
+          return new SynchronizedSortedMap(mutex, sm.headMap(toKey));
+        }
     }
 
-    public Object next()
+    public Object lastKey()
     {
-      synchronized(sync)
-      {
-	return i.next();
-      }
+      synchronized (mutex)
+        {
+          return sm.lastKey();
+        }
     }
-    public boolean hasNext()
+
+    public SortedMap subMap(Object fromKey, Object toKey)
     {
-      synchronized(sync)
-      {
-	return i.hasNext();
-      }
+      synchronized (mutex)
+        {
+          return new SynchronizedSortedMap(mutex, sm.subMap(fromKey, toKey));
+        }
     }
-    public void remove()
+
+    public SortedMap tailMap(Object fromKey)
     {
-      synchronized(sync)
-      {
-	i.remove();
-      }
+      synchronized (mutex)
+        {
+          return new SynchronizedSortedMap(mutex, sm.tailMap(fromKey));
+        }
     }
+  } // class SynchronizedSortedMap
+
+  /**
+   * Returns a synchronized (thread-safe) sorted set wrapper backed by the
+   * given set. Notice that element access through the iterator and through
+   * subviews are thread-safe, but if the set can be structurally modified
+   * (adding or removing elements) then you should synchronize around the
+   * iteration to avoid non-deterministic behavior:<br>
+   * <pre>
+   * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
+   * ...
+   * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
+   * synchronized (s) // synch on s, not s2
+   *   {
+   *     Iterator i = s2.iterator();
+   *     while (i.hasNext())
+   *       foo(i.next());
+   *   }
+   * </pre><p>
+   *
+   * The returned SortedSet implements Serializable, but can only be
+   * serialized if the set it wraps is likewise Serializable.
+   *
+   * @param s the sorted set to wrap
+   * @return a synchronized view of the sorted set
+   * @see Serializable
+   */
+  public static SortedSet synchronizedSortedSet(SortedSet s)
+  {
+    return new SynchronizedSortedSet(s);
   }
 
-  private static class SynchronizedListIterator extends SynchronizedIterator
-    implements ListIterator
+  /**
+   * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class SynchronizedSortedSet extends SynchronizedSet
+    implements SortedSet
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    private ListIterator li;
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 8695801310862127406L;
+
+    /**
+     * The wrapped set; stored both here and in the superclass to avoid
+     * excessive casting.
+     * @serial the wrapped set
+     */
+    private final SortedSet ss;
+
+    /**
+     * Wrap a given set.
+     * @param ss the set to wrap
+     * @throws NullPointerException if ss is null
+     */
+    SynchronizedSortedSet(SortedSet ss)
+    {
+      super(ss);
+      this.ss = ss;
+    }
 
-    public SynchronizedListIterator(Object sync, ListIterator li)
+    /**
+     * Called only by trusted code to specify the mutex as well as the set.
+     * @param sync the mutex
+     * @param l the list
+     */
+    SynchronizedSortedSet(Object sync, SortedSet ss)
     {
-      super(sync, li);
-      this.li = li;
+      super(sync, ss);
+      this.ss = ss;
     }
 
-    public boolean hasPrevious()
+    public Comparator comparator()
     {
-      synchronized(sync)
-      {
-	return li.hasPrevious();
-      }
+      synchronized (mutex)
+        {
+          return ss.comparator();
+        }
     }
-    public Object previous()
+
+    public Object first()
     {
-      synchronized(sync)
-      {
-	return li.previous();
-      }
+      synchronized (mutex)
+        {
+          return ss.first();
+        }
     }
-    public int nextIndex()
+
+    public SortedSet headSet(Object toElement)
     {
-      synchronized(sync)
-      {
-	return li.nextIndex();
-      }
+      synchronized (mutex)
+        {
+          return new SynchronizedSortedSet(mutex, ss.headSet(toElement));
+        }
     }
-    public int previousIndex()
+
+    public Object last()
     {
-      synchronized(sync)
-      {
-	return li.previousIndex();
-      }
+      synchronized (mutex)
+        {
+          return ss.last();
+        }
     }
-    public void add(Object o)
+
+    public SortedSet subSet(Object fromElement, Object toElement)
     {
-      synchronized(sync)
-      {
-	li.add(o);
-      }
+      synchronized (mutex)
+        {
+          return new SynchronizedSortedSet(mutex,
+                                           ss.subSet(fromElement, toElement));
+        }
     }
-    public void set(Object o)
+
+    public SortedSet tailSet(Object fromElement)
     {
-      synchronized(sync)
-      {
-	li.set(o);
-      }
+      synchronized (mutex)
+        {
+          return new SynchronizedSortedSet(mutex, ss.tailSet(fromElement));
+        }
     }
-  }
+  } // class SynchronizedSortedSet
 
   /**
-   * Package visible, so that collections such as the one for
-   * Hashtable.values() can specify which object to synchronize on.
+   * Returns an unmodifiable view of the given collection. This allows
+   * "read-only" access, although changes in the backing collection show up
+   * in this view. Attempts to modify the collection directly or via iterators
+   * will fail with {@link UnsupportedOperationException}.
+   * <p>
+   *
+   * Since the collection might be a List or a Set, and those have incompatible
+   * equals and hashCode requirements, this relies on Object's implementation
+   * rather than passing those calls on to the wrapped collection. The returned
+   * Collection implements Serializable, but can only be serialized if
+   * the collection it wraps is likewise Serializable.
+   *
+   * @param c the collection to wrap
+   * @return a read-only view of the collection
+   * @see Serializable
    */
-  static class SynchronizedCollection implements Collection,
-    Serializable
+  public static Collection unmodifiableCollection(Collection c)
   {
-    Object sync;
-    Collection c;
+    return new UnmodifiableCollection(c);
+  }
 
-    public SynchronizedCollection(Collection c)
-    {
-      this.sync = this;
-      this.c = c;
-    }
-    public SynchronizedCollection(Object sync, Collection c)
+  /**
+   * The implementation of {@link #unmodifiableCollection(Collection)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableCollection
+    implements Collection, Serializable
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = 1820017752578914078L;
+
+    /**
+     * The wrapped collection. Package visible for use by subclasses.
+     * @serial the real collection
+     */
+    final Collection c;
+
+    /**
+     * Wrap a given collection.
+     * @param c the collection to wrap
+     * @throws NullPointerException if c is null
+     */
+    UnmodifiableCollection(Collection c)
     {
       this.c = c;
-      this.sync = sync;
+      if (c == null)
+        throw new NullPointerException();
     }
 
     public boolean add(Object o)
     {
-      synchronized(sync)
-      {
-	return c.add(o);
-      }
+      throw new UnsupportedOperationException();
     }
-    public boolean addAll(Collection col)
+
+    public boolean addAll(Collection c)
     {
-      synchronized(sync)
-      {
-	return c.addAll(col);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public void clear()
     {
-      synchronized(sync)
-      {
-	c.clear();
-      }
+      throw new UnsupportedOperationException();
     }
+
     public boolean contains(Object o)
     {
-      synchronized(sync)
-      {
-	return c.contains(o);
-      }
+      return c.contains(o);
     }
+
     public boolean containsAll(Collection c1)
     {
-      synchronized(sync)
-      {
-	return c.containsAll(c1);
-      }
+      return c.containsAll(c1);
     }
+
     public boolean isEmpty()
     {
-      synchronized(sync)
-      {
-	return c.isEmpty();
-      }
+      return c.isEmpty();
     }
+
     public Iterator iterator()
     {
-      synchronized(sync)
-      {
-	return new SynchronizedIterator(sync, c.iterator());
-      }
+      return new UnmodifiableIterator(c.iterator());
     }
+
     public boolean remove(Object o)
     {
-      synchronized(sync)
-      {
-	return c.remove(o);
-      }
+      throw new UnsupportedOperationException();
     }
-    public boolean removeAll(Collection col)
+
+    public boolean removeAll(Collection c)
     {
-      synchronized(sync)
-      {
-	return c.removeAll(col);
-      }
+      throw new UnsupportedOperationException();
     }
-    public boolean retainAll(Collection col)
+
+    public boolean retainAll(Collection c)
     {
-      synchronized(sync)
-      {
-	return c.retainAll(col);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public int size()
     {
-      synchronized(sync)
-      {
-	return c.size();
-      }
+      return c.size();
     }
+
     public Object[] toArray()
     {
-      synchronized(sync)
-      {
-	return c.toArray();
-      }
+      return c.toArray();
     }
-    public Object[] toArray(Object[]a)
+
+    public Object[] toArray(Object[] a)
     {
-      synchronized(sync)
-      {
-	return c.toArray(a);
-      }
+      return c.toArray(a);
     }
+
     public String toString()
     {
-      synchronized(sync)
-      {
-	return c.toString();
-      }
+      return c.toString();
     }
-  }
+  } // class UnmodifiableCollection
 
-  private static class SynchronizedList extends SynchronizedCollection
-    implements List
+  /**
+   * The implementation of the various iterator methods in the
+   * unmodifiable classes.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableIterator implements Iterator
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    List l;
+    /**
+     * The wrapped iterator.
+     */
+    private final Iterator i;
 
-    public SynchronizedList(Object sync, List l)
+    /**
+     * Only trusted code creates a wrapper.
+     * @param i the wrapped iterator
+     */
+    UnmodifiableIterator(Iterator i)
     {
-      super(sync, l);
-      this.l = l;
+      this.i = i;
+    }
+
+    public Object next()
+    {
+      return i.next();
+    }
+
+    public boolean hasNext()
+    {
+      return i.hasNext();
     }
-    public SynchronizedList(List l)
+
+    public void remove()
+    {
+      throw new UnsupportedOperationException();
+    }
+  } // class UnmodifiableIterator
+
+  /**
+   * Returns an unmodifiable view of the given list. This allows
+   * "read-only" access, although changes in the backing list show up
+   * in this view. Attempts to modify the list directly, via iterators, or
+   * via sublists, will fail with {@link UnsupportedOperationException}.
+   * <p>
+   *
+   * The returned List implements Serializable, but can only be serialized if
+   * the list it wraps is likewise Serializable. In addition, if the wrapped
+   * list implements RandomAccess, this does too.
+   *
+   * @param l the list to wrap
+   * @return a read-only view of the list
+   * @see Serializable
+   * @see RandomAccess
+   */
+  public static List unmodifiableList(List l)
+  {
+    if (l instanceof RandomAccess)
+      return new UnmodifiableRandomAccessList(l);
+    return new UnmodifiableList(l);
+  }
+
+  /**
+   * The implementation of {@link #unmodifiableList(List)} for sequential
+   * lists. This class name is required for compatibility with Sun's JDK
+   * serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableList extends UnmodifiableCollection
+    implements List
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -283967356065247728L;
+
+
+    /**
+     * The wrapped list; stored both here and in the superclass to avoid
+     * excessive casting. Package visible for use by subclass.
+     * @serial the wrapped list
+     */
+    final List list;
+
+    /**
+     * Wrap a given list.
+     * @param l the list to wrap
+     * @throws NullPointerException if l is null
+     */
+    UnmodifiableList(List l)
     {
       super(l);
-      this.l = l;
+      list = l;
     }
 
     public void add(int index, Object o)
     {
-      synchronized(sync)
-      {
-	l.add(index, o);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public boolean addAll(int index, Collection c)
     {
-      synchronized(sync)
-      {
-	return l.addAll(index, c);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public boolean equals(Object o)
     {
-      synchronized(sync)
-      {
-	return l.equals(o);
-      }
+      return list.equals(o);
     }
+
     public Object get(int index)
     {
-      synchronized(sync)
-      {
-	return l.get(index);
-      }
+      return list.get(index);
     }
+
     public int hashCode()
     {
-      synchronized(sync)
-      {
-	return l.hashCode();
-      }
+      return list.hashCode();
     }
+
     public int indexOf(Object o)
     {
-      synchronized(sync)
-      {
-	return l.indexOf(o);
-      }
+      return list.indexOf(o);
     }
+
     public int lastIndexOf(Object o)
     {
-      synchronized(sync)
-      {
-	return l.lastIndexOf(o);
-      }
+      return list.lastIndexOf(o);
     }
+
     public ListIterator listIterator()
     {
-      synchronized(sync)
-      {
-	return new SynchronizedListIterator(sync, l.listIterator());
-      }
+      return new UnmodifiableListIterator(list.listIterator());
     }
+
     public ListIterator listIterator(int index)
     {
-      synchronized(sync)
-      {
-	return new SynchronizedListIterator(sync, l.listIterator(index));
-      }
+      return new UnmodifiableListIterator(list.listIterator(index));
     }
+
     public Object remove(int index)
     {
-      synchronized(sync)
-      {
-	return l.remove(index);
-      }
-    }
-    public boolean remove(Object o)
-    {
-      synchronized(sync)
-      {
-	return l.remove(o);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public Object set(int index, Object o)
     {
-      synchronized(sync)
-      {
-	return l.set(index, o);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public List subList(int fromIndex, int toIndex)
     {
-      synchronized(sync)
-      {
-	return new SynchronizedList(l.subList(fromIndex, toIndex));
-      }
+      return unmodifiableList(list.subList(fromIndex, toIndex));
     }
-  }
+  } // class UnmodifiableList
 
   /**
-   * Package visible, so that sets such as the one for Hashtable.keySet()
-   * can specify which object to synchronize on.
+   * The implementation of {@link #unmodifiableList(List)} for random-access
+   * lists. This class name is required for compatibility with Sun's JDK
+   * serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
    */
-  static class SynchronizedSet extends SynchronizedCollection
-    implements Set
+  private static final class UnmodifiableRandomAccessList
+    extends UnmodifiableList implements RandomAccess
   {
-    public SynchronizedSet(Object sync, Set s)
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -2542308836966382001L;
+
+    /**
+     * Wrap a given list.
+     * @param l the list to wrap
+     * @throws NullPointerException if l is null
+     */
+    UnmodifiableRandomAccessList(List l)
     {
-      super(sync, s);
-    }
-    public SynchronizedSet(Set s)
-    {
-      super(s);
-    }
-
-    public boolean equals(Object o)
-    {
-      synchronized(sync)
-      {
-	return c.equals(o);
-      }
-    }
-    public int hashCode()
-    {
-      synchronized(sync)
-      {
-	return c.hashCode();
-      }
+      super(l);
     }
-  }
+  } // class UnmodifiableRandomAccessList
 
-  private static class SynchronizedSortedSet extends SynchronizedSet
-    implements SortedSet
+  /**
+   * The implementation of {@link UnmodifiableList#listIterator()}.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class UnmodifiableListIterator
+    extends UnmodifiableIterator implements ListIterator
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    private SortedSet ss;
-
-    public SynchronizedSortedSet(Object sync, SortedSet ss)
-    {
-      super(sync, ss);
-      this.ss = ss;
-    }
-    public SynchronizedSortedSet(SortedSet ss)
+    /**
+     * The wrapped iterator, stored both here and in the superclass to
+     * avoid excessive casting.
+     */
+    private final ListIterator li;
+
+    /**
+     * Only trusted code creates a wrapper.
+     * @param li the wrapped iterator
+     */
+    UnmodifiableListIterator(ListIterator li)
     {
-      super(ss);
-      this.ss = ss;
+      super(li);
+      this.li = li;
     }
 
-    public Comparator comparator()
+    public void add(Object o)
     {
-      synchronized(sync)
-      {
-	return ss.comparator();
-      }
+      throw new UnsupportedOperationException();
     }
-    public Object first()
+
+    public boolean hasPrevious()
     {
-      synchronized(sync)
-      {
-	return ss.first();
-      }
+      return li.hasPrevious();
     }
-    public Object last()
+
+    public int nextIndex()
     {
-      synchronized(sync)
-      {
-	return ss.last();
-      }
+      return li.nextIndex();
     }
-    public SortedSet headSet(Object toElement)
+
+    public Object previous()
     {
-      synchronized(sync)
-      {
-	return new SynchronizedSortedSet(sync, ss.headSet(toElement));
-      }
+      return li.previous();
     }
-    public SortedSet tailSet(Object fromElement)
+
+    public int previousIndex()
     {
-      synchronized(sync)
-      {
-	return new SynchronizedSortedSet(sync, ss.tailSet(fromElement));
-      }
+      return li.previousIndex();
     }
-    public SortedSet subSet(Object fromElement, Object toElement)
+
+    public void set(Object o)
     {
-      synchronized(sync)
-      {
-	return new SynchronizedSortedSet(sync,
-					 ss.subSet(fromElement, toElement));
-      }
+      throw new UnsupportedOperationException();
     }
-  }
+  } // class UnmodifiableListIterator
 
-  private static class SynchronizedMap implements Map, Serializable
+  /**
+   * Returns an unmodifiable view of the given map. This allows "read-only"
+   * access, although changes in the backing map show up in this view.
+   * Attempts to modify the map directly, or via collection views or their
+   * iterators will fail with {@link UnsupportedOperationException}.
+   * <p>
+   *
+   * The returned Map implements Serializable, but can only be serialized if
+   * the map it wraps is likewise Serializable.
+   *
+   * @param m the map to wrap
+   * @return a read-only view of the map
+   * @see Serializable
+   */
+  public static Map unmodifiableMap(Map m)
   {
-    Object sync;
-    Map m;
+    return new UnmodifiableMap(m);
+  }
 
-    public SynchronizedMap(Object sync, Map m)
-    {
-      this.sync = sync;
-      this.m = m;
-    }
-    public SynchronizedMap(Map m)
+  /**
+   * The implementation of {@link #unmodifiableMap(Map)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableMap implements Map, Serializable
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -1034234728574286014L;
+
+    /**
+     * The wrapped map.
+     * @serial the real map
+     */
+    private final Map m;
+
+    /**
+     * Cache the entry set.
+     */
+    private transient Set entries;
+
+    /**
+     * Cache the key set.
+     */
+    private transient Set keys;
+
+    /**
+     * Cache the value collection.
+     */
+    private transient Collection values;
+
+    /**
+     * Wrap a given map.
+     * @param m the map to wrap
+     * @throws NullPointerException if m is null
+     */
+    UnmodifiableMap(Map m)
     {
       this.m = m;
-      this.sync = this;
+      if (m == null)
+        throw new NullPointerException();
     }
 
     public void clear()
     {
-      synchronized(sync)
-      {
-	m.clear();
-      }
+      throw new UnsupportedOperationException();
     }
+
     public boolean containsKey(Object key)
     {
-      synchronized(sync)
-      {
-	return m.containsKey(key);
-      }
+      return m.containsKey(key);
     }
+
     public boolean containsValue(Object value)
     {
-      synchronized(sync)
-      {
-	return m.containsValue(value);
-      }
+      return m.containsValue(value);
     }
 
-    // This is one of the ickiest cases of nesting I've ever seen. It just
-    // means "return a SynchronizedSet, except that the iterator() method
-    // returns an SynchronizedIterator whos next() method returns a
-    // synchronized wrapper around its normal return value".
     public Set entrySet()
     {
-      synchronized(sync)
+      if (entries == null)
+        entries = new UnmodifiableEntrySet(m.entrySet());
+      return entries;
+    }
+
+    /**
+     * The implementation of {@link UnmodifiableMap#entrySet()}. This class
+     * name is required for compatibility with Sun's JDK serializability.
+     *
+     * @author Eric Blake <ebb9@email.byu.edu>
+     */
+    private static final class UnmodifiableEntrySet extends UnmodifiableSet
+      implements Serializable
+    {
+      /**
+       * Compatible with JDK 1.4.
+       */
+      private static final long serialVersionUID = 7854390611657943733L;
+
+      /**
+       * Wrap a given set.
+       * @param s the set to wrap
+       */
+      UnmodifiableEntrySet(Set s)
+      {
+        super(s);
+      }
+
+      // The iterator must return unmodifiable map entries.
+      public Iterator iterator()
       {
-	return new SynchronizedSet(sync, m.entrySet())
+        return new UnmodifiableIterator(c.iterator())
 	{
-	  public Iterator iterator()
-	  {
-	    synchronized(SynchronizedMap.this.sync)
+          public Object next()
+          {
+            final Map.Entry e = (Map.Entry) super.next();
+            return new Map.Entry()
 	    {
-	      return new SynchronizedIterator(SynchronizedMap.this.sync,
-					      c.iterator())
-	      {
-		public Object next()
-		{
-		  synchronized(SynchronizedMap.this.sync)
-		  {
-		    final Map.Entry e = (Map.Entry) super.next();
-		    return new Map.Entry()
-		    {
-		      public Object getKey()
-		      {
-			synchronized(SynchronizedMap.this.sync)
-			{
-			  return e.getKey();
-			}
-		      }
-		      public Object getValue()
-		      {
-			synchronized(SynchronizedMap.this.sync)
-			{
-			  return e.getValue();
-			}
-		      }
-		      public Object setValue(Object value)
-		      {
-			synchronized(SynchronizedMap.this.sync)
-			{
-			  return e.setValue(value);
-			}
-		      }
-		      public int hashCode()
-		      {
-			synchronized(SynchronizedMap.this.sync)
-			{
-			  return e.hashCode();
-			}
-		      }
-		      public boolean equals(Object o)
-		      {
-			synchronized(SynchronizedMap.this.sync)
-			{
-			  return e.equals(o);
-			}
-		      }
-		    };
-		  }
-		}
-	      };
-	    }
-	  }
+              public boolean equals(Object o)
+              {
+                return e.equals(o);
+              }
+              public Object getKey()
+              {
+                return e.getKey();
+              }
+              public Object getValue()
+              {
+                return e.getValue();
+              }
+              public int hashCode()
+              {
+                return e.hashCode();
+              }
+              public Object setValue(Object value)
+              {
+                throw new UnsupportedOperationException();
+              }
+              public String toString()
+              {
+                return e.toString();
+              }
+	    };
+          }
 	};
       }
-    }
+    } // class UnmodifiableEntrySet
+
     public boolean equals(Object o)
     {
-      synchronized(sync)
-      {
-	return m.equals(o);
-      }
+      return m.equals(o);
     }
+
     public Object get(Object key)
     {
-      synchronized(sync)
-      {
-	return m.get(key);
-      }
+      return m.get(key);
     }
+
     public Object put(Object key, Object value)
     {
-      synchronized(sync)
-      {
-	return m.put(key, value);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public int hashCode()
     {
-      synchronized(sync)
-      {
-	return m.hashCode();
-      }
+      return m.hashCode();
     }
+
     public boolean isEmpty()
     {
-      synchronized(sync)
-      {
-	return m.isEmpty();
-      }
+      return m.isEmpty();
     }
+
     public Set keySet()
     {
-      synchronized(sync)
-      {
-	return new SynchronizedSet(sync, m.keySet());
-      }
+      if (keys == null)
+        keys = new UnmodifiableSet(m.keySet());
+      return keys;
     }
-    public void putAll(Map map)
+
+    public void putAll(Map m)
     {
-      synchronized(sync)
-      {
-	m.putAll(map);
-      }
+      throw new UnsupportedOperationException();
     }
+
     public Object remove(Object o)
     {
-      synchronized(sync)
-      {
-	return m.remove(o);
-      }
+      throw new UnsupportedOperationException();
     }
 
     public int size()
     {
-      synchronized(sync)
-      {
-	return m.size();
-      }
+      return m.size();
     }
-    public Collection values()
+
+    public String toString()
     {
-      synchronized(sync)
-      {
-	return new SynchronizedCollection(sync, m.values());
-      }
+      return m.toString();
     }
-    public String toString()
+
+    public Collection values()
     {
-      synchronized(sync)
-      {
-	return m.toString();
-      }
+      if (values == null)
+        values = new UnmodifiableCollection(m.values());
+      return values;
     }
+  } // class UnmodifiableMap
+
+  /**
+   * Returns an unmodifiable view of the given set. This allows
+   * "read-only" access, although changes in the backing set show up
+   * in this view. Attempts to modify the set directly or via iterators
+   * will fail with {@link UnsupportedOperationException}.
+   * <p>
+   *
+   * The returned Set implements Serializable, but can only be serialized if
+   * the set it wraps is likewise Serializable.
+   *
+   * @param s the set to wrap
+   * @return a read-only view of the set
+   * @see Serializable
+   */
+  public static Set unmodifiableSet(Set s)
+  {
+    return new UnmodifiableSet(s);
   }
 
-  private static class SynchronizedSortedMap extends SynchronizedMap
-    implements SortedMap
+  /**
+   * The implementation of {@link #unmodifiableSet(Set)}. This class
+   * name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableSet extends UnmodifiableCollection
+    implements Set
   {
-    // This is stored both here and in the superclass, to avoid excessive
-    // casting.
-    private SortedMap sm;
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -9215047833775013803L;
+
+    /**
+     * Wrap a given set.
+     * @param s the set to wrap
+     * @throws NullPointerException if s is null
+     */
+    UnmodifiableSet(Set s)
+    {
+      super(s);
+    }
 
-    public SynchronizedSortedMap(Object sync, SortedMap sm)
+    public boolean equals(Object o)
     {
-      super(sync, sm);
-      this.sm = sm;
+      return c.equals(o);
+    }
+
+    public int hashCode()
+    {
+      return c.hashCode();
     }
-    public SynchronizedSortedMap(SortedMap sm)
+  } // class UnmodifiableSet
+
+  /**
+   * Returns an unmodifiable view of the given sorted map. This allows
+   * "read-only" access, although changes in the backing map show up in this
+   * view. Attempts to modify the map directly, via subviews, via collection
+   * views, or iterators, will fail with {@link UnsupportedOperationException}.
+   * <p>
+   *
+   * The returned SortedMap implements Serializable, but can only be
+   * serialized if the map it wraps is likewise Serializable.
+   *
+   * @param m the map to wrap
+   * @return a read-only view of the map
+   * @see Serializable
+   */
+  public static SortedMap unmodifiableSortedMap(SortedMap m)
+  {
+    return new UnmodifiableSortedMap(m);
+  }
+
+  /**
+   * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableSortedMap extends UnmodifiableMap
+    implements SortedMap
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -8806743815996713206L;
+
+    /**
+     * The wrapped map; stored both here and in the superclass to avoid
+     * excessive casting.
+     * @serial the wrapped map
+     */
+    private final SortedMap sm;
+
+    /**
+     * Wrap a given map.
+     * @param sm the map to wrap
+     * @throws NullPointerException if sm is null
+     */
+    UnmodifiableSortedMap(SortedMap sm)
     {
       super(sm);
       this.sm = sm;
@@ -1827,36 +3350,114 @@ public class Collections
 
     public Comparator comparator()
     {
-      synchronized(sync)
-      {
-	return sm.comparator();
-      }
+      return sm.comparator();
     }
+
     public Object firstKey()
     {
-      synchronized(sync)
-      {
-	return sm.firstKey();
-      }
+      return sm.firstKey();
+    }
+
+    public SortedMap headMap(Object toKey)
+    {
+      return new UnmodifiableSortedMap(sm.headMap(toKey));
     }
+
     public Object lastKey()
     {
-      synchronized(sync)
-      {
-	return sm.lastKey();
-      }
+      return sm.lastKey();
     }
-    public SortedMap headMap(Object toKey)
+
+    public SortedMap subMap(Object fromKey, Object toKey)
     {
-      return new SynchronizedSortedMap(sync, sm.headMap(toKey));
+      return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
     }
+
     public SortedMap tailMap(Object fromKey)
     {
-      return new SynchronizedSortedMap(sync, sm.tailMap(fromKey));
+      return new UnmodifiableSortedMap(sm.tailMap(fromKey));
     }
-    public SortedMap subMap(Object fromKey, Object toKey)
+  } // class UnmodifiableSortedMap
+
+  /**
+   * Returns an unmodifiable view of the given sorted set. This allows
+   * "read-only" access, although changes in the backing set show up
+   * in this view. Attempts to modify the set directly, via subsets, or via
+   * iterators, will fail with {@link UnsupportedOperationException}.
+   * <p>
+   *
+   * The returns SortedSet implements Serializable, but can only be
+   * serialized if the set it wraps is likewise Serializable.
+   *
+   * @param s the set to wrap
+   * @return a read-only view of the set
+   * @see Serializable
+   */
+  public static SortedSet unmodifiableSortedSet(SortedSet s)
+  {
+    return new UnmodifiableSortedSet(s);
+  }
+
+  /**
+   * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
+   * class name is required for compatibility with Sun's JDK serializability.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static class UnmodifiableSortedSet extends UnmodifiableSet
+    implements SortedSet
+  {
+    /**
+     * Compatible with JDK 1.4.
+     */
+    private static final long serialVersionUID = -4929149591599911165L;
+
+    /**
+     * The wrapped set; stored both here and in the superclass to avoid
+     * excessive casting.
+     * @serial the wrapped set
+     */
+    private SortedSet ss;
+
+    /**
+     * Wrap a given set.
+     * @param ss the set to wrap
+     * @throws NullPointerException if ss is null
+     */
+    UnmodifiableSortedSet(SortedSet ss)
     {
-      return new SynchronizedSortedMap(sync, sm.subMap(fromKey, toKey));
+      super(ss);
+      this.ss = ss;
     }
-  }
-}
+
+    public Comparator comparator()
+    {
+      return ss.comparator();
+    }
+
+    public Object first()
+    {
+      return ss.first();
+    }
+
+    public SortedSet headSet(Object toElement)
+    {
+      return new UnmodifiableSortedSet(ss.headSet(toElement));
+    }
+
+    public Object last()
+    {
+      return ss.last();
+    }
+
+    public SortedSet subSet(Object fromElement, Object toElement)
+    {
+      return new UnmodifiableSortedSet(ss.subSet(fromElement, toElement));
+    }
+
+    public SortedSet tailSet(Object fromElement)
+    {
+      return new UnmodifiableSortedSet(ss.tailSet(fromElement));
+    }
+  } // class UnmodifiableSortedSet
+} // class Collections