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 org.apache.commons.rng.UniformRandomProvider;
20
21 /**
22 * Utilities for shuffling an array in-place.
23 *
24 * <p>Shuffles use the <a
25 * href="https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
26 * Fisher-Yates</a> algorithm.
27 *
28 * @since 1.6
29 */
30 public final class ArraySampler {
31 /** Class contains only static methods. */
32 private ArraySampler() {}
33
34 /**
35 * Shuffles the entries of the given array.
36 *
37 * @param rng Source of randomness.
38 * @param array Array whose entries will be shuffled (in-place).
39 * @return a reference to the given array
40 */
41 public static boolean[] shuffle(UniformRandomProvider rng, boolean[] array) {
42 for (int i = array.length; i > 1; i--) {
43 swap(array, i - 1, rng.nextInt(i));
44 }
45 return array;
46 }
47
48 /**
49 * Shuffles the entries of the given array.
50 *
51 * @param rng Source of randomness.
52 * @param array Array whose entries will be shuffled (in-place).
53 * @return a reference to the given array
54 */
55 public static byte[] shuffle(UniformRandomProvider rng, byte[] array) {
56 for (int i = array.length; i > 1; i--) {
57 swap(array, i - 1, rng.nextInt(i));
58 }
59 return array;
60 }
61
62 /**
63 * Shuffles the entries of the given array.
64 *
65 * @param rng Source of randomness.
66 * @param array Array whose entries will be shuffled (in-place).
67 * @return a reference to the given array
68 */
69 public static char[] shuffle(UniformRandomProvider rng, char[] array) {
70 for (int i = array.length; i > 1; i--) {
71 swap(array, i - 1, rng.nextInt(i));
72 }
73 return array;
74 }
75
76 /**
77 * Shuffles the entries of the given array.
78 *
79 * @param rng Source of randomness.
80 * @param array Array whose entries will be shuffled (in-place).
81 * @return a reference to the given array
82 */
83 public static double[] shuffle(UniformRandomProvider rng, double[] array) {
84 for (int i = array.length; i > 1; i--) {
85 swap(array, i - 1, rng.nextInt(i));
86 }
87 return array;
88 }
89
90 /**
91 * Shuffles the entries of the given array.
92 *
93 * @param rng Source of randomness.
94 * @param array Array whose entries will be shuffled (in-place).
95 * @return a reference to the given array
96 */
97 public static float[] shuffle(UniformRandomProvider rng, float[] array) {
98 for (int i = array.length; i > 1; i--) {
99 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 }