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}