Package squidpony.squidmath

Class AbstractRNG

java.lang.Object
squidpony.squidmath.AbstractRNG
All Implemented Interfaces:
Serializable, IRNG, RandomnessSource
Direct Known Subclasses:
DistributedRNG, GWTRNG, MoonwalkRNG, SilkRNG, TweakRNG
public abstract class AbstractRNG
extends Object
implements IRNG
A helper class for implementing IRNG without so much busy-work. You need to provide implementations for the abstract methods nextInt(), next(int), nextLong(), nextBoolean(), nextDouble(), nextFloat(), copy(), and toSerializable(), many of which may be built off of each other and some of which have sample code in their documentation strings in this class.
Big thanks to smelc for the concept in his hgameshrogue library.
Author:
Tommy Ettinger, smelC
See Also:
Serialized Form

  • Constructor Summary

    Constructors 
    Constructor Description
    AbstractRNG()  

  • Method Summary

    Modifier and Type Method Description
    double between​(double min, double max)
    Returns a value from a uniform distribution from min (inclusive) to max (exclusive).
    int between​(int min, int max)
    Returns a value between min (inclusive) and max (exclusive) as ints.
    long between​(long min, long max)
    Returns a value between min (inclusive) and max (exclusive) as longs.
    abstract IRNG copy()
    Creates a copy of this IRNG; it will generate the same random numbers, given the same calls in order, as this IRNG at the point copy() is called.
    <T> T getRandomElement​(Collection<T> coll)
    Returns a random element from the provided Collection, which should have predictable iteration order if you want predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection (just not predictably in all cases).
    <T> T getRandomElement​(List<T> list)
    Returns a random element from the provided list.
    <T> T getRandomElement​(T[] array)
    Returns a random element from the provided array and maintains object type.
    abstract int next​(int bits)
    Get up to 32 bits (inclusive) of random output; the int this produces will not require more than bits bits to represent.
    abstract boolean nextBoolean()
    Get a random bit of state, interpreted as true or false with approximately equal likelihood.
    abstract double nextDouble()
    Gets a random double between 0.0 inclusive and 1.0 exclusive.
    double nextDouble​(double outer)
    This returns a random double between 0.0 (inclusive) and outer (exclusive).
    abstract float nextFloat()
    Gets a random float between 0.0f inclusive and 1.0f exclusive.
    float nextFloat​(float outer)
    This returns a random float between 0.0f (inclusive) and outer (exclusive).
    abstract int nextInt()
    Get a random integer between Integer.MIN_VALUE to Integer.MAX_VALUE (both inclusive).
    int nextInt​(int bound)
    Returns a random non-negative integer below the given bound, or 0 if the bound is 0 or negative.
    abstract long nextLong()
    Get a random long between Long.MIN_VALUE to Long.MAX_VALUE (both inclusive).
    long nextLong​(long bound)
    Exclusive on bound (which must be positive), with an inner bound of 0.
    int nextSignedInt​(int bound)
    Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), or 0 if the bound is 0.
    long nextSignedLong​(long bound)
    Exclusive on bound (which may be positive or negative), with an inner bound of 0.
    int[] randomOrdering​(int length)
    Generates a random permutation of the range from 0 (inclusive) to length (exclusive).
    int[] randomOrdering​(int length, int[] dest)
    Generates a random permutation of the range from 0 (inclusive) to length (exclusive) and stores it in the dest parameter, avoiding allocations.
    <T> T[] randomPortion​(T[] data, T[] output)
    Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as it can, and then returns output.
    <T> ArrayList<T> shuffle​(Collection<T> elements)
    Shuffles a Collection of T using the Fisher-Yates algorithm and returns an ArrayList of T.
    <T> ArrayList<T> shuffle​(Collection<T> elements, ArrayList<T> buf)
    Shuffles a Collection of T using the Fisher-Yates algorithm and puts it in a buffer.
    <T> T[] shuffle​(T[] elements)
    Shuffle an array using the Fisher-Yates algorithm and returns a shuffled copy, freshly-allocated, without modifying elements.
    <T> T[] shuffle​(T[] elements, T[] dest)
    Shuffle an array using the Fisher-Yates algorithm.
    <T> List<T> shuffleInPlace​(List<T> elements)
    Shuffles a Collection of T items in-place using the Fisher-Yates algorithm.
    <T> T[] shuffleInPlace​(T[] elements)
    Shuffles an array in-place using the Fisher-Yates algorithm.
    protected static <T> void swap​(T[] arr, int pos1, int pos2)
    Mutates the array arr by switching the contents at pos1 and pos2.
    abstract Serializable toSerializable()
    Gets a view of this IRNG in a way that implements Serializable, which may simply be this IRNG if it implements Serializable as well as IRNG.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

  • Method Details

    • next

      public abstract int next​(int bits)
      Get up to 32 bits (inclusive) of random output; the int this produces will not require more than bits bits to represent.
      Specified by:
      next in interface IRNG
      Specified by:
      next in interface RandomnessSource
      Parameters:
      bits - an int between 1 and 32, both inclusive
      Returns:
      a random number that fits in the specified number of bits

    • nextInt

      public abstract int nextInt()
      Get a random integer between Integer.MIN_VALUE to Integer.MAX_VALUE (both inclusive).
      Specified by:
      nextInt in interface IRNG
      Returns:
      a 32-bit random int.

    • nextInt

      public int nextInt​(int bound)
      Returns a random non-negative integer below the given bound, or 0 if the bound is 0 or negative.
      Specified by:
      nextInt in interface IRNG
      Parameters:
      bound - the upper bound (exclusive)
      Returns:
      the found number

    • nextLong

      public abstract long nextLong()
      Get a random long between Long.MIN_VALUE to Long.MAX_VALUE (both inclusive).
      Specified by:
      nextLong in interface IRNG
      Specified by:
      nextLong in interface RandomnessSource
      Returns:
      a 64-bit random long.

    • nextLong

      public long nextLong​(long bound)
      Exclusive on bound (which must be positive), with an inner bound of 0. If bound is negative or 0 this always returns 0.
      Credit for this method goes to Rafael Baptista's blog for the original idea, and the JDK10 Math class' usage of Karatsuba multiplication for the current algorithm. This method is drastically faster than the previous implementation when the bound varies often (roughly 4x faster, possibly more). It also always gets exactly one random long, so by default it advances the state as much as nextLong(); subclasses can generate two ints instead of one long if they prefer.
      Specified by:
      nextLong in interface IRNG
      Parameters:
      bound - the outer exclusive bound; should be positive, otherwise this always returns 0L
      Returns:
      a random long between 0 (inclusive) and bound (exclusive)

    • nextBoolean

      public abstract boolean nextBoolean()
      Get a random bit of state, interpreted as true or false with approximately equal likelihood.
      Note: This is abstract because some implementations may be best served by using next(int) to get 1 bit, returning next(1) == 1, but others will get much better results with a sign check by calling their choice of nextInt() or nextLong() and returning nextInt() < 0 or nextLong < 0L. For example, an implementation that uses a linear congruential generator without truncating some lower bits will have very-low-period results for the bottom bit (alternating true and false), but perfectly fine results from a sign check. There are tested issues on the bottom (at least 2) bits of XoRoRNG, but again not on a sign check.
      Specified by:
      nextBoolean in interface IRNG
      Returns:
      a random boolean.

    • nextDouble

      public abstract double nextDouble()
      Gets a random double between 0.0 inclusive and 1.0 exclusive. This returns a maximum of 0.9999999999999999 because that is the largest double value that is less than 1.0 .
      This is abstract because some generators may natively work with double or float values, but others may need to convert a long to a double as with (nextLong() & 0x1fffffffffffffL) * 0x1p-53, which is recommended if longs are fast to produce.
      Specified by:
      nextDouble in interface IRNG
      Returns:
      a double between 0.0 (inclusive) and 0.9999999999999999 (inclusive)

    • nextDouble

      public double nextDouble​(double outer)
      This returns a random double between 0.0 (inclusive) and outer (exclusive). The value for outer can be positive or negative. Because of how math on doubles works, there are at most 2 to the 53 values this can return for any given outer bound, and very large values for outer will not necessarily produce all numbers you might expect.
      Specified by:
      nextDouble in interface IRNG
      Parameters:
      outer - the outer exclusive bound as a double; can be negative or positive
      Returns:
      a double between 0.0 (inclusive) and outer (exclusive)

    • nextFloat

      public abstract float nextFloat()
      Gets a random float between 0.0f inclusive and 1.0f exclusive. This returns a maximum of 0.99999994 because that is the largest float value that is less than 1.0f .
      This is abstract because some generators may natively work with double or float values, but others may need to convert an int or long to a float as with (nextInt() & 0xffffff) * 0x1p-24f, (nextLong() & 0xffffffL) * 0x1p-24f, or next(24) * 0x1p-24f, any of which can work when the method they call is high-quality and fast. You probably would want to use nextInt() or next() if your implementation is natively 32-bit and is slower at producing longs, for example.
      Specified by:
      nextFloat in interface IRNG
      Returns:
      a float between 0f (inclusive) and 0.99999994f (inclusive)

    • nextFloat

      public float nextFloat​(float outer)
      This returns a random float between 0.0f (inclusive) and outer (exclusive). The value for outer can be positive or negative. Because of how math on floats works, there are at most 2 to the 24 values this can return for any given outer bound, and very large values for outer will not necessarily produce all numbers you might expect.
      Specified by:
      nextFloat in interface IRNG
      Parameters:
      outer - the outer exclusive bound as a float; can be negative or positive
      Returns:
      a float between 0f (inclusive) and outer (exclusive)

    • nextSignedLong

      public long nextSignedLong​(long bound)
      Exclusive on bound (which may be positive or negative), with an inner bound of 0. If bound is negative this returns a negative long; if bound is positive this returns a positive long. The bound can even be 0, which will cause this to return 0L every time. This uses a biased technique to get numbers from large ranges, but the amount of bias is incredibly small (expected to be under 1/1000 if enough random ranged numbers are requested, which is about the same as an unbiased method that was also considered). It may have noticeable bias if the generator's period is exhausted by only calls to this method. Unlike all unbiased methods, this advances the state by an equivalent to exactly one call to nextLong(), where rejection sampling would sometimes advance by one call, but other times by arbitrarily many more.
      Credit for this method goes to Rafael Baptista's blog for the original idea, and the JDK10 Math class' usage of Hacker's Delight code for the current algorithm. This method is drastically faster than the previous implementation when the bound varies often (roughly 4x faster, possibly more). It also always gets exactly one random long, so by default it advances the state as much as nextLong(); subclasses that are better at generating ints can override this and generate two ints instead of one long that needs separating internally.
      Specified by:
      nextSignedLong in interface IRNG
      Parameters:
      bound - the outer exclusive bound; can be positive or negative
      Returns:
      a random long between 0 (inclusive) and bound (exclusive)

    • nextSignedInt

      public int nextSignedInt​(int bound)
      Returns a random non-negative integer between 0 (inclusive) and the given bound (exclusive), or 0 if the bound is 0. The bound can be negative, which will produce 0 or a negative result.
      Credit goes to Daniel Lemire, http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
      Specified by:
      nextSignedInt in interface IRNG
      Parameters:
      bound - the outer bound (exclusive), can be negative or positive
      Returns:
      the found number

    • between

      public int between​(int min, int max)
      Returns a value between min (inclusive) and max (exclusive) as ints.
      The inclusive and exclusive behavior is to match the behavior of the similar method that deals with floating point values.
      If min and max happen to be the same, min is returned (breaking the exclusive behavior, but it's convenient to do so).
      Specified by:
      between in interface IRNG
      Parameters:
      min - the minimum bound on the return value (inclusive)
      max - the maximum bound on the return value (exclusive)
      Returns:
      the found value

    • between

      public long between​(long min, long max)
      Returns a value between min (inclusive) and max (exclusive) as longs.
      The inclusive and exclusive behavior is to match the behavior of the similar method that deals with floating point values.
      If min and max happen to be the same, min is returned (breaking the exclusive behavior, but it's convenient to do so).
      Specified by:
      between in interface IRNG
      Parameters:
      min - the minimum bound on the return value (inclusive)
      max - the maximum bound on the return value (exclusive)
      Returns:
      the found value

    • between

      public double between​(double min, double max)
      Returns a value from a uniform distribution from min (inclusive) to max (exclusive).
      Specified by:
      between in interface IRNG
      Parameters:
      min - the minimum bound on the return value (inclusive)
      max - the maximum bound on the return value (exclusive)
      Returns:
      the found value

    • getRandomElement

      public <T> T getRandomElement​(T[] array)
      Returns a random element from the provided array and maintains object type.
      Specified by:
      getRandomElement in interface IRNG
      Type Parameters:
      T - the type of the returned object
      Parameters:
      array - the array to get an element from
      Returns:
      the randomly selected element

    • getRandomElement

      public <T> T getRandomElement​(List<T> list)
      Returns a random element from the provided list. If the list is empty then null is returned. This will perform well on Lists that allow random access, but will not perform as well on LinkedList or similar classes that need to iterate one-by-one in their List.get(int) method.
      Specified by:
      getRandomElement in interface IRNG
      Type Parameters:
      T - the type of the returned object
      Parameters:
      list - the list to get an element from
      Returns:
      the randomly selected element

    • getRandomElement

      public <T> T getRandomElement​(Collection<T> coll)
      Returns a random element from the provided Collection, which should have predictable iteration order if you want predictable behavior for identical RNG seeds, though it will get a random element just fine for any Collection (just not predictably in all cases). If you give this a Set, it should be a LinkedHashSet or some form of sorted Set like TreeSet if you want predictable results. Any List or Queue should be fine. Map does not implement Collection, thank you very much Java library designers, so you can't actually pass a Map to this, though you can pass the keys or values. If coll is empty, returns null.
      Requires iterating through a random amount of coll's elements, so performance depends on the size of coll but is likely to be decent, as long as iteration isn't unusually slow. This replaces getRandomElement(Queue), since Queue implements Collection and the older Queue-using implementation was probably less efficient.
      You should generally prefer getRandomElement(List) whenever possible, or in some cases you can use methods that get a random value on the Collection (or Map, in the case of OrderedMap) itself.
      Specified by:
      getRandomElement in interface IRNG
      Type Parameters:
      T - the type of the returned object
      Parameters:
      coll - the Collection to get an element from; remember, Map does not implement Collection
      Returns:
      the randomly selected element

    • swap

      protected static <T> void swap​(T[] arr, int pos1, int pos2)
      Mutates the array arr by switching the contents at pos1 and pos2.
      Parameters:
      arr - an array of T; must not be null
      pos1 - an index into arr; must be at least 0 and no greater than arr.length
      pos2 - an index into arr; must be at least 0 and no greater than arr.length

    • shuffle

      public <T> T[] shuffle​(T[] elements)
      Shuffle an array using the Fisher-Yates algorithm and returns a shuffled copy, freshly-allocated, without modifying elements.
      Wikipedia has more on this algorithm.
      Specified by:
      shuffle in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - an array of T; will not be modified
      Returns:
      a shuffled copy of elements

    • shuffleInPlace

      public <T> T[] shuffleInPlace​(T[] elements)
      Shuffles an array in-place using the Fisher-Yates algorithm. If you don't want the array modified, use shuffle(Object[], Object[]).
      Wikipedia has more on this algorithm.
      Specified by:
      shuffleInPlace in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - an array of T; will be modified
      Returns:
      elements after shuffling it in-place

    • shuffle

      public <T> T[] shuffle​(T[] elements, T[] dest)
      Shuffle an array using the Fisher-Yates algorithm. If possible, create a new array or reuse an existing array with the same length as elements and pass it in as dest; the dest array will contain the shuffled contents of elements and will also be returned as-is. If dest does not have the same length as elements, this will throw an IllegalArgumentException
      Wikipedia has more on this algorithm.
      Specified by:
      shuffle in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - an array of T; will not be modified
      dest - Where to put the shuffle. If it does not have the same length as elements, this will throw an IllegalArgumentException.
      Returns:
      dest after modifications

    • shuffle

      public <T> ArrayList<T> shuffle​(Collection<T> elements)
      Shuffles a Collection of T using the Fisher-Yates algorithm and returns an ArrayList of T.
      Wikipedia has more on this algorithm.
      Specified by:
      shuffle in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - a Collection of T; will not be modified
      Returns:
      a shuffled ArrayList containing the whole of elements in pseudo-random order.

    • shuffle

      public <T> ArrayList<T> shuffle​(Collection<T> elements, ArrayList<T> buf)
      Shuffles a Collection of T using the Fisher-Yates algorithm and puts it in a buffer. The result is allocated if buf is null or if buf isn't empty, otherwise elements is poured into buf.
      Wikipedia has more on this algorithm.
      Specified by:
      shuffle in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - a Collection of T; will not be modified
      buf - a buffer as an ArrayList that will be filled with the shuffled contents of elements; if null or non-empty, a new ArrayList will be allocated and returned
      Returns:
      a shuffled ArrayList containing the whole of elements in pseudo-random order, which may be buf

    • shuffleInPlace

      public <T> List<T> shuffleInPlace​(List<T> elements)
      Shuffles a Collection of T items in-place using the Fisher-Yates algorithm. This only shuffles List data structures. If you don't want the array modified, use shuffle(Collection), which returns a List as well.
      Wikipedia has more on this algorithm.
      Specified by:
      shuffleInPlace in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      elements - a Collection of T; will be modified
      Returns:
      elements after shuffling it in-place

    • randomOrdering

      public int[] randomOrdering​(int length)
      Generates a random permutation of the range from 0 (inclusive) to length (exclusive). Useful for passing to OrderedMap or OrderedSet's reorder() methods.
      Specified by:
      randomOrdering in interface IRNG
      Parameters:
      length - the size of the ordering to produce
      Returns:
      a random ordering containing all ints from 0 to length (exclusive)

    • randomOrdering

      public int[] randomOrdering​(int length, int[] dest)
      Generates a random permutation of the range from 0 (inclusive) to length (exclusive) and stores it in the dest parameter, avoiding allocations. Useful for passing to OrderedMap or OrderedSet's reorder() methods.
      Specified by:
      randomOrdering in interface IRNG
      Parameters:
      length - the size of the ordering to produce; the smaller of dest.length and length will be used
      dest - the destination array; will be modified
      Returns:
      dest, filled with a random ordering containing all ints from 0 to length (exclusive)

    • randomPortion

      public <T> T[] randomPortion​(T[] data, T[] output)
      Gets a random portion of data (an array), assigns that portion to output (an array) so that it fills as much as it can, and then returns output. Will only use a given position in the given data at most once; uses a Feistel Network to accomplish this without allocations. Internally, makes 2 calls to nextInt(), regardless of the data being randomized.
      Uses approximately the same code as LowStorageShuffler, but without any object or array allocations.
      Specified by:
      randomPortion in interface IRNG
      Type Parameters:
      T - can be any non-primitive type.
      Parameters:
      data - an array of T; will not be modified.
      output - an array of T that will be overwritten; should always be instantiated with the portion length
      Returns:
      output, after Math.min(output.length, data.length) unique items have been put into it from data

    • copy

      public abstract IRNG copy()
      Creates a copy of this IRNG; it will generate the same random numbers, given the same calls in order, as this IRNG at the point copy() is called. The copy will not share references with this IRNG. If this IRNG does not permit copying itself, it is suggested to either throw an UnsupportedOperationException or return a new IRNG of the same type but with a random seed, with the latter meant as a partial defense against cheating.
      This is abstract because every implementation is likely to have different specifics for this.
      Specified by:
      copy in interface IRNG
      Specified by:
      copy in interface RandomnessSource
      Returns:
      a copy of this IRNG

    • toSerializable

      public abstract Serializable toSerializable()
      Gets a view of this IRNG in a way that implements Serializable, which may simply be this IRNG if it implements Serializable as well as IRNG.
      For implementors: It is suggested to return an RNG initialized by calling RNG(long) with nextLong() if you are unable to save the current state of this IRNG and the caller still needs something saved. This won't preserve the current state or the choice of IRNG implementation, however, so it is simply a last resort in case you don't want to throw an exception.
      Specified by:
      toSerializable in interface IRNG
      Returns:
      a Serializable view of this IRNG or a similar one; may be this