--- jsr166/src/main/java/util/Collections.java	2005/04/27 00:58:57	1.4
+++ jsr166/src/main/java/util/Collections.java	2006/01/11 00:57:12	1.20
@@ -1,11 +1,12 @@
 /*
  * %W% %E%
  *
- * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2006 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;
@@ -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
@@ -408,9 +409,12 @@ public class Collections {
      *         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;
@@ -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) {
@@ -1051,7 +1055,6 @@ public class Collections {
      * @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);
     }
@@ -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();
                 }
 	    };
@@ -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() {
@@ -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]);
@@ -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);}
@@ -2221,7 +2221,6 @@ public class Collections {
         public Object[] toArray()           { return c.toArray(); }
         public <T> T[] toArray(T[] a)       { return c.toArray(a); }
         public String toString()            { return c.toString(); }
-        public Iterator<E> iterator()       { return c.iterator(); }
         public boolean remove(Object o)     { return c.remove(o); }
         public boolean containsAll(Collection<?> coll) {
             return c.containsAll(coll);
@@ -2236,9 +2235,17 @@ public class Collections {
             c.clear();
         }
 
-        public boolean add(E o){
-            typeCheck(o);
-            return c.add(o);
+        public Iterator<E> iterator() {
+	    return new Iterator<E>() {
+		private final Iterator<E> it = c.iterator();
+		public boolean hasNext() { return it.hasNext(); }
+		public E next()          { return it.next(); }
+		public void remove()     {        it.remove(); }};
+	}
+
+	public boolean add(E e){
+            typeCheck(e);
+            return c.add(e);
         }
 
         public boolean addAll(Collection<? extends E> coll) {
@@ -2246,13 +2253,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();
             }
 
@@ -2436,7 +2443,7 @@ public class Collections {
             E[] a = null;
             try {
                 a = c.toArray(zeroLengthElementArray());
-            } catch(ArrayStoreException e) {
+            } catch (ArrayStoreException e) {
                 throw new ClassCastException();
             }
 
@@ -2456,14 +2463,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 +2589,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();
             }
 
@@ -2658,7 +2665,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 +2707,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 +3066,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>() {
@@ -3197,6 +3203,8 @@ public class Collections {
      * @see    List#addAll(int, Collection)
      */
     public static <T> List<T> nCopies(int n, T o) {
+	if (n < 0)
+	    throw new IllegalArgumentException("List length = " + n);
         return new CopiesList<T>(n, o);
     }
 
@@ -3209,14 +3217,13 @@ public class Collections {
     {
         static final long serialVersionUID = 2739099268398711800L;
 
-        int n;
-        E element;
+        final int n;
+        final E element;
 
-        CopiesList(int n, E o) {
-            if (n < 0)
-                throw new IllegalArgumentException("List length = " + n);
+        CopiesList(int n, E e) {
+	    assert n >= 0;
             this.n = n;
-            element = o;
+            element = e;
         }
 
         public int size() {
@@ -3227,12 +3234,53 @@ public class Collections {
             return n != 0 && eq(obj, element);
         }
 
+	public int indexOf(Object o) {
+	    return contains(o) ? 0 : -1;
+	}
+
+	public int lastIndexOf(Object o) {
+	    return contains(o) ? n - 1 : -1;
+	}
+
         public E get(int index) {
-            if (index<0 || index>=n)
+            if (index < 0 || index >= n)
                 throw new IndexOutOfBoundsException("Index: "+index+
                                                     ", Size: "+n);
             return element;
         }
+
+	public Object[] toArray() {
+	    final Object[] a = new Object[n];
+	    if (element != null)
+		Arrays.fill(a, 0, n, element);
+	    return a;
+	}
+
+	public <T> T[] toArray(T[] a) {
+	    final int n = this.n;
+	    if (a.length < n) {
+		a = (T[])java.lang.reflect.Array
+		    .newInstance(a.getClass().getComponentType(), n);
+		if (element != null)
+		    Arrays.fill(a, 0, n, element);
+	    } else {
+		Arrays.fill(a, 0, n, element);
+		if (a.length > n)
+		    a[n] = null;
+	    }
+	    return a;
+	}
+
+	public List<E> subList(int fromIndex, int toIndex) {
+	    if (fromIndex < 0)
+		throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
+	    if (toIndex > n)
+		throw new IndexOutOfBoundsException("toIndex = " + toIndex);
+	    if (fromIndex > toIndex)
+		throw new IllegalArgumentException("fromIndex(" + fromIndex +
+						   ") > toIndex(" + toIndex + ")");
+	    return new CopiesList(toIndex - fromIndex, element);
+	}
     }
 
     /**
@@ -3457,22 +3505,22 @@ public class Collections {
      * </pre>
      *
      * @param c the collection into which <tt>elements</tt> are to be inserted
-     * @param a the elements to insert into <tt>c</tt>
+     * @param elements 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> operation.
+     *         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
      */
-    public static <T> boolean addAll(Collection<? super T> c, T... a) {
+    public static <T> boolean addAll(Collection<? super T> c, T... elements) {
         boolean result = false;
-        for (T e : a)
-            result |= c.add(e);
+        for (T element : elements)
+            result |= c.add(element);
         return result;
     }
 
@@ -3496,25 +3544,26 @@ public class Collections {
      * to this method, and no reference to the map is retained, as illustrated
      * in the following code fragment:
      * <pre>
-     *    Set&lt;Object&gt; weakHashSet = Collections.asSet(
+     *    Set&lt;Object&gt; weakHashSet = Collections.newSetFromMap(
      *        new WeakHashMap&lt;Object, Boolean&gt;());
      * </pre>
      *
      * @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);
+    public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) {
+        return new SetFromMap<E>(map);
     }
 
-    private static class MapAsSet<E> extends AbstractSet<E>
+    private static class SetFromMap<E> extends AbstractSet<E>
         implements Set<E>, Serializable
     {
         private final Map<E, Boolean> m;  // The backing map
         private transient Set<E> keySet;  // Its keySet
 
-        MapAsSet(Map<E, Boolean> map) {
+        SetFromMap(Map<E, Boolean> map) {
             if (!map.isEmpty())
                 throw new IllegalArgumentException("Map is non-empty");
             m = map;
@@ -3558,7 +3607,8 @@ 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
      */
@@ -3568,9 +3618,11 @@ public class Collections {
 
     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 add(E e)            { q.addFirst(e); return true; }
+        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(); }
@@ -3581,7 +3633,6 @@ 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 remove(Object o)    { return q.remove(o); }
         public void clear()                { q.clear(); }
     }