trie_rs/iter/
search_iter.rs

1use crate::iter::PostfixIter;
2use crate::map::Trie;
3use crate::try_collect::{Collect, TryCollect, TryFromIterator};
4use louds_rs::LoudsNodeNum;
5use std::marker::PhantomData;
6
7#[derive(Debug, Clone)]
8/// Iterates through all the matches of a query.
9pub struct SearchIter<'a, Label, Value, C, M> {
10    prefix: Vec<Label>,
11    first: Option<(C, &'a Value)>,
12    postfix_iter: PostfixIter<'a, Label, Value, Vec<Label>, Collect>,
13    col: PhantomData<(C, M)>,
14}
15
16impl<'a, Label: Ord + Clone, Value, C, M> SearchIter<'a, Label, Value, C, M>
17where
18    C: TryFromIterator<Label, M> + Clone,
19{
20    pub(crate) fn new(trie: &'a Trie<Label, Value>, query: impl AsRef<[Label]>) -> Self {
21        let mut cur_node_num = LoudsNodeNum(1);
22        let mut prefix = Vec::new();
23
24        // Consumes query (prefix)
25        for chr in query.as_ref() {
26            let children_node_nums: Vec<_> = trie.children_node_nums(cur_node_num).collect();
27            let res = trie.bin_search_by_children_labels(chr, &children_node_nums[..]);
28            match res {
29                Ok(i) => cur_node_num = children_node_nums[i],
30                Err(_) => return Self::empty(trie),
31            }
32            prefix.push(trie.label(cur_node_num).clone());
33        }
34        // let prefix:  = prefix.into_iter().try_collect().expect("Could not collect");
35        let first = trie.value(cur_node_num).map(|v| {
36            (
37                prefix
38                    .clone()
39                    .into_iter()
40                    .try_collect()
41                    .expect("Could not collect"),
42                v,
43            )
44        });
45        SearchIter {
46            prefix,
47            first,
48            postfix_iter: PostfixIter::new(trie, cur_node_num),
49            col: PhantomData,
50        }
51    }
52
53    fn empty(trie: &'a Trie<Label, Value>) -> Self {
54        SearchIter {
55            prefix: Vec::new(),
56            first: None,
57            postfix_iter: PostfixIter::empty(trie),
58            col: PhantomData,
59        }
60    }
61}
62
63impl<'a, Label: Ord + Clone, Value, C, M> Iterator for SearchIter<'a, Label, Value, C, M>
64where
65    C: TryFromIterator<Label, M> + Clone,
66    Vec<Label>: TryFromIterator<Label, Collect>,
67{
68    type Item = (C, &'a Value);
69    #[inline]
70    fn next(&mut self) -> Option<Self::Item> {
71        match self.first.take() {
72            // None => None,
73            None => self.postfix_iter.next().map(|(postfix, v)| {
74                let entry = C::try_from_iter(self.prefix.clone().into_iter().chain(postfix))
75                    .expect("Could not collect postfix");
76                // let mut entry = self.prefix.clone();
77                // let ext: C = postfix.into_iter().try_collect().expect("Could not collect postfix");
78                // entry.extend([ext]);
79                (entry, v)
80            }),
81            x => x,
82        }
83    }
84}
85
86// impl<'a, Label: Ord + Clone, Value, C> Iterator for SearchIter<'a, Label, Value, C, Collect>
87// where C: TryFromIterator<Label, Collect> + Extend<Label> + Clone,
88// Vec<Label>: TryFromIterator<Label, Collect>
89// {
90//     type Item = (C, &'a Value);
91//     #[inline]
92//     fn next(&mut self) -> Option<Self::Item> {
93//         match self.first.take() {
94//             // None => None,
95//             None => self.postfix_iter.next().map(|(postfix, v)| {
96//                 let mut entry = self.prefix.clone();
97//                 entry.extend(postfix.into_iter());
98//                 (entry, v)
99//             }),
100//             x => x
101//         }
102//     }
103// }
104
105// impl<'a, Label: Ord, V> Value<V> for frayed::defray::Group<'a, SearchIter<'_, Label, V>> {
106//     fn value(&self) -> Option<&V> {
107//         self.parent.iter_ref().value()
108//     }
109// }
trie_rs/iter/search_iter.rs

trie_rs/iter/
search_iter.rs
