1 // vector-fst.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 // Simple concrete, mutable FST whose states and arcs are stored in STL 18 // vectors. 19 20 #ifndef FST_LIB_VECTOR_FST_H__ 21 #define FST_LIB_VECTOR_FST_H__ 22 23 #include <string> 24 #include <string.h> 25 26 #include "fst/lib/mutable-fst.h" 27 #include "fst/lib/test-properties.h" 28 29 namespace fst { 30 31 template <class A> class VectorFst; 32 33 // States and arcs implemented by STL vectors, templated on the 34 // State definition. This does not manage the Fst properties. 35 template <class State> 36 class VectorFstBaseImpl : public FstImpl<typename State::Arc> { 37 public: 38 typedef typename State::Arc Arc; 39 typedef typename Arc::Weight Weight; 40 typedef typename Arc::StateId StateId; 41 42 VectorFstBaseImpl() : start_(kNoStateId) {} 43 44 ~VectorFstBaseImpl() { 45 for (StateId s = 0; s < (StateId)states_.size(); ++s) 46 delete states_[s]; 47 } 48 49 StateId Start() const { return start_; } 50 51 Weight Final(StateId s) const { return states_[s]->final; } 52 53 StateId NumStates() const { return states_.size(); } 54 55 size_t NumArcs(StateId s) const { return states_[s]->arcs.size(); } 56 57 void SetStart(StateId s) { start_ = s; } 58 59 void SetFinal(StateId s, Weight w) { states_[s]->final = w; } 60 61 StateId AddState() { 62 states_.push_back(new State); 63 return states_.size() - 1; 64 } 65 66 StateId AddState(State *state) { 67 states_.push_back(state); 68 return states_.size() - 1; 69 } 70 71 void AddArc(StateId s, const Arc &arc) { 72 states_[s]->arcs.push_back(arc); 73 } 74 75 void DeleteStates(const vector<StateId>& dstates) { 76 vector<StateId> newid(states_.size(), 0); 77 for (size_t i = 0; i < dstates.size(); ++i) 78 newid[dstates[i]] = kNoStateId; 79 StateId nstates = 0; 80 for (StateId s = 0; s < (StateId)states_.size(); ++s) { 81 if (newid[s] != kNoStateId) { 82 newid[s] = nstates; 83 if (s != nstates) 84 states_[nstates] = states_[s]; 85 ++nstates; 86 } else { 87 delete states_[s]; 88 } 89 } 90 states_.resize(nstates); 91 for (StateId s = 0; s < (StateId)states_.size(); ++s) { 92 vector<Arc> &arcs = states_[s]->arcs; 93 size_t narcs = 0; 94 for (size_t i = 0; i < arcs.size(); ++i) { 95 StateId t = newid[arcs[i].nextstate]; 96 if (t != kNoStateId) { 97 arcs[i].nextstate = t; 98 if (i != narcs) 99 arcs[narcs] = arcs[i]; 100 ++narcs; 101 } else { 102 if (arcs[i].ilabel == 0) 103 --states_[s]->niepsilons; 104 if (arcs[i].olabel == 0) 105 --states_[s]->noepsilons; 106 } 107 } 108 arcs.resize(narcs); 109 } 110 if (Start() != kNoStateId) 111 SetStart(newid[Start()]); 112 } 113 114 void DeleteStates() { 115 for (StateId s = 0; s < (StateId)states_.size(); ++s) 116 delete states_[s]; 117 states_.clear(); 118 SetStart(kNoStateId); 119 } 120 121 void DeleteArcs(StateId s, size_t n) { 122 states_[s]->arcs.resize(states_[s]->arcs.size() - n); 123 } 124 125 void DeleteArcs(StateId s) { states_[s]->arcs.clear(); } 126 127 State *GetState(StateId s) { return states_[s]; } 128 129 const State *GetState(StateId s) const { return states_[s]; } 130 131 void SetState(StateId s, State *state) { states_[s] = state; } 132 133 void ReserveStates(StateId n) { states_.reserve(n); } 134 135 void ReserveArcs(StateId s, size_t n) { states_[s]->arcs.reserve(n); } 136 137 // Provide information needed for generic state iterator 138 void InitStateIterator(StateIteratorData<Arc> *data) const { 139 data->base = 0; 140 data->nstates = states_.size(); 141 } 142 143 // Provide information needed for generic arc iterator 144 void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const { 145 data->base = 0; 146 data->narcs = states_[s]->arcs.size(); 147 data->arcs = data->narcs > 0 ? &states_[s]->arcs[0] : 0; 148 data->ref_count = 0; 149 } 150 151 private: 152 vector<State *> states_; // States represenation. 153 StateId start_; // initial state 154 155 DISALLOW_EVIL_CONSTRUCTORS(VectorFstBaseImpl); 156 }; 157 158 // Arcs implemented by an STL vector per state. 159 template <class A> 160 struct VectorState { 161 typedef A Arc; 162 typedef typename A::Weight Weight; 163 typedef typename A::StateId StateId; 164 165 VectorState() : final(Weight::Zero()), niepsilons(0), noepsilons(0) {} 166 167 Weight final; // Final weight 168 vector<A> arcs; // Arcs represenation 169 size_t niepsilons; // # of input epsilons 170 size_t noepsilons; // # of output epsilons 171 }; 172 173 // This is a VectorFstBaseImpl container that holds VectorState's. It 174 // manages Fst properties and the # of input and output epsilons. 175 template <class A> 176 class VectorFstImpl : public VectorFstBaseImpl< VectorState<A> > { 177 public: 178 using FstImpl<A>::SetType; 179 using FstImpl<A>::SetProperties; 180 using FstImpl<A>::Properties; 181 using FstImpl<A>::WriteHeaderAndSymbols; 182 183 using VectorFstBaseImpl<VectorState<A> >::Start; 184 using VectorFstBaseImpl<VectorState<A> >::NumStates; 185 186 friend class MutableArcIterator< VectorFst<A> >; 187 188 typedef VectorFstBaseImpl< VectorState<A> > BaseImpl; 189 typedef typename A::Weight Weight; 190 typedef typename A::StateId StateId; 191 192 VectorFstImpl() { 193 SetType("vector"); 194 SetProperties(kNullProperties | kStaticProperties); 195 } 196 explicit VectorFstImpl(const Fst<A> &fst); 197 198 static VectorFstImpl<A> *Read(istream &strm, const FstReadOptions &opts); 199 200 size_t NumInputEpsilons(StateId s) const { return this->GetState(s)->niepsilons; } 201 202 size_t NumOutputEpsilons(StateId s) const { return this->GetState(s)->noepsilons; } 203 204 bool Write(ostream &strm, const FstWriteOptions &opts) const; 205 206 void SetStart(StateId s) { 207 BaseImpl::SetStart(s); 208 SetProperties(Properties() & kSetStartProperties); 209 if (Properties() & kAcyclic) 210 SetProperties(Properties() | kInitialAcyclic); 211 } 212 213 void SetFinal(StateId s, Weight w) { 214 Weight ow = this->Final(s); 215 if (ow != Weight::Zero() && ow != Weight::One()) 216 SetProperties(Properties() & ~kWeighted); 217 BaseImpl::SetFinal(s, w); 218 if (w != Weight::Zero() && w != Weight::One()) { 219 SetProperties(Properties() | kWeighted); 220 SetProperties(Properties() & ~kUnweighted); 221 } 222 SetProperties(Properties() & 223 (kSetFinalProperties | kWeighted | kUnweighted)); 224 } 225 226 StateId AddState() { 227 StateId s = BaseImpl::AddState(); 228 SetProperties(Properties() & kAddStateProperties); 229 return s; 230 } 231 232 void AddArc(StateId s, const A &arc) { 233 VectorState<A> *state = this->GetState(s); 234 if (arc.ilabel != arc.olabel) { 235 SetProperties(Properties() | kNotAcceptor); 236 SetProperties(Properties() & ~kAcceptor); 237 } 238 if (arc.ilabel == 0) { 239 ++state->niepsilons; 240 SetProperties(Properties() | kIEpsilons); 241 SetProperties(Properties() & ~kNoIEpsilons); 242 if (arc.olabel == 0) { 243 SetProperties(Properties() | kEpsilons); 244 SetProperties(Properties() & ~kNoEpsilons); 245 } 246 } 247 if (arc.olabel == 0) { 248 ++state->noepsilons; 249 SetProperties(Properties() | kOEpsilons); 250 SetProperties(Properties() & ~kNoOEpsilons); 251 } 252 if (!state->arcs.empty()) { 253 A &parc = state->arcs.back(); 254 if (parc.ilabel > arc.ilabel) { 255 SetProperties(Properties() | kNotILabelSorted); 256 SetProperties(Properties() & ~kILabelSorted); 257 } 258 if (parc.olabel > arc.olabel) { 259 SetProperties(Properties() | kNotOLabelSorted); 260 SetProperties(Properties() & ~kOLabelSorted); 261 } 262 } 263 if (arc.weight != Weight::Zero() && arc.weight != Weight::One()) { 264 SetProperties(Properties() | kWeighted); 265 SetProperties(Properties() & ~kUnweighted); 266 } 267 if (arc.nextstate <= s) { 268 SetProperties(Properties() | kNotTopSorted); 269 SetProperties(Properties() & ~kTopSorted); 270 } 271 SetProperties(Properties() & 272 (kAddArcProperties | kAcceptor | 273 kNoEpsilons | kNoIEpsilons | kNoOEpsilons | 274 kILabelSorted | kOLabelSorted | kUnweighted | kTopSorted)); 275 if (Properties() & kTopSorted) 276 SetProperties(Properties() | kAcyclic | kInitialAcyclic); 277 BaseImpl::AddArc(s, arc); 278 } 279 280 void DeleteStates(const vector<StateId> &dstates) { 281 BaseImpl::DeleteStates(dstates); 282 SetProperties(Properties() & kDeleteStatesProperties); 283 } 284 285 void DeleteStates() { 286 BaseImpl::DeleteStates(); 287 SetProperties(kNullProperties | kStaticProperties); 288 } 289 290 void DeleteArcs(StateId s, size_t n) { 291 const vector<A> &arcs = this->GetState(s)->arcs; 292 for (size_t i = 0; i < n; ++i) { 293 size_t j = arcs.size() - i - 1; 294 if (arcs[j].ilabel == 0) 295 --this->GetState(s)->niepsilons; 296 if (arcs[j].olabel == 0) 297 --this->GetState(s)->noepsilons; 298 } 299 BaseImpl::DeleteArcs(s, n); 300 SetProperties(Properties() & kDeleteArcsProperties); 301 } 302 303 void DeleteArcs(StateId s) { 304 this->GetState(s)->niepsilons = 0; 305 this->GetState(s)->noepsilons = 0; 306 BaseImpl::DeleteArcs(s); 307 SetProperties(Properties() & kDeleteArcsProperties); 308 } 309 310 private: 311 // Properties always true of this Fst class 312 static const uint64 kStaticProperties = kExpanded | kMutable; 313 // Current file format version 314 static const int kFileVersion = 2; 315 // Minimum file format version supported 316 static const int kMinFileVersion = 2; 317 318 DISALLOW_EVIL_CONSTRUCTORS(VectorFstImpl); 319 }; 320 321 template <class A> 322 VectorFstImpl<A>::VectorFstImpl(const Fst<A> &fst) { 323 SetType("vector"); 324 SetProperties(fst.Properties(kCopyProperties, false) | kStaticProperties); 325 this->SetInputSymbols(fst.InputSymbols()); 326 this->SetOutputSymbols(fst.OutputSymbols()); 327 BaseImpl::SetStart(fst.Start()); 328 329 for (StateIterator< Fst<A> > siter(fst); 330 !siter.Done(); 331 siter.Next()) { 332 StateId s = siter.Value(); 333 BaseImpl::AddState(); 334 BaseImpl::SetFinal(s, fst.Final(s)); 335 this->ReserveArcs(s, fst.NumArcs(s)); 336 for (ArcIterator< Fst<A> > aiter(fst, s); 337 !aiter.Done(); 338 aiter.Next()) { 339 const A &arc = aiter.Value(); 340 BaseImpl::AddArc(s, arc); 341 if (arc.ilabel == 0) 342 ++this->GetState(s)->niepsilons; 343 if (arc.olabel == 0) 344 ++this->GetState(s)->noepsilons; 345 } 346 } 347 } 348 349 template <class A> 350 VectorFstImpl<A> *VectorFstImpl<A>::Read(istream &strm, 351 const FstReadOptions &opts) { 352 VectorFstImpl<A> *impl = new VectorFstImpl; 353 FstHeader hdr; 354 if (!impl->ReadHeaderAndSymbols(strm, opts, kMinFileVersion, &hdr)) 355 return 0; 356 impl->BaseImpl::SetStart(hdr.Start()); 357 impl->ReserveStates(hdr.NumStates()); 358 359 for (StateId s = 0; s < hdr.NumStates(); ++s) { 360 impl->BaseImpl::AddState(); 361 VectorState<A> *state = impl->GetState(s); 362 state->final.Read(strm); 363 int64 narcs; 364 ReadType(strm, &narcs); 365 if (!strm) { 366 LOG(ERROR) << "VectorFst::Read: read failed: " << opts.source; 367 return 0; 368 } 369 impl->ReserveArcs(s, narcs); 370 for (size_t j = 0; j < narcs; ++j) { 371 A arc; 372 ReadType(strm, &arc.ilabel); 373 ReadType(strm, &arc.olabel); 374 arc.weight.Read(strm); 375 ReadType(strm, &arc.nextstate); 376 if (!strm) { 377 LOG(ERROR) << "VectorFst::Read: read failed: " << opts.source; 378 return 0; 379 } 380 impl->BaseImpl::AddArc(s, arc); 381 if (arc.ilabel == 0) 382 ++state->niepsilons; 383 if (arc.olabel == 0) 384 ++state->noepsilons; 385 } 386 } 387 return impl; 388 } 389 390 // Converts a string into a weight. 391 template <class W> class WeightFromString { 392 public: 393 W operator()(const string &s); 394 }; 395 396 // Generic case fails. 397 template <class W> inline 398 W WeightFromString<W>::operator()(const string &s) { 399 LOG(FATAL) << "VectorFst::Read: Obsolete file format"; 400 return W(); 401 } 402 403 // TropicalWeight version. 404 template <> inline 405 TropicalWeight WeightFromString<TropicalWeight>::operator()(const string &s) { 406 float f; 407 memcpy(&f, s.data(), sizeof(f)); 408 return TropicalWeight(f); 409 } 410 411 // LogWeight version. 412 template <> inline 413 LogWeight WeightFromString<LogWeight>::operator()(const string &s) { 414 float f; 415 memcpy(&f, s.data(), sizeof(f)); 416 return LogWeight(f); 417 } 418 419 template <class A> 420 bool VectorFstImpl<A>::Write(ostream &strm, 421 const FstWriteOptions &opts) const { 422 FstHeader hdr; 423 hdr.SetStart(Start()); 424 hdr.SetNumStates(NumStates()); 425 WriteHeaderAndSymbols(strm, opts, kFileVersion, &hdr); 426 if (!strm) 427 return false; 428 429 for (StateId s = 0; s < NumStates(); ++s) { 430 const VectorState<A> *state = this->GetState(s); 431 state->final.Write(strm); 432 int64 narcs = state->arcs.size(); 433 WriteType(strm, narcs); 434 for (size_t a = 0; a < narcs; ++a) { 435 const A &arc = state->arcs[a]; 436 WriteType(strm, arc.ilabel); 437 WriteType(strm, arc.olabel); 438 arc.weight.Write(strm); 439 WriteType(strm, arc.nextstate); 440 } 441 } 442 strm.flush(); 443 if (!strm) 444 LOG(ERROR) << "VectorFst::Write: write failed: " << opts.source; 445 return strm; 446 } 447 448 // Simple concrete, mutable FST. Supports additional operations: 449 // ReserveStates and ReserveArcs (cf. STL vectors). This class 450 // attaches interface to implementation and handles reference 451 // counting. 452 template <class A> 453 class VectorFst : public MutableFst<A> { 454 public: 455 friend class StateIterator< VectorFst<A> >; 456 friend class ArcIterator< VectorFst<A> >; 457 friend class MutableArcIterator< VectorFst<A> >; 458 459 typedef A Arc; 460 typedef typename A::Weight Weight; 461 typedef typename A::StateId StateId; 462 463 VectorFst() : impl_(new VectorFstImpl<A>) {} 464 465 VectorFst(const VectorFst<A> &fst) : MutableFst<A>(fst), impl_(fst.impl_) { 466 impl_->IncrRefCount(); 467 } 468 explicit VectorFst(const Fst<A> &fst) : impl_(new VectorFstImpl<A>(fst)) {} 469 470 virtual ~VectorFst() { if (!impl_->DecrRefCount()) delete impl_; } 471 472 VectorFst<A> &operator=(const VectorFst<A> &fst) { 473 if (this != &fst) { 474 if (!impl_->DecrRefCount()) delete impl_; 475 fst.impl_->IncrRefCount(); 476 impl_ = fst.impl_; 477 } 478 return *this; 479 } 480 481 virtual VectorFst<A> &operator=(const Fst<A> &fst) { 482 if (this != &fst) { 483 if (!impl_->DecrRefCount()) delete impl_; 484 impl_ = new VectorFstImpl<A>(fst); 485 } 486 return *this; 487 } 488 489 virtual StateId Start() const { return impl_->Start(); } 490 491 virtual Weight Final(StateId s) const { return impl_->Final(s); } 492 493 virtual StateId NumStates() const { return impl_->NumStates(); } 494 495 virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); } 496 497 virtual size_t NumInputEpsilons(StateId s) const { 498 return impl_->NumInputEpsilons(s); 499 } 500 501 virtual size_t NumOutputEpsilons(StateId s) const { 502 return impl_->NumOutputEpsilons(s); 503 } 504 505 virtual uint64 Properties(uint64 mask, bool test) const { 506 if (test) { 507 uint64 known, test = TestProperties(*this, mask, &known); 508 impl_->SetProperties(test, known); 509 return test & mask; 510 } else { 511 return impl_->Properties(mask); 512 } 513 } 514 515 virtual const string& Type() const { return impl_->Type(); } 516 517 // Get a copy of this VectorFst 518 virtual VectorFst<A> *Copy() const { 519 impl_->IncrRefCount(); 520 return new VectorFst<A>(impl_); 521 } 522 523 // Read a VectorFst from an input stream; return NULL on error 524 static VectorFst<A> *Read(istream &strm, const FstReadOptions &opts) { 525 VectorFstImpl<A>* impl = VectorFstImpl<A>::Read(strm, opts); 526 return impl ? new VectorFst<A>(impl) : 0; 527 } 528 529 // Read a VectorFst from a file; return NULL on error 530 static VectorFst<A> *Read(const string &filename) { 531 ifstream strm(filename.c_str()); 532 if (!strm) { 533 LOG(ERROR) << "VectorFst::Read: Can't open file: " << filename; 534 return 0; 535 } 536 return Read(strm, FstReadOptions(filename)); 537 } 538 539 // Write a VectorFst to an output stream; return false on error 540 virtual bool Write(ostream &strm, const FstWriteOptions &opts) const { 541 return impl_->Write(strm, opts); 542 } 543 544 // Write a VectorFst to a file; return false on error 545 virtual bool Write(const string &filename) const { 546 if (!filename.empty()) { 547 ofstream strm(filename.c_str()); 548 if (!strm) { 549 LOG(ERROR) << "VectorFst::Write: Can't open file: " << filename; 550 return false; 551 } 552 return Write(strm, FstWriteOptions(filename)); 553 } else { 554 return Write(std::cout, FstWriteOptions("standard output")); 555 } 556 } 557 558 virtual SymbolTable* InputSymbols() { 559 return impl_->InputSymbols(); 560 } 561 562 virtual SymbolTable* OutputSymbols() { 563 return impl_->OutputSymbols(); 564 } 565 566 virtual const SymbolTable* InputSymbols() const { 567 return impl_->InputSymbols(); 568 } 569 570 virtual const SymbolTable* OutputSymbols() const { 571 return impl_->OutputSymbols(); 572 } 573 574 virtual void SetStart(StateId s) { 575 MutateCheck(); 576 impl_->SetStart(s); 577 } 578 579 virtual void SetFinal(StateId s, Weight w) { 580 MutateCheck(); 581 impl_->SetFinal(s, w); 582 } 583 584 virtual void SetProperties(uint64 props, uint64 mask) { 585 impl_->SetProperties(props, mask); 586 } 587 588 virtual StateId AddState() { 589 MutateCheck(); 590 return impl_->AddState(); 591 } 592 593 virtual void AddArc(StateId s, const A &arc) { 594 MutateCheck(); 595 impl_->AddArc(s, arc); 596 } 597 598 virtual void DeleteStates(const vector<StateId> &dstates) { 599 MutateCheck(); 600 impl_->DeleteStates(dstates); 601 } 602 603 virtual void DeleteStates() { 604 MutateCheck(); 605 impl_->DeleteStates(); 606 } 607 608 virtual void DeleteArcs(StateId s, size_t n) { 609 MutateCheck(); 610 impl_->DeleteArcs(s, n); 611 } 612 613 virtual void DeleteArcs(StateId s) { 614 MutateCheck(); 615 impl_->DeleteArcs(s); 616 } 617 618 virtual void SetInputSymbols(const SymbolTable* isyms) { 619 MutateCheck(); 620 impl_->SetInputSymbols(isyms); 621 } 622 623 virtual void SetOutputSymbols(const SymbolTable* osyms) { 624 MutateCheck(); 625 impl_->SetOutputSymbols(osyms); 626 } 627 628 void ReserveStates(StateId n) { 629 MutateCheck(); 630 impl_->ReserveStates(n); 631 } 632 633 void ReserveArcs(StateId s, size_t n) { 634 MutateCheck(); 635 impl_->ReserveArcs(s, n); 636 } 637 638 virtual void InitStateIterator(StateIteratorData<A> *data) const { 639 impl_->InitStateIterator(data); 640 } 641 642 virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const { 643 impl_->InitArcIterator(s, data); 644 } 645 646 virtual inline 647 void InitMutableArcIterator(StateId s, MutableArcIteratorData<A> *); 648 649 private: 650 explicit VectorFst(VectorFstImpl<A> *impl) : impl_(impl) {} 651 652 void MutateCheck() { 653 // Copy on write 654 if (impl_->RefCount() > 1) { 655 impl_->DecrRefCount(); 656 impl_ = new VectorFstImpl<A>(*this); 657 } 658 } 659 660 VectorFstImpl<A> *impl_; // FST's impl 661 }; 662 663 // Specialization for VectorFst; see generic version in fst.h 664 // for sample usage (but use the VectorFst type!). This version 665 // should inline. 666 template <class A> 667 class StateIterator< VectorFst<A> > { 668 public: 669 typedef typename A::StateId StateId; 670 671 explicit StateIterator(const VectorFst<A> &fst) 672 : nstates_(fst.impl_->NumStates()), s_(0) {} 673 674 bool Done() const { return s_ >= nstates_; } 675 676 StateId Value() const { return s_; } 677 678 void Next() { ++s_; } 679 680 void Reset() { s_ = 0; } 681 682 private: 683 StateId nstates_; 684 StateId s_; 685 686 DISALLOW_EVIL_CONSTRUCTORS(StateIterator); 687 }; 688 689 // Specialization for VectorFst; see generic version in fst.h 690 // for sample usage (but use the VectorFst type!). This version 691 // should inline. 692 template <class A> 693 class ArcIterator< VectorFst<A> > { 694 public: 695 typedef typename A::StateId StateId; 696 697 ArcIterator(const VectorFst<A> &fst, StateId s) 698 : arcs_(fst.impl_->GetState(s)->arcs), i_(0) {} 699 700 bool Done() const { return i_ >= arcs_.size(); } 701 702 const A& Value() const { return arcs_[i_]; } 703 704 void Next() { ++i_; } 705 706 void Reset() { i_ = 0; } 707 708 void Seek(size_t a) { i_ = a; } 709 710 private: 711 const vector<A>& arcs_; 712 size_t i_; 713 714 DISALLOW_EVIL_CONSTRUCTORS(ArcIterator); 715 }; 716 717 // Specialization for VectorFst; see generic version in fst.h 718 // for sample usage (but use the VectorFst type!). This version 719 // should inline. 720 template <class A> 721 class MutableArcIterator< VectorFst<A> > 722 : public MutableArcIteratorBase<A> { 723 public: 724 typedef typename A::StateId StateId; 725 typedef typename A::Weight Weight; 726 727 MutableArcIterator(VectorFst<A> *fst, StateId s) : i_(0) { 728 fst->MutateCheck(); 729 state_ = fst->impl_->GetState(s); 730 properties_ = &fst->impl_->properties_; 731 } 732 733 virtual bool Done() const { return i_ >= state_->arcs.size(); } 734 735 virtual const A& Value() const { return state_->arcs[i_]; } 736 737 virtual void Next() { ++i_; } 738 739 virtual void Reset() { i_ = 0; } 740 741 virtual void Seek(size_t a) { i_ = a; } 742 743 virtual void SetValue(const A &arc) { 744 A& oarc = state_->arcs[i_]; 745 if (oarc.ilabel != oarc.olabel) 746 *properties_ &= ~kNotAcceptor; 747 if (oarc.ilabel == 0) { 748 --state_->niepsilons; 749 *properties_ &= ~kIEpsilons; 750 if (oarc.olabel == 0) 751 *properties_ &= ~kEpsilons; 752 } 753 if (oarc.olabel == 0) { 754 --state_->noepsilons; 755 *properties_ &= ~kOEpsilons; 756 } 757 if (oarc.weight != Weight::Zero() && oarc.weight != Weight::One()) 758 *properties_ &= ~kWeighted; 759 oarc = arc; 760 if (arc.ilabel != arc.olabel) 761 *properties_ |= kNotAcceptor; 762 if (arc.ilabel == 0) { 763 ++state_->niepsilons; 764 *properties_ |= kIEpsilons; 765 if (arc.olabel == 0) 766 *properties_ |= kEpsilons; 767 } 768 if (arc.olabel == 0) { 769 ++state_->noepsilons; 770 *properties_ |= kOEpsilons; 771 } 772 if (arc.weight != Weight::Zero() && arc.weight != Weight::One()) 773 *properties_ |= kWeighted; 774 *properties_ &= kSetArcProperties | kNotAcceptor | 775 kEpsilons | kIEpsilons | kOEpsilons | kWeighted; 776 } 777 778 private: 779 struct VectorState<A> *state_; 780 uint64 *properties_; 781 size_t i_; 782 783 DISALLOW_EVIL_CONSTRUCTORS(MutableArcIterator); 784 }; 785 786 // Provide information needed for the generic mutable arc iterator 787 template <class A> inline 788 void VectorFst<A>::InitMutableArcIterator( 789 StateId s, MutableArcIteratorData<A> *data) { 790 data->base = new MutableArcIterator< VectorFst<A> >(this, s); 791 } 792 793 // A useful alias when using StdArc. 794 typedef VectorFst<StdArc> StdVectorFst; 795 796 } // namespace fst 797 798 #endif // FST_LIB_VECTOR_FST_H__ 799