fr_trie/
iterator.rs

1//! The Trie iterator based on a pushdown automata to perform lookup
2
3use crate::key::KeyPrefix;
4use crate::matcher::{Event, PushdownStateMachine, State};
5use crate::node::RFRNode;
6
7///! Tracks lookup
8struct LookupState<'a, K: 'a + KeyPrefix + Clone, V: 'a + Clone> {
9    node: &'a RFRNode<K, V>,
10    current_child_idx: usize,
11    key_char_pos: usize,
12}
13
14///! The iterator implementation
15pub struct TrieIterator<'a, K: 'a + KeyPrefix + Clone, V: 'a + Clone, M: PushdownStateMachine + Clone> {
16    stack: Vec<LookupState<'a, K, V>>,
17    match_key_chars: Vec<char>,
18    matcher_sm: M
19}
20
21impl <'a, K: KeyPrefix + Clone, V: Clone, M: PushdownStateMachine + Clone> TrieIterator<'a, K, V, M> {
22
23    ///! Creates a new iterator
24    pub fn new(root: &'a RFRNode<K, V>, match_key: &K) -> Self {
25        let it = Self {
26            stack: vec![LookupState {
27                node: root,
28                current_child_idx: 0,
29                key_char_pos: 0,
30            }],
31            match_key_chars: match_key.key_chars(),
32            matcher_sm: M::new(),
33        };
34        it
35    }
36}
37
38impl <'a, K: 'a + KeyPrefix + Clone, V: 'a + Clone, M: PushdownStateMachine + Clone> Iterator for TrieIterator<'a, K, V, M> {
39    type Item = V;
40
41    /// Consume iterator
42    fn next(&mut self) -> Option<Self::Item> {
43        loop {
44            match self.stack.pop() {
45                None => { // No more work to do
46                    return None;
47                }
48                Some(ls) => {
49
50                    if ls.current_child_idx >= ls.node.children.len() {
51                        // No (more) children. Give up at this level
52                        break;
53                    }
54
55                    let child = ls.node.children.get(ls.current_child_idx).unwrap();
56                    self.matcher_sm.step_in(&child.node_key.seq);
57                    let mut advanced = 0 as usize;
58                    for ch in self.match_key_chars[ls.key_char_pos..].iter() {
59                        if self.matcher_sm.is_sink() {
60                            break;
61                        }
62                        self.matcher_sm.feed(Event::CharIn(*ch));
63                        advanced += 1;
64                        if !self.matcher_sm.accepts_more() {
65                            break;
66                        }
67                    }
68                    if ls.key_char_pos + advanced == self.match_key_chars.len() {
69                        if !self.matcher_sm.is_sink() { // Flush (be always greedy)
70                            self.matcher_sm.feed(Event::EndOfStream);
71                        }
72
73                    }
74                    match self.matcher_sm.state() {
75                        State::Accepting | State::Expecting => {
76                            self.stack.push(LookupState {
77                                node: child,
78                                current_child_idx: 0,
79                                key_char_pos: ls.key_char_pos + advanced
80                            });
81                        }
82                        State::Accepted => {
83                            self.matcher_sm.step_out();
84                            self.stack.push(LookupState {
85                                node: ls.node,
86                                current_child_idx: ls.current_child_idx + 1,
87                                key_char_pos: ls.key_char_pos
88                            });
89                            return match &child.value {
90                                None => {
91                                    None
92                                },
93                                Some(v) => {
94                                    Some(v.clone())
95                                }
96                            }
97                        }
98                        State::Rejected => {
99                            self.matcher_sm.step_out();
100                            self.stack.push(LookupState {
101                                node: ls.node,
102                                current_child_idx: ls.current_child_idx + 1,
103                                key_char_pos: ls.key_char_pos
104                            });
105                        }
106                        State::Beyond => {
107                            return None // Won't find anything beyond
108                        }
109                        State::Failure(reason) => {
110                            panic!("Internal error: {}", reason);
111                        }
112                    }
113                }
114            }
115        }
116        return None;
117    }
118}
fr_trie/iterator.rs

fr_trie/
iterator.rs
