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 org.apache.commons.rng.UniformRandomProvider;
020
021/**
022 * Utilities for shuffling an array in-place.
023 *
024 * <p>Shuffles use the <a
025 * href="https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
026 * Fisher-Yates</a> algorithm.
027 *
028 * @since 1.6
029 */
030public final class ArraySampler {
031    /** Class contains only static methods. */
032    private ArraySampler() {}
033
034    /**
035     * Shuffles the entries of the given array.
036     *
037     * @param rng Source of randomness.
038     * @param array Array whose entries will be shuffled (in-place).
039     * @return a reference to the given array
040     */
041    public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array) {
042        for (int i = array.length; i > 1; i--) {
043            swap(array, i - 1, rng.nextInt(i));
044        }
045        return array;
046    }
047
048    /**
049     * Shuffles the entries of the given array.
050     *
051     * @param rng Source of randomness.
052     * @param array Array whose entries will be shuffled (in-place).
053     * @return a reference to the given array
054     */
055    public static byte[] shuffle(UniformRandomProvider rng, byte[] array) {
056        for (int i = array.length; i > 1; i--) {
057            swap(array, i - 1, rng.nextInt(i));
058        }
059        return array;
060    }
061
062    /**
063     * Shuffles the entries of the given array.
064     *
065     * @param rng Source of randomness.
066     * @param array Array whose entries will be shuffled (in-place).
067     * @return a reference to the given array
068     */
069    public static char[] shuffle(UniformRandomProvider rng, char[] array) {
070        for (int i = array.length; i > 1; i--) {
071            swap(array, i - 1, rng.nextInt(i));
072        }
073        return array;
074    }
075
076    /**
077     * Shuffles the entries of the given array.
078     *
079     * @param rng Source of randomness.
080     * @param array Array whose entries will be shuffled (in-place).
081     * @return a reference to the given array
082     */
083    public static double[] shuffle(UniformRandomProvider rng, double[] array) {
084        for (int i = array.length; i > 1; i--) {
085            swap(array, i - 1, rng.nextInt(i));
086        }
087        return array;
088    }
089
090    /**
091     * Shuffles the entries of the given array.
092     *
093     * @param rng Source of randomness.
094     * @param array Array whose entries will be shuffled (in-place).
095     * @return a reference to the given array
096     */
097    public static float[] shuffle(UniformRandomProvider rng, float[] array) {
098        for (int i = array.length; i > 1; i--) {
099            swap(array, i - 1, rng.nextInt(i));
100        }
101        return array;
102    }
103
104    /**
105     * Shuffles the entries of the given array.
106     *
107     * @param rng Source of randomness.
108     * @param array Array whose entries will be shuffled (in-place).
109     * @return a reference to the given array
110     */
111    public static int[] shuffle(UniformRandomProvider rng, int[] array) {
112        for (int i = array.length; i > 1; i--) {
113            swap(array, i - 1, rng.nextInt(i));
114        }
115        return array;
116    }
117
118    /**
119     * Shuffles the entries of the given array.
120     *
121     * @param rng Source of randomness.
122     * @param array Array whose entries will be shuffled (in-place).
123     * @return a reference to the given array
124     */
125    public static long[] shuffle(UniformRandomProvider rng, long[] array) {
126        for (int i = array.length; i > 1; i--) {
127            swap(array, i - 1, rng.nextInt(i));
128        }
129        return array;
130    }
131
132    /**
133     * Shuffles the entries of the given array.
134     *
135     * @param rng Source of randomness.
136     * @param array Array whose entries will be shuffled (in-place).
137     * @return a reference to the given array
138     */
139    public static short[] shuffle(UniformRandomProvider rng, short[] array) {
140        for (int i = array.length; i > 1; i--) {
141            swap(array, i - 1, rng.nextInt(i));
142        }
143        return array;
144    }
145
146    /**
147     * Shuffles the entries of the given array.
148     *
149     * @param <T> Type of the items.
150     * @param rng Source of randomness.
151     * @param array Array whose entries will be shuffled (in-place).
152     * @return a reference to the given array
153     */
154    public static <T> T[] shuffle(UniformRandomProvider rng, T[] array) {
155        for (int i = array.length; i > 1; i--) {
156            swap(array, i - 1, rng.nextInt(i));
157        }
158        return array;
159    }
160
161    /**
162     * Shuffles the entries of the given array in the range {@code [from, to)}.
163     *
164     * @param rng Source of randomness.
165     * @param array Array whose entries will be shuffled (in-place).
166     * @param from Lower-bound (inclusive) of the sub-range.
167     * @param to Upper-bound (exclusive) of the sub-range.
168     * @return a reference to the given array
169     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
170     */
171    public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array, int from, int to) {
172        final int length = to - checkFromToIndex(from, to, array.length);
173        for (int i = length; i > 1; i--) {
174            swap(array, from + i - 1, from + rng.nextInt(i));
175        }
176        return array;
177    }
178
179    /**
180     * Shuffles the entries of the given array in the range {@code [from, to)}.
181     *
182     * @param rng Source of randomness.
183     * @param array Array whose entries will be shuffled (in-place).
184     * @param from Lower-bound (inclusive) of the sub-range.
185     * @param to Upper-bound (exclusive) of the sub-range.
186     * @return a reference to the given array
187     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
188     */
189    public static byte[] shuffle(UniformRandomProvider rng, byte[] array, int from, int to) {
190        final int length = to - checkFromToIndex(from, to, array.length);
191        for (int i = length; i > 1; i--) {
192            swap(array, from + i - 1, from + rng.nextInt(i));
193        }
194        return array;
195    }
196
197    /**
198     * Shuffles the entries of the given array in the range {@code [from, to)}.
199     *
200     * @param rng Source of randomness.
201     * @param array Array whose entries will be shuffled (in-place).
202     * @param from Lower-bound (inclusive) of the sub-range.
203     * @param to Upper-bound (exclusive) of the sub-range.
204     * @return a reference to the given array
205     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
206     */
207    public static char[] shuffle(UniformRandomProvider rng, char[] array, int from, int to) {
208        final int length = to - checkFromToIndex(from, to, array.length);
209        for (int i = length; i > 1; i--) {
210            swap(array, from + i - 1, from + rng.nextInt(i));
211        }
212        return array;
213    }
214
215    /**
216     * Shuffles the entries of the given array in the range {@code [from, to)}.
217     *
218     * @param rng Source of randomness.
219     * @param array Array whose entries will be shuffled (in-place).
220     * @param from Lower-bound (inclusive) of the sub-range.
221     * @param to Upper-bound (exclusive) of the sub-range.
222     * @return a reference to the given array
223     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
224     */
225    public static double[] shuffle(UniformRandomProvider rng, double[] array, int from, int to) {
226        final int length = to - checkFromToIndex(from, to, array.length);
227        for (int i = length; i > 1; i--) {
228            swap(array, from + i - 1, from + rng.nextInt(i));
229        }
230        return array;
231    }
232
233    /**
234     * Shuffles the entries of the given array in the range {@code [from, to)}.
235     *
236     * @param rng Source of randomness.
237     * @param array Array whose entries will be shuffled (in-place).
238     * @param from Lower-bound (inclusive) of the sub-range.
239     * @param to Upper-bound (exclusive) of the sub-range.
240     * @return a reference to the given array
241     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
242     */
243    public static float[] shuffle(UniformRandomProvider rng, float[] array, int from, int to) {
244        final int length = to - checkFromToIndex(from, to, array.length);
245        for (int i = length; i > 1; i--) {
246            swap(array, from + i - 1, from + rng.nextInt(i));
247        }
248        return array;
249    }
250
251    /**
252     * Shuffles the entries of the given array in the range {@code [from, to)}.
253     *
254     * @param rng Source of randomness.
255     * @param array Array whose entries will be shuffled (in-place).
256     * @param from Lower-bound (inclusive) of the sub-range.
257     * @param to Upper-bound (exclusive) of the sub-range.
258     * @return a reference to the given array
259     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
260     */
261    public static int[] shuffle(UniformRandomProvider rng, int[] array, int from, int to) {
262        final int length = to - checkFromToIndex(from, to, array.length);
263        for (int i = length; i > 1; i--) {
264            swap(array, from + i - 1, from + rng.nextInt(i));
265        }
266        return array;
267    }
268
269    /**
270     * Shuffles the entries of the given array in the range {@code [from, to)}.
271     *
272     * @param rng Source of randomness.
273     * @param array Array whose entries will be shuffled (in-place).
274     * @param from Lower-bound (inclusive) of the sub-range.
275     * @param to Upper-bound (exclusive) of the sub-range.
276     * @return a reference to the given array
277     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
278     */
279    public static long[] shuffle(UniformRandomProvider rng, long[] array, int from, int to) {
280        final int length = to - checkFromToIndex(from, to, array.length);
281        for (int i = length; i > 1; i--) {
282            swap(array, from + i - 1, from + rng.nextInt(i));
283        }
284        return array;
285    }
286
287    /**
288     * Shuffles the entries of the given array in the range {@code [from, to)}.
289     *
290     * @param rng Source of randomness.
291     * @param array Array whose entries will be shuffled (in-place).
292     * @param from Lower-bound (inclusive) of the sub-range.
293     * @param to Upper-bound (exclusive) of the sub-range.
294     * @return a reference to the given array
295     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
296     */
297    public static short[] shuffle(UniformRandomProvider rng, short[] array, int from, int to) {
298        final int length = to - checkFromToIndex(from, to, array.length);
299        for (int i = length; i > 1; i--) {
300            swap(array, from + i - 1, from + rng.nextInt(i));
301        }
302        return array;
303    }
304
305    /**
306     * Shuffles the entries of the given array in the range {@code [from, to)}.
307     *
308     * @param <T> Type of the items.
309     * @param rng Source of randomness.
310     * @param array Array whose entries will be shuffled (in-place).
311     * @param from Lower-bound (inclusive) of the sub-range.
312     * @param to Upper-bound (exclusive) of the sub-range.
313     * @return a reference to the given array
314     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
315     */
316    public static <T> T[] shuffle(UniformRandomProvider rng, T[] array, int from, int to) {
317        final int length = to - checkFromToIndex(from, to, array.length);
318        for (int i = length; i > 1; i--) {
319            swap(array, from + i - 1, from + rng.nextInt(i));
320        }
321        return array;
322    }
323
324    /**
325     * Swaps the two specified elements in the array.
326     *
327     * @param array Array.
328     * @param i First index.
329     * @param j Second index.
330     */
331    private static void swap(boolean[] array, int i, int j) {
332        final boolean tmp = array[i];
333        array[i] = array[j];
334        array[j] = tmp;
335    }
336
337    /**
338     * Swaps the two specified elements in the array.
339     *
340     * @param array Array.
341     * @param i First index.
342     * @param j Second index.
343     */
344    private static void swap(byte[] array, int i, int j) {
345        final byte tmp = array[i];
346        array[i] = array[j];
347        array[j] = tmp;
348    }
349
350    /**
351     * Swaps the two specified elements in the array.
352     *
353     * @param array Array.
354     * @param i First index.
355     * @param j Second index.
356     */
357    private static void swap(char[] array, int i, int j) {
358        final char tmp = array[i];
359        array[i] = array[j];
360        array[j] = tmp;
361    }
362
363    /**
364     * Swaps the two specified elements in the array.
365     *
366     * @param array Array.
367     * @param i First index.
368     * @param j Second index.
369     */
370    private static void swap(double[] array, int i, int j) {
371        final double tmp = array[i];
372        array[i] = array[j];
373        array[j] = tmp;
374    }
375
376    /**
377     * Swaps the two specified elements in the array.
378     *
379     * @param array Array.
380     * @param i First index.
381     * @param j Second index.
382     */
383    private static void swap(float[] array, int i, int j) {
384        final float tmp = array[i];
385        array[i] = array[j];
386        array[j] = tmp;
387    }
388
389    /**
390     * Swaps the two specified elements in the array.
391     *
392     * @param array Array.
393     * @param i First index.
394     * @param j Second index.
395     */
396    private static void swap(int[] array, int i, int j) {
397        final int tmp = array[i];
398        array[i] = array[j];
399        array[j] = tmp;
400    }
401
402    /**
403     * Swaps the two specified elements in the array.
404     *
405     * @param array Array.
406     * @param i First index.
407     * @param j Second index.
408     */
409    private static void swap(long[] array, int i, int j) {
410        final long tmp = array[i];
411        array[i] = array[j];
412        array[j] = tmp;
413    }
414
415    /**
416     * Swaps the two specified elements in the array.
417     *
418     * @param array Array.
419     * @param i First index.
420     * @param j Second index.
421     */
422    private static void swap(short[] array, int i, int j) {
423        final short tmp = array[i];
424        array[i] = array[j];
425        array[j] = tmp;
426    }
427
428    /**
429     * Swaps the two specified elements in the array.
430     *
431     * @param array Array.
432     * @param i First index.
433     * @param j Second index.
434     */
435    private static void swap(Object[] array, int i, int j) {
436        final Object tmp = array[i];
437        array[i] = array[j];
438        array[j] = tmp;
439    }
440
441    /**
442     * Checks if the sub-range from fromIndex (inclusive) to toIndex (exclusive) is
443     * within the bounds of range from 0 (inclusive) to length (exclusive).
444     *
445     * <p>This function provides the functionality of
446     * {@code java.utils.Objects.checkFromToIndex} introduced in JDK 9. The <a
447     * href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Objects.html#checkFromToIndex(int,int,int)">Objects</a>
448     * javadoc has been reproduced for reference.
449     *
450     * <p>The sub-range is defined to be out of bounds if any of the following
451     * inequalities is true:
452     * <ul>
453     * <li>{@code fromIndex < 0}
454     * <li>{@code fromIndex > toIndex}
455     * <li>{@code toIndex > length}
456     * <li>{@code length < 0}, which is implied from the former inequalities
457     * </ul>
458     *
459     * @param fromIndex Lower-bound (inclusive) of the sub-range.
460     * @param toIndex Upper-bound (exclusive) of the sub-range.
461     * @param length Upper-bound (exclusive) of the range
462     * @return fromIndex if the sub-range is within the bounds of the range
463     * @throws IndexOutOfBoundsException if the sub-range is out of bounds
464     */
465    private static int checkFromToIndex(int fromIndex, int toIndex, int length) {
466        // Checks as documented above
467        if (fromIndex < 0 || fromIndex > toIndex || toIndex > length) {
468            throw new IndexOutOfBoundsException(
469                    String.format("Range [%d, %d) out of bounds for length %d", fromIndex, toIndex, length));
470        }
471        return fromIndex;
472    }
473}