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.31 by jsr166, Sun May 20 07:54:01 2007 UTC

# Line 1 | Line 1
1   /*
2 < * %W% %E%
2 > * Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.
3 > * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4   *
5 < * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
6 < * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
5 > * This code is free software; you can redistribute it and/or modify it
6 > * under the terms of the GNU General Public License version 2 only, as
7 > * published by the Free Software Foundation.  Sun designates this
8 > * particular file as subject to the "Classpath" exception as provided
9 > * by Sun in the LICENSE file that accompanied this code.
10 > *
11 > * This code is distributed in the hope that it will be useful, but WITHOUT
12 > * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 > * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 > * version 2 for more details (a copy is included in the LICENSE file that
15 > * accompanied this code).
16 > *
17 > * You should have received a copy of the GNU General Public License version
18 > * 2 along with this work; if not, write to the Free Software Foundation,
19 > * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 > *
21 > * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 > * CA 95054 USA or visit www.sun.com if you need additional information or
23 > * have any questions.
24   */
25  
26   package java.util;
9 – import java.util.*; // for javadoc (till 6280605 is fixed)
27   import java.io.Serializable;
28   import java.io.ObjectOutputStream;
29   import java.io.IOException;
# Line 39 | Line 56 | import java.lang.reflect.Array;
56   * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
57   *
58   * <p>This class is a member of the
59 < * <a href="{@docRoot}/../guide/collections/index.html">
59 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
60   * Java Collections Framework</a>.
61   *
62   * @author  Josh Bloch
# Line 169 | Line 186 | public class Collections {
186      /**
187       * Searches the specified list for the specified object using the binary
188       * search algorithm.  The list must be sorted into ascending order
189 <     * according to the <i>natural ordering</i> of its elements (as by the
190 <     * <tt>sort(List)</tt> method, above) prior to making this call.  If it is
191 <     * not sorted, the results are undefined.  If the list contains multiple
192 <     * elements equal to the specified object, there is no guarantee which one
193 <     * will be found.<p>
189 >     * according to the {@linkplain Comparable natural ordering} of its
190 >     * elements (as by the {@link #sort(List)} method) prior to making this
191 >     * call.  If it is not sorted, the results are undefined.  If the list
192 >     * contains multiple elements equal to the specified object, there is no
193 >     * guarantee which one will be found.
194       *
195 <     * This method runs in log(n) time for a "random access" list (which
195 >     * <p>This method runs in log(n) time for a "random access" list (which
196       * provides near-constant-time positional access).  If the specified list
197       * does not implement the {@link RandomAccess} interface and is large,
198       * this method will do an iterator-based binary search that performs
# Line 187 | Line 204 | public class Collections {
204       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
205       *         <i>insertion point</i> is defined as the point at which the
206       *         key would be inserted into the list: the index of the first
207 <     *         element greater than the key, or <tt>list.size()</tt>, if all
207 >     *         element greater than the key, or <tt>list.size()</tt> if all
208       *         elements in the list are less than the specified key.  Note
209       *         that this guarantees that the return value will be &gt;= 0 if
210       *         and only if the key is found.
211       * @throws ClassCastException if the list contains elements that are not
212       *         <i>mutually comparable</i> (for example, strings and
213 <     *         integers), or the search key in not mutually comparable
213 >     *         integers), or the search key is not mutually comparable
214       *         with the elements of the list.
198 –     * @see    Comparable
199 –     * @see #sort(List)
215       */
216      public static <T>
217      int binarySearch(List<? extends Comparable<? super T>> list, T key) {
# Line 213 | Line 228 | public class Collections {
228          int high = list.size()-1;
229  
230          while (low <= high) {
231 <            int mid = (low + high) >> 1;
231 >            int mid = (low + high) >>> 1;
232              Comparable<? super T> midVal = list.get(mid);
233              int cmp = midVal.compareTo(key);
234  
# Line 235 | Line 250 | public class Collections {
250          ListIterator<? extends Comparable<? super T>> i = list.listIterator();
251  
252          while (low <= high) {
253 <            int mid = (low + high) >> 1;
253 >            int mid = (low + high) >>> 1;
254              Comparable<? super T> midVal = get(i, mid);
255              int cmp = midVal.compareTo(key);
256  
# Line 271 | Line 286 | public class Collections {
286      /**
287       * Searches the specified list for the specified object using the binary
288       * search algorithm.  The list must be sorted into ascending order
289 <     * according to the specified comparator (as by the <tt>Sort(List,
290 <     * Comparator)</tt> method, above), prior to making this call.  If it is
289 >     * according to the specified comparator (as by the
290 >     * {@link #sort(List, Comparator) sort(List, Comparator)}
291 >     * method), prior to making this call.  If it is
292       * not sorted, the results are undefined.  If the list contains multiple
293       * elements equal to the specified object, there is no guarantee which one
294 <     * will be found.<p>
294 >     * will be found.
295       *
296 <     * This method runs in log(n) time for a "random access" list (which
296 >     * <p>This method runs in log(n) time for a "random access" list (which
297       * provides near-constant-time positional access).  If the specified list
298       * does not implement the {@link RandomAccess} interface and is large,
299       * this method will do an iterator-based binary search that performs
# Line 285 | Line 301 | public class Collections {
301       *
302       * @param  list the list to be searched.
303       * @param  key the key to be searched for.
304 <     * @param  c the comparator by which the list is ordered.  A
305 <     *        <tt>null</tt> value indicates that the elements' <i>natural
306 <     *        ordering</i> should be used.
304 >     * @param  c the comparator by which the list is ordered.
305 >     *         A <tt>null</tt> value indicates that the elements'
306 >     *         {@linkplain Comparable natural ordering} should be used.
307       * @return the index of the search key, if it is contained in the list;
308       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
309       *         <i>insertion point</i> is defined as the point at which the
310       *         key would be inserted into the list: the index of the first
311 <     *         element greater than the key, or <tt>list.size()</tt>, if all
311 >     *         element greater than the key, or <tt>list.size()</tt> if all
312       *         elements in the list are less than the specified key.  Note
313       *         that this guarantees that the return value will be &gt;= 0 if
314       *         and only if the key is found.
315       * @throws ClassCastException if the list contains elements that are not
316       *         <i>mutually comparable</i> using the specified comparator,
317 <     *         or the search key in not mutually comparable with the
317 >     *         or the search key is not mutually comparable with the
318       *         elements of the list using this comparator.
303 –     * @see    Comparable
304 –     * @see #sort(List, Comparator)
319       */
320      public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
321          if (c==null)
# Line 318 | Line 332 | public class Collections {
332          int high = l.size()-1;
333  
334          while (low <= high) {
335 <            int mid = (low + high) >> 1;
335 >            int mid = (low + high) >>> 1;
336              T midVal = l.get(mid);
337              int cmp = c.compare(midVal, key);
338  
# Line 338 | Line 352 | public class Collections {
352          ListIterator<? extends T> i = l.listIterator();
353  
354          while (low <= high) {
355 <            int mid = (low + high) >> 1;
355 >            int mid = (low + high) >>> 1;
356              T midVal = get(i, mid);
357              int cmp = c.compare(midVal, key);
358  
# Line 1067 | Line 1081 | public class Collections {
1081          private static final long serialVersionUID = -9215047833775013803L;
1082  
1083          UnmodifiableSet(Set<? extends E> s)     {super(s);}
1084 <        public boolean equals(Object o) {return c.equals(o);}
1084 >        public boolean equals(Object o) {return o == this || c.equals(o);}
1085          public int hashCode()           {return c.hashCode();}
1086      }
1087  
# Line 1152 | Line 1166 | public class Collections {
1166              this.list = list;
1167          }
1168  
1169 <        public boolean equals(Object o) {return list.equals(o);}
1169 >        public boolean equals(Object o) {return o == this || list.equals(o);}
1170          public int hashCode()           {return list.hashCode();}
1171  
1172          public E get(int index) {return list.get(index);}
# Line 1320 | Line 1334 | public class Collections {
1334              return values;
1335          }
1336  
1337 <        public boolean equals(Object o) {return m.equals(o);}
1337 >        public boolean equals(Object o) {return o == this || m.equals(o);}
1338          public int hashCode()           {return m.hashCode();}
1339          public String toString()        {return m.toString();}
1340  
# Line 1543 | Line 1557 | public class Collections {
1557          // use serialVersionUID from JDK 1.2.2 for interoperability
1558          private static final long serialVersionUID = 3053995032091335093L;
1559  
1560 <        final Collection<E> c;     // Backing Collection
1561 <        final Object       mutex;  // Object on which to synchronize
1560 >        final Collection<E> c;  // Backing Collection
1561 >        final Object mutex;     // Object on which to synchronize
1562  
1563          SynchronizedCollection(Collection<E> c) {
1564              if (c==null)
# Line 2318 | Line 2332 | public class Collections {
2332  
2333          CheckedSet(Set<E> s, Class<E> elementType) { super(s, elementType); }
2334  
2335 <        public boolean equals(Object o) { return c.equals(o); }
2335 >        public boolean equals(Object o) { return o == this || c.equals(o); }
2336          public int hashCode()           { return c.hashCode(); }
2337      }
2338  
# Line 2421 | Line 2435 | public class Collections {
2435              this.list = list;
2436          }
2437  
2438 <        public boolean equals(Object o)  { return list.equals(o); }
2438 >        public boolean equals(Object o)  { return o == this || list.equals(o); }
2439          public int hashCode()            { return list.hashCode(); }
2440          public E get(int index)          { return list.get(index); }
2441          public E remove(int index)       { return list.remove(index); }
# Line 2575 | Line 2589 | public class Collections {
2589          public void clear()                    { m.clear(); }
2590          public Set<K> keySet()                 { return m.keySet(); }
2591          public Collection<V> values()          { return m.values(); }
2592 <        public boolean equals(Object o)        { return m.equals(o);  }
2592 >        public boolean equals(Object o)        { return o == this || m.equals(o); }
2593          public int hashCode()                  { return m.hashCode(); }
2594          public String toString()               { return m.toString(); }
2595  
# Line 3303 | Line 3317 | public class Collections {
3317       * @see Comparable
3318       */
3319      public static <T> Comparator<T> reverseOrder() {
3320 <        return (Comparator<T>) REVERSE_ORDER;
3320 >        return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3321      }
3322  
3309 –    private static final Comparator REVERSE_ORDER = new ReverseComparator();
3310 –
3323      /**
3324       * @serial include
3325       */
3326 <    private static class ReverseComparator<T>
3326 >    private static class ReverseComparator
3327          implements Comparator<Comparable<Object>>, Serializable {
3328  
3329          // use serialVersionUID from JDK 1.2.2 for interoperability
3330          private static final long serialVersionUID = 7207038068494060240L;
3331  
3332 +        private static final ReverseComparator REVERSE_ORDER
3333 +            = new ReverseComparator();
3334 +
3335          public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3336              return c2.compareTo(c1);
3337          }
3338 +
3339 +        private Object readResolve() { return reverseOrder(); }
3340      }
3341  
3342      /**
# Line 3333 | Line 3350 | public class Collections {
3350       * comparator is also serializable or null).
3351       *
3352       * @return a comparator that imposes the reverse ordering of the
3353 <     *     specified comparator.
3353 >     *         specified comparator
3354       * @since 1.5
3355       */
3356      public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3357          if (cmp == null)
3358 <            return new ReverseComparator();  // Unchecked warning!!
3358 >            return reverseOrder();
3359 >
3360 >        if (cmp instanceof ReverseComparator2)
3361 >            return ((ReverseComparator2<T>)cmp).cmp;
3362  
3363          return new ReverseComparator2<T>(cmp);
3364      }
# Line 3358 | Line 3378 | public class Collections {
3378           *
3379           * @serial
3380           */
3381 <        private Comparator<T> cmp;
3381 >        private final Comparator<T> cmp;
3382  
3383          ReverseComparator2(Comparator<T> cmp) {
3384              assert cmp != null;
# Line 3368 | Line 3388 | public class Collections {
3388          public int compare(T t1, T t2) {
3389              return cmp.compare(t2, t1);
3390          }
3391 +
3392 +        public boolean equals(Object o) {
3393 +            return (o == this) ||
3394 +                (o instanceof ReverseComparator2 &&
3395 +                 cmp.equals(((ReverseComparator2)o).cmp));
3396 +        }
3397 +
3398 +        public int hashCode() {
3399 +            return cmp.hashCode() ^ Integer.MIN_VALUE;
3400 +        }
3401      }
3402  
3403      /**
# Line 3561 | Line 3591 | public class Collections {
3591          implements Set<E>, Serializable
3592      {
3593          private final Map<E, Boolean> m;  // The backing map
3594 <        private transient Set<E> keySet;  // Its keySet
3594 >        private transient Set<E> s;       // Its keySet
3595  
3596          SetFromMap(Map<E, Boolean> map) {
3597              if (!map.isEmpty())
3598                  throw new IllegalArgumentException("Map is non-empty");
3599              m = map;
3600 <            keySet = map.keySet();
3600 >            s = map.keySet();
3601          }
3602  
3603 +        public void clear()               {        m.clear(); }
3604          public int size()                 { return m.size(); }
3605          public boolean isEmpty()          { return m.isEmpty(); }
3606          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 –        }
3607          public boolean remove(Object o)   { return m.remove(o) != null; }
3608 <
3609 <        public boolean removeAll(Collection<?> c) {
3610 <            return keySet.removeAll(c);
3611 <        }
3612 <        public boolean retainAll(Collection<?> c) {
3613 <            return keySet.retainAll(c);
3614 <        }
3615 <        public void clear()               { m.clear(); }
3616 <        public boolean equals(Object o)   { return keySet.equals(o); }
3617 <        public int hashCode()             { return keySet.hashCode(); }
3608 >        public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
3609 >        public Iterator<E> iterator()     { return s.iterator(); }
3610 >        public Object[] toArray()         { return s.toArray(); }
3611 >        public <T> T[] toArray(T[] a)     { return s.toArray(a); }
3612 >        public String toString()          { return s.toString(); }
3613 >        public int hashCode()             { return s.hashCode(); }
3614 >        public boolean equals(Object o)   { return o == this || s.equals(o); }
3615 >        public boolean containsAll(Collection<?> c) {return s.containsAll(c);}
3616 >        public boolean removeAll(Collection<?> c)   {return s.removeAll(c);}
3617 >        public boolean retainAll(Collection<?> c)   {return s.retainAll(c);}
3618 >        // addAll is the only inherited implementation
3619  
3620          private static final long serialVersionUID = 2454657854757543876L;
3621  
3622 <        private void readObject(java.io.ObjectInputStream s)
3622 >        private void readObject(java.io.ObjectInputStream stream)
3623              throws IOException, ClassNotFoundException
3624          {
3625 <            s.defaultReadObject();
3626 <            keySet = m.keySet();
3625 >            stream.defaultReadObject();
3626 >            s = m.keySet();
3627          }
3628      }
3629  
# Line 3608 | Line 3634 | public class Collections {
3634       * view can be useful when you would like to use a method
3635       * requiring a <tt>Queue</tt> but you need Lifo ordering.
3636       *
3637 +     * <p>Each method invocation on the queue returned by this method
3638 +     * results in exactly one method invocation on the backing deque, with
3639 +     * one exception.  The {@link Queue#addAll addAll} method is
3640 +     * implemented as a sequence of {@link Deque#addFirst addFirst}
3641 +     * invocations on the backing deque.
3642 +     *
3643       * @param deque the deque
3644       * @return the queue
3645       * @since  1.6
# Line 3620 | Line 3652 | public class Collections {
3652          implements Queue<E>, Serializable {
3653          private static final long serialVersionUID = 1802017725587941708L;
3654          private final Deque<E> q;
3655 <        AsLIFOQueue(Deque<E> q)            { this.q = q; }
3656 <        public boolean add(E e)            { q.addFirst(e); return true; }
3657 <        public boolean offer(E e)          { return q.offerFirst(e); }
3658 <        public E poll()                    { return q.pollFirst(); }
3659 <        public E remove()                  { return q.removeFirst(); }
3660 <        public E peek()                    { return q.peekFirst(); }
3661 <        public E element()                 { return q.getFirst(); }
3662 <        public int size()                  { return q.size(); }
3663 <        public boolean isEmpty()           { return q.isEmpty(); }
3664 <        public boolean contains(Object o)  { return q.contains(o); }
3665 <        public Iterator<E> iterator()      { return q.iterator(); }
3666 <        public Object[] toArray()          { return q.toArray(); }
3667 <        public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3668 <        public boolean remove(Object o)    { return q.remove(o); }
3669 <        public void clear()                { q.clear(); }
3655 >        AsLIFOQueue(Deque<E> q)           { this.q = q; }
3656 >        public boolean add(E e)           { q.addFirst(e); return true; }
3657 >        public boolean offer(E e)         { return q.offerFirst(e); }
3658 >        public E poll()                   { return q.pollFirst(); }
3659 >        public E remove()                 { return q.removeFirst(); }
3660 >        public E peek()                   { return q.peekFirst(); }
3661 >        public E element()                { return q.getFirst(); }
3662 >        public void clear()               {        q.clear(); }
3663 >        public int size()                 { return q.size(); }
3664 >        public boolean isEmpty()          { return q.isEmpty(); }
3665 >        public boolean contains(Object o) { return q.contains(o); }
3666 >        public boolean remove(Object o)   { return q.remove(o); }
3667 >        public Iterator<E> iterator()     { return q.iterator(); }
3668 >        public Object[] toArray()         { return q.toArray(); }
3669 >        public <T> T[] toArray(T[] a)     { return q.toArray(a); }
3670 >        public String toString()          { return q.toString(); }
3671 >        public boolean containsAll(Collection<?> c) {return q.containsAll(c);}
3672 >        public boolean removeAll(Collection<?> c)   {return q.removeAll(c);}
3673 >        public boolean retainAll(Collection<?> c)   {return q.retainAll(c);}
3674 >        // We use inherited addAll; forwarding addAll would be wrong
3675      }
3676   }

Diff Legend

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