algorithms_fourth 0.1.10

//! 第三章：搜索算法
pub mod binary_search;
pub mod binary_tree_search;
pub mod linear_probing_hash;
pub mod red_black_search;
pub mod separate_chaining_hash;
pub mod sequential;
pub mod trie;
pub mod tst;
pub mod kmp;
pub mod boyer_moore;
pub mod rabin_karp;
pub trait ST<K: PartialOrd, V> {
    fn put(&mut self, key: K, value: V);
    fn get(&self, key: &K) -> Option<&V>;
    fn delete(&mut self, key: &K);
    fn contains(&self, key: &K) -> bool {
        self.get(key).is_some()
    }
    fn is_empty(&self) -> bool;
    fn size(&self) -> usize;
    fn min(&self) -> Option<&K>;
    fn max(&self) -> Option<&K>;
    /// 小于等于该值的键中的最大值
    fn floor(&self, key: &K) -> Option<&K>;
    /// 大于等于该值的键中的最小值
    fn ceiling(&self, key: &K) -> Option<&K>;
    /// 小于key的键的数量
    fn rank(&self, key: &K) -> usize;
    /// 从小到大排序，第k个位置的键值(从0开始)
    fn select(&self, k: usize) -> Option<&K>;
    fn delete_min(&mut self) {
        if let Some(min) = self.min() {
            let min = unsafe { (min as *const K).as_ref().unwrap() };
            self.delete(min);
        }
    }
    fn delete_max(&mut self) {
        if let Some(max) = self.max() {
            let max = unsafe { (max as *const K).as_ref().unwrap() };
            self.delete(max);
        }
    }
    //    [lo..hi] 之间的键的数量
    fn size_in(&self, lo: &K, hi: &K) -> usize {
        if hi < lo {
            0
        } else if self.contains(hi) {
            self.rank(hi) - self.rank(lo) + 1
        } else {
            self.rank(hi) - self.rank(lo)
        }
    }
    // fn keys(&self) -> box<dyn iterator<item = &k>> {
    //     if !self.is_empty() {
    //     return self.keys_in(self.min(), self.max());
    //     }else{

    //     }
    // }
    //fn keys_in(&self, lo: &k, hi: &k) -> box<dyn iterator<item = &k>>;
}

#[cfg(test)]
mod test {
    use std::fs;

    use rand::seq::SliceRandom;

    use super::{
        binary_search::BinarySearchST,
        binary_tree_search::BST,
        linear_probing_hash::LinearProbingHashST,
        red_black_search::trace::TraceRedBlackBST,
        red_black_search::{trace, RedBlackBST},
        separate_chaining_hash::SeparateChainingHashST,
        sequential::SequentialSearchST,
        ST,
    };

    #[test]
    fn test_sequential_search_st() {
        let st: Box<dyn ST<usize, usize>> = Box::<SequentialSearchST<usize, usize>>::default();
        test_st(st);
    }

    #[test]
    fn test_linear_probing_hash_search_st() {
        let st: Box<dyn ST<usize, usize>> = Box::<LinearProbingHashST<usize, usize>>::default();
        test_st(st);
    }
    #[test]
    fn test_separate_chaining_hash_search_st() {
        let st: Box<dyn ST<usize, usize>> = Box::new(SeparateChainingHashST::new(1));
        test_st(st);
    }
    #[test]
    fn test_binary_search() {
        let st: Box<dyn ST<usize, usize>> = Box::new(BinarySearchST::new(10));
        test_st(st);
    }
    #[test]
    fn test_red_black_search() {
        let st: Box<dyn ST<usize, usize>> = Box::new(RedBlackBST::new());
        test_st(st);
    }
    #[test]
    #[ignore = "用于打印红黑树的变化流程，非功能性测试函数"]
    fn test_loop_trace_red_black_search() {
        for _ in 1..100 {
            test_trace_red_black_search();
        }
    }
    #[test]
    #[ignore = "用于打印红黑树的变化流程，非功能性测试函数"]
    fn test_trace_red_black_search() {
        let mut st: Box<TraceRedBlackBST<usize, usize>> =
            Box::new(trace::new(RedBlackBST::new(), vec![]));
        let mut rng = rand::thread_rng();
        let n = 23;
        let mut arr: Vec<usize> = (1..=n).collect();
        arr.shuffle(&mut rng);
        for (i, key) in arr.iter().enumerate() {
            st.put(*key, key + 10);
            assert_eq!(st.size(), i + 1);
            assert!(st.is_balanced());
        }
        let mut arr: Vec<usize> = (1..=n).collect();
        arr.shuffle(&mut rng);
        for (i, key) in arr.iter().enumerate() {
            st.delete(key);
            // let _ = fs::write("trace.dot", st.get_graph());
            assert!(st.is_balanced());
            assert_eq!(st.size(), arr.len() - i - 1);
        }
        let _ = fs::write("trace.dot", st.get_graph());
        // println!("{}",st.get_graph());
    }
    #[test]
    fn test_binary_tree_search() {
        let st: Box<dyn ST<usize, usize>> = Box::<BST<usize, usize>>::default();
        test_st(st);
    }
    fn test_st(mut st: Box<dyn ST<usize, usize>>) {
        assert!(st.is_empty());
        for i in 1..=10 {
            st.put(i, i + 10);
            assert_eq!(st.size(), i);
        }
        for i in 1..=10 {
            assert_eq!(st.get(&i), Some(&(i + 10)));
            st.put(i, i);
        }
        assert!(!st.is_empty());
        assert_eq!(st.size(), 10);
        for i in 1..=10 {
            assert_eq!(st.size_in(&1, &i), { i });
            assert_eq!(st.size_in(&i, &i), 1);
            assert_eq!(st.size_in(&(i + 1), &i), 0);
            assert_eq!(st.rank(&i), i - 1);
            assert_eq!(st.size_in(&0, &i), { i });
            assert_eq!(st.floor(&i), Some(&i));
            assert_eq!(st.ceiling(&i), Some(&i));
            assert_eq!(st.select(i - 1), Some(&i));
        }
        assert_eq!(st.min(), Some(&1));
        assert_eq!(st.max(), Some(&10));
        st.delete_min();
        assert_eq!(st.size(), 9);
        assert_eq!(st.min(), Some(&2));
        st.delete_max();
        assert_eq!(st.size(), 8);
        assert_eq!(st.max(), Some(&9));
        st.delete(&5);
        assert_eq!(st.size(), 7);
        assert_eq!(st.floor(&5), Some(&4));
        assert_eq!(st.ceiling(&5), Some(&6));
        for i in (0..st.size()).rev() {
            if i % 2 == 0 {
                st.delete_min();
            } else {
                st.delete_max();
            }
            assert_eq!(st.size(), i);
        }
    }
}