1
use crate::LabelIndex;
2
use crate::LabelledTransitionSystem;
3
use crate::StateIndex;
4

            
5
/// A struct containg information related to the incoming transitions for every
6
/// state.
7
pub struct IncomingTransitions {
8
    incoming_transitions: Vec<(LabelIndex, StateIndex)>,
9
    state2incoming: Vec<TransitionIndex>,
10
}
11

            
12
#[derive(Default, Clone)]
13
struct TransitionIndex {
14
    start: usize,
15
    end: usize,
16
    silent: usize,
17
}
18

            
19
impl IncomingTransitions {
20
58
    pub fn new(lts: &LabelledTransitionSystem) -> IncomingTransitions {
21
58
        let mut incoming_transitions: Vec<(LabelIndex, StateIndex)> = vec![(0,0); lts.num_of_transitions()];
22
58
        let mut state2incoming: Vec<TransitionIndex> = vec![TransitionIndex::default(); lts.num_of_states()];
23
        
24
        // Compute the number of incoming (silent) transitions for each state.
25
282508
        for state_index in lts.iter_states() {
26
490506
            for (label_index, to) in lts.outgoing_transitions(state_index) {
27
490506
                state2incoming[*to].end += 1;
28
490506
                if lts.is_hidden_label(*label_index) {
29
85931
                    state2incoming[*to].silent += 1;
30
404575
                }
31
            }
32
        }
33

            
34
        // Fold the counts in state2incoming. Temporarily mixing up the data
35
        // structure such that after placing the transitions below the counts
36
        // will be correct.
37
282508
        state2incoming.iter_mut().fold(0, |count, index| {
38
282508
            let end = count + index.end;
39
282508
            index.start = end - index.silent;
40
282508
            index.end = end;
41
282508
            index.silent = end;
42
282508
            end
43
282508
        });
44

            
45
282508
        for state_index in lts.iter_states() {
46
490506
            for (label_index, to) in lts.outgoing_transitions(state_index) {
47
490506
                let index = &mut state2incoming[*to];
48
490506

            
49
490506
                if lts.is_hidden_label(*label_index) {
50
85931
                    // Place at end of incoming transitions.
51
85931
                    index.silent -= 1;
52
85931
                    incoming_transitions[index.silent] = (*label_index, state_index);
53
404575
                } else {
54
404575
                    index.start -= 1;
55
404575
                    incoming_transitions[index.start] = (*label_index, state_index);
56
404575
                }
57
            }
58
        }
59
        
60
58
        IncomingTransitions { incoming_transitions, state2incoming}
61
58
    }
62

            
63
    /// Returns an iterator over the incoming transitions for the given state.
64
298515
    pub fn incoming_transitions(&self, state_index: usize) -> impl Iterator<Item = &(LabelIndex, StateIndex)> {
65
298515
        self.incoming_transitions[self.state2incoming[state_index].start .. self.state2incoming[state_index].end].iter()
66
298515
    }
67

            
68
    // Return an iterator over the incoming silent transitions for the given state.
69
295809
    pub fn incoming_silent_transitions(&self, state_index: usize) -> impl Iterator<Item = &(LabelIndex, StateIndex)>  {
70
295809
        self.incoming_transitions[self.state2incoming[state_index].silent .. self.state2incoming[state_index].end].iter()
71
295809
    }
72
}
73

            
74
#[cfg(test)]
75
mod tests {
76

            
77
    use crate::random_lts;
78

            
79
    use super::*;
80

            
81
    #[test]
82
1
    fn test_incoming_transitions() {
83
1
        let lts = random_lts(10, 3, 3);
84
1
        let _ = IncomingTransitions::new(&lts);
85
1
    }
86
}