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 25namespace fst { 26 27// Mapper to implement inversion of an arc. 28template <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. 48template<class Arc> inline 49void 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. 61template <class A> 62class 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. 76template <class A> 77class 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. 86template <class A> 87class 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. 96typedef InvertFst<StdArc> StdInvertFst; 97 98} // namespace fst 99 100#endif // FST_LIB_INVERT_H__ 101