// See www.openfst.org for extensive documentation on this weighted
// finite-state transducer library.
//
// General weight set and associated semiring operation definitions.

#ifndef FST_WEIGHT_H_
#define FST_WEIGHT_H_

#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <type_traits>
#include <utility>

#include <fst/compat.h>
#include <fst/log.h>

#include <fst/util.h>


DECLARE_string(fst_weight_parentheses);
DECLARE_string(fst_weight_separator);

namespace fst {

// A semiring is specified by two binary operations Plus and Times and two
// designated elements Zero and One with the following properties:
//
//   Plus: associative, commutative, and has Zero as its identity.
//
//   Times: associative and has identity One, distributes w.r.t. Plus, and
//     has Zero as an annihilator:
//          Times(Zero(), a) == Times(a, Zero()) = Zero().
//
// A left semiring distributes on the left; a right semiring is similarly
// defined.
//
// A Weight class must have binary functions Plus and Times and static member
// functions Zero() and One() and these must form (at least) a left or right
// semiring.
//
// In addition, the following should be defined for a Weight:
//
//   Member: predicate on set membership.
//
//   NoWeight: static member function that returns an element that is
//      not a set member; used to signal an error.
//
//   >>: reads textual representation of a weight.
//
//   <<: prints textual representation of a weight.
//
//   Read(istream &istrm): reads binary representation of a weight.
//
//   Write(ostream &ostrm): writes binary representation of a weight.
//
//   Hash: maps weight to size_t.
//
//   ApproxEqual: approximate equality (for inexact weights)
//
//   Quantize: quantizes w.r.t delta (for inexact weights)
//
//   Divide: for all a, b, c s.t. Times(a, b) == c
//
//     --> b' = Divide(c, a, DIVIDE_LEFT) if a left semiring, b'.Member()
//      and Times(a, b') == c
//     --> a' = Divide(c, b, DIVIDE_RIGHT) if a right semiring, a'.Member()
//      and Times(a', b) == c
//     --> b' = Divide(c, a) = Divide(c, a, DIVIDE_ANY) =
//      Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a
//      commutative semiring, b'.Member() and Times(a, b') = Times(b', a) = c
//
//   ReverseWeight: the type of the corresponding reverse weight.
//
//     Typically the same type as Weight for a (both left and right) semiring.
//     For the left string semiring, it is the right string semiring.
//
//   Reverse: a mapping from Weight to ReverseWeight s.t.
//
//     --> Reverse(Reverse(a)) = a
//     --> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
//     --> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
//     Typically the identity mapping in a (both left and right) semiring.
//     In the left string semiring, it maps to the reverse string in the right
//     string semiring.
//
//   Properties: specifies additional properties that hold:
//      LeftSemiring: indicates weights form a left semiring.
//      RightSemiring: indicates weights form a right semiring.
//      Commutative: for all a,b: Times(a,b) == Times(b,a)
//      Idempotent: for all a: Plus(a, a) == a.
//      Path: for all a, b: Plus(a, b) == a or Plus(a, b) == b.

// CONSTANT DEFINITIONS

// A representable float near .001.
constexpr float kDelta = 1.0F / 1024.0F;

// For all a, b, c: Times(c, Plus(a, b)) = Plus(Times(c, a), Times(c, b)).
constexpr uint64 kLeftSemiring = 0x0000000000000001ULL;

// For all a, b, c: Times(Plus(a, b), c) = Plus(Times(a, c), Times(b, c)).
constexpr uint64 kRightSemiring = 0x0000000000000002ULL;

constexpr uint64 kSemiring = kLeftSemiring | kRightSemiring;

// For all a, b: Times(a, b) = Times(b, a).
constexpr uint64 kCommutative = 0x0000000000000004ULL;

// For all a: Plus(a, a) = a.
constexpr uint64 kIdempotent = 0x0000000000000008ULL;

// For all a, b: Plus(a, b) = a or Plus(a, b) = b.
constexpr uint64 kPath = 0x0000000000000010ULL;

// For random weight generation: default number of distinct weights.
// This is also used for a few other weight generation defaults.
constexpr size_t kNumRandomWeights = 5;

// Weight property boolean constants needed for SFINAE.

template <class W>
using IsIdempotent = std::integral_constant<bool,
    (W::Properties() & kIdempotent) != 0>;

template <class W>
using IsPath = std::integral_constant<bool, (W::Properties() & kPath) != 0>;

// Determines direction of division.
enum DivideType {
  DIVIDE_LEFT,   // left division
  DIVIDE_RIGHT,  // right division
  DIVIDE_ANY
};  // division in a commutative semiring

// NATURAL ORDER
//
// By definition:
//
//                 a <= b iff a + b = a
//
// The natural order is a negative partial order iff the semiring is
// idempotent. It is trivially monotonic for plus. It is left
// (resp. right) monotonic for times iff the semiring is left
// (resp. right) distributive. It is a total order iff the semiring
// has the path property.
//
// For more information, see:
//
// Mohri, M. 2002. Semiring framework and algorithms for shortest-distance
// problems, Journal of Automata, Languages and
// Combinatorics 7(3): 321-350, 2002.
//
// We define the strict version of this order below.

// Declares the template with a second parameter determining whether or not it
// can actually be constructed.
template <class W, class IdempotentType = void>
class NaturalLess;

// Variant for idempotent weights.
template <class W>
class NaturalLess<W, typename std::enable_if<IsIdempotent<W>::value>::type> {
 public:
  using Weight = W;

  NaturalLess() {}

  bool operator()(const Weight &w1, const Weight &w2) const {
    return w1 != w2 && Plus(w1, w2) == w1;
  }
};

// Non-constructible variant for non-idempotent weights.
template <class W>
class NaturalLess<W, typename std::enable_if<!IsIdempotent<W>::value>::type> {
 public:
  using Weight = W;

  // TODO(kbg): Trace down anywhere this is being instantiated, then add a
  // static_assert to prevent this from being instantiated.
  NaturalLess() {
    FSTERROR() << "NaturalLess: Weight type is not idempotent: " << W::Type();
  }

  bool operator()(const Weight &, const Weight &) const { return false; }
};

// Power is the iterated product for arbitrary semirings such that Power(w, 0)
// is One() for the semiring, and Power(w, n) = Times(Power(w, n - 1), w).
template <class Weight>
Weight Power(const Weight &weight, size_t n) {
  auto result = Weight::One();
  for (size_t i = 0; i < n; ++i) result = Times(result, weight);
  return result;
}

// Simple default adder class. Specializations might be more complex.
template <class Weight>
class Adder {
 public:
  explicit Adder(Weight w = Weight::Zero()) : sum_(w) { }

  Weight Add(const Weight &w) {
    sum_ = Plus(sum_, w);
    return sum_;
  }

  Weight Sum() { return sum_; }

  void Reset(Weight w = Weight::Zero()) { sum_ = w; }

 private:
  Weight sum_;
};

// General weight converter: raises error.
template <class W1, class W2>
struct WeightConvert {
  W2 operator()(W1 w1) const {
    FSTERROR() << "WeightConvert: Can't convert weight from \"" << W1::Type()
               << "\" to \"" << W2::Type();
    return W2::NoWeight();
  }
};

// Specialized weight converter to self.
template <class W>
struct WeightConvert<W, W> {
  W operator()(W weight) const { return weight; }
};

// General random weight generator: raises error.
template <class W>
struct WeightGenerate {
  W operator()() const {
    FSTERROR() << "WeightGenerate: No random generator for " << W::Type();
    return W::NoWeight();
  }
};

namespace internal {

class CompositeWeightIO {
 public:
  CompositeWeightIO();
  CompositeWeightIO(char separator, std::pair<char, char> parentheses);

  std::pair<char, char> parentheses() const {
    return {open_paren_, close_paren_};
  }
  char separator() const { return separator_; }

  bool error() const { return error_; }

 protected:
  const char separator_;
  const char open_paren_;
  const char close_paren_;

 private:
  bool error_;
};

}  // namespace internal

// Helper class for writing textual composite weights.
class CompositeWeightWriter : public internal::CompositeWeightIO {
 public:
  // Uses configuration from flags (FLAGS_fst_weight_separator,
  // FLAGS_fst_weight_parentheses).
  explicit CompositeWeightWriter(std::ostream &ostrm);

  // parentheses defines the opening and closing parenthesis characters.
  // Set parentheses = {0, 0} to disable writing parenthesis.
  CompositeWeightWriter(std::ostream &ostrm, char separator,
                        std::pair<char, char> parentheses);

  CompositeWeightWriter(const CompositeWeightWriter &) = delete;
  CompositeWeightWriter &operator=(const CompositeWeightWriter &) = delete;

  // Writes open parenthesis to a stream if option selected.
  void WriteBegin();

  // Writes element to a stream.
  template <class T>
  void WriteElement(const T &comp) {
    if (i_++ > 0) ostrm_ << separator_;
    ostrm_ << comp;
  }

  // Writes close parenthesis to a stream if option selected.
  void WriteEnd();

 private:
  std::ostream &ostrm_;
  int i_ = 0;  // Element position.
};

// Helper class for reading textual composite weights. Elements are separated by
// a separator character. There must be at least one element per textual
// representation.  Parentheses characters should be set if the composite
// weights themselves contain composite weights to ensure proper parsing.
class CompositeWeightReader : public internal::CompositeWeightIO {
 public:
  // Uses configuration from flags (FLAGS_fst_weight_separator,
  // FLAGS_fst_weight_parentheses).
  explicit CompositeWeightReader(std::istream &istrm);

  // parentheses defines the opening and closing parenthesis characters.
  // Set parentheses = {0, 0} to disable reading parenthesis.
  CompositeWeightReader(std::istream &istrm, char separator,
                        std::pair<char, char> parentheses);

  CompositeWeightReader(const CompositeWeightReader &) = delete;
  CompositeWeightReader &operator=(const CompositeWeightReader &) = delete;

  // Reads open parenthesis from a stream if option selected.
  void ReadBegin();

  // Reads element from a stream. The second argument, when true, indicates that
  // this will be the last element (allowing more forgiving formatting of the
  // last element). Returns false when last element is read.
  template <class T>
  bool ReadElement(T *comp, bool last = false);

  // Finalizes reading.
  void ReadEnd();

 private:
  std::istream &istrm_;  // Input stream.
  int c_ = 0;            // Last character read, or EOF.
  int depth_ = 0;        // Weight parentheses depth.
};

template <class T>
inline bool CompositeWeightReader::ReadElement(T *comp, bool last) {
  string s;
  const bool has_parens = open_paren_ != 0;
  while ((c_ != std::istream::traits_type::eof()) && !std::isspace(c_) &&
         (c_ != separator_ || depth_ > 1 || last) &&
         (c_ != close_paren_ || depth_ != 1)) {
    s += c_;
    // If parentheses encountered before separator, they must be matched.
    if (has_parens && c_ == open_paren_) {
      ++depth_;
    } else if (has_parens && c_ == close_paren_) {
      // Failure on unmatched parentheses.
      if (depth_ == 0) {
        FSTERROR() << "CompositeWeightReader: Unmatched close paren: "
                   << "Is the fst_weight_parentheses flag set correctly?";
        istrm_.clear(std::ios::badbit);
        return false;
      }
      --depth_;
    }
    c_ = istrm_.get();
  }
  if (s.empty()) {
    FSTERROR() << "CompositeWeightReader: Empty element: "
               << "Is the fst_weight_parentheses flag set correctly?";
    istrm_.clear(std::ios::badbit);
    return false;
  }
  std::istringstream istrm(s);
  istrm >> *comp;
  // Skips separator/close parenthesis.
  if (c_ != std::istream::traits_type::eof() && !std::isspace(c_)) {
    c_ = istrm_.get();
  }
  const bool is_eof = c_ == std::istream::traits_type::eof();
  // Clears fail bit if just EOF.
  if (is_eof && !istrm_.bad()) istrm_.clear(std::ios::eofbit);
  return !is_eof && !std::isspace(c_);
}

}  // namespace fst

#endif  // FST_WEIGHT_H_