Initial vendor packages

Signed-off-by: Valentin Popov <valentin@popov.link>

1 files changed, 337 insertions, 0 deletions

diff --git a/vendor/rand/src/seq.rs b/vendor/rand/src/seq.rs
new file mode 100644
index 0000000..a7889fe
--- /dev/null
+++ b/vendor/rand/src/seq.rs
@@ -0,0 +1,337 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Functions for randomly accessing and sampling sequences.
+
+use super::Rng;
+
+// This crate is only enabled when either std or alloc is available.
+// BTreeMap is not as fast in tests, but better than nothing.
+#[cfg(feature="std")] use std::collections::HashMap;
+#[cfg(not(feature="std"))] use alloc::btree_map::BTreeMap;
+
+#[cfg(not(feature="std"))] use alloc::Vec;
+
+/// Randomly sample `amount` elements from a finite iterator.
+///
+/// The following can be returned:
+/// - `Ok`: `Vec` of `amount` non-repeating randomly sampled elements. The order is not random.
+/// - `Err`: `Vec` of all the elements from `iterable` in sequential order. This happens when the
+///   length of `iterable` was less than `amount`. This is considered an error since exactly
+///   `amount` elements is typically expected.
+///
+/// This implementation uses `O(len(iterable))` time and `O(amount)` memory.
+///
+/// # Example
+///
+/// ```rust
+/// use rand::{thread_rng, seq};
+///
+/// let mut rng = thread_rng();
+/// let sample = seq::sample_iter(&mut rng, 1..100, 5).unwrap();
+/// println!("{:?}", sample);
+/// ```
+pub fn sample_iter<T, I, R>(rng: &mut R, iterable: I, amount: usize) -> Result<Vec<T>, Vec<T>>
+    where I: IntoIterator<Item=T>,
+          R: Rng,
+{
+    let mut iter = iterable.into_iter();
+    let mut reservoir = Vec::with_capacity(amount);
+    reservoir.extend(iter.by_ref().take(amount));
+
+    // Continue unless the iterator was exhausted
+    //
+    // note: this prevents iterators that "restart" from causing problems.
+    // If the iterator stops once, then so do we.
+    if reservoir.len() == amount {
+        for (i, elem) in iter.enumerate() {
+            let k = rng.gen_range(0, i + 1 + amount);
+            if let Some(spot) = reservoir.get_mut(k) {
+                *spot = elem;
+            }
+        }
+        Ok(reservoir)
+    } else {
+        // Don't hang onto extra memory. There is a corner case where
+        // `amount` was much less than `len(iterable)`.
+        reservoir.shrink_to_fit();
+        Err(reservoir)
+    }
+}
+
+/// Randomly sample exactly `amount` values from `slice`.
+///
+/// The values are non-repeating and in random order.
+///
+/// This implementation uses `O(amount)` time and memory.
+///
+/// Panics if `amount > slice.len()`
+///
+/// # Example
+///
+/// ```rust
+/// use rand::{thread_rng, seq};
+///
+/// let mut rng = thread_rng();
+/// let values = vec![5, 6, 1, 3, 4, 6, 7];
+/// println!("{:?}", seq::sample_slice(&mut rng, &values, 3));
+/// ```
+pub fn sample_slice<R, T>(rng: &mut R, slice: &[T], amount: usize) -> Vec<T>
+    where R: Rng,
+          T: Clone
+{
+    let indices = sample_indices(rng, slice.len(), amount);
+
+    let mut out = Vec::with_capacity(amount);
+    out.extend(indices.iter().map(|i| slice[*i].clone()));
+    out
+}
+
+/// Randomly sample exactly `amount` references from `slice`.
+///
+/// The references are non-repeating and in random order.
+///
+/// This implementation uses `O(amount)` time and memory.
+///
+/// Panics if `amount > slice.len()`
+///
+/// # Example
+///
+/// ```rust
+/// use rand::{thread_rng, seq};
+///
+/// let mut rng = thread_rng();
+/// let values = vec![5, 6, 1, 3, 4, 6, 7];
+/// println!("{:?}", seq::sample_slice_ref(&mut rng, &values, 3));
+/// ```
+pub fn sample_slice_ref<'a, R, T>(rng: &mut R, slice: &'a [T], amount: usize) -> Vec<&'a T>
+    where R: Rng
+{
+    let indices = sample_indices(rng, slice.len(), amount);
+
+    let mut out = Vec::with_capacity(amount);
+    out.extend(indices.iter().map(|i| &slice[*i]));
+    out
+}
+
+/// Randomly sample exactly `amount` indices from `0..length`.
+///
+/// The values are non-repeating and in random order.
+///
+/// This implementation uses `O(amount)` time and memory.
+///
+/// This method is used internally by the slice sampling methods, but it can sometimes be useful to
+/// have the indices themselves so this is provided as an alternative.
+///
+/// Panics if `amount > length`
+pub fn sample_indices<R>(rng: &mut R, length: usize, amount: usize) -> Vec<usize>
+    where R: Rng,
+{
+    if amount > length {
+        panic!("`amount` must be less than or equal to `slice.len()`");
+    }
+
+    // We are going to have to allocate at least `amount` for the output no matter what. However,
+    // if we use the `cached` version we will have to allocate `amount` as a HashMap as well since
+    // it inserts an element for every loop.
+    //
+    // Therefore, if `amount >= length / 2` then inplace will be both faster and use less memory.
+    // In fact, benchmarks show the inplace version is faster for length up to about 20 times
+    // faster than amount.
+    //
+    // TODO: there is probably even more fine-tuning that can be done here since
+    // `HashMap::with_capacity(amount)` probably allocates more than `amount` in practice,
+    // and a trade off could probably be made between memory/cpu, since hashmap operations
+    // are slower than array index swapping.
+    if amount >= length / 20 {
+        sample_indices_inplace(rng, length, amount)
+    } else {
+        sample_indices_cache(rng, length, amount)
+    }
+}
+
+/// Sample an amount of indices using an inplace partial fisher yates method.
+///
+/// This allocates the entire `length` of indices and randomizes only the first `amount`.
+/// It then truncates to `amount` and returns.
+///
+/// This is better than using a HashMap "cache" when `amount >= length / 2` since it does not
+/// require allocating an extra cache and is much faster.
+fn sample_indices_inplace<R>(rng: &mut R, length: usize, amount: usize) -> Vec<usize>
+    where R: Rng,
+{
+    debug_assert!(amount <= length);
+    let mut indices: Vec<usize> = Vec::with_capacity(length);
+    indices.extend(0..length);
+    for i in 0..amount {
+        let j: usize = rng.gen_range(i, length);
+        let tmp = indices[i];
+        indices[i] = indices[j];
+        indices[j] = tmp;
+    }
+    indices.truncate(amount);
+    debug_assert_eq!(indices.len(), amount);
+    indices
+}
+
+
+/// This method performs a partial fisher-yates on a range of indices using a HashMap
+/// as a cache to record potential collisions.
+///
+/// The cache avoids allocating the entire `length` of values. This is especially useful when
+/// `amount <<< length`, i.e. select 3 non-repeating from 1_000_000
+fn sample_indices_cache<R>(
+    rng: &mut R,
+    length: usize,
+    amount: usize,
+) -> Vec<usize>
+    where R: Rng,
+{
+    debug_assert!(amount <= length);
+    #[cfg(feature="std")] let mut cache = HashMap::with_capacity(amount);
+    #[cfg(not(feature="std"))] let mut cache = BTreeMap::new();
+    let mut out = Vec::with_capacity(amount);
+    for i in 0..amount {
+        let j: usize = rng.gen_range(i, length);
+
+        // equiv: let tmp = slice[i];
+        let tmp = match cache.get(&i) {
+            Some(e) => *e,
+            None => i,
+        };
+
+        // equiv: slice[i] = slice[j];
+        let x = match cache.get(&j) {
+            Some(x) => *x,
+            None => j,
+        };
+
+        // equiv: slice[j] = tmp;
+        cache.insert(j, tmp);
+
+        // note that in the inplace version, slice[i] is automatically "returned" value
+        out.push(x);
+    }
+    debug_assert_eq!(out.len(), amount);
+    out
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use {thread_rng, XorShiftRng, SeedableRng};
+
+    #[test]
+    fn test_sample_iter() {
+        let min_val = 1;
+        let max_val = 100;
+
+        let mut r = thread_rng();
+        let vals = (min_val..max_val).collect::<Vec<i32>>();
+        let small_sample = sample_iter(&mut r, vals.iter(), 5).unwrap();
+        let large_sample = sample_iter(&mut r, vals.iter(), vals.len() + 5).unwrap_err();
+
+        assert_eq!(small_sample.len(), 5);
+        assert_eq!(large_sample.len(), vals.len());
+        // no randomization happens when amount >= len
+        assert_eq!(large_sample, vals.iter().collect::<Vec<_>>());
+
+        assert!(small_sample.iter().all(|e| {
+            **e >= min_val && **e <= max_val
+        }));
+    }
+    #[test]
+    fn test_sample_slice_boundaries() {
+        let empty: &[u8] = &[];
+
+        let mut r = thread_rng();
+
+        // sample 0 items
+        assert_eq!(sample_slice(&mut r, empty, 0), vec![]);
+        assert_eq!(sample_slice(&mut r, &[42, 2, 42], 0), vec![]);
+
+        // sample 1 item
+        assert_eq!(sample_slice(&mut r, &[42], 1), vec![42]);
+        let v = sample_slice(&mut r, &[1, 42], 1)[0];
+        assert!(v == 1 || v == 42);
+
+        // sample "all" the items
+        let v = sample_slice(&mut r, &[42, 133], 2);
+        assert!(v == vec![42, 133] || v == vec![133, 42]);
+
+        assert_eq!(sample_indices_inplace(&mut r, 0, 0), vec![]);
+        assert_eq!(sample_indices_inplace(&mut r, 1, 0), vec![]);
+        assert_eq!(sample_indices_inplace(&mut r, 1, 1), vec![0]);
+
+        assert_eq!(sample_indices_cache(&mut r, 0, 0), vec![]);
+        assert_eq!(sample_indices_cache(&mut r, 1, 0), vec![]);
+        assert_eq!(sample_indices_cache(&mut r, 1, 1), vec![0]);
+
+        // Make sure lucky 777's aren't lucky
+        let slice = &[42, 777];
+        let mut num_42 = 0;
+        let total = 1000;
+        for _ in 0..total {
+            let v = sample_slice(&mut r, slice, 1);
+            assert_eq!(v.len(), 1);
+            let v = v[0];
+            assert!(v == 42 || v == 777);
+            if v == 42 {
+                num_42 += 1;
+            }
+        }
+        let ratio_42 = num_42 as f64 / 1000 as f64;
+        assert!(0.4 <= ratio_42 || ratio_42 <= 0.6, "{}", ratio_42);
+    }
+
+    #[test]
+    fn test_sample_slice() {
+        let xor_rng = XorShiftRng::from_seed;
+
+        let max_range = 100;
+        let mut r = thread_rng();
+
+        for length in 1usize..max_range {
+            let amount = r.gen_range(0, length);
+            let seed: [u32; 4] = [
+                r.next_u32(), r.next_u32(), r.next_u32(), r.next_u32()
+            ];
+
+            println!("Selecting indices: len={}, amount={}, seed={:?}", length, amount, seed);
+
+            // assert that the two index methods give exactly the same result
+            let inplace = sample_indices_inplace(
+                &mut xor_rng(seed), length, amount);
+            let cache = sample_indices_cache(
+                &mut xor_rng(seed), length, amount);
+            assert_eq!(inplace, cache);
+
+            // assert the basics work
+            let regular = sample_indices(
+                &mut xor_rng(seed), length, amount);
+            assert_eq!(regular.len(), amount);
+            assert!(regular.iter().all(|e| *e < length));
+            assert_eq!(regular, inplace);
+
+            // also test that sampling the slice works
+            let vec: Vec<usize> = (0..length).collect();
+            {
+                let result = sample_slice(&mut xor_rng(seed), &vec, amount);
+                assert_eq!(result, regular);
+            }
+
+            {
+                let result = sample_slice_ref(&mut xor_rng(seed), &vec, amount);
+                let expected = regular.iter().map(|v| v).collect::<Vec<_>>();
+                assert_eq!(result, expected);
+            }
+        }
+    }
+}