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