trie_rs/iter/
postfix_iter.rs

1use crate::map::Trie;
2use crate::try_collect::{TryCollect, TryFromIterator};
3use louds_rs::LoudsNodeNum;
4use std::marker::PhantomData;
5
6#[derive(Debug, Clone)]
7/// Iterates through all the postfixes of a matching query.
8pub struct PostfixIter<'a, Label, Value, C, M> {
9    trie: &'a Trie<Label, Value>,
10    queue: Vec<(usize, LoudsNodeNum)>,
11    buffer: Vec<&'a Label>,
12    value: Option<&'a Value>,
13    col: PhantomData<(C, M)>,
14}
15
16impl<'a, Label: Ord, Value, C, M> PostfixIter<'a, Label, Value, C, M>
17where
18    C: TryFromIterator<Label, M>,
19{
20    #[inline]
21    pub(crate) fn new(trie: &'a Trie<Label, Value>, root: LoudsNodeNum) -> Self {
22        let mut children: Vec<_> = trie.children_node_nums(root).map(|n| (0, n)).collect();
23        children.reverse();
24        Self {
25            trie,
26            queue: children,
27            buffer: Vec::new(),
28            value: None,
29            col: PhantomData,
30        }
31    }
32
33    #[inline]
34    pub(crate) fn empty(trie: &'a Trie<Label, Value>) -> Self {
35        Self {
36            trie,
37            queue: Vec::new(),
38            buffer: Vec::new(),
39            value: None,
40            col: PhantomData,
41        }
42    }
43}
44
45impl<'a, Label: Ord + Clone, Value, C, M> Iterator for PostfixIter<'a, Label, Value, C, M>
46where
47    C: TryFromIterator<Label, M>,
48{
49    type Item = (C, &'a Value);
50    #[inline]
51    fn next(&mut self) -> Option<Self::Item> {
52        use std::cmp::Ordering;
53        while self.value.is_none() {
54            if let Some((depth, node)) = self.queue.pop() {
55                let children = self.trie.children_node_nums(node);
56                self.queue
57                    .extend(children.rev().map(|child| (depth + 1, child)));
58                match depth.cmp(&self.buffer.len()) {
59                    Ordering::Equal => {
60                        self.buffer.push(self.trie.label(node));
61                    }
62                    Ordering::Less => {
63                        let _ = self.buffer.drain(depth + 1..);
64                        self.buffer[depth] = self.trie.label(node);
65                    }
66                    Ordering::Greater => {
67                        panic!("depth > buffer.len()");
68                    }
69                }
70                self.value = self.trie.value(node);
71            } else {
72                break;
73            }
74        }
75        if let Some(v) = self.value.take() {
76            Some((
77                self.buffer
78                    .iter()
79                    .cloned()
80                    .cloned()
81                    .try_collect()
82                    .expect("Could not collect"),
83                v,
84            ))
85        } else {
86            None
87        }
88    }
89}
90
91// impl<Label: Ord, V, C, M> Value<V> for PostfixIter<'_, Label, V, C, M> {
92//     fn value(&self) -> Option<&V> {
93//         self.value
94//     }
95// }
trie_rs/iter/postfix_iter.rs

trie_rs/iter/
postfix_iter.rs
