src/include/fst/vector-fst.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // Simple concrete, mutable FST whose states and arcs are stored in STL vectors.
   5
   6 #ifndef FST_VECTOR_FST_H_
   7 #define FST_VECTOR_FST_H_
   8
   9 #include <string>
  10 #include <utility>
  11 #include <vector>
  12
  13 #include <fst/log.h>
  14
  15 #include <fst/fst-decl.h>  // For optional argument declarations
  16 #include <fst/mutable-fst.h>
  17 #include <fst/test-properties.h>
  18
  19
  20 namespace fst {
  21
  22 template <class A, class S>
  23 class VectorFst;
  24
  25 template <class F, class G>
  26 void Cast(const F &, G *);
  27
  28 // Arcs (of type A) implemented by an STL vector per state. M specifies Arc
  29 // allocator (default declared in fst-decl.h).
  30 template <class A, class M /* = std::allocator<A> */>
  31 class VectorState {
  32  public:
  33   using Arc = A;
  34   using StateId = typename Arc::StateId;
  35   using Weight = typename Arc::Weight;
  36   using ArcAllocator = M;
  37   using StateAllocator =
  38       typename ArcAllocator::template rebind<VectorState<Arc, M>>::other;
  39
  40   // Provide STL allocator for arcs.
  41   explicit VectorState(const ArcAllocator &alloc)
  42       : final_(Weight::Zero()), niepsilons_(0), noepsilons_(0), arcs_(alloc) {}
  43
  44   VectorState(const VectorState<A, M> &state, const ArcAllocator &alloc)
  45       : final_(state.Final()),
  46         niepsilons_(state.NumInputEpsilons()),
  47         noepsilons_(state.NumOutputEpsilons()),
  48         arcs_(state.arcs_.begin(), state.arcs_.end(), alloc) {}
  49
  50   void Reset() {
  51     final_ = Weight::Zero();
  52     niepsilons_ = 0;
  53     noepsilons_ = 0;
  54     arcs_.clear();
  55   }
  56
  57   Weight Final() const { return final_; }
  58
  59   size_t NumInputEpsilons() const { return niepsilons_; }
  60
  61   size_t NumOutputEpsilons() const { return noepsilons_; }
  62
  63   size_t NumArcs() const { return arcs_.size(); }
  64
  65   const Arc &GetArc(size_t n) const { return arcs_[n]; }
  66
  67   const Arc *Arcs() const { return !arcs_.empty() ? &arcs_[0] : nullptr; }
  68
  69   Arc *MutableArcs() { return !arcs_.empty() ? &arcs_[0] : nullptr; }
  70
  71   void ReserveArcs(size_t n) { arcs_.reserve(n); }
  72
  73   void SetFinal(Weight weight) { final_ = std::move(weight); }
  74
  75   void SetNumInputEpsilons(size_t n) { niepsilons_ = n; }
  76
  77   void SetNumOutputEpsilons(size_t n) { noepsilons_ = n; }
  78
  79   void AddArc(const Arc &arc) {
  80     if (arc.ilabel == 0) ++niepsilons_;
  81     if (arc.olabel == 0) ++noepsilons_;
  82     arcs_.push_back(arc);
  83   }
  84
  85   void SetArc(const Arc &arc, size_t n) {
  86     if (arcs_[n].ilabel == 0) --niepsilons_;
  87     if (arcs_[n].olabel == 0) --noepsilons_;
  88     if (arc.ilabel == 0) ++niepsilons_;
  89     if (arc.olabel == 0) ++noepsilons_;
  90     arcs_[n] = arc;
  91   }
  92
  93   void DeleteArcs() {
  94     niepsilons_ = 0;
  95     noepsilons_ = 0;
  96     arcs_.clear();
  97   }
  98
  99   void DeleteArcs(size_t n) {
 100     for (size_t i = 0; i < n; ++i) {
 101       if (arcs_.back().ilabel == 0) --niepsilons_;
 102       if (arcs_.back().olabel == 0) --noepsilons_;
 103       arcs_.pop_back();
 104     }
 105   }
 106
 107   // For state class allocation.
 108   void *operator new(size_t size, StateAllocator *alloc) {
 109     return alloc->allocate(1);
 110   }
 111
 112   // For state destruction and memory freeing.
 113   static void Destroy(VectorState<A, M> *state, StateAllocator *alloc) {
 114     if (state) {
 115       state->~VectorState<A, M>();
 116       alloc->deallocate(state, 1);
 117     }
 118   }
 119
 120  private:
 121   Weight final_;                       // Final weight.
 122   size_t niepsilons_;                  // # of input epsilons
 123   size_t noepsilons_;                  // # of output epsilons
 124   std::vector<A, ArcAllocator> arcs_;  // Arc container.
 125 };
 126
 127 namespace internal {
 128
 129 // States are implemented by STL vectors, templated on the
 130 // State definition. This does not manage the Fst properties.
 131 template <class S>
 132 class VectorFstBaseImpl : public FstImpl<typename S::Arc> {
 133  public:
 134   using State = S;
 135   using Arc = typename State::Arc;
 136   using StateId = typename Arc::StateId;
 137   using Weight = typename Arc::Weight;
 138
 139   VectorFstBaseImpl() : start_(kNoStateId) {}
 140
 141   ~VectorFstBaseImpl() override {
 142     for (StateId s = 0; s < states_.size(); ++s) {
 143       State::Destroy(states_[s], &state_alloc_);
 144     }
 145   }
 146
 147   StateId Start() const { return start_; }
 148
 149   Weight Final(StateId state) const { return states_[state]->Final(); }
 150
 151   StateId NumStates() const { return states_.size(); }
 152
 153   size_t NumArcs(StateId state) const { return states_[state]->NumArcs(); }
 154
 155   size_t NumInputEpsilons(StateId state) const {
 156     return GetState(state)->NumInputEpsilons();
 157   }
 158
 159   size_t NumOutputEpsilons(StateId state) const {
 160     return GetState(state)->NumOutputEpsilons();
 161   }
 162
 163   void SetStart(StateId state) { start_ = state; }
 164
 165   void SetFinal(StateId state, Weight weight) {
 166     states_[state]->SetFinal(std::move(weight));
 167   }
 168
 169   StateId AddState() {
 170     states_.push_back(new (&state_alloc_) State(arc_alloc_));
 171     return states_.size() - 1;
 172   }
 173
 174   StateId AddState(State *state) {
 175     states_.push_back(state);
 176     return states_.size() - 1;
 177   }
 178
 179   void AddArc(StateId state, const Arc &arc) { states_[state]->AddArc(arc); }
 180
 181   void DeleteStates(const std::vector<StateId> &dstates) {
 182     std::vector<StateId> newid(states_.size(), 0);
 183     for (StateId i = 0; i < dstates.size(); ++i) newid[dstates[i]] = kNoStateId;
 184     StateId nstates = 0;
 185     for (StateId state = 0; state < states_.size(); ++state) {
 186       if (newid[state] != kNoStateId) {
 187         newid[state] = nstates;
 188         if (state != nstates) states_[nstates] = states_[state];
 189         ++nstates;
 190       } else {
 191         State::Destroy(states_[state], &state_alloc_);
 192       }
 193     }
 194     states_.resize(nstates);
 195     for (StateId state = 0; state < states_.size(); ++state) {
 196       auto *arcs = states_[state]->MutableArcs();
 197       size_t narcs = 0;
 198       auto nieps = states_[state]->NumInputEpsilons();
 199       auto noeps = states_[state]->NumOutputEpsilons();
 200       for (size_t i = 0; i < states_[state]->NumArcs(); ++i) {
 201         const auto t = newid[arcs[i].nextstate];
 202         if (t != kNoStateId) {
 203           arcs[i].nextstate = t;
 204           if (i != narcs) arcs[narcs] = arcs[i];
 205           ++narcs;
 206         } else {
 207           if (arcs[i].ilabel == 0) --nieps;
 208           if (arcs[i].olabel == 0) --noeps;
 209         }
 210       }
 211       states_[state]->DeleteArcs(states_[state]->NumArcs() - narcs);
 212       states_[state]->SetNumInputEpsilons(nieps);
 213       states_[state]->SetNumOutputEpsilons(noeps);
 214     }
 215     if (Start() != kNoStateId) SetStart(newid[Start()]);
 216   }
 217
 218   void DeleteStates() {
 219     for (StateId state = 0; state < states_.size(); ++state) {
 220       State::Destroy(states_[state], &state_alloc_);
 221     }
 222     states_.clear();
 223     SetStart(kNoStateId);
 224   }
 225
 226   void DeleteArcs(StateId state, size_t n) { states_[state]->DeleteArcs(n); }
 227
 228   void DeleteArcs(StateId state) { states_[state]->DeleteArcs(); }
 229
 230   State *GetState(StateId state) { return states_[state]; }
 231
 232   const State *GetState(StateId state) const { return states_[state]; }
 233
 234   void SetState(StateId state, State *vstate) { states_[state] = vstate; }
 235
 236   void ReserveStates(StateId n) { states_.reserve(n); }
 237
 238   void ReserveArcs(StateId state, size_t n) { states_[state]->ReserveArcs(n); }
 239
 240   // Provide information needed for generic state iterator.
 241   void InitStateIterator(StateIteratorData<Arc> *data) const {
 242     data->base = nullptr;
 243     data->nstates = states_.size();
 244   }
 245
 246   // Provide information needed for generic arc iterator.
 247   void InitArcIterator(StateId state, ArcIteratorData<Arc> *data) const {
 248     data->base = nullptr;
 249     data->narcs = states_[state]->NumArcs();
 250     data->arcs = states_[state]->Arcs();
 251     data->ref_count = nullptr;
 252   }
 253
 254  private:
 255   std::vector<State *> states_;                 // States represenation.
 256   StateId start_;                               // Initial state.
 257   typename State::StateAllocator state_alloc_;  // For state allocation.
 258   typename State::ArcAllocator arc_alloc_;      // For arc allocation.
 259
 260   VectorFstBaseImpl(const VectorFstBaseImpl &) = delete;
 261   VectorFstBaseImpl &operator=(const VectorFstBaseImpl &) = delete;
 262 };
 263
 264 // This is a VectorFstBaseImpl container that holds VectorStates and manages FST
 265 // properties.
 266 template <class S>
 267 class VectorFstImpl : public VectorFstBaseImpl<S> {
 268  public:
 269   using State = S;
 270   using Arc = typename State::Arc;
 271   using Label = typename Arc::Label;
 272   using StateId = typename Arc::StateId;
 273   using Weight = typename Arc::Weight;
 274
 275   using FstImpl<Arc>::SetInputSymbols;
 276   using FstImpl<Arc>::SetOutputSymbols;
 277   using FstImpl<Arc>::SetType;
 278   using FstImpl<Arc>::SetProperties;
 279   using FstImpl<Arc>::Properties;
 280
 281   using VectorFstBaseImpl<S>::Start;
 282   using VectorFstBaseImpl<S>::NumStates;
 283   using VectorFstBaseImpl<S>::GetState;
 284   using VectorFstBaseImpl<S>::ReserveArcs;
 285
 286   friend class MutableArcIterator<VectorFst<Arc, S>>;
 287
 288   using BaseImpl = VectorFstBaseImpl<S>;
 289
 290   VectorFstImpl() {
 291     SetType("vector");
 292     SetProperties(kNullProperties | kStaticProperties);
 293   }
 294
 295   explicit VectorFstImpl(const Fst<Arc> &fst);
 296
 297   static VectorFstImpl<S> *Read(std::istream &strm, const FstReadOptions &opts);
 298
 299   void SetStart(StateId state) {
 300     BaseImpl::SetStart(state);
 301     SetProperties(SetStartProperties(Properties()));
 302   }
 303
 304   void SetFinal(StateId state, Weight weight) {
 305     const auto old_weight = BaseImpl::Final(state);
 306     const auto properties =
 307         SetFinalProperties(Properties(), old_weight, weight);
 308     BaseImpl::SetFinal(state, std::move(weight));
 309     SetProperties(properties);
 310   }
 311
 312   StateId AddState() {
 313     const auto state = BaseImpl::AddState();
 314     SetProperties(AddStateProperties(Properties()));
 315     return state;
 316   }
 317
 318   void AddArc(StateId state, const Arc &arc) {
 319     auto *vstate = GetState(state);
 320     const auto *parc = vstate->NumArcs() == 0
 321                            ? nullptr
 322                            : &(vstate->GetArc(vstate->NumArcs() - 1));
 323     SetProperties(AddArcProperties(Properties(), state, arc, parc));
 324     BaseImpl::AddArc(state, arc);
 325   }
 326
 327   void DeleteStates(const std::vector<StateId> &dstates) {
 328     BaseImpl::DeleteStates(dstates);
 329     SetProperties(DeleteStatesProperties(Properties()));
 330   }
 331
 332   void DeleteStates() {
 333     BaseImpl::DeleteStates();
 334     SetProperties(DeleteAllStatesProperties(Properties(), kStaticProperties));
 335   }
 336
 337   void DeleteArcs(StateId state, size_t n) {
 338     BaseImpl::DeleteArcs(state, n);
 339     SetProperties(DeleteArcsProperties(Properties()));
 340   }
 341
 342   void DeleteArcs(StateId state) {
 343     BaseImpl::DeleteArcs(state);
 344     SetProperties(DeleteArcsProperties(Properties()));
 345   }
 346
 347   // Properties always true of this FST class
 348   static constexpr uint64 kStaticProperties = kExpanded | kMutable;
 349
 350  private:
 351   // Minimum file format version supported.
 352   static constexpr int kMinFileVersion = 2;
 353 };
 354
 355 template <class S>
 356 constexpr uint64 VectorFstImpl<S>::kStaticProperties;
 357
 358 template <class S>
 359 constexpr int VectorFstImpl<S>::kMinFileVersion;
 360
 361 template <class S>
 362 VectorFstImpl<S>::VectorFstImpl(const Fst<Arc> &fst) {
 363   SetType("vector");
 364   SetInputSymbols(fst.InputSymbols());
 365   SetOutputSymbols(fst.OutputSymbols());
 366   BaseImpl::SetStart(fst.Start());
 367   if (fst.Properties(kExpanded, false)) {
 368     BaseImpl::ReserveStates(CountStates(fst));
 369   }
 370   for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
 371     const auto state = siter.Value();
 372     BaseImpl::AddState();
 373     BaseImpl::SetFinal(state, fst.Final(state));
 374     ReserveArcs(state, fst.NumArcs(state));
 375     for (ArcIterator<Fst<Arc>> aiter(fst, state); !aiter.Done(); aiter.Next()) {
 376       const auto &arc = aiter.Value();
 377       BaseImpl::AddArc(state, arc);
 378     }
 379   }
 380   SetProperties(fst.Properties(kCopyProperties, false) | kStaticProperties);
 381 }
 382
 383 template <class S>
 384 VectorFstImpl<S> *VectorFstImpl<S>::Read(std::istream &strm,
 385                                          const FstReadOptions &opts) {
 386   std::unique_ptr<VectorFstImpl<S>> impl(new VectorFstImpl());
 387   FstHeader hdr;
 388   if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) return nullptr;
 389   impl->BaseImpl::SetStart(hdr.Start());
 390   if (hdr.NumStates() != kNoStateId) impl->ReserveStates(hdr.NumStates());
 391   StateId state = 0;
 392   for (; hdr.NumStates() == kNoStateId || state < hdr.NumStates(); ++state) {
 393     Weight weight;
 394     if (!weight.Read(strm)) break;
 395     impl->BaseImpl::AddState();
 396     auto *vstate = impl->GetState(state);
 397     vstate->SetFinal(weight);
 398     int64 narcs;
 399     ReadType(strm, &narcs);
 400     if (!strm) {
 401       LOG(ERROR) << "VectorFst::Read: Read failed: " << opts.source;
 402       return nullptr;
 403     }
 404     impl->ReserveArcs(state, narcs);
 405     for (int64 i = 0; i < narcs; ++i) {
 406       Arc arc;
 407       ReadType(strm, &arc.ilabel);
 408       ReadType(strm, &arc.olabel);
 409       arc.weight.Read(strm);
 410       ReadType(strm, &arc.nextstate);
 411       if (!strm) {
 412         LOG(ERROR) << "VectorFst::Read: Read failed: " << opts.source;
 413         return nullptr;
 414       }
 415       impl->BaseImpl::AddArc(state, arc);
 416     }
 417   }
 418   if (hdr.NumStates() != kNoStateId && state != hdr.NumStates()) {
 419     LOG(ERROR) << "VectorFst::Read: Unexpected end of file: " << opts.source;
 420     return nullptr;
 421   }
 422   return impl.release();
 423 }
 424
 425 }  // namespace internal
 426
 427 // Simple concrete, mutable FST. This class attaches interface to implementation
 428 // and handles reference counting, delegating most methods to ImplToMutableFst.
 429 // Also supports ReserveStates and ReserveArcs methods (cf. STL vector methods).
 430 // The second optional template argument gives the State definition.
 431 template <class A, class S /* = VectorState<A> */>
 432 class VectorFst : public ImplToMutableFst<internal::VectorFstImpl<S>> {
 433  public:
 434   using Arc = A;
 435   using StateId = typename Arc::StateId;
 436
 437   using State = S;
 438   using Impl = internal::VectorFstImpl<State>;
 439
 440   friend class StateIterator<VectorFst<Arc, State>>;
 441   friend class ArcIterator<VectorFst<Arc, State>>;
 442   friend class MutableArcIterator<VectorFst<A, S>>;
 443
 444   template <class F, class G>
 445   friend void Cast(const F &, G *);
 446
 447   VectorFst() : ImplToMutableFst<Impl>(std::make_shared<Impl>()) {}
 448
 449   explicit VectorFst(const Fst<Arc> &fst)
 450       : ImplToMutableFst<Impl>(std::make_shared<Impl>(fst)) {}
 451
 452   VectorFst(const VectorFst<Arc, State> &fst, bool safe = false)
 453       : ImplToMutableFst<Impl>(fst) {}
 454
 455   // Get a copy of this VectorFst. See Fst<>::Copy() for further doc.
 456   VectorFst<Arc, State> *Copy(bool safe = false) const override {
 457     return new VectorFst<Arc, State>(*this, safe);
 458   }
 459
 460   VectorFst<Arc, State> &operator=(const VectorFst<Arc, State> &fst) {
 461     SetImpl(fst.GetSharedImpl());
 462     return *this;
 463   }
 464
 465   VectorFst<Arc, State> &operator=(const Fst<Arc> &fst) override {
 466     if (this != &fst) SetImpl(std::make_shared<Impl>(fst));
 467     return *this;
 468   }
 469
 470   // Reads a VectorFst from an input stream, returning nullptr on error.
 471   static VectorFst<Arc, State> *Read(std::istream &strm,
 472                                      const FstReadOptions &opts) {
 473     auto *impl = Impl::Read(strm, opts);
 474     return impl ? new VectorFst<Arc, State>(std::shared_ptr<Impl>(impl))
 475                 : nullptr;
 476   }
 477
 478   // Read a VectorFst from a file, returning nullptr on error; empty filename
 479   // reads from standard input.
 480   static VectorFst<Arc, State> *Read(const string &filename) {
 481     auto *impl = ImplToExpandedFst<Impl, MutableFst<Arc>>::Read(filename);
 482     return impl ? new VectorFst<Arc, State>(std::shared_ptr<Impl>(impl))
 483                 : nullptr;
 484   }
 485
 486   bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
 487     return WriteFst(*this, strm, opts);
 488   }
 489
 490   bool Write(const string &filename) const override {
 491     return Fst<Arc>::WriteFile(filename);
 492   }
 493
 494   template <class FST>
 495   static bool WriteFst(const FST &fst, std::ostream &strm,
 496                        const FstWriteOptions &opts);
 497
 498   void InitStateIterator(StateIteratorData<Arc> *data) const override {
 499     GetImpl()->InitStateIterator(data);
 500   }
 501
 502   void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
 503     GetImpl()->InitArcIterator(s, data);
 504   }
 505
 506   inline void InitMutableArcIterator(StateId s,
 507                                      MutableArcIteratorData<Arc> *) override;
 508
 509   using ImplToMutableFst<Impl, MutableFst<Arc>>::ReserveArcs;
 510   using ImplToMutableFst<Impl, MutableFst<Arc>>::ReserveStates;
 511
 512  private:
 513   using ImplToMutableFst<Impl, MutableFst<Arc>>::GetImpl;
 514   using ImplToMutableFst<Impl, MutableFst<Arc>>::MutateCheck;
 515   using ImplToMutableFst<Impl, MutableFst<Arc>>::SetImpl;
 516
 517   explicit VectorFst(std::shared_ptr<Impl> impl)
 518       : ImplToMutableFst<Impl>(impl) {}
 519 };
 520
 521 // Writes FST to file in Vector format, potentially with a pass over the machine
 522 // before writing to compute number of states.
 523 template <class Arc, class State>
 524 template <class FST>
 525 bool VectorFst<Arc, State>::WriteFst(const FST &fst, std::ostream &strm,
 526                                      const FstWriteOptions &opts) {
 527   static constexpr int file_version = 2;
 528   bool update_header = true;
 529   FstHeader hdr;
 530   hdr.SetStart(fst.Start());
 531   hdr.SetNumStates(kNoStateId);
 532   size_t start_offset = 0;
 533   if (fst.Properties(kExpanded, false) || opts.stream_write ||
 534       (start_offset = strm.tellp()) != -1) {
 535     hdr.SetNumStates(CountStates(fst));
 536     update_header = false;
 537   }
 538   const auto properties =
 539       fst.Properties(kCopyProperties, false) | Impl::kStaticProperties;
 540   internal::FstImpl<Arc>::WriteFstHeader(fst, strm, opts, file_version,
 541                                          "vector", properties, &hdr);
 542   StateId num_states = 0;
 543   for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
 544     const auto s = siter.Value();
 545     fst.Final(s).Write(strm);
 546     const int64 narcs = fst.NumArcs(s);
 547     WriteType(strm, narcs);
 548     for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
 549       const auto &arc = aiter.Value();
 550       WriteType(strm, arc.ilabel);
 551       WriteType(strm, arc.olabel);
 552       arc.weight.Write(strm);
 553       WriteType(strm, arc.nextstate);
 554     }
 555     ++num_states;
 556   }
 557   strm.flush();
 558   if (!strm) {
 559     LOG(ERROR) << "VectorFst::Write: Write failed: " << opts.source;
 560     return false;
 561   }
 562   if (update_header) {
 563     hdr.SetNumStates(num_states);
 564     return internal::FstImpl<Arc>::UpdateFstHeader(
 565         fst, strm, opts, file_version, "vector", properties, &hdr,
 566         start_offset);
 567   } else {
 568     if (num_states != hdr.NumStates()) {
 569       LOG(ERROR) << "Inconsistent number of states observed during write";
 570       return false;
 571     }
 572   }
 573   return true;
 574 }
 575
 576 // Specialization for VectorFst; see generic version in fst.h for sample usage
 577 // (but use the VectorFst type instead). This version should inline.
 578 template <class Arc, class State>
 579 class StateIterator<VectorFst<Arc, State>> {
 580  public:
 581   using StateId = typename Arc::StateId;
 582
 583   explicit StateIterator(const VectorFst<Arc, State> &fst)
 584       : nstates_(fst.GetImpl()->NumStates()), s_(0) {}
 585
 586   bool Done() const { return s_ >= nstates_; }
 587
 588   StateId Value() const { return s_; }
 589
 590   void Next() { ++s_; }
 591
 592   void Reset() { s_ = 0; }
 593
 594  private:
 595   const StateId nstates_;
 596   StateId s_;
 597 };
 598
 599 // Specialization for VectorFst; see generic version in fst.h for sample usage
 600 // (but use the VectorFst type instead). This version should inline.
 601 template <class Arc, class State>
 602 class ArcIterator<VectorFst<Arc, State>> {
 603  public:
 604   using StateId = typename Arc::StateId;
 605
 606   ArcIterator(const VectorFst<Arc, State> &fst, StateId s)
 607       : arcs_(fst.GetImpl()->GetState(s)->Arcs()),
 608         narcs_(fst.GetImpl()->GetState(s)->NumArcs()),
 609         i_(0) {}
 610
 611   bool Done() const { return i_ >= narcs_; }
 612
 613   const Arc &Value() const { return arcs_[i_]; }
 614
 615   void Next() { ++i_; }
 616
 617   void Reset() { i_ = 0; }
 618
 619   void Seek(size_t a) { i_ = a; }
 620
 621   size_t Position() const { return i_; }
 622
 623   constexpr uint32 Flags() const { return kArcValueFlags; }
 624
 625   void SetFlags(uint32, uint32) {}
 626
 627  private:
 628   const Arc *arcs_;
 629   size_t narcs_;
 630   size_t i_;
 631 };
 632
 633 // Specialization for VectorFst; see generic version in mutable-fst.h for sample
 634 // usage (but use the VectorFst type instead). This version should inline.
 635 template <class Arc, class State>
 636 class MutableArcIterator<VectorFst<Arc, State>>
 637     : public MutableArcIteratorBase<Arc> {
 638  public:
 639   using StateId = typename Arc::StateId;
 640   using Weight = typename Arc::Weight;
 641
 642   MutableArcIterator(VectorFst<Arc, State> *fst, StateId s) : i_(0) {
 643     fst->MutateCheck();
 644     state_ = fst->GetMutableImpl()->GetState(s);
 645     properties_ = &fst->GetImpl()->properties_;
 646   }
 647
 648   bool Done() const final { return i_ >= state_->NumArcs(); }
 649
 650   const Arc &Value() const final { return state_->GetArc(i_); }
 651
 652   void Next() final { ++i_; }
 653
 654   size_t Position() const final { return i_; }
 655
 656   void Reset() final { i_ = 0; }
 657
 658   void Seek(size_t a) final { i_ = a; }
 659
 660   void SetValue(const Arc &arc) final {
 661     const auto &oarc = state_->GetArc(i_);
 662     if (oarc.ilabel != oarc.olabel) *properties_ &= ~kNotAcceptor;
 663     if (oarc.ilabel == 0) {
 664       *properties_ &= ~kIEpsilons;
 665       if (oarc.olabel == 0) *properties_ &= ~kEpsilons;
 666     }
 667     if (oarc.olabel == 0) *properties_ &= ~kOEpsilons;
 668     if (oarc.weight != Weight::Zero() && oarc.weight != Weight::One()) {
 669       *properties_ &= ~kWeighted;
 670     }
 671     state_->SetArc(arc, i_);
 672     if (arc.ilabel != arc.olabel) {
 673       *properties_ |= kNotAcceptor;
 674       *properties_ &= ~kAcceptor;
 675     }
 676     if (arc.ilabel == 0) {
 677       *properties_ |= kIEpsilons;
 678       *properties_ &= ~kNoIEpsilons;
 679       if (arc.olabel == 0) {
 680         *properties_ |= kEpsilons;
 681         *properties_ &= ~kNoEpsilons;
 682       }
 683     }
 684     if (arc.olabel == 0) {
 685       *properties_ |= kOEpsilons;
 686       *properties_ &= ~kNoOEpsilons;
 687     }
 688     if (arc.weight != Weight::Zero() && arc.weight != Weight::One()) {
 689       *properties_ |= kWeighted;
 690       *properties_ &= ~kUnweighted;
 691     }
 692     *properties_ &= kSetArcProperties | kAcceptor | kNotAcceptor | kEpsilons |
 693                     kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
 694                     kNoOEpsilons | kWeighted | kUnweighted;
 695   }
 696
 697   uint32 Flags() const final { return kArcValueFlags; }
 698
 699   void SetFlags(uint32, uint32) final {}
 700
 701  private:
 702   State *state_;
 703   uint64 *properties_;
 704   size_t i_;
 705 };
 706
 707 // Provides information needed for the generic mutable arc iterator.
 708 template <class Arc, class State>
 709 inline void VectorFst<Arc, State>::InitMutableArcIterator(
 710     StateId s, MutableArcIteratorData<Arc> *data) {
 711   data->base = new MutableArcIterator<VectorFst<Arc, State>>(this, s);
 712 }
 713
 714 // A useful alias when using StdArc.
 715 using StdVectorFst = VectorFst<StdArc>;
 716
 717 }  // namespace fst
 718
 719 #endif  // FST_VECTOR_FST_H_