76 template <
class FST,
class Visitor,
class Queue,
class ArcFilter>
77 void Visit(
const FST &
fst, Visitor *visitor, Queue *queue, ArcFilter filter,
78 bool access_only =
false) {
79 using Arc =
typename FST::Arc;
80 using StateId =
typename Arc::StateId;
81 visitor->InitVisit(fst);
82 const auto start = fst.Start();
84 visitor->FinishVisit();
88 static constexpr uint8_t kWhiteState = 0x01;
89 static constexpr uint8_t kGreyState = 0x02;
90 static constexpr uint8_t kBlackState = 0x04;
92 static constexpr uint8_t kArcIterDone = 0x08;
93 std::vector<uint8_t> state_status;
94 std::vector<ArcIterator<FST> *> arc_iterator;
97 StateId nstates = fst.NumStatesIfKnown().value_or(start + 1);
98 const bool expanded = fst.Properties(
kExpanded,
false);
99 state_status.resize(nstates, kWhiteState);
100 arc_iterator.resize(nstates);
105 for (
auto root = start; visit && root < nstates;) {
106 visit = visitor->InitState(root, root);
107 state_status[root] = kGreyState;
108 queue->Enqueue(root);
109 while (!queue->Empty()) {
110 auto state = queue->Head();
111 if (state >= state_status.size()) {
113 state_status.resize(nstates, kWhiteState);
114 arc_iterator.resize(nstates);
117 if (!arc_iterator[state] && !(state_status[state] & kArcIterDone) &&
122 auto *aiter = arc_iterator[state];
123 if ((aiter && aiter->Done()) || !visit) {
125 arc_iterator[state] =
nullptr;
126 state_status[state] |= kArcIterDone;
129 if (state_status[state] & kArcIterDone) {
131 visitor->FinishState(state);
132 state_status[state] = kBlackState;
135 const auto &arc = aiter->Value();
136 if (arc.nextstate >= state_status.size()) {
137 nstates = arc.nextstate + 1;
138 state_status.resize(nstates, kWhiteState);
139 arc_iterator.resize(nstates);
144 if (state_status[arc.nextstate] == kWhiteState) {
145 visit = visitor->WhiteArc(state, arc);
146 if (!visit)
continue;
147 visit = visitor->InitState(arc.nextstate, root);
148 state_status[arc.nextstate] = kGreyState;
149 queue->Enqueue(arc.nextstate);
150 }
else if (state_status[arc.nextstate] == kBlackState) {
151 visit = visitor->BlackArc(state, arc);
153 visit = visitor->GreyArc(state, arc);
160 arc_iterator[state] =
nullptr;
161 state_status[state] |= kArcIterDone;
164 if (access_only)
break;
166 for (root = (root == start) ? 0 : root + 1;
167 root < nstates && state_status[root] != kWhiteState; ++root) {
170 if (!expanded && root == nstates) {
171 for (; !siter.
Done(); siter.
Next()) {
172 if (siter.
Value() == nstates) {
174 state_status.push_back(kWhiteState);
175 arc_iterator.push_back(
nullptr);
181 visitor->FinishVisit();
184 template <
class Arc,
class Visitor,
class Queue>
210 ofst_->
AddArc(state, arc);
215 ofst_->
AddArc(state, arc);
220 ofst_->
AddArc(state, arc);
243 : fst_(nullptr), maxvisit_(maxvisit) {}
253 return ninit_ <= maxvisit_;
290 bool copy_grey =
true,
bool copy_black =
true)
293 copy_grey_(copy_grey),
294 copy_black_(copy_black) {}
305 return ninit_ <= maxvisit_;
333 const bool copy_grey_;
334 const bool copy_black_;
339 #endif // FST_VISIT_H_ bool WhiteArc(StateId state, const Arc &arc)
bool BlackArc(StateId state, const Arc &arc)
bool GreyArc(StateId state, const Arc &arc)
bool WhiteArc(StateId state, const Arc &arc)
void FinishState(StateId state)
CopyVisitor(MutableFst< Arc > *ofst)
void Visit(const FST &fst, Visitor *visitor, Queue *queue, ArcFilter filter, bool access_only=false)
typename Arc::StateId StateId
bool BlackArc(StateId state, const Arc &arc)
void InitVisit(const Fst< A > &ifst)
void FinishState(StateId state)
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
bool GreyArc(StateId state, const Arc &arc)
bool BlackArc(StateId state, const Arc &arc)
typename Arc::StateId StateId
PartialCopyVisitor(MutableFst< Arc > *ofst, StateId maxvisit, bool copy_grey=true, bool copy_black=true)
PartialVisitor(StateId maxvisit)
virtual StateId Start() const =0
bool InitState(StateId state, StateId root)
void InitVisit(const Fst< A > &ifst)
bool GreyArc(StateId state, const Arc &arc)
virtual void AddArc(StateId, const Arc &)=0
void FinishState(StateId state)
virtual StateId AddState()=0
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
virtual void DeleteStates(const std::vector< StateId > &)=0
virtual StateId NumStates() const =0
constexpr uint64_t kExpanded
bool InitState(StateId state, StateId root)
bool InitState(StateId state, StateId)
void Destroy(ArcIterator< FST > *aiter, MemoryPool< ArcIterator< FST >> *pool)
void InitVisit(const Fst< A > &ifst)