// See www.openfst.org for extensive documentation on this weighted
  // finite-state transducer library.
  //
  // Queue-dependent visitation of finite-state transducers. See also dfs-visit.h.
  
  #ifndef FST_VISIT_H_
  #define FST_VISIT_H_
  
  
  #include <fst/arcfilter.h>
  #include <fst/mutable-fst.h>
  
  
  namespace fst {
  
  // Visitor Interface: class determining 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:
  //   using StateId = typename Arc::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 &arc);
  //
  //   // Invoked when arc to grey/unfinished state examined.
  //   bool GreyArc(StateId s, const Arc &arc);
  //
  //   // Invoked when arc to black/finished state examined.
  //   bool BlackArc(StateId s, const Arc &arc);
  //
  //   // 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. If 'access_only' is true, performs visitation only to states
  // accessible from the initial state.
  template <class FST, class Visitor, class Queue, class ArcFilter>
  void Visit(const FST &fst, Visitor *visitor, Queue *queue, ArcFilter filter,
             bool access_only = false) {
    using Arc = typename FST::Arc;
    using StateId = typename Arc::StateId;
    visitor->InitVisit(fst);
    const auto start = fst.Start();
    if (start == kNoStateId) {
      visitor->FinishVisit();
      return;
    }
    // An FST's state's visit color.
    static constexpr uint8 kWhiteState = 0x01;  // Undiscovered.
    static constexpr uint8 kGreyState = 0x02;   // Discovered & unfinished.
    static constexpr uint8 kBlackState = 0x04;  // Finished.
    // We destroy an iterator as soon as possible and mark it so.
    static constexpr uint8 kArcIterDone = 0x08;
    std::vector<uint8> state_status;
    std::vector<ArcIterator<FST> *> arc_iterator;
    MemoryPool<ArcIterator<FST>> aiter_pool;
    StateId nstates = start + 1;  // Number of known states in general case.
    bool expanded = false;
    if (fst.Properties(kExpanded, false)) {  // Tests if expanded, then uses
      nstates = CountStates(fst);            // 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 (auto root = start; visit && root < nstates;) {
      visit = visitor->InitState(root, root);
      state_status[root] = kGreyState;
      queue->Enqueue(root);
      while (!queue->Empty()) {
        auto state = queue->Head();
        if (state >= state_status.size()) {
          nstates = state + 1;
          state_status.resize(nstates, kWhiteState);
          arc_iterator.resize(nstates);
        }
        // Creates arc iterator if needed.
        if (!arc_iterator[state] && !(state_status[state] & kArcIterDone) &&
            visit) {
          arc_iterator[state] = new (&aiter_pool) ArcIterator<FST>(fst, state);
        }
        // Deletes arc iterator if done.
        auto *aiter = arc_iterator[state];
        if ((aiter && aiter->Done()) || !visit) {
          Destroy(aiter, &aiter_pool);
          arc_iterator[state] = nullptr;
          state_status[state] |= kArcIterDone;
        }
        // Dequeues state and marks black if done.
        if (state_status[state] & kArcIterDone) {
          queue->Dequeue();
          visitor->FinishState(state);
          state_status[state] = kBlackState;
          continue;
        }
        const auto &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(state, 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(state, arc);
          } else {
            visit = visitor->GreyArc(state, arc);
          }
        }
        aiter->Next();
        // Destroys an iterator ASAP for efficiency.
        if (aiter->Done()) {
          Destroy(aiter, &aiter_pool);
          arc_iterator[state] = nullptr;
          state_status[state] |= kArcIterDone;
        }
      }
      if (access_only) break;
      // 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(nullptr);
            break;
          }
        }
      }
    }
    visitor->FinishVisit();
  }
  
  template <class Arc, class Visitor, class Queue>
  inline void Visit(const Fst<Arc> &fst, Visitor *visitor, Queue *queue) {
    Visit(fst, visitor, queue, AnyArcFilter<Arc>());
  }
  
  // Copies input FST to mutable FST following queue order.
  template <class A>
  class CopyVisitor {
   public:
    using Arc = A;
    using StateId = typename Arc::StateId;
  
    explicit CopyVisitor(MutableFst<Arc> *ofst) : ifst_(nullptr), ofst_(ofst) {}
  
    void InitVisit(const Fst<A> &ifst) {
      ifst_ = &ifst;
      ofst_->DeleteStates();
      ofst_->SetStart(ifst_->Start());
    }
  
    bool InitState(StateId state, StateId) {
      while (ofst_->NumStates() <= state) ofst_->AddState();
      return true;
    }
  
    bool WhiteArc(StateId state, const Arc &arc) {
      ofst_->AddArc(state, arc);
      return true;
    }
  
    bool GreyArc(StateId state, const Arc &arc) {
      ofst_->AddArc(state, arc);
      return true;
    }
  
    bool BlackArc(StateId state, const Arc &arc) {
      ofst_->AddArc(state, arc);
      return true;
    }
  
    void FinishState(StateId state) {
      ofst_->SetFinal(state, ifst_->Final(state));
    }
  
    void FinishVisit() {}
  
   private:
    const Fst<Arc> *ifst_;
    MutableFst<Arc> *ofst_;
  };
  
  // Visits input FST up to a state limit following queue order.
  template <class A>
  class PartialVisitor {
   public:
    using Arc = A;
    using StateId = typename Arc::StateId;
  
    explicit PartialVisitor(StateId maxvisit)
        : fst_(nullptr), maxvisit_(maxvisit) {}
  
    void InitVisit(const Fst<A> &ifst) {
      fst_ = &ifst;
      ninit_ = 0;
      nfinish_ = 0;
    }
  
    bool InitState(StateId state, StateId root) {
      ++ninit_;
      return ninit_ <= maxvisit_;
    }
  
    bool WhiteArc(StateId state, const Arc &arc) { return true; }
  
    bool GreyArc(StateId state, const Arc &arc) { return true; }
  
    bool BlackArc(StateId state, const Arc &arc) { return true; }
  
    void FinishState(StateId state) {
      fst_->Final(state);  // Visits super-final arc.
      ++nfinish_;
    }
  
    void FinishVisit() {}
  
    StateId NumInitialized() { return ninit_; }
  
    StateId NumFinished() { return nfinish_; }
  
   private:
    const Fst<Arc> *fst_;
    StateId maxvisit_;
    StateId ninit_;
    StateId nfinish_;
  };
  
  // Copies input FST to mutable FST up to a state limit following queue order.
  template <class A>
  class PartialCopyVisitor : public CopyVisitor<A> {
   public:
    using Arc = A;
    using StateId = typename Arc::StateId;
  
    using CopyVisitor<A>::WhiteArc;
  
    PartialCopyVisitor(MutableFst<Arc> *ofst, StateId maxvisit,
                       bool copy_grey = true, bool copy_black = true)
        : CopyVisitor<A>(ofst), maxvisit_(maxvisit),
          copy_grey_(copy_grey), copy_black_(copy_black) {}
  
    void InitVisit(const Fst<A> &ifst) {
      CopyVisitor<A>::InitVisit(ifst);
      ninit_ = 0;
      nfinish_ = 0;
    }
  
    bool InitState(StateId state, StateId root) {
      CopyVisitor<A>::InitState(state, root);
      ++ninit_;
      return ninit_ <= maxvisit_;
    }
  
    bool GreyArc(StateId state, const Arc &arc) {
      if (copy_grey_) return CopyVisitor<A>::GreyArc(state, arc);
      return true;
    }
  
    bool BlackArc(StateId state, const Arc &arc) {
      if (copy_black_) return CopyVisitor<A>::BlackArc(state, arc);
      return true;
    }
  
    void FinishState(StateId state) {
      CopyVisitor<A>::FinishState(state);
      ++nfinish_;
    }
  
    void FinishVisit() {}
  
    StateId NumInitialized() { return ninit_; }
  
    StateId NumFinished() { return nfinish_; }
  
   private:
    StateId maxvisit_;
    StateId ninit_;
    StateId nfinish_;
    const bool copy_grey_;
    const bool copy_black_;
  };
  
  }  // namespace fst
  
  #endif  // FST_VISIT_H_