14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// invert.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 invert an Fst. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_INVERT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_INVERT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/map.h" 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Mapper to implement inversion of an arc. 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> struct InvertMapper { 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project InvertMapper() {} 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A operator()(const A &arc) { 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate); 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 Properties(uint64 props) { return InvertProperties(props); } 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Inverts the transduction corresponding to an FST by exchanging the 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST's input and output labels. This version modifies its input. 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(V + E) 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(1) 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where V = # of states and E = # of arcs. 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class Arc> inline 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid Invert(MutableFst<Arc> *fst) { Map(fst, InvertMapper<Arc>()); } 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Inverts the transduction corresponding to an FST by exchanging the 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// FST's input and output labels. This version is a delayed Fst. 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Complexity: 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Time: O(v + e) 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// - Space: O(1) 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// where v = # of states visited, e = # of arcs visited. Constant 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// time and to visit an input state or arc is assumed and exclusive 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of caching. 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass InvertFst : public MapFst<A, A, InvertMapper<A> > { 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef InvertMapper<A> C; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit InvertFst(const Fst<A> &fst) : MapFst<A, A, C>(fst, C()) {} 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project InvertFst(const InvertFst<A> &fst) : MapFst<A, A, C>(fst) {} 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual InvertFst<A> *Copy() const { return new InvertFst(*this); } 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for InvertFst. 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateIterator< InvertFst<A> > 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public StateIterator< MapFst<A, A, InvertMapper<A> > > { 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit StateIterator(const InvertFst<A> &fst) 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : StateIterator< MapFst<A, A, InvertMapper<A> > >(fst) {} 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Specialization for InvertFst. 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A> 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ArcIterator< InvertFst<A> > 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : public ArcIterator< MapFst<A, A, InvertMapper<A> > > { 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator(const InvertFst<A> &fst, typename A::StateId s) 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : ArcIterator< MapFst<A, A, InvertMapper<A> > >(fst, s) {} 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Useful alias when using StdArc. 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttypedef InvertFst<StdArc> StdInvertFst; 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_INVERT_H__ 101