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
25namespace fst {
26
27// This specifies whether to project on input or output.
28enum ProjectType { PROJECT_INPUT = 1, PROJECT_OUTPUT = 2 };
29
30
31// Mapper to implement projection per arc.
32template <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.
62template<class Arc> inline
63void 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.
78template <class A>
79class 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.
94template <class A>
95class 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.
104template <class A>
105class 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.
114typedef ProjectFst<StdArc> StdProjectFst;
115
116}  // namespace fst
117
118#endif  // FST_LIB_PROJECT_H__
119