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.1 by dl, Tue Dec 28 12:14:07 2004 UTC vs.
Revision 1.7 by jsr166, Wed May 18 03:45:35 2005 UTC

# Line 1 | Line 1
1   /*
2   * %W% %E%
3   *
4 < * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
4 > * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */
7  
# Line 37 | Line 37 | import java.lang.reflect.Array;
37   * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
38   * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
39   *
40 < * <p>This class is a member of the
40 > * <p>This class is a member of the
41   * <a href="{@docRoot}/../guide/collections/index.html">
42   * Java Collections Framework</a>.
43   *
# Line 63 | Line 63 | public class Collections {
63       * two implementations, one of which is appropriate for RandomAccess
64       * lists, the other for "sequential."  Often, the random access variant
65       * yields better performance on small sequential access lists.  The
66 <     * tuning  parameters below determine the cutoff point for what constitutes
66 >     * tuning parameters below determine the cutoff point for what constitutes
67       * a "small" sequential access list for each algorithm.  The values below
68       * were empirically determined to work well for LinkedList. Hopefully
69       * they should be reasonable for other sequential access List
# Line 97 | Line 97 | public class Collections {
97       * The sorting algorithm is a modified mergesort (in which the merge is
98       * omitted if the highest element in the low sublist is less than the
99       * lowest element in the high sublist).  This algorithm offers guaranteed
100 <     * n log(n) performance.
100 >     * n log(n) performance.
101       *
102       * This implementation dumps the specified list into an array, sorts
103       * the array, and iterates over the list resetting each element
# Line 135 | Line 135 | public class Collections {
135       * The sorting algorithm is a modified mergesort (in which the merge is
136       * omitted if the highest element in the low sublist is less than the
137       * lowest element in the high sublist).  This algorithm offers guaranteed
138 <     * n log(n) performance.
138 >     * n log(n) performance.
139       *
140       * The specified list must be modifiable, but need not be resizable.
141       * This implementation dumps the specified list into an array, sorts
# Line 182 | Line 182 | public class Collections {
182       *
183       * @param  list the list to be searched.
184       * @param  key the key to be searched for.
185 <     * @return index of the search key, if it is contained in the list;
185 >     * @return the index of the search key, if it is contained in the list;
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
# Line 287 | Line 287 | public class Collections {
287       * @param  c the comparator by which the list is ordered.  A
288       *        <tt>null</tt> value indicates that the elements' <i>natural
289       *        ordering</i> should be used.
290 <     * @return index of the search key, if it is contained in the list;
290 >     * @return the index of the search key, if it is contained in the list;
291       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
292       *         <i>insertion point</i> is defined as the point at which the
293       *         key would be inserted into the list: the index of the first
# Line 361 | Line 361 | public class Collections {
361       *
362       * @param  list the list whose elements are to be reversed.
363       * @throws UnsupportedOperationException if the specified list or
364 <     *         its list-iterator does not support the <tt>set</tt> method.
364 >     *         its list-iterator does not support the <tt>set</tt> operation.
365       */
366      public static void reverse(List<?> list) {
367          int size = list.size();
# Line 405 | Line 405 | public class Collections {
405       *
406       * @param  list the list to be shuffled.
407       * @throws UnsupportedOperationException if the specified list or
408 <     *         its list-iterator does not support the <tt>set</tt> method.
408 >     *         its list-iterator does not support the <tt>set</tt> operation.
409       */
410      public static void shuffle(List<?> list) {
411          shuffle(list, r);
# Line 569 | Line 569 | public class Collections {
569          Iterator<? extends T> i = coll.iterator();
570          T candidate = i.next();
571  
572 <        while(i.hasNext()) {
572 >        while (i.hasNext()) {
573              T next = i.next();
574              if (next.compareTo(candidate) < 0)
575                  candidate = next;
# Line 606 | Line 606 | public class Collections {
606          Iterator<? extends T> i = coll.iterator();
607          T candidate = i.next();
608  
609 <        while(i.hasNext()) {
609 >        while (i.hasNext()) {
610              T next = i.next();
611              if (comp.compare(next, candidate) < 0)
612                  candidate = next;
# Line 639 | Line 639 | public class Collections {
639          Iterator<? extends T> i = coll.iterator();
640          T candidate = i.next();
641  
642 <        while(i.hasNext()) {
642 >        while (i.hasNext()) {
643              T next = i.next();
644              if (next.compareTo(candidate) > 0)
645                  candidate = next;
# Line 676 | Line 676 | public class Collections {
676          Iterator<? extends T> i = coll.iterator();
677          T candidate = i.next();
678  
679 <        while(i.hasNext()) {
679 >        while (i.hasNext()) {
680              T next = i.next();
681              if (comp.compare(next, candidate) > 0)
682                  candidate = next;
# Line 712 | Line 712 | public class Collections {
712       *     Collections.rotate(l.subList(1, 4), -1);
713       * </pre>
714       * The resulting list is <tt>[a, c, d, b, e]</tt>.
715 <     *
715 >     *
716       * <p>To move more than one element forward, increase the absolute value
717       * of the rotation distance.  To move elements backward, use a positive
718       * shift distance.
# Line 736 | Line 736 | public class Collections {
736       *        constraints on this value; it may be zero, negative, or
737       *        greater than <tt>list.size()</tt>.
738       * @throws UnsupportedOperationException if the specified list or
739 <     *         its list-iterator does not support the <tt>set</tt> method.
739 >     *         its list-iterator does not support the <tt>set</tt> operation.
740       * @since 1.4
741       */
742      public static void rotate(List<?> list, int distance) {
# Line 772 | Line 772 | public class Collections {
772      private static void rotate2(List<?> list, int distance) {
773          int size = list.size();
774          if (size == 0)
775 <            return;
775 >            return;
776          int mid =  -distance % size;
777          if (mid < 0)
778              mid += size;
# Line 799 | Line 799 | public class Collections {
799       *         <tt>e</tt> such that
800       *         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
801       * @throws UnsupportedOperationException if the specified list or
802 <     *         its list-iterator does not support the <tt>set</tt> method.
802 >     *         its list-iterator does not support the <tt>set</tt> operation.
803       * @since  1.4
804       */
805      public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {
# Line 970 | Line 970 | public class Collections {
970       * that the backing collection is a set or a list.<p>
971       *
972       * The returned collection will be serializable if the specified collection
973 <     * is serializable.
973 >     * is serializable.
974       *
975       * @param  c the collection for which an unmodifiable view is to be
976       *         returned.
# Line 1014 | Line 1014 | public class Collections {
1014              };
1015          }
1016  
1017 <        public boolean add(E o){
1017 >        public boolean add(E e){
1018              throw new UnsupportedOperationException();
1019          }
1020          public boolean remove(Object o) {
# Line 1046 | Line 1046 | public class Collections {
1046       * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1047       *
1048       * The returned set will be serializable if the specified set
1049 <     * is serializable.
1049 >     * is serializable.
1050       *
1051       * @param  s the set for which an unmodifiable view is to be returned.
1052       * @return an unmodifiable view of the specified set.
1053       */
1054 –
1054      public static <T> Set<T> unmodifiableSet(Set<? extends T> s) {
1055          return new UnmodifiableSet<T>(s);
1056      }
# Line 1078 | Line 1077 | public class Collections {
1077       * an <tt>UnsupportedOperationException</tt>.<p>
1078       *
1079       * The returned sorted set will be serializable if the specified sorted set
1080 <     * is serializable.
1080 >     * is serializable.
1081       *
1082       * @param s the sorted set for which an unmodifiable view is to be
1083 <     *        returned.
1083 >     *        returned.
1084       * @return an unmodifiable view of the specified sorted set.
1085       */
1086      public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
# Line 1183 | Line 1182 | public class Collections {
1182                  public void remove() {
1183                      throw new UnsupportedOperationException();
1184                  }
1185 <                public void set(E o) {
1185 >                public void set(E e) {
1186                      throw new UnsupportedOperationException();
1187                  }
1188 <                public void add(E o) {
1188 >                public void add(E e) {
1189                      throw new UnsupportedOperationException();
1190                  }
1191              };
# Line 1252 | Line 1251 | public class Collections {
1251       * <tt>UnsupportedOperationException</tt>.<p>
1252       *
1253       * The returned map will be serializable if the specified map
1254 <     * is serializable.
1254 >     * is serializable.
1255       *
1256       * @param  m the map for which an unmodifiable view is to be returned.
1257       * @return an unmodifiable view of the specified map.
# Line 1334 | Line 1333 | public class Collections {
1333              private static final long serialVersionUID = 7854390611657943733L;
1334  
1335              UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1336 <                super((Set<Map.Entry<K,V>>)(Set)s);
1336 >                super((Set)s);
1337              }
1338              public Iterator<Map.Entry<K,V>> iterator() {
1339                  return new Iterator<Map.Entry<K,V>>() {
# Line 1456 | Line 1455 | public class Collections {
1455       * an <tt>UnsupportedOperationException</tt>.<p>
1456       *
1457       * The returned sorted map will be serializable if the specified sorted map
1458 <     * is serializable.
1458 >     * is serializable.
1459       *
1460       * @param m the sorted map for which an unmodifiable view is to be
1461 <     *        returned.
1461 >     *        returned.
1462       * @return an unmodifiable view of the specified sorted map.
1463       */
1464      public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m) {
# Line 1523 | Line 1522 | public class Collections {
1522       * that the backing collection is a set or a list.<p>
1523       *
1524       * The returned collection will be serializable if the specified collection
1525 <     * is serializable.
1525 >     * is serializable.
1526       *
1527       * @param  c the collection to be "wrapped" in a synchronized collection.
1528       * @return a synchronized view of the specified collection.
# Line 1577 | Line 1576 | public class Collections {
1576              return c.iterator(); // Must be manually synched by user!
1577          }
1578  
1579 <        public boolean add(E o) {
1580 <            synchronized(mutex) {return c.add(o);}
1579 >        public boolean add(E e) {
1580 >            synchronized(mutex) {return c.add(e);}
1581          }
1582          public boolean remove(Object o) {
1583              synchronized(mutex) {return c.remove(o);}
# Line 1673 | Line 1672 | public class Collections {
1672       * sorted set when iterating over it or any of its <tt>subSet</tt>,
1673       * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1674       * <pre>
1675 <     *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1675 >     *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1676       *      ...
1677       *  synchronized(s) {
1678       *      Iterator i = s.iterator(); // Must be in the synchronized block
# Line 1683 | Line 1682 | public class Collections {
1682       * </pre>
1683       * or:
1684       * <pre>
1685 <     *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1685 >     *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
1686       *  SortedSet s2 = s.headSet(foo);
1687       *      ...
1688       *  synchronized(s) {  // Note: s, not s2!!!
# Line 2007 | Line 2006 | public class Collections {
2006          public Set<Map.Entry<K,V>> entrySet() {
2007              synchronized(mutex) {
2008                  if (entrySet==null)
2009 <                    entrySet = new SynchronizedSet<Map.Entry<K,V>>((Set<Map.Entry<K,V>>)m.entrySet(), mutex);
2009 >                    entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
2010                  return entrySet;
2011              }
2012          }
# Line 2045 | Line 2044 | public class Collections {
2044       * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2045       * <tt>tailMap</tt> views.
2046       * <pre>
2047 <     *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2047 >     *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2048       *      ...
2049       *  Set s = m.keySet();  // Needn't be in synchronized block
2050       *      ...
# Line 2057 | Line 2056 | public class Collections {
2056       * </pre>
2057       * or:
2058       * <pre>
2059 <     *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2059 >     *  SortedMap m = Collections.synchronizedSortedMap(new TreeMap());
2060       *  SortedMap m2 = m.subMap(foo, bar);
2061       *      ...
2062       *  Set s2 = m2.keySet();  // Needn't be in synchronized block
# Line 2191 | Line 2190 | public class Collections {
2190                                                        Class<E> type) {
2191          return new CheckedCollection<E>(c, type);
2192      }
2193 <
2193 >
2194      /**
2195       * @serial include
2196       */
# Line 2236 | Line 2235 | public class Collections {
2235              c.clear();
2236          }
2237  
2238 <        public boolean add(E o){
2239 <            typeCheck(o);
2240 <            return c.add(o);
2238 >        public boolean add(E e){
2239 >            typeCheck(e);
2240 >            return c.add(e);
2241          }
2242  
2243          public boolean addAll(Collection<? extends E> coll) {
# Line 2246 | Line 2245 | public class Collections {
2245               * Dump coll into an array of the required type.  This serves
2246               * three purposes: it insulates us from concurrent changes in
2247               * the contents of coll, it type-checks all of the elements in
2248 <             * coll, and it provides all-or-nothing semantics(which we
2248 >             * coll, and it provides all-or-nothing semantics (which we
2249               * wouldn't get if we type-checked each element as we added it).
2250               */
2251              E[] a = null;
2252              try {
2253                  a = coll.toArray(zeroLengthElementArray());
2254 <            } catch(ArrayStoreException e) {
2254 >            } catch (ArrayStoreException e) {
2255                  throw new ClassCastException();
2256              }
2257  
# Line 2265 | Line 2264 | public class Collections {
2264          private E[] zeroLengthElementArray = null; // Lazily initialized
2265  
2266          /*
2267 <         * We don't need locking or volatile, because it's OK if we create
2267 >         * We don't need locking or volatile, because it's OK if we create
2268           * several zeroLengthElementArrays, and they're immutable.
2269           */
2270          E[] zeroLengthElementArray() {
# Line 2300 | Line 2299 | public class Collections {
2299      public static <E> Set<E> checkedSet(Set<E> s, Class<E> type) {
2300          return new CheckedSet<E>(s, type);
2301      }
2302 <
2302 >
2303      /**
2304       * @serial include
2305       */
# Line 2436 | Line 2435 | public class Collections {
2435              E[] a = null;
2436              try {
2437                  a = c.toArray(zeroLengthElementArray());
2438 <            } catch(ArrayStoreException e) {
2438 >            } catch (ArrayStoreException e) {
2439                  throw new ClassCastException();
2440              }
2441  
# Line 2456 | Line 2455 | public class Collections {
2455                  public int previousIndex()   { return i.previousIndex(); }
2456                  public void remove()         { i.remove(); }
2457  
2458 <                public void set(E o) {
2459 <                    typeCheck(o);
2460 <                    i.set(o);
2458 >                public void set(E e) {
2459 >                    typeCheck(e);
2460 >                    i.set(e);
2461                  }
2462  
2463 <                public void add(E o) {
2464 <                    typeCheck(o);
2465 <                    i.add(o);
2463 >                public void add(E e) {
2464 >                    typeCheck(e);
2465 >                    i.add(e);
2466                  }
2467              };
2468          }
# Line 2582 | Line 2581 | public class Collections {
2581              K[] keys = null;
2582              try {
2583                  keys = t.keySet().toArray(zeroLengthKeyArray());
2584 <            } catch(ArrayStoreException e) {
2584 >            } catch (ArrayStoreException e) {
2585                  throw new ClassCastException();
2586              }
2587              V[] values = null;
2588              try {
2589                  values = t.values().toArray(zeroLengthValueArray());
2590 <            } catch(ArrayStoreException e) {
2590 >            } catch (ArrayStoreException e) {
2591                  throw new ClassCastException();
2592              }
2593  
# Line 2604 | Line 2603 | public class Collections {
2603          private V[] zeroLengthValueArray = null;
2604  
2605          /*
2606 <         * We don't need locking or volatile, because it's OK if we create
2606 >         * We don't need locking or volatile, because it's OK if we create
2607           * several zeroLengthValueArrays, and they're immutable.
2608           */
2609          private K[] zeroLengthKeyArray() {
# Line 2658 | Line 2657 | public class Collections {
2657                  s.clear();
2658              }
2659  
2660 <            public boolean add(Map.Entry<K, V> o){
2660 >            public boolean add(Map.Entry<K, V> e){
2661                  throw new UnsupportedOperationException();
2662              }
2663              public boolean addAll(Collection<? extends Map.Entry<K, V>> coll) {
# Line 3060 | Line 3059 | public class Collections {
3059  
3060          final private E element;
3061  
3062 <        SingletonSet(E o) {element = o;}
3062 >        SingletonSet(E e) {element = e;}
3063  
3064          public Iterator<E> iterator() {
3065              return new Iterator<E>() {
# Line 3168 | Line 3167 | public class Collections {
3167  
3168          public Set<Map.Entry<K,V>> entrySet() {
3169              if (entrySet==null)
3170 <                entrySet = singleton((Map.Entry<K,V>)new ImmutableEntry<K,V>(k, v));
3170 >                entrySet = Collections.<Map.Entry<K,V>>singleton(
3171 >                    new SimpleImmutableEntry<K,V>(k, v));
3172              return entrySet;
3173          }
3174  
# Line 3178 | Line 3178 | public class Collections {
3178              return values;
3179          }
3180  
3181 –        private static class ImmutableEntry<K,V>
3182 –            implements Map.Entry<K,V> {
3183 –            final K k;
3184 –            final V v;
3185 –
3186 –            ImmutableEntry(K key, V value) {
3187 –                k = key;
3188 –                v = value;
3189 –            }
3190 –
3191 –            public K getKey()   {return k;}
3192 –
3193 –            public V getValue() {return v;}
3194 –
3195 –            public V setValue(V value) {
3196 –                throw new UnsupportedOperationException();
3197 –            }
3198 –
3199 –            public boolean equals(Object o) {
3200 –                if (!(o instanceof Map.Entry))
3201 –                    return false;
3202 –                Map.Entry e = (Map.Entry)o;
3203 –                return eq(e.getKey(), k) && eq(e.getValue(), v);
3204 –            }
3205 –
3206 –            public int hashCode() {
3207 –                return ((k==null ? 0 : k.hashCode()) ^
3208 –                        (v==null ? 0 : v.hashCode()));
3209 –            }
3210 –
3211 –            public String toString() {
3212 –                return k+"="+v;
3213 –            }
3214 –        }
3181      }
3182  
3183      /**
# Line 3245 | Line 3211 | public class Collections {
3211          int n;
3212          E element;
3213  
3214 <        CopiesList(int n, E o) {
3214 >        CopiesList(int n, E e) {
3215              if (n < 0)
3216                  throw new IllegalArgumentException("List length = " + n);
3217              this.n = n;
3218 <            element = o;
3218 >            element = e;
3219          }
3220  
3221          public int size() {
# Line 3324 | Line 3290 | public class Collections {
3290      public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) {
3291          if (cmp == null)
3292              return new ReverseComparator();  // Unchecked warning!!
3293 <
3293 >
3294          return new ReverseComparator2<T>(cmp);
3295      }
3296 <
3296 >
3297      /**
3298       * @serial include
3299       */
# Line 3335 | Line 3301 | public class Collections {
3301          Serializable
3302      {
3303          private static final long serialVersionUID = 4374092139857L;
3304 <
3304 >
3305          /**
3306           * The comparator specified in the static factory.  This will never
3307           * be null, as the static factory returns a ReverseComparator
# Line 3344 | Line 3310 | public class Collections {
3310           * @serial
3311           */
3312          private Comparator<T> cmp;
3313 <
3313 >
3314          ReverseComparator2(Comparator<T> cmp) {
3315              assert cmp != null;
3316              this.cmp = cmp;
3317          }
3318 <
3318 >
3319          public int compare(T t1, T t2) {
3320              return cmp.compare(t2, t1);
3321          }
# Line 3469 | Line 3435 | public class Collections {
3435              c1 = c2;
3436              c2 = tmp;
3437          }
3438 <
3438 >
3439          for (Object e : c1)
3440              if (c2.contains(e))
3441                  return false;
# Line 3493 | Line 3459 | public class Collections {
3459       * @param a the elements to insert into <tt>c</tt>
3460       * @return <tt>true</tt> if the collection changed as a result of the call
3461       * @throws UnsupportedOperationException if <tt>c</tt> does not support
3462 <     *         the <tt>add</tt> method
3462 >     *         the <tt>add</tt> operation.
3463       * @throws NullPointerException if <tt>elements</tt> contains one or more
3464 <     *         null values and <tt>c</tt> does not support null elements, or
3464 >     *         null values and <tt>c</tt> does not permit null elements, or
3465       *         if <tt>c</tt> or <tt>elements</tt> are <tt>null</tt>
3466 <     * @throws IllegalArgumentException if some aspect of a value in
3466 >     * @throws IllegalArgumentException if some property of a value in
3467       *         <tt>elements</tt> prevents it from being added to <tt>c</tt>
3468       * @see Collection#addAll(Collection)
3469       * @since 1.5
# Line 3599 | Line 3565 | public class Collections {
3565          return new AsLIFOQueue<T>(deque);
3566      }
3567  
3568 <    static class AsLIFOQueue<E> extends AbstractQueue<E>
3568 >    static class AsLIFOQueue<E> extends AbstractQueue<E>
3569          implements Queue<E>, Serializable {
3570          private final Deque<E> q;
3571          AsLIFOQueue(Deque<E> q)            { this.q = q; }
3572 <        public boolean offer(E o)          { return q.offerFirst(o); }
3572 >        public boolean offer(E e)          { return q.offerFirst(e); }
3573          public E poll()                    { return q.pollFirst(); }
3574          public E remove()                  { return q.removeFirst(); }
3575          public E peek()                    { return q.peekFirst(); }
# Line 3614 | Line 3580 | public class Collections {
3580          public Iterator<E> iterator()      { return q.iterator(); }
3581          public Object[] toArray()          { return q.toArray(); }
3582          public <T> T[] toArray(T[] a)      { return q.toArray(a); }
3583 <        public boolean add(E o)            { return q.offerFirst(o); }
3583 >        public boolean add(E e)            { return q.offerFirst(e); }
3584          public boolean remove(Object o)    { return q.remove(o); }
3585          public void clear()                { q.clear(); }
3586      }

Diff Legend

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