project.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2 
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