--- jsr166/src/main/java/util/Collections.java	2004/12/28 12:14:07	1.1
+++ jsr166/src/main/java/util/Collections.java	2005/08/11 08:52:39	1.13
@@ -1,11 +1,12 @@
 /*
  * %W% %E%
  *
- * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  */
 
 package java.util;
+import java.util.*; // for javadoc (till 6280605 is fixed)
 import java.io.Serializable;
 import java.io.ObjectOutputStream;
 import java.io.IOException;
@@ -37,7 +38,7 @@ import java.lang.reflect.Array;
  * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
  * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
  *
- * <p>This class is a member of the 
+ * <p>This class is a member of the
  * <a href="{@docRoot}/../guide/collections/index.html">
  * Java Collections Framework</a>.
  *
@@ -63,7 +64,7 @@ public class Collections {
      * two implementations, one of which is appropriate for RandomAccess
      * lists, the other for "sequential."  Often, the random access variant
      * yields better performance on small sequential access lists.  The
-     * tuning  parameters below determine the cutoff point for what constitutes
+     * tuning parameters below determine the cutoff point for what constitutes
      * a "small" sequential access list for each algorithm.  The values below
      * were empirically determined to work well for LinkedList. Hopefully
      * they should be reasonable for other sequential access List
@@ -97,7 +98,7 @@ public class Collections {
      * The sorting algorithm is a modified mergesort (in which the merge is
      * omitted if the highest element in the low sublist is less than the
      * lowest element in the high sublist).  This algorithm offers guaranteed
-     * n log(n) performance. 
+     * n log(n) performance.
      *
      * This implementation dumps the specified list into an array, sorts
      * the array, and iterates over the list resetting each element
@@ -135,7 +136,7 @@ public class Collections {
      * The sorting algorithm is a modified mergesort (in which the merge is
      * omitted if the highest element in the low sublist is less than the
      * lowest element in the high sublist).  This algorithm offers guaranteed
-     * n log(n) performance. 
+     * n log(n) performance.
      *
      * The specified list must be modifiable, but need not be resizable.
      * This implementation dumps the specified list into an array, sorts
@@ -182,7 +183,7 @@ public class Collections {
      *
      * @param  list the list to be searched.
      * @param  key the key to be searched for.
-     * @return index of the search key, if it is contained in the list;
+     * @return the index of the search key, if it is contained in the list;
      *	       otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
      *	       <i>insertion point</i> is defined as the point at which the
      *	       key would be inserted into the list: the index of the first
@@ -287,7 +288,7 @@ public class Collections {
      * @param  c the comparator by which the list is ordered.  A
      *        <tt>null</tt> value indicates that the elements' <i>natural
      *        ordering</i> should be used.
-     * @return index of the search key, if it is contained in the list;
+     * @return the index of the search key, if it is contained in the list;
      *	       otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
      *	       <i>insertion point</i> is defined as the point at which the
      *	       key would be inserted into the list: the index of the first
@@ -361,7 +362,7 @@ public class Collections {
      *
      * @param  list the list whose elements are to be reversed.
      * @throws UnsupportedOperationException if the specified list or
-     *         its list-iterator does not support the <tt>set</tt> method.
+     *         its list-iterator does not support the <tt>set</tt> operation.
      */
     public static void reverse(List<?> list) {
         int size = list.size();
@@ -405,12 +406,15 @@ public class Collections {
      *
      * @param  list the list to be shuffled.
      * @throws UnsupportedOperationException if the specified list or
-     *         its list-iterator does not support the <tt>set</tt> method.
+     *         its list-iterator does not support the <tt>set</tt> operation.
      */
     public static void shuffle(List<?> list) {
+        if (r == null) {
+            r = new Random();
+        }
         shuffle(list, r);
     }
-    private static Random r = new Random();
+    private static Random r;
 
     /**
      * Randomly permute the specified list using the specified source of
@@ -569,7 +573,7 @@ public class Collections {
 	Iterator<? extends T> i = coll.iterator();
 	T candidate = i.next();
 
-        while(i.hasNext()) {
+        while (i.hasNext()) {
 	    T next = i.next();
 	    if (next.compareTo(candidate) < 0)
 		candidate = next;
@@ -606,7 +610,7 @@ public class Collections {
 	Iterator<? extends T> i = coll.iterator();
 	T candidate = i.next();
 
-        while(i.hasNext()) {
+        while (i.hasNext()) {
 	    T next = i.next();
 	    if (comp.compare(next, candidate) < 0)
 		candidate = next;
@@ -639,7 +643,7 @@ public class Collections {
 	Iterator<? extends T> i = coll.iterator();
 	T candidate = i.next();
 
-        while(i.hasNext()) {
+        while (i.hasNext()) {
 	    T next = i.next();
 	    if (next.compareTo(candidate) > 0)
 		candidate = next;
@@ -676,7 +680,7 @@ public class Collections {
 	Iterator<? extends T> i = coll.iterator();
 	T candidate = i.next();
 
-        while(i.hasNext()) {
+        while (i.hasNext()) {
 	    T next = i.next();
 	    if (comp.compare(next, candidate) > 0)
 		candidate = next;
@@ -712,7 +716,7 @@ public class Collections {
      *     Collections.rotate(l.subList(1, 4), -1);
      * </pre>
      * The resulting list is <tt>[a, c, d, b, e]</tt>.
-     * 
+     *
      * <p>To move more than one element forward, increase the absolute value
      * of the rotation distance.  To move elements backward, use a positive
      * shift distance.
@@ -736,7 +740,7 @@ public class Collections {
      *        constraints on this value; it may be zero, negative, or
      *        greater than <tt>list.size()</tt>.
      * @throws UnsupportedOperationException if the specified list or
-     *         its list-iterator does not support the <tt>set</tt> method.
+     *         its list-iterator does not support the <tt>set</tt> operation.
      * @since 1.4
      */
     public static void rotate(List<?> list, int distance) {
@@ -772,7 +776,7 @@ public class Collections {
     private static void rotate2(List<?> list, int distance) {
         int size = list.size();
         if (size == 0)
-            return; 
+            return;
         int mid =  -distance % size;
         if (mid < 0)
             mid += size;
@@ -799,7 +803,7 @@ public class Collections {
      *         <tt>e</tt> such that
      *         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
      * @throws UnsupportedOperationException if the specified list or
-     *         its list-iterator does not support the <tt>set</tt> method.
+     *         its list-iterator does not support the <tt>set</tt> operation.
      * @since  1.4
      */
     public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
@@ -970,7 +974,7 @@ public class Collections {
      * that the backing collection is a set or a list.<p>
      *
      * The returned collection will be serializable if the specified collection
-     * is serializable. 
+     * is serializable.
      *
      * @param  c the collection for which an unmodifiable view is to be
      *	       returned.
@@ -1014,7 +1018,7 @@ public class Collections {
 	    };
         }
 
-	public boolean add(E o){
+	public boolean add(E e){
 	    throw new UnsupportedOperationException();
         }
 	public boolean remove(Object o) {
@@ -1046,12 +1050,11 @@ public class Collections {
      * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
      *
      * The returned set will be serializable if the specified set
-     * is serializable. 
+     * is serializable.
      *
      * @param  s the set for which an unmodifiable view is to be returned.
      * @return an unmodifiable view of the specified set.
      */
-
     public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
 	return new UnmodifiableSet<T>(s);
     }
@@ -1078,10 +1081,10 @@ public class Collections {
      * an <tt>UnsupportedOperationException</tt>.<p>
      *
      * The returned sorted set will be serializable if the specified sorted set
-     * is serializable. 
+     * is serializable.
      *
      * @param s the sorted set for which an unmodifiable view is to be
-     *        returned. 
+     *        returned.
      * @return an unmodifiable view of the specified sorted set.
      */
     public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
@@ -1183,10 +1186,10 @@ public class Collections {
 		public void remove() {
 		    throw new UnsupportedOperationException();
                 }
-		public void set(E o) {
+		public void set(E e) {
 		    throw new UnsupportedOperationException();
                 }
-		public void add(E o) {
+		public void add(E e) {
 		    throw new UnsupportedOperationException();
                 }
 	    };
@@ -1252,7 +1255,7 @@ public class Collections {
      * <tt>UnsupportedOperationException</tt>.<p>
      *
      * The returned map will be serializable if the specified map
-     * is serializable. 
+     * is serializable.
      *
      * @param  m the map for which an unmodifiable view is to be returned.
      * @return an unmodifiable view of the specified map.
@@ -1288,7 +1291,7 @@ public class Collections {
 	public V remove(Object key) {
 	    throw new UnsupportedOperationException();
         }
-	public void putAll(Map<? extends K, ? extends V> t) {
+	public void putAll(Map<? extends K, ? extends V> m) {
 	    throw new UnsupportedOperationException();
         }
 	public void clear() {
@@ -1334,7 +1337,7 @@ public class Collections {
 	    private static final long serialVersionUID = 7854390611657943733L;
 
             UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
-                super((Set<Map.Entry<K,V>>)(Set)s);
+                super((Set)s);
             }
             public Iterator<Map.Entry<K,V>> iterator() {
                 return new Iterator<Map.Entry<K,V>>() {
@@ -1363,10 +1366,7 @@ public class Collections {
                 // We don't pass a to c.toArray, to avoid window of
                 // vulnerability wherein an unscrupulous multithreaded client
                 // could get his hands on raw (unwrapped) Entries from c.
-		Object[] arr =
-		    c.toArray(
-			a.length==0 ? a :
-			(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), 0));
+		Object[] arr = c.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
 
                 for (int i=0; i<arr.length; i++)
                     arr[i] = new UnmodifiableEntry<K,V>((Map.Entry<K,V>)arr[i]);
@@ -1456,10 +1456,10 @@ public class Collections {
      * an <tt>UnsupportedOperationException</tt>.<p>
      *
      * The returned sorted map will be serializable if the specified sorted map
-     * is serializable. 
+     * is serializable.
      *
      * @param m the sorted map for which an unmodifiable view is to be
-     *        returned. 
+     *        returned.
      * @return an unmodifiable view of the specified sorted map.
      */
     public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
@@ -1523,7 +1523,7 @@ public class Collections {
      * that the backing collection is a set or a list.<p>
      *
      * The returned collection will be serializable if the specified collection
-     * is serializable. 
+     * is serializable.
      *
      * @param  c the collection to be "wrapped" in a synchronized collection.
      * @return a synchronized view of the specified collection.
@@ -1577,8 +1577,8 @@ public class Collections {
             return c.iterator(); // Must be manually synched by user!
         }
 
-	public boolean add(E o) {
-	    synchronized(mutex) {return c.add(o);}
+	public boolean add(E e) {
+	    synchronized(mutex) {return c.add(e);}
         }
 	public boolean remove(Object o) {
 	    synchronized(mutex) {return c.remove(o);}
@@ -1673,7 +1673,7 @@ public class Collections {
      * sorted set when iterating over it or any of its <tt>subSet</tt>,
      * <tt>headSet</tt>, or <tt>tailSet</tt> views.
      * <pre>
-     *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
+     *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
      *      ...
      *  synchronized(s) {
      *      Iterator i = s.iterator(); // Must be in the synchronized block
@@ -1683,7 +1683,7 @@ public class Collections {
      * </pre>
      * or:
      * <pre>
-     *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
+     *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
      *  SortedSet s2 = s.headSet(foo);
      *      ...
      *  synchronized(s) {  // Note: s, not s2!!!
@@ -2007,7 +2007,7 @@ public class Collections {
 	public Set<Map.Entry<K,V>> entrySet() {
             synchronized(mutex) {
                 if (entrySet==null)
-                    entrySet = new SynchronizedSet<Map.Entry<K,V>>((Set<Map.Entry<K,V>>)m.entrySet(), mutex);
+                    entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
                 return entrySet;
             }
 	}
@@ -2045,7 +2045,7 @@ public class Collections {
      * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
      * <tt>tailMap</tt> views.
      * <pre>
-     *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
+     *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
      *      ...
      *  Set s = m.keySet();  // Needn't be in synchronized block
      *      ...
@@ -2057,7 +2057,7 @@ public class Collections {
      * </pre>
      * or:
      * <pre>
-     *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
+     *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
      *  SortedMap m2 = m.subMap(foo, bar);
      *      ...
      *  Set s2 = m2.keySet();  // Needn't be in synchronized block
@@ -2191,7 +2191,7 @@ public class Collections {
                                                       Class<E> type) {
         return new CheckedCollection<E>(c, type);
     }
- 
+
     /**
      * @serial include
      */
@@ -2236,9 +2236,9 @@ public class Collections {
             c.clear();
         }
 
-        public boolean add(E o){
-            typeCheck(o);
-            return c.add(o);
+        public boolean add(E e){
+            typeCheck(e);
+            return c.add(e);
         }
 
         public boolean addAll(Collection<? extends E> coll) {
@@ -2246,13 +2246,13 @@ public class Collections {
              * Dump coll into an array of the required type.  This serves
              * three purposes: it insulates us from concurrent changes in
              * the contents of coll, it type-checks all of the elements in
-             * coll, and it provides all-or-nothing semantics(which we
+             * coll, and it provides all-or-nothing semantics (which we
              * wouldn't get if we type-checked each element as we added it).
              */
             E[] a = null;
             try {
                 a = coll.toArray(zeroLengthElementArray());
-            } catch(ArrayStoreException e) {
+            } catch (ArrayStoreException e) {
                 throw new ClassCastException();
             }
 
@@ -2265,7 +2265,7 @@ public class Collections {
         private E[] zeroLengthElementArray = null; // Lazily initialized
 
         /*
-         * We don't need locking or volatile, because it's OK if we create 
+         * We don't need locking or volatile, because it's OK if we create
          * several zeroLengthElementArrays, and they're immutable.
          */
         E[] zeroLengthElementArray() {
@@ -2300,7 +2300,7 @@ public class Collections {
     public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
         return new CheckedSet<E>(s, type);
     }
- 
+
     /**
      * @serial include
      */
@@ -2436,7 +2436,7 @@ public class Collections {
             E[] a = null;
             try {
                 a = c.toArray(zeroLengthElementArray());
-            } catch(ArrayStoreException e) {
+            } catch (ArrayStoreException e) {
                 throw new ClassCastException();
             }
 
@@ -2456,14 +2456,14 @@ public class Collections {
                 public int previousIndex()   { return i.previousIndex(); }
                 public void remove()         { i.remove(); }
 
-                public void set(E o) {
-                    typeCheck(o);
-                    i.set(o);
+                public void set(E e) {
+                    typeCheck(e);
+                    i.set(e);
                 }
 
-                public void add(E o) {
-                    typeCheck(o);
-                    i.add(o);
+                public void add(E e) {
+                    typeCheck(e);
+                    i.add(e);
                 }
             };
         }
@@ -2582,13 +2582,13 @@ public class Collections {
             K[] keys = null;
             try {
                 keys = t.keySet().toArray(zeroLengthKeyArray());
-            } catch(ArrayStoreException e) {
+            } catch (ArrayStoreException e) {
                 throw new ClassCastException();
             }
             V[] values = null;
             try {
                 values = t.values().toArray(zeroLengthValueArray());
-            } catch(ArrayStoreException e) {
+            } catch (ArrayStoreException e) {
                 throw new ClassCastException();
             }
 
@@ -2604,7 +2604,7 @@ public class Collections {
         private V[] zeroLengthValueArray = null;
 
         /*
-         * We don't need locking or volatile, because it's OK if we create 
+         * We don't need locking or volatile, because it's OK if we create
          * several zeroLengthValueArrays, and they're immutable.
          */
         private K[] zeroLengthKeyArray() {
@@ -2658,7 +2658,7 @@ public class Collections {
                 s.clear();
             }
 
-            public boolean add(Map.Entry<K, V> o){
+            public boolean add(Map.Entry<K, V> e){
                 throw new UnsupportedOperationException();
             }
             public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
@@ -2700,8 +2700,7 @@ public class Collections {
                 // We don't pass a to s.toArray, to avoid window of
                 // vulnerability wherein an unscrupulous multithreaded client
                 // could get his hands on raw (unwrapped) Entries from s.
-                Object[] arr = s.toArray(a.length==0 ? a :
-                   (T[])Array.newInstance(a.getClass().getComponentType(), 0));
+                Object[] arr = s.toArray(a.length==0 ? a : Arrays.copyOf(a, 0));
 
                 for (int i=0; i<arr.length; i++)
                     arr[i] = new CheckedEntry<K,V>((Map.Entry<K,V>)arr[i],
@@ -3060,7 +3059,7 @@ public class Collections {
 
         final private E element;
 
-        SingletonSet(E o) {element = o;}
+        SingletonSet(E e) {element = e;}
 
         public Iterator<E> iterator() {
             return new Iterator<E>() {
@@ -3168,7 +3167,8 @@ public class Collections {
 
 	public Set<Map.Entry<K,V>> entrySet() {
 	    if (entrySet==null)
-		entrySet = singleton((Map.Entry<K,V>)new ImmutableEntry<K,V>(k, v));
+		entrySet = Collections.<Map.Entry<K,V>>singleton(
+		    new SimpleImmutableEntry<K,V>(k, v));
 	    return entrySet;
 	}
 
@@ -3178,40 +3178,6 @@ public class Collections {
 	    return values;
 	}
 
-        private static class ImmutableEntry<K,V>
-	    implements Map.Entry<K,V> {
-            final K k;
-            final V v;
-
-            ImmutableEntry(K key, V value) {
-                k = key;
-                v = value;
-            }
-
-            public K getKey()   {return k;}
-
-            public V getValue() {return v;}
-
-            public V setValue(V value) {
-                throw new UnsupportedOperationException();
-            }
-
-            public boolean equals(Object o) {
-                if (!(o instanceof Map.Entry))
-                    return false;
-                Map.Entry e = (Map.Entry)o;
-                return eq(e.getKey(), k) && eq(e.getValue(), v);
-            }
-
-            public int hashCode() {
-                return ((k==null ? 0 : k.hashCode()) ^
-                        (v==null ? 0 : v.hashCode()));
-            }
-
-            public String toString() {
-                return k+"="+v;
-            }
-        }
     }
 
     /**
@@ -3245,11 +3211,11 @@ public class Collections {
         int n;
         E element;
 
-        CopiesList(int n, E o) {
+        CopiesList(int n, E e) {
             if (n < 0)
                 throw new IllegalArgumentException("List length = " + n);
             this.n = n;
-            element = o;
+            element = e;
         }
 
         public int size() {
@@ -3324,10 +3290,10 @@ public class Collections {
     public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
         if (cmp == null)
             return new ReverseComparator();  // Unchecked warning!!
- 
+
         return new ReverseComparator2<T>(cmp);
     }
- 
+
     /**
      * @serial include
      */
@@ -3335,7 +3301,7 @@ public class Collections {
         Serializable
     {
         private static final long serialVersionUID = 4374092139857L;
- 
+
         /**
          * The comparator specified in the static factory.  This will never
          * be null, as the static factory returns a ReverseComparator
@@ -3344,12 +3310,12 @@ public class Collections {
          * @serial
          */
         private Comparator<T> cmp;
- 
+
         ReverseComparator2(Comparator<T> cmp) {
             assert cmp != null;
             this.cmp = cmp;
         }
- 
+
         public int compare(T t1, T t2) {
             return cmp.compare(t2, t1);
         }
@@ -3469,7 +3435,7 @@ public class Collections {
             c1 = c2;
             c2 = tmp;
         }
- 
+
         for (Object e : c1)
             if (c2.contains(e))
                 return false;
@@ -3493,11 +3459,11 @@ public class Collections {
      * @param a the elements to insert into <tt>c</tt>
      * @return <tt>true</tt> if the collection changed as a result of the call
      * @throws UnsupportedOperationException if <tt>c</tt> does not support
-     *         the <tt>add</tt> method
+     *         the <tt>add</tt> operation.
      * @throws NullPointerException if <tt>elements</tt> contains one or more
-     *         null values and <tt>c</tt> does not support null elements, or
+     *         null values and <tt>c</tt> does not permit null elements, or
      *         if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
-     * @throws IllegalArgumentException if some aspect of a value in
+     * @throws IllegalArgumentException if some property of a value in
      *         <tt>elements</tt> prevents it from being added to <tt>c</tt>
      * @see Collection#addAll(Collection)
      * @since 1.5
@@ -3536,6 +3502,7 @@ public class Collections {
      * @param map the backing map
      * @return the set backed by the map
      * @throws IllegalArgumentException if <tt>map</tt> is not empty
+     * @since 1.6
      */
     public static <E> Set<E> asSet(Map<E, Boolean> map) {
         return new MapAsSet<E>(map);
@@ -3591,7 +3558,7 @@ public class Collections {
      * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
      * view can be useful when you would like to use a method
      * requiring a <tt>Queue</tt> but you need Lifo ordering.
-     * @param deque the Deque
+     * @param deque the deque
      * @return the queue
      * @since  1.6
      */
@@ -3599,11 +3566,12 @@ public class Collections {
         return new AsLIFOQueue<T>(deque);
     }
 
-    static class AsLIFOQueue<E> extends AbstractQueue<E> 
+    static class AsLIFOQueue<E> extends AbstractQueue<E>
         implements Queue<E>, Serializable {
+	private static final long serialVersionUID = 1802017725587941708L;
         private final Deque<E> q;
         AsLIFOQueue(Deque<E> q)            { this.q = q; }
-        public boolean offer(E o)          { return q.offerFirst(o); }
+        public boolean offer(E e)          { return q.offerFirst(e); }
         public E poll()                    { return q.pollFirst(); }
         public E remove()                  { return q.removeFirst(); }
         public E peek()                    { return q.peekFirst(); }
@@ -3614,7 +3582,7 @@ public class Collections {
         public Iterator<E> iterator()      { return q.iterator(); }
         public Object[] toArray()          { return q.toArray(); }
         public <T> T[] toArray(T[] a)      { return q.toArray(a); }
-        public boolean add(E o)            { return q.offerFirst(o); }
+        public boolean add(E e)            { return q.offerFirst(e); }
         public boolean remove(Object o)    { return q.remove(o); }
         public void clear()                { q.clear(); }
     }