generalized_suffix_tree/iter/
edge_iter.rs

1use crate::suffix_node::node::*;
2use crate::suffix_node::Node;
3use super::node_iter::PostOrdNodes;
4
5#[cfg(feature = "non_crypto_hash")]
6use fxhash::FxHashMap as HashMap;
7#[cfg(not(feature = "non_crypto_hash"))]
8use std::collections::HashMap;
9
10use std::hash::Hash;
11use std::fmt::{Display, Debug};
12
13pub struct PostOrdEdges<T: PartialEq + Display + Debug + PartialOrd>
14{
15    node_iter: PostOrdNodes<T>,
16    s_links: HashMap<NodeID, NodeID>,
17    parents: HashMap<NodeID, NodeID>,
18    stack: Vec<(NodeID, NodeID)>
19}
20
21impl<T> PostOrdEdges<T>
22where
23    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
24{
25    pub fn new(start_node_id: &NodeID, nodes: &HashMap<NodeID, Node<T>>, s_links: HashMap<NodeID, NodeID>, parents: HashMap<NodeID, NodeID>)->Self{
26        Self {
27            node_iter: PostOrdNodes::new(start_node_id, nodes),
28            s_links: s_links.into_iter()
29                            .filter(|(_k, v)| v!=&0)
30                            .map(|(k, v)| (v, k))
31                            .collect(),
32            parents,
33            stack: Vec::new()
34        }
35    }
36
37    pub fn len(&self)->usize{
38        self.parents.len()+self.s_links.len()-1
39    }
40
41    pub fn is_empty(&self)->bool{
42        self.len()==0
43    }
44}
45
46impl<T> Iterator for PostOrdEdges<T>
47where
48    T: Display + Debug + Eq + PartialEq + Hash + Clone + PartialOrd
49{
50    type Item = (NodeID, NodeID);
51
52    fn next(&mut self) -> Option<Self::Item> {
53        match self.stack.pop(){
54            Some(edge) => Some(edge),
55            None => {
56                match self.node_iter.next(){
57                    Some(node_id) => {
58                        let node_id_parent = self.parents.get(&node_id).unwrap();
59                        if let Some(slink_node_id) = self.s_links.get(&node_id) { self.stack.push((*slink_node_id, node_id)) }
60                        Some((*node_id_parent, node_id))
61                    },
62                    None => None
63                }
64            }
65        }
66    }
67}
generalized_suffix_tree/iter/edge_iter.rs

generalized_suffix_tree/iter/
edge_iter.rs
