// shuffledIterator()

//

// -iterates over a list in random order

// -each element is returned exactly once if you iterate to the end

// -efficient no matter how many elements you want

// -can handle null elements

// (whether it's very few, half of the list or almost all elements)

static <A> IterableIterator<A> shuffledIterator(L<A> l) {

  ret new IterableIterator<A>() {

    int n = l(l);

    int i = 0;

    new HashMap<Int, A> shuffled;

    public bool hasNext() { ret i < n; }

    public A next() {

      int j = random(i, n);

      A a = get(i), b = get(j);

      shuffled.put(j, a);

      shuffled.remove(i);

      ++i;

      ret b;

    }

    A get(int i) {

      // must call containsKey first because of possible null elements

      ret shuffled.containsKey(i) ? shuffled.get(i) : l.get(i);

    }

  };

}