14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// reverse.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions and classes to sort arcs in an FST. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_REVERSE_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_REVERSE_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/cache.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Reverses an FST. The reversed result is written to an output 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// MutableFst. If A transduces string x to y with weight a, then the 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// reverse of A transduces the reverse of x to the reverse of y with 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// weight a.Reverse(). 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Typically, a = a.Reverse() and Arc = RevArc (e.g. for 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// TropicalWeight or LogWeight). In general, e.g. when the weights 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// only form a left or right semiring, the output arc type must match 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// the input arc type except having the reversed Weight type. 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc, class RevArc> 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) { 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename RevArc::Weight RevWeight; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->DeleteStates(); 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetInputSymbols(ifst.InputSymbols()); 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetOutputSymbols(ifst.OutputSymbols()); 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId istart = ifst.Start(); 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId ostart = ofst->AddState(); 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetStart(ostart); 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator< Fst<Arc> > siter(ifst); 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !siter.Done(); 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project siter.Next()) { 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId is = siter.Value(); 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId os = is + 1; 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (ofst->NumStates() <= os) 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddState(); 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (is == istart) 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetFinal(os, RevWeight::One()); 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight final = ifst.Final(is); 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (final != Weight::Zero()) { 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RevArc oarc(0, 0, final.Reverse(), os); 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(0, oarc); 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > aiter(ifst, is); 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !aiter.Done(); 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next()) { 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &iarc = aiter.Value(); 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os); 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nos = iarc.nextstate + 1; 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (ofst->NumStates() <= nos) 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddState(); 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->AddArc(nos, oarc); 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 iprops = ifst.Properties(kCopyProperties, false); 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 oprops = ofst->Properties(kFstProperties, false); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties); 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_REVERSE_H__ 83