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