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

// Performance: Takes between 5 and 18 ns per nextIndex() on a laptop
//              and between 2 and 11 ns on a desktop CPU.
//              (these numbers are actually for WeightlessShuffledIteratorWithSeed,
//              WeightlessShuffledIterator itself is a tiny bit faster.)

sclass WeightlessShuffledIterator<A> extends ItIt<A> is IndexIterator {
  final L<A> list;
  final int n;
  final int bits, cycleLength, a, b, c;
  
  int i; // step counter
  
  // now doing the TripletLSFR stuff directly in here
  int value;
  
  // initialize only with a length (i.e. list containing 0, 1, ...)
  // if you are going to be calling nextIndex() instead of next()
  *(int n) {
    this((L) iotaZeroList(n));
  }
  
  // initialize with a list to shuffle
  *(L<A> *list) {
    n = l(list);
    if (n == 0) ret with a = b = c = bits = cycleLength = 0;
    bits = numberOfBitsNeededToRepresentNOptions(n+1);
    var lsfr = new TripletLSFR(bits);
    meta-for a also as b, c, value, cycleLength { a = lsfr.a; }
  }
  
  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;
    ++i;
    
    int raw;
    do {
      int x = value;
      x ^= (x << a) & cycleLength;
      x ^= x >>> b;
      x ^= (x << c) & cycleLength;
      value = x;
      raw = postProcessLSFRValue(x-1);
    } while (raw >= n);
    
    ret raw;
  };
  
  int bits() { ret bits; }
  
  // overridable in subclasses
  int postProcessLSFRValue(int i) { ret i; }
}