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.14 by jsr166, Wed Aug 24 04:55:09 2005 UTC vs.
Revision 1.28 by jsr166, Sun May 28 23:36:29 2006 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2006 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 2221 | Line 2217 | public class Collections {
2217          public Object[] toArray()           { return c.toArray(); }
2218          public <T> T[] toArray(T[] a)       { return c.toArray(a); }
2219          public String toString()            { return c.toString(); }
2224 –        public Iterator<E> iterator()       { return c.iterator(); }
2220          public boolean remove(Object o)     { return c.remove(o); }
2221          public boolean containsAll(Collection<?> coll) {
2222              return c.containsAll(coll);
# Line 2236 | Line 2231 | public class Collections {
2231              c.clear();
2232          }
2233  
2234 <        public boolean add(E e){
2234 >        public Iterator<E> iterator() {
2235 >            return new Iterator<E>() {
2236 >                private final Iterator<E> it = c.iterator();
2237 >                public boolean hasNext() { return it.hasNext(); }
2238 >                public E next()          { return it.next(); }
2239 >                public void remove()     {        it.remove(); }};
2240 >        }
2241 >
2242 >        public boolean add(E e){
2243              typeCheck(e);
2244              return c.add(e);
2245          }
# Line 2311 | 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 2414 | 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 2568 | 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 3313 | 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 3331 | 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 3498 | Line 3503 | public class Collections {
3503       * </pre>
3504       *
3505       * @param c the collection into which <tt>elements</tt> are to be inserted
3506 <     * @param a the elements to insert into <tt>c</tt>
3506 >     * @param elements the elements to insert into <tt>c</tt>
3507       * @return <tt>true</tt> if the collection changed as a result of the call
3508       * @throws UnsupportedOperationException if <tt>c</tt> does not support
3509 <     *         the <tt>add</tt> operation.
3509 >     *         the <tt>add</tt> operation
3510       * @throws NullPointerException if <tt>elements</tt> contains one or more
3511       *         null values and <tt>c</tt> does not permit null elements, or
3512       *         if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
# Line 3510 | Line 3515 | public class Collections {
3515       * @see Collection#addAll(Collection)
3516       * @since 1.5
3517       */
3518 <    public static <T> boolean addAll(Collection<? super T> c, T... a) {
3518 >    public static <T> boolean addAll(Collection<? super T> c, T... elements) {
3519          boolean result = false;
3520 <        for (T e : a)
3521 <            result |= c.add(e);
3520 >        for (T element : elements)
3521 >            result |= c.add(element);
3522          return result;
3523      }
3524  
# Line 3537 | Line 3542 | public class Collections {
3542       * to this method, and no reference to the map is retained, as illustrated
3543       * in the following code fragment:
3544       * <pre>
3545 <     *    Set&lt;Object&gt; weakHashSet = Collections.asSet(
3545 >     *    Set&lt;Object&gt; weakHashSet = Collections.newSetFromMap(
3546       *        new WeakHashMap&lt;Object, Boolean&gt;());
3547       * </pre>
3548       *
# Line 3554 | 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); }
3569 –        public Iterator<E> iterator()     { return keySet.iterator(); }
3570 –        public Object[] toArray()         { return keySet.toArray(); }
3571 –        public <T> T[] toArray(T[] a)     { return keySet.toArray(a); }
3572 –        public boolean add(E e) {
3573 –            return m.put(e, Boolean.TRUE) == null;
3574 –        }
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 3600 | Line 3601 | public class Collections {
3601       * <tt>remove</tt> is mapped to <tt>pop</tt> and so on. This
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 3612 | 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 offer(E e)          { return q.offerFirst(e); }
3625 <        public E poll()                    { return q.pollFirst(); }
3626 <        public E remove()                  { return q.removeFirst(); }
3627 <        public E peek()                    { return q.peekFirst(); }
3628 <        public E element()                 { return q.getFirst(); }
3629 <        public int size()                  { return q.size(); }
3630 <        public boolean isEmpty()           { return q.isEmpty(); }
3631 <        public boolean contains(Object o)  { return q.contains(o); }
3632 <        public Iterator<E> iterator()      { return q.iterator(); }
3633 <        public Object[] toArray()          { return q.toArray(); }
3634 <        public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3635 <        public boolean add(E e)            { return q.offerFirst(e); }
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