// See www.openfst.org for extensive documentation on this weighted
  // finite-state transducer library.
  //
  // Function to test two FSTs are isomorphic, i.e., they are equal up to a state
  // and arc re-ordering. FSTs should be deterministic when viewed as
  // unweighted automata.
  
  #ifndef FST_ISOMORPHIC_H_
  #define FST_ISOMORPHIC_H_
  
  #include <algorithm>
  #include <list>
  #include <type_traits>
  #include <vector>
  
  #include <fst/log.h>
  
  #include <fst/fst.h>
  
  
  namespace fst {
  namespace internal {
  
  // Orders weights for equality checking.
  template <class Weight, typename std::enable_if<
                              IsIdempotent<Weight>::value>::type * = nullptr>
  bool WeightCompare(const Weight &w1, const Weight &w2, float delta,
                     bool *error) {
    return NaturalLess<Weight>()(w1, w2);
  }
  
  template <class Weight, typename std::enable_if<
                              !IsIdempotent<Weight>::value>::type * = nullptr>
  bool WeightCompare(const Weight &w1, const Weight &w2, float delta,
                     bool *error) {
    // No natural order; use hash.
    const auto q1 = w1.Quantize(delta);
    const auto q2 = w2.Quantize(delta);
    auto n1 = q1.Hash();
    auto n2 = q2.Hash();
    // Hash not unique; very unlikely to happen.
    if (n1 == n2 && q1 != q2) {
      VLOG(1) << "Isomorphic: Weight hash collision";
      *error = true;
    }
    return n1 < n2;
  }
  
  template <class Arc>
  class Isomorphism {
    using StateId = typename Arc::StateId;
  
   public:
    Isomorphism(const Fst<Arc> &fst1, const Fst<Arc> &fst2, float delta)
        : fst1_(fst1.Copy()),
          fst2_(fst2.Copy()),
          delta_(delta),
          error_(false),
          comp_(delta, &error_) {}
  
    // Checks if input FSTs are isomorphic.
    bool IsIsomorphic() {
      if (fst1_->Start() == kNoStateId && fst2_->Start() == kNoStateId) {
        return true;
      }
      if (fst1_->Start() == kNoStateId || fst2_->Start() == kNoStateId) {
        return false;
      }
      PairState(fst1_->Start(), fst2_->Start());
      while (!queue_.empty()) {
        const auto &pr = queue_.front();
        if (!IsIsomorphicState(pr.first, pr.second)) return false;
        queue_.pop_front();
      }
      return true;
    }
  
    bool Error() const { return error_; }
  
   private:
    // Orders arcs for equality checking.
    class ArcCompare {
     public:
      ArcCompare(float delta, bool *error) : delta_(delta), error_(error) {}
  
      bool operator()(const Arc &arc1, const Arc &arc2) const {
        if (arc1.ilabel < arc2.ilabel) return true;
        if (arc1.ilabel > arc2.ilabel) return false;
        if (arc1.olabel < arc2.olabel) return true;
        if (arc1.olabel > arc2.olabel) return false;
        return WeightCompare(arc1.weight, arc2.weight, delta_, error_);
      }
  
     private:
      float delta_;
      bool *error_;
    };
  
    // Maintains state correspondences and queue.
    bool PairState(StateId s1, StateId s2) {
      if (state_pairs_.size() <= s1) state_pairs_.resize(s1 + 1, kNoStateId);
      if (state_pairs_[s1] == s2) {
        return true;  // already seen this pair
      } else if (state_pairs_[s1] != kNoStateId) {
        return false;  // s1 already paired with another s2
      }
      state_pairs_[s1] = s2;
      queue_.push_back(std::make_pair(s1, s2));
      return true;
    }
  
    // Checks if state pair is isomorphic
    bool IsIsomorphicState(StateId s1, StateId s2);
  
    std::unique_ptr<Fst<Arc>> fst1_;
    std::unique_ptr<Fst<Arc>> fst2_;
    float delta_;                          // Weight equality delta.
    std::vector<Arc> arcs1_;               // For sorting arcs on FST1.
    std::vector<Arc> arcs2_;               // For sorting arcs on FST2.
    std::vector<StateId> state_pairs_;     // Maintains state correspondences.
    std::list<std::pair<StateId, StateId>> queue_;  // Queue of state pairs.
    bool error_;                           // Error flag.
    ArcCompare comp_;
  };
  
  template <class Arc>
  bool Isomorphism<Arc>::IsIsomorphicState(StateId s1, StateId s2) {
    if (!ApproxEqual(fst1_->Final(s1), fst2_->Final(s2), delta_)) return false;
    auto narcs1 = fst1_->NumArcs(s1);
    auto narcs2 = fst2_->NumArcs(s2);
    if (narcs1 != narcs2) return false;
    ArcIterator<Fst<Arc>> aiter1(*fst1_, s1);
    ArcIterator<Fst<Arc>> aiter2(*fst2_, s2);
    arcs1_.clear();
    arcs1_.reserve(narcs1);
    arcs2_.clear();
    arcs2_.reserve(narcs2);
    for (; !aiter1.Done(); aiter1.Next(), aiter2.Next()) {
      arcs1_.push_back(aiter1.Value());
      arcs2_.push_back(aiter2.Value());
    }
    std::sort(arcs1_.begin(), arcs1_.end(), comp_);
    std::sort(arcs2_.begin(), arcs2_.end(), comp_);
    for (size_t i = 0; i < arcs1_.size(); ++i) {
      const auto &arc1 = arcs1_[i];
      const auto &arc2 = arcs2_[i];
      if (arc1.ilabel != arc2.ilabel) return false;
      if (arc1.olabel != arc2.olabel) return false;
      if (!ApproxEqual(arc1.weight, arc2.weight, delta_)) return false;
      if (!PairState(arc1.nextstate, arc2.nextstate)) return false;
      if (i > 0) {  // Checks for non-determinism.
        const auto &arc0 = arcs1_[i - 1];
        if (arc1.ilabel == arc0.ilabel && arc1.olabel == arc0.olabel &&
            ApproxEqual(arc1.weight, arc0.weight, delta_)) {
          VLOG(1) << "Isomorphic: Non-determinism as an unweighted automaton";
          error_ = true;
          return false;
        }
      }
    }
    return true;
  }
  
  }  // namespace internal
  
  // Tests if two FSTs have the same states and arcs up to a reordering.
  // Inputs should be non-deterministic when viewed as unweighted automata.
  template <class Arc>
  bool Isomorphic(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
                  float delta = kDelta) {
    internal::Isomorphism<Arc> iso(fst1, fst2, delta);
    bool result = iso.IsIsomorphic();
    if (iso.Error()) {
      FSTERROR() << "Isomorphic: Cannot determine if inputs are isomorphic";
      return false;
    } else {
      return result;
    }
  }
  
  }  // namespace fst
  
  #endif  // FST_ISOMORPHIC_H_