--- jsr166/src/main/java/util/Collections.java	2006/01/11 00:57:12	1.20
+++ jsr166/src/main/java/util/Collections.java	2006/04/20 20:34:37	1.26
@@ -6,7 +6,6 @@
  */
 
 package java.util;
-import java.util.*; // for javadoc (till 6280605 is fixed)
 import java.io.Serializable;
 import java.io.ObjectOutputStream;
 import java.io.IOException;
@@ -44,7 +43,7 @@ import java.lang.reflect.Array;
  *
  * @author  Josh Bloch
  * @author  Neal Gafter
- * @version %I%, %G%
+ * @version 1.104, 03/21/06
  * @see	    Collection
  * @see	    Set
  * @see	    List
@@ -169,13 +168,13 @@ public class Collections {
     /**
      * Searches the specified list for the specified object using the binary
      * search algorithm.  The list must be sorted into ascending order
-     * according to the <i>natural ordering</i> of its elements (as by the
-     * <tt>sort(List)</tt> method, above) prior to making this call.  If it is
-     * not sorted, the results are undefined.  If the list contains multiple
-     * elements equal to the specified object, there is no guarantee which one
-     * will be found.<p>
+     * according to the {@linkplain Comparable natural ordering} of its
+     * elements (as by the {@link #sort(List)} method) prior to making this
+     * call.  If it is not sorted, the results are undefined.  If the list
+     * contains multiple elements equal to the specified object, there is no
+     * guarantee which one will be found.
      *
-     * This method runs in log(n) time for a "random access" list (which
+     * <p>This method runs in log(n) time for a "random access" list (which
      * provides near-constant-time positional access).  If the specified list
      * does not implement the {@link RandomAccess} interface and is large,
      * this method will do an iterator-based binary search that performs
@@ -187,16 +186,14 @@ public class Collections {
      *	       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
-     *	       element greater than the key, or <tt>list.size()</tt>, if all
+     *	       element greater than the key, or <tt>list.size()</tt> if all
      *	       elements in the list are less than the specified key.  Note
      *	       that this guarantees that the return value will be &gt;= 0 if
      *	       and only if the key is found.
      * @throws ClassCastException if the list contains elements that are not
      *	       <i>mutually comparable</i> (for example, strings and
-     *	       integers), or the search key in not mutually comparable
+     *	       integers), or the search key is not mutually comparable
      *	       with the elements of the list.
-     * @see    Comparable
-     * @see #sort(List)
      */
     public static <T>
     int binarySearch(List<? extends Comparable<? super T>> list, T key) {
@@ -213,7 +210,7 @@ public class Collections {
 	int high = list.size()-1;
 
 	while (low <= high) {
-	    int mid = (low + high) >> 1;
+	    int mid = (low + high) >>> 1;
 	    Comparable<? super T> midVal = list.get(mid);
 	    int cmp = midVal.compareTo(key);
 
@@ -235,7 +232,7 @@ public class Collections {
         ListIterator<? extends Comparable<? super T>> i = list.listIterator();
 
         while (low <= high) {
-            int mid = (low + high) >> 1;
+            int mid = (low + high) >>> 1;
             Comparable<? super T> midVal = get(i, mid);
             int cmp = midVal.compareTo(key);
 
@@ -271,13 +268,14 @@ public class Collections {
     /**
      * Searches the specified list for the specified object using the binary
      * search algorithm.  The list must be sorted into ascending order
-     * according to the specified comparator (as by the <tt>Sort(List,
-     * Comparator)</tt> method, above), prior to making this call.  If it is
+     * according to the specified comparator (as by the
+     * {@link #sort(List, Comparator) sort(List, Comparator)}
+     * method), prior to making this call.  If it is
      * not sorted, the results are undefined.  If the list contains multiple
      * elements equal to the specified object, there is no guarantee which one
-     * will be found.<p>
+     * will be found.
      *
-     * This method runs in log(n) time for a "random access" list (which
+     * <p>This method runs in log(n) time for a "random access" list (which
      * provides near-constant-time positional access).  If the specified list
      * does not implement the {@link RandomAccess} interface and is large,
      * this method will do an iterator-based binary search that performs
@@ -285,23 +283,21 @@ public class Collections {
      *
      * @param  list the list to be searched.
      * @param  key the key to be searched for.
-     * @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.
+     * @param  c the comparator by which the list is ordered.
+     *         A <tt>null</tt> value indicates that the elements'
+     *	       {@linkplain Comparable natural ordering} should be used.
      * @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
-     *	       element greater than the key, or <tt>list.size()</tt>, if all
+     *	       element greater than the key, or <tt>list.size()</tt> if all
      *	       elements in the list are less than the specified key.  Note
      *	       that this guarantees that the return value will be &gt;= 0 if
      *	       and only if the key is found.
      * @throws ClassCastException if the list contains elements that are not
      *	       <i>mutually comparable</i> using the specified comparator,
-     *	       or the search key in not mutually comparable with the
+     *	       or the search key is not mutually comparable with the
      *	       elements of the list using this comparator.
-     * @see    Comparable
-     * @see #sort(List, Comparator)
      */
     public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
         if (c==null)
@@ -318,7 +314,7 @@ public class Collections {
 	int high = l.size()-1;
 
 	while (low <= high) {
-	    int mid = (low + high) >> 1;
+	    int mid = (low + high) >>> 1;
 	    T midVal = l.get(mid);
 	    int cmp = c.compare(midVal, key);
 
@@ -338,7 +334,7 @@ public class Collections {
         ListIterator<? extends T> i = l.listIterator();
 
         while (low <= high) {
-            int mid = (low + high) >> 1;
+            int mid = (low + high) >>> 1;
             T midVal = get(i, mid);
             int cmp = c.compare(midVal, key);
 
@@ -1067,7 +1063,7 @@ public class Collections {
 	private static final long serialVersionUID = -9215047833775013803L;
 
 	UnmodifiableSet(Set<? extends E> s)	{super(s);}
-	public boolean equals(Object o) {return c.equals(o);}
+	public boolean equals(Object o) {return o == this || c.equals(o);}
 	public int hashCode() 		{return c.hashCode();}
     }
 
@@ -1152,7 +1148,7 @@ public class Collections {
 	    this.list = list;
 	}
 
-	public boolean equals(Object o) {return list.equals(o);}
+	public boolean equals(Object o) {return o == this || list.equals(o);}
 	public int hashCode() 		{return list.hashCode();}
 
 	public E get(int index) {return list.get(index);}
@@ -1320,7 +1316,7 @@ public class Collections {
 	    return values;
 	}
 
-	public boolean equals(Object o) {return m.equals(o);}
+	public boolean equals(Object o) {return o == this || m.equals(o);}
 	public int hashCode()           {return m.hashCode();}
         public String toString()        {return m.toString();}
 
@@ -1543,8 +1539,8 @@ public class Collections {
 	// use serialVersionUID from JDK 1.2.2 for interoperability
 	private static final long serialVersionUID = 3053995032091335093L;
 
-	final Collection<E> c;	   // Backing Collection
-	final Object	   mutex;  // Object on which to synchronize
+	final Collection<E> c;  // Backing Collection
+	final Object mutex;     // Object on which to synchronize
 
 	SynchronizedCollection(Collection<E> c) {
             if (c==null)
@@ -2318,7 +2314,7 @@ public class Collections {
 
         CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
 
-        public boolean equals(Object o) { return c.equals(o); }
+        public boolean equals(Object o) { return o == this || c.equals(o); }
         public int hashCode()           { return c.hashCode(); }
     }
 
@@ -2421,7 +2417,7 @@ public class Collections {
             this.list = list;
         }
 
-        public boolean equals(Object o)  { return list.equals(o); }
+        public boolean equals(Object o)  { return o == this || list.equals(o); }
         public int hashCode()            { return list.hashCode(); }
         public E get(int index)          { return list.get(index); }
         public E remove(int index)       { return list.remove(index); }
@@ -2575,7 +2571,7 @@ public class Collections {
         public void clear()                    { m.clear(); }
         public Set<K> keySet()                 { return m.keySet(); }
         public Collection<V> values()          { return m.values(); }
-        public boolean equals(Object o)        { return m.equals(o);  }
+        public boolean equals(Object o)        { return o == this || m.equals(o); }
         public int hashCode()                  { return m.hashCode(); }
         public String toString()               { return m.toString(); }
 
@@ -3320,6 +3316,8 @@ public class Collections {
         public int compare(Comparable<Object> c1, Comparable<Object> c2) {
             return c2.compareTo(c1);
         }
+
+        private Object readResolve() { return reverseOrder(); }
     }
 
     /**
@@ -3338,7 +3336,7 @@ public class Collections {
      */
     public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
         if (cmp == null)
-            return new ReverseComparator();  // Unchecked warning!!
+            return reverseOrder();
 
         return new ReverseComparator2<T>(cmp);
     }
@@ -3561,43 +3559,39 @@ public class Collections {
         implements Set<E>, Serializable
     {
         private final Map<E, Boolean> m;  // The backing map
-        private transient Set<E> keySet;  // Its keySet
+        private transient Set<E> s;       // Its keySet
 
         SetFromMap(Map<E, Boolean> map) {
             if (!map.isEmpty())
                 throw new IllegalArgumentException("Map is non-empty");
             m = map;
-            keySet = map.keySet();
+            s = map.keySet();
         }
 
+        public void clear()               {        m.clear(); }
         public int size()                 { return m.size(); }
         public boolean isEmpty()          { return m.isEmpty(); }
         public boolean contains(Object o) { return m.containsKey(o); }
-        public Iterator<E> iterator()     { return keySet.iterator(); }
-        public Object[] toArray()         { return keySet.toArray(); }
-        public <T> T[] toArray(T[] a)     { return keySet.toArray(a); }
-        public boolean add(E e) {
-            return m.put(e, Boolean.TRUE) == null;
-        }
         public boolean remove(Object o)   { return m.remove(o) != null; }
-
-        public boolean removeAll(Collection<?> c) {
-            return keySet.removeAll(c);
-        }
-        public boolean retainAll(Collection<?> c) {
-            return keySet.retainAll(c);
-        }
-        public void clear()               { m.clear(); }
-        public boolean equals(Object o)   { return keySet.equals(o); }
-        public int hashCode()             { return keySet.hashCode(); }
+        public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
+        public Iterator<E> iterator()     { return s.iterator(); }
+        public Object[] toArray()         { return s.toArray(); }
+        public <T> T[] toArray(T[] a)     { return s.toArray(a); }
+        public String toString()          { return s.toString(); }
+        public int hashCode()             { return s.hashCode(); }
+        public boolean equals(Object o)   { return o == this || s.equals(o); }
+        public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
+        public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
+        public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
+	// addAll is the only inherited implementation
 
         private static final long serialVersionUID = 2454657854757543876L;
 
-        private void readObject(java.io.ObjectInputStream s)
+        private void readObject(java.io.ObjectInputStream stream)
             throws IOException, ClassNotFoundException
         {
-            s.defaultReadObject();
-            keySet = m.keySet();
+            stream.defaultReadObject();
+            s = m.keySet();
         }
     }
 
@@ -3608,6 +3602,12 @@ public class Collections {
      * view can be useful when you would like to use a method
      * requiring a <tt>Queue</tt> but you need Lifo ordering.
      *
+     * <p>Each method invocation on the queue returned by this method
+     * results in exactly one method invocation on the backing deque, with
+     * one exception.  The {@link Queue#addAll addAll} method is
+     * implemented as a sequence of {@link Deque#addFirst addFirst}
+     * invocations on the backing deque.
+     *
      * @param deque the deque
      * @return the queue
      * @since  1.6
@@ -3620,20 +3620,25 @@ public class Collections {
         implements Queue<E>, Serializable {
 	private static final long serialVersionUID = 1802017725587941708L;
         private final Deque<E> q;
-        AsLIFOQueue(Deque<E> q)            { this.q = q; }
-        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(); }
-        public E element()                 { return q.getFirst(); }
-        public int size()                  { return q.size(); }
-        public boolean isEmpty()           { return q.isEmpty(); }
-        public boolean contains(Object o)  { return q.contains(o); }
-        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 remove(Object o)    { return q.remove(o); }
-        public void clear()                { q.clear(); }
+        AsLIFOQueue(Deque<E> q)           { this.q = q; }
+        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(); }
+        public E element()                { return q.getFirst(); }
+        public void clear()               {        q.clear(); }
+        public int size()                 { return q.size(); }
+        public boolean isEmpty()          { return q.isEmpty(); }
+        public boolean contains(Object o) { return q.contains(o); }
+        public boolean remove(Object o)   { return q.remove(o); }
+        public Iterator<E> iterator()     { return q.iterator(); }
+        public Object[] toArray()         { return q.toArray(); }
+        public <T> T[] toArray(T[] a)     { return q.toArray(a); }
+        public String toString()          { return q.toString(); }
+	public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
+	public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
+	public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
+	// We use inherited addAll; forwarding addAll would be wrong
     }
 }