1// rational.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// An Fst implementation and base interface for delayed unions,
20// concatenations and closures.
21
22#ifndef FST_LIB_RATIONAL_H__
23#define FST_LIB_RATIONAL_H__
24
25#include <algorithm>
26#include <string>
27#include <vector>
28using std::vector;
29
30#include <fst/mutable-fst.h>
31#include <fst/replace.h>
32#include <fst/test-properties.h>
33
34
35namespace fst {
36
37typedef CacheOptions RationalFstOptions;
38
39// This specifies whether to add the empty string.
40enum ClosureType { CLOSURE_STAR = 0,    // T* -> add the empty string
41                   CLOSURE_PLUS = 1 };  // T+ -> don't add the empty string
42
43template <class A> class RationalFst;
44template <class A> void Union(RationalFst<A> *fst1, const Fst<A> &fst2);
45template <class A> void Concat(RationalFst<A> *fst1, const Fst<A> &fst2);
46template <class A> void Concat(const Fst<A> &fst1, RationalFst<A> *fst2);
47template <class A> void Closure(RationalFst<A> *fst, ClosureType closure_type);
48
49
50// Implementation class for delayed unions, concatenations and closures.
51template<class A>
52class RationalFstImpl : public FstImpl<A> {
53 public:
54  using FstImpl<A>::SetType;
55  using FstImpl<A>::SetProperties;
56  using FstImpl<A>::WriteHeader;
57  using FstImpl<A>::SetInputSymbols;
58  using FstImpl<A>::SetOutputSymbols;
59
60  typedef A Arc;
61  typedef typename A::Weight Weight;
62  typedef typename A::StateId StateId;
63  typedef typename A::Label Label;
64
65  explicit RationalFstImpl(const RationalFstOptions &opts)
66      : nonterminals_(0),
67        replace_(0),
68        replace_options_(opts, 0) {
69    SetType("rational");
70    fst_tuples_.push_back(pair<Label, const Fst<A>*>(0, 0));
71  }
72
73  RationalFstImpl(const RationalFstImpl<A> &impl)
74      : rfst_(impl.rfst_),
75        nonterminals_(impl.nonterminals_),
76
77        replace_(impl.replace_ ? impl.replace_->Copy(true) : 0),
78        replace_options_(impl.replace_options_) {
79    SetType("rational");
80    fst_tuples_.reserve(impl.fst_tuples_.size());
81    for (size_t i = 0; i < impl.fst_tuples_.size(); ++i)
82      fst_tuples_.push_back(make_pair(impl.fst_tuples_[i].first,
83                                      impl.fst_tuples_[i].second
84                                      ? impl.fst_tuples_[i].second->Copy(true)
85                                      : 0));
86  }
87
88  virtual ~RationalFstImpl() {
89    for (size_t i = 0; i < fst_tuples_.size(); ++i)
90      if (fst_tuples_[i].second)
91        delete fst_tuples_[i].second;
92    if (replace_)
93      delete replace_;
94  }
95
96  StateId Start() { return Replace()->Start(); }
97
98  Weight Final(StateId s) { return Replace()->Final(s); }
99
100  size_t NumArcs(StateId s) { return Replace()->NumArcs(s); }
101
102  size_t NumInputEpsilons(StateId s) {
103    return Replace()->NumInputEpsilons(s);
104  }
105
106  size_t NumOutputEpsilons(StateId s) {
107    return Replace()->NumOutputEpsilons(s);
108  }
109
110  uint64 Properties() const { return Properties(kFstProperties); }
111
112  // Set error if found; return FST impl properties.
113  uint64 Properties(uint64 mask) const {
114    if ((mask & kError) && Replace()->Properties(kError, false))
115      SetProperties(kError, kError);
116    return FstImpl<Arc>::Properties(mask);
117  }
118
119  // Implementation of UnionFst(fst1,fst2)
120  void InitUnion(const Fst<A> &fst1, const Fst<A> &fst2) {
121    if (replace_)
122      delete replace_;
123    uint64 props1 = fst1.Properties(kFstProperties, false);
124    uint64 props2 = fst2.Properties(kFstProperties, false);
125    SetInputSymbols(fst1.InputSymbols());
126    SetOutputSymbols(fst1.OutputSymbols());
127    rfst_.AddState();
128    rfst_.AddState();
129    rfst_.SetStart(0);
130    rfst_.SetFinal(1, Weight::One());
131    rfst_.SetInputSymbols(fst1.InputSymbols());
132    rfst_.SetOutputSymbols(fst1.OutputSymbols());
133    nonterminals_ = 2;
134    rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
135    rfst_.AddArc(0, A(0, -2, Weight::One(), 1));
136    fst_tuples_.push_back(make_pair(-1, fst1.Copy()));
137    fst_tuples_.push_back(make_pair(-2, fst2.Copy()));
138    SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
139  }
140
141  // Implementation of ConcatFst(fst1,fst2)
142  void InitConcat(const Fst<A> &fst1, const Fst<A> &fst2) {
143    if (replace_)
144      delete replace_;
145    uint64 props1 = fst1.Properties(kFstProperties, false);
146    uint64 props2 = fst2.Properties(kFstProperties, false);
147    SetInputSymbols(fst1.InputSymbols());
148    SetOutputSymbols(fst1.OutputSymbols());
149    rfst_.AddState();
150    rfst_.AddState();
151    rfst_.AddState();
152    rfst_.SetStart(0);
153    rfst_.SetFinal(2, Weight::One());
154    rfst_.SetInputSymbols(fst1.InputSymbols());
155    rfst_.SetOutputSymbols(fst1.OutputSymbols());
156    nonterminals_ = 2;
157    rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
158    rfst_.AddArc(1, A(0, -2, Weight::One(), 2));
159    fst_tuples_.push_back(make_pair(-1, fst1.Copy()));
160    fst_tuples_.push_back(make_pair(-2, fst2.Copy()));
161    SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
162  }
163
164  // Implementation of ClosureFst(fst, closure_type)
165  void InitClosure(const Fst<A> &fst, ClosureType closure_type) {
166    if (replace_)
167      delete replace_;
168    uint64 props = fst.Properties(kFstProperties, false);
169    SetInputSymbols(fst.InputSymbols());
170    SetOutputSymbols(fst.OutputSymbols());
171    if (closure_type == CLOSURE_STAR) {
172      rfst_.AddState();
173      rfst_.SetStart(0);
174      rfst_.SetFinal(0, Weight::One());
175      rfst_.AddArc(0, A(0, -1, Weight::One(), 0));
176    } else {
177      rfst_.AddState();
178      rfst_.AddState();
179      rfst_.SetStart(0);
180      rfst_.SetFinal(1, Weight::One());
181      rfst_.AddArc(0, A(0, -1, Weight::One(), 1));
182      rfst_.AddArc(1, A(0, 0, Weight::One(), 0));
183    }
184    rfst_.SetInputSymbols(fst.InputSymbols());
185    rfst_.SetOutputSymbols(fst.OutputSymbols());
186    fst_tuples_.push_back(make_pair(-1, fst.Copy()));
187    nonterminals_ = 1;
188    SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
189                  kCopyProperties);
190  }
191
192  // Implementation of Union(Fst &, RationalFst *)
193  void AddUnion(const Fst<A> &fst) {
194    if (replace_)
195      delete replace_;
196    uint64 props1 = FstImpl<A>::Properties();
197    uint64 props2 = fst.Properties(kFstProperties, false);
198    VectorFst<A> afst;
199    afst.AddState();
200    afst.AddState();
201    afst.SetStart(0);
202    afst.SetFinal(1, Weight::One());
203    ++nonterminals_;
204    afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1));
205    Union(&rfst_, afst);
206    fst_tuples_.push_back(make_pair(-nonterminals_, fst.Copy()));
207    SetProperties(UnionProperties(props1, props2, true), kCopyProperties);
208  }
209
210  // Implementation of Concat(Fst &, RationalFst *)
211  void AddConcat(const Fst<A> &fst, bool append) {
212    if (replace_)
213      delete replace_;
214    uint64 props1 = FstImpl<A>::Properties();
215    uint64 props2 = fst.Properties(kFstProperties, false);
216    VectorFst<A> afst;
217    afst.AddState();
218    afst.AddState();
219    afst.SetStart(0);
220    afst.SetFinal(1, Weight::One());
221    ++nonterminals_;
222    afst.AddArc(0, A(0, -nonterminals_, Weight::One(), 1));
223    if (append)
224      Concat(&rfst_, afst);
225    else
226      Concat(afst, &rfst_);
227    fst_tuples_.push_back(make_pair(-nonterminals_, fst.Copy()));
228    SetProperties(ConcatProperties(props1, props2, true), kCopyProperties);
229  }
230
231  // Implementation of Closure(RationalFst *, closure_type)
232  void AddClosure(ClosureType closure_type) {
233    if (replace_)
234      delete replace_;
235    uint64 props = FstImpl<A>::Properties();
236    Closure(&rfst_, closure_type);
237    SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR, true),
238                  kCopyProperties);
239  }
240
241  // Returns the underlying ReplaceFst.
242  ReplaceFst<A> *Replace() const {
243    if (!replace_) {
244      fst_tuples_[0].second = rfst_.Copy();
245      replace_ = new ReplaceFst<A>(fst_tuples_, replace_options_);
246    }
247    return replace_;
248  }
249
250 private:
251  VectorFst<A> rfst_;   // rational topology machine; uses neg. nonterminals
252  Label nonterminals_;  // # of nonterminals used
253  // Contains the nonterminals and their corresponding FSTs.
254  mutable vector<pair<Label, const Fst<A>*> > fst_tuples_;
255  mutable ReplaceFst<A> *replace_;        // Underlying ReplaceFst
256  ReplaceFstOptions<A> replace_options_;  // Options for creating 'replace_'
257
258  void operator=(const RationalFstImpl<A> &impl);    // disallow
259};
260
261// Parent class for the delayed rational operations - delayed union,
262// concatenation, and closure.
263//
264// This class attaches interface to implementation and handles
265// reference counting, delegating most methods to ImplToFst.
266template <class A>
267class RationalFst : public ImplToFst< RationalFstImpl<A> > {
268 public:
269  friend class StateIterator< RationalFst<A> >;
270  friend class ArcIterator< RationalFst<A> >;
271  friend void Union<>(RationalFst<A> *fst1, const Fst<A> &fst2);
272  friend void Concat<>(RationalFst<A> *fst1, const Fst<A> &fst2);
273  friend void Concat<>(const Fst<A> &fst1, RationalFst<A> *fst2);
274  friend void Closure<>(RationalFst<A> *fst, ClosureType closure_type);
275
276  typedef A Arc;
277  typedef typename A::StateId StateId;
278  typedef RationalFstImpl<A> Impl;
279
280  virtual void InitStateIterator(StateIteratorData<A> *data) const {
281    GetImpl()->Replace()->InitStateIterator(data);
282  }
283
284  virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
285    GetImpl()->Replace()->InitArcIterator(s, data);
286  }
287
288 protected:
289  RationalFst()
290      : ImplToFst<Impl>(new Impl(RationalFstOptions())) {}
291
292  explicit RationalFst(const RationalFstOptions &opts)
293      : ImplToFst<Impl>(new Impl(opts)) {}
294
295  // See Fst<>::Copy() for doc.
296  RationalFst(const RationalFst<A> &fst , bool safe = false)
297      : ImplToFst<Impl>(fst, safe) {}
298
299 private:
300  // Makes visible to friends.
301  Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
302
303  void operator=(const RationalFst<A> &fst);  // disallow
304};
305
306
307// Specialization for RationalFst.
308template <class A>
309class StateIterator< RationalFst<A> >
310    : public StateIterator< ReplaceFst<A> > {
311 public:
312  explicit StateIterator(const RationalFst<A> &fst)
313      : StateIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace())) {}
314};
315
316
317// Specialization for RationalFst.
318template <class A>
319class ArcIterator< RationalFst<A> >
320    : public CacheArcIterator< ReplaceFst<A> > {
321 public:
322  typedef typename A::StateId StateId;
323
324  ArcIterator(const RationalFst<A> &fst, StateId s)
325      : ArcIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace()), s) {}
326};
327
328}  // namespace fst
329
330#endif  // FST_LIB_RATIONAL_H__
331