001package squidpony.squidmath; 002 003import squidpony.ArrayTools; 004 005import java.io.Serializable; 006import java.util.*; 007 008import static squidpony.squidmath.NumberTools.intBitsToFloat; 009 010/** 011 * A wrapper class for working with random number generators in a more friendly way. 012 * Implements {@link IRNG}, which covers most of the API surface, but RNG implements 013 * a decent amount of additional methods. You should consider if your code needs 014 * these additional methods, and if not you should use IRNG as the type for when you 015 * need some random number generator. 016 * <p> 017 * Includes methods for getting values between two numbers and for getting 018 * random elements from a collection or array. There are methods to shuffle 019 * a collection and to get a random ordering that can be applied as one shuffle 020 * across multiple collections, such as via {@link OrderedMap#reorder(int...)}, 021 * {@link ArrayTools#reorder(ArrayList, int...)}, and so on. You can construct 022 * an RNG with all sorts of RandomnessSource implementations, and choosing them 023 * is usually not a big concern because the default works very well. If you target 024 * GWT, then it is suggested that you use {@link GWTRNG} instead of RNG; both 025 * implement {@link IRNG}, which is enough for most usage across SquidLib, but 026 * GWTRNG is optimized heavily for better performance on GWT, even returning long 027 * values faster than implementations that natively do their math on longs. It has 028 * worse performance on 64-bit PCs and mobile devices, but should also have better 029 * performance on 32-bit PCs and mobile devices. 030 * <br> 031 * But if you do want advice on what RandomnessSource to use... {@link DiverRNG} 032 * is the default, and is the fastest generator that passes most tests and can 033 * produce all 64-bit values, and though relative to many of the others it has a 034 * significantly shorter period (the amount of random numbers it will go through 035 * before repeating the sequence), this almost never matters in games, and is 036 * primarily relevant for massively-parallel scientific programs. DiverRNG has a 037 * period of {@code pow(2, 64)} as opposed to {@link XoRoRNG}'s 038 * {@code pow(2, 128) - 1}, or {@link LongPeriodRNG}'s {@code pow(2, 1024) - 1}. 039 * {@link LightRNG} is a solid choice and a former default RandomnessSource; 040 * additional features of LightRNG are exposed in {@link MoonwalkRNG} and using 041 * MoonwalkRNG is recommended if you need unusual features like skipping backwards 042 * in a random number sequence, taking a result of a nextLong() call and reversing 043 * it to get the state that produced it, or calculating the distance in number of 044 * nextLong() calls between two results of nextLong() calls. LightRNG is a 045 * StatefulRandomness, which lets it be used in {@link StatefulRNG}, and so is 046 * DiverRNG, but LightRNG is also a {@link SkippingRandomness}, which means you can 047 * leap forward or backwards in its sequence very efficiently (DiverRNG is not a 048 * SkippingRandomness). {@link ThrustAltRNG} provides similar qualities to LightRNG, 049 * and is one of the fastest generators here, but can't produce all possible 64-bit 050 * values (possibly some 32-bit values as well); it was the default at one point so 051 * you may want to keep compatibility with some versions by specifying ThrustAltRNG. 052 * The defaults have changed in the past as issues are found in various generators; 053 * LightRNG has high quality all-around but is slower than the other defaults, 054 * ThrustAltRNG can't produce all results, LinnormRNG passed tests in an earlier 055 * version of the PractRand test suite but now fails in the current version, and now 056 * the default is DiverRNG, which shares the known issue of LightRNG and LinnormRNG 057 * that it can't produce the same result twice from {@link #nextLong()} until the 058 * generator exhausts its period and repeats its output from the beginning. 059 * For most cases, you should decide between DiverRNG, ThrustAltRNG, LightRNG, 060 * LongPeriodRNG, MiniMover64RNG, and XoshiroStarPhi32RNG based on your priorities. 061 * Some tasks are better solved by using a different class, usually {@link GWTRNG}, 062 * which can always be serialized on GWT to save its state easily and is usually the 063 * fastest substitute for RNG on that platform. DiverRNG is the best if you want high 064 * speed, very good quality of randomness, and expect to generate a reasonable quantity 065 * of numbers for a game (less than 18446744073709551616 numbers) without any single 066 * results being impossible. LightRNG is the second-best at the above criteria, but is 067 * the best option if you need an RNG that can skip backwards or jump forwards without 068 * incurring speed penalties. LongPeriodRNG is best if you for some reason need a massive 069 * amount of random numbers (as in, ten quintillion would be far too little) or want to 070 * split up such a large generator into unrelated subsequences. XoshiroStarPhi32RNG is 071 * best if GWT is a possible target but you either need to generate more than 072 * 18446744073709551616 numbers (but less than 340282366920938463463374607431768211455 073 * numbers) or you need to ensure that each 128-bit chunk of output is unique; if GWT is 074 * a target but those specific needs don't matter, use GWTRNG. ThrustAltRNG and 075 * MiniMover64RNG are both faster than DiverRNG usually (MiniMover64RNG is the fastest), 076 * but because they are unable to generate some outputs, that may make them a poor choice 077 * for some usage (ThrustAltRNG also has some bias toward specific numbers and produces 078 * them more frequently, but not frequently enough to make it fail statistical tests, and 079 * ThrustAltRNG can skip around in its output sequence like LightRNG). 080 * <br> 081 * There are many more RandomnessSource implementations! You might want significantly less 082 * predictable random results, which {@link IsaacRNG} can provide, along with a 083 * large period. The quality of {@link PermutedRNG} is also good, usually, and it 084 * has a sound basis in PCG-Random, an involved library with many variants on its 085 * RNGs. 086 * <br> 087 * There may be reasons why you would want a random number generator that uses 32-bit 088 * math instead of the more common 64-bit math, but using a 32-bit int on desktop and 089 * Android won't act the same as that same 32-bit int on GWT. Since GWT is stuck with 090 * JavaScript's implementation of ints with doubles, overflow (which is needed for an 091 * RNG) doesn't work with ints as expected, but does with GWT's implementation of longs. 092 * If targeting GWT, you should probably consider {@link GWTRNG} or {@link SilkRNG}, 093 * which would be used in place of this class and have a similar API. You can instead 094 * choose a RandomnessSource that is efficient on GWT; {@link Lathe32RNG} is 095 * significantly faster at producing int values on GWT than any long-based generator, 096 * and will produce the same results on GWT as on desktop or Android (not all 32-bit 097 * generators do this). {@link Starfish32RNG} goes one step further than Lathe32RNG at 098 * an even distribution, and has better quality, but is slightly slower; it is also used 099 * internally by GWTRNG. While Lathe32RNG can produce all ints over the course of its 100 * period, it will produce some pairs of ints, or longs, more often than others and will 101 * never produce some longs. Starfish32RNG will produce all longs but one. 102 * {@link Oriole32RNG} and {@link XoshiroStarPhi32RNG} are also GWT-safe, but other 103 * generators that were thought to be GWT-friendly are not. {@link PintRNG} is a 104 * GWT-unsafe generators with other uses, but should not be used on GWT. All other 105 * RandomnessSources use longs, and so will be slower than the recommended Starfish32RNG 106 * or Lathe32RNG on GWT, but probably are much faster on 64-bit JREs. 107 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 108 * @author Tommy Ettinger 109 * @author smelC 110 */ 111public class RNG implements Serializable, IRNG { 112 113 protected RandomnessSource random; 114 protected Random ran; 115 116 private static final long serialVersionUID = 2352426757973945105L; 117 118 119 /** 120 * Default constructor; uses {@link DiverRNG}, which is of high quality, but low period (which rarely matters 121 * for games), and has excellent speed, tiny state size, and natively generates 64-bit numbers. 122 * <br> 123 * Previous versions of SquidLib used different implementations, including {@link LightRNG}, {@link ThrustAltRNG}, 124 * {@link LinnormRNG}, and {@link MersenneTwister}. You can still use one of these by instantiating one of those 125 * classes and passing it to {@link #RNG(RandomnessSource)}, which may be the best way to ensure the same results 126 * across versions. 127 */ 128 public RNG() { 129 this(new DiverRNG()); 130 } 131 132 /** 133 * Default constructor; uses {@link DiverRNG}, which is of high quality, but low period (which rarely matters 134 * for games), and has excellent speed, tiny state size, and natively generates 64-bit numbers. The seed can be 135 * any long, including 0. 136 * @param seed any long 137 */ 138 public RNG(long seed) { 139 this(new DiverRNG(seed)); 140 } 141 142 /** 143 * String-seeded constructor; uses a platform-independent hash of the String (it does not use String.hashCode, 144 * instead using {@link CrossHash#hash64(CharSequence)}) as a seed for {@link DiverRNG}, which is of high quality, 145 * but low period (which rarely matters for games), and has excellent speed, tiny state size, and natively generates 146 * 64-bit numbers. 147 */ 148 public RNG(CharSequence seedString) { 149 this(new DiverRNG(CrossHash.hash64(seedString))); 150 } 151 152 /** 153 * Uses the provided source of randomness for all calculations. This constructor should be used if an alternate 154 * RandomnessSource other than DiverRNG is desirable, such as to keep compatibility with earlier SquidLib 155 * versions that defaulted to MersenneTwister, LightRNG, ThrustAltRNG, or LinnormRNG. 156 * <br> 157 * If the parameter is null, this is equivalent to using {@link #RNG()} as the constructor. 158 * @param random the source of pseudo-randomness, such as a LightRNG or LongPeriodRNG object 159 */ 160 public RNG(RandomnessSource random) { 161 this.random = (random == null) ? new DiverRNG() : random; 162 } 163 164 /** 165 * A subclass of java.util.Random that uses a RandomnessSource supplied by the user instead of the default. 166 * 167 * @author Tommy Ettinger 168 */ 169 public static class CustomRandom extends Random { 170 171 private static final long serialVersionUID = 8211985716129281944L; 172 private final RandomnessSource randomnessSource; 173 174 /** 175 * Creates a new random number generator. This constructor uses 176 * a DiverRNG with a random seed. 177 */ 178 public CustomRandom() { 179 randomnessSource = new DiverRNG(); 180 } 181 182 /** 183 * Creates a new random number generator. This constructor uses 184 * the seed of the given RandomnessSource if it has been seeded. 185 * 186 * @param randomnessSource a way to get random bits, supplied by RNG 187 */ 188 public CustomRandom(RandomnessSource randomnessSource) { 189 this.randomnessSource = randomnessSource; 190 } 191 192 /** 193 * Generates the next pseudorandom number. Subclasses should 194 * override this, as this is used by all other methods. 195 * <p> 196 * <p>The general contract of {@code next} is that it returns an 197 * {@code int} value and if the argument {@code bits} is between 198 * {@code 1} and {@code 32} (inclusive), then that many low-order 199 * bits of the returned value will be (approximately) independently 200 * chosen bit values, each of which is (approximately) equally 201 * likely to be {@code 0} or {@code 1}. The method {@code next} is 202 * implemented by class {@code Random} by atomically updating the seed to 203 * <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre> 204 * and returning 205 * <pre>{@code (int)(seed >>> (48 - bits))}.</pre> 206 * 207 * This is a linear congruential pseudorandom number generator, as 208 * defined by D. H. Lehmer and described by Donald E. Knuth in 209 * <i>The Art of Computer Programming,</i> Volume 3: 210 * <i>Seminumerical Algorithms</i>, section 3.2.1. 211 * 212 * @param bits random bits 213 * @return the next pseudorandom value from this random number 214 * generator's sequence 215 * @since 1.1 216 */ 217 @Override 218 protected int next(int bits) { 219 return randomnessSource.next(bits); 220 } 221 222 /** 223 * Returns the next pseudorandom, uniformly distributed {@code long} 224 * value from this random number generator's sequence. The general 225 * contract of {@code nextLong} is that one {@code long} value is 226 * pseudorandomly generated and returned. 227 * 228 * @return the next pseudorandom, uniformly distributed {@code long} 229 * value from this random number generator's sequence 230 */ 231 @Override 232 public long nextLong() { 233 return randomnessSource.nextLong(); 234 } 235 } 236 237 /** 238 * @return a Random instance that can be used for legacy compatibility 239 */ 240 public Random asRandom() { 241 if (ran == null) { 242 ran = new CustomRandom(random); 243 } 244 return ran; 245 } 246 247 /** 248 * Returns a value from an even distribution from min (inclusive) to max 249 * (exclusive). 250 * 251 * @param min the minimum bound on the return value (inclusive) 252 * @param max the maximum bound on the return value (exclusive) 253 * @return the found value 254 */ 255 @Override 256 public double between(double min, double max) { 257 return min + (max - min) * nextDouble(); 258 } 259 260 /** 261 * Returns a value between min (inclusive) and max (exclusive). 262 * <br> 263 * The inclusive and exclusive behavior is to match the behavior of the similar 264 * method that deals with floating point values. 265 * <br> 266 * If {@code min} and {@code max} happen to be the same, {@code min} is returned 267 * (breaking the exclusive behavior, but it's convenient to do so). 268 * 269 * @param min the minimum bound on the return value (inclusive) 270 * @param max the maximum bound on the return value (exclusive) 271 * @return the found value 272 */ 273 @Override 274 public int between(int min, int max) { 275 return nextInt(max - min) + min; 276 } 277 278 /** 279 * Returns a value between min (inclusive) and max (exclusive). 280 * <p> 281 * The inclusive and exclusive behavior is to match the behavior of the 282 * similar method that deals with floating point values. 283 * 284 * @param min the minimum bound on the return value (inclusive) 285 * @param max the maximum bound on the return value (exclusive) 286 * @return the found value 287 */ 288 @Override 289 public long between(long min, long max) { 290 return nextLong(max - min) + min; 291 } 292 293 /** 294 * Returns the average of a number of randomly selected numbers from the 295 * provided range, with min being inclusive and max being exclusive. It will 296 * sample the number of times passed in as the third parameter. 297 * <p> 298 * The inclusive and exclusive behavior is to match the behavior of the 299 * similar method that deals with floating point values. 300 * <p> 301 * This can be used to weight RNG calls to the average between min and max. 302 * 303 * @param min the minimum bound on the return value (inclusive) 304 * @param max the maximum bound on the return value (exclusive) 305 * @param samples the number of samples to take 306 * @return the found value 307 */ 308 public int betweenWeighted(int min, int max, int samples) { 309 int sum = 0; 310 for (int i = 0; i < samples; i++) { 311 sum += between(min, max); 312 } 313 314 return Math.round((float) sum / samples); 315 } 316 317 /** 318 * Returns a random element from the provided array and maintains object 319 * type. 320 * 321 * @param <T> the type of the returned object 322 * @param array the array to get an element from 323 * @return the randomly selected element 324 */ 325 @Override 326 public <T> T getRandomElement(T[] array) { 327 if (array.length < 1) { 328 return null; 329 } 330 return array[nextInt(array.length)]; 331 } 332 333 /** 334 * Returns a random element from the provided list. If the list is empty 335 * then null is returned. 336 * 337 * @param <T> the type of the returned object 338 * @param list the list to get an element from 339 * @return the randomly selected element 340 */ 341 @Override 342 public <T> T getRandomElement(List<T> list) { 343 if (list.isEmpty()) { 344 return null; 345 } 346 return list.get(nextInt(list.size())); 347 } 348 349 /** 350 * Returns a random element from the provided Collection, which should have predictable iteration order if you want 351 * predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection 352 * (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted 353 * Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement 354 * Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can 355 * pass the keys or values. If coll is empty, returns null. 356 * <p> 357 * <p> 358 * Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is 359 * likely to be decent, as long as iteration isn't unusually slow. This replaces {@code getRandomElement(Queue)}, 360 * since Queue implements Collection and the older Queue-using implementation was probably less efficient. 361 * </p> 362 * 363 * @param <T> the type of the returned object 364 * @param coll the Collection to get an element from; remember, Map does not implement Collection 365 * @return the randomly selected element 366 */ 367 @Override 368 public <T> T getRandomElement(Collection<T> coll) { 369 int n; 370 if ((n = coll.size()) <= 0) { 371 return null; 372 } 373 n = nextInt(n); 374 T t = null; 375 Iterator<T> it = coll.iterator(); 376 while (n-- >= 0 && it.hasNext()) 377 t = it.next(); 378 return t; 379 } 380 381 /** 382 * Given a {@link List} l, this selects a random element of l to be the first value in the returned list l2. It 383 * retains the order of elements in l after that random element and makes them follow the first element in l2, and 384 * loops around to use elements from the start of l after it has placed the last element of l into l2. 385 * <br> 386 * Essentially, it does what it says on the tin. It randomly rotates the List l. 387 * <br> 388 * If you only need to iterate through a collection starting at a random point, the method getRandomStartIterable() 389 * should have better performance. This was GWT incompatible before GWT 2.8.0 became the version SquidLib uses; now 390 * this method works fine with GWT. 391 * 392 * @param l A {@link List} that will not be modified by this method. All elements of this parameter will be 393 * shared with the returned List. 394 * @param <T> No restrictions on type. Changes to elements of the returned List will be reflected in the parameter. 395 * @return A shallow copy of {@code l} that has been rotated so its first element has been randomly chosen 396 * from all possible elements but order is retained. Will "loop around" to contain element 0 of l after the last 397 * element of l, then element 1, etc. 398 */ 399 public <T> List<T> randomRotation(final List<T> l) { 400 final int sz = l.size(); 401 if (sz == 0) 402 return new ArrayList<>(0); 403 404 /* 405 * Collections.rotate should prefer the best-performing way to rotate l, 406 * which would be an in-place modification for ArrayLists and an append 407 * to a sublist for Lists that don't support efficient random access. 408 */ 409 List<T> l2 = new ArrayList<>(l); 410 Collections.rotate(l2, nextInt(sz)); 411 return l2; 412 } 413 414 /** 415 * Get an Iterable that starts at a random location in list and continues on through list in its current order. 416 * Loops around to the beginning after it gets to the end, stops when it returns to the starting location. 417 * <br> 418 * You should not modify {@code list} while you use the returned reference. And there'll be no 419 * ConcurrentModificationException to detect such erroneous uses. 420 * 421 * @param list A list <b>with a constant-time {@link List#get(int)} method</b> (otherwise performance degrades). 422 * @return An {@link Iterable} that iterates over {@code list} but start at 423 * a random index. If the chosen index is {@code i}, the iterator 424 * will return: 425 * {@code list[i]; list[i+1]; ...; list[list.length() - 1]; list[0]; list[i-1]} 426 */ 427 public <T> Iterable<T> getRandomStartIterable(final List<T> list) { 428 final int sz = list.size(); 429 if (sz == 0) 430 return new ArrayList<>(0); 431 432 /* 433 * Here's a tricky bit: Defining 'start' here means that every Iterator 434 * returned by the returned Iterable will have the same iteration order. 435 * In other words, if you use more than once the returned Iterable, 436 * you'll will see elements in the same order every time, which is 437 * desirable. 438 */ 439 final int start = nextInt(sz); 440 441 return new Iterable<T>() { 442 @Override 443 public Iterator<T> iterator() { 444 return new Iterator<T>() { 445 446 int next = -1; 447 448 @Override 449 public boolean hasNext() { 450 return next != start; 451 } 452 453 @Override 454 public T next() { 455 if (next == start) 456 throw new NoSuchElementException("Iteration terminated; check hasNext() before next()"); 457 if (next == -1) 458 /* First call */ 459 next = start; 460 final T result = list.get(next); 461 if (next == sz - 1) 462 /* 463 * Reached the list's end, let's continue from the list's 464 * left. 465 */ 466 next = 0; 467 else 468 next++; 469 return result; 470 } 471 472 @Override 473 public void remove() { 474 throw new UnsupportedOperationException("Remove is not supported from a randomStartIterable"); 475 } 476 477 @Override 478 public String toString() { 479 return "RandomStartIterator at index " + next; 480 } 481 }; 482 } 483 }; 484 } 485 486 487 /** 488 * Mutates the array arr by switching the contents at pos1 and pos2. 489 * @param arr an array of T; must not be null 490 * @param pos1 an index into arr; must be at least 0 and no greater than arr.length 491 * @param pos2 an index into arr; must be at least 0 and no greater than arr.length 492 */ 493 private static <T> void swap(T[] arr, int pos1, int pos2) { 494 final T tmp = arr[pos1]; 495 arr[pos1] = arr[pos2]; 496 arr[pos2] = tmp; 497 } 498 499 /** 500 * Shuffle an array using the Fisher-Yates algorithm and returns a shuffled copy. 501 * GWT-compatible since GWT 2.8.0, which is the default if you use libGDX 1.9.5 or higher. 502 * <br> 503 * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Wikipedia has more on this algorithm</a>. 504 * 505 * @param elements an array of T; will not be modified 506 * @param <T> can be any non-primitive type. 507 * @return a shuffled copy of elements 508 */ 509 @Override 510 public <T> T[] shuffle(final T[] elements) { 511 final int size = elements.length; 512 final T[] array = Arrays.copyOf(elements, size); 513 for (int i = size; i > 1; i--) { 514 swap(array, i - 1, nextIntHasty(i)); 515 } 516 return array; 517 } 518 519 /** 520 * Shuffles an array in-place using the Fisher-Yates algorithm. 521 * If you don't want the array modified, use {@link #shuffle(Object[], Object[])}. 522 * <br> 523 * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Wikipedia has more on this algorithm</a>. 524 * 525 * @param elements an array of T; <b>will</b> be modified 526 * @param <T> can be any non-primitive type. 527 * @return elements after shuffling it in-place 528 */ 529 @Override 530 public <T> T[] shuffleInPlace(T[] elements) { 531 final int size = elements.length; 532 for (int i = size; i > 1; i--) { 533 swap(elements, i - 1, nextIntHasty(i)); 534 } 535 return elements; 536 } 537 538 /** 539 * Shuffle an array using the Fisher-Yates algorithm. If possible, create a new array or reuse an existing array 540 * with the same length as elements and pass it in as dest; the dest array will contain the shuffled contents of 541 * elements and will also be returned as-is. 542 * <br> 543 * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Wikipedia has more on this algorithm</a>. 544 * 545 * @param elements an array of T; will not be modified 546 * @param <T> can be any non-primitive type. 547 * @param dest Where to put the shuffle. If it does not have the same length as {@code elements}, this will use the 548 * randomPortion method of this class to fill the smaller dest. 549 * @return {@code dest} after modifications 550 */ 551 @Override 552 public <T> T[] shuffle(T[] elements, T[] dest) { 553 if (dest.length != elements.length) 554 return randomPortion(elements, dest); 555 System.arraycopy(elements, 0, dest, 0, elements.length); 556 shuffleInPlace(dest); 557 return dest; 558 } 559 560 /** 561 * Shuffles a {@link Collection} of T using the Fisher-Yates algorithm and returns an ArrayList of T. 562 * <br> 563 * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Wikipedia has more on this algorithm</a>. 564 * @param elements a Collection of T; will not be modified 565 * @param <T> can be any non-primitive type. 566 * @return a shuffled ArrayList containing the whole of elements in pseudo-random order. 567 */ 568 @Override 569 public <T> ArrayList<T> shuffle(Collection<T> elements) { 570 return shuffle(elements, null); 571 } 572 573 /** 574 * Shuffles a {@link Collection} of T using the Fisher-Yates algorithm. The result 575 * is allocated if {@code buf} is null or if {@code buf} isn't empty, 576 * otherwise {@code elements} is poured into {@code buf}. 577 * <br> 578 * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Wikipedia has more on this algorithm</a>. 579 * @param elements a Collection of T; will not be modified 580 * @param <T> can be any non-primitive type. 581 * @param buf a buffer as an ArrayList that will be filled with the shuffled contents of elements; 582 * if null or non-empty, a new ArrayList will be allocated and returned 583 * @return a shuffled ArrayList containing the whole of elements in pseudo-random order. 584 */ 585 @Override 586 public <T> ArrayList<T> shuffle(Collection<T> elements, /*@Nullable*/ ArrayList<T> buf) { 587 final ArrayList<T> al; 588 if (buf == null || !buf.isEmpty()) 589 al = new ArrayList<>(elements); 590 else { 591 al = buf; 592 al.addAll(elements); 593 } 594 final int n = al.size(); 595 for (int i = n; i > 1; i--) { 596 Collections.swap(al, nextInt(i), i - 1); 597 } 598 return al; 599 } 600 /** 601 * Shuffles a Collection of T items in-place using the Fisher-Yates algorithm. 602 * This only shuffles List data structures. 603 * If you don't want the array modified, use {@link #shuffle(Collection)}, which returns a List as well. 604 * <br> 605 * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">Wikipedia has more on this algorithm</a>. 606 * 607 * @param elements a Collection of T; <b>will</b> be modified 608 * @param <T> can be any non-primitive type. 609 * @return elements after shuffling it in-place 610 */ 611 @Override 612 public <T> List<T> shuffleInPlace(List<T> elements) { 613 final int n = elements.size(); 614 for (int i = n; i > 1; i--) { 615 Collections.swap(elements, nextInt(i), i - 1); 616 } 617 return elements; 618 } 619 620 621 /** 622 * Generates a random permutation of the range from 0 (inclusive) to length (exclusive). 623 * Useful for passing to OrderedMap or OrderedSet's reorder() methods. 624 * 625 * @param length the size of the ordering to produce 626 * @return a random ordering containing all ints from 0 to length (exclusive) 627 */ 628 @Override 629 public int[] randomOrdering(int length) { 630 if (length <= 0) 631 return new int[0]; 632 return randomOrdering(length, new int[length]); 633 } 634 635 /** 636 * Generates a random permutation of the range from 0 (inclusive) to length (exclusive) and stores it in 637 * the dest parameter, avoiding allocations. 638 * Useful for passing to OrderedMap or OrderedSet's reorder() methods. 639 * 640 * @param length the size of the ordering to produce 641 * @param dest the destination array; will be modified 642 * @return dest, filled with a random ordering containing all ints from 0 to length (exclusive) 643 */ 644 @Override 645 public int[] randomOrdering(int length, int[] dest) { 646 if (dest == null) return null; 647 648 final int n = Math.min(length, dest.length); 649 for (int i = 0; i < n; i++) { 650 dest[i] = i; 651 } 652 for (int i = n - 1; i > 0; i--) { 653 final int r = nextIntHasty(i+1), 654 t = dest[r]; 655 dest[r] = dest[i]; 656 dest[i] = t; 657 } 658 return dest; 659 } 660 661 /** 662 * Gets a random portion of a Collection and returns it as a new List. Will only use a given position in the given 663 * Collection at most once; does this by shuffling a copy of the Collection and getting a section of it. 664 * 665 * @param data a Collection of T; will not be modified. 666 * @param count the non-negative number of elements to randomly take from data 667 * @param <T> can be any non-primitive type 668 * @return a List of T that has length equal to the smaller of count or data.length 669 */ 670 public <T> List<T> randomPortion(Collection<T> data, int count) { 671 return shuffle(data).subList(0, Math.min(count, data.size())); 672 } 673 674 /** 675 * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements. 676 * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative). 677 * 678 * @param start the start of the range of numbers to potentially use (inclusive) 679 * @param end the end of the range of numbers to potentially use (exclusive) 680 * @param count the total number of elements to use; will be less if the range is smaller than count 681 * @return an int array that contains at most one of each number in the range 682 */ 683 public int[] randomRange(int start, int end, int count) { 684 if (end <= start || start < 0) 685 return new int[0]; 686 687 int n = end - start; 688 final int[] data = new int[n]; 689 690 for (int e = start, i = 0; e < end; e++) { 691 data[i++] = e; 692 } 693 694 for (int i = 0; i < n - 1; i++) { 695 final int r = i + nextInt(n - i), t = data[r]; 696 data[r] = data[i]; 697 data[i] = t; 698 } 699 final int[] array = new int[Math.min(count, n)]; 700 System.arraycopy(data, 0, array, 0, Math.min(count, n)); 701 return array; 702 } 703 704 /** 705 * Generates a random float with a curved distribution that centers on 0 (where it has a bias) and can (rarely) 706 * approach -1f and 1f, but not go beyond those bounds. This is similar to {@link Random#nextGaussian()} in that it 707 * uses a curved distribution, but it is not the same. The distribution for the values is similar to Irwin-Hall, and 708 * is frequently near 0 but not too-rarely near -1f or 1f. It cannot produce values greater than or equal to 1f, or 709 * less than -1f, but it can produce -1f. 710 * @return a deterministic float between -1f (inclusive) and 1f (exclusive), that is very likely to be close to 0f 711 */ 712 public float nextCurvedFloat() { 713 final long start = random.nextLong(); 714 return (intBitsToFloat((int)start >>> 9 | 0x3F000000) 715 + intBitsToFloat((int) (start >>> 41) | 0x3F000000) 716 + intBitsToFloat(((int)(start ^ ~start >>> 20) & 0x007FFFFF) | 0x3F000000) 717 + intBitsToFloat(((int) (~start ^ start >>> 30) & 0x007FFFFF) | 0x3F000000) 718 - 3f); 719 } 720 721 722 /** 723 * Gets a random double between 0.0 inclusive and 1.0 exclusive. 724 * This returns a maximum of 0.9999999999999999 because that is the largest double value that is less than 1.0 . 725 * 726 * @return a double between 0.0 (inclusive) and 0.9999999999999999 (inclusive) 727 */ 728 @Override 729 public double nextDouble() { 730 return (random.nextLong() & 0x1fffffffffffffL) * 0x1p-53; 731 //this is here for a record of another possibility; it can't generate quite a lot of possible values though 732 //return Double.longBitsToDouble(0x3FF0000000000000L | random.nextLong() >>> 12) - 1.0; 733 } 734 735 /** 736 * This returns a random double between 0.0 (inclusive) and outer (exclusive). The value for outer can be positive 737 * or negative. Because of how math on doubles works, there are at most 2 to the 53 values this can return for any 738 * given outer bound, and very large values for outer will not necessarily produce all numbers you might expect. 739 * 740 * @param outer the outer exclusive bound as a double; can be negative or positive 741 * @return a double between 0.0 (inclusive) and outer (exclusive) 742 */ 743 @Override 744 public double nextDouble(final double outer) { 745 return (random.nextLong() & 0x1fffffffffffffL) * 0x1p-53 * outer; 746 } 747 748 /** 749 * Gets a random float between 0.0f inclusive and 1.0f exclusive. 750 * This returns a maximum of 0.99999994 because that is the largest float value that is less than 1.0f . 751 * 752 * @return a float between 0f (inclusive) and 0.99999994f (inclusive) 753 */ 754 @Override 755 public float nextFloat() { 756 return random.next(24) * 0x1p-24f; 757 } 758 /** 759 * This returns a random float between 0.0f (inclusive) and outer (exclusive). The value for outer can be positive 760 * or negative. Because of how math on floats works, there are at most 2 to the 24 values this can return for any 761 * given outer bound, and very large values for outer will not necessarily produce all numbers you might expect. 762 * 763 * @param outer the outer exclusive bound as a float; can be negative or positive 764 * @return a float between 0f (inclusive) and outer (exclusive) 765 */ 766 @Override 767 public float nextFloat(final float outer) { 768 return random.next(24) * 0x1p-24f * outer; 769 } 770 771 /** 772 * Get a random bit of state, interpreted as true or false with approximately equal likelihood. 773 * This may have better behavior than {@code rng.next(1)}, depending on the RandomnessSource implementation; the 774 * default DiverRNG will behave fine, as will LightRNG and ThrustAltRNG (these all use similar algorithms), but 775 * the normally-high-quality XoRoRNG will produce very predictable output with {@code rng.next(1)} and very good 776 * output with {@code rng.nextBoolean()}. This is a known and considered flaw of Xoroshiro128+, the algorithm used 777 * by XoRoRNG, and a large number of generators have lower quality on the least-significant bit than the most- 778 * significant bit, where this method only checks the most-significant bit. 779 * @return a random boolean. 780 */ 781 @Override 782 public boolean nextBoolean() { 783 return nextLong() < 0L; 784 } 785 786 /** 787 * Get a random long between Long.MIN_VALUE to Long.MAX_VALUE (both inclusive). 788 * 789 * @return a 64-bit random long. 790 */ 791 @Override 792 public long nextLong() { 793 return random.nextLong(); 794 } 795 796 /** 797 * Gets a pseudo-random long between 0 and bound. 798 * Exclusive on bound (which must be positive), with an inner bound of 0 If bound is negative or 0, this always 799 * returns 0. You can use {@link #nextSignedLong(long)} to use a negative bound. The technique that 800 * <br> 801 * Credit for this method goes to <a href="https://oroboro.com/large-random-in-range/">Rafael Baptista's blog</a> 802 * for the original idea, and the JDK10 Math class' usage of Karatsuba multiplication for the current algorithm. 803 * This method is drastically faster than the previous implementation when the bound varies often (roughly 4x 804 * faster, possibly more). It also always gets exactly one random long, so by default it advances the state as much 805 * as {@link #nextLong()}. 806 * 807 * @param bound the outer exclusive bound; should be positive, otherwise this always returns 0L 808 * @return a random long between 0 (inclusive) and bound (exclusive) 809 */ 810 public long nextLong(long bound) { 811 long rand = random.nextLong(); 812 if (bound <= 0) return 0; 813 final long randLow = rand & 0xFFFFFFFFL; 814 final long boundLow = bound & 0xFFFFFFFFL; 815 rand >>>= 32; 816 bound >>>= 32; 817 final long a = rand * bound; 818 final long b = randLow * boundLow; 819 return (((b >>> 32) + (rand + randLow) * (bound + boundLow) - a - b) >>> 32) + a; 820 } 821 /** 822 * Exclusive on bound (which may be positive or negative), with an inner bound of 0. 823 * If bound is negative this returns a negative long; if bound is positive this returns a positive long. The bound 824 * can even be 0, which will cause this to return 0L every time. This uses a biased technique to get numbers from 825 * large ranges, but the amount of bias is incredibly small (expected to be under 1/1000 if enough random ranged 826 * numbers are requested, which is about the same as an unbiased method that was also considered).It may have 827 * noticeable bias if the generator's period is exhausted by only calls to this method. Unlike all unbiased methods, 828 * this advances the state by an equivalent to exactly one call to {@link #nextLong()}, where rejection sampling 829 * would sometimes advance by one call, but other times by arbitrarily many more. 830 * <br> 831 * Credit for this method goes to <a href="https://oroboro.com/large-random-in-range/">Rafael Baptista's blog</a> 832 * for the original idea, and the JDK10 Math class' usage of Hacker's Delight code for the current algorithm. 833 * This method is drastically faster than the previous implementation when the bound varies often (roughly 4x 834 * faster, possibly more). It also always gets exactly one random long, so by default it advances the state as much 835 * as {@link #nextLong()}. 836 * 837 * @param bound the outer exclusive bound; can be positive or negative 838 * @return a random long between 0 (inclusive) and bound (exclusive) 839 */ 840 public long nextSignedLong(long bound) { 841 long rand = random.nextLong(); 842 final long randLow = rand & 0xFFFFFFFFL; 843 final long boundLow = bound & 0xFFFFFFFFL; 844 rand >>>= 32; 845 bound >>= 32; 846 final long t = rand * boundLow + (randLow * boundLow >>> 32); 847 return rand * bound + (t >> 32) + (randLow * bound + (t & 0xFFFFFFFFL) >> 32); 848 } 849 850 /** 851 * Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), 852 * or 0 if the bound is 0. The bound can be negative, which will produce 0 or a negative result. 853 * This is almost identical to the earlier {@link #nextIntHasty(int)} except that it will perform better when the 854 * RandomnessSource this uses natively produces 32-bit output. It was added to the existing nextIntHasty() so 855 * existing code using nextIntHasty would produce the same results, but new code matches the API with 856 * {@link #nextSignedLong(long)}. This is implemented slightly differently in {@link AbstractRNG}, and different 857 * results should be expected when using code based on that abstract class. 858 * <br> 859 * Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ 860 * 861 * @param bound the outer bound (exclusive), can be negative or positive 862 * @return the found number 863 */ 864 public int nextSignedInt(final int bound) { 865 return (int) ((bound * (long)random.next(31)) >> 31); 866 } 867 868 /** 869 * Returns a random non-negative integer below the given bound, or 0 if the bound is 0 or 870 * negative. Always makes one call to the {@link RandomnessSource#next(int)} method of the RandomnessSource that 871 * would be returned by {@link #getRandomness()}, even if bound is 0 or negative, to avoid branching and also to 872 * ensure consistent advancement rates for the RandomnessSource (this can be important if you use a 873 * {@link SkippingRandomness} and want to go back before a result was produced). 874 * <br> 875 * This method changed a fair amount on April 5, 2018 to better support RandomnessSource implementations with a 876 * slower nextLong() method, such as {@link Lathe32RNG}, and to avoid branching/irregular state advancement/modulus 877 * operations. It is now almost identical to {@link #nextIntHasty(int)}, but won't return negative results if bound 878 * is negative (matching its previous behavior). This may have statistical issues (small ones) if bound is very 879 * large (the estimate is still at least a bound of a billion or more before issues are observable). Consider 880 * {@link #nextSignedInt(int)} if the bound should be allowed to be negative; {@link #nextIntHasty(int)} is here for 881 * compatibility with earlier versions, but the two methods are very similar. 882 * <br> 883 * Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ 884 * 885 * @param bound the upper bound (exclusive) 886 * @return the found number 887 */ 888 @Override 889 public int nextInt(final int bound) { 890 return (int) ((bound * ((long)random.next(31))) >>> 31) & ~(bound >> 31); 891// int threshold = (0x7fffffff - bound + 1) % bound; 892// for (; ; ) { 893// int bits = random.next(31); 894// if (bits >= threshold) 895// return bits % bound; 896// } 897 } 898 899 /** 900 * Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), 901 * or 0 if the bound is 0. The bound can be negative, which will produce 0 or a negative result. 902 * Uses an aggressively optimized technique that has some bias, but mostly for values of 903 * bound over 1 billion. This method is no more "hasty" than {@link #nextInt(int)}, but it is a little 904 * faster than that method because this avoids special behavior for when bound is negative. 905 * <br> 906 * Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ 907 * 908 * @param bound the outer bound (exclusive), can be negative or positive 909 * @return the found number 910 */ 911 public int nextIntHasty(final int bound) { 912 return (int) ((bound * (random.nextLong() & 0x7FFFFFFFL)) >> 31); 913 } 914 915 /** 916 * Generates random bytes and places them into the given byte array, modifying it in-place. 917 * The number of random bytes produced is equal to the length of the byte array. Unlike the 918 * method in java.util.Random, this generates 8 bytes at a time, which can be more efficient 919 * with many RandomnessSource types than the JDK's method that generates 4 bytes at a time. 920 * <br> 921 * Adapted from code in the JavaDocs of {@link Random#nextBytes(byte[])}. 922 * <br> 923 * @param bytes the byte array to fill with random bytes; cannot be null, will be modified 924 * @throws NullPointerException if the byte array is null 925 */ 926 public void nextBytes(final byte[] bytes) { 927 for (int i = 0; i < bytes.length; ) 928 for (long r = random.nextLong(), n = Math.min(bytes.length - i, 8); n-- > 0; r >>>= 8) 929 bytes[i++] = (byte) r; 930 } 931 932 /** 933 * Get a random integer between Integer.MIN_VALUE to Integer.MAX_VALUE (both inclusive). 934 * 935 * @return a 32-bit random int. 936 */ 937 @Override 938 public int nextInt() { 939 return random.next(32); 940 } 941 942 /** 943 * Get up to 32 bits (inclusive) of random output; the int this produces 944 * will not require more than {@code bits} bits to represent. 945 * 946 * @param bits an int between 1 and 32, both inclusive 947 * @return a random number that fits in the specified number of bits 948 */ 949 @Override 950 public int next(int bits) { 951 return random.next(bits); 952 } 953 954 public RandomnessSource getRandomness() { 955 return random; 956 } 957 958 public void setRandomness(RandomnessSource random) { 959 this.random = random; 960 } 961 962 /** 963 * Creates a copy of this RNG; it will generate the same random numbers, given the same calls in order, as this RNG 964 * at the point copy() is called. The copy will not share references with this RNG. 965 * 966 * @return a copy of this RNG 967 */ 968 @Override 969 public RNG copy() { 970 return new RNG(random.copy()); 971 } 972 973 /** 974 * Generates a random 64-bit long with a number of '1' bits (Hamming weight) equal on average to bitCount. 975 * For example, calling this with a parameter of 32 will be equivalent to calling nextLong() on this object's 976 * RandomnessSource (it doesn't consider overridden nextLong() methods, where present, on subclasses of RNG). 977 * Calling this with a parameter of 16 will have on average 16 of the 64 bits in the returned long set to '1', 978 * distributed pseudo-randomly, while a parameter of 47 will have on average 47 bits set. This can be useful for 979 * certain code that uses bits to represent data but needs a different ratio of set bits to unset bits than 1:1. 980 * <br> 981 * This method is deprecated because it really only finds usage in GreasedRegion, so it has been moved there and 982 * made so it can take any RandomnessSource as a parameter, including any IRNG or RNG. 983 * 984 * @param bitCount an int, only considered if between 0 and 64, that is the average number of bits to set 985 * @return a 64-bit long that, on average, should have bitCount bits set to 1, potentially anywhere in the long 986 * @deprecated see the version in GreasedRegion, {@link GreasedRegion#approximateBits(RandomnessSource, int)} 987 */ 988 @Deprecated 989 public long approximateBits(int bitCount) { 990 if (bitCount <= 0) 991 return 0L; 992 if (bitCount >= 64) 993 return -1L; 994 if (bitCount == 32) 995 return random.nextLong(); 996 boolean high = bitCount > 32; 997 int altered = (high ? 64 - bitCount : bitCount), lsb = NumberTools.lowestOneBit(altered); 998 long data = random.nextLong(); 999 for (int i = lsb << 1; i <= 16; i <<= 1) { 1000 if ((altered & i) == 0) 1001 data &= random.nextLong(); 1002 else 1003 data |= random.nextLong(); 1004 } 1005 return high ? ~(random.nextLong() & data) : (random.nextLong() & data); 1006 } 1007 1008 /** 1009 * Gets a somewhat-random long with exactly 32 bits set; in each pair of bits starting at bit 0 and bit 1, then bit 1010 * 2 and bit 3, up to bit 62 and bit 3, one bit will be 1 and one bit will be 0 in each pair. 1011 * <br> 1012 * Not exactly general-use; meant for generating data for GreasedRegion. This is deprecated in favor of the version 1013 * in GreasedRegion. 1014 * @return a random long with 32 "1" bits, distributed so exactly one bit is "1" for each pair of bits 1015 * @deprecated See {@link GreasedRegion#randomInterleave(RandomnessSource)} for where this will be moved 1016 */ 1017 @Deprecated 1018 public long randomInterleave() { 1019 long bits = nextLong() & 0xFFFFFFFFL, ib = ~bits & 0xFFFFFFFFL; 1020 bits |= (bits << 16); 1021 ib |= (ib << 16); 1022 bits &= 0x0000FFFF0000FFFFL; 1023 ib &= 0x0000FFFF0000FFFFL; 1024 bits |= (bits << 8); 1025 ib |= (ib << 8); 1026 bits &= 0x00FF00FF00FF00FFL; 1027 ib &= 0x00FF00FF00FF00FFL; 1028 bits |= (bits << 4); 1029 ib |= (ib << 4); 1030 bits &= 0x0F0F0F0F0F0F0F0FL; 1031 ib &= 0x0F0F0F0F0F0F0F0FL; 1032 bits |= (bits << 2); 1033 ib |= (ib << 2); 1034 bits &= 0x3333333333333333L; 1035 ib &= 0x3333333333333333L; 1036 bits |= (bits << 1); 1037 ib |= (ib << 1); 1038 bits &= 0x5555555555555555L; 1039 ib &= 0x5555555555555555L; 1040 return (bits | (ib << 1)); 1041 } 1042 1043 /** 1044 * Gets the minimum random long between 0 and {@code bound} generated out of {@code trials} generated numbers. 1045 * Useful for when numbers should have a strong bias toward zero, but all possible values are between 0, inclusive, 1046 * and bound, exclusive. 1047 * @param bound the outer exclusive bound; may be negative or positive 1048 * @param trials how many numbers to generate and get the minimum of 1049 * @return the minimum generated long between 0 and bound out of the specified amount of trials 1050 */ 1051 public long minLongOf(final long bound, final int trials) 1052 { 1053 long value = nextSignedLong(bound); 1054 for (int i = 1; i < trials; i++) { 1055 value = Math.min(value, nextSignedLong(bound)); 1056 } 1057 return value; 1058 } 1059 /** 1060 * Gets the maximum random long between 0 and {@code bound} generated out of {@code trials} generated numbers. 1061 * Useful for when numbers should have a strong bias away from zero, but all possible values are between 0, 1062 * inclusive, and bound, exclusive. 1063 * @param bound the outer exclusive bound; may be negative or positive 1064 * @param trials how many numbers to generate and get the maximum of 1065 * @return the maximum generated long between 0 and bound out of the specified amount of trials 1066 */ 1067 public long maxLongOf(final long bound, final int trials) 1068 { 1069 long value = nextSignedLong(bound); 1070 for (int i = 1; i < trials; i++) { 1071 value = Math.max(value, nextSignedLong(bound)); 1072 } 1073 return value; 1074 } 1075 1076 /** 1077 * Gets the minimum random int between 0 and {@code bound} generated out of {@code trials} generated numbers. 1078 * Useful for when numbers should have a strong bias toward zero, but all possible values are between 0, inclusive, 1079 * and bound, exclusive. 1080 * @param bound the outer exclusive bound; may be negative or positive 1081 * @param trials how many numbers to generate and get the minimum of 1082 * @return the minimum generated int between 0 and bound out of the specified amount of trials 1083 */ 1084 public int minIntOf(final int bound, final int trials) 1085 { 1086 int value = nextSignedInt(bound); 1087 for (int i = 1; i < trials; i++) { 1088 value = Math.min(value, nextSignedInt(bound)); 1089 } 1090 return value; 1091 } 1092 /** 1093 * Gets the maximum random int between 0 and {@code bound} generated out of {@code trials} generated numbers. 1094 * Useful for when numbers should have a strong bias away from zero, but all possible values are between 0, 1095 * inclusive, and bound, exclusive. 1096 * @param bound the outer exclusive bound; may be negative or positive 1097 * @param trials how many numbers to generate and get the maximum of 1098 * @return the maximum generated int between 0 and bound out of the specified amount of trials 1099 */ 1100 public int maxIntOf(final int bound, final int trials) 1101 { 1102 int value = nextSignedInt(bound); 1103 for (int i = 1; i < trials; i++) { 1104 value = Math.max(value, nextSignedInt(bound)); 1105 } 1106 return value; 1107 } 1108 1109 /** 1110 * Gets the minimum random double between 0 and {@code bound} generated out of {@code trials} generated numbers. 1111 * Useful for when numbers should have a strong bias toward zero, but all possible values are between 0, inclusive, 1112 * and bound, exclusive. 1113 * @param bound the outer exclusive bound 1114 * @param trials how many numbers to generate and get the minimum of 1115 * @return the minimum generated double between 0 and bound out of the specified amount of trials 1116 */ 1117 public double minDoubleOf(final double bound, final int trials) 1118 { 1119 double value = nextDouble(bound); 1120 for (int i = 1; i < trials; i++) { 1121 value = Math.min(value, nextDouble(bound)); 1122 } 1123 return value; 1124 } 1125 1126 /** 1127 * Gets the maximum random double between 0 and {@code bound} generated out of {@code trials} generated numbers. 1128 * Useful for when numbers should have a strong bias away from zero, but all possible values are between 0, 1129 * inclusive, and bound, exclusive. 1130 * @param bound the outer exclusive bound 1131 * @param trials how many numbers to generate and get the maximum of 1132 * @return the maximum generated double between 0 and bound out of the specified amount of trials 1133 */ 1134 public double maxDoubleOf(final double bound, final int trials) 1135 { 1136 double value = nextDouble(bound); 1137 for (int i = 1; i < trials; i++) { 1138 value = Math.max(value, nextDouble(bound)); 1139 } 1140 return value; 1141 } 1142 /** 1143 * Gets the minimum random float between 0 and {@code bound} generated out of {@code trials} generated numbers. 1144 * Useful for when numbers should have a strong bias toward zero, but all possible values are between 0, inclusive, 1145 * and bound, exclusive. 1146 * @param bound the outer exclusive bound 1147 * @param trials how many numbers to generate and get the minimum of 1148 * @return the minimum generated float between 0 and bound out of the specified amount of trials 1149 */ 1150 public float minFloatOf(final float bound, final int trials) 1151 { 1152 float value = nextFloat(bound); 1153 for (int i = 1; i < trials; i++) { 1154 value = Math.min(value, nextFloat(bound)); 1155 } 1156 return value; 1157 } 1158 1159 /** 1160 * Gets the maximum random float between 0 and {@code bound} generated out of {@code trials} generated numbers. 1161 * Useful for when numbers should have a strong bias away from zero, but all possible values are between 0, 1162 * inclusive, and bound, exclusive. 1163 * @param bound the outer exclusive bound 1164 * @param trials how many numbers to generate and get the maximum of 1165 * @return the maximum generated float between 0 and bound out of the specified amount of trials 1166 */ 1167 public float maxFloatOf(final float bound, final int trials) 1168 { 1169 float value = nextFloat(bound); 1170 for (int i = 1; i < trials; i++) { 1171 value = Math.max(value, nextFloat(bound)); 1172 } 1173 return value; 1174 } 1175 1176 1177 @Override 1178 public String toString() { 1179 return "RNG with Randomness Source " + random; 1180 } 1181 1182 @Override 1183 public boolean equals(Object o) { 1184 if (this == o) return true; 1185 if (!(o instanceof RNG)) return false; 1186 1187 RNG rng = (RNG) o; 1188 1189 return random.equals(rng.random); 1190 } 1191 1192 @Override 1193 public int hashCode() { 1194 return 31 * random.hashCode(); 1195 } 1196 1197 /** 1198 * Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as 1199 * it can, and then returns output. Will only use a given position in the given data at most once; uses a Feistel 1200 * Network to accomplish this without allocations. Internally, makes 2 calls to {@link #nextInt()}, regardless of 1201 * the data being randomized. 1202 * <br> 1203 * Uses approximately the same code as {@link LowStorageShuffler}, but without any object or array allocations. 1204 * 1205 * @param data an array of T; will not be modified. 1206 * @param output an array of T that will be overwritten; should always be instantiated with the portion length 1207 * @param <T> can be any non-primitive type. 1208 * @return output, after {@code Math.min(output.length, data.length)} unique items have been put into it from data 1209 */ 1210 @Override 1211 public <T> T[] randomPortion(T[] data, T[] output) { 1212 final int length = data.length, n = Math.min(length, output.length); 1213 // calculate next power of 4. Needed since the balanced Feistel network needs 1214 // an even number of bits to work with 1215 int pow4 = HashCommon.nextPowerOfTwo(length); 1216 if((pow4 & 0x55555554) == 0) 1217 pow4 = HashCommon.nextPowerOfTwo(pow4); 1218 pow4--; 1219 // calculate our left and right masks to split our indices for the Feistel network 1220 final int halfBits = Integer.bitCount(pow4) >>> 1; 1221 final int rightMask = pow4 >>> halfBits; 1222 final int leftMask = pow4 ^ rightMask; 1223 final int key0 = nextInt(), key1 = nextInt(); 1224 int index = 0; 1225 for (int i = 0; i < n; i++) { 1226 int shuffleIndex; 1227 // index is the index to start searching for the next number at 1228 while (index <= pow4) 1229 { 1230 // break our index into the left and right half 1231 int left = (index & leftMask) >>> halfBits; 1232 int right = (index & rightMask); 1233 // do 2 Feistel rounds 1234 int newRight = left ^ (LowStorageShuffler.round(right, key0) & rightMask); 1235 left = right; 1236 right = newRight; 1237 newRight = left ^ (LowStorageShuffler.round(right, key1) & rightMask); 1238 shuffleIndex = right << halfBits | newRight; 1239 index++; 1240 1241 // if we found a valid index, return it! 1242 if (shuffleIndex < length) { 1243 output[i] = data[shuffleIndex]; 1244 break; 1245 } 1246 } 1247 } 1248 return output; 1249 } 1250 1251 1252 /** 1253 * Gets a random double between 0.0 inclusive and 1.0 inclusive. 1254 * 1255 * @return a double between 0.0 (inclusive) and 1.0 (inclusive) 1256 */ 1257 public double nextDoubleInclusive() 1258 { 1259 return (random.nextLong() & 0x1fffffffffffffL) * 0x1.0000000000001p-53; 1260 } 1261 1262 /** 1263 * This returns a random double between 0.0 (inclusive) and outer (inclusive). The value for outer can be positive 1264 * or negative. Because of how math on doubles works, there are at most 2 to the 53 values this can return for any 1265 * given outer bound, and very large values for outer will not necessarily produce all numbers you might expect. 1266 * 1267 * @param outer the outer inclusive bound as a double; can be negative or positive 1268 * @return a double between 0.0 (inclusive) and outer (inclusive) 1269 */ 1270 public double nextDoubleInclusive(final double outer) { 1271 return (random.nextLong() & 0x1fffffffffffffL) * 0x1.0000000000001p-53 * outer; 1272 } 1273 1274 /** 1275 * Gets a random float between 0.0f inclusive and 1.0f inclusive. 1276 * 1277 * @return a float between 0f (inclusive) and 1f (inclusive) 1278 */ 1279 public float nextFloatInclusive() { 1280 return random.next(24) * 0x1.000002p-24f; 1281 } 1282 1283 /** 1284 * This returns a random float between 0.0f (inclusive) and outer (inclusive). The value for outer can be positive 1285 * or negative. Because of how math on floats works, there are at most 2 to the 24 values this can return for any 1286 * given outer bound, and very large values for outer will not necessarily produce all numbers you might expect. 1287 * 1288 * @param outer the outer inclusive bound as a float; can be negative or positive 1289 * @return a float between 0f (inclusive) and outer (inclusive) 1290 */ 1291 public float nextFloatInclusive(final float outer) { 1292 return random.next(24) * 0x1.000002p-24f * outer; 1293 } 1294 1295 1296 1297 1298 1299 /** 1300 * Gets a random Coord that has x between 0 (inclusive) and width (exclusive) and y between 0 (inclusive) 1301 * and height (exclusive). This makes one call to randomLong to generate (more than) 31 random bits for 1302 * each axis, and should be very fast. Remember that Coord values are cached in a pool that starts able to 1303 * hold up to 255 x and 255 y for positive values, and the pool should be grown with the static method 1304 * Coord.expandPool() in order to efficiently use larger Coord values. If width and height are very large, 1305 * greater than 100,000 for either, this particular method may show bias toward certain positions due to 1306 * the "hasty" technique used to reduce the random numbers to the given size, but because most maps in 1307 * tile-based games are relatively small, this technique should be fine. 1308 * <br> 1309 * Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ 1310 * 1311 * @param width the upper bound (exclusive) for x coordinates 1312 * @param height the upper bound (exclusive) for y coordinates 1313 * @return a random Coord between (0,0) inclusive and (width,height) exclusive 1314 */ 1315 public Coord nextCoord(int width, int height) { 1316 final long n = random.nextLong(); 1317 return Coord.get((int) ((width * (n >>> 33)) >> 31), (int) ((height * (n & 0x7FFFFFFFL)) >> 31)); 1318 } 1319 1320 /** 1321 * Use that to get random cells in a rectangular map. 1322 * 1323 * @param width The map's width (bounds the x-coordinate in returned coords). 1324 * @param height The map's height (bounds the y-coordinate in returned coords). 1325 * @param size The number of elements in the returned iterable or anything 1326 * negative for no bound (in which case the iterator is infinite, it's 1327 * up to you to bound your iteration). 1328 * @return An iterable that returns random cells in the rectangle (0,0) 1329 * (inclusive) .. (width, height) (exclusive). 1330 */ 1331 public Iterable<Coord> getRandomCellsIterable(final int width, final int height, final int size) { 1332 return new Iterable<Coord>() { 1333 @Override 1334 public Iterator<Coord> iterator() { 1335 return new Iterator<Coord>() { 1336 1337 /** 1338 * The number of elements returned so far 1339 */ 1340 int returned; 1341 1342 @Override 1343 public boolean hasNext() { 1344 return size < 0 || returned < size; 1345 } 1346 1347 @Override 1348 public Coord next() { 1349 if (!hasNext()) 1350 throw new NoSuchElementException(); 1351 returned++; 1352 return nextCoord(width, height); 1353 } 1354 1355 @Override 1356 public void remove() { 1357 throw new UnsupportedOperationException(); 1358 } 1359 }; 1360 } 1361 }; 1362 } 1363 1364 /** 1365 * Gets an array of unique Coords, from (startX,startY) inclusive to (startX+width,startY+height) exclusive, in a 1366 * random order, with the array containing {@code width * height} items. 1367 * 1368 * @param startX the inclusive starting x position 1369 * @param startY the inclusive starting y position 1370 * @param width the width of the space to place Coords in, extending from startX 1371 * @param height the height of the space to place Coords in, extending from startY 1372 * @return an array containing {@code width * height} Coord items in random order, inside the given bounds 1373 */ 1374 public Coord[] getRandomUniqueCells(final int startX, final int startY, final int width, final int height) { 1375 if (width <= 0 || height <= 0) 1376 return new Coord[0]; 1377 return getRandomUniqueCells(startX, startY, width, height, new Coord[width * height]); 1378 } 1379 1380 /** 1381 * Gets an array of unique Coords, from (startX,startY) inclusive to (startX+width,startY+height) exclusive, in a 1382 * random order, with the array containing {@code Math.min(width * height, size)} items. If size is less than width 1383 * times height, then not all Coords in the space will be used. 1384 * 1385 * @param startX the inclusive starting x position 1386 * @param startY the inclusive starting y position 1387 * @param width the width of the space to place Coords in, extending from startX 1388 * @param height the height of the space to place Coords in, extending from startY 1389 * @param size the size of the array to return; only matters if it is smaller than {@code width * height} 1390 * @return an array containing {@code Math.min(width * height, size)} Coord items in random order, inside the given bounds 1391 */ 1392 public Coord[] getRandomUniqueCells(final int startX, final int startY, final int width, final int height, 1393 final int size) { 1394 if (width <= 0 || height <= 0 || size <= 0) 1395 return new Coord[0]; 1396 return getRandomUniqueCells(startX, startY, width, height, new Coord[Math.min(width * height, size)]); 1397 } 1398 1399 /** 1400 * Assigns to dest an array of unique Coords, from (startX,startY) inclusive to (startX+width,startY+height) 1401 * exclusive, in a random order, with dest after this is called containing the lesser of {@code width * height} or 1402 * {@code dest.length} items. This will not allocate a new array for dest, but will create a temporary int array for 1403 * handling the shuffle. 1404 * 1405 * @param startX the inclusive starting x position 1406 * @param startY the inclusive starting y position 1407 * @param width the width of the space to place Coords in, extending from startX 1408 * @param height the height of the space to place Coords in, extending from startY 1409 * @param dest a Coord array that will be modified to contain randomly-ordered Coords, but will not be resized 1410 * @return dest, now with up to its first {@code width * height} items assigned to random Coords inside the given bounds 1411 */ 1412 public Coord[] getRandomUniqueCells(final int startX, final int startY, final int width, final int height, 1413 final Coord[] dest) { 1414 if (width <= 0 || height <= 0 || dest == null || dest.length <= 0) 1415 return dest; 1416 int[] o = randomOrdering(width * height); 1417 for (int i = 0; i < o.length && i < dest.length; i++) { 1418 dest[i] = Coord.get(startX + o[i] % width, startY + o[i] / width); 1419 } 1420 return dest; 1421 } 1422 1423 /** 1424 * Returns this RNG in a way that can be deserialized even if only {@link IRNG}'s methods can be called. 1425 * @return a {@link Serializable} view of this RNG; always {@code this} 1426 */ 1427 @Override 1428 public Serializable toSerializable() { 1429 return this; 1430 } 1431}