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// Copyright 2005-2010 Google, Inc. 16// Author: riley@google.com (Michael Riley) 17// 18// \file 19// Functions and classes to project an Fst on to its domain or range. 20 21#ifndef FST_LIB_PROJECT_H__ 22#define FST_LIB_PROJECT_H__ 23 24#include <fst/arc-map.h> 25#include <fst/mutable-fst.h> 26 27 28namespace fst { 29 30// This specifies whether to project on input or output. 31enum ProjectType { PROJECT_INPUT = 1, PROJECT_OUTPUT = 2 }; 32 33 34// Mapper to implement projection per arc. 35template <class A> class ProjectMapper { 36 public: 37 explicit ProjectMapper(ProjectType project_type) 38 : project_type_(project_type) {} 39 40 A operator()(const A &arc) { 41 typename A::Label label = project_type_ == PROJECT_INPUT 42 ? arc.ilabel : arc.olabel; 43 return A(label, label, arc.weight, arc.nextstate); 44 } 45 46 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; } 47 48 MapSymbolsAction InputSymbolsAction() const { 49 return project_type_ == PROJECT_INPUT ? MAP_COPY_SYMBOLS : 50 MAP_CLEAR_SYMBOLS; 51 } 52 53 MapSymbolsAction OutputSymbolsAction() const { 54 return project_type_ == PROJECT_OUTPUT ? MAP_COPY_SYMBOLS : 55 MAP_CLEAR_SYMBOLS; 56 } 57 58 uint64 Properties(uint64 props) { 59 return ProjectProperties(props, project_type_ == PROJECT_INPUT); 60 } 61 62 63 private: 64 ProjectType project_type_; 65}; 66 67 68// Projects an FST onto its domain or range by either copying each arcs' 69// input label to the output label or vice versa. This version modifies 70// its input. 71// 72// Complexity: 73// - Time: O(V + E) 74// - Space: O(1) 75// where V = # of states and E = # of arcs. 76template<class Arc> inline 77void Project(MutableFst<Arc> *fst, ProjectType project_type) { 78 ArcMap(fst, ProjectMapper<Arc>(project_type)); 79 if (project_type == PROJECT_INPUT) 80 fst->SetOutputSymbols(fst->InputSymbols()); 81 if (project_type == PROJECT_OUTPUT) 82 fst->SetInputSymbols(fst->OutputSymbols()); 83} 84 85 86// Projects an FST onto its domain or range by either copying each arc's 87// input label to the output label or vice versa. This version is a delayed 88// Fst. 89// 90// Complexity: 91// - Time: O(v + e) 92// - Space: O(1) 93// where v = # of states visited, e = # of arcs visited. Constant 94// time and to visit an input state or arc is assumed and exclusive 95// of caching. 96template <class A> 97class ProjectFst : public ArcMapFst<A, A, ProjectMapper<A> > { 98 public: 99 typedef A Arc; 100 typedef ProjectMapper<A> C; 101 typedef ArcMapFstImpl< A, A, ProjectMapper<A> > Impl; 102 using ImplToFst<Impl>::GetImpl; 103 104 ProjectFst(const Fst<A> &fst, ProjectType project_type) 105 : ArcMapFst<A, A, C>(fst, C(project_type)) { 106 if (project_type == PROJECT_INPUT) 107 GetImpl()->SetOutputSymbols(fst.InputSymbols()); 108 if (project_type == PROJECT_OUTPUT) 109 GetImpl()->SetInputSymbols(fst.OutputSymbols()); 110 } 111 112 // See Fst<>::Copy() for doc. 113 ProjectFst(const ProjectFst<A> &fst, bool safe = false) 114 : ArcMapFst<A, A, C>(fst, safe) {} 115 116 // Get a copy of this ProjectFst. See Fst<>::Copy() for further doc. 117 virtual ProjectFst<A> *Copy(bool safe = false) const { 118 return new ProjectFst(*this, safe); 119 } 120}; 121 122 123// Specialization for ProjectFst. 124template <class A> 125class StateIterator< ProjectFst<A> > 126 : public StateIterator< ArcMapFst<A, A, ProjectMapper<A> > > { 127 public: 128 explicit StateIterator(const ProjectFst<A> &fst) 129 : StateIterator< ArcMapFst<A, A, ProjectMapper<A> > >(fst) {} 130}; 131 132 133// Specialization for ProjectFst. 134template <class A> 135class ArcIterator< ProjectFst<A> > 136 : public ArcIterator< ArcMapFst<A, A, ProjectMapper<A> > > { 137 public: 138 ArcIterator(const ProjectFst<A> &fst, typename A::StateId s) 139 : ArcIterator< ArcMapFst<A, A, ProjectMapper<A> > >(fst, s) {} 140}; 141 142 143// Useful alias when using StdArc. 144typedef ProjectFst<StdArc> StdProjectFst; 145 146} // namespace fst 147 148#endif // FST_LIB_PROJECT_H__ 149