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}