1// reverse.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// Expand a PDT to an FST.
20
21#ifndef FST_EXTENSIONS_PDT_REVERSE_H__
22#define FST_EXTENSIONS_PDT_REVERSE_H__
23
24#include <tr1/unordered_map>
25using std::tr1::unordered_map;
26using std::tr1::unordered_multimap;
27#include <vector>
28using std::vector;
29
30#include <fst/mutable-fst.h>
31#include <fst/relabel.h>
32#include <fst/reverse.h>
33
34namespace fst {
35
36// Reverses a pushdown transducer (PDT) encoded as an FST.
37template<class Arc, class RevArc>
38void Reverse(const Fst<Arc> &ifst,
39             const vector<pair<typename Arc::Label,
40             typename Arc::Label> > &parens,
41             MutableFst<RevArc> *ofst) {
42  typedef typename Arc::Label Label;
43
44  // Reverses FST
45  Reverse(ifst, ofst);
46
47  // Exchanges open and close parenthesis pairs
48  vector<pair<Label, Label> > relabel_pairs;
49  for (size_t i = 0; i < parens.size(); ++i) {
50    relabel_pairs.push_back(make_pair(parens[i].first, parens[i].second));
51    relabel_pairs.push_back(make_pair(parens[i].second, parens[i].first));
52  }
53  Relabel(ofst, relabel_pairs, relabel_pairs);
54}
55
56}  // namespace fst
57
58#endif  // FST_EXTENSIONS_PDT_REVERSE_H__
59