Skip to main content

lekhani_parser/
trie.rs

1//! Compact L1 Prefix Trie for Fast Phonetic Pattern Matching
2
3pub const NO_PATTERN: u16 = u16::MAX;
4pub const NO_NODE: u16 = u16::MAX;
5
6#[derive(Debug, Clone)]
7pub struct TrieNode {
8    pub pattern_idx: u16,
9    pub children: [u16; 128],
10}
11
12impl Default for TrieNode {
13    fn default() -> Self {
14        Self {
15            pattern_idx: NO_PATTERN,
16            children: [NO_NODE; 128],
17        }
18    }
19}
20
21#[derive(Debug, Clone)]
22pub struct PatternTrie {
23    pub nodes: Vec<TrieNode>,
24    pub max_depth: usize,
25}
26
27impl Default for PatternTrie {
28    fn default() -> Self {
29        Self::new()
30    }
31}
32
33impl PatternTrie {
34    pub fn new() -> Self {
35        let mut trie = Self {
36            nodes: Vec::with_capacity(384),
37            max_depth: 0,
38        };
39        // Allocate root node (node 0)
40        trie.nodes.push(TrieNode::default());
41        trie
42    }
43
44    /// Insert an ASCII pattern into the Trie
45    pub fn insert(&mut self, pattern_bytes: &[u8], pattern_idx: u16) {
46        let mut current_idx: usize = 0;
47        let mut depth = 0;
48
49        for &b in pattern_bytes {
50            let ascii_idx = (b & 0x7F) as usize;
51            let next_idx = self.nodes[current_idx].children[ascii_idx];
52
53            if next_idx == NO_NODE {
54                let new_idx = self.nodes.len() as u16;
55                self.nodes.push(TrieNode::default());
56                self.nodes[current_idx].children[ascii_idx] = new_idx;
57                current_idx = new_idx as usize;
58            } else {
59                current_idx = next_idx as usize;
60            }
61            depth += 1;
62        }
63
64        self.nodes[current_idx].pattern_idx = pattern_idx;
65        if depth > self.max_depth {
66            self.max_depth = depth;
67        }
68    }
69
70    /// Find the longest matching pattern prefix starting at `start` in `input`.
71    /// Returns `Some((pattern_index, match_len))` or `None`.
72    #[inline(always)]
73    pub fn longest_match(&self, input: &[u8], start: usize) -> Option<(u16, usize)> {
74        let len = input.len();
75        if start >= len {
76            return None;
77        }
78
79        let mut current_node = 0usize;
80        let mut best_match: Option<(u16, usize)> = None;
81        let limit = (start + self.max_depth).min(len);
82
83        let mut offset = start;
84        while offset < limit {
85            let b = input[offset];
86            if b >= 128 {
87                break;
88            }
89            let next_node = self.nodes[current_node].children[b as usize];
90            if next_node == NO_NODE {
91                break;
92            }
93            current_node = next_node as usize;
94            let pat_idx = self.nodes[current_node].pattern_idx;
95            if pat_idx != NO_PATTERN {
96                best_match = Some((pat_idx, offset - start + 1));
97            }
98            offset += 1;
99        }
100
101        best_match
102    }
103}