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}