summaryrefslogtreecommitdiff
path: root/kaldi_io/src/tools/openfst/include/fst/visit.h
diff options
context:
space:
mode:
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/visit.h')
-rw-r--r--kaldi_io/src/tools/openfst/include/fst/visit.h284
1 files changed, 0 insertions, 284 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/visit.h b/kaldi_io/src/tools/openfst/include/fst/visit.h
deleted file mode 100644
index 5f5059a..0000000
--- a/kaldi_io/src/tools/openfst/include/fst/visit.h
+++ /dev/null
@@ -1,284 +0,0 @@
-// visit.h
-
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-// Copyright 2005-2010 Google, Inc.
-// Author: [email protected] (Michael Riley)
-//
-// \file
-// Queue-dependent visitation of finite-state transducers. See also
-// dfs-visit.h.
-
-#ifndef FST_LIB_VISIT_H__
-#define FST_LIB_VISIT_H__
-
-
-#include <fst/arcfilter.h>
-#include <fst/mutable-fst.h>
-
-
-namespace fst {
-
-// Visitor Interface - class determines actions taken during a visit.
-// If any of the boolean member functions return false, the visit is
-// aborted by first calling FinishState() on all unfinished (grey)
-// states and then calling FinishVisit().
-//
-// Note this is more general than the visitor interface in
-// dfs-visit.h but lacks some DFS-specific behavior.
-//
-// template <class Arc>
-// class Visitor {
-// public:
-// typedef typename Arc::StateId StateId;
-//
-// Visitor(T *return_data);
-// // Invoked before visit
-// void InitVisit(const Fst<Arc> &fst);
-// // Invoked when state discovered (2nd arg is visitation root)
-// bool InitState(StateId s, StateId root);
-// // Invoked when arc to white/undiscovered state examined
-// bool WhiteArc(StateId s, const Arc &a);
-// // Invoked when arc to grey/unfinished state examined
-// bool GreyArc(StateId s, const Arc &a);
-// // Invoked when arc to black/finished state examined
-// bool BlackArc(StateId s, const Arc &a);
-// // Invoked when state finished.
-// void FinishState(StateId s);
-// // Invoked after visit
-// void FinishVisit();
-// };
-
-// Performs queue-dependent visitation. Visitor class argument
-// determines actions and contains any return data. ArcFilter
-// determines arcs that are considered.
-//
-// Note this is more general than DfsVisit() in dfs-visit.h but lacks
-// some DFS-specific Visitor behavior.
-template <class Arc, class V, class Q, class ArcFilter>
-void Visit(const Fst<Arc> &fst, V *visitor, Q *queue, ArcFilter filter) {
-
- typedef typename Arc::StateId StateId;
- typedef ArcIterator< Fst<Arc> > AIterator;
-
- visitor->InitVisit(fst);
-
- StateId start = fst.Start();
- if (start == kNoStateId) {
- visitor->FinishVisit();
- return;
- }
-
- // An Fst state's visit color
- const unsigned kWhiteState = 0x01; // Undiscovered
- const unsigned kGreyState = 0x02; // Discovered & unfinished
- const unsigned kBlackState = 0x04; // Finished
-
- // We destroy an iterator as soon as possible and mark it so
- const unsigned kArcIterDone = 0x08; // Arc iterator done and destroyed
-
- vector<unsigned char> state_status;
- vector<AIterator *> arc_iterator;
-
- StateId nstates = start + 1; // # of known states in general case
- bool expanded = false;
- if (fst.Properties(kExpanded, false)) { // tests if expanded case, then
- nstates = CountStates(fst); // uses ExpandedFst::NumStates().
- expanded = true;
- }
-
- state_status.resize(nstates, kWhiteState);
- arc_iterator.resize(nstates);
- StateIterator< Fst<Arc> > siter(fst);
-
- // Continues visit while true
- bool visit = true;
-
- // Iterates over trees in visit forest.
- for (StateId root = start; visit && root < nstates;) {
- visit = visitor->InitState(root, root);
- state_status[root] = kGreyState;
- queue->Enqueue(root);
- while (!queue->Empty()) {
- StateId s = queue->Head();
- if (s >= state_status.size()) {
- nstates = s + 1;
- state_status.resize(nstates, kWhiteState);
- arc_iterator.resize(nstates);
- }
- // Creates arc iterator if needed.
- if (arc_iterator[s] == 0 && !(state_status[s] & kArcIterDone) && visit)
- arc_iterator[s] = new AIterator(fst, s);
- // Deletes arc iterator if done.
- AIterator *aiter = arc_iterator[s];
- if ((aiter && aiter->Done()) || !visit) {
- delete aiter;
- arc_iterator[s] = 0;
- state_status[s] |= kArcIterDone;
- }
- // Dequeues state and marks black if done
- if (state_status[s] & kArcIterDone) {
- queue->Dequeue();
- visitor->FinishState(s);
- state_status[s] = kBlackState;
- continue;
- }
-
- const Arc &arc = aiter->Value();
- if (arc.nextstate >= state_status.size()) {
- nstates = arc.nextstate + 1;
- state_status.resize(nstates, kWhiteState);
- arc_iterator.resize(nstates);
- }
- // Visits respective arc types
- if (filter(arc)) {
- // Enqueues destination state and marks grey if white
- if (state_status[arc.nextstate] == kWhiteState) {
- visit = visitor->WhiteArc(s, arc);
- if (!visit) continue;
- visit = visitor->InitState(arc.nextstate, root);
- state_status[arc.nextstate] = kGreyState;
- queue->Enqueue(arc.nextstate);
- } else if (state_status[arc.nextstate] == kBlackState) {
- visit = visitor->BlackArc(s, arc);
- } else {
- visit = visitor->GreyArc(s, arc);
- }
- }
- aiter->Next();
- // Destroys an iterator ASAP for efficiency.
- if (aiter->Done()) {
- delete aiter;
- arc_iterator[s] = 0;
- state_status[s] |= kArcIterDone;
- }
- }
- // Finds next tree root
- for (root = root == start ? 0 : root + 1;
- root < nstates && state_status[root] != kWhiteState;
- ++root) {
- }
-
- // Check for a state beyond the largest known state
- if (!expanded && root == nstates) {
- for (; !siter.Done(); siter.Next()) {
- if (siter.Value() == nstates) {
- ++nstates;
- state_status.push_back(kWhiteState);
- arc_iterator.push_back(0);
- break;
- }
- }
- }
- }
- visitor->FinishVisit();
-}
-
-
-template <class Arc, class V, class Q>
-inline void Visit(const Fst<Arc> &fst, V *visitor, Q* queue) {
- Visit(fst, visitor, queue, AnyArcFilter<Arc>());
-}
-
-// Copies input FST to mutable FST following queue order.
-template <class A>
-class CopyVisitor {
- public:
- typedef A Arc;
- typedef typename A::StateId StateId;
-
- CopyVisitor(MutableFst<Arc> *ofst) : ifst_(0), ofst_(ofst) {}
-
- void InitVisit(const Fst<A> &ifst) {
- ifst_ = &ifst;
- ofst_->DeleteStates();
- ofst_->SetStart(ifst_->Start());
- }
-
- bool InitState(StateId s, StateId) {
- while (ofst_->NumStates() <= s)
- ofst_->AddState();
- return true;
- }
-
- bool WhiteArc(StateId s, const Arc &arc) {
- ofst_->AddArc(s, arc);
- return true;
- }
-
- bool GreyArc(StateId s, const Arc &arc) {
- ofst_->AddArc(s, arc);
- return true;
- }
-
- bool BlackArc(StateId s, const Arc &arc) {
- ofst_->AddArc(s, arc);
- return true;
- }
-
- void FinishState(StateId s) {
- ofst_->SetFinal(s, ifst_->Final(s));
- }
-
- void FinishVisit() {}
-
- private:
- const Fst<Arc> *ifst_;
- MutableFst<Arc> *ofst_;
-};
-
-
-// Visits input FST up to a state limit following queue order. If
-// 'access_only' is true, aborts on visiting first state not
-// accessible from the initial state.
-template <class A>
-class PartialVisitor {
- public:
- typedef A Arc;
- typedef typename A::StateId StateId;
-
- explicit PartialVisitor(StateId maxvisit, bool access_only = false)
- : maxvisit_(maxvisit),
- access_only_(access_only),
- start_(kNoStateId) {}
-
- void InitVisit(const Fst<A> &ifst) {
- nvisit_ = 0;
- start_ = ifst.Start();
- }
-
- bool InitState(StateId s, StateId root) {
- if (access_only_ && root != start_)
- return false;
- ++nvisit_;
- return nvisit_ <= maxvisit_;
- }
-
- bool WhiteArc(StateId s, const Arc &arc) { return true; }
- bool GreyArc(StateId s, const Arc &arc) { return true; }
- bool BlackArc(StateId s, const Arc &arc) { return true; }
- void FinishState(StateId s) {}
- void FinishVisit() {}
-
- private:
- StateId maxvisit_;
- bool access_only_;
- StateId nvisit_;
- StateId start_;
-
-};
-
-
-} // namespace fst
-
-#endif // FST_LIB_VISIT_H__
Powered by cgit, Themed by Ted Yin.