1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
use failure::Fallible;
use crate::arc::Arc;
use crate::fst_traits::{ExpandedFst, FinalStatesIterator, MutableFst};
use crate::semirings::Semiring;
use crate::EPS_LABEL;
/// Reverses an FST. The reversed result is written to an output mutable FST.
/// If A transduces string x to y with weight a, then the reverse of A
/// transduces the reverse of x to the reverse of y with weight a.Reverse().
///
/// Typically, a = a.Reverse() and an arc is its own reverse (e.g., for
/// TropicalWeight or LogWeight). In general, e.g., when the weights only form a
/// left or right semiring, the output arc type must match the input arc type
/// except having the reversed Weight type.
///
/// A superinitial state is always created.
pub fn reverse<W, F1, F2>(fst: &F1) -> Fallible<F2>
where
W: Semiring,
F1: ExpandedFst<W = W>,
F2: MutableFst<W = W> + ExpandedFst<W = W>,
{
let mut fst_reversed = F2::new();
let num_states = fst.num_states();
(0..num_states).for_each(|_| {
fst_reversed.add_state();
});
// Reverse all the transitions
for state in 0..num_states {
for arc in fst.arcs_iter(state)? {
fst_reversed.add_arc(
arc.nextstate,
Arc::new(arc.ilabel, arc.olabel, arc.weight.clone(), state),
)?;
}
}
// Creates the initial state
let super_initial_state = fst_reversed.add_state();
fst_reversed.set_start(super_initial_state)?;
// Add epsilon arc from the initial state to the former final states
for final_state in fst.final_states_iter() {
fst_reversed.add_arc(
super_initial_state,
Arc::new(
EPS_LABEL,
EPS_LABEL,
final_state.final_weight,
final_state.state_id,
),
)?;
}
// Forme initial states are now final
if let Some(state_state_in) = fst.start() {
fst_reversed.set_final(state_state_in, W::one())?;
}
Ok(fst_reversed)
}