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
29namespace fst {
30
31template <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.
35template <class State>
36class 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.
159template <class A>
160struct 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.
175template <class A>
176class 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
321template <class A>
322VectorFstImpl<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
349template <class A>
350VectorFstImpl<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    uint64 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.
391template <class W> class WeightFromString {
392 public:
393  W operator()(const string &s);
394};
395
396// Generic case fails.
397template <class W> inline
398W WeightFromString<W>::operator()(const string &s) {
399  LOG(FATAL) << "VectorFst::Read: Obsolete file format";
400  return W();
401}
402
403// TropicalWeight version.
404template <> inline
405TropicalWeight 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.
412template <> inline
413LogWeight WeightFromString<LogWeight>::operator()(const string &s) {
414  float f;
415  memcpy(&f, s.data(), sizeof(f));
416  return LogWeight(f);
417}
418
419template <class A>
420bool 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    size_t 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 false;
446  }
447  return true;
448}
449
450// Simple concrete, mutable FST. Supports additional operations:
451// ReserveStates and ReserveArcs (cf. STL vectors). This class
452// attaches interface to implementation and handles reference
453// counting.
454template <class A>
455class VectorFst : public MutableFst<A> {
456 public:
457  friend class StateIterator< VectorFst<A> >;
458  friend class ArcIterator< VectorFst<A> >;
459  friend class MutableArcIterator< VectorFst<A> >;
460
461  typedef A Arc;
462  typedef typename A::Weight Weight;
463  typedef typename A::StateId StateId;
464
465  VectorFst() : impl_(new VectorFstImpl<A>) {}
466
467  VectorFst(const VectorFst<A> &fst) : MutableFst<A>(fst), impl_(fst.impl_) {
468    impl_->IncrRefCount();
469  }
470  explicit VectorFst(const Fst<A> &fst) : impl_(new VectorFstImpl<A>(fst)) {}
471
472  virtual ~VectorFst() { if (!impl_->DecrRefCount()) delete impl_; }
473
474  VectorFst<A> &operator=(const VectorFst<A> &fst) {
475    if (this != &fst) {
476      if (!impl_->DecrRefCount()) delete impl_;
477      fst.impl_->IncrRefCount();
478      impl_ = fst.impl_;
479    }
480    return *this;
481  }
482
483  virtual VectorFst<A> &operator=(const Fst<A> &fst) {
484    if (this != &fst) {
485      if (!impl_->DecrRefCount()) delete impl_;
486      impl_ = new VectorFstImpl<A>(fst);
487    }
488    return *this;
489  }
490
491  virtual StateId Start() const { return impl_->Start(); }
492
493  virtual Weight Final(StateId s) const { return impl_->Final(s); }
494
495  virtual StateId NumStates() const { return impl_->NumStates(); }
496
497  virtual size_t NumArcs(StateId s) const { return impl_->NumArcs(s); }
498
499  virtual size_t NumInputEpsilons(StateId s) const {
500    return impl_->NumInputEpsilons(s);
501  }
502
503  virtual size_t NumOutputEpsilons(StateId s) const {
504    return impl_->NumOutputEpsilons(s);
505  }
506
507  virtual uint64 Properties(uint64 mask, bool test) const {
508    if (test) {
509      uint64 known, test = TestProperties(*this, mask, &known);
510      impl_->SetProperties(test, known);
511      return test & mask;
512    } else {
513      return impl_->Properties(mask);
514    }
515  }
516
517  virtual const string& Type() const { return impl_->Type(); }
518
519  // Get a copy of this VectorFst
520  virtual VectorFst<A> *Copy() const {
521    impl_->IncrRefCount();
522    return new VectorFst<A>(impl_);
523  }
524
525  // Read a VectorFst from an input stream; return NULL on error
526  static VectorFst<A> *Read(istream &strm, const FstReadOptions &opts) {
527    VectorFstImpl<A>* impl = VectorFstImpl<A>::Read(strm, opts);
528    return impl ? new VectorFst<A>(impl) : 0;
529  }
530
531  // Read a VectorFst from a file; return NULL on error
532  static VectorFst<A> *Read(const string &filename) {
533    ifstream strm(filename.c_str());
534    if (!strm) {
535      LOG(ERROR) << "VectorFst::Read: Can't open file: " << filename;
536      return 0;
537    }
538    return Read(strm, FstReadOptions(filename));
539  }
540
541  // Write a VectorFst to an output stream; return false on error
542  virtual bool Write(ostream &strm, const FstWriteOptions &opts) const {
543    return impl_->Write(strm, opts);
544  }
545
546  // Write a VectorFst to a file; return false on error
547  virtual bool Write(const string &filename) const {
548    if (!filename.empty()) {
549      ofstream strm(filename.c_str());
550      if (!strm) {
551        LOG(ERROR) << "VectorFst::Write: Can't open file: " << filename;
552        return false;
553      }
554      return Write(strm, FstWriteOptions(filename));
555    } else {
556      return Write(std::cout, FstWriteOptions("standard output"));
557    }
558  }
559
560  virtual SymbolTable* InputSymbols() {
561    return impl_->InputSymbols();
562  }
563
564  virtual SymbolTable* OutputSymbols() {
565    return impl_->OutputSymbols();
566  }
567
568  virtual const SymbolTable* InputSymbols() const {
569    return impl_->InputSymbols();
570  }
571
572  virtual const SymbolTable* OutputSymbols() const {
573    return impl_->OutputSymbols();
574  }
575
576  virtual void SetStart(StateId s) {
577    MutateCheck();
578    impl_->SetStart(s);
579  }
580
581  virtual void SetFinal(StateId s, Weight w) {
582    MutateCheck();
583    impl_->SetFinal(s, w);
584  }
585
586  virtual void SetProperties(uint64 props, uint64 mask) {
587    impl_->SetProperties(props, mask);
588  }
589
590  virtual StateId AddState() {
591    MutateCheck();
592    return impl_->AddState();
593  }
594
595  virtual void AddArc(StateId s, const A &arc) {
596    MutateCheck();
597    impl_->AddArc(s, arc);
598  }
599
600  virtual void DeleteStates(const vector<StateId> &dstates) {
601    MutateCheck();
602    impl_->DeleteStates(dstates);
603  }
604
605  virtual void DeleteStates() {
606    MutateCheck();
607    impl_->DeleteStates();
608  }
609
610  virtual void DeleteArcs(StateId s, size_t n) {
611    MutateCheck();
612    impl_->DeleteArcs(s, n);
613  }
614
615  virtual void DeleteArcs(StateId s) {
616    MutateCheck();
617    impl_->DeleteArcs(s);
618  }
619
620  virtual void SetInputSymbols(const SymbolTable* isyms) {
621    MutateCheck();
622    impl_->SetInputSymbols(isyms);
623  }
624
625  virtual void SetOutputSymbols(const SymbolTable* osyms) {
626    MutateCheck();
627    impl_->SetOutputSymbols(osyms);
628  }
629
630  void ReserveStates(StateId n) {
631    MutateCheck();
632    impl_->ReserveStates(n);
633  }
634
635  void ReserveArcs(StateId s, size_t n) {
636    MutateCheck();
637    impl_->ReserveArcs(s, n);
638  }
639
640  virtual void InitStateIterator(StateIteratorData<A> *data) const {
641    impl_->InitStateIterator(data);
642  }
643
644  virtual void InitArcIterator(StateId s, ArcIteratorData<A> *data) const {
645    impl_->InitArcIterator(s, data);
646  }
647
648  virtual inline
649  void InitMutableArcIterator(StateId s, MutableArcIteratorData<A> *);
650
651 private:
652  explicit VectorFst(VectorFstImpl<A> *impl) : impl_(impl) {}
653
654  void MutateCheck() {
655    // Copy on write
656    if (impl_->RefCount() > 1) {
657      impl_->DecrRefCount();
658      impl_ = new VectorFstImpl<A>(*this);
659    }
660  }
661
662  VectorFstImpl<A> *impl_;  // FST's impl
663};
664
665// Specialization for VectorFst; see generic version in fst.h
666// for sample usage (but use the VectorFst type!). This version
667// should inline.
668template <class A>
669class StateIterator< VectorFst<A> > {
670 public:
671  typedef typename A::StateId StateId;
672
673  explicit StateIterator(const VectorFst<A> &fst)
674    : nstates_(fst.impl_->NumStates()), s_(0) {}
675
676  bool Done() const { return s_ >= nstates_; }
677
678  StateId Value() const { return s_; }
679
680  void Next() { ++s_; }
681
682  void Reset() { s_ = 0; }
683
684 private:
685  StateId nstates_;
686  StateId s_;
687
688  DISALLOW_EVIL_CONSTRUCTORS(StateIterator);
689};
690
691// Specialization for VectorFst; see generic version in fst.h
692// for sample usage (but use the VectorFst type!). This version
693// should inline.
694template <class A>
695class ArcIterator< VectorFst<A> > {
696 public:
697  typedef typename A::StateId StateId;
698
699  ArcIterator(const VectorFst<A> &fst, StateId s)
700    : arcs_(fst.impl_->GetState(s)->arcs), i_(0) {}
701
702  bool Done() const { return i_ >= arcs_.size(); }
703
704  const A& Value() const { return arcs_[i_]; }
705
706  void Next() { ++i_; }
707
708  void Reset() { i_ = 0; }
709
710  void Seek(size_t a) { i_ = a; }
711
712 private:
713  const vector<A>& arcs_;
714  size_t i_;
715
716  DISALLOW_EVIL_CONSTRUCTORS(ArcIterator);
717};
718
719// Specialization for VectorFst; see generic version in fst.h
720// for sample usage (but use the VectorFst type!). This version
721// should inline.
722template <class A>
723class MutableArcIterator< VectorFst<A> >
724  : public MutableArcIteratorBase<A> {
725 public:
726  typedef typename A::StateId StateId;
727  typedef typename A::Weight Weight;
728
729  MutableArcIterator(VectorFst<A> *fst, StateId s) : i_(0) {
730    fst->MutateCheck();
731    state_ = fst->impl_->GetState(s);
732    properties_ = &fst->impl_->properties_;
733  }
734
735  virtual bool Done() const { return i_ >= state_->arcs.size(); }
736
737  virtual const A& Value() const { return state_->arcs[i_]; }
738
739  virtual void Next() { ++i_; }
740
741  virtual void Reset() { i_ = 0; }
742
743  virtual void Seek(size_t a) { i_ = a; }
744
745  virtual void SetValue(const A &arc) {
746    A& oarc = state_->arcs[i_];
747    if (oarc.ilabel != oarc.olabel)
748      *properties_ &= ~kNotAcceptor;
749    if (oarc.ilabel == 0) {
750      --state_->niepsilons;
751      *properties_ &= ~kIEpsilons;
752      if (oarc.olabel == 0)
753        *properties_ &= ~kEpsilons;
754    }
755    if (oarc.olabel == 0) {
756      --state_->noepsilons;
757      *properties_ &= ~kOEpsilons;
758    }
759    if (oarc.weight != Weight::Zero() && oarc.weight != Weight::One())
760      *properties_ &= ~kWeighted;
761    oarc = arc;
762    if (arc.ilabel != arc.olabel)
763      *properties_ |= kNotAcceptor;
764    if (arc.ilabel == 0) {
765      ++state_->niepsilons;
766      *properties_ |= kIEpsilons;
767      if (arc.olabel == 0)
768        *properties_ |= kEpsilons;
769    }
770    if (arc.olabel == 0) {
771      ++state_->noepsilons;
772      *properties_ |= kOEpsilons;
773    }
774    if (arc.weight != Weight::Zero() && arc.weight != Weight::One())
775      *properties_ |= kWeighted;
776    *properties_ &= kSetArcProperties | kNotAcceptor |
777                    kEpsilons | kIEpsilons | kOEpsilons | kWeighted;
778  }
779
780 private:
781  struct VectorState<A> *state_;
782  uint64 *properties_;
783  size_t i_;
784
785  DISALLOW_EVIL_CONSTRUCTORS(MutableArcIterator);
786};
787
788// Provide information needed for the generic mutable arc iterator
789template <class A> inline
790void VectorFst<A>::InitMutableArcIterator(
791    StateId s, MutableArcIteratorData<A> *data) {
792  data->base = new MutableArcIterator< VectorFst<A> >(this, s);
793}
794
795// A useful alias when using StdArc.
796typedef VectorFst<StdArc> StdVectorFst;
797
798}  // namespace fst
799
800#endif  // FST_LIB_VECTOR_FST_H__
801