1 // complement.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 // Class to complement an Fst.
20
21 #ifndef FST_LIB_COMPLEMENT_H__
22 #define FST_LIB_COMPLEMENT_H__
23
24 #include <algorithm>
25 #include <string>
26 #include <vector>
27 using std::vector;
28
29 #include <fst/fst.h>
30 #include <fst/test-properties.h>
31
32
33 namespace fst {
34
35 template <class A> class ComplementFst;
36
37 // Implementation of delayed ComplementFst. The algorithm used
38 // completes the (deterministic) FSA and then exchanges final and
39 // non-final states. Completion, i.e. ensuring that all labels can be
40 // read from every state, is accomplished by using RHO labels, which
41 // match all labels that are otherwise not found leaving a state. The
42 // first state in the output is reserved to be a new state that is the
43 // destination of all RHO labels. Each remaining output state s
44 // corresponds to input state s - 1. The first arc in the output at
45 // these states is the rho label, the remaining arcs correspond to the
46 // input arcs.
47 template <class A>
48 class ComplementFstImpl : public FstImpl<A> {
49 public:
50 using FstImpl<A>::SetType;
51 using FstImpl<A>::SetProperties;
52 using FstImpl<A>::SetInputSymbols;
53 using FstImpl<A>::SetOutputSymbols;
54
55 friend class StateIterator< ComplementFst<A> >;
56 friend class ArcIterator< ComplementFst<A> >;
57
58 typedef A Arc;
59 typedef typename A::Label Label;
60 typedef typename A::Weight Weight;
61 typedef typename A::StateId StateId;
62
ComplementFstImpl(const Fst<A> & fst)63 explicit ComplementFstImpl(const Fst<A> &fst) : fst_(fst.Copy()) {
64 SetType("complement");
65 uint64 props = fst.Properties(kILabelSorted, false);
66 SetProperties(ComplementProperties(props), kCopyProperties);
67 SetInputSymbols(fst.InputSymbols());
68 SetOutputSymbols(fst.OutputSymbols());
69 }
70
ComplementFstImpl(const ComplementFstImpl<A> & impl)71 ComplementFstImpl(const ComplementFstImpl<A> &impl)
72 : fst_(impl.fst_->Copy()) {
73 SetType("complement");
74 SetProperties(impl.Properties(), kCopyProperties);
75 SetInputSymbols(impl.InputSymbols());
76 SetOutputSymbols(impl.OutputSymbols());
77 }
78
~ComplementFstImpl()79 ~ComplementFstImpl() { delete fst_; }
80
Start()81 StateId Start() const {
82 if (Properties(kError))
83 return kNoStateId;
84
85 StateId start = fst_->Start();
86 if (start != kNoStateId)
87 return start + 1;
88 else
89 return 0;
90 }
91
92 // Exchange final and non-final states; make rho destination state final.
Final(StateId s)93 Weight Final(StateId s) const {
94 if (s == 0 || fst_->Final(s - 1) == Weight::Zero())
95 return Weight::One();
96 else
97 return Weight::Zero();
98 }
99
NumArcs(StateId s)100 size_t NumArcs(StateId s) const {
101 if (s == 0)
102 return 1;
103 else
104 return fst_->NumArcs(s - 1) + 1;
105 }
106
NumInputEpsilons(StateId s)107 size_t NumInputEpsilons(StateId s) const {
108 return s == 0 ? 0 : fst_->NumInputEpsilons(s - 1);
109 }
110
NumOutputEpsilons(StateId s)111 size_t NumOutputEpsilons(StateId s) const {
112 return s == 0 ? 0 : fst_->NumOutputEpsilons(s - 1);
113 }
114
115
Properties()116 uint64 Properties() const { return Properties(kFstProperties); }
117
118 // Set error if found; return FST impl properties.
Properties(uint64 mask)119 uint64 Properties(uint64 mask) const {
120 if ((mask & kError) && fst_->Properties(kError, false))
121 SetProperties(kError, kError);
122 return FstImpl<Arc>::Properties(mask);
123 }
124
125
126 private:
127 const Fst<A> *fst_;
128
129 void operator=(const ComplementFstImpl<A> &fst); // Disallow
130 };
131
132
133 // Complements an automaton. This is a library-internal operation that
134 // introduces a (negative) 'rho' label; use Difference/DifferenceFst in
135 // user code, which will not see this label. This version is a delayed Fst.
136 //
137 // This class attaches interface to implementation and handles
138 // reference counting, delegating most methods to ImplToFst.
139 template <class A>
140 class ComplementFst : public ImplToFst< ComplementFstImpl<A> > {
141 public:
142 friend class StateIterator< ComplementFst<A> >;
143 friend class ArcIterator< ComplementFst<A> >;
144
145 using ImplToFst< ComplementFstImpl<A> >::GetImpl;
146
147 typedef A Arc;
148 typedef typename A::StateId StateId;
149 typedef typename A::Label Label;
150 typedef ComplementFstImpl<A> Impl;
151
ComplementFst(const Fst<A> & fst)152 explicit ComplementFst(const Fst<A> &fst)
153 : ImplToFst<Impl>(new Impl(fst)) {
154 uint64 props = kUnweighted | kNoEpsilons | kIDeterministic | kAcceptor;
155 if (fst.Properties(props, true) != props) {
156 FSTERROR() << "ComplementFst: argument not an unweighted "
157 << "epsilon-free deterministic acceptor";
158 GetImpl()->SetProperties(kError, kError);
159 }
160 }
161
162 // See Fst<>::Copy() for doc.
163 ComplementFst(const ComplementFst<A> &fst, bool safe = false)
164 : ImplToFst<Impl>(fst, safe) {}
165
166 // Get a copy of this ComplementFst. See Fst<>::Copy() for further doc.
167 virtual ComplementFst<A> *Copy(bool safe = false) const {
168 return new ComplementFst<A>(*this, safe);
169 }
170
171 virtual inline void InitStateIterator(StateIteratorData<A> *data) const;
172
173 virtual inline void InitArcIterator(StateId s,
174 ArcIteratorData<A> *data) const;
175
176 // Label that represents the rho transition.
177 // We use a negative value, which is thus private to the library and
178 // which will preserve FST label sort order.
179 static const Label kRhoLabel = -2;
180 private:
181 // Makes visible to friends.
GetImpl()182 Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
183
184 void operator=(const ComplementFst<A> &fst); // disallow
185 };
186
187 template <class A> const typename A::Label ComplementFst<A>::kRhoLabel;
188
189
190 // Specialization for ComplementFst.
191 template <class A>
192 class StateIterator< ComplementFst<A> > : public StateIteratorBase<A> {
193 public:
194 typedef typename A::StateId StateId;
195 typedef typename A::Label Label;
196
StateIterator(const ComplementFst<A> & fst)197 explicit StateIterator(const ComplementFst<A> &fst)
198 : siter_(*fst.GetImpl()->fst_), s_(0) {
199 }
200
Done()201 bool Done() const { return s_ > 0 && siter_.Done(); }
202
Value()203 StateId Value() const { return s_; }
204
Next()205 void Next() {
206 if (s_ != 0)
207 siter_.Next();
208 ++s_;
209 }
210
Reset()211 void Reset() {
212 siter_.Reset();
213 s_ = 0;
214 }
215
216 private:
217 // This allows base class virtual access to non-virtual derived-
218 // class members of the same name. It makes the derived class more
219 // efficient to use but unsafe to further derive.
Done_()220 virtual bool Done_() const { return Done(); }
Value_()221 virtual StateId Value_() const { return Value(); }
Next_()222 virtual void Next_() { Next(); }
Reset_()223 virtual void Reset_() { Reset(); }
224
225 StateIterator< Fst<A> > siter_;
226 StateId s_;
227
228 DISALLOW_COPY_AND_ASSIGN(StateIterator);
229 };
230
231
232 // Specialization for ComplementFst.
233 template <class A>
234 class ArcIterator< ComplementFst<A> > : public ArcIteratorBase<A> {
235 public:
236 typedef typename A::StateId StateId;
237 typedef typename A::Label Label;
238 typedef typename A::Weight Weight;
239
ArcIterator(const ComplementFst<A> & fst,StateId s)240 ArcIterator(const ComplementFst<A> &fst, StateId s)
241 : aiter_(0), s_(s), pos_(0) {
242 if (s_ != 0)
243 aiter_ = new ArcIterator< Fst<A> >(*fst.GetImpl()->fst_, s - 1);
244 }
245
~ArcIterator()246 virtual ~ArcIterator() { delete aiter_; }
247
Done()248 bool Done() const {
249 if (s_ != 0)
250 return pos_ > 0 && aiter_->Done();
251 else
252 return pos_ > 0;
253 }
254
255 // Adds the rho label to the rho destination state.
Value()256 const A& Value() const {
257 if (pos_ == 0) {
258 arc_.ilabel = arc_.olabel = ComplementFst<A>::kRhoLabel;
259 arc_.weight = Weight::One();
260 arc_.nextstate = 0;
261 } else {
262 arc_ = aiter_->Value();
263 ++arc_.nextstate;
264 }
265 return arc_;
266 }
267
Next()268 void Next() {
269 if (s_ != 0 && pos_ > 0)
270 aiter_->Next();
271 ++pos_;
272 }
273
Position()274 size_t Position() const {
275 return pos_;
276 }
277
Reset()278 void Reset() {
279 if (s_ != 0)
280 aiter_->Reset();
281 pos_ = 0;
282 }
283
Seek(size_t a)284 void Seek(size_t a) {
285 if (s_ != 0) {
286 if (a == 0) {
287 aiter_->Reset();
288 } else {
289 aiter_->Seek(a - 1);
290 }
291 }
292 pos_ = a;
293 }
294
Flags()295 uint32 Flags() const {
296 return kArcValueFlags;
297 }
298
SetFlags(uint32 f,uint32 m)299 void SetFlags(uint32 f, uint32 m) {}
300
301 private:
302 // This allows base class virtual access to non-virtual derived-
303 // class members of the same name. It makes the derived class more
304 // efficient to use but unsafe to further derive.
Done_()305 virtual bool Done_() const { return Done(); }
Value_()306 virtual const A& Value_() const { return Value(); }
Next_()307 virtual void Next_() { Next(); }
Position_()308 virtual size_t Position_() const { return Position(); }
Reset_()309 virtual void Reset_() { Reset(); }
Seek_(size_t a)310 virtual void Seek_(size_t a) { Seek(a); }
Flags_()311 uint32 Flags_() const { return Flags(); }
SetFlags_(uint32 f,uint32 m)312 void SetFlags_(uint32 f, uint32 m) { SetFlags(f, m); }
313
314 ArcIterator< Fst<A> > *aiter_;
315 StateId s_;
316 size_t pos_;
317 mutable A arc_;
318 DISALLOW_COPY_AND_ASSIGN(ArcIterator);
319 };
320
321
322 template <class A> inline void
InitStateIterator(StateIteratorData<A> * data)323 ComplementFst<A>::InitStateIterator(StateIteratorData<A> *data) const {
324 data->base = new StateIterator< ComplementFst<A> >(*this);
325 }
326
327 template <class A> inline void
InitArcIterator(StateId s,ArcIteratorData<A> * data)328 ComplementFst<A>::InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
329 data->base = new ArcIterator< ComplementFst<A> >(*this, s);
330 }
331
332
333 // Useful alias when using StdArc.
334 typedef ComplementFst<StdArc> StdComplementFst;
335
336 } // namespace fst
337
338 #endif // FST_LIB_COMPLEMENT_H__
339