442      *
 443      * This method runs in linear time.  If the specified list does not
 444      * implement the {@link RandomAccess} interface and is large, this
 445      * implementation dumps the specified list into an array before shuffling
 446      * it, and dumps the shuffled array back into the list.  This avoids the
 447      * quadratic behavior that would result from shuffling a "sequential
 448      * access" list in place.
 449      *
 450      * @param  list the list to be shuffled.
 451      * @param  rnd the source of randomness to use to shuffle the list.
 452      * @throws UnsupportedOperationException if the specified list or its
 453      *         list-iterator does not support the {@code set} operation.
 454      */
 455     @SuppressWarnings({"rawtypes", "unchecked"})
 456     public static void shuffle(List<?> list, Random rnd) {
 457         int size = list.size();
 458         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
 459             for (int i=size; i>1; i--)
 460                 swap(list, i-1, rnd.nextInt(i));
 461         } else {
 462             Object arr[] = list.toArray();
 463 
 464             // Shuffle array
 465             for (int i=size; i>1; i--)
 466                 swap(arr, i-1, rnd.nextInt(i));
 467 
 468             // Dump array back into list
 469             // instead of using a raw type here, it's possible to capture
 470             // the wildcard but it will require a call to a supplementary
 471             // private method
 472             ListIterator it = list.listIterator();
 473             for (Object e : arr) {
 474                 it.next();
 475                 it.set(e);
 476             }
 477         }
 478     }
 479 
 480     /**
 481      * Swaps the elements at the specified positions in the specified list.
 482      * (If the specified positions are equal, invoking this method leaves

 442      *
 443      * This method runs in linear time.  If the specified list does not
 444      * implement the {@link RandomAccess} interface and is large, this
 445      * implementation dumps the specified list into an array before shuffling
 446      * it, and dumps the shuffled array back into the list.  This avoids the
 447      * quadratic behavior that would result from shuffling a "sequential
 448      * access" list in place.
 449      *
 450      * @param  list the list to be shuffled.
 451      * @param  rnd the source of randomness to use to shuffle the list.
 452      * @throws UnsupportedOperationException if the specified list or its
 453      *         list-iterator does not support the {@code set} operation.
 454      */
 455     @SuppressWarnings({"rawtypes", "unchecked"})
 456     public static void shuffle(List<?> list, Random rnd) {
 457         int size = list.size();
 458         if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
 459             for (int i=size; i>1; i--)
 460                 swap(list, i-1, rnd.nextInt(i));
 461         } else {
 462             Object[] arr = list.toArray();
 463 
 464             // Shuffle array
 465             for (int i=size; i>1; i--)
 466                 swap(arr, i-1, rnd.nextInt(i));
 467 
 468             // Dump array back into list
 469             // instead of using a raw type here, it's possible to capture
 470             // the wildcard but it will require a call to a supplementary
 471             // private method
 472             ListIterator it = list.listIterator();
 473             for (Object e : arr) {
 474                 it.next();
 475                 it.set(e);
 476             }
 477         }
 478     }
 479 
 480     /**
 481      * Swaps the elements at the specified positions in the specified list.
 482      * (If the specified positions are equal, invoking this method leaves