001package squidpony.squidmath;
002
003import squidpony.annotation.GwtIncompatible;
004
005import java.util.*;
006
007/**
008 * An alteration to a RandomnessSource that attempts to produce values that are perceived as fair to an imperfect user.
009 * <p>
010 * This takes a RandomnessSource, defaulting to a LightRNG, and uses it to generate random values, but tracks the total
011 * and compares it to the potential total of a generator of only numbers with a desired value (default 0.54,
012 * so it compares against a sequence of all 0.54). If the current generated total is too high or low compared to the
013 * desired total, the currently used seed is possibly changed, the generated number is moved in the direction of the
014 * desired fairness, and it returns that instead of the number that would have pushed the current generated total
015 * beyond the desired threshold. The new number, if one is changed, will always be closer to the desired fairness.
016 * This is absolutely insecure for cryptographic purposes, but should seem more "fair" to a player than a
017 * random number generator that seeks to be truly random.
018 * You can create multiple DharmaRNG objects with different fairness values and seeds, and use favorable generators
019 * (with fairness greater than 0.54) for characters that need an easier time, or unfavorable generators if you want
020 * the characters that use that RNG to be impeded somewhat.
021 * The name comes from the Wheel of Dharma.
022 * This class currently will have a slight bias toward lower numbers with many RNGs unless fairness is tweaked; 0.54
023 * can be used as a stand-in because 0.5 leans too low.
024 *
025 * <p>
026 * You can get values from this generator with: {@link #nextDouble()}, {@link #nextInt()},
027 *   {@link #nextLong()}, and the bounded variants on each of those.
028 * <p>
029 * You can alter the tracking information or requested fairness with {@link #resetFortune()},
030 *   {@link #setFairness(double)}, and {@link #getFairness()}.
031 *
032 * Created by Tommy Ettinger on 5/2/2015.
033 */
034public class DharmaRNG extends RNG {
035
036        /** Used to tweak the generator toward high or low values. */
037    private double fairness = 0.54;
038
039    /** Running total for what this has actually produced. */
040    private double produced = 0.0;
041
042    /** Running total for what this would produce if it always produced a value equal to fairness. */
043    private double baseline = 0.0;
044
045        private static final long serialVersionUID = -8919455766853811999L;
046
047    /**
048     * Constructs a DharmaRNG with a pseudo-random seed from Math.random().
049     */
050    public DharmaRNG()
051    {
052        this((long)(Math.random() * ((1L << 50) - 1)));
053    }
054    /**
055     * Construct a new DharmaRNG with the given seed.
056     *
057     * @param seed used to seed the default RandomnessSource.
058     */
059    public DharmaRNG(final long seed) {
060        super(seed);
061    }
062
063    /**
064     * Construct a new DharmaRNG with the given seed.
065     *
066     * @param seed used to seed the default RandomnessSource.
067     * @param fairness the desired fairness metric, which must be between 0.0 and 1.0
068     */
069    public DharmaRNG(final long seed, final double fairness) {
070        super(seed);
071        if(fairness < 0.0 || fairness >= 1.0)
072            this.fairness = 0.54;
073        else
074            this.fairness = fairness;
075    }
076
077
078    /**
079     * String-seeded constructor; uses a platform-independent hash of the String (it does not use String.hashCode) as a
080     * seed for LightRNG, which is of high quality, but low period (which rarely matters for games), and has good speed,
081     * tiny state size, and excellent 64-bit number generation.
082     *
083     * @param seedString a String as a seed
084     */
085    public DharmaRNG(String seedString) {
086        super(seedString);
087    }
088
089
090    /**
091     * String-seeded constructor; uses a platform-independent hash of the String (it does not use String.hashCode) as a
092     * seed for LightRNG, which is of high quality, but low period (which rarely matters for games), and has good speed,
093     * tiny state size, and excellent 64-bit number generation.
094     *
095     * @param seedString a String as a seed
096     */
097    public DharmaRNG(String seedString, double fairness) {
098        super(seedString);
099        if(fairness < 0.0 || fairness >= 1.0)
100            this.fairness = 0.54;
101        else
102            this.fairness = fairness;
103
104    }
105    /**
106     * Construct a new DharmaRNG with the given seed.
107     *
108     * @param rs the implementation used to generate random bits.
109     */
110    public DharmaRNG(final RandomnessSource rs) {
111        super(rs);
112    }
113    /**
114     * Construct a new DharmaRNG with the given seed.
115     *
116     * @param rs the implementation used to generate random bits.
117     * @param fairness the desired fairness metric, which must be between 0.0 and 1.0
118     */
119    public DharmaRNG(final RandomnessSource rs, final double fairness) {
120        super(rs);
121        if(fairness < 0.0 || fairness >= 1.0)
122            this.fairness = 0.54;
123        else
124            this.fairness = fairness;
125    }
126
127    /**
128     * Generate a random double, altering the result if recently generated results have been leaning
129     * away from this class' fairness value.
130     * @return a double between 0.0 (inclusive) and 1.0 (exclusive)
131     */
132    @Override
133    public double nextDouble() {
134        double gen = random.nextLong() * DOUBLE_UNIT;
135        /*if(Math.abs((produced + gen) - (baseline + fairness)) > 1.5) {
136            //do some reseeding here if possible
137        }*/
138        if(Math.abs((produced + gen) - (baseline + fairness)) > 0.5)
139        {
140            gen = (gen + fairness) / 2.0;
141            produced *= 0.5;
142            baseline *= 0.5;
143            produced += gen;
144            baseline += fairness;
145            return gen;
146        }
147        else
148        {
149            produced += gen;
150            baseline += fairness;
151            return gen;
152        }
153    }
154
155    /**
156     * This returns a random double between 0.0 (inclusive) and max (exclusive).
157     *
158     * @return a value between 0 (inclusive) and max (exclusive)
159     */
160    @Override
161    public double nextDouble(double max) {
162        return super.nextDouble(max);
163    }
164
165    /**
166     * Returns a value from a even distribution from min (inclusive) to max
167     * (exclusive).
168     *
169     * @param min the minimum bound on the return value (inclusive)
170     * @param max the maximum bound on the return value (exclusive)
171     * @return the found value
172     */
173    @Override
174    public double between(double min, double max) {
175        return super.between(min, max);
176    }
177
178    /**
179     * Returns a value between min (inclusive) and max (exclusive).
180     *
181     * The inclusive and exclusive behavior is to match the behavior of the
182     * similar method that deals with floating point values.
183     *
184     * @param min the minimum bound on the return value (inclusive)
185     * @param max the maximum bound on the return value (exclusive)
186     * @return the found value
187     */
188    @Override
189    public int between(int min, int max)
190    {
191        return super.between(min, max);
192    }
193
194    /**
195     * Returns the average of a number of randomly selected numbers from the
196     * provided range, with min being inclusive and max being exclusive. It will
197     * sample the number of times passed in as the third parameter.
198     *
199     * The inclusive and exclusive behavior is to match the behavior of the
200     * similar method that deals with floating point values.
201     *
202     * This can be used to weight RNG calls to the average between min and max.
203     *
204     * @param min the minimum bound on the return value (inclusive)
205     * @param max the maximum bound on the return value (exclusive)
206     * @param samples the number of samples to take
207     * @return the found value
208     */
209    @Override
210    public int betweenWeighted(int min, int max, int samples) {
211        return super.betweenWeighted(min, max, samples);
212    }
213
214    /**
215     * Returns a random element from the provided array and maintains object
216     * type.
217     *
218     * @param <T> the type of the returned object
219     * @param array the array to get an element from
220     * @return the randomly selected element
221     */
222    @Override
223    public <T> T getRandomElement(T[] array) {
224        return super.getRandomElement(array);
225    }
226
227    /**
228     * Returns a random element from the provided list. If the list is empty
229     * then null is returned.
230     *
231     * @param <T> the type of the returned object
232     * @param list the list to get an element from
233     * @return the randomly selected element
234     */
235    @Override
236    public <T> T getRandomElement(List<T> list) {
237        return super.getRandomElement(list);
238    }
239
240    /**
241     * Returns a random element from the provided ShortSet. If the set is empty
242     * then an exception is thrown.
243     *
244     * <p>
245     * Requires iterating through a random amount of the elements in set, so performance depends on the size of set but
246     * is likely to be decent. This is mostly meant for internal use, the same as ShortSet.
247     * </p>
248     * @param set the ShortSet to get an element from
249     * @return the randomly selected element
250     */
251    public short getRandomElement(ShortSet set) {
252        return super.getRandomElement(set);
253    }
254
255    /**
256     * Returns a random element from the provided Collection, which should have predictable iteration order if you want
257     * predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection
258     * (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted
259     * Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement
260     * Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can
261     * pass the keys or values. If coll is empty, returns null.
262     *
263     * <p>
264     * Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is
265     * likely to be decent, as long as iteration isn't unusually slow. This replaces {@code getRandomElement(Queue)},
266     * since Queue implements Collection and the older Queue-using implementation was probably less efficient.
267     * </p>
268     * @param <T> the type of the returned object
269     * @param coll the Collection to get an element from; remember, Map does not implement Collection
270     * @return the randomly selected element
271     */
272    public <T> T getRandomElement(Collection<T> coll) {
273        return super.getRandomElement(coll);
274    }
275
276    /**
277     * @return a value from the gaussian distribution
278     */
279    @Override
280    public synchronized double nextGaussian() {
281        return super.nextGaussian();
282    }
283    /**
284     * Returns a random integer below the given bound, or 0 if the bound is 0 or
285     * negative. Affects the current fortune.
286     *
287     * @param bound the upper bound (exclusive)
288     * @return the found number
289     */
290    @Override
291    public int nextInt(int bound) {
292        if (bound <= 0) {
293            return 0;
294        }
295
296        return (int)(nextDouble() * bound);
297    }
298
299    /**
300     * Returns a random integer, which may be positive or negative. Affects the current fortune.
301     * @return A random int
302     */
303    @Override
304    public int nextInt() {
305        return (int)((nextDouble() - 0.5) * 2.0 * 0x7FFFFFFF);
306    }
307
308    /**
309     * Returns a random long, which may be positive or negative. Affects the current fortune.
310     * @return A random long
311     */
312    @Override
313    public long nextLong() {
314        return (long)((nextDouble() - 0.5) * 2.0 * 0x7FFFFFFFFFFFFFFFL);
315    }
316
317    /**
318     * Returns a random long below the given bound, or 0 if the bound is 0 or
319     * negative.
320     *
321     * @param bound the upper bound (exclusive)
322     * @return the found number
323     */
324    @Override
325        public long nextLong(long bound) {
326        if (bound <= 0) {
327            return 0;
328        }
329        return (long)(nextDouble() * bound);
330    }
331    /**
332     * Gets the measure that this class uses for RNG fairness, defaulting to 0.54 (always between 0.0 and 1.0).
333     * @return the current fairness metric.
334     */
335    public double getFairness() {
336        return fairness;
337    }
338
339    /**
340     * Sets the measure that this class uses for RNG fairness, which must always be between 0.0 and 1.0, and will be
341     * set to 0.54 if an invalid value is passed.
342     * @param fairness the desired fairness metric, which must be 0.0 &lt;= fairness &lt; 1.0
343     */
344    public void setFairness(double fairness) {
345        if(fairness < 0.0 || fairness >= 1.0)
346            this.fairness = 0.54;
347        else
348            this.fairness = fairness;
349    }
350
351    /**
352     * Gets the status of the fortune used when calculating fairness adjustments.
353     * @return the current value used to determine whether the results should be adjusted toward fairness.
354     */
355    public double getFortune()
356    {
357        return Math.abs(produced - baseline);
358    }
359
360    /**
361     * Resets the stored history this RNG uses to try to ensure fairness.
362     */
363    public void resetFortune()
364    {
365        produced = 0.0;
366        baseline = 0.0;
367    }
368    /**
369     *
370     * @param bits the number of bits to be returned
371     * @return a random int of the number of bits specified.
372     */
373    @Override
374    public int next(int bits) {
375        if(bits <= 0)
376            return 0;
377        if(bits > 32)
378            bits = 32;
379        return (int)(nextDouble() * (1l << bits));
380
381    }
382
383    @Override
384    public Random asRandom() {
385        return super.asRandom();
386    }
387
388    @Override
389    @GwtIncompatible
390    public <T> List<T> randomRotation(List<T> l) {
391        return super.randomRotation(l);
392    }
393
394    @Override
395    public <T> Iterable<T> getRandomStartIterable(List<T> list) {
396        return super.getRandomStartIterable(list);
397    }
398/*
399    @Override
400    @GwtIncompatible
401    public <T> T[] shuffle(T[] elements) {
402        return super.shuffle(elements);
403    }
404*/
405    @Override
406    public <T> T[] shuffle(T[] elements, T[] dest) {
407        return super.shuffle(elements, dest);
408    }
409
410    @Override
411    public <T> ArrayList<T> shuffle(Collection<T> elements) {
412        return super.shuffle(elements);
413    }
414
415    @Override
416    public float nextFloat() {
417        return (float)nextDouble();
418    }
419
420    @Override
421    public boolean nextBoolean() {
422        return nextDouble() >= 0.5;
423    }
424
425    @Override
426    public RandomnessSource getRandomness() {
427        return random;
428    }
429
430    @Override
431    public void setRandomness(RandomnessSource random) {
432        this.random = random;
433    }
434
435    /**
436     * Creates a copy of this DharmaRNG; it will generate the same random numbers, given the same calls in order, as
437     * this DharmaRNG at the point copy() is called. The copy will not share references with this DharmaRNG.
438     *
439     * @return a copy of this DharmaRNG
440     */
441    @Override
442    public RNG copy() {
443        DharmaRNG next = new DharmaRNG(random.copy(), fairness);
444        next.produced = produced;
445        next.baseline = baseline;
446        return next;
447    }
448
449    /**
450     * Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as
451     * it can, and then returns output. Will only use a given position in the given data at most once; does this by
452     * shuffling a copy of data and getting a section of it that matches the length of output.
453     *
454     * Based on http://stackoverflow.com/a/21460179 , credit to Vincent van der Weele; modifications were made to avoid
455     * copying or creating a new generic array (a problem on GWT).
456     * @param data an array of T; will not be modified.
457     * @param output an array of T that will be overwritten; should always be instantiated with the portion length
458     * @param <T> can be any non-primitive type.
459     * @return an array of T that has length equal to output's length and may contain null elements if output is shorter
460     * than data
461     */
462    @Override
463    public <T> T[] randomPortion(T[] data, T[] output) {
464        return super.randomPortion(data, output);
465    }
466
467    /**
468     * Gets a random portion of a List and returns it as a new List. Will only use a given position in the given
469     * List at most once; does this by shuffling a copy of the List and getting a section of it.
470     *
471     * @param data  a List of T; will not be modified.
472     * @param count the non-negative number of elements to randomly take from data
473     * @return a List of T that has length equal to the smaller of count or data.length
474     */
475    @Override
476    public <T> List<T> randomPortion(List<T> data, int count) {
477        return super.randomPortion(data, count);
478    }
479
480    /**
481     * Gets a random subrange of the non-negative ints from start (inclusive) to end (exclusive), using count elements.
482     * May return an empty array if the parameters are invalid (end is less than/equal to start, or start is negative).
483     *
484     * @param start the start of the range of numbers to potentially use (inclusive)
485     * @param end   the end of the range of numbers to potentially use (exclusive)
486     * @param count the total number of elements to use; will be less if the range is smaller than count
487     * @return an int array that contains at most one of each number in the range
488     */
489    @Override
490    public int[] randomRange(int start, int end, int count) {
491        return super.randomRange(start, end, count);
492    }
493
494    @Override
495    public String toString() {
496        return "DharmaRNG{" +
497                "fairness=" + fairness +
498                ", produced=" + produced +
499                ", baseline=" + baseline +
500                "Randomness Source" + random +
501                '}';
502    }
503}