complement.h revision 4a68b3365c8c50aa93505e99ead2565ab73dcdb0 
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//
16// \file
17// Class to complement an Fst.
18
19#ifndef FST_LIB_COMPLEMENT_H__
20#define FST_LIB_COMPLEMENT_H__
21
22#include <algorithm>
23
24#include "fst/lib/fst.h"
25#include "fst/lib/test-properties.h"
26
27namespace fst {
28
29template <class A> class ComplementFst;
30
31// Implementation of delayed ComplementFst. The algorithm used
32// completes the (deterministic) FSA and then exchanges final and
33// non-final states.  Completion, i.e. ensuring that all labels can be
34// read from every state, is accomplished by using RHO labels, which
35// match all labels that are otherwise not found leaving a state. The
36// first state in the output is reserved to be a new state that is the
37// destination of all RHO labels. Each remaining output state s
38// corresponds to input state s - 1. The first arc in the output at
39// these states is the rho label, the remaining arcs correspond to the
40// input arcs.
41template<class A>
42class ComplementFstImpl : public FstImpl<A> {
43 public:
44  using FstImpl<A>::SetType;
45  using FstImpl<A>::SetProperties;
46  using FstImpl<A>::Properties;
47  using FstImpl<A>::SetInputSymbols;
48  using FstImpl<A>::SetOutputSymbols;
49
50  friend class StateIterator< ComplementFst<A> >;
51  friend class ArcIterator< ComplementFst<A> >;
52
53  typedef typename A::Label Label;
54  typedef typename A::Weight Weight;
55  typedef typename A::StateId StateId;
56
57  explicit ComplementFstImpl(const Fst<A> &fst) : fst_(fst.Copy()) {
58    SetType("complement");
59    uint64 props = fst.Properties(kILabelSorted, false);
60    SetProperties(ComplementProperties(props), kCopyProperties);
61    SetInputSymbols(fst.InputSymbols());
62    SetOutputSymbols(fst.OutputSymbols());
63  }
64
65  ~ComplementFstImpl() { delete fst_; }
66
67  StateId Start() const {
68    StateId start = fst_->Start();
69    if (start != kNoStateId)
70      return start + 1;
71    else
72      return 0;
73  }
74
75  // Exchange final and non-final states; make rho destination state final.
76  Weight Final(StateId s) const {
77    if (s == 0 || fst_->Final(s - 1) == Weight::Zero())
78      return Weight::One();
79    else
80      return Weight::Zero();
81  }
82
83  size_t NumArcs(StateId s) const {
84    if (s == 0)
85      return 1;
86    else
87      return fst_->NumArcs(s - 1) + 1;
88  }
89
90  size_t NumInputEpsilons(StateId s) const {
91    return s == 0 ? 0 : fst_->NumInputEpsilons(s - 1);
92  }
93
94  size_t NumOutputEpsilons(StateId s) const {
95    return s == 0 ? 0 : fst_->NumOutputEpsilons(s - 1);
96  }
97
98 private:
99  const Fst<A> *fst_;
100
101  DISALLOW_EVIL_CONSTRUCTORS(ComplementFstImpl);
102};
103
104
105// Complements an automaton; this is a library-internal operation
106// that introduces the rho label. This version is a delayed Fst.
107template <class A>
108class ComplementFst : public Fst<A> {
109 public:
110  friend class StateIterator< ComplementFst<A> >;
111  friend class ArcIterator< ComplementFst<A> >;
112
113  typedef A Arc;
114  typedef typename A::Label Label;
115  typedef typename A::Weight Weight;
116  typedef typename A::StateId StateId;
117
118  explicit ComplementFst(const Fst<A> &fst)
119      : impl_(new ComplementFstImpl<A>(fst)) {
120    uint64 props = kUnweighted | kNoEpsilons | kIDeterministic | kAcceptor;
121    if (fst.Properties(props, true) != props)
122      LOG(FATAL) << "ComplementFst: argument not an unweighted"
123                 << " epsilon-free deterministic acceptor";
124  }
125
126  ComplementFst(const ComplementFst<A> &fst) : impl_(fst.impl_) {
127    impl_->IncrRefCount();
128  }
129
130  virtual ~ComplementFst() { if (!impl_->DecrRefCount()) { delete impl_;  }}
131
132  virtual StateId Start() const { return impl_->Start(); }
133
134  virtual Weight Final(StateId s) const { return impl_->Final(s); }
135
136  virtual uint64 Properties(uint64 mask, bool test) const {
137    if (test) {
138      uint64 known, test = TestProperties(*this, mask, &known);
139      impl_->SetProperties(test, known);
140      return test & mask;
141    } else {
142      return impl_->Properties(mask);
143    }
144  }
145
146  virtual const string& Type() const { return impl_->Type(); }
147
148  virtual ComplementFst<A> *Copy() const {
149    return new ComplementFst<A>(*this);
150  }
151
152  virtual const SymbolTable* InputSymbols() const {
153    return impl_->InputSymbols();
154  }
155
156  virtual const SymbolTable* OutputSymbols() const {
157    return impl_->OutputSymbols();
158  }
159
160  virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }
161
162  virtual size_t NumInputEpsilons(StateId s) const {
163    return impl_->NumInputEpsilons(s);
164  }
165
166  virtual size_t NumOutputEpsilons(StateId s) const {
167    return impl_->NumOutputEpsilons(s);
168  }
169
170  virtual inline void InitStateIterator(StateIteratorData<A> *data) const;
171
172  virtual inline void InitArcIterator(StateId s,
173                                      ArcIteratorData<A> *data) const;
174
175 private:
176  ComplementFstImpl<A> *impl_;
177
178  void operator=(const ComplementFst<A> &fst);  // disallow
179};
180
181
182// Specialization for ComplementFst.
183template <class A>
184class StateIterator< ComplementFst<A> > : public StateIteratorBase<A> {
185 public:
186  typedef typename A::StateId StateId;
187  typedef typename A::Label Label;
188
189  explicit StateIterator(const ComplementFst<A> &fst)
190      : siter_(*fst.impl_->fst_), s_(0) {
191  }
192
193  virtual bool Done() const { return s_ > 0 && siter_.Done(); }
194  virtual StateId Value() const { return s_; }
195  virtual void Next() {
196    if (s_ != 0)
197      siter_.Next();
198    ++s_;
199  }
200  virtual void Reset() {
201    siter_.Reset();
202    s_ = 0;
203  }
204
205 private:
206  StateIterator< Fst<A> > siter_;
207  StateId s_;
208
209  DISALLOW_EVIL_CONSTRUCTORS(StateIterator);
210};
211
212
213// Specialization for ComplementFst.
214template <class A>
215class ArcIterator< ComplementFst<A> > : public ArcIteratorBase<A> {
216 public:
217  typedef typename A::StateId StateId;
218  typedef typename A::Label Label;
219  typedef typename A::Weight Weight;
220
221  ArcIterator(const ComplementFst<A> &fst, StateId s)
222      : aiter_(0), s_(s), pos_(0) {
223    if (s_ != 0)
224      aiter_ = new ArcIterator< Fst<A> >(*fst.impl_->fst_, s - 1);
225  }
226  virtual ~ArcIterator() { delete aiter_; }
227
228  virtual bool Done() const {
229    if (s_ != 0)
230      return pos_ > 0 && aiter_->Done();
231    else
232      return pos_ > 0;
233  }
234
235  // Adds the rho label to the rho destination state.
236  virtual const A& Value() const {
237    if (pos_ == 0) {
238      arc_.ilabel = arc_.olabel = kRhoLabel;
239      arc_.weight = Weight::One();
240      arc_.nextstate = 0;
241    } else {
242      arc_ = aiter_->Value();
243      ++arc_.nextstate;
244    }
245    return arc_;
246  }
247  virtual void Next() {
248    if (s_ != 0 && pos_ > 0)
249      aiter_->Next();
250    ++pos_;
251  }
252  virtual void Reset() {
253    if (s_ != 0)
254      aiter_->Reset();
255    pos_ = 0;
256  }
257  virtual void Seek(size_t a) {
258    if (s_ != 0) {
259      if (a == 0) {
260        aiter_->Reset();
261      } else {
262        aiter_->Seek(a - 1);
263      }
264    }
265    pos_ = a;
266  }
267
268 private:
269  ArcIterator< Fst<A> > *aiter_;
270  StateId s_;
271  size_t pos_;
272  mutable A arc_;
273  DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
274};
275
276
277template <class A> inline void
278ComplementFst<A>::InitStateIterator(StateIteratorData<A> *data) const {
279  data->base = new StateIterator< ComplementFst<A> >(*this);
280}
281
282template <class A> inline void
283ComplementFst<A>::InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
284  data->base = new ArcIterator< ComplementFst<A> >(*this, s);
285}
286
287
288// Useful alias when using StdArc.
289typedef ComplementFst<StdArc> StdComplementFst;
290
291}  // namespace fst
292
293#endif  // FST_LIB_COMPLEMENT_H__
294