001package squidpony.squidmath; 002 003import squidpony.StringKit; 004import squidpony.annotation.GwtIncompatible; 005 006import java.util.*; 007 008/** 009 * An RNG variant that has 16 possible grades of value it can produce and shuffles them like a deck of cards. 010 * It repeats grades of value, but not exact values, every 16 numbers requested from it. Grades go in increments of 011 * 0.0625 from 0.0 to 0.9375, and are added to a random double less than 0.0625 to get the random number for that 012 * grade. 013 * <p> 014 * You can get values from this generator with: {@link #nextDouble()}, {@link #nextInt()}, 015 * {@link #nextLong()}, and the bounded variants on each of those. 016 * 017 * Created by Tommy Ettinger on 5/2/2015. 018 */ 019public class DeckRNG extends StatefulRNG { 020 private static final long serialVersionUID = 7828346657944720807L; 021 private int step; 022 private long lastShuffledState; 023 private double[] baseDeck = new double[]{0.0, 0.0625, 0.125, 0.1875, 0.25, 0.3125, 0.375, 0.4375, 024 0.5, 0.5625, 0.625, 0.6875, 0.75, 0.8125, 0.875, 0.9375}, 025 deck = new double[16]; 026 027 /** 028 * Constructs a DeckRNG with a pseudo-random seed from Math.random(). 029 */ 030 public DeckRNG() 031 { 032 this((long)(Math.random() * ((1L << 50) - 1))); 033 } 034 /** 035 * Construct a new DeckRNG with the given seed. 036 * 037 * @param seed used to seed the default RandomnessSource. 038 */ 039 public DeckRNG(final long seed) { 040 lastShuffledState = seed; 041 random = new LightRNG(seed); 042 step = 0; 043 } 044 045 /** 046 * String-seeded constructor uses the hash of the String as a seed for LightRNG, which is of high quality, but low 047 * period (which rarely matters for games), and has good speed and tiny state size. 048 * 049 * @param seedString a String to use as a seed; will be hashed in a uniform way across platforms. 050 */ 051 public DeckRNG(String seedString) { 052 this(CrossHash.hash(seedString)); 053 } 054 /** 055 * Seeds this DeckRNG using the RandomnessSource it is given. Does not assign the RandomnessSource to any fields 056 * that would affect future pseudo-random number generation. 057 * @param random will be used to generate a new seed, but will not be assigned as this object's RandomnessSource 058 */ 059 public DeckRNG(RandomnessSource random) { 060 this(random.nextLong()); 061 062 } 063 064 /** 065 * Generate a random double, altering the result if recently generated results have been leaning 066 * away from this class' fairness value. 067 * @return a double between 0.0 (inclusive) and 1.0 (exclusive) 068 */ 069 @Override 070 public double nextDouble() { 071 if(step == 0) 072 shuffleInPlace(deck); 073 double gen = deck[step++]; 074 step %= 16; 075 return gen; 076 } 077 078 /** 079 * This returns a random double between 0.0 (inclusive) and max (exclusive). 080 * 081 * @return a value between 0 (inclusive) and max (exclusive) 082 */ 083 @Override 084 public double nextDouble(double max) { 085 return nextDouble() * max; 086 } 087 088 /** 089 * Returns a value from a even distribution from min (inclusive) to max 090 * (exclusive). 091 * 092 * @param min the minimum bound on the return value (inclusive) 093 * @param max the maximum bound on the return value (exclusive) 094 * @return the found value 095 */ 096 @Override 097 public double between(double min, double max) { 098 return min + (max - min) * nextDouble(); 099 } 100 101 /** 102 * Returns a value between min (inclusive) and max (exclusive). 103 * 104 * The inclusive and exclusive behavior is to match the behavior of the 105 * similar method that deals with floating point values. 106 * 107 * @param min the minimum bound on the return value (inclusive) 108 * @param max the maximum bound on the return value (exclusive) 109 * @return the found value 110 */ 111 @Override 112 public int between(int min, int max) { 113 return nextInt(max - min) + min; 114 } 115 116 /** 117 * Returns the average of a number of randomly selected numbers from the 118 * provided range, with min being inclusive and max being exclusive. It will 119 * sample the number of times passed in as the third parameter. 120 * 121 * The inclusive and exclusive behavior is to match the behavior of the 122 * similar method that deals with floating point values. 123 * 124 * This can be used to weight RNG calls to the average between min and max. 125 * 126 * @param min the minimum bound on the return value (inclusive) 127 * @param max the maximum bound on the return value (exclusive) 128 * @param samples the number of samples to take 129 * @return the found value 130 */ 131 @Override 132 public int betweenWeighted(int min, int max, int samples) { 133 int sum = 0; 134 for (int i = 0; i < samples; i++) { 135 sum += between(min, max); 136 } 137 138 return Math.round((float) sum / samples); 139 } 140 141 /** 142 * Returns a random element from the provided array and maintains object 143 * type. 144 * 145 * @param <T> the type of the returned object 146 * @param array the array to get an element from 147 * @return the randomly selected element 148 */ 149 @Override 150 public <T> T getRandomElement(T[] array) { 151 if (array.length < 1) { 152 return null; 153 } 154 return array[nextInt(array.length)]; 155 } 156 157 /** 158 * Returns a random element from the provided list. If the list is empty 159 * then null is returned. 160 * 161 * @param <T> the type of the returned object 162 * @param list the list to get an element from 163 * @return the randomly selected element 164 */ 165 @Override 166 public <T> T getRandomElement(List<T> list) { 167 if (list.size() <= 0) { 168 return null; 169 } 170 return list.get(nextInt(list.size())); 171 } 172 173 /** 174 * Returns a random element from the provided ShortSet. If the set is empty 175 * then an exception is thrown. 176 * 177 * <p> 178 * Requires iterating through a random amount of the elements in set, so performance depends on the size of set but 179 * is likely to be decent. This is mostly meant for internal use, the same as ShortSet. 180 * </p> 181 * @param set the ShortSet to get an element from 182 * @return the randomly selected element 183 */ 184 public short getRandomElement(ShortSet set) { 185 if (set.size <= 0) { 186 throw new UnsupportedOperationException("ShortSet cannot be empty when getting a random element"); 187 } 188 int n = nextInt(set.size); 189 short s = 0; 190 ShortSet.ShortSetIterator ssi = set.iterator(); 191 while (n-- >= 0 && ssi.hasNext) 192 s = ssi.next(); 193 ssi.reset(); 194 return s; 195 } 196 197 /** 198 * Returns a random element from the provided Collection, which should have predictable iteration order if you want 199 * predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection 200 * (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted 201 * Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement 202 * Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can 203 * pass the keys or values. If coll is empty, returns null. 204 * 205 * <p> 206 * Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is 207 * likely to be decent, as long as iteration isn't unusually slow. This replaces {@code getRandomElement(Queue)}, 208 * since Queue implements Collection and the older Queue-using implementation was probably less efficient. 209 * </p> 210 * @param <T> the type of the returned object 211 * @param coll the Collection to get an element from; remember, Map does not implement Collection 212 * @return the randomly selected element 213 */ 214 public <T> T getRandomElement(Collection<T> coll) { 215 if (coll.size() <= 0) { 216 return null; 217 } 218 int n = nextInt(coll.size()); 219 T t = null; 220 Iterator<T> it = coll.iterator(); 221 while (n-- >= 0 && it.hasNext()) 222 t = it.next(); 223 return t; 224 } 225 226 227 /** 228 * @return a value from the gaussian distribution 229 */ 230 @Override 231 public synchronized double nextGaussian() { 232 if (haveNextNextGaussian) { 233 haveNextNextGaussian = false; 234 return nextNextGaussian; 235 } else { 236 double v1, v2, s; 237 do { 238 v1 = 2 * nextDouble() - 1; // between -1 and 1 239 v2 = 2 * nextDouble() - 1; // between -1 and 1 240 s = v1 * v1 + v2 * v2; 241 } while (s >= 1 || s == 0); 242 double multiplier = Math.sqrt(-2 * Math.log(s) / s); 243 nextNextGaussian = v2 * multiplier; 244 haveNextNextGaussian = true; 245 return v1 * multiplier; 246 } 247 } 248 /** 249 * Returns a random integer below the given bound, or 0 if the bound is 0 or 250 * negative. Affects the current fortune. 251 * 252 * @param bound the upper bound (exclusive) 253 * @return the found number 254 */ 255 @Override 256 public int nextInt(int bound) { 257 if (bound <= 0) { 258 return 0; 259 } 260 261 return (int)(nextDouble() * bound); 262 } 263 264 /** 265 * Returns a random integer, which may be positive or negative. 266 * @return A random int 267 */ 268 @Override 269 public int nextInt() { 270 return (int)((nextDouble() * 2.0 - 1.0) * 0x7FFFFFFF); 271 } 272 273 /** 274 * Returns a random long, which may be positive or negative. 275 * @return A random long 276 */ 277 @Override 278 public long nextLong() { 279 double nx = nextDouble(); 280 return (long)((nx * 2.0 - 1.0) * 0x7FFFFFFFFFFFFFFFL); 281 } 282 283 /** 284 * Returns a random long below the given bound, or 0 if the bound is 0 or 285 * negative. 286 * 287 * @param bound the upper bound (exclusive) 288 * @return the found number 289 */ 290 @Override 291 public long nextLong(long bound) { 292 if (bound <= 0) { 293 return 0; 294 } 295 double nx = nextDouble(); 296 return (long)(nx * bound); 297 //return ((long)(nx * bound)) ^ (long)((nx * 0xFFFFFL) % bound) ^ (long)((nx * 0xFFFFF00000L) % bound); 298 } 299 /** 300 * 301 * @param bits the number of bits to be returned 302 * @return a random int of the number of bits specified. 303 */ 304 @Override 305 public int next(int bits) { 306 if(bits <= 0) 307 return 0; 308 if(bits > 32) 309 bits = 32; 310 return (int)(nextDouble() * (1L << bits)); 311 312 } 313 314 @Override 315 public Random asRandom() { 316 if(ran == null) 317 { 318 ran = new CustomRandom(new LightRNG(getState())); 319 } 320 return ran; 321 } 322 323 @Override 324 @GwtIncompatible 325 public <T> List<T> randomRotation(List<T> l) { 326 return super.randomRotation(l); 327 } 328 329 @Override 330 public <T> Iterable<T> getRandomStartIterable(List<T> list) { 331 return super.getRandomStartIterable(list); 332 } 333 334 335 /** 336 * Returns a value between min (inclusive) and max (exclusive). 337 * <p/> 338 * The inclusive and exclusive behavior is to match the behavior of the 339 * similar method that deals with floating point values. 340 * 341 * @param min the minimum bound on the return value (inclusive) 342 * @param max the maximum bound on the return value (exclusive) 343 * @return the found value 344 */ 345 @Override 346 public long between(long min, long max) { 347 return nextLong(max - min) + min; 348 } 349 350 /* 351 * Shuffle an array using the Fisher-Yates algorithm. 352 * 353 * @param elements an array of T; will not be modified 354 * @return a shuffled copy of elements 355 * / 356 @Override 357 @GwtIncompatible 358 public <T> T[] shuffle(T[] elements) { 359 return super.shuffle(elements); 360 } 361*/ 362 /** 363 * Shuffle an array using the Fisher-Yates algorithm. 364 * 365 * @param elements an array of T; will not be modified 366 * @param dest Where to put the shuffle. It MUST have the same length as {@code elements} 367 * @return {@code dest} 368 * @throws IllegalStateException If {@code dest.length != elements.length} 369 */ 370 @Override 371 public <T> T[] shuffle(T[] elements, T[] dest) { 372 return super.shuffle(elements, dest); 373 } 374 375 @Override 376 public <T> ArrayList<T> shuffle(Collection<T> elements) { 377 return super.shuffle(elements); 378 } 379 380 @Override 381 public float nextFloat() { 382 return (float)nextDouble(); 383 } 384 385 @Override 386 public boolean nextBoolean() { 387 return nextDouble() >= 0.5; 388 } 389 390 @Override 391 public RandomnessSource getRandomness() { 392 return random; 393 } 394 395 /** 396 * Reseeds this DeckRNG using the RandomnessSource it is given. Does not assign the RandomnessSource to any fields 397 * that would affect future pseudo-random number generation. 398 * @param random will be used to generate a new seed, but will not be assigned as this object's RandomnessSource 399 */ 400 @Override 401 public void setRandomness(RandomnessSource random) { 402 setState(((long)random.next(32) << 32) | random.next(32)); 403 404 } 405 406 /** 407 * Creates a copy of this DeckRNG; it will generate the same random numbers, given the same calls in order, as 408 * this DeckRNG at the point copy() is called. The copy will not share references with this DeckRNG. 409 * 410 * @return a copy of this DeckRNG 411 */ 412 public RNG copy() 413 { 414 DeckRNG next = new DeckRNG(lastShuffledState); 415 next.random = random.copy(); 416 System.arraycopy(deck, 0, next.deck, 0, deck.length); 417 next.step = step; 418 return next; 419 } 420 421 /** 422 * Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as 423 * it can, and then returns output. Will only use a given position in the given data at most once; does this by 424 * shuffling a copy of data and getting a section of it that matches the length of output. 425 * 426 * Based on http://stackoverflow.com/a/21460179 , credit to Vincent van der Weele; modifications were made to avoid 427 * copying or creating a new generic array (a problem on GWT). 428 * @param data an array of T; will not be modified. 429 * @param output an array of T that will be overwritten; should always be instantiated with the portion length 430 * @param <T> can be any non-primitive type. 431 * @return an array of T that has length equal to output's length and may contain null elements if output is shorter 432 * than data 433 */ 434 @Override 435 public <T> T[] randomPortion(T[] data, T[] output) { 436 return super.randomPortion(data, output); 437 } 438 439 /** 440 * Gets a random portion of a List and returns it as a new List. Will only use a given position in the given 441 * List at most once; does this by shuffling a copy of the List and getting a section of it. 442 * 443 * @param data a List of T; will not be modified. 444 * @param count the non-negative number of elements to randomly take from data 445 * @return a List of T that has length equal to the smaller of count or data.length 446 */ 447 @Override 448 public <T> List<T> randomPortion(List<T> data, int count) { 449 return super.randomPortion(data, count); 450 } 451 452 /** 453 * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements. 454 * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative). 455 * 456 * @param start the start of the range of numbers to potentially use (inclusive) 457 * @param end the end of the range of numbers to potentially use (exclusive) 458 * @param count the total number of elements to use; will be less if the range is smaller than count 459 * @return an int array that contains at most one of each number in the range 460 */ 461 @Override 462 public int[] randomRange(int start, int end, int count) { 463 return super.randomRange(start, end, count); 464 } 465 466 /** 467 * Shuffle an array using the Fisher-Yates algorithm. 468 * @param array an array of double; WILL be modified 469 */ 470 private void shuffleInPlace(double[] array) 471 { 472 lastShuffledState = ((LightRNG)random).getState(); 473 int n = array.length; 474 System.arraycopy(baseDeck, 0, array, 0, n); 475 for (int i = 0; i < n; i++) 476 { 477 int r = i + ((LightRNG)random).nextInt(n - i); 478 double t = array[r]; 479 array[r] = array[i]; 480 array[i] =((LightRNG)random).nextDouble(0.0625) + t; 481 } 482 } 483 484 /** 485 * Get a long that can be used to reproduce the sequence of random numbers this object will generate starting now. 486 * 487 * @return a long that can be used as state. 488 */ 489 @Override 490 public long getState() { 491 return lastShuffledState; 492 } 493 494 /** 495 * Sets the state of the random number generator to a given long, which will alter future random numbers this 496 * produces based on the state. Setting the state always causes the "deck" of random grades to be shuffled. 497 * 498 * @param state any long (this can tolerate states of 0) 499 */ 500 @Override 501 public void setState(long state) { 502 ((LightRNG)random).setState(state); 503 shuffleInPlace(deck); 504 step = 0; 505 506 } 507 508 @Override 509 public String toString() { 510 return "DeckRNG{state: 0x" + StringKit.hex(lastShuffledState) + "L}"; 511 } 512 513 public int getStep() { 514 return step; 515 } 516 517 public void setStep(int step) { 518 this.step = step; 519 } 520}