// reverse.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Functions and classes to sort arcs in an FST.
#ifndef FST_LIB_REVERSE_H__
#define FST_LIB_REVERSE_H__
#include <algorithm>
#include <vector>
using std::vector;
#include <fst/cache.h>
namespace fst {
// Reverses an FST. The reversed result is written to an output
// MutableFst. 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 Arc = RevArc (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.
template<class Arc, class RevArc>
void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) {
typedef typename Arc::StateId StateId;
typedef typename Arc::Weight Weight;
typedef typename RevArc::Weight RevWeight;
ofst->DeleteStates();
ofst->SetInputSymbols(ifst.InputSymbols());
ofst->SetOutputSymbols(ifst.OutputSymbols());
if (ifst.Properties(kExpanded, false))
ofst->ReserveStates(CountStates(ifst) + 1);
StateId istart = ifst.Start();
StateId ostart = ofst->AddState();
ofst->SetStart(ostart);
for (StateIterator< Fst<Arc> > siter(ifst);
!siter.Done();
siter.Next()) {
StateId is = siter.Value();
StateId os = is + 1;
while (ofst->NumStates() <= os)
ofst->AddState();
if (is == istart)
ofst->SetFinal(os, RevWeight::One());
Weight final = ifst.Final(is);
if (final != Weight::Zero()) {
RevArc oarc(0, 0, final.Reverse(), os);
ofst->AddArc(0, oarc);
}
for (ArcIterator< Fst<Arc> > aiter(ifst, is);
!aiter.Done();
aiter.Next()) {
const Arc &iarc = aiter.Value();
RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os);
StateId nos = iarc.nextstate + 1;
while (ofst->NumStates() <= nos)
ofst->AddState();
ofst->AddArc(nos, oarc);
}
}
uint64 iprops = ifst.Properties(kCopyProperties, false);
uint64 oprops = ofst->Properties(kFstProperties, false);
ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties);
}
} // namespace fst
#endif // FST_LIB_REVERSE_H__