1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.rng.sampling;
18
19 import java.util.List;
20 import org.apache.commons.rng.UniformRandomProvider;
21
22 /**
23 * Utilities for shuffling an array in-place.
24 *
25 * <p>Shuffles use the <a
26 * href="https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
27 * Fisher-Yates</a> algorithm.
28 *
29 * <p>Small ranges use batched random integer generation to increase performance.
30 *
31 * <ul>
32 * <li>Nevin Brackett-Rozinsky, Daniel Lemire,
33 * Batched Ranged Random Integer Generation, Software: Practice and Experience (to appear)
34 * <a href="https://arxiv.org/abs/2408.06213">arXiv:2408.06213M</a></li>
35 * </ul>
36 *
37 * @since 1.6
38 */
39 public final class ArraySampler {
40 /** Mask the lower 32-bit of a long. */
41 private static final long MASK_32 = 0xffffffffL;
42 /** 2^32. Used for the bounded random algorithm. This is required as the original
43 * method used (-bound % bound) for (2^L % bound) which only works for unsigned integer
44 * modulus. */
45 private static final long POW_32 = 1L << 32;
46 /** Length threshold to sample 2 integers from a random 32-bit value.
47 * The threshold provided in the Brackett-Rozinsky and Lemire paper
48 * is the power of 2 below 20724. Note that the product 2^15*2^15
49 * is representable using signed integers. */
50 private static final int BATCH_2 = 1 << 15;
51
52 /** Class contains only static methods. */
53 private ArraySampler() {}
54
55 /**
56 * Shuffles the entries of the given array.
57 *
58 * @param rng Source of randomness.
59 * @param array Array whose entries will be shuffled (in-place).
60 * @return a reference to the given array
61 */
62 public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array) {
63 int i = array.length;
64 for (; i > BATCH_2; --i) {
65 swap(array, i - 1, rng.nextInt(i));
66 }
67 // Batches of 2
68 final int[] productBound = {i * (i - 1)};
69 for (; i > 1; i -= 2) {
70 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
71 final int index1 = indices[0];
72 final int index2 = indices[1];
73 swap(array, i - 1, index1);
74 swap(array, i - 2, index2);
75 }
76 return array;
77 }
78
79 /**
80 * Shuffles the entries of the given array.
81 *
82 * @param rng Source of randomness.
83 * @param array Array whose entries will be shuffled (in-place).
84 * @return a reference to the given array
85 */
86 public static byte[] shuffle(UniformRandomProvider rng, byte[] array) {
87 int i = array.length;
88 for (; i > BATCH_2; --i) {
89 swap(array, i - 1, rng.nextInt(i));
90 }
91 // Batches of 2
92 final int[] productBound = {i * (i - 1)};
93 for (; i > 1; i -= 2) {
94 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
95 final int index1 = indices[0];
96 final int index2 = indices[1];
97 swap(array, i - 1, index1);
98 swap(array, i - 2, index2);
99 }
100 return array;
101 }
102
103 /**
104 * Shuffles the entries of the given array.
105 *
106 * @param rng Source of randomness.
107 * @param array Array whose entries will be shuffled (in-place).
108 * @return a reference to the given array
109 */
110 public static char[] shuffle(UniformRandomProvider rng, char[] array) {
111 int i = array.length;
112 for (; i > BATCH_2; --i) {
113 swap(array, i - 1, rng.nextInt(i));
114 }
115 // Batches of 2
116 final int[] productBound = {i * (i - 1)};
117 for (; i > 1; i -= 2) {
118 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
119 final int index1 = indices[0];
120 final int index2 = indices[1];
121 swap(array, i - 1, index1);
122 swap(array, i - 2, index2);
123 }
124 return array;
125 }
126
127 /**
128 * Shuffles the entries of the given array.
129 *
130 * @param rng Source of randomness.
131 * @param array Array whose entries will be shuffled (in-place).
132 * @return a reference to the given array
133 */
134 public static double[] shuffle(UniformRandomProvider rng, double[] array) {
135 int i = array.length;
136 for (; i > BATCH_2; --i) {
137 swap(array, i - 1, rng.nextInt(i));
138 }
139 // Batches of 2
140 final int[] productBound = {i * (i - 1)};
141 for (; i > 1; i -= 2) {
142 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
143 final int index1 = indices[0];
144 final int index2 = indices[1];
145 swap(array, i - 1, index1);
146 swap(array, i - 2, index2);
147 }
148 return array;
149 }
150
151 /**
152 * Shuffles the entries of the given array.
153 *
154 * @param rng Source of randomness.
155 * @param array Array whose entries will be shuffled (in-place).
156 * @return a reference to the given array
157 */
158 public static float[] shuffle(UniformRandomProvider rng, float[] array) {
159 int i = array.length;
160 for (; i > BATCH_2; --i) {
161 swap(array, i - 1, rng.nextInt(i));
162 }
163 // Batches of 2
164 final int[] productBound = {i * (i - 1)};
165 for (; i > 1; i -= 2) {
166 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
167 final int index1 = indices[0];
168 final int index2 = indices[1];
169 swap(array, i - 1, index1);
170 swap(array, i - 2, index2);
171 }
172 return array;
173 }
174
175 /**
176 * Shuffles the entries of the given array.
177 *
178 * @param rng Source of randomness.
179 * @param array Array whose entries will be shuffled (in-place).
180 * @return a reference to the given array
181 */
182 public static int[] shuffle(UniformRandomProvider rng, int[] array) {
183 int i = array.length;
184 for (; i > BATCH_2; --i) {
185 swap(array, i - 1, rng.nextInt(i));
186 }
187 // Batches of 2
188 final int[] productBound = {i * (i - 1)};
189 for (; i > 1; i -= 2) {
190 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
191 final int index1 = indices[0];
192 final int index2 = indices[1];
193 swap(array, i - 1, index1);
194 swap(array, i - 2, index2);
195 }
196 return array;
197 }
198
199 /**
200 * Shuffles the entries of the given array.
201 *
202 * @param rng Source of randomness.
203 * @param array Array whose entries will be shuffled (in-place).
204 * @return a reference to the given array
205 */
206 public static long[] shuffle(UniformRandomProvider rng, long[] array) {
207 int i = array.length;
208 for (; i > BATCH_2; --i) {
209 swap(array, i - 1, rng.nextInt(i));
210 }
211 // Batches of 2
212 final int[] productBound = {i * (i - 1)};
213 for (; i > 1; i -= 2) {
214 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
215 final int index1 = indices[0];
216 final int index2 = indices[1];
217 swap(array, i - 1, index1);
218 swap(array, i - 2, index2);
219 }
220 return array;
221 }
222
223 /**
224 * Shuffles the entries of the given array.
225 *
226 * @param rng Source of randomness.
227 * @param array Array whose entries will be shuffled (in-place).
228 * @return a reference to the given array
229 */
230 public static short[] shuffle(UniformRandomProvider rng, short[] array) {
231 int i = array.length;
232 for (; i > BATCH_2; --i) {
233 swap(array, i - 1, rng.nextInt(i));
234 }
235 // Batches of 2
236 final int[] productBound = {i * (i - 1)};
237 for (; i > 1; i -= 2) {
238 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
239 final int index1 = indices[0];
240 final int index2 = indices[1];
241 swap(array, i - 1, index1);
242 swap(array, i - 2, index2);
243 }
244 return array;
245 }
246
247 /**
248 * Shuffles the entries of the given array.
249 *
250 * @param <T> Type of the items.
251 * @param rng Source of randomness.
252 * @param array Array whose entries will be shuffled (in-place).
253 * @return a reference to the given array
254 */
255 public static <T> T[] shuffle(UniformRandomProvider rng, T[] array) {
256 int i = array.length;
257 for (; i > BATCH_2; --i) {
258 swap(array, i - 1, rng.nextInt(i));
259 }
260 // Batches of 2
261 final int[] productBound = {i * (i - 1)};
262 for (; i > 1; i -= 2) {
263 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
264 final int index1 = indices[0];
265 final int index2 = indices[1];
266 swap(array, i - 1, index1);
267 swap(array, i - 2, index2);
268 }
269 return array;
270 }
271
272 /**
273 * Shuffles the entries of the given list.
274 *
275 * <p>Note: This method is intentionally package-private.
276 *
277 * <p>This method exists to allow the shuffle performed by the {@link ListSampler} to
278 * match the {@link PermutationSampler} and {@link ArraySampler}.
279 *
280 * @param <T> Type of the items.
281 * @param rng Source of randomness.
282 * @param array Array whose entries will be shuffled (in-place).
283 */
284 static <T> void shuffle(UniformRandomProvider rng, List<T> array) {
285 int i = array.size();
286 for (; i > BATCH_2; --i) {
287 swap(array, i - 1, rng.nextInt(i));
288 }
289 // Batches of 2
290 final int[] productBound = {i * (i - 1)};
291 for (; i > 1; i -= 2) {
292 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
293 final int index1 = indices[0];
294 final int index2 = indices[1];
295 swap(array, i - 1, index1);
296 swap(array, i - 2, index2);
297 }
298 }
299
300 /**
301 * Shuffles the entries of the given array in the range {@code [from, to)}.
302 *
303 * @param rng Source of randomness.
304 * @param array Array whose entries will be shuffled (in-place).
305 * @param from Lower-bound (inclusive) of the sub-range.
306 * @param to Upper-bound (exclusive) of the sub-range.
307 * @return a reference to the given array
308 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
309 */
310 public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array, int from, int to) {
311 int i = to - checkFromToIndex(from, to, array.length);
312 for (; i > BATCH_2; --i) {
313 swap(array, from + i - 1, from + rng.nextInt(i));
314 }
315 // Batches of 2
316 final int[] productBound = {i * (i - 1)};
317 for (; i > 1; i -= 2) {
318 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
319 final int index1 = indices[0];
320 final int index2 = indices[1];
321 swap(array, from + i - 1, from + index1);
322 swap(array, from + i - 2, from + index2);
323 }
324 return array;
325 }
326
327 /**
328 * Shuffles the entries of the given array in the range {@code [from, to)}.
329 *
330 * @param rng Source of randomness.
331 * @param array Array whose entries will be shuffled (in-place).
332 * @param from Lower-bound (inclusive) of the sub-range.
333 * @param to Upper-bound (exclusive) of the sub-range.
334 * @return a reference to the given array
335 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
336 */
337 public static byte[] shuffle(UniformRandomProvider rng, byte[] array, int from, int to) {
338 int i = to - checkFromToIndex(from, to, array.length);
339 for (; i > BATCH_2; --i) {
340 swap(array, from + i - 1, from + rng.nextInt(i));
341 }
342 // Batches of 2
343 final int[] productBound = {i * (i - 1)};
344 for (; i > 1; i -= 2) {
345 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
346 final int index1 = indices[0];
347 final int index2 = indices[1];
348 swap(array, from + i - 1, from + index1);
349 swap(array, from + i - 2, from + index2);
350 }
351 return array;
352 }
353
354 /**
355 * Shuffles the entries of the given array in the range {@code [from, to)}.
356 *
357 * @param rng Source of randomness.
358 * @param array Array whose entries will be shuffled (in-place).
359 * @param from Lower-bound (inclusive) of the sub-range.
360 * @param to Upper-bound (exclusive) of the sub-range.
361 * @return a reference to the given array
362 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
363 */
364 public static char[] shuffle(UniformRandomProvider rng, char[] array, int from, int to) {
365 int i = to - checkFromToIndex(from, to, array.length);
366 for (; i > BATCH_2; --i) {
367 swap(array, from + i - 1, from + rng.nextInt(i));
368 }
369 // Batches of 2
370 final int[] productBound = {i * (i - 1)};
371 for (; i > 1; i -= 2) {
372 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
373 final int index1 = indices[0];
374 final int index2 = indices[1];
375 swap(array, from + i - 1, from + index1);
376 swap(array, from + i - 2, from + index2);
377 }
378 return array;
379 }
380
381 /**
382 * Shuffles the entries of the given array in the range {@code [from, to)}.
383 *
384 * @param rng Source of randomness.
385 * @param array Array whose entries will be shuffled (in-place).
386 * @param from Lower-bound (inclusive) of the sub-range.
387 * @param to Upper-bound (exclusive) of the sub-range.
388 * @return a reference to the given array
389 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
390 */
391 public static double[] shuffle(UniformRandomProvider rng, double[] array, int from, int to) {
392 int i = to - checkFromToIndex(from, to, array.length);
393 for (; i > BATCH_2; --i) {
394 swap(array, from + i - 1, from + rng.nextInt(i));
395 }
396 // Batches of 2
397 final int[] productBound = {i * (i - 1)};
398 for (; i > 1; i -= 2) {
399 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
400 final int index1 = indices[0];
401 final int index2 = indices[1];
402 swap(array, from + i - 1, from + index1);
403 swap(array, from + i - 2, from + index2);
404 }
405 return array;
406 }
407
408 /**
409 * Shuffles the entries of the given array in the range {@code [from, to)}.
410 *
411 * @param rng Source of randomness.
412 * @param array Array whose entries will be shuffled (in-place).
413 * @param from Lower-bound (inclusive) of the sub-range.
414 * @param to Upper-bound (exclusive) of the sub-range.
415 * @return a reference to the given array
416 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
417 */
418 public static float[] shuffle(UniformRandomProvider rng, float[] array, int from, int to) {
419 int i = to - checkFromToIndex(from, to, array.length);
420 for (; i > BATCH_2; --i) {
421 swap(array, from + i - 1, from + rng.nextInt(i));
422 }
423 // Batches of 2
424 final int[] productBound = {i * (i - 1)};
425 for (; i > 1; i -= 2) {
426 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
427 final int index1 = indices[0];
428 final int index2 = indices[1];
429 swap(array, from + i - 1, from + index1);
430 swap(array, from + i - 2, from + index2);
431 }
432 return array;
433 }
434
435 /**
436 * Shuffles the entries of the given array in the range {@code [from, to)}.
437 *
438 * @param rng Source of randomness.
439 * @param array Array whose entries will be shuffled (in-place).
440 * @param from Lower-bound (inclusive) of the sub-range.
441 * @param to Upper-bound (exclusive) of the sub-range.
442 * @return a reference to the given array
443 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
444 */
445 public static int[] shuffle(UniformRandomProvider rng, int[] array, int from, int to) {
446 int i = to - checkFromToIndex(from, to, array.length);
447 for (; i > BATCH_2; --i) {
448 swap(array, from + i - 1, from + rng.nextInt(i));
449 }
450 // Batches of 2
451 final int[] productBound = {i * (i - 1)};
452 for (; i > 1; i -= 2) {
453 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
454 final int index1 = indices[0];
455 final int index2 = indices[1];
456 swap(array, from + i - 1, from + index1);
457 swap(array, from + i - 2, from + index2);
458 }
459 return array;
460 }
461
462 /**
463 * Shuffles the entries of the given array in the range {@code [from, to)}.
464 *
465 * @param rng Source of randomness.
466 * @param array Array whose entries will be shuffled (in-place).
467 * @param from Lower-bound (inclusive) of the sub-range.
468 * @param to Upper-bound (exclusive) of the sub-range.
469 * @return a reference to the given array
470 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
471 */
472 public static long[] shuffle(UniformRandomProvider rng, long[] array, int from, int to) {
473 int i = to - checkFromToIndex(from, to, array.length);
474 for (; i > BATCH_2; --i) {
475 swap(array, from + i - 1, from + rng.nextInt(i));
476 }
477 // Batches of 2
478 final int[] productBound = {i * (i - 1)};
479 for (; i > 1; i -= 2) {
480 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
481 final int index1 = indices[0];
482 final int index2 = indices[1];
483 swap(array, from + i - 1, from + index1);
484 swap(array, from + i - 2, from + index2);
485 }
486 return array;
487 }
488
489 /**
490 * Shuffles the entries of the given array in the range {@code [from, to)}.
491 *
492 * @param rng Source of randomness.
493 * @param array Array whose entries will be shuffled (in-place).
494 * @param from Lower-bound (inclusive) of the sub-range.
495 * @param to Upper-bound (exclusive) of the sub-range.
496 * @return a reference to the given array
497 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
498 */
499 public static short[] shuffle(UniformRandomProvider rng, short[] array, int from, int to) {
500 int i = to - checkFromToIndex(from, to, array.length);
501 for (; i > BATCH_2; --i) {
502 swap(array, from + i - 1, from + rng.nextInt(i));
503 }
504 // Batches of 2
505 final int[] productBound = {i * (i - 1)};
506 for (; i > 1; i -= 2) {
507 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
508 final int index1 = indices[0];
509 final int index2 = indices[1];
510 swap(array, from + i - 1, from + index1);
511 swap(array, from + i - 2, from + index2);
512 }
513 return array;
514 }
515
516 /**
517 * Shuffles the entries of the given array in the range {@code [from, to)}.
518 *
519 * @param <T> Type of the items.
520 * @param rng Source of randomness.
521 * @param array Array whose entries will be shuffled (in-place).
522 * @param from Lower-bound (inclusive) of the sub-range.
523 * @param to Upper-bound (exclusive) of the sub-range.
524 * @return a reference to the given array
525 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
526 */
527 public static <T> T[] shuffle(UniformRandomProvider rng, T[] array, int from, int to) {
528 int i = to - checkFromToIndex(from, to, array.length);
529 for (; i > BATCH_2; --i) {
530 swap(array, from + i - 1, from + rng.nextInt(i));
531 }
532 // Batches of 2
533 final int[] productBound = {i * (i - 1)};
534 for (; i > 1; i -= 2) {
535 final int[] indices = randomBounded2(i, i - 1, productBound, rng);
536 final int index1 = indices[0];
537 final int index2 = indices[1];
538 swap(array, from + i - 1, from + index1);
539 swap(array, from + i - 2, from + index2);
540 }
541 return array;
542 }
543
544 /**
545 * Swaps the two specified elements in the array.
546 *
547 * @param array Array.
548 * @param i First index.
549 * @param j Second index.
550 */
551 private static void swap(boolean[] array, int i, int j) {
552 final boolean tmp = array[i];
553 array[i] = array[j];
554 array[j] = tmp;
555 }
556
557 /**
558 * Swaps the two specified elements in the array.
559 *
560 * @param array Array.
561 * @param i First index.
562 * @param j Second index.
563 */
564 private static void swap(byte[] array, int i, int j) {
565 final byte tmp = array[i];
566 array[i] = array[j];
567 array[j] = tmp;
568 }
569
570 /**
571 * Swaps the two specified elements in the array.
572 *
573 * @param array Array.
574 * @param i First index.
575 * @param j Second index.
576 */
577 private static void swap(char[] array, int i, int j) {
578 final char tmp = array[i];
579 array[i] = array[j];
580 array[j] = tmp;
581 }
582
583 /**
584 * Swaps the two specified elements in the array.
585 *
586 * @param array Array.
587 * @param i First index.
588 * @param j Second index.
589 */
590 private static void swap(double[] array, int i, int j) {
591 final double tmp = array[i];
592 array[i] = array[j];
593 array[j] = tmp;
594 }
595
596 /**
597 * Swaps the two specified elements in the array.
598 *
599 * @param array Array.
600 * @param i First index.
601 * @param j Second index.
602 */
603 private static void swap(float[] array, int i, int j) {
604 final float tmp = array[i];
605 array[i] = array[j];
606 array[j] = tmp;
607 }
608
609 /**
610 * Swaps the two specified elements in the array.
611 *
612 * @param array Array.
613 * @param i First index.
614 * @param j Second index.
615 */
616 private static void swap(int[] array, int i, int j) {
617 final int tmp = array[i];
618 array[i] = array[j];
619 array[j] = tmp;
620 }
621
622 /**
623 * Swaps the two specified elements in the array.
624 *
625 * @param array Array.
626 * @param i First index.
627 * @param j Second index.
628 */
629 private static void swap(long[] array, int i, int j) {
630 final long tmp = array[i];
631 array[i] = array[j];
632 array[j] = tmp;
633 }
634
635 /**
636 * Swaps the two specified elements in the array.
637 *
638 * @param array Array.
639 * @param i First index.
640 * @param j Second index.
641 */
642 private static void swap(short[] array, int i, int j) {
643 final short tmp = array[i];
644 array[i] = array[j];
645 array[j] = tmp;
646 }
647
648 /**
649 * Swaps the two specified elements in the array.
650 *
651 * @param array Array.
652 * @param i First index.
653 * @param j Second index.
654 */
655 private static void swap(Object[] array, int i, int j) {
656 final Object tmp = array[i];
657 array[i] = array[j];
658 array[j] = tmp;
659 }
660
661 /**
662 * Swaps the two specified elements in the list.
663 *
664 * @param <T> Type of the list items.
665 * @param list List.
666 * @param i First index.
667 * @param j Second index.
668 */
669 private static <T> void swap(List<T> list, int i, int j) {
670 final T tmp = list.get(i);
671 list.set(i, list.get(j));
672 list.set(j, tmp);
673 }
674
675 /**
676 * Return two random values in {@code [0, range1)} and {@code [0, range2)}. The
677 * product bound is used for the reject algorithm. See Brackett-Rozinsky and Lemire.
678 *
679 * <p>The product bound can be any positive integer {@code >= range1*range2}.
680 * It may be updated to become {@code range1*range2}.
681 *
682 * @param range1 Range 1.
683 * @param range2 Range 2.
684 * @param productBound Product bound.
685 * @param rng Source of randomness.
686 * @return [index1, index2]
687 */
688 static int[] randomBounded2(int range1, int range2, int[] productBound, UniformRandomProvider rng) {
689 long m = (rng.nextInt() & MASK_32) * range1;
690 // index1 and index2 are the top 32-bits of the long
691 long index1 = m;
692 // Leftover bits * range2
693 m = (m & MASK_32) * range2;
694 long index2 = m;
695 // Leftover bits must be unsigned
696 long l = m & MASK_32;
697 if (l < productBound[0]) {
698 final int bound = range1 * range2;
699 productBound[0] = bound;
700 if (l < bound) {
701 // 2^32 % bound
702 final long t = POW_32 % bound;
703 while (l < t) {
704 m = (rng.nextInt() & MASK_32) * range1;
705 index1 = m;
706 m = (m & MASK_32) * range2;
707 index2 = m;
708 l = m & MASK_32;
709 }
710 }
711 }
712 // Convert to [0, range1), [0, range2)
713 return new int[] {(int) (index1 >> 32), (int) (index2 >> 32)};
714 }
715
716 /**
717 * Checks if the sub-range from fromIndex (inclusive) to toIndex (exclusive) is
718 * within the bounds of range from 0 (inclusive) to length (exclusive).
719 *
720 * <p>This function provides the functionality of
721 * {@code java.utils.Objects.checkFromToIndex} introduced in JDK 9. The <a
722 * href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Objects.html#checkFromToIndex(int,int,int)">Objects</a>
723 * javadoc has been reproduced for reference.
724 *
725 * <p>The sub-range is defined to be out of bounds if any of the following
726 * inequalities is true:
727 * <ul>
728 * <li>{@code fromIndex < 0}</li>
729 * <li>{@code fromIndex > toIndex}</li>
730 * <li>{@code toIndex > length}</li>
731 * <li>{@code length < 0}, which is implied from the former inequalities</li>
732 * </ul>
733 *
734 * @param fromIndex Lower-bound (inclusive) of the sub-range.
735 * @param toIndex Upper-bound (exclusive) of the sub-range.
736 * @param length Upper-bound (exclusive) of the range
737 * @return fromIndex if the sub-range is within the bounds of the range
738 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
739 */
740 private static int checkFromToIndex(int fromIndex, int toIndex, int length) {
741 // Checks as documented above
742 if (fromIndex < 0 || fromIndex > toIndex || toIndex > length) {
743 throw new IndexOutOfBoundsException(
744 String.format("Range [%d, %d) out of bounds for length %d", fromIndex, toIndex, length));
745 }
746 return fromIndex;
747 }
748 }