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
28 namespace fst {
29
30 // This specifies whether to project on input or output.
31 enum ProjectType { PROJECT_INPUT = 1, PROJECT_OUTPUT = 2 };
32
33
34 // Mapper to implement projection per arc.
35 template <class A> class ProjectMapper {
36 public:
ProjectMapper(ProjectType project_type)37 explicit ProjectMapper(ProjectType project_type)
38 : project_type_(project_type) {}
39
operator()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
FinalAction()46 MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
47
InputSymbolsAction()48 MapSymbolsAction InputSymbolsAction() const {
49 return project_type_ == PROJECT_INPUT ? MAP_COPY_SYMBOLS :
50 MAP_CLEAR_SYMBOLS;
51 }
52
OutputSymbolsAction()53 MapSymbolsAction OutputSymbolsAction() const {
54 return project_type_ == PROJECT_OUTPUT ? MAP_COPY_SYMBOLS :
55 MAP_CLEAR_SYMBOLS;
56 }
57
Properties(uint64 props)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.
76 template<class Arc> inline
Project(MutableFst<Arc> * fst,ProjectType project_type)77 void 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.
96 template <class A>
97 class 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
ProjectFst(const Fst<A> & fst,ProjectType project_type)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.
124 template <class A>
125 class StateIterator< ProjectFst<A> >
126 : public StateIterator< ArcMapFst<A, A, ProjectMapper<A> > > {
127 public:
StateIterator(const ProjectFst<A> & fst)128 explicit StateIterator(const ProjectFst<A> &fst)
129 : StateIterator< ArcMapFst<A, A, ProjectMapper<A> > >(fst) {}
130 };
131
132
133 // Specialization for ProjectFst.
134 template <class A>
135 class ArcIterator< ProjectFst<A> >
136 : public ArcIterator< ArcMapFst<A, A, ProjectMapper<A> > > {
137 public:
ArcIterator(const ProjectFst<A> & fst,typename A::StateId s)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.
144 typedef ProjectFst<StdArc> StdProjectFst;
145
146 } // namespace fst
147
148 #endif // FST_LIB_PROJECT_H__
149