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

}