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>
27using std::vector;
28
29#include <fst/fst.h>
30#include <fst/test-properties.h>
31
32
33namespace fst {
34
35template <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.
47template <class A>
48class 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
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
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
79  ~ComplementFstImpl() { delete fst_; }
80
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.
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
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
107  size_t NumInputEpsilons(StateId s) const {
108    return s == 0 ? 0 : fst_->NumInputEpsilons(s - 1);
109  }
110
111  size_t NumOutputEpsilons(StateId s) const {
112    return s == 0 ? 0 : fst_->NumOutputEpsilons(s - 1);
113  }
114
115
116  uint64 Properties() const { return Properties(kFstProperties); }
117
118  // Set error if found; return FST impl properties.
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.
139template <class A>
140class 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
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.
182  Impl *GetImpl() const { return ImplToFst<Impl>::GetImpl(); }
183
184  void operator=(const ComplementFst<A> &fst);  // disallow
185};
186
187template <class A> const typename A::Label ComplementFst<A>::kRhoLabel;
188
189
190// Specialization for ComplementFst.
191template <class A>
192class StateIterator< ComplementFst<A> > : public StateIteratorBase<A> {
193 public:
194  typedef typename A::StateId StateId;
195  typedef typename A::Label Label;
196
197  explicit StateIterator(const ComplementFst<A> &fst)
198      : siter_(*fst.GetImpl()->fst_), s_(0) {
199  }
200
201  bool Done() const { return s_ > 0 && siter_.Done(); }
202
203  StateId Value() const { return s_; }
204
205  void Next() {
206    if (s_ != 0)
207      siter_.Next();
208    ++s_;
209  }
210
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.
220  virtual bool Done_() const { return Done(); }
221  virtual StateId Value_() const { return Value(); }
222  virtual void Next_() { Next(); }
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.
233template <class A>
234class 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
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
246  virtual ~ArcIterator() { delete aiter_; }
247
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.
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
268  void Next() {
269    if (s_ != 0 && pos_ > 0)
270      aiter_->Next();
271    ++pos_;
272  }
273
274  size_t Position() const {
275    return pos_;
276  }
277
278  void Reset() {
279    if (s_ != 0)
280      aiter_->Reset();
281    pos_ = 0;
282  }
283
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
295  uint32 Flags() const {
296    return kArcValueFlags;
297  }
298
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.
305  virtual bool Done_() const { return Done(); }
306  virtual const A& Value_() const { return Value(); }
307  virtual void Next_() { Next(); }
308  virtual size_t Position_() const { return Position(); }
309  virtual void Reset_() { Reset(); }
310  virtual void Seek_(size_t a) { Seek(a); }
311  uint32 Flags_() const { return Flags(); }
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
322template <class A> inline void
323ComplementFst<A>::InitStateIterator(StateIteratorData<A> *data) const {
324  data->base = new StateIterator< ComplementFst<A> >(*this);
325}
326
327template <class A> inline void
328ComplementFst<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.
334typedef ComplementFst<StdArc> StdComplementFst;
335
336}  // namespace fst
337
338#endif  // FST_LIB_COMPLEMENT_H__
339