// Deterministic shuffled list iterator using an XORSHIFT RNG // Each step is O(1), iterator is OSPACE(1) // This iterator doesn't have a seed parameter and is completely // deterministic with respect to a given list size. // If you want to pass a seed, use WeightlessShuffledIteratorWithSeed. sclass WeightlessShuffledIterator<A> extends ItIt<A> { final L<A> list; final int n; int i; final TripletLSFR lsfr; // initialize only with a length (and a pseudo-list) // if you are going to be calling nextIndex() instead of next() *(int n) { this((L) virtualNullList(n)); } // initialize with a list to shuffle *(L<A> *list) { n = l(list); if (n == 0) ret with lsfr = null; int bits = numberOfBitsNeededToRepresentNOptions(n+1); lsfr = new TripletLSFR(bits); } public bool hasNext() { ret i < n; } public A next() { ret list.get(nextIndex()); } // you can call nextIndex() without having checked hasNext(), // then it will just return -1 when the iteration is complete. public int nextIndex() { if (i++ >= n) ret -1; int raw; do { ifdef WeightlessShuffledIterator_SafetyChecks if (lsfr.cycleComplete()) fail("Internal error"); endifdef raw = postProcessLSFRValue(lsfr.next()-1); printVars ifdef WeightlessShuffledIterator_debug(+i, +raw, step := lsfr.step); } while (raw >= n); ret raw; }; int bits() { ret lsfr == null ? 0 : lsfr.n; } // overridable in subclasses int postProcessLSFRValue(int i) { ret i; } }
Began life as a copy of #1035206
download show line numbers debug dex old transpilations
Travelled to 3 computer(s): bhatertpkbcr, mowyntqkapby, mqqgnosmbjvj
No comments. add comment
Snippet ID: | #1035213 |
Snippet name: | WeightlessShuffledIterator (working backup with external LSFR) - iterate over list in random order using an LSFR (=iterator is OSPACE(1)) |
Eternal ID of this version: | #1035213/1 |
Text MD5: | e7f34dd56f29b29fc7d56798ca38c2ad |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2022-04-15 17:18:30 |
Source code size: | 1635 bytes / 58 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 159 / 166 |
Referenced in: | -