1// visit.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// Copyright 2005-2010 Google, Inc.
16// Author: riley@google.com (Michael Riley)
17//
18// \file
19// Queue-dependent visitation of finite-state transducers. See also
20// dfs-visit.h.
21
22#ifndef FST_LIB_VISIT_H__
23#define FST_LIB_VISIT_H__
24
25
26#include <fst/arcfilter.h>
27#include <fst/mutable-fst.h>
28
29
30namespace fst {
31
32// Visitor Interface - class determines actions taken during a visit.
33// If any of the boolean member functions return false, the visit is
34// aborted by first calling FinishState() on all unfinished (grey)
35// states and then calling FinishVisit().
36//
37// Note this is more general than the visitor interface in
38// dfs-visit.h but lacks some DFS-specific behavior.
39//
40// template <class Arc>
41// class Visitor {
42//  public:
43//   typedef typename Arc::StateId StateId;
44//
45//   Visitor(T *return_data);
46//   // Invoked before visit
47//   void InitVisit(const Fst<Arc> &fst);
48//   // Invoked when state discovered (2nd arg is visitation root)
49//   bool InitState(StateId s, StateId root);
50//   // Invoked when arc to white/undiscovered state examined
51//   bool WhiteArc(StateId s, const Arc &a);
52//   // Invoked when arc to grey/unfinished state examined
53//   bool GreyArc(StateId s, const Arc &a);
54//   // Invoked when arc to black/finished state examined
55//   bool BlackArc(StateId s, const Arc &a);
56//   // Invoked when state finished.
57//   void FinishState(StateId s);
58//   // Invoked after visit
59//   void FinishVisit();
60// };
61
62// Performs queue-dependent visitation. Visitor class argument
63// determines actions and contains any return data. ArcFilter
64// determines arcs that are considered.
65//
66// Note this is more general than DfsVisit() in dfs-visit.h but lacks
67// some DFS-specific Visitor behavior.
68template <class Arc, class V, class Q, class ArcFilter>
69void Visit(const Fst<Arc> &fst, V *visitor, Q *queue, ArcFilter filter) {
70
71  typedef typename Arc::StateId StateId;
72  typedef ArcIterator< Fst<Arc> > AIterator;
73
74  visitor->InitVisit(fst);
75
76  StateId start = fst.Start();
77  if (start == kNoStateId) {
78    visitor->FinishVisit();
79    return;
80  }
81
82  // An Fst state's visit color
83  const unsigned kWhiteState =  0x01;    // Undiscovered
84  const unsigned kGreyState =   0x02;    // Discovered & unfinished
85  const unsigned kBlackState =  0x04;    // Finished
86
87  // We destroy an iterator as soon as possible and mark it so
88  const unsigned kArcIterDone = 0x08;      // Arc iterator done and destroyed
89
90  vector<unsigned char> state_status;
91  vector<AIterator *> arc_iterator;
92
93  StateId nstates = start + 1;             // # of known states in general case
94  bool expanded = false;
95  if (fst.Properties(kExpanded, false)) {  // tests if expanded case, then
96    nstates = CountStates(fst);            // uses ExpandedFst::NumStates().
97    expanded = true;
98  }
99
100  state_status.resize(nstates, kWhiteState);
101  arc_iterator.resize(nstates);
102  StateIterator< Fst<Arc> > siter(fst);
103
104  // Continues visit while true
105  bool visit = true;
106
107  // Iterates over trees in visit forest.
108  for (StateId root = start; visit && root < nstates;) {
109    visit = visitor->InitState(root, root);
110    state_status[root] = kGreyState;
111    queue->Enqueue(root);
112    while (!queue->Empty()) {
113      StateId s = queue->Head();
114      if (s >= state_status.size()) {
115        nstates = s + 1;
116        state_status.resize(nstates, kWhiteState);
117        arc_iterator.resize(nstates);
118      }
119      // Creates arc iterator if needed.
120      if (arc_iterator[s] == 0 && !(state_status[s] & kArcIterDone) && visit)
121        arc_iterator[s] = new AIterator(fst, s);
122      // Deletes arc iterator if done.
123      AIterator *aiter = arc_iterator[s];
124      if ((aiter && aiter->Done()) || !visit) {
125        delete aiter;
126        arc_iterator[s] = 0;
127        state_status[s] |= kArcIterDone;
128      }
129      // Dequeues state and marks black if done
130      if (state_status[s] & kArcIterDone) {
131        queue->Dequeue();
132        visitor->FinishState(s);
133        state_status[s] = kBlackState;
134        continue;
135      }
136
137      const Arc &arc = aiter->Value();
138      if (arc.nextstate >= state_status.size()) {
139        nstates = arc.nextstate + 1;
140        state_status.resize(nstates, kWhiteState);
141        arc_iterator.resize(nstates);
142      }
143      // Visits respective arc types
144      if (filter(arc)) {
145        // Enqueues destination state and marks grey if white
146        if (state_status[arc.nextstate] == kWhiteState) {
147          visit = visitor->WhiteArc(s, arc);
148          if (!visit) continue;
149          visit = visitor->InitState(arc.nextstate, root);
150          state_status[arc.nextstate] = kGreyState;
151          queue->Enqueue(arc.nextstate);
152        } else if (state_status[arc.nextstate] == kBlackState) {
153          visit = visitor->BlackArc(s, arc);
154        } else {
155          visit = visitor->GreyArc(s, arc);
156        }
157      }
158      aiter->Next();
159      // Destroys an iterator ASAP for efficiency.
160      if (aiter->Done()) {
161        delete aiter;
162        arc_iterator[s] = 0;
163        state_status[s] |= kArcIterDone;
164      }
165    }
166    // Finds next tree root
167    for (root = root == start ? 0 : root + 1;
168         root < nstates && state_status[root] != kWhiteState;
169         ++root);
170
171    // Check for a state beyond the largest known state
172    if (!expanded && root == nstates) {
173      for (; !siter.Done(); siter.Next()) {
174        if (siter.Value() == nstates) {
175          ++nstates;
176          state_status.push_back(kWhiteState);
177          arc_iterator.push_back(0);
178          break;
179        }
180      }
181    }
182  }
183  visitor->FinishVisit();
184}
185
186
187template <class Arc, class V, class Q>
188inline void Visit(const Fst<Arc> &fst, V *visitor, Q* queue) {
189  Visit(fst, visitor, queue, AnyArcFilter<Arc>());
190}
191
192// Copies input FST to mutable FST following queue order.
193template <class A>
194class CopyVisitor {
195 public:
196  typedef A Arc;
197  typedef typename A::StateId StateId;
198
199  CopyVisitor(MutableFst<Arc> *ofst) : ifst_(0), ofst_(ofst) {}
200
201  void InitVisit(const Fst<A> &ifst) {
202    ifst_ = &ifst;
203    ofst_->DeleteStates();
204    ofst_->SetStart(ifst_->Start());
205  }
206
207  bool InitState(StateId s, StateId) {
208    while (ofst_->NumStates() <= s)
209      ofst_->AddState();
210    return true;
211  }
212
213  bool WhiteArc(StateId s, const Arc &arc) {
214    ofst_->AddArc(s, arc);
215    return true;
216  }
217
218  bool GreyArc(StateId s, const Arc &arc) {
219    ofst_->AddArc(s, arc);
220    return true;
221  }
222
223  bool BlackArc(StateId s, const Arc &arc) {
224    ofst_->AddArc(s, arc);
225    return true;
226  }
227
228  void FinishState(StateId s) {
229    ofst_->SetFinal(s, ifst_->Final(s));
230  }
231
232  void FinishVisit() {}
233
234 private:
235  const Fst<Arc> *ifst_;
236  MutableFst<Arc> *ofst_;
237};
238
239
240// Visits input FST up to a state limit following queue order.
241template <class A>
242class PartialVisitor {
243 public:
244  typedef A Arc;
245  typedef typename A::StateId StateId;
246
247  explicit PartialVisitor(StateId maxvisit) : maxvisit_(maxvisit) {}
248
249  void InitVisit(const Fst<A> &ifst) { nvisit_ = 0; }
250
251  bool InitState(StateId s, StateId) {
252    ++nvisit_;
253    return nvisit_ <= maxvisit_;
254  }
255
256  bool WhiteArc(StateId s, const Arc &arc) { return true; }
257  bool GreyArc(StateId s, const Arc &arc) { return true; }
258  bool BlackArc(StateId s, const Arc &arc) { return true; }
259  void FinishState(StateId s) {}
260  void FinishVisit() {}
261
262 private:
263  StateId maxvisit_;
264  StateId nvisit_;
265};
266
267
268}  // namespace fst
269
270#endif  // FST_LIB_VISIT_H__
271