// See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Functions and classes to sort arcs in an FST.

#ifndef FST_REVERSE_H_
#define FST_REVERSE_H_

#include <algorithm>
#include <vector>

#include <fst/cache.h>


namespace fst {

// Reverses an FST. The reversed result is written to an output mutable FST.
// If A transduces string x to y with weight a, then the reverse of A
// transduces the reverse of x to the reverse of y with weight a.Reverse().
//
// Typically, a = a.Reverse() and an arc is its own reverse (e.g., for
// TropicalWeight or LogWeight). In general, e.g., when the weights only form a
// left or right semiring, the output arc type must match the input arc type
// except having the reversed Weight type.
//
// When require_superinitial is false, a superinitial state is not created in
// the reversed FST iff the input FST has exactly one final state (which becomes
// the initial state of the reversed FST) with a final weight of semiring One,
// or if it does not belong to any cycle. When require_superinitial is true, a
// superinitial state is always created.
template <class FromArc, class ToArc>
void Reverse(const Fst<FromArc> &ifst, MutableFst<ToArc> *ofst,
             bool require_superinitial = true) {
  using StateId = typename FromArc::StateId;
  using FromWeight = typename FromArc::Weight;
  using ToWeight = typename ToArc::Weight;
  ofst->DeleteStates();
  ofst->SetInputSymbols(ifst.InputSymbols());
  ofst->SetOutputSymbols(ifst.OutputSymbols());
  if (ifst.Properties(kExpanded, false)) {
    ofst->ReserveStates(CountStates(ifst) + 1);
  }
  StateId istart = ifst.Start();
  StateId ostart = kNoStateId;
  StateId offset = 0;
  uint64 dfs_iprops = 0;
  uint64 dfs_oprops = 0;
  if (!require_superinitial) {
    for (StateIterator<Fst<FromArc>> siter(ifst); !siter.Done(); siter.Next()) {
      const auto s = siter.Value();
      if (ifst.Final(s) == FromWeight::Zero()) continue;
      if (ostart != kNoStateId) {
        ostart = kNoStateId;
        break;
      } else {
        ostart = s;
      }
    }
    if (ostart != kNoStateId && ifst.Final(ostart) != FromWeight::One()) {
      std::vector<StateId> scc;
      SccVisitor<FromArc> scc_visitor(&scc, nullptr, nullptr, &dfs_iprops);
      DfsVisit(ifst, &scc_visitor);
      if (count(scc.begin(), scc.end(), scc[ostart]) > 1) {
        ostart = kNoStateId;
      } else {
        for (ArcIterator<Fst<FromArc>> aiter(ifst, ostart); !aiter.Done();
             aiter.Next()) {
          if (aiter.Value().nextstate == ostart) {
            ostart = kNoStateId;
            break;
          }
        }
      }
      if (ostart != kNoStateId) dfs_oprops = kInitialAcyclic;
    }
  }
  if (ostart == kNoStateId) {  // Super-initial requested or needed.
    ostart = ofst->AddState();
    offset = 1;
  }
  for (StateIterator<Fst<FromArc>> siter(ifst); !siter.Done(); siter.Next()) {
    const auto is = siter.Value();
    const auto os = is + offset;
    while (ofst->NumStates() <= os) ofst->AddState();
    if (is == istart) ofst->SetFinal(os, ToWeight::One());
    const auto weight = ifst.Final(is);
    if ((weight != FromWeight::Zero()) && (offset == 1)) {
      const ToArc oarc(0, 0, weight.Reverse(), os);
      ofst->AddArc(0, oarc);
    }
    for (ArcIterator<Fst<FromArc>> aiter(ifst, is); !aiter.Done();
         aiter.Next()) {
      const auto &iarc = aiter.Value();
      const auto nos = iarc.nextstate + offset;
      auto weight = iarc.weight.Reverse();
      if (!offset && (nos == ostart)) {
        weight = Times(ifst.Final(ostart).Reverse(), weight);
      }
      const ToArc oarc(iarc.ilabel, iarc.olabel, weight, os);
      while (ofst->NumStates() <= nos) ofst->AddState();
      ofst->AddArc(nos, oarc);
    }
  }
  ofst->SetStart(ostart);
  if (offset == 0 && ostart == istart) {
    ofst->SetFinal(ostart, ifst.Final(ostart).Reverse());
  }
  const auto iprops = ifst.Properties(kCopyProperties, false) | dfs_iprops;
  const auto oprops = ofst->Properties(kFstProperties, false) | dfs_oprops;
  ofst->SetProperties(ReverseProperties(iprops, offset == 1) | oprops,
                      kFstProperties);
}

}  // namespace fst

#endif  // FST_REVERSE_H_