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>
28 using std::vector;
29 
30 #include <fst/mutable-fst.h>
31 #include <fst/replace.h>
32 #include <fst/test-properties.h>
33 
34 
35 namespace fst {
36 
37 typedef CacheOptions RationalFstOptions;
38 
39 // This specifies whether to add the empty string.
40 enum ClosureType { CLOSURE_STAR = 0,    // T* -> add the empty string
41                    CLOSURE_PLUS = 1 };  // T+ -> don't add the empty string
42 
43 template <class A> class RationalFst;
44 template <class A> void Union(RationalFst<A> *fst1, const Fst<A> &fst2);
45 template <class A> void Concat(RationalFst<A> *fst1, const Fst<A> &fst2);
46 template <class A> void Concat(const Fst<A> &fst1, RationalFst<A> *fst2);
47 template <class A> void Closure(RationalFst<A> *fst, ClosureType closure_type);
48 
49 
50 // Implementation class for delayed unions, concatenations and closures.
51 template<class A>
52 class 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 
RationalFstImpl(const RationalFstOptions & opts)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 
RationalFstImpl(const RationalFstImpl<A> & impl)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 
~RationalFstImpl()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 
Start()96   StateId Start() { return Replace()->Start(); }
97 
Final(StateId s)98   Weight Final(StateId s) { return Replace()->Final(s); }
99 
NumArcs(StateId s)100   size_t NumArcs(StateId s) { return Replace()->NumArcs(s); }
101 
NumInputEpsilons(StateId s)102   size_t NumInputEpsilons(StateId s) {
103     return Replace()->NumInputEpsilons(s);
104   }
105 
NumOutputEpsilons(StateId s)106   size_t NumOutputEpsilons(StateId s) {
107     return Replace()->NumOutputEpsilons(s);
108   }
109 
Properties()110   uint64 Properties() const { return Properties(kFstProperties); }
111 
112   // Set error if found; return FST impl properties.
Properties(uint64 mask)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)
InitUnion(const Fst<A> & fst1,const Fst<A> & 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)
InitConcat(const Fst<A> & fst1,const Fst<A> & 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)
InitClosure(const Fst<A> & fst,ClosureType 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 *)
AddUnion(const Fst<A> & fst)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 *)
AddConcat(const Fst<A> & fst,bool append)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)
AddClosure(ClosureType 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.
Replace()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.
266 template <class A>
267 class 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 
InitStateIterator(StateIteratorData<A> * data)280   virtual void InitStateIterator(StateIteratorData<A> *data) const {
281     GetImpl()->Replace()->InitStateIterator(data);
282   }
283 
InitArcIterator(StateId s,ArcIteratorData<A> * data)284   virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
285     GetImpl()->Replace()->InitArcIterator(s, data);
286   }
287 
288  protected:
RationalFst()289   RationalFst()
290       : ImplToFst<Impl>(new Impl(RationalFstOptions())) {}
291 
RationalFst(const RationalFstOptions & opts)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.
GetImpl()301   Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
302 
303   void operator=(const RationalFst<A> &fst);  // disallow
304 };
305 
306 
307 // Specialization for RationalFst.
308 template <class A>
309 class StateIterator< RationalFst<A> >
310     : public StateIterator< ReplaceFst<A> > {
311  public:
StateIterator(const RationalFst<A> & fst)312   explicit StateIterator(const RationalFst<A> &fst)
313       : StateIterator< ReplaceFst<A> >(*(fst.GetImpl()->Replace())) {}
314 };
315 
316 
317 // Specialization for RationalFst.
318 template <class A>
319 class ArcIterator< RationalFst<A> >
320     : public CacheArcIterator< ReplaceFst<A> > {
321  public:
322   typedef typename A::StateId StateId;
323 
ArcIterator(const RationalFst<A> & fst,StateId s)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