algorithms_fourth 0.1.10

//! 《算法 第四版》书中大部分算法的rust实现  

pub mod search;
pub mod sort;
pub use sort::*;
pub mod digraph;
pub mod graph;
pub use digraph::bellman_for_sp;
pub use search::boyer_moore;
pub use search::kmp;
pub use search::rabin_karp;
pub use search::red_black_search;
pub use string::nfa;
pub mod io;
pub mod string;
#[macro_export]
macro_rules! fill_vec_with {
    // $(...),+ 包围起来，就可以匹配一个或多个用逗号隔开的表达式
    ($vec:expr,$x:expr, $count:expr) => {
        for _ in 0..$count {
            $vec.push($x);
        }
    };
}
/// 生成Vec，用特定数目的默认值填充
#[macro_export]
macro_rules! generate_vec_with {
    ($x:expr, $count:expr) => {{
        let mut vec = Vec::with_capacity($count);
        $crate::fill_vec_with!(vec, $x, $count);
        vec
    }};
}
#[cfg(test)]
mod tests {
    // use super::*;
    use rand::{self, seq::SliceRandom};

    use crate::sort;
    #[test]
    fn heap_sort() {
        let mut data = set_up();
        // data = vec![4, 2, 1, 3];
        sort::heap_sort(&mut data);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "merge sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn merge_sort() {
        let mut data = set_up();
        // data = vec![4,2,1];
        sort::merge_sort(&mut data);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "merge sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn quick_sort_for_three_direction() {
        let mut data = set_up();
        // data = vec![4,2,1];
        let len = data.len() - 1;
        sort::quick_sort_for_three_direction(&mut data, 0, len);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "quick sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn quick_sort() {
        let mut data = set_up();
        // data = vec![4,2,1];
        let len = data.len() - 1;
        sort::quick_sort(&mut data, 0, len);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "quick sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn shell_sort() {
        let mut data = set_up();
        sort::shell_sort(&mut data);
        // println!("{:?}",data);
        assert!(is_sorted(&data), "shell sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn insert_sort() {
        let mut data = set_up();
        sort::insert_sort(&mut data);
        // println!("{:?}",data);
        assert!(is_sorted(&data), "insert sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn bubble_sort() {
        let mut data = set_up();
        sort::bubble_sort(&mut data);
        // println!("{:?}",data);
        assert!(is_sorted(&data), "bubble sort failed");
        // assert!([1,2].is_sorted());
    }

    fn set_up() -> Vec<i32> {
        let mut data: Vec<i32> = (1..10000).collect();
        let mut rng = rand::thread_rng();
        data.shuffle(&mut rng);
        // data.reverse();
        data
    }
    fn is_sorted(data: &[i32]) -> bool {
        let mut ans = true;
        let sential = data.len() - 1;
        for i in 0..sential {
            // print!("{} ",i);
            if data[i + 1] < data[i] {
                ans = false;
                break;
            }
        }
        ans
    }
}