reverse.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2 
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>
26using std::vector;
27
28#include <fst/cache.h>
29
30
31namespace 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.
42template<class Arc, class RevArc>
43void 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