14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// dfs-visit.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Depth-first search visitation 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_DFS_VISIT_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_DFS_VISIT_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <stack> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcfilter.h" 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/expanded-fst.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Visitor Interface - class determines actions taken during a Dfs. 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// If any of the boolean member functions return false, the DFS is 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// aborted by first calling FinishState() on all currently grey states 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and then calling FinishVisit(). 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// template <class Arc> 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// class Visitor { 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// public: 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// typedef typename Arc::StateId StateId; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Visitor(T *return_data); 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked before DFS visit 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void InitVisit(const Fst<Arc> &fst); 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked when state discovered (2nd arg is DFS tree root) 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bool InitState(StateId s, StateId root); 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked when tree arc examined (to white/undiscovered state) 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bool TreeArc(StateId s, const Arc &a); 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked when back arc examined (to grey/unfinished state) 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bool BackArc(StateId s, const Arc &a); 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked when forward or cross arc examined (to black/finished state) 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bool ForwardOrCrossArc(StateId s, const Arc &a); 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked when state finished (PARENT is kNoStateID and ARC == NULL 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // when S is tree root) 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void FinishState(StateId s, StateId parent, const Arc *parent_arc); 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Invoked after DFS visit 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void FinishVisit(); 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// }; 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// An Fst state's DFS status 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst int kDfsWhite = 0; // Undiscovered 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst int kDfsGrey = 1; // Discovered & unfinished 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectconst int kDfsBlack = 2; // Finished 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// An Fst state's DFS stack state 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc> 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstruct DfsState { 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsState(const Fst<Arc> &fst, StateId s): state_id(s), arc_iter(fst, s) {} 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state_id; // Fst state ... 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator< Fst<Arc> > arc_iter; // and its corresponding arcs 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Performs depth-first visitation. Visitor class argument determines actions 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and contains any return data. ArcFilter determines arcs that are considered. 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class V, class ArcFilter> 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid DfsVisit(const Fst<Arc> &fst, V *visitor, ArcFilter filter) { 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::StateId StateId; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visitor->InitVisit(fst); 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId start = fst.Start(); 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (start == kNoStateId) { 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visitor->FinishVisit(); 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<char> state_color; // Fst state DFS status 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project stack<DfsState<Arc> *> state_stack; // DFS execution stack 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nstates = CountStates(fst); 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)state_color.size() < nstates) 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_color.push_back(kDfsWhite); 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Continue DFS while true 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool dfs = true; 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Iterate over trees in DFS forest. 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId root = start; dfs && root < nstates;) { 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_color[root] = kDfsGrey; 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_stack.push(new DfsState<Arc>(fst, root)); 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfs = visitor->InitState(root, root); 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (!state_stack.empty()) { 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsState<Arc> *dfs_state = state_stack.top(); 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = dfs_state->state_id; 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator< Fst<Arc> > &aiter = dfs_state->arc_iter; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!dfs || aiter.Done()) { 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_color[s] = kDfsBlack; 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete dfs_state; 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_stack.pop(); 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!state_stack.empty()) { 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsState<Arc> *parent_state = state_stack.top(); 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId p = parent_state->state_id; 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcIterator< Fst<Arc> > &piter = parent_state->arc_iter; 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visitor->FinishState(s, p, &piter.Value()); 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project piter.Next(); 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visitor->FinishState(s, kNoStateId, 0); 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = aiter.Value(); 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!filter(arc)) { 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next(); 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project continue; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int next_color = state_color[arc.nextstate]; 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project switch (next_color) { 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project default: 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case kDfsWhite: 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfs = visitor->TreeArc(s, arc); 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!dfs) break; 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_color[arc.nextstate] = kDfsGrey; 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_stack.push(new DfsState<Arc>(fst, arc.nextstate)); 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfs = visitor->InitState(arc.nextstate, root); 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case kDfsGrey: 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfs = visitor->BackArc(s, arc); 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next(); 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case kDfsBlack: 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project dfs = visitor->ForwardOrCrossArc(s, arc); 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project aiter.Next(); 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Find next tree root 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (root = root == start ? 0 : root + 1; 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project root < nstates && state_color[root] != kDfsWhite; 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++root); 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project visitor->FinishVisit(); 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class Arc, class V> 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid DfsVisit(const Fst<Arc> &fst, V *visitor) { 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(fst, visitor, AnyArcFilter<Arc>()); 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_DFS_VISIT_H__ 165