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 // 16 // \file 17 // Functions and classes to invert an Fst. 18 19 #ifndef FST_LIB_INVERT_H__ 20 #define FST_LIB_INVERT_H__ 21 22 #include "fst/lib/map.h" 23 #include "fst/lib/mutable-fst.h" 24 25 namespace fst { 26 27 // Mapper to implement inversion of an arc. 28 template <class A> struct InvertMapper { 29 InvertMapper() {} 30 31 A operator()(const A &arc) { 32 return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate); 33 } 34 35 uint64 Properties(uint64 props) { return InvertProperties(props); } 36 37 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 38 }; 39 40 41 // Inverts the transduction corresponding to an FST by exchanging the 42 // FST's input and output labels. This version modifies its input. 43 // 44 // Complexity: 45 // - Time: O(V + E) 46 // - Space: O(1) 47 // where V = # of states and E = # of arcs. 48 template<class Arc> inline 49 void Invert(MutableFst<Arc> *fst) { Map(fst, InvertMapper<Arc>()); } 50 51 52 // Inverts the transduction corresponding to an FST by exchanging the 53 // FST's input and output labels. This version is a delayed Fst. 54 // 55 // Complexity: 56 // - Time: O(v + e) 57 // - Space: O(1) 58 // where v = # of states visited, e = # of arcs visited. Constant 59 // time and to visit an input state or arc is assumed and exclusive 60 // of caching. 61 template <class A> 62 class InvertFst : public MapFst<A, A, InvertMapper<A> > { 63 public: 64 typedef A Arc; 65 typedef InvertMapper<A> C; 66 67 explicit InvertFst(const Fst<A> &fst) : MapFst<A, A, C>(fst, C()) {} 68 69 InvertFst(const InvertFst<A> &fst) : MapFst<A, A, C>(fst) {} 70 71 virtual InvertFst<A> *Copy() const { return new InvertFst(*this); } 72 }; 73 74 75 // Specialization for InvertFst. 76 template <class A> 77 class StateIterator< InvertFst<A> > 78 : public StateIterator< MapFst<A, A, InvertMapper<A> > > { 79 public: 80 explicit StateIterator(const InvertFst<A> &fst) 81 : StateIterator< MapFst<A, A, InvertMapper<A> > >(fst) {} 82 }; 83 84 85 // Specialization for InvertFst. 86 template <class A> 87 class ArcIterator< InvertFst<A> > 88 : public ArcIterator< MapFst<A, A, InvertMapper<A> > > { 89 public: 90 ArcIterator(const InvertFst<A> &fst, typename A::StateId s) 91 : ArcIterator< MapFst<A, A, InvertMapper<A> > >(fst, s) {} 92 }; 93 94 95 // Useful alias when using StdArc. 96 typedef InvertFst<StdArc> StdInvertFst; 97 98 } // namespace fst 99 100 #endif // FST_LIB_INVERT_H__ 101
