tep_lib/common/
tree.rs

1/// Overview: Tree to match substring with rule.
2use std::collections::HashMap;
3
4use super::rule::Rule;
5
6pub struct Tree {
7    rules: Vec<Rule>,
8    rules_from_chars: Vec<Vec<char>>,
9    nodes: Vec<Node>,
10}
11
12impl Tree {
13    pub fn from(rules: Vec<Rule>) -> Tree {
14        // Improve performance for custom string matching.
15        let rules_from_chars = rules
16            .iter()
17            .map(|rule| rule.from.chars().collect())
18            .collect();
19
20        let mut tree = Tree {
21            rules,
22            rules_from_chars,
23            nodes: Vec::new(),
24        };
25
26        tree.nodes.push(Node {
27            rule_index: None,
28            children_map: HashMap::new(),
29        });
30
31        for index in 0..tree.rules.len() {
32            tree.add(index);
33        }
34
35        tree
36    }
37
38    fn add(&mut self, rule_index: usize) {
39        let from = &self.rules_from_chars[rule_index];
40        let mut current_index = 0usize;
41
42        for ch in from {
43            current_index = match self.nodes[current_index].children_map.get(ch) {
44                Some(&index) => index,
45                None => {
46                    // "index" will be the index of following node.
47                    let index = self.nodes.len();
48                    self.nodes[current_index].children_map.insert(*ch, index);
49                    self.nodes.push(Node {
50                        rule_index: None,
51                        children_map: HashMap::new(),
52                    });
53                    index
54                }
55            };
56        }
57
58        self.nodes[current_index].rule_index = Some(rule_index);
59    }
60
61    pub fn query(&self, chars: &[char], start: usize, chars_len: usize) -> Option<(&str, usize)> {
62        let mut pivot = start;
63        let mut depth = 0usize;
64        let mut current_index = 0usize;
65        let mut rule_index: Option<usize> = None;
66
67        while pivot < chars_len {
68            match self.nodes[current_index].children_map.get(&chars[pivot]) {
69                Some(&index) => {
70                    current_index = index;
71                    if let Some(i) = self.nodes[current_index].rule_index {
72                        rule_index = Some(i);
73                    }
74                }
75                None => break,
76            }
77
78            pivot += 1;
79            depth += 1;
80        }
81
82        rule_index.map(|index| (self.rules[index].to, depth))
83    }
84}
85
86struct Node {
87    pub rule_index: Option<usize>,
88    pub children_map: HashMap<char, usize>,
89}
tep_lib/common/tree.rs

tep_lib/common/
tree.rs
