// 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