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.30 by jsr166, Tue Jan 30 03:46:05 2007 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
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 39 | Line 38 | import java.lang.reflect.Array;
38   * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
39   *
40   * <p>This class is a member of the
41 < * <a href="{@docRoot}/../guide/collections/index.html">
41 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
42   * Java Collections Framework</a>.
43   *
44   * @author  Josh Bloch
# 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 3303 | Line 3299 | public class Collections {
3299       * @see Comparable
3300       */
3301      public static <T> Comparator<T> reverseOrder() {
3302 <        return (Comparator<T>) REVERSE_ORDER;
3302 >        return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3303      }
3304  
3309 –    private static final Comparator REVERSE_ORDER = new ReverseComparator();
3310 –
3305      /**
3306       * @serial include
3307       */
3308 <    private static class ReverseComparator<T>
3308 >    private static class ReverseComparator
3309          implements Comparator<Comparable<Object>>, Serializable {
3310  
3311          // use serialVersionUID from JDK 1.2.2 for interoperability
3312          private static final long serialVersionUID = 7207038068494060240L;
3313  
3314 +        private static final ReverseComparator REVERSE_ORDER
3315 +            = new ReverseComparator();
3316 +
3317          public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3318              return c2.compareTo(c1);
3319          }
3320 +
3321 +        private Object readResolve() { return reverseOrder(); }
3322      }
3323  
3324      /**
# Line 3333 | Line 3332 | public class Collections {
3332       * comparator is also serializable or null).
3333       *
3334       * @return a comparator that imposes the reverse ordering of the
3335 <     *     specified comparator.
3335 >     *         specified comparator
3336       * @since 1.5
3337       */
3338      public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3339          if (cmp == null)
3340 <            return new ReverseComparator();  // Unchecked warning!!
3340 >            return reverseOrder();
3341 >
3342 >        if (cmp instanceof ReverseComparator2)
3343 >            return ((ReverseComparator2<T>)cmp).cmp;
3344  
3345          return new ReverseComparator2<T>(cmp);
3346      }
# Line 3358 | Line 3360 | public class Collections {
3360           *
3361           * @serial
3362           */
3363 <        private Comparator<T> cmp;
3363 >        private final Comparator<T> cmp;
3364  
3365          ReverseComparator2(Comparator<T> cmp) {
3366              assert cmp != null;
# Line 3368 | Line 3370 | public class Collections {
3370          public int compare(T t1, T t2) {
3371              return cmp.compare(t2, t1);
3372          }
3373 +
3374 +        public boolean equals(Object o) {
3375 +            return (o == this) ||
3376 +                (o instanceof ReverseComparator2 &&
3377 +                 cmp.equals(((ReverseComparator2)o).cmp));
3378 +        }
3379 +
3380 +        public int hashCode() {
3381 +            return cmp.hashCode() ^ Integer.MIN_VALUE;
3382 +        }
3383      }
3384  
3385      /**
# Line 3561 | Line 3573 | public class Collections {
3573          implements Set<E>, Serializable
3574      {
3575          private final Map<E, Boolean> m;  // The backing map
3576 <        private transient Set<E> keySet;  // Its keySet
3576 >        private transient Set<E> s;       // Its keySet
3577  
3578          SetFromMap(Map<E, Boolean> map) {
3579              if (!map.isEmpty())
3580                  throw new IllegalArgumentException("Map is non-empty");
3581              m = map;
3582 <            keySet = map.keySet();
3582 >            s = map.keySet();
3583          }
3584  
3585 +        public void clear()               {        m.clear(); }
3586          public int size()                 { return m.size(); }
3587          public boolean isEmpty()          { return m.isEmpty(); }
3588          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 –        }
3589          public boolean remove(Object o)   { return m.remove(o) != null; }
3590 <
3591 <        public boolean removeAll(Collection<?> c) {
3592 <            return keySet.removeAll(c);
3593 <        }
3594 <        public boolean retainAll(Collection<?> c) {
3595 <            return keySet.retainAll(c);
3596 <        }
3597 <        public void clear()               { m.clear(); }
3598 <        public boolean equals(Object o)   { return keySet.equals(o); }
3599 <        public int hashCode()             { return keySet.hashCode(); }
3590 >        public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3591 >        public Iterator<E> iterator()     { return s.iterator(); }
3592 >        public Object[] toArray()         { return s.toArray(); }
3593 >        public <T> T[] toArray(T[] a)     { return s.toArray(a); }
3594 >        public String toString()          { return s.toString(); }
3595 >        public int hashCode()             { return s.hashCode(); }
3596 >        public boolean equals(Object o)   { return o == this || s.equals(o); }
3597 >        public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3598 >        public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
3599 >        public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
3600 >        // addAll is the only inherited implementation
3601  
3602          private static final long serialVersionUID = 2454657854757543876L;
3603  
3604 <        private void readObject(java.io.ObjectInputStream s)
3604 >        private void readObject(java.io.ObjectInputStream stream)
3605              throws IOException, ClassNotFoundException
3606          {
3607 <            s.defaultReadObject();
3608 <            keySet = m.keySet();
3607 >            stream.defaultReadObject();
3608 >            s = m.keySet();
3609          }
3610      }
3611  
# Line 3608 | Line 3616 | public class Collections {
3616       * view can be useful when you would like to use a method
3617       * requiring a <tt>Queue</tt> but you need Lifo ordering.
3618       *
3619 +     * <p>Each method invocation on the queue returned by this method
3620 +     * results in exactly one method invocation on the backing deque, with
3621 +     * one exception.  The {@link Queue#addAll addAll} method is
3622 +     * implemented as a sequence of {@link Deque#addFirst addFirst}
3623 +     * invocations on the backing deque.
3624 +     *
3625       * @param deque the deque
3626       * @return the queue
3627       * @since  1.6
# Line 3620 | Line 3634 | public class Collections {
3634          implements Queue<E>, Serializable {
3635          private static final long serialVersionUID = 1802017725587941708L;
3636          private final Deque<E> q;
3637 <        AsLIFOQueue(Deque<E> q)            { this.q = q; }
3638 <        public boolean add(E e)            { q.addFirst(e); return true; }
3639 <        public boolean offer(E e)          { return q.offerFirst(e); }
3640 <        public E poll()                    { return q.pollFirst(); }
3641 <        public E remove()                  { return q.removeFirst(); }
3642 <        public E peek()                    { return q.peekFirst(); }
3643 <        public E element()                 { return q.getFirst(); }
3644 <        public int size()                  { return q.size(); }
3645 <        public boolean isEmpty()           { return q.isEmpty(); }
3646 <        public boolean contains(Object o)  { return q.contains(o); }
3647 <        public Iterator<E> iterator()      { return q.iterator(); }
3648 <        public Object[] toArray()          { return q.toArray(); }
3649 <        public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3650 <        public boolean remove(Object o)    { return q.remove(o); }
3651 <        public void clear()                { q.clear(); }
3637 >        AsLIFOQueue(Deque<E> q)           { this.q = q; }
3638 >        public boolean add(E e)           { q.addFirst(e); return true; }
3639 >        public boolean offer(E e)         { return q.offerFirst(e); }
3640 >        public E poll()                   { return q.pollFirst(); }
3641 >        public E remove()                 { return q.removeFirst(); }
3642 >        public E peek()                   { return q.peekFirst(); }
3643 >        public E element()                { return q.getFirst(); }
3644 >        public void clear()               {        q.clear(); }
3645 >        public int size()                 { return q.size(); }
3646 >        public boolean isEmpty()          { return q.isEmpty(); }
3647 >        public boolean contains(Object o) { return q.contains(o); }
3648 >        public boolean remove(Object o)   { return q.remove(o); }
3649 >        public Iterator<E> iterator()     { return q.iterator(); }
3650 >        public Object[] toArray()         { return q.toArray(); }
3651 >        public <T> T[] toArray(T[] a)     { return q.toArray(a); }
3652 >        public String toString()          { return q.toString(); }
3653 >        public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3654 >        public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
3655 >        public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
3656 >        // We use inherited addAll; forwarding addAll would be wrong
3657      }
3658   }

Diff Legend

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