Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

58
LINES

< > BotCompany Repo | #1035213 // WeightlessShuffledIterator (working backup with external LSFR) - iterate over list in random order using an LSFR (=iterator is OSPACE(1))

JavaX fragment (include)

1  
// Deterministic shuffled list iterator using an XORSHIFT RNG
2  
// Each step is O(1), iterator is OSPACE(1)
3  
4  
// This iterator doesn't have a seed parameter and is completely
5  
// deterministic with respect to a given list size.
6  
// If you want to pass a seed, use WeightlessShuffledIteratorWithSeed.
7  
8  
sclass WeightlessShuffledIterator<A> extends ItIt<A> {
9  
  final L<A> list;
10  
  final int n;
11  
  int i;
12  
  final TripletLSFR lsfr;
13  
14  
  // initialize only with a length (and a pseudo-list)
15  
  // if you are going to be calling nextIndex() instead of next()
16  
  *(int n) {
17  
    this((L) virtualNullList(n));
18  
  }
19  
  
20  
  // initialize with a list to shuffle
21  
  *(L<A> *list) {
22  
    n = l(list);
23  
    if (n == 0) ret with lsfr = null;
24  
    int bits = numberOfBitsNeededToRepresentNOptions(n+1);
25  
    lsfr = new TripletLSFR(bits);
26  
  }
27  
  
28  
  public bool hasNext() { ret i < n; }
29  
  
30  
  public A next() {
31  
    ret list.get(nextIndex());
32  
  }
33  
  
34  
  // you can call nextIndex() without having checked hasNext(),
35  
  // then it will just return -1 when the iteration is complete.
36  
  public int nextIndex() {
37  
    if (i++ >= n) ret -1;
38  
    
39  
    int raw;
40  
    do {
41  
      ifdef WeightlessShuffledIterator_SafetyChecks
42  
        if (lsfr.cycleComplete())
43  
          fail("Internal error");
44  
      endifdef
45  
      
46  
      raw = postProcessLSFRValue(lsfr.next()-1);
47  
      
48  
      printVars ifdef WeightlessShuffledIterator_debug(+i, +raw, step := lsfr.step);
49  
    } while (raw >= n);
50  
    
51  
    ret raw;
52  
  };
53  
  
54  
  int bits() { ret lsfr == null ? 0 : lsfr.n; }
55  
  
56  
  // overridable in subclasses
57  
  int postProcessLSFRValue(int i) { ret i; }
58  
}

Author comment

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: 158 / 165
Referenced in: [show references]