tree_automata/bottom_up/
search.rs

1use std::rc::Rc;
2use terms::Term;
3use crate::{Symbol, State, Label, Labeled};
4use crate::utils::combinations;
5use super::{Automaton, Configuration, Configurations};
6
7/// Common configurations searcher.
8pub struct CommonConfigurations<'a, F: Symbol, Q: State, L: Label> {
9    automata: &'a [&'a Automaton<F, Q, L>],
10    positions: &'a [Q],
11    iterators: Vec<Configurations<'a, F, Q, L>>,
12    configurations: Vec<Labeled<Configuration<F, Q>, L>>,
13    // pattern: P
14}
15
16impl<'a, F: Symbol, Q: State, L: Label> CommonConfigurations<'a, F, Q, L> {
17    pub fn new(
18        automata: &'a [&'a Automaton<F, Q, L>],
19        positions: &'a [Q]
20    ) -> CommonConfigurations<'a, F, Q, L>
21    {
22        // println!("looking for common confs: {:?} {:?}", positions, patterns);
23
24        let mut iterators = Vec::with_capacity(positions.len());
25        if !positions.is_empty() {
26            iterators.push(automata[0].configurations_for_state(&positions[0]))
27        };
28
29        CommonConfigurations {
30            automata: automata,
31            positions: positions,
32            iterators: iterators,
33            configurations: Vec::with_capacity(positions.len())
34        }
35    }
36}
37
38impl<'a, F: Symbol, Q: State, L: Label> Iterator for CommonConfigurations<'a, F, Q, L> {
39    type Item = Vec<Labeled<Configuration<F, Q>, L>>;
40
41    fn next(&mut self) -> Option<Self::Item> {
42        if self.positions.is_empty() {
43            None
44        } else {
45            while self.configurations.len() < self.positions.len() {
46                let i = self.configurations.len();
47                let j = i + 1;
48
49                match self.iterators.last_mut().unwrap().next() {
50                    Some((Configuration(f, sub_states), label)) => {
51                        if self.configurations.is_empty() || f == self.configurations.first().unwrap().0.symbol() {
52                            if j < self.positions.len() {
53                                let it = self.automata[j].configurations_for_state(&self.positions[j]);
54                                // println!("new it");
55                                self.iterators.push(it);
56                            }
57                            self.configurations.push((Configuration(f.clone(), sub_states.clone()), label.clone()))
58                        }
59                    },
60                    None => {
61                        match self.configurations.pop() {
62                            Some(_) => {
63                                if i < self.positions.len() {
64                                    // println!("drop it");
65                                    self.iterators.pop();
66                                }
67                            },
68                            None => {
69                                // println!("no other common confs.");
70                                return None
71                            }
72                        }
73                    }
74                }
75            }
76
77            let result = self.configurations.clone();
78            self.configurations.pop();
79            Some(result)
80        }
81    }
82}
83
84#[derive(Clone)]
85struct VisitedTransitions<'a, F: Symbol, Q: State, L: Label> {
86    previously_visited: Option<Rc<VisitedTransitions<'a, F, Q, L>>>,
87    conf: &'a Configuration<F, Q>,
88    label: &'a L,
89    q: &'a Q
90}
91
92impl<'a, F: Symbol, Q: State, L: Label> VisitedTransitions<'a, F, Q, L> {
93    fn new(previously_visited: &Option<Rc<VisitedTransitions<'a, F, Q, L>>>, conf: &'a Configuration<F, Q>, label: &'a L, q: &'a Q) -> VisitedTransitions<'a, F, Q, L> {
94        VisitedTransitions {
95            previously_visited: previously_visited.clone(),
96            conf: conf,
97            label: label,
98            q: q
99        }
100    }
101
102    fn contains(&self, conf: &'a Configuration<F, Q>, label: &'a L, q: &'a Q) -> bool {
103        // println!("compare {:?} -{:?}-> {:?} and {:?} -{:?}-> {:?}", self.conf, self.label, self.q, conf, label, q);
104        if self.q == q && self.label == label && self.conf == conf {
105            // println!("visited");
106            true
107        } else {
108            match &self.previously_visited {
109                Some(previously_visited) => previously_visited.contains(conf, label, q),
110                None => false
111            }
112        }
113    }
114}
115
116pub struct Representatives<'a, F: Symbol, Q: State, L: Label> {
117    automaton: &'a Automaton<F, Q, L>,
118    visited_transitions: Option<Rc<VisitedTransitions<'a, F, Q, L>>>,
119    pending_states: Vec<&'a Q>,
120    current_state: Option<(&'a Q, Configurations<'a, F, Q, L>)>,
121    current_configuration: Option<(&'a F, Box<dyn Iterator<Item=Vec<Term<F>>> + 'a>)>
122}
123
124impl<'a, F: Symbol, Q: State, L: Label> Representatives<'a, F, Q, L> {
125    pub fn new(aut: &'a Automaton<F, Q, L>) -> Representatives<'a, F, Q, L> {
126        let mut pending_states: Vec<&'a Q> = aut.final_states.iter().collect();
127        let current_state = match pending_states.pop() {
128            Some(q) => Some((q, aut.configurations_for_state(q))),
129            None => None
130        };
131        Representatives {
132            automaton: aut,
133            visited_transitions: None,
134            pending_states: pending_states,
135            current_state: current_state,
136            current_configuration: None
137        }
138    }
139
140    pub fn visited(&self, conf: &'a Configuration<F, Q>, label: &'a L, q: &'a Q) -> bool {
141        match &self.visited_transitions {
142            Some(visited_transitions) => visited_transitions.contains(conf, label, q),
143            None => false
144        }
145    }
146}
147
148impl<'a, F: Symbol, Q: State, L: Label> Iterator for Representatives<'a, F, Q, L> {
149    type Item = Term<F>;
150
151    fn next(&mut self) -> Option<Term<F>> {
152        loop {
153            match self.current_configuration {
154                Some((f, ref mut iterator)) => {
155                    match iterator.next() {
156                        Some(sub_terms) => {
157                            return Some(Term::new(f.clone(), sub_terms))
158                        },
159                        None => self.current_configuration = None
160                    }
161                },
162                None => {
163                    match self.current_state {
164                        Some((q, ref mut configurations)) => {
165                            match configurations.next() {
166                                Some((conf, label)) => {
167                                    if !self.visited(conf, label, q) {
168                                        let aut = self.automaton;
169                                        let visited_transitions = Some(Rc::new(VisitedTransitions::new(&self.visited_transitions, conf, label, q)));
170                                        let sub_terms_it = combinations(conf.states(), move |q| Representatives {
171                                            automaton: aut,
172                                            visited_transitions: visited_transitions.clone(),
173                                            pending_states: Vec::new(),
174                                            current_state: Some((q, aut.configurations_for_state(q))),
175                                            current_configuration: None
176                                        });
177                                        // println!("conf: {:?}", conf);
178                                        self.current_configuration = Some((conf.symbol(), Box::new(sub_terms_it)));
179                                    }
180                                },
181                                None => self.current_state = None
182                            }
183                        },
184                        None => {
185                            match self.pending_states.pop() {
186                                Some(q) => {
187                                    self.current_state = Some((q, self.automaton.configurations_for_state(q)))
188                                },
189                                None => return None
190                            }
191                        }
192                    }
193                }
194            }
195        }
196    }
197}
tree_automata/bottom_up/search.rs

tree_automata/bottom_up/
search.rs
