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