src/share/classes/java/util/Collections.java

Print this page




 196      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 197      * January 1993.
 198      *
 199      * <p>This implementation dumps the specified list into an array, sorts
 200      * the array, and iterates over the list resetting each element
 201      * from the corresponding position in the array.  This avoids the
 202      * n<sup>2</sup> log(n) performance that would result from attempting
 203      * to sort a linked list in place.
 204      *
 205      * @param  list the list to be sorted.
 206      * @param  c the comparator to determine the order of the list.  A
 207      *        {@code null} value indicates that the elements' <i>natural
 208      *        ordering</i> should be used.
 209      * @throws ClassCastException if the list contains elements that are not
 210      *         <i>mutually comparable</i> using the specified comparator.
 211      * @throws UnsupportedOperationException if the specified list's
 212      *         list-iterator does not support the {@code set} operation.
 213      * @throws IllegalArgumentException (optional) if the comparator is
 214      *         found to violate the {@link Comparator} contract
 215      */
 216     @SuppressWarnings({ "unchecked", "rawtypes" })
 217     public static <T> void sort(List<T> list, Comparator<? super T> c) {
 218         Object[] a = list.toArray();
 219         Arrays.sort(a, (Comparator)c);
 220         ListIterator<T> i = list.listIterator();
 221         for (int j=0; j<a.length; j++) {
 222             i.next();
 223             i.set((T)a[j]);
 224         }
 225     }
 226 
 227 
 228     /**
 229      * Searches the specified list for the specified object using the binary
 230      * search algorithm.  The list must be sorted into ascending order
 231      * according to the {@linkplain Comparable natural ordering} of its
 232      * elements (as by the {@link #sort(List)} method) prior to making this
 233      * call.  If it is not sorted, the results are undefined.  If the list
 234      * contains multiple elements equal to the specified object, there is no
 235      * guarantee which one will be found.
 236      *


 401 
 402             if (cmp < 0)
 403                 low = mid + 1;
 404             else if (cmp > 0)
 405                 high = mid - 1;
 406             else
 407                 return mid; // key found
 408         }
 409         return -(low + 1);  // key not found
 410     }
 411 
 412     /**
 413      * Reverses the order of the elements in the specified list.<p>
 414      *
 415      * This method runs in linear time.
 416      *
 417      * @param  list the list whose elements are to be reversed.
 418      * @throws UnsupportedOperationException if the specified list or
 419      *         its list-iterator does not support the <tt>set</tt> operation.
 420      */
 421     @SuppressWarnings({ "rawtypes", "unchecked" })
 422     public static void reverse(List<?> list) {
 423         int size = list.size();
 424         if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
 425             for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
 426                 swap(list, i, j);
 427         } else {
 428             // instead of using a raw type here, it's possible to capture
 429             // the wildcard but it will require a call to a supplementary
 430             // private method
 431             ListIterator fwd = list.listIterator();
 432             ListIterator rev = list.listIterator(size);
 433             for (int i=0, mid=list.size()>>1; i<mid; i++) {
 434                 Object tmp = fwd.next();
 435                 fwd.set(rev.previous());
 436                 rev.set(tmp);
 437             }
 438         }
 439     }
 440 
 441     /**


 480      * assuming that the source of randomness is fair.<p>
 481      *
 482      * This implementation traverses the list backwards, from the last element
 483      * up to the second, repeatedly swapping a randomly selected element into
 484      * the "current position".  Elements are randomly selected from the
 485      * portion of the list that runs from the first element to the current
 486      * position, inclusive.<p>
 487      *
 488      * This method runs in linear time.  If the specified list does not
 489      * implement the {@link RandomAccess} interface and is large, this
 490      * implementation dumps the specified list into an array before shuffling
 491      * it, and dumps the shuffled array back into the list.  This avoids the
 492      * quadratic behavior that would result from shuffling a "sequential
 493      * access" list in place.
 494      *
 495      * @param  list the list to be shuffled.
 496      * @param  rnd the source of randomness to use to shuffle the list.
 497      * @throws UnsupportedOperationException if the specified list or its
 498      *         list-iterator does not support the <tt>set</tt> operation.
 499      */
 500     @SuppressWarnings({ "rawtypes", "unchecked" })
 501     public static void shuffle(List<?> list, Random rnd) {
 502         int size = list.size();
 503         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
 504             for (int i=size; i>1; i--)
 505                 swap(list, i-1, rnd.nextInt(i));
 506         } else {
 507             Object arr[] = list.toArray();
 508 
 509             // Shuffle array
 510             for (int i=size; i>1; i--)
 511                 swap(arr, i-1, rnd.nextInt(i));
 512 
 513             // Dump array back into list
 514             // instead of using a raw type here, it's possible to capture
 515             // the wildcard but it will require a call to a supplementary
 516             // private method
 517             ListIterator it = list.listIterator();
 518             for (int i=0; i<arr.length; i++) {
 519                 it.next();
 520                 it.set(arr[i]);
 521             }
 522         }
 523     }
 524 
 525     /**
 526      * Swaps the elements at the specified positions in the specified list.
 527      * (If the specified positions are equal, invoking this method leaves
 528      * the list unchanged.)
 529      *
 530      * @param list The list in which to swap elements.
 531      * @param i the index of one element to be swapped.
 532      * @param j the index of the other element to be swapped.
 533      * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
 534      *         is out of range (i &lt; 0 || i &gt;= list.size()
 535      *         || j &lt; 0 || j &gt;= list.size()).
 536      * @since 1.4
 537      */
 538     @SuppressWarnings({ "rawtypes", "unchecked" })
 539     public static void swap(List<?> list, int i, int j) {
 540         // instead of using a raw type here, it's possible to capture
 541         // the wildcard but it will require a call to a supplementary
 542         // private method
 543         final List l = list;
 544         l.set(i, l.set(j, l.get(i)));
 545     }
 546 
 547     /**
 548      * Swaps the two specified elements in the specified array.
 549      */
 550     private static void swap(Object[] arr, int i, int j) {
 551         Object tmp = arr[i];
 552         arr[i] = arr[j];
 553         arr[j] = tmp;
 554     }
 555 
 556     /**
 557      * Replaces all of the elements of the specified list with the specified
 558      * element. <p>


 652      * order induced by the specified comparator.  All elements in the
 653      * collection must be <i>mutually comparable</i> by the specified
 654      * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
 655      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
 656      * <tt>e2</tt> in the collection).<p>
 657      *
 658      * This method iterates over the entire collection, hence it requires
 659      * time proportional to the size of the collection.
 660      *
 661      * @param  coll the collection whose minimum element is to be determined.
 662      * @param  comp the comparator with which to determine the minimum element.
 663      *         A <tt>null</tt> value indicates that the elements' <i>natural
 664      *         ordering</i> should be used.
 665      * @return the minimum element of the given collection, according
 666      *         to the specified comparator.
 667      * @throws ClassCastException if the collection contains elements that are
 668      *         not <i>mutually comparable</i> using the specified comparator.
 669      * @throws NoSuchElementException if the collection is empty.
 670      * @see Comparable
 671      */
 672     @SuppressWarnings({ "unchecked", "rawtypes" })
 673     public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
 674         if (comp==null)
 675             return (T)min((Collection) coll);
 676 
 677         Iterator<? extends T> i = coll.iterator();
 678         T candidate = i.next();
 679 
 680         while (i.hasNext()) {
 681             T next = i.next();
 682             if (comp.compare(next, candidate) < 0)
 683                 candidate = next;
 684         }
 685         return candidate;
 686     }
 687 
 688     /**
 689      * Returns the maximum element of the given collection, according to the
 690      * <i>natural ordering</i> of its elements.  All elements in the
 691      * collection must implement the <tt>Comparable</tt> interface.
 692      * Furthermore, all elements in the collection must be <i>mutually


 723      * order induced by the specified comparator.  All elements in the
 724      * collection must be <i>mutually comparable</i> by the specified
 725      * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
 726      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
 727      * <tt>e2</tt> in the collection).<p>
 728      *
 729      * This method iterates over the entire collection, hence it requires
 730      * time proportional to the size of the collection.
 731      *
 732      * @param  coll the collection whose maximum element is to be determined.
 733      * @param  comp the comparator with which to determine the maximum element.
 734      *         A <tt>null</tt> value indicates that the elements' <i>natural
 735      *        ordering</i> should be used.
 736      * @return the maximum element of the given collection, according
 737      *         to the specified comparator.
 738      * @throws ClassCastException if the collection contains elements that are
 739      *         not <i>mutually comparable</i> using the specified comparator.
 740      * @throws NoSuchElementException if the collection is empty.
 741      * @see Comparable
 742      */
 743     @SuppressWarnings({ "unchecked", "rawtypes" })
 744     public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
 745         if (comp==null)
 746             return (T)max((Collection) coll);
 747 
 748         Iterator<? extends T> i = coll.iterator();
 749         T candidate = i.next();
 750 
 751         while (i.hasNext()) {
 752             T next = i.next();
 753             if (comp.compare(next, candidate) > 0)
 754                 candidate = next;
 755         }
 756         return candidate;
 757     }
 758 
 759     /**
 760      * Rotates the elements in the specified list by the specified distance.
 761      * After calling this method, the element at index <tt>i</tt> will be
 762      * the element previously at index <tt>(i - distance)</tt> mod
 763      * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>


1386                 values = unmodifiableCollection(m.values());
1387             return values;
1388         }
1389 
1390         public boolean equals(Object o) {return o == this || m.equals(o);}
1391         public int hashCode()           {return m.hashCode();}
1392         public String toString()        {return m.toString();}
1393 
1394         /**
1395          * We need this class in addition to UnmodifiableSet as
1396          * Map.Entries themselves permit modification of the backing Map
1397          * via their setValue operation.  This class is subtle: there are
1398          * many possible attacks that must be thwarted.
1399          *
1400          * @serial include
1401          */
1402         static class UnmodifiableEntrySet<K,V>
1403             extends UnmodifiableSet<Map.Entry<K,V>> {
1404             private static final long serialVersionUID = 7854390611657943733L;
1405 
1406             @SuppressWarnings({ "unchecked", "rawtypes" })
1407             UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1408                 // Need to cast to raw in order to work around a limitation in the type system
1409                 super((Set)s);
1410             }
1411             public Iterator<Map.Entry<K,V>> iterator() {
1412                 return new Iterator<Map.Entry<K,V>>() {
1413                     private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1414 
1415                     public boolean hasNext() {
1416                         return i.hasNext();
1417                     }
1418                     public Map.Entry<K,V> next() {
1419                         return new UnmodifiableEntry<>(i.next());
1420                     }
1421                     public void remove() {
1422                         throw new UnsupportedOperationException();
1423                     }
1424                 };
1425             }
1426 


3155      * @since 1.7
3156      */
3157     @SuppressWarnings("unchecked")
3158     public static <T> Enumeration<T> emptyEnumeration() {
3159         return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
3160     }
3161 
3162     private static class EmptyEnumeration<E> implements Enumeration<E> {
3163         static final EmptyEnumeration<Object> EMPTY_ENUMERATION
3164             = new EmptyEnumeration<>();
3165 
3166         public boolean hasMoreElements() { return false; }
3167         public E nextElement() { throw new NoSuchElementException(); }
3168     }
3169 
3170     /**
3171      * The empty set (immutable).  This set is serializable.
3172      *
3173      * @see #emptySet()
3174      */
3175     @SuppressWarnings("unchecked")
3176     public static final Set EMPTY_SET = new EmptySet<>();
3177 
3178     /**
3179      * Returns the empty set (immutable).  This set is serializable.
3180      * Unlike the like-named field, this method is parameterized.
3181      *
3182      * <p>This example illustrates the type-safe way to obtain an empty set:
3183      * <pre>
3184      *     Set&lt;String&gt; s = Collections.emptySet();
3185      * </pre>
3186      * Implementation note:  Implementations of this method need not
3187      * create a separate <tt>Set</tt> object for each call.   Using this
3188      * method is likely to have comparable cost to using the like-named
3189      * field.  (Unlike this method, the field does not provide type safety.)
3190      *
3191      * @see #EMPTY_SET
3192      * @since 1.5
3193      */
3194     @SuppressWarnings("unchecked")
3195     public static final <T> Set<T> emptySet() {


3254     {
3255         private static final long serialVersionUID = 6316515401502265487L;
3256         public Iterator<E> iterator() { return emptyIterator(); }
3257         public int size() {return 0;}
3258         public boolean isEmpty() {return true;}
3259         public boolean contains(Object obj) {return false;}
3260         public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3261         public Object[] toArray() { return new Object[0]; }
3262 
3263         public <E> E[] toArray(E[] a) {
3264             if (a.length > 0)
3265                 a[0] = null;
3266             return a;
3267         }
3268 
3269         // Preserves singleton property
3270         private Object readResolve() {
3271             return new EmptySortedSet<>();
3272         }
3273 
3274         public Comparator comparator() {

3275             return null;
3276         }
3277 


3278         public SortedSet<E> subSet(Object fromElement, Object toElement) {
3279             Objects.requireNonNull(fromElement);
3280             Objects.requireNonNull(toElement);
3281 
3282             if (!(fromElement instanceof Comparable) ||
3283                     !(toElement instanceof Comparable))
3284             {
3285                 throw new ClassCastException();
3286             }
3287 
3288             if ((((Comparable)fromElement).compareTo(toElement) >= 0) ||
3289                     (((Comparable)toElement).compareTo(fromElement) < 0))
3290             {
3291                 throw new IllegalArgumentException();
3292             }
3293 
3294             return emptySortedSet();
3295         }
3296 

3297         public SortedSet<E> headSet(Object toElement) {
3298             Objects.requireNonNull(toElement);
3299 
3300             if (!(toElement instanceof Comparable)) {
3301                 throw new ClassCastException();
3302             }
3303 
3304             return emptySortedSet();
3305         }
3306 

3307         public SortedSet<E> tailSet(Object fromElement) {
3308             Objects.requireNonNull(fromElement);
3309 
3310             if (!(fromElement instanceof Comparable)) {
3311                 throw new ClassCastException();
3312             }
3313 
3314             return emptySortedSet();
3315         }
3316 

3317         public E first() {
3318             throw new NoSuchElementException();
3319         }
3320 

3321         public E last() {
3322             throw new NoSuchElementException();
3323         }
3324     }
3325 
3326     /**
3327      * The empty list (immutable).  This list is serializable.
3328      *
3329      * @see #emptyList()
3330      */
3331     @SuppressWarnings("unchecked")
3332     public static final List EMPTY_LIST = new EmptyList<>();
3333 
3334     /**
3335      * Returns the empty list (immutable).  This list is serializable.
3336      *
3337      * <p>This example illustrates the type-safe way to obtain an empty list:
3338      * <pre>
3339      *     List&lt;String&gt; s = Collections.emptyList();
3340      * </pre>
3341      * Implementation note:  Implementations of this method need not
3342      * create a separate <tt>List</tt> object for each call.   Using this
3343      * method is likely to have comparable cost to using the like-named
3344      * field.  (Unlike this method, the field does not provide type safety.)
3345      *
3346      * @see #EMPTY_LIST
3347      * @since 1.5
3348      */
3349     @SuppressWarnings("unchecked")
3350     public static final <T> List<T> emptyList() {
3351         return (List<T>) EMPTY_LIST;


3385         }
3386 
3387         public boolean equals(Object o) {
3388             return (o instanceof List) && ((List<?>)o).isEmpty();
3389         }
3390 
3391         public int hashCode() { return 1; }
3392 
3393         // Preserves singleton property
3394         private Object readResolve() {
3395             return EMPTY_LIST;
3396         }
3397     }
3398 
3399     /**
3400      * The empty map (immutable).  This map is serializable.
3401      *
3402      * @see #emptyMap()
3403      * @since 1.3
3404      */
3405     @SuppressWarnings("unchecked")
3406     public static final Map EMPTY_MAP = new EmptyMap<>();
3407 
3408     /**
3409      * Returns the empty map (immutable).  This map is serializable.
3410      *
3411      * <p>This example illustrates the type-safe way to obtain an empty set:
3412      * <pre>
3413      *     Map&lt;String, Date&gt; s = Collections.emptyMap();
3414      * </pre>
3415      * Implementation note:  Implementations of this method need not
3416      * create a separate <tt>Map</tt> object for each call.   Using this
3417      * method is likely to have comparable cost to using the like-named
3418      * field.  (Unlike this method, the field does not provide type safety.)
3419      *
3420      * @see #EMPTY_MAP
3421      * @since 1.5
3422      */
3423     @SuppressWarnings("unchecked")
3424     public static final <K,V> Map<K,V> emptyMap() {
3425         return (Map<K,V>) EMPTY_MAP;


3668         }
3669 
3670         public int lastIndexOf(Object o) {
3671             return contains(o) ? n - 1 : -1;
3672         }
3673 
3674         public E get(int index) {
3675             if (index < 0 || index >= n)
3676                 throw new IndexOutOfBoundsException("Index: "+index+
3677                                                     ", Size: "+n);
3678             return element;
3679         }
3680 
3681         public Object[] toArray() {
3682             final Object[] a = new Object[n];
3683             if (element != null)
3684                 Arrays.fill(a, 0, n, element);
3685             return a;
3686         }
3687 

3688         public <T> T[] toArray(T[] a) {
3689             final int n = this.n;
3690             if (a.length < n) {
3691                 a = (T[])java.lang.reflect.Array
3692                     .newInstance(a.getClass().getComponentType(), n);
3693                 if (element != null)
3694                     Arrays.fill(a, 0, n, element);
3695             } else {
3696                 Arrays.fill(a, 0, n, element);
3697                 if (a.length > n)
3698                     a[n] = null;
3699             }
3700             return a;
3701         }
3702 
3703         public List<E> subList(int fromIndex, int toIndex) {
3704             if (fromIndex < 0)
3705                 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3706             if (toIndex > n)
3707                 throw new IndexOutOfBoundsException("toIndex = " + toIndex);


3714 
3715     /**
3716      * Returns a comparator that imposes the reverse of the <em>natural
3717      * ordering</em> on a collection of objects that implement the
3718      * {@code Comparable} interface.  (The natural ordering is the ordering
3719      * imposed by the objects' own {@code compareTo} method.)  This enables a
3720      * simple idiom for sorting (or maintaining) collections (or arrays) of
3721      * objects that implement the {@code Comparable} interface in
3722      * reverse-natural-order.  For example, suppose {@code a} is an array of
3723      * strings. Then: <pre>
3724      *          Arrays.sort(a, Collections.reverseOrder());
3725      * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
3726      *
3727      * The returned comparator is serializable.
3728      *
3729      * @return A comparator that imposes the reverse of the <i>natural
3730      *         ordering</i> on a collection of objects that implement
3731      *         the <tt>Comparable</tt> interface.
3732      * @see Comparable
3733      */

3734     public static <T> Comparator<T> reverseOrder() {
3735         return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3736     }
3737 
3738     /**
3739      * @serial include
3740      */
3741     private static class ReverseComparator
3742         implements Comparator<Comparable<Object>>, Serializable {
3743 
3744         private static final long serialVersionUID = 7207038068494060240L;
3745 
3746         static final ReverseComparator REVERSE_ORDER
3747             = new ReverseComparator();
3748 
3749         public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3750             return c2.compareTo(c1);
3751         }
3752 
3753         private Object readResolve() { return reverseOrder(); }




 196      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 197      * January 1993.
 198      *
 199      * <p>This implementation dumps the specified list into an array, sorts
 200      * the array, and iterates over the list resetting each element
 201      * from the corresponding position in the array.  This avoids the
 202      * n<sup>2</sup> log(n) performance that would result from attempting
 203      * to sort a linked list in place.
 204      *
 205      * @param  list the list to be sorted.
 206      * @param  c the comparator to determine the order of the list.  A
 207      *        {@code null} value indicates that the elements' <i>natural
 208      *        ordering</i> should be used.
 209      * @throws ClassCastException if the list contains elements that are not
 210      *         <i>mutually comparable</i> using the specified comparator.
 211      * @throws UnsupportedOperationException if the specified list's
 212      *         list-iterator does not support the {@code set} operation.
 213      * @throws IllegalArgumentException (optional) if the comparator is
 214      *         found to violate the {@link Comparator} contract
 215      */
 216     @SuppressWarnings({"unchecked", "rawtypes"})
 217     public static <T> void sort(List<T> list, Comparator<? super T> c) {
 218         Object[] a = list.toArray();
 219         Arrays.sort(a, (Comparator)c);
 220         ListIterator<T> i = list.listIterator();
 221         for (int j=0; j<a.length; j++) {
 222             i.next();
 223             i.set((T)a[j]);
 224         }
 225     }
 226 
 227 
 228     /**
 229      * Searches the specified list for the specified object using the binary
 230      * search algorithm.  The list must be sorted into ascending order
 231      * according to the {@linkplain Comparable natural ordering} of its
 232      * elements (as by the {@link #sort(List)} method) prior to making this
 233      * call.  If it is not sorted, the results are undefined.  If the list
 234      * contains multiple elements equal to the specified object, there is no
 235      * guarantee which one will be found.
 236      *


 401 
 402             if (cmp < 0)
 403                 low = mid + 1;
 404             else if (cmp > 0)
 405                 high = mid - 1;
 406             else
 407                 return mid; // key found
 408         }
 409         return -(low + 1);  // key not found
 410     }
 411 
 412     /**
 413      * Reverses the order of the elements in the specified list.<p>
 414      *
 415      * This method runs in linear time.
 416      *
 417      * @param  list the list whose elements are to be reversed.
 418      * @throws UnsupportedOperationException if the specified list or
 419      *         its list-iterator does not support the <tt>set</tt> operation.
 420      */
 421     @SuppressWarnings({"rawtypes", "unchecked"})
 422     public static void reverse(List<?> list) {
 423         int size = list.size();
 424         if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
 425             for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
 426                 swap(list, i, j);
 427         } else {
 428             // instead of using a raw type here, it's possible to capture
 429             // the wildcard but it will require a call to a supplementary
 430             // private method
 431             ListIterator fwd = list.listIterator();
 432             ListIterator rev = list.listIterator(size);
 433             for (int i=0, mid=list.size()>>1; i<mid; i++) {
 434                 Object tmp = fwd.next();
 435                 fwd.set(rev.previous());
 436                 rev.set(tmp);
 437             }
 438         }
 439     }
 440 
 441     /**


 480      * assuming that the source of randomness is fair.<p>
 481      *
 482      * This implementation traverses the list backwards, from the last element
 483      * up to the second, repeatedly swapping a randomly selected element into
 484      * the "current position".  Elements are randomly selected from the
 485      * portion of the list that runs from the first element to the current
 486      * position, inclusive.<p>
 487      *
 488      * This method runs in linear time.  If the specified list does not
 489      * implement the {@link RandomAccess} interface and is large, this
 490      * implementation dumps the specified list into an array before shuffling
 491      * it, and dumps the shuffled array back into the list.  This avoids the
 492      * quadratic behavior that would result from shuffling a "sequential
 493      * access" list in place.
 494      *
 495      * @param  list the list to be shuffled.
 496      * @param  rnd the source of randomness to use to shuffle the list.
 497      * @throws UnsupportedOperationException if the specified list or its
 498      *         list-iterator does not support the <tt>set</tt> operation.
 499      */
 500     @SuppressWarnings({"rawtypes", "unchecked"})
 501     public static void shuffle(List<?> list, Random rnd) {
 502         int size = list.size();
 503         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
 504             for (int i=size; i>1; i--)
 505                 swap(list, i-1, rnd.nextInt(i));
 506         } else {
 507             Object arr[] = list.toArray();
 508 
 509             // Shuffle array
 510             for (int i=size; i>1; i--)
 511                 swap(arr, i-1, rnd.nextInt(i));
 512 
 513             // Dump array back into list
 514             // instead of using a raw type here, it's possible to capture
 515             // the wildcard but it will require a call to a supplementary
 516             // private method
 517             ListIterator it = list.listIterator();
 518             for (int i=0; i<arr.length; i++) {
 519                 it.next();
 520                 it.set(arr[i]);
 521             }
 522         }
 523     }
 524 
 525     /**
 526      * Swaps the elements at the specified positions in the specified list.
 527      * (If the specified positions are equal, invoking this method leaves
 528      * the list unchanged.)
 529      *
 530      * @param list The list in which to swap elements.
 531      * @param i the index of one element to be swapped.
 532      * @param j the index of the other element to be swapped.
 533      * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
 534      *         is out of range (i &lt; 0 || i &gt;= list.size()
 535      *         || j &lt; 0 || j &gt;= list.size()).
 536      * @since 1.4
 537      */
 538     @SuppressWarnings({"rawtypes", "unchecked"})
 539     public static void swap(List<?> list, int i, int j) {
 540         // instead of using a raw type here, it's possible to capture
 541         // the wildcard but it will require a call to a supplementary
 542         // private method
 543         final List l = list;
 544         l.set(i, l.set(j, l.get(i)));
 545     }
 546 
 547     /**
 548      * Swaps the two specified elements in the specified array.
 549      */
 550     private static void swap(Object[] arr, int i, int j) {
 551         Object tmp = arr[i];
 552         arr[i] = arr[j];
 553         arr[j] = tmp;
 554     }
 555 
 556     /**
 557      * Replaces all of the elements of the specified list with the specified
 558      * element. <p>


 652      * order induced by the specified comparator.  All elements in the
 653      * collection must be <i>mutually comparable</i> by the specified
 654      * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
 655      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
 656      * <tt>e2</tt> in the collection).<p>
 657      *
 658      * This method iterates over the entire collection, hence it requires
 659      * time proportional to the size of the collection.
 660      *
 661      * @param  coll the collection whose minimum element is to be determined.
 662      * @param  comp the comparator with which to determine the minimum element.
 663      *         A <tt>null</tt> value indicates that the elements' <i>natural
 664      *         ordering</i> should be used.
 665      * @return the minimum element of the given collection, according
 666      *         to the specified comparator.
 667      * @throws ClassCastException if the collection contains elements that are
 668      *         not <i>mutually comparable</i> using the specified comparator.
 669      * @throws NoSuchElementException if the collection is empty.
 670      * @see Comparable
 671      */
 672     @SuppressWarnings({"unchecked", "rawtypes"})
 673     public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
 674         if (comp==null)
 675             return (T)min((Collection) coll);
 676 
 677         Iterator<? extends T> i = coll.iterator();
 678         T candidate = i.next();
 679 
 680         while (i.hasNext()) {
 681             T next = i.next();
 682             if (comp.compare(next, candidate) < 0)
 683                 candidate = next;
 684         }
 685         return candidate;
 686     }
 687 
 688     /**
 689      * Returns the maximum element of the given collection, according to the
 690      * <i>natural ordering</i> of its elements.  All elements in the
 691      * collection must implement the <tt>Comparable</tt> interface.
 692      * Furthermore, all elements in the collection must be <i>mutually


 723      * order induced by the specified comparator.  All elements in the
 724      * collection must be <i>mutually comparable</i> by the specified
 725      * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
 726      * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
 727      * <tt>e2</tt> in the collection).<p>
 728      *
 729      * This method iterates over the entire collection, hence it requires
 730      * time proportional to the size of the collection.
 731      *
 732      * @param  coll the collection whose maximum element is to be determined.
 733      * @param  comp the comparator with which to determine the maximum element.
 734      *         A <tt>null</tt> value indicates that the elements' <i>natural
 735      *        ordering</i> should be used.
 736      * @return the maximum element of the given collection, according
 737      *         to the specified comparator.
 738      * @throws ClassCastException if the collection contains elements that are
 739      *         not <i>mutually comparable</i> using the specified comparator.
 740      * @throws NoSuchElementException if the collection is empty.
 741      * @see Comparable
 742      */
 743     @SuppressWarnings({"unchecked", "rawtypes"})
 744     public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
 745         if (comp==null)
 746             return (T)max((Collection) coll);
 747 
 748         Iterator<? extends T> i = coll.iterator();
 749         T candidate = i.next();
 750 
 751         while (i.hasNext()) {
 752             T next = i.next();
 753             if (comp.compare(next, candidate) > 0)
 754                 candidate = next;
 755         }
 756         return candidate;
 757     }
 758 
 759     /**
 760      * Rotates the elements in the specified list by the specified distance.
 761      * After calling this method, the element at index <tt>i</tt> will be
 762      * the element previously at index <tt>(i - distance)</tt> mod
 763      * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>


1386                 values = unmodifiableCollection(m.values());
1387             return values;
1388         }
1389 
1390         public boolean equals(Object o) {return o == this || m.equals(o);}
1391         public int hashCode()           {return m.hashCode();}
1392         public String toString()        {return m.toString();}
1393 
1394         /**
1395          * We need this class in addition to UnmodifiableSet as
1396          * Map.Entries themselves permit modification of the backing Map
1397          * via their setValue operation.  This class is subtle: there are
1398          * many possible attacks that must be thwarted.
1399          *
1400          * @serial include
1401          */
1402         static class UnmodifiableEntrySet<K,V>
1403             extends UnmodifiableSet<Map.Entry<K,V>> {
1404             private static final long serialVersionUID = 7854390611657943733L;
1405 
1406             @SuppressWarnings({"unchecked", "rawtypes"})
1407             UnmodifiableEntrySet(Set<? extends Map.Entry<? extends K, ? extends V>> s) {
1408                 // Need to cast to raw in order to work around a limitation in the type system
1409                 super((Set)s);
1410             }
1411             public Iterator<Map.Entry<K,V>> iterator() {
1412                 return new Iterator<Map.Entry<K,V>>() {
1413                     private final Iterator<? extends Map.Entry<? extends K, ? extends V>> i = c.iterator();
1414 
1415                     public boolean hasNext() {
1416                         return i.hasNext();
1417                     }
1418                     public Map.Entry<K,V> next() {
1419                         return new UnmodifiableEntry<>(i.next());
1420                     }
1421                     public void remove() {
1422                         throw new UnsupportedOperationException();
1423                     }
1424                 };
1425             }
1426 


3155      * @since 1.7
3156      */
3157     @SuppressWarnings("unchecked")
3158     public static <T> Enumeration<T> emptyEnumeration() {
3159         return (Enumeration<T>) EmptyEnumeration.EMPTY_ENUMERATION;
3160     }
3161 
3162     private static class EmptyEnumeration<E> implements Enumeration<E> {
3163         static final EmptyEnumeration<Object> EMPTY_ENUMERATION
3164             = new EmptyEnumeration<>();
3165 
3166         public boolean hasMoreElements() { return false; }
3167         public E nextElement() { throw new NoSuchElementException(); }
3168     }
3169 
3170     /**
3171      * The empty set (immutable).  This set is serializable.
3172      *
3173      * @see #emptySet()
3174      */
3175     @SuppressWarnings("rawtypes")
3176     public static final Set EMPTY_SET = new EmptySet<>();
3177 
3178     /**
3179      * Returns the empty set (immutable).  This set is serializable.
3180      * Unlike the like-named field, this method is parameterized.
3181      *
3182      * <p>This example illustrates the type-safe way to obtain an empty set:
3183      * <pre>
3184      *     Set&lt;String&gt; s = Collections.emptySet();
3185      * </pre>
3186      * Implementation note:  Implementations of this method need not
3187      * create a separate <tt>Set</tt> object for each call.   Using this
3188      * method is likely to have comparable cost to using the like-named
3189      * field.  (Unlike this method, the field does not provide type safety.)
3190      *
3191      * @see #EMPTY_SET
3192      * @since 1.5
3193      */
3194     @SuppressWarnings("unchecked")
3195     public static final <T> Set<T> emptySet() {


3254     {
3255         private static final long serialVersionUID = 6316515401502265487L;
3256         public Iterator<E> iterator() { return emptyIterator(); }
3257         public int size() {return 0;}
3258         public boolean isEmpty() {return true;}
3259         public boolean contains(Object obj) {return false;}
3260         public boolean containsAll(Collection<?> c) { return c.isEmpty(); }
3261         public Object[] toArray() { return new Object[0]; }
3262 
3263         public <E> E[] toArray(E[] a) {
3264             if (a.length > 0)
3265                 a[0] = null;
3266             return a;
3267         }
3268 
3269         // Preserves singleton property
3270         private Object readResolve() {
3271             return new EmptySortedSet<>();
3272         }
3273 
3274         @Override
3275         public Comparator<? super E> comparator() {
3276             return null;
3277         }
3278 
3279         @Override
3280         @SuppressWarnings("unchecked")
3281         public SortedSet<E> subSet(Object fromElement, Object toElement) {
3282             Objects.requireNonNull(fromElement);
3283             Objects.requireNonNull(toElement);
3284 
3285             if (!(fromElement instanceof Comparable) ||
3286                     !(toElement instanceof Comparable))
3287             {
3288                 throw new ClassCastException();
3289             }
3290 
3291             if ((((Comparable)fromElement).compareTo(toElement) >= 0) ||
3292                     (((Comparable)toElement).compareTo(fromElement) < 0))
3293             {
3294                 throw new IllegalArgumentException();
3295             }
3296 
3297             return emptySortedSet();
3298         }
3299 
3300         @Override
3301         public SortedSet<E> headSet(Object toElement) {
3302             Objects.requireNonNull(toElement);
3303 
3304             if (!(toElement instanceof Comparable)) {
3305                 throw new ClassCastException();
3306             }
3307 
3308             return emptySortedSet();
3309         }
3310 
3311         @Override
3312         public SortedSet<E> tailSet(Object fromElement) {
3313             Objects.requireNonNull(fromElement);
3314 
3315             if (!(fromElement instanceof Comparable)) {
3316                 throw new ClassCastException();
3317             }
3318 
3319             return emptySortedSet();
3320         }
3321 
3322         @Override
3323         public E first() {
3324             throw new NoSuchElementException();
3325         }
3326 
3327         @Override
3328         public E last() {
3329             throw new NoSuchElementException();
3330         }
3331     }
3332 
3333     /**
3334      * The empty list (immutable).  This list is serializable.
3335      *
3336      * @see #emptyList()
3337      */
3338     @SuppressWarnings("rawtypes")
3339     public static final List EMPTY_LIST = new EmptyList<>();
3340 
3341     /**
3342      * Returns the empty list (immutable).  This list is serializable.
3343      *
3344      * <p>This example illustrates the type-safe way to obtain an empty list:
3345      * <pre>
3346      *     List&lt;String&gt; s = Collections.emptyList();
3347      * </pre>
3348      * Implementation note:  Implementations of this method need not
3349      * create a separate <tt>List</tt> object for each call.   Using this
3350      * method is likely to have comparable cost to using the like-named
3351      * field.  (Unlike this method, the field does not provide type safety.)
3352      *
3353      * @see #EMPTY_LIST
3354      * @since 1.5
3355      */
3356     @SuppressWarnings("unchecked")
3357     public static final <T> List<T> emptyList() {
3358         return (List<T>) EMPTY_LIST;


3392         }
3393 
3394         public boolean equals(Object o) {
3395             return (o instanceof List) && ((List<?>)o).isEmpty();
3396         }
3397 
3398         public int hashCode() { return 1; }
3399 
3400         // Preserves singleton property
3401         private Object readResolve() {
3402             return EMPTY_LIST;
3403         }
3404     }
3405 
3406     /**
3407      * The empty map (immutable).  This map is serializable.
3408      *
3409      * @see #emptyMap()
3410      * @since 1.3
3411      */
3412     @SuppressWarnings("rawtypes")
3413     public static final Map EMPTY_MAP = new EmptyMap<>();
3414 
3415     /**
3416      * Returns the empty map (immutable).  This map is serializable.
3417      *
3418      * <p>This example illustrates the type-safe way to obtain an empty set:
3419      * <pre>
3420      *     Map&lt;String, Date&gt; s = Collections.emptyMap();
3421      * </pre>
3422      * Implementation note:  Implementations of this method need not
3423      * create a separate <tt>Map</tt> object for each call.   Using this
3424      * method is likely to have comparable cost to using the like-named
3425      * field.  (Unlike this method, the field does not provide type safety.)
3426      *
3427      * @see #EMPTY_MAP
3428      * @since 1.5
3429      */
3430     @SuppressWarnings("unchecked")
3431     public static final <K,V> Map<K,V> emptyMap() {
3432         return (Map<K,V>) EMPTY_MAP;


3675         }
3676 
3677         public int lastIndexOf(Object o) {
3678             return contains(o) ? n - 1 : -1;
3679         }
3680 
3681         public E get(int index) {
3682             if (index < 0 || index >= n)
3683                 throw new IndexOutOfBoundsException("Index: "+index+
3684                                                     ", Size: "+n);
3685             return element;
3686         }
3687 
3688         public Object[] toArray() {
3689             final Object[] a = new Object[n];
3690             if (element != null)
3691                 Arrays.fill(a, 0, n, element);
3692             return a;
3693         }
3694 
3695         @SuppressWarnings("unchecked")
3696         public <T> T[] toArray(T[] a) {
3697             final int n = this.n;
3698             if (a.length < n) {
3699                 a = (T[])java.lang.reflect.Array
3700                     .newInstance(a.getClass().getComponentType(), n);
3701                 if (element != null)
3702                     Arrays.fill(a, 0, n, element);
3703             } else {
3704                 Arrays.fill(a, 0, n, element);
3705                 if (a.length > n)
3706                     a[n] = null;
3707             }
3708             return a;
3709         }
3710 
3711         public List<E> subList(int fromIndex, int toIndex) {
3712             if (fromIndex < 0)
3713                 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
3714             if (toIndex > n)
3715                 throw new IndexOutOfBoundsException("toIndex = " + toIndex);


3722 
3723     /**
3724      * Returns a comparator that imposes the reverse of the <em>natural
3725      * ordering</em> on a collection of objects that implement the
3726      * {@code Comparable} interface.  (The natural ordering is the ordering
3727      * imposed by the objects' own {@code compareTo} method.)  This enables a
3728      * simple idiom for sorting (or maintaining) collections (or arrays) of
3729      * objects that implement the {@code Comparable} interface in
3730      * reverse-natural-order.  For example, suppose {@code a} is an array of
3731      * strings. Then: <pre>
3732      *          Arrays.sort(a, Collections.reverseOrder());
3733      * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
3734      *
3735      * The returned comparator is serializable.
3736      *
3737      * @return A comparator that imposes the reverse of the <i>natural
3738      *         ordering</i> on a collection of objects that implement
3739      *         the <tt>Comparable</tt> interface.
3740      * @see Comparable
3741      */
3742     @SuppressWarnings("unchecked")
3743     public static <T> Comparator<T> reverseOrder() {
3744         return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
3745     }
3746 
3747     /**
3748      * @serial include
3749      */
3750     private static class ReverseComparator
3751         implements Comparator<Comparable<Object>>, Serializable {
3752 
3753         private static final long serialVersionUID = 7207038068494060240L;
3754 
3755         static final ReverseComparator REVERSE_ORDER
3756             = new ReverseComparator();
3757 
3758         public int compare(Comparable<Object> c1, Comparable<Object> c2) {
3759             return c2.compareTo(c1);
3760         }
3761 
3762         private Object readResolve() { return reverseOrder(); }