generalized_suffix_tree/iter/
node_iter.rs

1use crate::suffix_node::node::*;
2use crate::suffix_node::Node;
3
4#[cfg(feature = "non_crypto_hash")]
5use fxhash::FxHashMap as HashMap;
6#[cfg(not(feature = "non_crypto_hash"))]
7use std::collections::HashMap;
8
9use std::hash::Hash;
10use crate::data::tree_item::Character;
11use core::fmt::{Debug, Display};
12use itertools::Itertools;
13
14pub struct EulerWalk<T: PartialEq + Display + Debug + PartialOrd>
15{
16    stack: Vec<NodeID>,
17    nodes: HashMap<NodeID, HashMap<Character<T>, NodeID>>
18}
19
20impl<T> EulerWalk<T>
21where
22    T: Display + Debug + Eq + PartialEq + PartialOrd + Hash + Clone
23{
24    pub fn new(start_node_id: &NodeID, nodes: &HashMap<NodeID, Node<T>>)->Self{
25        Self { stack:vec![*start_node_id], nodes: nodes.iter().map(|(edge_label, child_node)| {
26            (*edge_label, child_node.get_children().clone())
27        }).collect::<HashMap<NodeID, HashMap<Character<T>, NodeID>>>() }
28    }
29}
30
31impl<T> Iterator for EulerWalk<T>
32where
33    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
34{
35    type Item = NodeID;
36
37    fn next(&mut self)->Option<Self::Item>{
38        match self.stack.pop() {
39            Some(node_id) => {
40                let children_ids:Vec<&NodeID> = self.nodes.get(&node_id).expect("Invalid Node ID!").values().collect();
41                for child_node_id in children_ids.into_iter().sorted(){
42                    self.stack.push(*child_node_id);
43                    self.stack.push(node_id);
44            }
45            Some(node_id)
46            }
47            None => None,
48        }
49    }
50}
51
52pub struct PreOrdNodes<T: PartialEq + Display + Debug + PartialOrd>
53{
54    stack: Vec<NodeID>,
55    nodes: HashMap<NodeID, HashMap<Character<T>, NodeID>>
56}
57
58impl<T> PreOrdNodes<T>
59where
60    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
61{
62    pub fn new(start_node_id: &NodeID, nodes: &HashMap<NodeID, Node<T>>)->Self{
63        Self { stack:vec![*start_node_id], nodes: nodes.iter().map(|(edge_label, child_node)| {
64            (*edge_label, child_node.get_children().clone())
65        }).collect::<HashMap<NodeID, HashMap<Character<T>, NodeID>>>() }
66    }
67}
68
69impl<T> Iterator for PreOrdNodes<T>
70where
71    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
72{
73    type Item = NodeID;
74
75    fn next(&mut self)->Option<Self::Item>{
76        match self.stack.pop() {
77            Some(node_id) => {
78                let children_ids:Vec<&NodeID> = self.nodes.get(&node_id).expect("Invalid Node ID!").values().collect();
79                for child_node_id in children_ids.into_iter().sorted(){
80                    self.stack.push(*child_node_id)
81            }
82            Some(node_id)
83            }
84            None => None,
85        }
86    }
87}
88
89pub struct PostOrdNodes<T: PartialEq + Display + Debug + PartialOrd>
90{
91    stack: Vec<NodeID>,
92    nodes: HashMap<NodeID, HashMap<Character<T>, NodeID>>
93}
94
95impl<T> PostOrdNodes<T>
96where
97    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
98{
99    pub fn new(start_node_id: &NodeID, nodes: &HashMap<NodeID, Node<T>>)->Self{
100        Self { stack:vec![*start_node_id], nodes: nodes.iter().map(|(edge_label, child_node)| {
101            (*edge_label, child_node.get_children().clone())
102        }).collect::<HashMap<NodeID, HashMap<Character<T>, NodeID>>>() }
103    }
104}
105
106impl<T> Iterator for PostOrdNodes<T>
107where
108    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
109{
110    type Item = NodeID;
111
112    fn next(&mut self)->Option<Self::Item>{
113        while let Some(node_id) = self.stack.pop()  {
114            if self.nodes.contains_key(&node_id){
115                self.stack.push(node_id);
116                let children = self.nodes.remove(&node_id).unwrap();
117                for child_id in children.values().sorted(){
118                    self.stack.push(*child_id)
119                }
120            }
121            else{
122                return Some(node_id)
123            }
124        }
125        None
126    }
127}
generalized_suffix_tree/iter/node_iter.rs

generalized_suffix_tree/iter/
node_iter.rs
