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

}