ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/Collections.java
(Generate patch)

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.20 by jsr166, Wed Jan 11 00:57:12 2006 UTC vs.
Revision 1.25 by jsr166, Thu Apr 20 17:04:35 2006 UTC

# Line 6 | Line 6
6   */
7  
8   package java.util;
9 – import java.util.*; // for javadoc (till 6280605 is fixed)
9   import java.io.Serializable;
10   import java.io.ObjectOutputStream;
11   import java.io.IOException;
# Line 169 | Line 168 | public class Collections {
168      /**
169       * Searches the specified list for the specified object using the binary
170       * search algorithm.  The list must be sorted into ascending order
171 <     * according to the <i>natural ordering</i> of its elements (as by the
172 <     * <tt>sort(List)</tt> method, above) prior to making this call.  If it is
173 <     * not sorted, the results are undefined.  If the list contains multiple
174 <     * elements equal to the specified object, there is no guarantee which one
175 <     * will be found.<p>
171 >     * according to the {@linkplain Comparable natural ordering} of its
172 >     * elements (as by the {@link #sort(List)} method) prior to making this
173 >     * call.  If it is not sorted, the results are undefined.  If the list
174 >     * contains multiple elements equal to the specified object, there is no
175 >     * guarantee which one will be found.
176       *
177 <     * This method runs in log(n) time for a "random access" list (which
177 >     * <p>This method runs in log(n) time for a "random access" list (which
178       * provides near-constant-time positional access).  If the specified list
179       * does not implement the {@link RandomAccess} interface and is large,
180       * this method will do an iterator-based binary search that performs
# Line 187 | Line 186 | public class Collections {
186       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
187       *         <i>insertion point</i> is defined as the point at which the
188       *         key would be inserted into the list: the index of the first
189 <     *         element greater than the key, or <tt>list.size()</tt>, if all
189 >     *         element greater than the key, or <tt>list.size()</tt> if all
190       *         elements in the list are less than the specified key.  Note
191       *         that this guarantees that the return value will be &gt;= 0 if
192       *         and only if the key is found.
193       * @throws ClassCastException if the list contains elements that are not
194       *         <i>mutually comparable</i> (for example, strings and
195 <     *         integers), or the search key in not mutually comparable
195 >     *         integers), or the search key is not mutually comparable
196       *         with the elements of the list.
198 –     * @see    Comparable
199 –     * @see #sort(List)
197       */
198      public static <T>
199      int binarySearch(List<? extends Comparable<? super T>> list, T key) {
# Line 213 | Line 210 | public class Collections {
210          int high = list.size()-1;
211  
212          while (low <= high) {
213 <            int mid = (low + high) >> 1;
213 >            int mid = (low + high) >>> 1;
214              Comparable<? super T> midVal = list.get(mid);
215              int cmp = midVal.compareTo(key);
216  
# Line 235 | Line 232 | public class Collections {
232          ListIterator<? extends Comparable<? super T>> i = list.listIterator();
233  
234          while (low <= high) {
235 <            int mid = (low + high) >> 1;
235 >            int mid = (low + high) >>> 1;
236              Comparable<? super T> midVal = get(i, mid);
237              int cmp = midVal.compareTo(key);
238  
# Line 271 | Line 268 | public class Collections {
268      /**
269       * Searches the specified list for the specified object using the binary
270       * search algorithm.  The list must be sorted into ascending order
271 <     * according to the specified comparator (as by the <tt>Sort(List,
272 <     * Comparator)</tt> method, above), prior to making this call.  If it is
271 >     * according to the specified comparator (as by the
272 >     * {@link #sort(List, Comparator) sort(List, Comparator)}
273 >     * method), prior to making this call.  If it is
274       * not sorted, the results are undefined.  If the list contains multiple
275       * elements equal to the specified object, there is no guarantee which one
276 <     * will be found.<p>
276 >     * will be found.
277       *
278 <     * This method runs in log(n) time for a "random access" list (which
278 >     * <p>This method runs in log(n) time for a "random access" list (which
279       * provides near-constant-time positional access).  If the specified list
280       * does not implement the {@link RandomAccess} interface and is large,
281       * this method will do an iterator-based binary search that performs
# Line 285 | Line 283 | public class Collections {
283       *
284       * @param  list the list to be searched.
285       * @param  key the key to be searched for.
286 <     * @param  c the comparator by which the list is ordered.  A
287 <     *        <tt>null</tt> value indicates that the elements' <i>natural
288 <     *        ordering</i> should be used.
286 >     * @param  c the comparator by which the list is ordered.
287 >     *         A <tt>null</tt> value indicates that the elements'
288 >     *         {@linkplain Comparable natural ordering} should be used.
289       * @return the index of the search key, if it is contained in the list;
290       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
291       *         <i>insertion point</i> is defined as the point at which the
292       *         key would be inserted into the list: the index of the first
293 <     *         element greater than the key, or <tt>list.size()</tt>, if all
293 >     *         element greater than the key, or <tt>list.size()</tt> if all
294       *         elements in the list are less than the specified key.  Note
295       *         that this guarantees that the return value will be &gt;= 0 if
296       *         and only if the key is found.
297       * @throws ClassCastException if the list contains elements that are not
298       *         <i>mutually comparable</i> using the specified comparator,
299 <     *         or the search key in not mutually comparable with the
299 >     *         or the search key is not mutually comparable with the
300       *         elements of the list using this comparator.
303 –     * @see    Comparable
304 –     * @see #sort(List, Comparator)
301       */
302      public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
303          if (c==null)
# Line 318 | Line 314 | public class Collections {
314          int high = l.size()-1;
315  
316          while (low <= high) {
317 <            int mid = (low + high) >> 1;
317 >            int mid = (low + high) >>> 1;
318              T midVal = l.get(mid);
319              int cmp = c.compare(midVal, key);
320  
# Line 338 | Line 334 | public class Collections {
334          ListIterator<? extends T> i = l.listIterator();
335  
336          while (low <= high) {
337 <            int mid = (low + high) >> 1;
337 >            int mid = (low + high) >>> 1;
338              T midVal = get(i, mid);
339              int cmp = c.compare(midVal, key);
340  
# Line 1067 | Line 1063 | public class Collections {
1063          private static final long serialVersionUID = -9215047833775013803L;
1064  
1065          UnmodifiableSet(Set<? extends E> s)     {super(s);}
1066 <        public boolean equals(Object o) {return c.equals(o);}
1066 >        public boolean equals(Object o) {return o == this || c.equals(o);}
1067          public int hashCode()           {return c.hashCode();}
1068      }
1069  
# Line 1152 | Line 1148 | public class Collections {
1148              this.list = list;
1149          }
1150  
1151 <        public boolean equals(Object o) {return list.equals(o);}
1151 >        public boolean equals(Object o) {return o == this || list.equals(o);}
1152          public int hashCode()           {return list.hashCode();}
1153  
1154          public E get(int index) {return list.get(index);}
# Line 1320 | Line 1316 | public class Collections {
1316              return values;
1317          }
1318  
1319 <        public boolean equals(Object o) {return m.equals(o);}
1319 >        public boolean equals(Object o) {return o == this || m.equals(o);}
1320          public int hashCode()           {return m.hashCode();}
1321          public String toString()        {return m.toString();}
1322  
# Line 1543 | Line 1539 | public class Collections {
1539          // use serialVersionUID from JDK 1.2.2 for interoperability
1540          private static final long serialVersionUID = 3053995032091335093L;
1541  
1542 <        final Collection<E> c;     // Backing Collection
1543 <        final Object       mutex;  // Object on which to synchronize
1542 >        final Collection<E> c;  // Backing Collection
1543 >        final Object mutex;     // Object on which to synchronize
1544  
1545          SynchronizedCollection(Collection<E> c) {
1546              if (c==null)
# Line 2318 | Line 2314 | public class Collections {
2314  
2315          CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2316  
2317 <        public boolean equals(Object o) { return c.equals(o); }
2317 >        public boolean equals(Object o) { return o == this || c.equals(o); }
2318          public int hashCode()           { return c.hashCode(); }
2319      }
2320  
# Line 2421 | Line 2417 | public class Collections {
2417              this.list = list;
2418          }
2419  
2420 <        public boolean equals(Object o)  { return list.equals(o); }
2420 >        public boolean equals(Object o)  { return o == this || list.equals(o); }
2421          public int hashCode()            { return list.hashCode(); }
2422          public E get(int index)          { return list.get(index); }
2423          public E remove(int index)       { return list.remove(index); }
# Line 2575 | Line 2571 | public class Collections {
2571          public void clear()                    { m.clear(); }
2572          public Set<K> keySet()                 { return m.keySet(); }
2573          public Collection<V> values()          { return m.values(); }
2574 <        public boolean equals(Object o)        { return m.equals(o);  }
2574 >        public boolean equals(Object o)        { return o == this || m.equals(o); }
2575          public int hashCode()                  { return m.hashCode(); }
2576          public String toString()               { return m.toString(); }
2577  
# Line 3320 | Line 3316 | public class Collections {
3316          public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3317              return c2.compareTo(c1);
3318          }
3319 +
3320 +        private Object readResolve() { return reverseOrder(); }
3321      }
3322  
3323      /**
# Line 3338 | Line 3336 | public class Collections {
3336       */
3337      public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3338          if (cmp == null)
3339 <            return new ReverseComparator();  // Unchecked warning!!
3339 >            return reverseOrder();
3340  
3341          return new ReverseComparator2<T>(cmp);
3342      }
# Line 3561 | Line 3559 | public class Collections {
3559          implements Set<E>, Serializable
3560      {
3561          private final Map<E, Boolean> m;  // The backing map
3562 <        private transient Set<E> keySet;  // Its keySet
3562 >        private transient Set<E> s;       // Its keySet
3563  
3564          SetFromMap(Map<E, Boolean> map) {
3565              if (!map.isEmpty())
3566                  throw new IllegalArgumentException("Map is non-empty");
3567              m = map;
3568 <            keySet = map.keySet();
3568 >            s = map.keySet();
3569          }
3570  
3571 +        public void clear()               {        m.clear(); }
3572          public int size()                 { return m.size(); }
3573          public boolean isEmpty()          { return m.isEmpty(); }
3574          public boolean contains(Object o) { return m.containsKey(o); }
3576 –        public Iterator<E> iterator()     { return keySet.iterator(); }
3577 –        public Object[] toArray()         { return keySet.toArray(); }
3578 –        public <T> T[] toArray(T[] a)     { return keySet.toArray(a); }
3579 –        public boolean add(E e) {
3580 –            return m.put(e, Boolean.TRUE) == null;
3581 –        }
3575          public boolean remove(Object o)   { return m.remove(o) != null; }
3576 <
3577 <        public boolean removeAll(Collection<?> c) {
3578 <            return keySet.removeAll(c);
3579 <        }
3580 <        public boolean retainAll(Collection<?> c) {
3581 <            return keySet.retainAll(c);
3582 <        }
3583 <        public void clear()               { m.clear(); }
3584 <        public boolean equals(Object o)   { return keySet.equals(o); }
3585 <        public int hashCode()             { return keySet.hashCode(); }
3576 >        public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3577 >        public Iterator<E> iterator()     { return s.iterator(); }
3578 >        public Object[] toArray()         { return s.toArray(); }
3579 >        public <T> T[] toArray(T[] a)     { return s.toArray(a); }
3580 >        public String toString()          { return s.toString(); }
3581 >        public int hashCode()             { return s.hashCode(); }
3582 >        public boolean equals(Object o)   { return o == this || s.equals(o); }
3583 >        public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3584 >        public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
3585 >        public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
3586 >        // addAll is the only inherited implementation
3587  
3588          private static final long serialVersionUID = 2454657854757543876L;
3589  
3590 <        private void readObject(java.io.ObjectInputStream s)
3590 >        private void readObject(java.io.ObjectInputStream stream)
3591              throws IOException, ClassNotFoundException
3592          {
3593 <            s.defaultReadObject();
3594 <            keySet = m.keySet();
3593 >            stream.defaultReadObject();
3594 >            s = m.keySet();
3595          }
3596      }
3597  
# Line 3608 | Line 3602 | public class Collections {
3602       * view can be useful when you would like to use a method
3603       * requiring a <tt>Queue</tt> but you need Lifo ordering.
3604       *
3605 +     * <p>Each method invocation on the queue returned by this method
3606 +     * results in exactly one method invocation on the backing deque, with
3607 +     * one exception.  The {@link Queue#addAll addAll} method is
3608 +     * implemented as a sequence of {@link Deque#addFirst addFirst}
3609 +     * invocations on the backing deque.
3610 +     *
3611       * @param deque the deque
3612       * @return the queue
3613       * @since  1.6
# Line 3620 | Line 3620 | public class Collections {
3620          implements Queue<E>, Serializable {
3621          private static final long serialVersionUID = 1802017725587941708L;
3622          private final Deque<E> q;
3623 <        AsLIFOQueue(Deque<E> q)            { this.q = q; }
3624 <        public boolean add(E e)            { q.addFirst(e); return true; }
3625 <        public boolean offer(E e)          { return q.offerFirst(e); }
3626 <        public E poll()                    { return q.pollFirst(); }
3627 <        public E remove()                  { return q.removeFirst(); }
3628 <        public E peek()                    { return q.peekFirst(); }
3629 <        public E element()                 { return q.getFirst(); }
3630 <        public int size()                  { return q.size(); }
3631 <        public boolean isEmpty()           { return q.isEmpty(); }
3632 <        public boolean contains(Object o)  { return q.contains(o); }
3633 <        public Iterator<E> iterator()      { return q.iterator(); }
3634 <        public Object[] toArray()          { return q.toArray(); }
3635 <        public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3636 <        public boolean remove(Object o)    { return q.remove(o); }
3637 <        public void clear()                { q.clear(); }
3623 >        AsLIFOQueue(Deque<E> q)           { this.q = q; }
3624 >        public boolean add(E e)           { q.addFirst(e); return true; }
3625 >        public boolean offer(E e)         { return q.offerFirst(e); }
3626 >        public E poll()                   { return q.pollFirst(); }
3627 >        public E remove()                 { return q.removeFirst(); }
3628 >        public E peek()                   { return q.peekFirst(); }
3629 >        public E element()                { return q.getFirst(); }
3630 >        public void clear()               {        q.clear(); }
3631 >        public int size()                 { return q.size(); }
3632 >        public boolean isEmpty()          { return q.isEmpty(); }
3633 >        public boolean contains(Object o) { return q.contains(o); }
3634 >        public boolean remove(Object o)   { return q.remove(o); }
3635 >        public Iterator<E> iterator()     { return q.iterator(); }
3636 >        public Object[] toArray()         { return q.toArray(); }
3637 >        public <T> T[] toArray(T[] a)     { return q.toArray(a); }
3638 >        public String toString()          { return q.toString(); }
3639 >        public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3640 >        public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
3641 >        public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
3642 >        // We use inherited addAll; forwarding addAll would be wrong
3643      }
3644   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines