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//
16// \file
17// Functions and classes to sort arcs in an FST.
18
19#ifndef FST_LIB_REVERSE_H__
20#define FST_LIB_REVERSE_H__
21
22#include "fst/lib/cache.h"
23
24namespace fst {
25
26// Reverses an FST. The reversed result is written to an output
27// MutableFst.  If A transduces string x to y with weight a, then the
28// reverse of A transduces the reverse of x to the reverse of y with
29// weight a.Reverse().
30//
31// Typically, a = a.Reverse() and Arc = RevArc (e.g. for
32// TropicalWeight or LogWeight).  In general, e.g. when the weights
33// only form a left or right semiring, the output arc type must match
34// the input arc type except having the reversed Weight type.
35template<class Arc, class RevArc>
36void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) {
37  typedef typename Arc::StateId StateId;
38  typedef typename Arc::Weight Weight;
39  typedef typename RevArc::Weight RevWeight;
40
41  ofst->DeleteStates();
42  ofst->SetInputSymbols(ifst.InputSymbols());
43  ofst->SetOutputSymbols(ifst.OutputSymbols());
44  StateId istart = ifst.Start();
45  StateId ostart = ofst->AddState();
46  ofst->SetStart(ostart);
47
48  for (StateIterator< Fst<Arc> > siter(ifst);
49       !siter.Done();
50       siter.Next()) {
51    StateId is = siter.Value();
52    StateId os = is + 1;
53    while (ofst->NumStates() <= os)
54      ofst->AddState();
55    if (is == istart)
56      ofst->SetFinal(os, RevWeight::One());
57
58    Weight final = ifst.Final(is);
59    if (final != Weight::Zero()) {
60      RevArc oarc(0, 0, final.Reverse(), os);
61      ofst->AddArc(0, oarc);
62    }
63
64    for (ArcIterator< Fst<Arc> > aiter(ifst, is);
65         !aiter.Done();
66         aiter.Next()) {
67      const Arc &iarc = aiter.Value();
68      RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os);
69      StateId nos = iarc.nextstate + 1;
70      while (ofst->NumStates() <= nos)
71        ofst->AddState();
72      ofst->AddArc(nos, oarc);
73    }
74  }
75  uint64 iprops = ifst.Properties(kCopyProperties, false);
76  uint64 oprops = ofst->Properties(kFstProperties, false);
77  ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties);
78}
79
80}  // namespace fst
81
82#endif  // FST_LIB_REVERSE_H__
83