1 // invert.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 (at) google.com (Michael Riley) 17 // 18 // \file 19 // Functions and classes to invert an Fst. 20 21 #ifndef FST_LIB_INVERT_H__ 22 #define FST_LIB_INVERT_H__ 23 24 #include <fst/arc-map.h> 25 #include <fst/mutable-fst.h> 26 27 28 namespace fst { 29 30 // Mapper to implement inversion of an arc. 31 template <class A> struct InvertMapper { 32 InvertMapper() {} 33 34 A operator()(const A &arc) { 35 return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate); 36 } 37 38 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 39 40 MapSymbolsAction InputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; } 41 42 MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;} 43 44 uint64 Properties(uint64 props) { return InvertProperties(props); } 45 }; 46 47 48 // Inverts the transduction corresponding to an FST by exchanging the 49 // FST's input and output labels. This version modifies its input. 50 // 51 // Complexity: 52 // - Time: O(V + E) 53 // - Space: O(1) 54 // where V = # of states and E = # of arcs. 55 template<class Arc> inline 56 void Invert(MutableFst<Arc> *fst) { 57 SymbolTable *input = fst->InputSymbols() ? fst->InputSymbols()->Copy() : 0; 58 SymbolTable *output = fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : 0; 59 ArcMap(fst, InvertMapper<Arc>()); 60 fst->SetInputSymbols(output); 61 fst->SetOutputSymbols(input); 62 delete input; 63 delete output; 64 } 65 66 67 // Inverts the transduction corresponding to an FST by exchanging the 68 // FST's input and output labels. This version is a delayed Fst. 69 // 70 // Complexity: 71 // - Time: O(v + e) 72 // - Space: O(1) 73 // where v = # of states visited, e = # of arcs visited. Constant 74 // time and to visit an input state or arc is assumed and exclusive 75 // of caching. 76 template <class A> 77 class InvertFst : public ArcMapFst<A, A, InvertMapper<A> > { 78 public: 79 typedef A Arc; 80 typedef InvertMapper<A> C; 81 typedef ArcMapFstImpl< A, A, InvertMapper<A> > Impl; 82 using ImplToFst<Impl>::GetImpl; 83 84 explicit InvertFst(const Fst<A> &fst) : ArcMapFst<A, A, C>(fst, C()) { 85 GetImpl()->SetOutputSymbols(fst.InputSymbols()); 86 GetImpl()->SetInputSymbols(fst.OutputSymbols()); 87 } 88 89 // See Fst<>::Copy() for doc. 90 InvertFst(const InvertFst<A> &fst, bool safe = false) 91 : ArcMapFst<A, A, C>(fst, safe) {} 92 93 // Get a copy of this InvertFst. See Fst<>::Copy() for further doc. 94 virtual InvertFst<A> *Copy(bool safe = false) const { 95 return new InvertFst(*this, safe); 96 } 97 }; 98 99 100 // Specialization for InvertFst. 101 template <class A> 102 class StateIterator< InvertFst<A> > 103 : public StateIterator< ArcMapFst<A, A, InvertMapper<A> > > { 104 public: 105 explicit StateIterator(const InvertFst<A> &fst) 106 : StateIterator< ArcMapFst<A, A, InvertMapper<A> > >(fst) {} 107 }; 108 109 110 // Specialization for InvertFst. 111 template <class A> 112 class ArcIterator< InvertFst<A> > 113 : public ArcIterator< ArcMapFst<A, A, InvertMapper<A> > > { 114 public: 115 ArcIterator(const InvertFst<A> &fst, typename A::StateId s) 116 : ArcIterator< ArcMapFst<A, A, InvertMapper<A> > >(fst, s) {} 117 }; 118 119 120 // Useful alias when using StdArc. 121 typedef InvertFst<StdArc> StdInvertFst; 122 123 } // namespace fst 124 125 #endif // FST_LIB_INVERT_H__ 126
