// Deterministic shuffled list iterator using an XORSHIFT RNG
// Each step is O(1), iterator is OSPACE(1)

sclass WeightlessShuffledIterator<A> extends ItIt<A> {
  final L<A> list;
  final int n;
  int i;
  TripletLSFR lsfr;

  // deterministic version
  *(L<A> *list) {
    n = l(list);
    if (n == 0) ret;
    int bits = numberOfBitsNeededToRepresentNOptions(n+1);
    lsfr = new TripletLSFR(bits);
  }
  
  public bool hasNext() { ret i < n; }
  
  public A next() {
    ++i;
    int raw;
    do {
      if (lsfr.step >= lsfr.cycleLength()+1)
        fail("Internal error");
      raw = postProcessLSFRValue(lsfr.next()-1);
      printVars ifdef WeightlessShuffledIterator_debug(+i, +raw, step := lsfr.step);
    } while (raw >= n);
    ret list.get(raw);
  };
  
  int bits() { ret lsfr == null ? 0 : lsfr.n; }
  
  // overridable in subclasses
  int postProcessLSFRValue(int i) { ret i; }
}