001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.rng.sampling;
018
019import java.util.List;
020import org.apache.commons.rng.UniformRandomProvider;
021
022/**
023 * Utilities for shuffling an array in-place.
024 *
025 * <p>Shuffles use the <a
026 * href="https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
027 * Fisher-Yates</a> algorithm.
028 *
029 * <p>Small ranges use batched random integer generation to increase performance.
030 *
031 * <ul>
032 * <li>Nevin Brackett-Rozinsky, Daniel Lemire,
033 * Batched Ranged Random Integer Generation, Software: Practice and Experience (to appear)
034 * <a href="https://arxiv.org/abs/2408.06213">arXiv:2408.06213M</a></li>
035 * </ul>
036 *
037 * @since 1.6
038 */
039public final class ArraySampler {
040    /** Mask the lower 32-bit of a long. */
041    private static final long MASK_32 = 0xffffffffL;
042    /** 2^32. Used for the bounded random algorithm. This is required as the original
043     * method used (-bound % bound) for (2^L % bound) which only works for unsigned integer
044     * modulus. */
045    private static final long POW_32 = 1L << 32;
046    /** Length threshold to sample 2 integers from a random 32-bit value.
047     * The threshold provided in the Brackett-Rozinsky and Lemire paper
048     * is the power of 2 below 20724. Note that the product 2^15*2^15
049     * is representable using signed integers. */
050    private static final int BATCH_2 = 1 << 15;
051
052    /** Class contains only static methods. */
053    private ArraySampler() {}
054
055    /**
056     * Shuffles the entries of the given array.
057     *
058     * @param rng Source of randomness.
059     * @param array Array whose entries will be shuffled (in-place).
060     * @return a reference to the given array
061     */
062    public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array) {
063        int i = array.length;
064        for (; i > BATCH_2; --i) {
065            swap(array, i - 1, rng.nextInt(i));
066        }
067        // Batches of 2
068        final int[] productBound = {i * (i - 1)};
069        for (; i > 1; i -= 2) {
070            final int[] indices = randomBounded2(i, i - 1, productBound, rng);
071            final int index1 = indices[0];
072            final int index2 = indices[1];
073            swap(array, i - 1, index1);
074            swap(array, i - 2, index2);
075        }
076        return array;
077    }
078
079    /**
080     * Shuffles the entries of the given array.
081     *
082     * @param rng Source of randomness.
083     * @param array Array whose entries will be shuffled (in-place).
084     * @return a reference to the given array
085     */
086    public static byte[] shuffle(UniformRandomProvider rng, byte[] array) {
087        int i = array.length;
088        for (; i > BATCH_2; --i) {
089            swap(array, i - 1, rng.nextInt(i));
090        }
091        // Batches of 2
092        final int[] productBound = {i * (i - 1)};
093        for (; i > 1; i -= 2) {
094            final int[] indices = randomBounded2(i, i - 1, productBound, rng);
095            final int index1 = indices[0];
096            final int index2 = indices[1];
097            swap(array, i - 1, index1);
098            swap(array, i - 2, index2);
099        }
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}