1 // reverse.h
2
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // Copyright 2005-2010 Google, Inc.
16 // Author: riley@google.com (Michael Riley)
17 //
18 // \file
19 // Functions and classes to sort arcs in an FST.
20
21 #ifndef FST_LIB_REVERSE_H__
22 #define FST_LIB_REVERSE_H__
23
24 #include <algorithm>
25 #include <vector>
26 using std::vector;
27
28 #include <fst/cache.h>
29
30
31 namespace fst {
32
33 // Reverses an FST. The reversed result is written to an output
34 // MutableFst. If A transduces string x to y with weight a, then the
35 // reverse of A transduces the reverse of x to the reverse of y with
36 // weight a.Reverse().
37 //
38 // Typically, a = a.Reverse() and Arc = RevArc (e.g. for
39 // TropicalWeight or LogWeight). In general, e.g. when the weights
40 // only form a left or right semiring, the output arc type must match
41 // the input arc type except having the reversed Weight type.
42 template<class Arc, class RevArc>
Reverse(const Fst<Arc> & ifst,MutableFst<RevArc> * ofst)43 void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) {
44 typedef typename Arc::StateId StateId;
45 typedef typename Arc::Weight Weight;
46 typedef typename RevArc::Weight RevWeight;
47
48 ofst->DeleteStates();
49 ofst->SetInputSymbols(ifst.InputSymbols());
50 ofst->SetOutputSymbols(ifst.OutputSymbols());
51 if (ifst.Properties(kExpanded, false))
52 ofst->ReserveStates(CountStates(ifst) + 1);
53 StateId istart = ifst.Start();
54 StateId ostart = ofst->AddState();
55 ofst->SetStart(ostart);
56
57 for (StateIterator< Fst<Arc> > siter(ifst);
58 !siter.Done();
59 siter.Next()) {
60 StateId is = siter.Value();
61 StateId os = is + 1;
62 while (ofst->NumStates() <= os)
63 ofst->AddState();
64 if (is == istart)
65 ofst->SetFinal(os, RevWeight::One());
66
67 Weight final = ifst.Final(is);
68 if (final != Weight::Zero()) {
69 RevArc oarc(0, 0, final.Reverse(), os);
70 ofst->AddArc(0, oarc);
71 }
72
73 for (ArcIterator< Fst<Arc> > aiter(ifst, is);
74 !aiter.Done();
75 aiter.Next()) {
76 const Arc &iarc = aiter.Value();
77 RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os);
78 StateId nos = iarc.nextstate + 1;
79 while (ofst->NumStates() <= nos)
80 ofst->AddState();
81 ofst->AddArc(nos, oarc);
82 }
83 }
84 uint64 iprops = ifst.Properties(kCopyProperties, false);
85 uint64 oprops = ofst->Properties(kFstProperties, false);
86 ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties);
87 }
88
89 } // namespace fst
90
91 #endif // FST_LIB_REVERSE_H__
92