squidpony.squidmath

Class ShuffledIntSequence

java.lang.Object

squidpony.squidmath.LowStorageShuffler

squidpony.squidmath.ShuffledIntSequence

All Implemented Interfaces:

java.io.Serializable

public class ShuffledIntSequence
extends LowStorageShuffler
implements java.io.Serializable

An infinite sequence of pseudo-random ints (typically used as indices) from 0 to some bound, with all possible ints returned in a shuffled order before re-shuffling for the next result. Does not store the sequence in memory. Uses a Feistel network, as described in this post by Alan Wolfe. The API is very simple; you construct a ShuffledIntSequence by specifying how many items it should shuffle (the actual sequence is boundless, but the items it can return are limited to between 0 and some bound), and you can optionally use a seed (it will be random if you don't specify a seed). Call next() on a ShuffledIntSequence to get the next distinct int in the shuffled ordering; next() will re-shuffle the sequence if it runs out of distinct possible results. You can go back to the previous item with previous(), which is allowed to go earlier than the first result generated (it will jump back to what is effectively the previous shuffled sequence). You can restart the sequence with LowStorageShuffler.restart() to use the same sequence over again (which doesn't make much sense here, since this makes many sequences by re-shuffling), 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 LowStorageShuffler.round(long, long) method used here reuses the CrossHash.Water.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.
This class extends LowStorageShuffler, changing it from producing a unique set of ints once, to producing many sets of ints one after the next.
Created by Tommy Ettinger on 9/30/2018.

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected long	seed

Fields inherited from class squidpony.squidmath.LowStorageShuffler

bound, halfBits, index, key0, key1, key2, key3, leftMask, pow4, rightMask

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
int	next() Gets the next distinct int in the sequence, shuffling the sequence if it has been exhausted so it never runs out.
int	previous() Gets the previous returned int from the sequence (as yielded by next()), restarting the sequence in a correctly-ordered way if it would go to before the "start" of the sequence (it is actually close to infinite both going forwards and backwards).
void	restart(long seed) Starts the sequence over, but can change the seed (completely changing the sequence).

Methods inherited from class squidpony.squidmath.LowStorageShuffler

copy, deserializeFromString, encode, equals, hashCode, restart, round, serializeToString

Methods inherited from class java.lang.Object

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

Field Detail

seed

protected long seed

Constructor Detail

ShuffledIntSequence

public ShuffledIntSequence()

Constructs a ShuffledIntSequence with a random seed and a bound of 10.

ShuffledIntSequence

public ShuffledIntSequence(int bound)

Constructs a ShuffledIntSequence with the given exclusive upper bound and a random seed.

Parameters:

bound - how many distinct ints this can return

ShuffledIntSequence

public ShuffledIntSequence(int bound,
                           long seed)

Constructs a ShuffledIntSequence with the given exclusive upper bound and int seed.

Parameters:

bound - how many distinct ints this can return

seed - any int; will be used to get several seeds used internally

Method Detail

next

public int next()

Gets the next distinct int in the sequence, shuffling the sequence if it has been exhausted so it never runs out.

Overrides:

next in class LowStorageShuffler

Returns:

the next item in the sequence

previous

public int previous()

Gets the previous returned int from the sequence (as yielded by next()), restarting the sequence in a correctly-ordered way if it would go to before the "start" of the sequence (it is actually close to infinite both going forwards and backwards).

Overrides:

previous in class LowStorageShuffler

Returns:

the previously-given item in the sequence, or -1 if something goes wrong (which shouldn't be possible)

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 LowStorageShuffler.restart().

Overrides:

restart in class LowStorageShuffler

Parameters:

seed - any int; will be used to get several seeds used internally