// See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// Class to compute the difference between two FSAs.

#ifndef FST_DIFFERENCE_H_
#define FST_DIFFERENCE_H_

#include <memory>


#include <fst/cache.h>
#include <fst/complement.h>
#include <fst/compose.h>


namespace fst {

template <class Arc, class M = Matcher<Fst<Arc>>,
          class Filter = SequenceComposeFilter<M>,
          class StateTable =
              GenericComposeStateTable<Arc, typename Filter::FilterState>>
struct DifferenceFstOptions
    : public ComposeFstOptions<Arc, M, Filter, StateTable> {
  explicit DifferenceFstOptions(const CacheOptions &opts = CacheOptions(),
                                M *matcher1 = nullptr, M *matcher2 = nullptr,
                                Filter *filter = nullptr,
                                StateTable *state_table = nullptr)
      : ComposeFstOptions<Arc, M, Filter, StateTable>(opts, matcher1, matcher2,
                                                      filter, state_table) {}
};

// Computes the difference between two FSAs. This version is a delayed FST.
// Only strings that are in the first automaton but not in second are retained
// in the result.
//
// The first argument must be an acceptor; the second argument must be an
// unweighted, epsilon-free, deterministic acceptor. One of the arguments must
// be label-sorted.
//
// Complexity: same as ComposeFst.
//
// Caveats: same as ComposeFst.
template <class A>
class DifferenceFst : public ComposeFst<A> {
 public:
  using Arc = A;
  using Weight = typename Arc::Weight;
  using StateId = typename Arc::StateId;

  using ComposeFst<Arc>::CreateBase1;

  // A - B = A ^ B'.
  DifferenceFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
                const CacheOptions &opts = CacheOptions())
      : ComposeFst<Arc>(CreateDifferenceImplWithCacheOpts(fst1, fst2, opts)) {
    if (!fst1.Properties(kAcceptor, true)) {
      FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
      GetImpl()->SetProperties(kError, kError);
    }
  }

  template <class Matcher, class Filter, class StateTable>
  DifferenceFst(
      const Fst<Arc> &fst1, const Fst<Arc> &fst2,
      const DifferenceFstOptions<Arc, Matcher, Filter, StateTable> &opts)
      : ComposeFst<Arc>(
            CreateDifferenceImplWithDifferenceOpts(fst1, fst2, opts)) {
    if (!fst1.Properties(kAcceptor, true)) {
      FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
      GetImpl()->SetProperties(kError, kError);
    }
  }

  // See Fst<>::Copy() for doc.
  DifferenceFst(const DifferenceFst<Arc> &fst, bool safe = false)
      : ComposeFst<Arc>(fst, safe) {}

  // Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc.
  DifferenceFst<Arc> *Copy(bool safe = false) const override {
    return new DifferenceFst<Arc>(*this, safe);
  }

 private:
  using Impl = internal::ComposeFstImplBase<Arc>;
  using ImplToFst<Impl>::GetImpl;

  static std::shared_ptr<Impl> CreateDifferenceImplWithCacheOpts(
      const Fst<Arc> &fst1, const Fst<Arc> &fst2, const CacheOptions &opts) {
    using RM = RhoMatcher<Matcher<Fst<A>>>;
    ComplementFst<Arc> cfst(fst2);
    ComposeFstOptions<A, RM> copts(
        CacheOptions(), new RM(fst1, MATCH_NONE),
        new RM(cfst, MATCH_INPUT, ComplementFst<Arc>::kRhoLabel));
    return CreateBase1(fst1, cfst, copts);
  }

  template <class Matcher, class Filter, class StateTable>
  static std::shared_ptr<Impl> CreateDifferenceImplWithDifferenceOpts(
      const Fst<Arc> &fst1, const Fst<Arc> &fst2,
      const DifferenceFstOptions<Arc, Matcher, Filter, StateTable> &opts) {
    using RM = RhoMatcher<Matcher>;
    ComplementFst<Arc> cfst(fst2);
    ComposeFstOptions<Arc, RM> copts(opts);
    copts.matcher1 = new RM(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS,
                            opts.matcher1);
    copts.matcher2 = new RM(cfst, MATCH_INPUT, ComplementFst<Arc>::kRhoLabel,
                            MATCHER_REWRITE_ALWAYS, opts.matcher2);
    return CreateBase1(fst1, cfst, copts);
  }
};

// Specialization for DifferenceFst.
template <class Arc>
class StateIterator<DifferenceFst<Arc>>
    : public StateIterator<ComposeFst<Arc>> {
 public:
  explicit StateIterator(const DifferenceFst<Arc> &fst)
      : StateIterator<ComposeFst<Arc>>(fst) {}
};

// Specialization for DifferenceFst.
template <class Arc>
class ArcIterator<DifferenceFst<Arc>> : public ArcIterator<ComposeFst<Arc>> {
 public:
  using StateId = typename Arc::StateId;

  ArcIterator(const DifferenceFst<Arc> &fst, StateId s)
      : ArcIterator<ComposeFst<Arc>>(fst, s) {}
};

using DifferenceOptions = ComposeOptions;

// Useful alias when using StdArc.
using StdDifferenceFst = DifferenceFst<StdArc>;

using DifferenceOptions = ComposeOptions;

// Computes the difference between two FSAs. This version writes the difference
// to an output MutableFst. Only strings that are in the first automaton but not
// in the second are retained in the result.
//
// The first argument must be an acceptor; the second argument must be an
// unweighted, epsilon-free, deterministic acceptor. One of the arguments must
// be label-sorted.
//
// Complexity: same as Compose.
//
// Caveats: same as Compose.
template <class Arc>
void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
                MutableFst<Arc> *ofst,
                const DifferenceOptions &opts = DifferenceOptions()) {
  using M = Matcher<Fst<Arc>>;
  if (opts.filter_type == AUTO_FILTER) {
    CacheOptions nopts;
    nopts.gc_limit = 0;  // Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
  } else if (opts.filter_type == SEQUENCE_FILTER) {
    DifferenceFstOptions<Arc> dopts;
    dopts.gc_limit = 0;  // Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
  } else if (opts.filter_type == ALT_SEQUENCE_FILTER) {
    DifferenceFstOptions<Arc, M, AltSequenceComposeFilter<M>> dopts;
    dopts.gc_limit = 0;  // Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
  } else if (opts.filter_type == MATCH_FILTER) {
    DifferenceFstOptions<Arc, M, MatchComposeFilter<M>> dopts;
    dopts.gc_limit = 0;  // Cache only the last state for fastest copy.
    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
  }
  if (opts.connect) Connect(ofst);
}

}  // namespace fst

#endif  // FST_DIFFERENCE_H_