001package squidpony.squidmath; 002 003import squidpony.annotation.GwtIncompatible; 004 005import java.io.Serializable; 006import java.util.*; 007 008/** 009 * A wrapper class for working with random number generators in a more friendly 010 * way. 011 * 012 * Includes methods for getting values between two numbers and for getting 013 * random elements from a collection or array. 014 * 015 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 016 * @author Tommy Ettinger 017 * @author smelC 018 */ 019public class RNG implements Serializable { 020 021 protected static final double DOUBLE_UNIT = 1.0 / (1L << 53); 022 protected static final float FLOAT_UNIT = 1.0f / (1 << 24); 023 protected RandomnessSource random; 024 protected double nextNextGaussian; 025 protected boolean haveNextNextGaussian = false; 026 protected Random ran = null; 027 028 private static final long serialVersionUID = 2352426757973945149L; 029 030 /** 031 * Default constructor; uses SplitMix64, which is of high quality, but low period (which rarely matters for games), 032 * and has good speed, tiny state size, and excellent 64-bit number generation. 033 * <br> 034 * Compatibility note: previous versions of SquidLib used Mersenne Twister by default. Due to the incompatibility 035 * of the threads used by this Mersenne Twister implementation with GWT and HTML5 applications, the randomness 036 * algorithm has been changed to a faster, more compatible algorithm, though it does suffer from a much lower 037 * period. If you need drastically larger periods than 2^64, you can pass a LongPeriodRNG (or MersenneTwister on 038 * targets other than HTML) object to the constructor that takes a RandomnessSource. If you don't know what the 039 * period of a PRNG is, you probably don't need to worry about it; it's mainly relevant to heavily multi-threaded 040 * applications anyway. The addition of LongPeriodRNG on March 21, 2016 should help to take the part of a fast, 041 * large-period RNG, which MersenneTwister is unable to act as on GWT. The default may change again some time after 042 * May 1, 2016, now that we have XoRoRNG, which is approximately as fast as LightRNG and has a substantially better 043 * period (pow(2, 128) - 1). 044 */ 045 public RNG() { 046 this(new LightRNG()); 047 } 048 049 /** 050 * Seeded constructor; uses LightRNG, which is of high quality, but low period (which rarely matters for games), 051 * and has good speed, tiny state size, and excellent 64-bit number generation. 052 */ 053 public RNG(long seed) { 054 this(new LightRNG(seed)); 055 } 056 057 /** 058 * String-seeded constructor; uses a platform-independent hash of the String (it does not use String.hashCode) as a 059 * seed for LightRNG, which is of high quality, but low period (which rarely matters for games), and has good speed, 060 * tiny state size, and excellent 64-bit number generation. 061 */ 062 public RNG(String seedString) { 063 this(new LightRNG(CrossHash.hash(seedString))); 064 } 065 066 /** 067 * Uses the provided source of randomness for all calculations. This 068 * constructor should be used if an alternate RandomnessSource other than LightRNG is desirable. 069 * 070 * @param random the source of pseudo-randomness, such as a MersenneTwister or SobolQRNG object 071 */ 072 public RNG(RandomnessSource random) { 073 this.random = random; 074 } 075 076 /** 077 * A subclass of java.util.Random that uses a RandomnessSource supplied by the user instead of the default. 078 * @author Tommy Ettinger 079 */ 080 public static class CustomRandom extends Random 081 { 082 083 private static final long serialVersionUID = 8211985716129281944L; 084 private final RandomnessSource randomnessSource; 085 086 /** 087 * Creates a new random number generator. This constructor uses 088 * a LightRNG with a random seed. 089 */ 090 public CustomRandom() 091 { 092 randomnessSource = new LightRNG(); 093 } 094 /** 095 * Creates a new random number generator. This constructor uses 096 * the seed of the given RandomnessSource if it has been seeded. 097 * @param randomnessSource a way to get random bits, supplied by RNG 098 */ 099 public CustomRandom(RandomnessSource randomnessSource) { 100 this.randomnessSource = randomnessSource; 101 } 102 103 /** 104 * Generates the next pseudorandom number. Subclasses should 105 * override this, as this is used by all other methods. 106 * <p> 107 * <p>The general contract of {@code next} is that it returns an 108 * {@code int} value and if the argument {@code bits} is between 109 * {@code 1} and {@code 32} (inclusive), then that many low-order 110 * bits of the returned value will be (approximately) independently 111 * chosen bit values, each of which is (approximately) equally 112 * likely to be {@code 0} or {@code 1}. The method {@code next} is 113 * implemented by class {@code Random} by atomically updating the seed to 114 * <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre> 115 * and returning 116 * <pre>{@code (int)(seed >>> (48 - bits))}.</pre> 117 * <p> 118 * This is a linear congruential pseudorandom number generator, as 119 * defined by D. H. Lehmer and described by Donald E. Knuth in 120 * <i>The Art of Computer Programming,</i> Volume 3: 121 * <i>Seminumerical Algorithms</i>, section 3.2.1. 122 * 123 * @param bits random bits 124 * @return the next pseudorandom value from this random number 125 * generator's sequence 126 * @since 1.1 127 */ 128 @Override 129 protected int next(int bits) { 130 return randomnessSource.next(bits); 131 } 132 } 133 /** 134 * @return a Random instance that can be used for legacy compatibility 135 */ 136 public Random asRandom() { 137 if (ran == null) { 138 ran = new CustomRandom(random); 139 } 140 return ran; 141 } 142 143 /** 144 * Returns a value from a even distribution from min (inclusive) to max 145 * (exclusive). 146 * 147 * @param min the minimum bound on the return value (inclusive) 148 * @param max the maximum bound on the return value (exclusive) 149 * @return the found value 150 */ 151 public double between(double min, double max) { 152 return min + (max - min) * nextDouble(); 153 } 154 155 /** 156 * Returns a value between min (inclusive) and max (exclusive). 157 * 158 * The inclusive and exclusive behavior is to match the behavior of the 159 * similar method that deals with floating point values. 160 * 161 * @param min the minimum bound on the return value (inclusive) 162 * @param max the maximum bound on the return value (exclusive) 163 * @return the found value 164 */ 165 public int between(int min, int max) { 166 return nextInt(max - min) + min; 167 } 168 169 /** 170 * Returns a value between min (inclusive) and max (exclusive). 171 * 172 * The inclusive and exclusive behavior is to match the behavior of the 173 * similar method that deals with floating point values. 174 * 175 * @param min the minimum bound on the return value (inclusive) 176 * @param max the maximum bound on the return value (exclusive) 177 * @return the found value 178 */ 179 public long between(long min, long max) { 180 return nextLong(max - min) + min; 181 } 182 183 /** 184 * Returns the average of a number of randomly selected numbers from the 185 * provided range, with min being inclusive and max being exclusive. It will 186 * sample the number of times passed in as the third parameter. 187 * 188 * The inclusive and exclusive behavior is to match the behavior of the 189 * similar method that deals with floating point values. 190 * 191 * This can be used to weight RNG calls to the average between min and max. 192 * 193 * @param min the minimum bound on the return value (inclusive) 194 * @param max the maximum bound on the return value (exclusive) 195 * @param samples the number of samples to take 196 * @return the found value 197 */ 198 public int betweenWeighted(int min, int max, int samples) { 199 int sum = 0; 200 for (int i = 0; i < samples; i++) { 201 sum += between(min, max); 202 } 203 204 return Math.round((float) sum / samples); 205 } 206 207 /** 208 * Returns a random element from the provided array and maintains object 209 * type. 210 * 211 * @param <T> the type of the returned object 212 * @param array the array to get an element from 213 * @return the randomly selected element 214 */ 215 public <T> T getRandomElement(T[] array) { 216 if (array.length < 1) { 217 return null; 218 } 219 return array[nextInt(array.length)]; 220 } 221 222 /** 223 * Returns a random element from the provided list. If the list is empty 224 * then null is returned. 225 * 226 * @param <T> the type of the returned object 227 * @param list the list to get an element from 228 * @return the randomly selected element 229 */ 230 public <T> T getRandomElement(List<T> list) { 231 if (list.size() <= 0) { 232 return null; 233 } 234 return list.get(nextInt(list.size())); 235 } 236 237 /** 238 * Returns a random element from the provided ShortSet. If the set is empty 239 * then an exception is thrown. 240 * 241 * <p> 242 * Requires iterating through a random amount of the elements in set, so performance depends on the size of set but 243 * is likely to be decent. This is mostly meant for internal use, the same as ShortSet. 244 * </p> 245 * @param set the ShortSet to get an element from 246 * @return the randomly selected element 247 */ 248 public short getRandomElement(ShortSet set) { 249 if (set.size <= 0) { 250 throw new UnsupportedOperationException("ShortSet cannot be empty when getting a random element"); 251 } 252 int n = nextInt(set.size); 253 short s = 0; 254 ShortSet.ShortSetIterator ssi = set.iterator(); 255 while (n-- >= 0 && ssi.hasNext) 256 s = ssi.next(); 257 ssi.reset(); 258 return s; 259 } 260 261 /** 262 * Returns a random element from the provided Collection, which should have predictable iteration order if you want 263 * predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection 264 * (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted 265 * Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement 266 * Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can 267 * pass the keys or values. If coll is empty, returns null. 268 * 269 * <p> 270 * Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is 271 * likely to be decent, as long as iteration isn't unusually slow. This replaces {@code getRandomElement(Queue)}, 272 * since Queue implements Collection and the older Queue-using implementation was probably less efficient. 273 * </p> 274 * @param <T> the type of the returned object 275 * @param coll the Collection to get an element from; remember, Map does not implement Collection 276 * @return the randomly selected element 277 */ 278 public <T> T getRandomElement(Collection<T> coll) { 279 if (coll.size() <= 0) { 280 return null; 281 } 282 int n = nextInt(coll.size()); 283 T t = null; 284 Iterator<T> it = coll.iterator(); 285 while (n-- >= 0 && it.hasNext()) 286 t = it.next(); 287 return t; 288 } 289 290 /* 291 * Returns a random elements from the provided queue. If the queue is empty 292 * then null is returned. 293 * 294 * <p> 295 * Beware that this method allocates a copy of {@code list}, hence it's 296 * quite costly. 297 * </p> 298 * 299 * @param <T> the type of the returned object 300 * @param list the list to get an element from 301 * @return the randomly selected element 302 */ 303 /* 304 public <T> T getRandomElement(Queue<T> list) { 305 if (list.isEmpty()) { 306 return null; 307 } 308 return new ArrayList<>(list).get(nextInt(list.size())); 309 }*/ 310 311 /** 312 * Given a {@link List} l, this selects a random element of l to be the first value in the returned list l2. It 313 * retains the order of elements in l after that random element and makes them follow the first element in l2, and 314 * loops around to use elements from the start of l after it has placed the last element of l into l2. 315 * <br> 316 * Essentially, it does what it says on the tin. It randomly rotates the List l. 317 * <br> 318 * If you only need to iterate through a collection starting at a random point, the method getRandomStartIterable() 319 * should have better performance. 320 * 321 * @param l A {@link List} that will not be modified by this method. All elements of this parameter will be 322 * shared with the returned List. 323 * @param <T> No restrictions on type. Changes to elements of the returned List will be reflected in the parameter. 324 * @return A shallow copy of {@code l} that has been rotated so its first element has been randomly chosen 325 * from all possible elements but order is retained. Will "loop around" to contain element 0 of l after the last 326 * element of l, then element 1, etc. 327 */ 328 @GwtIncompatible /* Because of Collections.rotate */ 329 public <T> List<T> randomRotation(final List<T> l) { 330 final int sz = l.size(); 331 if (sz == 0) 332 return Collections.<T>emptyList(); 333 334 /* 335 * Collections.rotate should prefer the best-performing way to rotate l, which would be an in-place 336 * modification for ArrayLists and an append to a sublist for Lists that don't support efficient random access. 337 */ 338 List<T> l2 = new ArrayList<>(l); 339 Collections.rotate(l2, nextInt(sz)); 340 return l2; 341 } 342 /** 343 * Get an Iterable that starts at a random location in list and continues on through list in its current order. 344 * Loops around to the beginning after it gets to the end, stops when it returns to the starting location. 345 * <br> 346 * You should not modify {@code list} while you use the returned reference. And there'll be no 347 * ConcurrentModificationException to detect such erroneous uses. 348 * @param list A list <b>with a constant-time {@link List#get(int)} method</b> (otherwise performance degrades). 349 * @return An {@link Iterable} that iterates over {@code list} but start at 350 * a random index. If the chosen index is {@code i}, the iterator 351 * will return: 352 * {@code list[i]; list[i+1]; ...; list[list.length() - 1]; list[0]; list[i-1]} 353 * 354 */ 355 public <T> Iterable<T> getRandomStartIterable(final List<T> list) { 356 final int sz = list.size(); 357 if (sz == 0) 358 return Collections.<T> emptyList(); 359 360 /* 361 * Here's a tricky bit: Defining 'start' here means that every Iterator 362 * returned by the returned Iterable will have the same iteration order. 363 * In other words, if you use more than once the returned Iterable, 364 * you'll will see elements in the same order every time, which is 365 * desirable. 366 */ 367 final int start = nextInt(sz); 368 369 return new Iterable<T>() { 370 @Override 371 public Iterator<T> iterator() { 372 return new Iterator<T>() { 373 374 int next = -1; 375 376 @Override 377 public boolean hasNext() { 378 return next != start; 379 } 380 381 @Override 382 public T next() { 383 if (next == start) 384 throw new NoSuchElementException("Iteration terminated; check hasNext() before next()"); 385 if (next == -1) 386 /* First call */ 387 next = start; 388 final T result = list.get(next); 389 if (next == sz - 1) 390 /* 391 * Reached the list's end, let's continue from the list's 392 * left. 393 */ 394 next = 0; 395 else 396 next++; 397 return result; 398 } 399 400 @Override 401 public void remove() { 402 throw new UnsupportedOperationException("Remove is not supported from a randomStartIterable"); 403 } 404 405 @Override 406 public String toString() { 407 return "RandomStartIterator at index " + next; 408 } 409 }; 410 } 411 }; 412 } 413 414 /** 415 * Shuffle an array using the Fisher-Yates algorithm. Not GWT-compatible; use the overload that takes two arrays. 416 * <br> 417 * https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle 418 * @param elements an array of T; will not be modified 419 * @param <T> can be any non-primitive type. 420 * @return a shuffled copy of elements 421 */ 422 @GwtIncompatible 423 public <T> T[] shuffle(T[] elements) 424 { 425 int n = elements.length; 426 T[] array = Arrays.copyOf(elements, n); 427 for (int i = 0; i < n; i++) 428 { 429 int r = i + nextInt(n - i); 430 T t = array[r]; 431 array[r] = array[i]; 432 array[i] = t; 433 } 434 return array; 435 } 436 437 /** 438 * Shuffle an array using the "inside-out" Fisher-Yates algorithm. DO NOT give the same array for both elements and 439 * dest, since the prior contents of dest are rearranged before elements is used, and if they refer to the same 440 * array, then you can end up with bizarre bugs where one previously-unique item shows up dozens of times. If 441 * possible, create a new array with the same length as elements and pass it in as dest; the returned value can be 442 * assigned to whatever you want and will have the same items as the newly-formed array. 443 * <br> 444 * https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm 445 * @param elements an array of T; will not be modified 446 * @param <T> can be any non-primitive type. 447 * @param dest Where to put the shuffle. If it does not have the same length as {@code elements}, this will use the 448 * randomPortion method of this class to fill the smaller dest. MUST NOT be the same array as elements! 449 * @return {@code dest} after modifications 450 */ 451 /* This method has this prototype to be compatible with GWT. */ 452 public <T> T[] shuffle(T[] elements, T[] dest) 453 { 454 if (dest.length != elements.length) 455 return randomPortion(elements, dest); 456 for (int i = 0; i < elements.length; i++) 457 { 458 int r = nextInt(i + 1); 459 if(r != i) 460 dest[i] = dest[r]; 461 dest[r] = elements[i]; 462 } 463 return dest; 464 } 465 466 /** 467 * Shuffles a {@link Collection} of T using the Fisher-Yates algorithm and returns an ArrayList of T. 468 * @param elements a Collection of T; will not be modified 469 * @param <T> can be any non-primitive type. 470 * @return a shuffled ArrayList containing the whole of elements in pseudo-random order. 471 */ 472 public <T> ArrayList<T> shuffle(Collection<T> elements) 473 { 474 ArrayList<T> al = new ArrayList<>(elements); 475 int n = al.size(); 476 for (int i = 0; i < n; i++) 477 { 478 Collections.swap(al, i + nextInt(n - i), i); 479 } 480 return al; 481 } 482 483 /** 484 * Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as 485 * it can, and then returns output. Will only use a given position in the given data at most once; does this by 486 * generating random indices for data's elements, but only as much as needed, assigning the copied section to output 487 * and not modifying data. 488 * <br> 489 * Based on http://stackoverflow.com/a/21460179 , credit to Vincent van der Weele; modifications were made to avoid 490 * copying or creating a new generic array (a problem on GWT). 491 * @param data an array of T; will not be modified. 492 * @param output an array of T that will be overwritten; should always be instantiated with the portion length 493 * @param <T> can be any non-primitive type. 494 * @return an array of T that has length equal to output's length and may contain unchanged elements (null if output 495 * was empty) if data is shorter than output 496 */ 497 public <T> T[] randomPortion(T[] data, T[] output) 498 { 499 int length = data.length; 500 int[] mapping = new int[length]; 501 for (int i = 0; i < length; i++) { 502 mapping[i] = i; 503 } 504 505 for (int i = 0; i < output.length && length > 0; i++) { 506 int r = nextInt(length); 507 508 output[i] = data[mapping[r]]; 509 510 mapping[r] = length-1; 511 length--; 512 } 513 514 return output; 515 } 516 517 /** 518 * Gets a random portion of a List and returns it as a new List. Will only use a given position in the given 519 * List at most once; does this by shuffling a copy of the List and getting a section of it. 520 * @param data a List of T; will not be modified. 521 * @param count the non-negative number of elements to randomly take from data 522 * @param <T> can be any non-primitive type 523 * @return a List of T that has length equal to the smaller of count or data.length 524 */ 525 public <T> List<T> randomPortion(List<T> data, int count) 526 { 527 return shuffle(data).subList(0, Math.min(count, data.size())); 528 } 529 530 /** 531 * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements. 532 * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative). 533 * @param start the start of the range of numbers to potentially use (inclusive) 534 * @param end the end of the range of numbers to potentially use (exclusive) 535 * @param count the total number of elements to use; will be less if the range is smaller than count 536 * @return an int array that contains at most one of each number in the range 537 */ 538 public int[] randomRange(int start, int end, int count) 539 { 540 if(end <= start || start < 0) 541 return new int[0]; 542 543 int n = end - start; 544 int[] data = new int[n]; 545 546 for (int e = start, i = 0; e < end; e++) { 547 data[i++] = e; 548 } 549 550 for (int i = 0; i < n; i++) 551 { 552 int r = i + nextInt(n - i); 553 int t = data[r]; 554 data[r] = data[i]; 555 data[i] = t; 556 } 557 int[] array = new int[Math.min(count, n)]; 558 System.arraycopy(data, 0, array, 0, Math.min(count, n)); 559 return array; 560 } 561 562 /** 563 * @return a value from the gaussian distribution 564 */ 565 public synchronized double nextGaussian() { 566 if (haveNextNextGaussian) { 567 haveNextNextGaussian = false; 568 return nextNextGaussian; 569 } else { 570 double v1, v2, s; 571 do { 572 v1 = 2 * nextDouble() - 1; // between -1 and 1 573 v2 = 2 * nextDouble() - 1; // between -1 and 1 574 s = v1 * v1 + v2 * v2; 575 } while (s >= 1 || s == 0); 576 double multiplier = Math.sqrt(-2 * Math.log(s) / s); 577 nextNextGaussian = v2 * multiplier; 578 haveNextNextGaussian = true; 579 return v1 * multiplier; 580 } 581 } 582 583 /** 584 * This returns a maximum of 0.9999999999999999 because that is the largest 585 * Double value that is less than 1.0 586 * 587 * @return a value between 0 (inclusive) and 0.9999999999999999 (inclusive) 588 */ 589 public double nextDouble() { 590 return (random.nextLong() & 0x1fffffffffffffL) * DOUBLE_UNIT; 591 // consider changing to this in a future version; it will break compatibility but should be fast/correct 592 //return Double.longBitsToDouble(0x3FFL << 52 | random.nextLong() >>> 12) - 1.0; 593 594 } 595 596 /** 597 * This returns a random double between 0.0 (inclusive) and max (exclusive). 598 * 599 * @return a value between 0 (inclusive) and max (exclusive) 600 */ 601 public double nextDouble(double max) { 602 return nextDouble() * max; 603 } 604 605 /** 606 * This returns a maximum of 0.99999994 because that is the largest Float 607 * value that is less than 1.0f 608 * 609 * @return a value between 0 (inclusive) and 0.99999994 (inclusive) 610 */ 611 public float nextFloat() { 612 return next(24) * FLOAT_UNIT; 613 } 614 615 /** 616 * Get a random bit of state, interpreted as true or false with approximately equal likelihood. 617 * @return a random boolean. 618 */ 619 public boolean nextBoolean() { 620 return next(1) != 0; 621 } 622 623 /** 624 * Get a random long between Long.MIN_VALUE to Long.MAX_VALUE (both inclusive). 625 * @return a 64-bit random long. 626 */ 627 public long nextLong() { 628 return random.nextLong(); 629 } 630 631 /** 632 * Returns a random long below the given bound, or 0 if the bound is 0 or 633 * negative. 634 * 635 * @param bound the upper bound (exclusive) 636 * @return the found number 637 */ 638 public long nextLong( final long bound ) { 639 if ( bound <= 0 ) return 0; 640 long threshold = (0x7fffffffffffffffL - bound + 1) % bound; 641 for (;;) { 642 long bits = random.nextLong() & 0x7fffffffffffffffL; 643 if (bits >= threshold) 644 return bits % bound; 645 } 646 } 647 /** 648 * Returns a random integer below the given bound, or 0 if the bound is 0 or 649 * negative. 650 * 651 * @param bound the upper bound (exclusive) 652 * @return the found number 653 */ 654 public int nextInt(final int bound) { 655 if ( bound <= 0 ) return 0; 656 int threshold = (0x7fffffff - bound + 1) % bound; 657 for (;;) { 658 int bits = random.next(31); 659 if (bits >= threshold) 660 return bits % bound; 661 } 662 } 663 /** 664 * Get a random integer between Integer.MIN_VALUE to Integer.MAX_VALUE (both inclusive). 665 * @return a 32-bit random int. 666 */ 667 public int nextInt() { 668 return next(32); 669 } 670 671 /** 672 * Get up to 32 bits (inclusive) of random state from the RandomnessSource. 673 * @param bits 1 to 32 674 * @return a random number that fits in the specified number of bits. 675 */ 676 public int next(int bits) { 677 return random.next(bits); 678 } 679 680 public RandomnessSource getRandomness() { 681 return random; 682 } 683 684 public void setRandomness(RandomnessSource random) { 685 this.random = random; 686 } 687 688 /** 689 * Creates a copy of this RNG; it will generate the same random numbers, given the same calls in order, as this RNG 690 * at the point copy() is called. The copy will not share references with this RNG. 691 * @return a copy of this RNG 692 */ 693 public RNG copy() 694 { 695 return new RNG(random.copy()); 696 } 697 698 @Override 699 public String toString() { 700 return "RNG with Randomness Source " + random; 701 } 702}