Gankro/collect-rs — pull request #30 by cybergeek94 (2014-12-20 02:49:47+00:00)
Title: `Sample` iterator adaptor that randomly skips values and yields them later

Adds a `Sample` iterator adaptor and a `SampleIterator: Iterator` adaptor trait.

The `Sample` iterator uses a user-chosen (or default task-local) PRNG to randomly sample elements from an iterator based on a weighted boolean (configurable), but also holding skipped elements in a ringbuffer to yield later, so that it never discards elements.

If it skips an element, it pops from the back of the ringbuffer and yields that. If the ringbuffer is empty, it pushes the current element and recurses.

With finite iterators, it yields all elements in a random order, effectively shuffling the source collection.
With infinite iterators, it skips or yields elements at random, storing skipped elements to possibly yield later but never discarding them.

Since the weight is a public field, the adaptor can later be set to yield just skipped elements, or directly from the underlying iterator.

**Bikeshedding:** Should the iterator be called `SkipRand` or `Shuffle` instead? I couldn't decide. Each of them implies different but somewhat intersecting behavior.

It might be good to add a disclaimer that this hasn't been audited for cryptographic uses; I can't think of any ways that this would be useful in crypto but you never know. Theoretically, it shouldn't be predictable as long as the underling PRNG is cryptographically secure, though once the underlying iterator has been exhausted it will yield skipped elements in FIFO order which might be a potential security issue.