algorithms_fourth 0.1.10

//! NFA 非确定性有限状态自动机
//! # 使用
//! ```
//!     use algorithms_fourth::string::nfa::NFA;
//!         let nfa = NFA::new("(abc*d*|de.)".to_string());
//!         assert!(nfa.recognizes("abccdd"));
//!         assert!(nfa.recognizes("abcccc"));
//!         assert!(!nfa.recognizes("abce"));
//!         assert!(nfa.recognizes("abc"));
//!         assert!(nfa.recognizes("abd"));
//!         assert!(!nfa.recognizes("abf"));
//!         assert!(!nfa.recognizes("de"));
//!         assert!(nfa.recognizes("de."));
//!         assert!(nfa.recognizes("def"));
//!         assert!(!nfa.recognizes("deff"));
//!         assert!(nfa.recognizes("abccdd"));
//!         assert!(nfa.recognizes("abdd"));
//!
//! ```
//!
//! # 原理
//! <pre>
//! 1. 状态机本质上是图，所以构造有向图的规则是重点
//! 2. 有向图有现成的可达点搜索方法，比如深度优先路径搜索。为了效率，只有
//! 必要且不需要消耗字符即可达的点间构造边，其他点与点间的前进方向用索引获取
//! 3. 简单的正则规则（其后表示紧跟着）：
//!     3.a. (): 串
//!     3.b. *:跟在)或字符后，表示0次或多次
//!     3.c. (|): 或
//!     3.d, .: 匹配任一字符
//! 4. 根据2、3，边的构造规则:
//!     4.1. ( 与其后的字符连接
//!     4.2. ( 与(|)中的|其后的字符连接
//!     4.3. )与其后的字符连接
//!     4.4. )与其后的*连接
//!     4.5. 字符与其后的*连接
//!     4.6. *与前边的字符连接
//!     4.7. *与)对应的(连接
//!     4.7. *与后边的字符连接
//!     4.8. *与后边的(连接
//!     4.8. ｜与前边(对应的)连接
//! 5. 识别匹配:
//!     5.1. 状态图的起点为0，用图的路径可达算法获取可达的状态位置集合pc
//!     5.2. 依次遍历txt中的字符c，如果c与pc中的点v对应的字符（如果是字符）匹配，则状态v+1,是下一轮的状态点之一，
//!     用当前获取的下一轮状态点通过路径可达算法检索，获取下一轮的所有状态点
//!     5.3. 当没有下一轮状态点或txt字符遍历完后下一轮的状态点中没有终点时，说明不匹配，否则匹配成功
//!     
//! </pre>

use crate::digraph::{directed_dfs::DirectedDFS, Digraph};
const DEBUG: bool = false;
pub struct NFA {
    re: String,
    g: Digraph,
    m: usize,
}
impl NFA {
    pub fn new(regexp: String) -> Self {
        let mut ops = vec![];
        let m = regexp.len();
        let mut g = Digraph::new(m + 1);
        let re = regexp.as_bytes();
        for (i, c) in re.iter().enumerate() {
            // 当前项的左边位置
            let mut lp = i;
            match c {
                b'(' | b'|' => {
                    ops.push(i);
                }
                b')' => {
                    let or = ops.pop().expect(")一定对应一个(,所以这里一定非none");
                    // (|) 表示或
                    if re[or] == b'|' {
                        lp = ops.pop().expect("该位置一定是(");
                        assert_eq!(re[lp], b'(');
                        g.add_edge(lp, or + 1);
                        g.add_edge(or, i);
                    } else {
                        lp = or;
                    }
                }
                _ => {}
            }
            let after_p = i + 1;
            if re.get(after_p) == Some(&b'*') {
                g.add_edge(lp, after_p);
                g.add_edge(after_p, lp);
            }
            match c {
                b'(' | b'*' | b')' => {
                    g.add_edge(i, after_p);
                }
                _ => {}
            }
        }
        if !ops.is_empty() {
            panic!("ops:{:?}", ops)
        }
        if DEBUG {
            print_nfs(re, &g);
        }
        NFA { re: regexp, g, m }
    }
    pub fn recognizes(&self, txt: &str) -> bool {
        // 当前到达的位置信息
        let mut pc = vec![];
        let mut dfs: DirectedDFS = DirectedDFS::new(&self.g, 0);
        for v in 0..self.g.vertex_count() {
            if dfs.marked(v) {
                pc.push(v);
            }
        }
        for i in 0..txt.len() {
            let mut match_info = vec![];
            for &v in pc.iter() {
                if let Some(&c) = self.re.as_bytes().get(v) {
                    if c == txt.as_bytes()[i] || c == b'.' {
                        match_info.push(v + 1);
                    }
                }
            }
            pc = vec![];
            dfs = DirectedDFS::new2(&self.g, match_info.iter());
            for v in 0..self.g.vertex_count() {
                if dfs.marked(v) {
                    pc.push(v);
                }
            }
            if pc.is_empty() {
                return false;
            }
        }
        pc.iter().any(|&v| v == self.m)
    }
}

pub fn print_nfs(re: &[u8], g: &Digraph) {
    let mut labes = vec![];
    for &c in re {
        labes.push(char::from(c).to_string());
    }
    labes.push("end".to_string());
    g.print_dot_with("re.dot", Some(labes));
}
#[cfg(test)]
mod test {
    use crate::string::nfa::NFA;

    #[test]
    fn test() {
        let nfa = NFA::new("(abc*d*|de.)".to_string());
        assert!(nfa.recognizes("abccdd"));
        assert!(nfa.recognizes("abcccc"));
        assert!(!nfa.recognizes("abce"));
        assert!(nfa.recognizes("abc"));
        assert!(nfa.recognizes("abd"));
        assert!(!nfa.recognizes("abf"));
        assert!(!nfa.recognizes("de"));
        assert!(nfa.recognizes("de."));
        assert!(nfa.recognizes("def"));
        assert!(!nfa.recognizes("deff"));
        assert!(nfa.recognizes("abccdd"));
        assert!(nfa.recognizes("abdd"));
    }
}