Class IntShuffler

java.lang.Object
com.github.yellowstonegames.core.IntShuffler
@Beta public class IntShuffler extends Object
Gets a sequence of distinct pseudo-random ints (typically used as indices) from 0 to some bound, without storing all the sequence in memory. Uses a Feistel network, as described in this post by Alan Wolfe. The API is very simple; you construct an IntShuffler by specifying how many items it can shuffle, and you can optionally use a seed (it will be random if you don't specify a seed). Call next() on an IntShuffler to get the next distinct int in the shuffled ordering; next() will return -1 if there are no more distinct ints (if bound items have already been returned). You can go back to the previous item with previous(), which similarly returns -1 if it can't go earlier in the sequence. You can restart the sequence with restart() to use the same sequence over again, or restart(long) to use a different seed (the bound is fixed).
This differs from the version in Alan Wolfe's example code and blog post; it uses a very different round function. Wolfe's round function is MurmurHash2, but as far as I can tell the version he uses doesn't have anything like MurmurHash3's fmix32() to adequately avalanche bits, and since all keys are small keys with the usage of MurmurHash2 in his code, avalanche is the most important thing. It's also perfectly fine to use irreversible operations in a Feistel network round function, and I do that since it seems to improve randomness slightly. The round(long, long) method used here reuses the Hasher.wow(long, long) method; it acts like an unbalanced, irreversible PRNG with two states, and that turns out to be just fine for a Feistel network. This also uses a different seed for each round.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    bound
     
    protected int
    halfBits
     
    protected int
    index
     
    protected long
    key0
     
    protected long
    key1
     
    protected long
    key2
     
    protected long
    key3
     
    protected int
    leftMask
     
    protected int
    pow4
     
    protected int
    rightMask
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    IntShuffler()
    Constructs an IntShuffler with a random seed and a bound of 10.
    IntShuffler(int bound)
    Constructs an IntShuffler with the given exclusive upper bound and a random seed.
    IntShuffler(int bound, long seed)
    Constructs an IntShuffler with the given exclusive upper bound and int seed.
    IntShuffler(IntShuffler other)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    IntShuffler
    copy()
    Fully copies this IntShuffler, including its current index in its sequence and internal seeds.
    int
    encode(int index)
    Encodes an index with a 4-round Feistel network.
    boolean
    equals(Object o)
     
    long
    fuse(long a, long b)
    Used by the round function, this can technically be any deterministic function that takes two long inputs and produces a long output.
    int
    getBound()
     
    int
    hashCode()
     
    int
    next()
    Gets the next distinct int in the sequence, or -1 if all distinct ints have been returned that are non-negative and less than bound.
    int
    previous()
    Gets the previous returned int from the sequence (as yielded by next()), or -1 if next() has never been called (or the IntShuffler has reached the beginning from repeated calls to this method).
    void
    restart()
    Starts the same sequence over from the beginning.
    void
    restart(long seed)
    Starts the sequence over, but can change the seed (completely changing the sequence).
    int
    round(long data, long seed)
     
    static IntShuffler
    stringDeserialize(String data)
     
    String
    stringSerialize()
     

    Methods inherited from class Object

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

  • Field Details

    • bound

      protected int bound

    • index

      protected int index

    • pow4

      protected int pow4

    • halfBits

      protected int halfBits

    • leftMask

      protected int leftMask

    • rightMask

      protected int rightMask

    • key0

      protected long key0

    • key1

      protected long key1

    • key2

      protected long key2

    • key3

      protected long key3

  • Constructor Details

    • IntShuffler

      public IntShuffler()
      Constructs an IntShuffler with a random seed and a bound of 10.

    • IntShuffler

      public IntShuffler(int bound)
      Constructs an IntShuffler with the given exclusive upper bound and a random seed.
      Parameters:
      bound - how many distinct ints this can return

    • IntShuffler

      public IntShuffler(int bound, long seed)
      Constructs an IntShuffler with the given exclusive upper bound and int seed.
      Parameters:
      bound - how many distinct ints this can return
      seed - any long; will be used to get several seeds used internally

    • IntShuffler

      public IntShuffler(IntShuffler other)

  • Method Details

    • next

      public int next()
      Gets the next distinct int in the sequence, or -1 if all distinct ints have been returned that are non-negative and less than bound.
      Returns:
      the next item in the sequence, or -1 if the sequence has been exhausted

    • previous

      public int previous()
      Gets the previous returned int from the sequence (as yielded by next()), or -1 if next() has never been called (or the IntShuffler has reached the beginning from repeated calls to this method).
      Returns:
      the previously-given item in the sequence, or -1 if this can't go earlier

    • restart

      public void restart()
      Starts the same sequence over from the beginning.

    • restart

      public void restart(long seed)
      Starts the sequence over, but can change the seed (completely changing the sequence). If seed is the same as the seed given in the constructor, this will use the same sequence, acting like restart().
      Parameters:
      seed - any long; will be used to get several seeds used internally

    • fuse

      public long fuse(long a, long b)
      Used by the round function, this can technically be any deterministic function that takes two long inputs and produces a long output. It doesn't need to be "fair" at all. Other good options for this are Hasher.wow(long, long) and potentially Hasher.mum(long, long) (which sometimes fails tests with a random component, though any random-enough function should fail such tests occasionally).
      Parameters:
      a - any long
      b - any long
      Returns:
      any long

    • round

      public int round(long data, long seed)

    • encode

      public int encode(int index)
      Encodes an index with a 4-round Feistel network. It is possible that someone would want to override this method to use more or less rounds, but there must always be an even number.
      Parameters:
      index - the index to cipher; must be between 0 and pow4, inclusive
      Returns:
      the ciphered index, which might not be less than bound but will be less than or equal to pow4

    • copy

      public IntShuffler copy()
      Fully copies this IntShuffler, including its current index in its sequence and internal seeds. This simply returns IntShuffler(IntShuffler) with this as the argument.
      Returns:
      an exact copy of this IntShuffler

    • stringSerialize

      public String stringSerialize()

    • stringDeserialize

      public static IntShuffler stringDeserialize(String data)

    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • getBound

      public int getBound()