use crate::std_facade::{Cell, VecDeque, Vec};
use rand::Rng;
use crate::num;
use crate::strategy::traits::*;
use crate::test_runner::*;
#[derive(Clone, Debug)]
#[must_use = "strategies do nothing unless used"]
pub struct Shuffle<S>(pub(super) S);
pub trait Shuffleable {
fn shuffle_len(&self) -> usize;
fn shuffle_swap(&mut self, a: usize, b: usize);
}
macro_rules! shuffleable {
($($t:tt)*) => {
impl<T> Shuffleable for $($t)* {
fn shuffle_len(&self) -> usize {
self.len()
}
fn shuffle_swap(&mut self, a: usize, b: usize) {
self.swap(a, b);
}
}
}
}
shuffleable!([T]);
shuffleable!(Vec<T>);
shuffleable!(VecDeque<T>);
shuffleable!([T;0]);
shuffleable!([T;1]);
shuffleable!([T;2]);
shuffleable!([T;3]);
shuffleable!([T;4]);
shuffleable!([T;5]);
shuffleable!([T;6]);
shuffleable!([T;7]);
shuffleable!([T;8]);
shuffleable!([T;9]);
shuffleable!([T;10]);
shuffleable!([T;11]);
shuffleable!([T;12]);
shuffleable!([T;13]);
shuffleable!([T;14]);
shuffleable!([T;15]);
shuffleable!([T;16]);
shuffleable!([T;17]);
shuffleable!([T;18]);
shuffleable!([T;19]);
shuffleable!([T;20]);
shuffleable!([T;21]);
shuffleable!([T;22]);
shuffleable!([T;23]);
shuffleable!([T;24]);
shuffleable!([T;25]);
shuffleable!([T;26]);
shuffleable!([T;27]);
shuffleable!([T;28]);
shuffleable!([T;29]);
shuffleable!([T;30]);
shuffleable!([T;31]);
shuffleable!([T;32]);
impl<S : Strategy> Strategy for Shuffle<S>
where S::Value : Shuffleable {
type Tree = ShuffleValueTree<S::Tree>;
type Value = S::Value;
fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
let rng = runner.new_rng();
self.0.new_tree(runner).map(|inner| ShuffleValueTree {
inner, rng,
dist: Cell::new(None),
simplifying_inner: false,
})
}
}
#[derive(Clone, Debug)]
pub struct ShuffleValueTree<V> {
inner: V,
rng: TestRng,
dist: Cell<Option<num::usize::BinarySearch>>,
simplifying_inner: bool,
}
impl<V : ValueTree> ShuffleValueTree<V>
where V::Value : Shuffleable {
fn init_dist(&self, dflt: usize) -> usize {
if self.dist.get().is_none() {
self.dist.set(Some(num::usize::BinarySearch::new(dflt)));
}
self.dist.get().unwrap().current()
}
fn force_init_dist(&self) {
if self.dist.get().is_none() {
self.init_dist(self.current().shuffle_len());
}
}
}
impl<V : ValueTree> ValueTree for ShuffleValueTree<V>
where V::Value : Shuffleable {
type Value = V::Value;
fn current(&self) -> V::Value {
let mut value = self.inner.current();
let len = value.shuffle_len();
let max_swap = self.init_dist(len);
if 0 == len || 0 == max_swap { return value; }
let mut rng = self.rng.clone();
for start_index in 0..len - 1 {
let end_index = rng.gen_range(start_index + 1, len);
if end_index - start_index <= max_swap {
value.shuffle_swap(start_index, end_index);
}
}
value
}
fn simplify(&mut self) -> bool {
if self.simplifying_inner {
self.inner.simplify()
} else {
self.force_init_dist();
if self.dist.get_mut().as_mut().unwrap().simplify() {
true
} else {
self.simplifying_inner = true;
self.inner.simplify()
}
}
}
fn complicate(&mut self) -> bool {
if self.simplifying_inner {
self.inner.complicate()
} else {
self.force_init_dist();
self.dist.get_mut().as_mut().unwrap().complicate()
}
}
}
#[cfg(test)]
mod test {
use std::borrow::ToOwned;
use std::collections::HashSet;
use std::i32;
use crate::collection;
use crate::strategy::just::Just;
use super::*;
static VALUES: &'static [i32] = &[
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
];
#[test]
fn generates_different_permutations() {
let mut runner = TestRunner::default();
let mut seen = HashSet::<Vec<i32>>::new();
let input = Just(VALUES.to_owned()).prop_shuffle();
for _ in 0..1024 {
let mut value = input.new_tree(&mut runner).unwrap().current();
assert!(seen.insert(value.clone()),
"Value {:?} generated more than once", value);
value.sort();
assert_eq!(VALUES, &value[..]);
}
}
#[test]
fn simplify_reduces_shuffle_amount() {
let mut runner = TestRunner::default();
let input = Just(VALUES.to_owned()).prop_shuffle();
for _ in 0..1024 {
let mut value = input.new_tree(&mut runner).unwrap();
let mut prev_dist = i32::MAX;
loop {
let v = value.current();
let mut dist = 0;
for (ix, &nominal) in v.iter().enumerate() {
dist += (nominal - ix as i32).abs();
}
assert!(dist <= prev_dist,
"dist = {}, prev_dist = {}", dist, prev_dist);
prev_dist = dist;
if !value.simplify() {
break
}
}
assert_eq!(0, prev_dist);
}
}
#[test]
fn simplify_complicate_contract_upheld() {
check_strategy_sanity(
collection::vec(0i32..1000, 5..10).prop_shuffle(), None);
}
}