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
5082 .newInstance(a.getClass().getComponentType(), n);
5083 if (element != null)
5084 Arrays.fill(a, 0, n, element);
5085 } else {
5086 Arrays.fill(a, 0, n, element);
5087 if (a.length > n)
5088 a[n] = null;
5089 }
5090 return a;
5091 }
5092
5093 public List<E> subList(int fromIndex, int toIndex) {
5094 if (fromIndex < 0)
5095 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
5096 if (toIndex > n)
5097 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
5098 if (fromIndex > toIndex)
5099 throw new IllegalArgumentException("fromIndex(" + fromIndex +
5100 ") > toIndex(" + toIndex + ")");
5101 return new CopiesList<>(toIndex - fromIndex, element);
5102 }
5103
5104 // Override default methods in Collection
5105 @Override
5106 public Stream<E> stream() {
5107 return IntStream.range(0, n).mapToObj(i -> element);
5108 }
5109
5110 @Override
5111 public Stream<E> parallelStream() {
5112 return IntStream.range(0, n).parallel().mapToObj(i -> element);
5113 }
5114
5115 @Override
5116 public Spliterator<E> spliterator() {
5117 return stream().spliterator();
5118 }
5119 }
5120
5121 /**
|
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
5082 .newInstance(a.getClass().getComponentType(), n);
5083 if (element != null)
5084 Arrays.fill(a, 0, n, element);
5085 } else {
5086 Arrays.fill(a, 0, n, element);
5087 if (a.length > n)
5088 a[n] = null;
5089 }
5090 return a;
5091 }
5092
5093 public List<E> subList(int fromIndex, int toIndex) {
5094 if (fromIndex < 0)
5095 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
5096 if (toIndex > n)
5097 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
5098 if (fromIndex > toIndex)
5099 throw new IllegalArgumentException("fromIndex(" + fromIndex +
5100 ") > toIndex(" + toIndex + ")");
5101 return new CopiesList<>(toIndex - fromIndex, element);
5102 }
5103
5104 @Override
5105 public int hashCode() {
5106 if (n == 0) return 1;
5107 // hashCode of n repeating elements is 31^n + elementHash * Sum(31^k, k = 0..n-1)
5108 // this implementation completes in O(log(n)) steps taking advantage of
5109 // 31^(2*n) = (31^n)^2 and Sum(31^k, k = 0..(2*n-1)) = Sum(31^k, k = 0..n-1) * (31^n + 1)
5110 int pow = 31;
5111 int sum = 1;
5112 for (int i = Integer.numberOfLeadingZeros(n) + 1; i < Integer.SIZE; i++) {
5113 sum *= pow + 1;
5114 pow *= pow;
5115 if ((n << i) < 0) {
5116 pow *= 31;
5117 sum = sum * 31 + 1;
5118 }
5119 }
5120 return pow + sum * (element == null ? 0 : element.hashCode());
5121 }
5122
5123 // Override default methods in Collection
5124 @Override
5125 public Stream<E> stream() {
5126 return IntStream.range(0, n).mapToObj(i -> element);
5127 }
5128
5129 @Override
5130 public Stream<E> parallelStream() {
5131 return IntStream.range(0, n).parallel().mapToObj(i -> element);
5132 }
5133
5134 @Override
5135 public Spliterator<E> spliterator() {
5136 return stream().spliterator();
5137 }
5138 }
5139
5140 /**
|