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// Copyright 2005-2010 Google, Inc.
16// Author: riley@google.com (Michael Riley)
17//
18// \file
19// Functions and classes to invert an Fst.
20
21#ifndef FST_LIB_INVERT_H__
22#define FST_LIB_INVERT_H__
23
24#include <fst/arc-map.h>
25#include <fst/mutable-fst.h>
26
27
28namespace fst {
29
30// Mapper to implement inversion of an arc.
31template <class A> struct InvertMapper {
32  InvertMapper() {}
33
34  A operator()(const A &arc) {
35    return A(arc.olabel, arc.ilabel, arc.weight, arc.nextstate);
36  }
37
38  MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
39
40  MapSymbolsAction InputSymbolsAction() const { return MAP_CLEAR_SYMBOLS; }
41
42  MapSymbolsAction OutputSymbolsAction() const { return MAP_CLEAR_SYMBOLS;}
43
44  uint64 Properties(uint64 props) { return InvertProperties(props); }
45};
46
47
48// Inverts the transduction corresponding to an FST by exchanging the
49// FST's input and output labels. This version modifies its input.
50//
51// Complexity:
52// - Time: O(V + E)
53// - Space: O(1)
54// where V = # of states and E = # of arcs.
55template<class Arc> inline
56void Invert(MutableFst<Arc> *fst) {
57  SymbolTable *input = fst->InputSymbols() ? fst->InputSymbols()->Copy() : 0;
58  SymbolTable *output = fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : 0;
59  ArcMap(fst, InvertMapper<Arc>());
60  fst->SetInputSymbols(output);
61  fst->SetOutputSymbols(input);
62  delete input;
63  delete output;
64}
65
66
67// Inverts the transduction corresponding to an FST by exchanging the
68// FST's input and output labels.  This version is a delayed Fst.
69//
70// Complexity:
71// - Time: O(v + e)
72// - Space: O(1)
73// where v = # of states visited, e = # of arcs visited. Constant
74// time and to visit an input state or arc is assumed and exclusive
75// of caching.
76template <class A>
77class InvertFst : public ArcMapFst<A, A, InvertMapper<A> > {
78 public:
79  typedef A Arc;
80  typedef InvertMapper<A> C;
81  typedef ArcMapFstImpl< A, A, InvertMapper<A> > Impl;
82  using ImplToFst<Impl>::GetImpl;
83
84  explicit InvertFst(const Fst<A> &fst) : ArcMapFst<A, A, C>(fst, C()) {
85    GetImpl()->SetOutputSymbols(fst.InputSymbols());
86    GetImpl()->SetInputSymbols(fst.OutputSymbols());
87  }
88
89  // See Fst<>::Copy() for doc.
90  InvertFst(const InvertFst<A> &fst, bool safe = false)
91      : ArcMapFst<A, A, C>(fst, safe) {}
92
93  // Get a copy of this InvertFst. See Fst<>::Copy() for further doc.
94  virtual InvertFst<A> *Copy(bool safe = false) const {
95    return new InvertFst(*this, safe);
96  }
97};
98
99
100// Specialization for InvertFst.
101template <class A>
102class StateIterator< InvertFst<A> >
103    : public StateIterator< ArcMapFst<A, A, InvertMapper<A> > > {
104 public:
105  explicit StateIterator(const InvertFst<A> &fst)
106      : StateIterator< ArcMapFst<A, A, InvertMapper<A> > >(fst) {}
107};
108
109
110// Specialization for InvertFst.
111template <class A>
112class ArcIterator< InvertFst<A> >
113    : public ArcIterator< ArcMapFst<A, A, InvertMapper<A> > > {
114 public:
115  ArcIterator(const InvertFst<A> &fst, typename A::StateId s)
116      : ArcIterator< ArcMapFst<A, A, InvertMapper<A> > >(fst, s) {}
117};
118
119
120// Useful alias when using StdArc.
121typedef InvertFst<StdArc> StdInvertFst;
122
123}  // namespace fst
124
125#endif  // FST_LIB_INVERT_H__
126