//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#[allow(unused_imports)]
use crate::s4;

pub const SECTIONS: &[fn()] = &[
    section_1, section_2, section_3, section_4, section_5, section_6,
];

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// Computes the mean and the standard deviation of a sequence of real values.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// a (mean, standard_deviation) pair is provided.
///
/// This version uses two passes and explicit loops.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::stats_v1 as stats;
/// use s4prg::s4;
/// assert_eq!(stats(&[]), None);
/// let (m, d) = stats(&[1.0, 2.0, 3.0]).unwrap();
/// let expected_m = 2.0;
/// let expected_d = 0.816497;
/// let eps = 1e-6;
/// s4::assert_float_eq!(m, expected_m, eps);
/// s4::assert_float_eq!(d, expected_d, eps);
/// ```
pub fn stats_v1(values: &[f32]) -> Option<(f32, f32)> {
    let n = values.len() as f32;
    if n > 0.0 {
        let mut mean = 0.0;
        for v in values.iter() {
            mean += v;
        }
        mean /= n;
        let mut variance = 0.0;
        for v in values.iter() {
            let delta = v - mean;
            variance += delta * delta;
        }
        variance /= n;
        Some((mean, variance.sqrt()))
    } else {
        None
    }
}

/// Computes the mean and the standard deviation of a sequence of real values.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// a (mean, standard_deviation) pair is provided.
///
/// This version uses two passes and the idiomatic (functional) style.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::stats_v1bis as stats;
/// use s4prg::s4;
/// assert_eq!(stats(&[]), None);
/// let (m, d) = stats(&[1.0, 2.0, 3.0]).unwrap();
/// let expected_m = 2.0;
/// let expected_d = 0.816497;
/// let eps = 1e-6;
/// s4::assert_float_eq!(m, expected_m, eps);
/// s4::assert_float_eq!(d, expected_d, eps);
/// ```
pub fn stats_v1bis(values: &[f32]) -> Option<(f32, f32)> {
    let n = values.len() as f32;
    if n > 0.0 {
        let mean = values.iter().sum::<f32>() / n;
        let variance = values
            .iter()
            .map(|v| {
                let delta = v - mean;
                delta * delta
            })
            .sum::<f32>()
            / n;
        Some((mean, variance.sqrt()))
    } else {
        None
    }
}

/// Computes the mean and the standard deviation of a sequence of real values.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// a (mean, standard_deviation) pair is provided.
///
/// This version uses only one pass but experiences some
/// [numerical stability problems](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Na%C3%AFve_algorithm).
///
/// # Examples
/// ```
/// use s4prg::chapter_3::stats_v2 as stats;
/// use s4prg::s4;
/// assert_eq!(stats(&[]), None);
/// let (m, d) = stats(&[1.0, 2.0, 3.0]).unwrap();
/// let expected_m = 2.0;
/// let expected_d = 0.816497;
/// let eps = 1e-6;
/// s4::assert_float_eq!(m, expected_m, eps);
/// s4::assert_float_eq!(d, expected_d, eps);
/// ```
pub fn stats_v2(values: &[f32]) -> Option<(f32, f32)> {
    // one pass
    let n = values.len() as f32;
    if n > 0.0 {
        let mut accum = 0.0;
        let mut sqr_accum = 0.0;
        for v in values.iter() {
            accum += v;
            sqr_accum += v * v;
        }
        let mean = accum / n;
        let variance = sqr_accum / n - mean * mean;
        Some((mean, variance.sqrt()))
    } else {
        None
    }
}

/// Computes the mean and the standard deviation of a sequence of real values.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// a (mean, standard_deviation) pair is provided.
///
/// This version uses only one pass but tries to mitigate the numerical
/// stability problems by computing with `f64` reals.  
///
/// # Examples
/// ```
/// use s4prg::chapter_3::stats_v3 as stats;
/// use s4prg::s4;
/// assert_eq!(stats(&[]), None);
/// let (m, d) = stats(&[1.0, 2.0, 3.0]).unwrap();
/// let expected_m = 2.0;
/// let expected_d = 0.816497;
/// let eps = 1e-6;
/// s4::assert_float_eq!(m, expected_m, eps);
/// s4::assert_float_eq!(d, expected_d, eps);
/// ```
pub fn stats_v3(values: &[f32]) -> Option<(f32, f32)> {
    // one pass
    let n = values.len() as f64;
    if n > 0.0 {
        let mut accum = 0.0;
        let mut sqr_accum = 0.0;
        for v in values.iter().map(|v| *v as f64) {
            accum += v;
            sqr_accum += v * v;
        }
        let mean = accum / n;
        let variance = (sqr_accum - accum * accum / n) / n;
        Some((mean as f32, variance.sqrt() as f32))
    } else {
        None
    }
}

/// Computes the mean and the standard deviation of a sequence of real values.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// a (mean, standard_deviation) pair is provided.
///
/// This version uses only one pass and mitigates the numerical stability
/// problems, according to [Welford's algorithm](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm).
///
/// # Examples
/// ```
/// use s4prg::chapter_3::stats_v4 as stats;
/// use s4prg::s4;
/// assert_eq!(stats(&[]), None);
/// let (m, d) = stats(&[1.0, 2.0, 3.0]).unwrap();
/// let expected_m = 2.0;
/// let expected_d = 0.816497;
/// let eps = 1e-6;
/// s4::assert_float_eq!(m, expected_m, eps);
/// s4::assert_float_eq!(d, expected_d, eps);
/// ```
pub fn stats_v4(values: &[f32]) -> Option<(f32, f32)> {
    let mut values_iter = values.iter();
    if let Some(first) = values_iter.next() {
        let mut mean = *first;
        let mut variance = 0.0;
        let mut n = 0.0;
        for v in values.iter() {
            n += 1.0;
            let delta = v - mean;
            mean += delta / n;
            variance += delta * (v - mean);
        }
        variance /= n;
        Some((mean, variance.sqrt()))
    } else {
        None
    }
}

fn section_1() {
    println!("\n~~~~ chapter 3, section 1 ~~~~");
    let mut rng = s4::Rng::new();
    let mut counts = [0.0_f32; 100];
    for _ in 0..100_000_000_usize {
        counts[rng.range(0, counts.len())] += 1.0;
    }
    let mut min_pos = 0;
    let mut max_pos = 0;
    for (pos, elem) in counts.iter().enumerate() {
        if *elem < counts[min_pos] {
            min_pos = pos;
        } else if *elem > counts[max_pos] {
            max_pos = pos;
        }
    }
    println!("min {} at index {}", counts[min_pos], min_pos);
    println!("max {} at index {}", counts[max_pos], max_pos);
    let delta = counts[max_pos] - counts[min_pos];
    let mid = (counts[max_pos] + counts[min_pos]) / 2.0;
    println!("delta: {:.2} %", 100.0 * delta / mid);
    let s1 = stats_v1(&counts);
    println!("v1 {:?}", s1);
    let s1bis = stats_v1bis(&counts);
    println!("v1bis {:?}", s1bis);
    let s2 = stats_v2(&counts);
    println!("v2 {:?}", s2);
    let s3 = stats_v3(&counts);
    println!("v3 {:?}", s3);
    let s4 = stats_v4(&counts);
    println!("v4 {:?}", s4);
    //
    let bm = s4::Benchmark::new("stats");
    bm.record("v1, two passes", 2.0, |t| {
        s4::bm_call!(t, stats_v1(&counts));
    });
    bm.record("v1bis, two passes (idiomatic)", 2.0, |t| {
        s4::bm_call!(t, stats_v1bis(&counts));
    });
    bm.record("v2, one pass (unstable)", 2.0, |t| {
        s4::bm_call!(t, stats_v2(&counts));
    });
    bm.record("v3, one pass (via f64)", 2.0, |t| {
        s4::bm_call!(t, stats_v3(&counts));
    });
    bm.record("v4, one pass (stable)", 2.0, |t| {
        s4::bm_call!(t, stats_v4(&counts));
    });
    println!("{}", bm);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// strings and a vector of occurrences.
///
/// This version expects a shared slice on the input sequence, but provides
/// owned strings, which implies the cloning of each string.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v1 as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let (words, occurrences) = split_word_occurrences(&word_occurrences);
/// assert_eq!(words.len(), word_occurrences.len());
/// assert_eq!(occurrences.len(), word_occurrences.len());
/// for (((w1, o1), w2), o2) in
///     word_occurrences.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v1(
    word_occurrences: &[(String, u64)]
) -> (Vec<String>, Vec<u64>) {
    let mut words = Vec::new();
    let mut occurrences = Vec::new();
    for (word, occurrence) in word_occurrences.iter() {
        words.push(word.clone());
        occurrences.push(*occurrence);
    }
    (words, occurrences)
}

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// strings and a vector of occurrences.
///
/// This version consumes the input sequence in order to transfer the
/// strings into the resulting vector.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v2 as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let len = word_occurrences.len();
/// let saved = word_occurrences.clone(); // in order to check afterwards
/// let (words, occurrences) = split_word_occurrences(word_occurrences);
/// assert_eq!(words.len(), saved.len());
/// assert_eq!(occurrences.len(), saved.len());
/// for (((w1, o1), w2), o2) in
///     saved.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v2(
    word_occurrences: Vec<(String, u64)>
) -> (Vec<String>, Vec<u64>) {
    let mut words = Vec::new();
    let mut occurrences = Vec::new();
    for (word, occurrence) in word_occurrences.into_iter() {
        words.push(word);
        occurrences.push(occurrence);
    }
    (words, occurrences)
}

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// strings and a vector of occurrences.
///
/// This version consumes the input sequence in order to transfer the
/// strings into the resulting vector.  
/// It considers the predictable length of the resulting vectors
/// in order to allocate their storage once for all (instead of many
/// reallocations.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v2bis as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let len = word_occurrences.len();
/// let saved = word_occurrences.clone(); // in order to check afterwards
/// let (words, occurrences) = split_word_occurrences(word_occurrences);
/// assert_eq!(words.len(), saved.len());
/// assert_eq!(occurrences.len(), saved.len());
/// for (((w1, o1), w2), o2) in
///     saved.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v2bis(
    word_occurrences: Vec<(String, u64)>
) -> (Vec<String>, Vec<u64>) {
    let mut words = Vec::with_capacity(word_occurrences.len());
    let mut occurrences = Vec::with_capacity(word_occurrences.len());
    for (word, occurrence) in word_occurrences.into_iter() {
        words.push(word);
        occurrences.push(occurrence);
    }
    (words, occurrences)
}

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// strings and a vector of occurrences.
///
/// This version consumes the input sequence in order to transfer the
/// strings into the resulting vector.
/// It uses the idiomatic (functional) style.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v3 as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let len = word_occurrences.len();
/// let saved = word_occurrences.clone(); // in order to check afterwards
/// let (words, occurrences) = split_word_occurrences(word_occurrences);
/// assert_eq!(words.len(), saved.len());
/// assert_eq!(occurrences.len(), saved.len());
/// for (((w1, o1), w2), o2) in
///     saved.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v3(
    word_occurrences: Vec<(String, u64)>
) -> (Vec<String>, Vec<u64>) {
    word_occurrences.into_iter().unzip()
}

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// string-slices and a vector of occurrences.
///
/// This version expects a shared slice on the input sequence and provides
/// string-slices refering to these input strings.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v4 as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let (words, occurrences) = split_word_occurrences(&word_occurrences);
/// assert_eq!(words.len(), word_occurrences.len());
/// assert_eq!(occurrences.len(), word_occurrences.len());
/// for (((w1, o1), w2), o2) in
///     word_occurrences.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v4(
    word_occurrences: &[(String, u64)]
) -> (Vec<&str>, Vec<u64>) {
    let mut words = Vec::new();
    let mut occurrences = Vec::new();
    for (word, occurrence) in word_occurrences.iter() {
        words.push(word.as_str());
        occurrences.push(*occurrence);
    }
    (words, occurrences)
}

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// string-slices and a vector of occurrences.
///
/// This version expects a shared slice on the input sequence and provides
/// string-slices refering to these input strings.  
/// It considers the predictable length of the resulting vectors
/// in order to allocate their storage once for all (instead of many
/// reallocations.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v4bis as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let (words, occurrences) = split_word_occurrences(&word_occurrences);
/// assert_eq!(words.len(), word_occurrences.len());
/// assert_eq!(occurrences.len(), word_occurrences.len());
/// for (((w1, o1), w2), o2) in
///     word_occurrences.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v4bis(
    word_occurrences: &[(String, u64)]
) -> (Vec<&str>, Vec<u64>) {
    let mut words = Vec::with_capacity(word_occurrences.len());
    let mut occurrences = Vec::with_capacity(word_occurrences.len());
    for (word, occurrence) in word_occurrences.iter() {
        words.push(word.as_str());
        occurrences.push(*occurrence);
    }
    (words, occurrences)
}

/// Splits a sequence of (word, occurrences) tuples into a vector of
/// string-slices and a vector of occurrences.
///
/// This version expects a shared slice on the input sequence and provides
/// string-slices refering to these input strings.  
/// It uses the idiomatic (functional) style.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::split_word_occurrences_v5 as split_word_occurrences;
/// use s4prg::s4;
/// let word_occurrences = s4::load_word_occurrences();
/// let (words, occurrences) = split_word_occurrences(&word_occurrences);
/// assert_eq!(words.len(), word_occurrences.len());
/// assert_eq!(occurrences.len(), word_occurrences.len());
/// for (((w1, o1), w2), o2) in
///     word_occurrences.iter().zip(words.iter()).zip(occurrences.iter()) {
///     assert_eq!(w1, w2);
///     assert_eq!(o1, o2);
/// }
/// ```
pub fn split_word_occurrences_v5(
    word_occurrences: &[(String, u64)]
) -> (Vec<&str>, Vec<u64>) {
    word_occurrences
        .iter()
        .map(|(w, o)| (w.as_str(), *o))
        .unzip()
}

fn section_2() {
    println!("\n~~~~ chapter 3, section 2 ~~~~");
    let word_occurrences = s4::load_word_occurrences();
    println!("word_occurrences: {}", word_occurrences.len(),);
    let (w1, o1) = split_word_occurrences_v1(&word_occurrences);
    println!("v1: {} {}", w1.len(), o1.len());
    let (w2, o2) = split_word_occurrences_v2(word_occurrences.clone());
    println!("v2: {} {}", w2.len(), o2.len());
    let (w2b, o2b) = split_word_occurrences_v2bis(word_occurrences.clone());
    println!("v2bis: {} {}", w2b.len(), o2b.len());
    let (w3, o3) = split_word_occurrences_v3(word_occurrences.clone());
    println!("v3: {} {}", w3.len(), o3.len());
    let (w4, o4) = split_word_occurrences_v4(&word_occurrences);
    println!("v4: {} {}", w4.len(), o4.len());
    let (w4b, o4b) = split_word_occurrences_v4bis(&word_occurrences);
    println!("v4bis: {} {}", w4b.len(), o4b.len());
    let (w5, o5) = split_word_occurrences_v5(&word_occurrences);
    println!("v5: {} {}", w5.len(), o5.len());
    //
    let bm = s4::Benchmark::new("split_word_occurrences");
    bm.record("v1, clone", 2.0, |t| {
        s4::bm_call!(t, split_word_occurrences_v1(&word_occurrences));
    });
    bm.record("v2, consume", 2.0, |t| {
        let word_occurrences = word_occurrences.clone(); // not measured
        s4::bm_call!(t, split_word_occurrences_v2(word_occurrences));
    });
    bm.record("v2bis, consume (capacity)", 2.0, |t| {
        let word_occurrences = word_occurrences.clone(); // not measured
        s4::bm_call!(t, split_word_occurrences_v2bis(word_occurrences));
    });
    bm.record("v3, consume (idiomatic)", 2.0, |t| {
        let word_occurrences = word_occurrences.clone(); // not measured
        s4::bm_call!(t, split_word_occurrences_v3(word_occurrences));
    });
    bm.record("v4, string-slices", 2.0, |t| {
        s4::bm_call!(t, split_word_occurrences_v4(&word_occurrences));
    });
    bm.record("v4bis, string-slices (capacity)", 2.0, |t| {
        s4::bm_call!(t, split_word_occurrences_v4bis(&word_occurrences));
    });
    bm.record("v5, string-slices (idiomatic)", 2.0, |t| {
        s4::bm_call!(t, split_word_occurrences_v5(&word_occurrences));
    });
    println!("{}", bm);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// Tells if a word is a palindrome.
///
/// This version expects an owned string, which is totally
/// inappropriate.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::is_palindrome_v1 as is_palindrome;
/// assert!(is_palindrome("été".to_owned()));
/// assert!(!is_palindrome("summer".to_owned()));
/// assert!(is_palindrome("kayak".to_owned()));
/// assert!(!is_palindrome("steamboat".to_owned()));
/// ```
pub fn is_palindrome_v1(word: String) -> bool {
    let chars = Vec::from_iter(word.chars());
    let length = chars.len();
    for i in 0..length / 2 {
        if chars[i] != chars[length - 1 - i] {
            return false;
        }
    }
    true
}

/// Tells if a word is a palindrome.
///
/// This version expects a string-slice, which is perfectly enough.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::is_palindrome_v2 as is_palindrome;
/// assert!(is_palindrome("été"));
/// assert!(!is_palindrome("summer"));
/// assert!(is_palindrome("kayak"));
/// assert!(!is_palindrome("steamboat"));
/// ```
pub fn is_palindrome_v2(word: &str) -> bool {
    let chars = Vec::from_iter(word.chars());
    let length = chars.len();
    for i in 0..length / 2 {
        if chars[i] != chars[length - 1 - i] {
            return false;
        }
    }
    true
}

/// Tells if a word is a palindrome.
///
/// This version expects a string-slice, which is perfectly enough.  
/// It uses the idiomatic (functional) style.  
/// Note that there is no need to determine the length of the string
/// since the middle is reached in very occasional cases.  
/// This versions offers a performance gain since there is no need
/// to allocate a vector of chars.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::is_palindrome_v3 as is_palindrome;
/// assert!(is_palindrome("été"));
/// assert!(!is_palindrome("summer"));
/// assert!(is_palindrome("kayak"));
/// assert!(!is_palindrome("steamboat"));
/// ```
pub fn is_palindrome_v3(word: &str) -> bool {
    let forwards = word.chars();
    let backwards = word.chars().rev();
    forwards.zip(backwards).all(|(f, b)| f == b)
}

/// Tells if a word is a palindrome.
///
/// This version expects a string-slice, which is perfectly enough.  
/// It uses the idiomatic (functional) style.  
/// An attempt to stop the iterations at the middle of the string
/// is made, but is detrimental to performances since a complete
/// iteration is needed to determine the number of chars.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::is_palindrome_v3bis as is_palindrome;
/// assert!(is_palindrome("été"));
/// assert!(!is_palindrome("summer"));
/// assert!(is_palindrome("kayak"));
/// assert!(!is_palindrome("steamboat"));
/// ```
pub fn is_palindrome_v3bis(word: &str) -> bool {
    let mid = word.chars().count() / 2;
    let forwards = word.chars();
    let backwards = word.chars().rev();
    forwards.zip(backwards).take(mid).all(|(f, b)| f == b)
}

fn section_3() {
    println!("\n~~~~ chapter 3, section 3 ~~~~");
    let words = ["été", "summer", "kayak", "steamboat"];
    for word in words.iter() {
        println!("v1: {:?} ~~> {}", word, is_palindrome_v1(word.to_string()));
        println!("v2: {:?} ~~> {}", word, is_palindrome_v2(word));
        println!("v3: {:?} ~~> {}", word, is_palindrome_v3(word));
        println!("v3bis: {:?} ~~> {}", word, is_palindrome_v3bis(word));
    }
    //
    let word_occurrences = s4::load_word_occurrences();
    let bm = s4::Benchmark::new("is_palindrome");
    bm.record("v1, owned+clone", 2.0, |t| {
        for (word, _occurrence) in word_occurrences.iter() {
            s4::bm_call!(t, is_palindrome_v1(word.clone()));
        }
    });
    bm.record("v1, owned", 2.0, |t| {
        for (word, _occurrence) in word_occurrences.iter() {
            let word = word.clone(); // not measured
            s4::bm_call!(t, is_palindrome_v1(word));
        }
    });
    bm.record("v2, string-slice", 2.0, |t| {
        for (word, _occurrence) in word_occurrences.iter() {
            s4::bm_call!(t, is_palindrome_v2(word));
        }
    });
    bm.record("v3, string-slice (idiomatic)", 2.0, |t| {
        for (word, _occurrence) in word_occurrences.iter() {
            s4::bm_call!(t, is_palindrome_v3(word));
        }
    });
    bm.record("v3bis, string-slice (idiomatic, middle)", 2.0, |t| {
        for (word, _occurrence) in word_occurrences.iter() {
            s4::bm_call!(t, is_palindrome_v3bis(word));
        }
    });
    println!("{}", bm);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// Tells if a sequence of words is sorted.
///
/// This version directly compares words at consecutive indices.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::words_are_sorted_v1 as words_are_sorted;
/// let empty = [];
/// let one = ["alone"];
/// let sorted = ["any", "bier", "cures", "dehydration"];
/// let mixed = ["one", "two", "three", "four"];
/// assert!(words_are_sorted(&empty));
/// assert!(words_are_sorted(&one));
/// assert!(words_are_sorted(&sorted));
/// assert!(!words_are_sorted(&mixed));
/// ```
pub fn words_are_sorted_v1(words: &[&str]) -> bool {
    for i in 1..words.len() {
        if words[i - 1] > words[i] {
            return false;
        }
    }
    true
}

/// Tells if a sequence of words is sorted.
///
/// This version builds two iterators on the sequence, offset by one.  
/// A locked step progression through these two iterators detects if any
/// pait of words is not ordered.  
/// It uses the idiomatic (functional) style.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::words_are_sorted_v2 as words_are_sorted;
/// let empty = [];
/// let one = ["alone"];
/// let sorted = ["any", "bier", "cures", "dehydration"];
/// let mixed = ["one", "two", "three", "four"];
/// assert!(words_are_sorted(&empty));
/// assert!(words_are_sorted(&one));
/// assert!(words_are_sorted(&sorted));
/// assert!(!words_are_sorted(&mixed));
/// ```
pub fn words_are_sorted_v2(words: &[&str]) -> bool {
    let it1 = words.iter();
    let it2 = words.iter().skip(1);
    it1.zip(it2).all(|(w1, w2)| w1 <= w2)
}

/// Tells if a sequence of words is sorted.
///
/// This version generates a sliding window of two words over the sequence
/// and detects if any window is not ordered.  
/// It uses the idiomatic (functional) style.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::words_are_sorted_v3 as words_are_sorted;
/// let empty = [];
/// let one = ["alone"];
/// let sorted = ["any", "bier", "cures", "dehydration"];
/// let mixed = ["one", "two", "three", "four"];
/// assert!(words_are_sorted(&empty));
/// assert!(words_are_sorted(&one));
/// assert!(words_are_sorted(&sorted));
/// assert!(!words_are_sorted(&mixed));
/// ```
pub fn words_are_sorted_v3(words: &[&str]) -> bool {
    words.windows(2).all(|w| w[0] <= w[1])
}

fn section_4() {
    println!("\n~~~~ chapter 3, section 4 ~~~~");
    let sorted = ["any", "bier", "cures", "dehydration"];
    let mixed = ["one", "two", "three", "four"];
    println!("v1: {:?} ~~> {}", sorted, words_are_sorted_v1(&sorted));
    println!("v2: {:?} ~~> {}", sorted, words_are_sorted_v2(&sorted));
    println!("v3: {:?} ~~> {}", sorted, words_are_sorted_v3(&sorted));
    println!("v1: {:?}  ~~> {}", mixed, words_are_sorted_v1(&mixed));
    println!("v2: {:?}  ~~> {}", mixed, words_are_sorted_v2(&mixed));
    println!("v3: {:?}  ~~> {}", mixed, words_are_sorted_v3(&mixed));
    //
    let word_occurrences = s4::load_word_occurrences();
    let (words, _occurrences) = split_word_occurrences_v5(&word_occurrences);
    let bm = s4::Benchmark::new("words_are_sorted");
    bm.record("v1, index", 2.0, |t| {
        s4::bm_call!(t, words_are_sorted_v1(&words));
    });
    bm.record("v2, two iterators", 2.0, |t| {
        s4::bm_call!(t, words_are_sorted_v2(&words));
    });
    bm.record("v3, window", 2.0, |t| {
        s4::bm_call!(t, words_are_sorted_v3(&words));
    });
    println!("{}", bm);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// Finds the position of the minimal word in a sequence.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// the index in the sequence is provided.
///
/// This version directly compares words at different indices.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::min_word_pos_v1 as min_word_pos;
/// let empty = [];
/// let italian = ["uno", "due", "tre", "quattro"];
/// let english = ["one", "two", "three", "four"];
/// assert_eq!(min_word_pos(&empty), None);
/// assert_eq!(min_word_pos(&italian), Some(1));
/// assert_eq!(min_word_pos(&english), Some(3));
/// ```
pub fn min_word_pos_v1(words: &[&str]) -> Option<usize> {
    if !words.is_empty() {
        let mut min_pos = 0;
        for pos in 1..words.len() {
            if words[pos] < words[min_pos] {
                min_pos = pos;
            }
        }
        Some(min_pos)
    } else {
        None
    }
}

/// Finds the position of the minimal word in a sequence.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// the index in the sequence is provided.
///
/// This version uses the idiomatic (functional) style on an
/// enumeration of words provided by an iterator.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::min_word_pos_v2 as min_word_pos;
/// let empty = [];
/// let italian = ["uno", "due", "tre", "quattro"];
/// let english = ["one", "two", "three", "four"];
/// assert_eq!(min_word_pos(&empty), None);
/// assert_eq!(min_word_pos(&italian), Some(1));
/// assert_eq!(min_word_pos(&english), Some(3));
/// ```
pub fn min_word_pos_v2(words: &[&str]) -> Option<usize> {
    words
        .iter()
        .enumerate()
        .min_by_key(|(_pos, elem)| *elem)
        .map(|(pos, _elem)| pos)
}

/// Finds the position of the minimal word in a sequence.
///
/// In case the sequence is empty, `None` is returned, otherwise
/// the index in the sequence is provided.
///
/// This version makes extensive use of `Option`, which seems
/// to be highly optimisable.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::min_word_pos_v3 as min_word_pos;
/// let empty = [];
/// let italian = ["uno", "due", "tre", "quattro"];
/// let english = ["one", "two", "three", "four"];
/// assert_eq!(min_word_pos(&empty), None);
/// assert_eq!(min_word_pos(&italian), Some(1));
/// assert_eq!(min_word_pos(&english), Some(3));
/// ```
pub fn min_word_pos_v3(words: &[&str]) -> Option<usize> {
    let mut min_pos_opt = None;
    let mut min_word_opt = None;
    for (pos, word) in words.iter().enumerate() {
        let update_min = match min_word_opt {
            Some(min_word) => word < min_word,
            None => true,
        };
        if update_min {
            min_word_opt = Some(word);
            min_pos_opt = Some(pos);
        }
    }
    min_pos_opt
}

fn section_5() {
    println!("\n~~~~ chapter 3, section 5 ~~~~");
    let italian = ["uno", "due", "tre", "quattro"];
    let english = ["one", "two", "three", "four"];
    println!("v1: {:?} ~~> {:?}", italian, min_word_pos_v1(&italian));
    println!("v1: {:?} ~~> {:?}", english, min_word_pos_v1(&english));
    println!("v2: {:?} ~~> {:?}", italian, min_word_pos_v2(&italian));
    println!("v2: {:?} ~~> {:?}", english, min_word_pos_v2(&english));
    println!("v3: {:?} ~~> {:?}", italian, min_word_pos_v3(&italian));
    println!("v3: {:?} ~~> {:?}", english, min_word_pos_v3(&english));
    //
    let word_occurrences = s4::load_word_occurrences();
    let (mut words, _occurrences) =
        split_word_occurrences_v5(&word_occurrences);
    let mut rng = s4::Rng::new();
    let bm = s4::Benchmark::new("min_word_pos");
    bm.record("v1, index", 2.0, |t| {
        rng.shuffle(&mut words); // not measured
        s4::bm_call!(t, min_word_pos_v1(&words));
    });
    bm.record("v2, iterator", 2.0, |t| {
        rng.shuffle(&mut words); // not measured
        s4::bm_call!(t, min_word_pos_v2(&words));
    });
    bm.record("v3, option", 2.0, |t| {
        rng.shuffle(&mut words); // not measured
        s4::bm_call!(t, min_word_pos_v3(&words));
    });
    println!("{}", bm);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// Sorts a sequence of words.
///
/// This version uses the
/// [selection-sort](https://en.wikipedia.org/wiki/Selection_sort)
/// algorithm.  
/// It swaps the word at each successive index in the sequence
/// with the minimal word found in the remaining of the sequence.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::sort_words_v1 as sort_words;
/// let sorted = ["four", "one", "three", "two"];
/// let mut mixed = ["one", "two", "three", "four"];
/// sort_words(&mut mixed);
/// assert_eq!(mixed, sorted);
/// ```
pub fn sort_words_v1(words: &mut [&str]) {
    for pos in 0..words.len() {
        if let Some(min_pos) = min_word_pos_v3(&words[pos..]) {
            words.swap(pos, pos + min_pos);
        }
    }
}

/// Sorts a sequence of words.
///
/// This version uses the standard `.sort()` function of the slice.
///
/// # Examples
/// ```
/// use s4prg::chapter_3::sort_words_v2 as sort_words;
/// let sorted = ["four", "one", "three", "two"];
/// let mut mixed = ["one", "two", "three", "four"];
/// sort_words(&mut mixed);
/// assert_eq!(mixed, sorted);
/// ```
pub fn sort_words_v2(words: &mut [&str]) {
    // words.sort()
    words.sort_unstable()
}

fn section_6() {
    println!("\n~~~~ chapter 3, section 6 ~~~~");
    let mixed = ["one", "two", "three", "four"];
    let mut words1 = mixed;
    sort_words_v1(&mut words1);
    println!("v1: {:?} ~~> {:?}", mixed, words1);
    let mut words2 = mixed;
    sort_words_v2(&mut words2);
    println!("v2: {:?} ~~> {:?}", mixed, words2);
    //
    let word_occurrences = s4::load_word_occurrences();
    let (mut words, _occurrences) =
        split_word_occurrences_v5(&word_occurrences);
    for size in [words.len(), 10000, 1000, 100, 10] {
        words.truncate(size);
        let mut rng = s4::Rng::new();
        let bm = s4::Benchmark::new(format!("sort_words {}", size));
        bm.record("v1, selection", 2.0, |t| {
            rng.shuffle(&mut words); // not measured
            s4::bm_call!(t, sort_words_v1(&mut words));
        });
        bm.record("v2, standard", 2.0, |t| {
            rng.shuffle(&mut words); // not measured
            s4::bm_call!(t, sort_words_v2(&mut words));
        });
        println!("{}", bm);
    }
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#[allow(unused_imports)]
use s4prg::{chapter_3::*, s4};

#[test]
fn chapter_3_section_1() {
    let mut rng = s4::Rng::new();
    let values =
        Vec::from_iter((0..1000).map(|_| rng.number::<f32>() * 100.0));
    // https://en.wikipedia.org/wiki/Continuous_uniform_distribution
    // width = 1    variance = 1/12    std_dev = 0.2886751345948129
    let (m1, s1) = stats_v1(&values).unwrap();
    let (m1bis, s1bis) = stats_v1bis(&values).unwrap();
    let (m2, s2) = stats_v2(&values).unwrap();
    let (m3, s3) = stats_v3(&values).unwrap();
    let (m4, s4) = stats_v4(&values).unwrap();
    let eps = 1e-3;
    s4::assert_float_eq!(m1, m1bis, eps);
    s4::assert_float_eq!(s1, s1bis, eps);
    s4::assert_float_eq!(m1bis, m2, eps);
    s4::assert_float_eq!(s1bis, s2, eps);
    s4::assert_float_eq!(m2, m3, eps);
    s4::assert_float_eq!(s2, s3, eps);
    s4::assert_float_eq!(m3, m4, eps);
    s4::assert_float_eq!(s3, s4, eps);
}

#[test]
fn chapter_3_section_2() {
    let word_occurrences = s4::load_word_occurrences();
    let r1 = split_word_occurrences_v1(&word_occurrences);
    let r2 = split_word_occurrences_v2(word_occurrences.clone());
    let r2bis = split_word_occurrences_v2bis(word_occurrences.clone());
    let r3 = split_word_occurrences_v3(word_occurrences.clone());
    let r4 = split_word_occurrences_v4(&word_occurrences);
    let r4bis = split_word_occurrences_v4bis(&word_occurrences);
    let r5 = split_word_occurrences_v5(&word_occurrences);
    assert_eq!(r1, r2);
    assert_eq!(r2, r2bis);
    assert_eq!(r2bis, r3);
    assert_eq!(r3.0, r4.0);
    assert_eq!(r3.1, r4.1);
    assert_eq!(r4, r4bis);
    assert_eq!(r4bis, r5);
}

#[test]
fn chapter_3_section_3() {
    let word_occurrences = s4::load_word_occurrences();
    for (word, _occurrences) in word_occurrences.iter() {
        let r1 = is_palindrome_v1(word.clone());
        let r2 = is_palindrome_v2(word);
        let r3 = is_palindrome_v3(word);
        let r3bis = is_palindrome_v3bis(word);
        assert_eq!(r1, r2);
        assert_eq!(r2, r3);
        assert_eq!(r3, r3bis);
    }
}

#[test]
fn chapter_3_section_4() {
    let empty = [];
    let one = ["alone"];
    let sorted = ["any", "bier", "cures", "dehydration"];
    let mixed = ["one", "two", "three", "four"];
    let word_occurrences = s4::load_word_occurrences();
    let (many, _occurrences) = split_word_occurrences_v5(&word_occurrences);
    for words in [many.as_slice(), &empty, &one, &sorted, &mixed] {
        let r1 = words_are_sorted_v1(words);
        let r2 = words_are_sorted_v2(words);
        let r3 = words_are_sorted_v3(words);
        assert_eq!(r1, r2);
        assert_eq!(r2, r3);
    }
}

#[test]
fn chapter_3_section_5() {
    let word_occurrences = s4::load_word_occurrences();
    let (mut words, _occurrences) =
        split_word_occurrences_v5(&word_occurrences);
    let mut rng = s4::Rng::new();
    rng.shuffle(&mut words);
    let r1 = min_word_pos_v1(&words);
    let r2 = min_word_pos_v2(&words);
    let r3 = min_word_pos_v3(&words);
    assert_eq!(r1, r2);
    assert_eq!(r2, r3);
}

#[test]
fn chapter_3_section_6() {
    let word_occurrences = s4::load_word_occurrences();
    let (mut w1, _occurrences) = split_word_occurrences_v5(&word_occurrences);
    let mut rng = s4::Rng::new();
    rng.shuffle(&mut w1);
    w1.truncate(1000);
    let mut w2 = w1.clone();
    sort_words_v1(&mut w1);
    sort_words_v2(&mut w2);
    assert_eq!(w1, w2);
    assert!(words_are_sorted_v3(&w1));
    assert!(words_are_sorted_v3(&w2));
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~