invert.h revision 8fc5a7f51e62cb4ae44a27bdf4176d04adc80ede 
1// invert.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 invert an Fst.
18
19#ifndef FST_LIB_INVERT_H__
20#define FST_LIB_INVERT_H__
21
22#include "fst/lib/map.h"
23#include "fst/lib/mutable-fst.h"
24
25namespace fst {
26
27// Mapper to implement inversion of an arc.
28template <class A> struct InvertMapper {
29  InvertMapper() {}
30
31  A operator()(const A &arc) {
32    return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate);
33  }
34
35  uint64 Properties(uint64 props) { return InvertProperties(props); }
36
37  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
38};
39
40
41// Inverts the transduction corresponding to an FST by exchanging the
42// FST's input and output labels. This version modifies its input.
43//
44// Complexity:
45// - Time: O(V + E)
46// - Space: O(1)
47// where V = # of states and E = # of arcs.
48template<class Arc> inline
49void Invert(MutableFst<Arc> *fst) { Map(fst, InvertMapper<Arc>()); }
50
51
52// Inverts the transduction corresponding to an FST by exchanging the
53// FST's input and output labels.  This version is a delayed Fst.
54//
55// Complexity:
56// - Time: O(v + e)
57// - Space: O(1)
58// where v = # of states visited, e = # of arcs visited. Constant
59// time and to visit an input state or arc is assumed and exclusive
60// of caching.
61template <class A>
62class InvertFst : public MapFst<A, A, InvertMapper<A> > {
63 public:
64  typedef A Arc;
65  typedef InvertMapper<A> C;
66
67  explicit InvertFst(const Fst<A> &fst) : MapFst<A, A, C>(fst, C()) {}
68
69  InvertFst(const InvertFst<A> &fst) : MapFst<A, A, C>(fst) {}
70
71  virtual InvertFst<A> *Copy() const { return new InvertFst(*this); }
72};
73
74
75// Specialization for InvertFst.
76template <class A>
77class StateIterator< InvertFst<A> >
78    : public StateIterator< MapFst<A, A, InvertMapper<A> > > {
79 public:
80  explicit StateIterator(const InvertFst<A> &fst)
81      : StateIterator< MapFst<A, A, InvertMapper<A> > >(fst) {}
82};
83
84
85// Specialization for InvertFst.
86template <class A>
87class ArcIterator< InvertFst<A> >
88    : public ArcIterator< MapFst<A, A, InvertMapper<A> > > {
89 public:
90  ArcIterator(const InvertFst<A> &fst, typename A::StateId s)
91      : ArcIterator< MapFst<A, A, InvertMapper<A> > >(fst, s) {}
92};
93
94
95// Useful alias when using StdArc.
96typedef InvertFst<StdArc> StdInvertFst;
97
98}  // namespace fst
99
100#endif  // FST_LIB_INVERT_H__
101