tree_automata/
inter.rs

1use std::fmt;
2use crate::{Language, Symbol, State, Label, Labeled};
3use crate::bottom_up::{Automaton, Configuration, CommonConfigurations};
4use crate::combinations;
5
6trait Inter<F>: Language<F> {
7    type Output: Language<F>;
8
9    fn inter(automata: &[&Self]) -> Self::Output;
10}
11
12#[derive(Clone, Debug, Hash, PartialEq, Eq)]
13pub struct Product<Q> {
14    states: Vec<Q>
15}
16
17impl<Q: fmt::Display> fmt::Display for Product<Q> {
18    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
19        match self.states.split_first() {
20            Some((head, tail)) => {
21                write!(f, "{}", head)?;
22                for q in tail.iter() {
23                    write!(f, "×{}", q)?;
24                }
25                Ok(())
26            },
27            None => Ok(())
28        }
29    }
30}
31
32impl<Q: Clone> Product<Q> {
33    pub fn new(states: &[Q]) -> Product<Q> {
34        Product {
35            states: states.iter().map(|q| q.clone()).collect()
36        }
37    }
38
39    fn configurations<'a, F: Symbol, L: Label>(&'a self, automata: &'a [&'a Automaton<F, Q, L>]) -> ProductConfigurations<'a, F, Q, L> where Q: State {
40        ProductConfigurations {
41            it: Automaton::common_configurations(automata, &self.states)
42        }
43    }
44}
45
46impl<Q> From<Vec<Q>> for Product<Q> {
47    fn from(vec: Vec<Q>) -> Product<Q> {
48        Product {
49            states: vec
50        }
51    }
52}
53
54impl<Q: Clone> From<Vec<&Q>> for Product<Q> {
55    fn from(vec: Vec<&Q>) -> Product<Q> {
56        Product {
57            states: vec.iter().map(|q| (*q).clone()).collect()
58        }
59    }
60}
61
62pub struct ProductConfigurations<'a, F: Symbol, Q: State, L: Label> {
63    it: CommonConfigurations<'a, F, Q, L>
64}
65
66impl<'a, F: Symbol, Q: State, L: Label> Iterator for ProductConfigurations<'a, F, Q, L> {
67    type Item = Labeled<Configuration<F, Product<Q>>, L>;
68
69    fn next(&mut self) -> Option<Self::Item> {
70        match self.it.next() {
71            Some(ref confs) => {
72                let (first, label) = confs.first().unwrap();
73                let (f, arity) = first.signature();
74                let mut states = Vec::with_capacity(arity);
75                for i in 0..arity {
76                    let mut product = Vec::with_capacity(confs.len());
77                    for (conf, _) in confs {
78                        product.push(conf.states()[i].clone());
79                    }
80                    states.push(product.into())
81                }
82
83                Some((Configuration(f.clone(), states), label.clone()))
84            },
85            None => None
86        }
87    }
88}
89
90impl<F: Symbol, Q: State, L: Label> Inter<F> for Automaton<F, Q, L> where Q: Clone {
91    type Output = Automaton<F, Product<Q>, L>;
92
93    fn inter(automata: &[&Self]) -> Automaton<F, Product<Q>, L> {
94        fn process_state<F: Symbol, Q: State, L: Label>(automata: &[&Automaton<F, Q, L>], aut: &mut Automaton<F, Product<Q>, L>, product_state: Product<Q>) where Q: Clone {
95            for (conf, label) in product_state.configurations(automata) {
96                aut.add(conf.clone(), label, product_state.clone());
97
98                for sub_state in conf.states() {
99                    if !aut.includes(&sub_state) {
100                        process_state(automata, aut, sub_state.clone())
101                    }
102                }
103            }
104        }
105
106        let mut aut = Automaton::new();
107
108        for final_states in combinations(automata, |a| a.final_states()) {
109            let product = final_states.into();
110            process_state(automata, &mut aut, product)
111        }
112
113        aut
114    }
115}
tree_automata/inter.rs

tree_automata/
inter.rs
