// See www.openfst.org for extensive documentation on this weighted
  // finite-state transducer library.
  //
  // Class to compute various information about FSTs, a helper class for
  // fstinfo.cc.
  
  #ifndef FST_SCRIPT_INFO_IMPL_H_
  #define FST_SCRIPT_INFO_IMPL_H_
  
  #include <map>
  #include <string>
  #include <vector>
  
  #include <fst/connect.h>
  #include <fst/dfs-visit.h>
  #include <fst/fst.h>
  #include <fst/lookahead-matcher.h>
  #include <fst/matcher.h>
  #include <fst/queue.h>
  #include <fst/test-properties.h>
  #include <fst/verify.h>
  #include <fst/visit.h>
  
  namespace fst {
  
  // Compute various information about FSTs, helper class for fstinfo.cc.
  // WARNING: Stand-alone use of this class is not recommended, most code
  // should call directly the relevant library functions: Fst<Arc>::NumStates,
  // Fst<Arc>::NumArcs, TestProperties, etc.
  class FstInfo {
   public:
    FstInfo() {}
  
    // When info_type is "short" (or "auto" and not an ExpandedFst) then only
    // minimal info is computed and can be requested.
    template <typename Arc>
    FstInfo(const Fst<Arc> &fst, bool test_properties,
            const string &arc_filter_type = "any",
            const string &info_type = "auto", bool verify = true)
        : fst_type_(fst.Type()),
          input_symbols_(fst.InputSymbols() ? fst.InputSymbols()->Name()
                                            : "none"),
          output_symbols_(fst.OutputSymbols() ? fst.OutputSymbols()->Name()
                                              : "none"),
          nstates_(0),
          narcs_(0),
          start_(kNoStateId),
          nfinal_(0),
          nepsilons_(0),
          niepsilons_(0),
          noepsilons_(0),
          ilabel_mult_(0.0),
          olabel_mult_(0.0),
          naccess_(0),
          ncoaccess_(0),
          nconnect_(0),
          ncc_(0),
          nscc_(0),
          input_match_type_(MATCH_NONE),
          output_match_type_(MATCH_NONE),
          input_lookahead_(false),
          output_lookahead_(false),
          properties_(0),
          arc_filter_type_(arc_filter_type),
          long_info_(true),
          arc_type_(Arc::Type()) {
      using Label = typename Arc::Label;
      using StateId = typename Arc::StateId;
      using Weight = typename Arc::Weight;
      if (info_type == "long") {
        long_info_ = true;
      } else if (info_type == "short") {
        long_info_ = false;
      } else if (info_type == "auto") {
        long_info_ = fst.Properties(kExpanded, false);
      } else {
        FSTERROR() << "Bad info type: " << info_type;
        return;
      }
      if (!long_info_) return;
      // If the FST is not sane, we return.
      if (verify && !Verify(fst)) {
        FSTERROR() << "FstInfo: Verify: FST not well-formed";
        return;
      }
      start_ = fst.Start();
      properties_ = fst.Properties(kFstProperties, test_properties);
      for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
        ++nstates_;
        const auto s = siter.Value();
        if (fst.Final(s) != Weight::Zero()) ++nfinal_;
        std::map<Label, size_t> ilabel_count;
        std::map<Label, size_t> olabel_count;
        for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
          const auto &arc = aiter.Value();
          ++narcs_;
          if (arc.ilabel == 0 && arc.olabel == 0) ++nepsilons_;
          if (arc.ilabel == 0) ++niepsilons_;
          if (arc.olabel == 0) ++noepsilons_;
          ++ilabel_count[arc.ilabel];
          ++olabel_count[arc.olabel];
        }
        for (auto it = ilabel_count.begin(); it != ilabel_count.end(); ++it) {
          ilabel_mult_ += it->second * it->second;
        }
        for (auto it = olabel_count.begin(); it != olabel_count.end(); ++it) {
          olabel_mult_ += it->second * it->second;
        }
      }
      if (narcs_ > 0) {
        ilabel_mult_ /= narcs_;
        olabel_mult_ /= narcs_;
      }
      {
        std::vector<StateId> cc;
        CcVisitor<Arc> cc_visitor(&cc);
        FifoQueue<StateId> fifo_queue;
        if (arc_filter_type == "any") {
          Visit(fst, &cc_visitor, &fifo_queue);
        } else if (arc_filter_type == "epsilon") {
          Visit(fst, &cc_visitor, &fifo_queue, EpsilonArcFilter<Arc>());
        } else if (arc_filter_type == "iepsilon") {
          Visit(fst, &cc_visitor, &fifo_queue, InputEpsilonArcFilter<Arc>());
        } else if (arc_filter_type == "oepsilon") {
          Visit(fst, &cc_visitor, &fifo_queue, OutputEpsilonArcFilter<Arc>());
        } else {
          FSTERROR() << "Bad arc filter type: " << arc_filter_type;
          return;
        }
        for (StateId s = 0; s < cc.size(); ++s) {
          if (cc[s] >= ncc_) ncc_ = cc[s] + 1;
        }
      }
      {
        std::vector<StateId> scc;
        std::vector<bool> access, coaccess;
        uint64 props = 0;
        SccVisitor<Arc> scc_visitor(&scc, &access, &coaccess, &props);
        if (arc_filter_type == "any") {
          DfsVisit(fst, &scc_visitor);
        } else if (arc_filter_type == "epsilon") {
          DfsVisit(fst, &scc_visitor, EpsilonArcFilter<Arc>());
        } else if (arc_filter_type == "iepsilon") {
          DfsVisit(fst, &scc_visitor, InputEpsilonArcFilter<Arc>());
        } else if (arc_filter_type == "oepsilon") {
          DfsVisit(fst, &scc_visitor, OutputEpsilonArcFilter<Arc>());
        } else {
          FSTERROR() << "Bad arc filter type: " << arc_filter_type;
          return;
        }
        for (StateId s = 0; s < scc.size(); ++s) {
          if (access[s]) ++naccess_;
          if (coaccess[s]) ++ncoaccess_;
          if (access[s] && coaccess[s]) ++nconnect_;
          if (scc[s] >= nscc_) nscc_ = scc[s] + 1;
        }
      }
      LookAheadMatcher<Fst<Arc>> imatcher(fst, MATCH_INPUT);
      input_match_type_ = imatcher.Type(test_properties);
      input_lookahead_ = imatcher.Flags() & kInputLookAheadMatcher;
      LookAheadMatcher<Fst<Arc>> omatcher(fst, MATCH_OUTPUT);
      output_match_type_ = omatcher.Type(test_properties);
      output_lookahead_ = omatcher.Flags() & kOutputLookAheadMatcher;
    }
  
    // Short info.
  
    const string &FstType() const { return fst_type_; }
  
    const string &ArcType() const { return arc_type_; }
  
    const string &InputSymbols() const { return input_symbols_; }
  
    const string &OutputSymbols() const { return output_symbols_; }
  
    bool LongInfo() const { return long_info_; }
  
    const string &ArcFilterType() const { return arc_filter_type_; }
  
    // Long info.
  
    MatchType InputMatchType() const {
      CheckLong();
      return input_match_type_;
    }
  
    MatchType OutputMatchType() const {
      CheckLong();
      return output_match_type_;
    }
  
    bool InputLookAhead() const {
      CheckLong();
      return input_lookahead_;
    }
  
    bool OutputLookAhead() const {
      CheckLong();
      return output_lookahead_;
    }
  
    int64 NumStates() const {
      CheckLong();
      return nstates_;
    }
  
    size_t NumArcs() const {
      CheckLong();
      return narcs_;
    }
  
    int64 Start() const {
      CheckLong();
      return start_;
    }
  
    size_t NumFinal() const {
      CheckLong();
      return nfinal_;
    }
  
    size_t NumEpsilons() const {
      CheckLong();
      return nepsilons_;
    }
  
    size_t NumInputEpsilons() const {
      CheckLong();
      return niepsilons_;
    }
  
    size_t NumOutputEpsilons() const {
      CheckLong();
      return noepsilons_;
    }
  
    double InputLabelMultiplicity() const {
      CheckLong();
      return ilabel_mult_;
    }
  
    double OutputLabelMultiplicity() const {
      CheckLong();
      return olabel_mult_;
    }
  
    size_t NumAccessible() const {
      CheckLong();
      return naccess_;
    }
  
    size_t NumCoAccessible() const {
      CheckLong();
      return ncoaccess_;
    }
  
    size_t NumConnected() const {
      CheckLong();
      return nconnect_;
    }
  
    size_t NumCc() const {
      CheckLong();
      return ncc_;
    }
  
    size_t NumScc() const {
      CheckLong();
      return nscc_;
    }
  
    uint64 Properties() const {
      CheckLong();
      return properties_;
    }
  
   private:
    void CheckLong() const {
      if (!long_info_)
        FSTERROR() << "FstInfo: Method only available with long info signature";
    }
  
    string fst_type_;
    string input_symbols_;
    string output_symbols_;
    int64 nstates_;
    size_t narcs_;
    int64 start_;
    size_t nfinal_;
    size_t nepsilons_;
    size_t niepsilons_;
    size_t noepsilons_;
    double ilabel_mult_;
    double olabel_mult_;
    size_t naccess_;
    size_t ncoaccess_;
    size_t nconnect_;
    size_t ncc_;
    size_t nscc_;
    MatchType input_match_type_;
    MatchType output_match_type_;
    bool input_lookahead_;
    bool output_lookahead_;
    uint64 properties_;
    string arc_filter_type_;
    bool long_info_;
    string arc_type_;
  };
  
  void PrintFstInfoImpl(const FstInfo &fstinfo, bool pipe = false);
  
  }  // namespace fst
  
  #endif  // FST_SCRIPT_INFO_IMPL_H_