1 // project.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 project an Fst on to its domain or range. 18 19 #ifndef FST_LIB_PROJECT_H__ 20 #define FST_LIB_PROJECT_H__ 21 22 #include "fst/lib/map.h" 23 #include "fst/lib/mutable-fst.h" 24 25 namespace fst { 26 27 // This specifies whether to project on input or output. 28 enum ProjectType { PROJECT_INPUT = 1, PROJECT_OUTPUT = 2 }; 29 30 31 // Mapper to implement projection per arc. 32 template <class A> class ProjectMapper { 33 public: 34 explicit ProjectMapper(ProjectType project_type) 35 : project_type_(project_type) {} 36 37 A operator()(const A &arc) { 38 typename A::Label label = project_type_ == PROJECT_INPUT 39 ? arc.ilabel : arc.olabel; 40 return A(label, label, arc.weight, arc.nextstate); 41 } 42 43 uint64 Properties(uint64 props) { 44 return ProjectProperties(props, project_type_ == PROJECT_INPUT); 45 } 46 47 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 48 49 private: 50 ProjectType project_type_; 51 }; 52 53 54 // Projects an FST onto its domain or range by either copying each arcs' 55 // input label to the output label or vice versa. This version modifies 56 // its input. 57 // 58 // Complexity: 59 // - Time: O(V + E) 60 // - Space: O(1) 61 // where V = # of states and E = # of arcs. 62 template<class Arc> inline 63 void Project(MutableFst<Arc> *fst, ProjectType project_type) { 64 Map(fst, ProjectMapper<Arc>(project_type)); 65 } 66 67 68 // Projects an FST onto its domain or range by either copying each arc's 69 // input label to the output label or vice versa. This version is a delayed 70 // Fst. 71 // 72 // Complexity: 73 // - Time: O(v + e) 74 // - Space: O(1) 75 // where v = # of states visited, e = # of arcs visited. Constant 76 // time and to visit an input state or arc is assumed and exclusive 77 // of caching. 78 template <class A> 79 class ProjectFst : public MapFst<A, A, ProjectMapper<A> > { 80 public: 81 typedef A Arc; 82 typedef ProjectMapper<A> C; 83 84 ProjectFst(const Fst<A> &fst, ProjectType project_type) 85 : MapFst<A, A, C>(fst, C(project_type)) {} 86 87 ProjectFst(const ProjectFst<A> &fst) : MapFst<A, A, C>(fst) {} 88 89 virtual ProjectFst<A> *Copy() const { return new ProjectFst(*this); } 90 }; 91 92 93 // Specialization for ProjectFst. 94 template <class A> 95 class StateIterator< ProjectFst<A> > 96 : public StateIterator< MapFst<A, A, ProjectMapper<A> > > { 97 public: 98 explicit StateIterator(const ProjectFst<A> &fst) 99 : StateIterator< MapFst<A, A, ProjectMapper<A> > >(fst) {} 100 }; 101 102 103 // Specialization for ProjectFst. 104 template <class A> 105 class ArcIterator< ProjectFst<A> > 106 : public ArcIterator< MapFst<A, A, ProjectMapper<A> > > { 107 public: 108 ArcIterator(const ProjectFst<A> &fst, typename A::StateId s) 109 : ArcIterator< MapFst<A, A, ProjectMapper<A> > >(fst, s) {} 110 }; 111 112 113 // Useful alias when using StdArc. 114 typedef ProjectFst<StdArc> StdProjectFst; 115 116 } // namespace fst 117 118 #endif // FST_LIB_PROJECT_H__ 119
