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

#ifndef FST_FLOAT_WEIGHT_H_
#define FST_FLOAT_WEIGHT_H_

#include <climits>
#include <cmath>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <limits>
#include <sstream>
#include <string>

#include <fst/util.h>
#include <fst/weight.h>


namespace fst {

// Numeric limits class.
template <class T>
class FloatLimits {
 public:
  static constexpr T PosInfinity() {
    return std::numeric_limits<T>::infinity();
  }

  static constexpr T NegInfinity() { return -PosInfinity(); }

  static constexpr T NumberBad() { return std::numeric_limits<T>::quiet_NaN(); }
};

// Weight class to be templated on floating-points types.
template <class T = float>
class FloatWeightTpl {
 public:
  using ValueType = T;

  FloatWeightTpl() {}

  FloatWeightTpl(T f) : value_(f) {}

  FloatWeightTpl(const FloatWeightTpl<T> &weight) : value_(weight.value_) {}

  FloatWeightTpl<T> &operator=(const FloatWeightTpl<T> &weight) {
    value_ = weight.value_;
    return *this;
  }

  std::istream &Read(std::istream &strm) { return ReadType(strm, &value_); }

  std::ostream &Write(std::ostream &strm) const {
    return WriteType(strm, value_);
  }

  size_t Hash() const {
    size_t hash = 0;
    // Avoid using union, which would be undefined behavior.
    // Use memcpy, similar to bit_cast, but sizes may be different.
    // This should be optimized into a single move instruction by
    // any reasonable compiler.
    std::memcpy(&hash, &value_, std::min(sizeof(hash), sizeof(value_)));
    return hash;
  }

  const T &Value() const { return value_; }

 protected:
  void SetValue(const T &f) { value_ = f; }

  static constexpr const char *GetPrecisionString() {
    return sizeof(T) == 4
               ? ""
               : sizeof(T) == 1
                     ? "8"
                     : sizeof(T) == 2 ? "16"
                                      : sizeof(T) == 8 ? "64" : "unknown";
  }

 private:
  T value_;
};

// Single-precision float weight.
using FloatWeight = FloatWeightTpl<float>;

template <class T>
inline bool operator==(const FloatWeightTpl<T> &w1,
                       const FloatWeightTpl<T> &w2) {
  // Volatile qualifier thwarts over-aggressive compiler optimizations that
  // lead to problems esp. with NaturalLess().
  volatile T v1 = w1.Value();
  volatile T v2 = w2.Value();
  return v1 == v2;
}

// These seemingly unnecessary overloads are actually needed to make
// comparisons like FloatWeightTpl<float> == float compile.  If only the
// templated version exists, the FloatWeightTpl<float>(float) conversion
// won't be found.
inline bool operator==(const FloatWeightTpl<float> &w1,
                       const FloatWeightTpl<float> &w2) {
  return operator==<float>(w1, w2);
}

inline bool operator==(const FloatWeightTpl<double> &w1,
                       const FloatWeightTpl<double> &w2) {
  return operator==<double>(w1, w2);
}

template <class T>
inline bool operator!=(const FloatWeightTpl<T> &w1,
                       const FloatWeightTpl<T> &w2) {
  return !(w1 == w2);
}

inline bool operator!=(const FloatWeightTpl<float> &w1,
                       const FloatWeightTpl<float> &w2) {
  return operator!=<float>(w1, w2);
}

inline bool operator!=(const FloatWeightTpl<double> &w1,
                       const FloatWeightTpl<double> &w2) {
  return operator!=<double>(w1, w2);
}

template <class T>
inline bool ApproxEqual(const FloatWeightTpl<T> &w1,
                        const FloatWeightTpl<T> &w2, float delta = kDelta) {
  return w1.Value() <= w2.Value() + delta && w2.Value() <= w1.Value() + delta;
}

template <class T>
inline std::ostream &operator<<(std::ostream &strm,
                                const FloatWeightTpl<T> &w) {
  if (w.Value() == FloatLimits<T>::PosInfinity()) {
    return strm << "Infinity";
  } else if (w.Value() == FloatLimits<T>::NegInfinity()) {
    return strm << "-Infinity";
  } else if (w.Value() != w.Value()) {  // Fails for IEEE NaN.
    return strm << "BadNumber";
  } else {
    return strm << w.Value();
  }
}

template <class T>
inline std::istream &operator>>(std::istream &strm, FloatWeightTpl<T> &w) {
  string s;
  strm >> s;
  if (s == "Infinity") {
    w = FloatWeightTpl<T>(FloatLimits<T>::PosInfinity());
  } else if (s == "-Infinity") {
    w = FloatWeightTpl<T>(FloatLimits<T>::NegInfinity());
  } else {
    char *p;
    T f = strtod(s.c_str(), &p);
    if (p < s.c_str() + s.size()) {
      strm.clear(std::ios::badbit);
    } else {
      w = FloatWeightTpl<T>(f);
    }
  }
  return strm;
}

// Tropical semiring: (min, +, inf, 0).
template <class T>
class TropicalWeightTpl : public FloatWeightTpl<T> {
 public:
  using typename FloatWeightTpl<T>::ValueType;
  using FloatWeightTpl<T>::Value;
  using ReverseWeight = TropicalWeightTpl<T>;
  using Limits = FloatLimits<T>;

  constexpr TropicalWeightTpl() : FloatWeightTpl<T>() {}

  constexpr TropicalWeightTpl(T f) : FloatWeightTpl<T>(f) {}

  constexpr TropicalWeightTpl(const TropicalWeightTpl<T> &weight)
      : FloatWeightTpl<T>(weight) {}

  static const TropicalWeightTpl<T> &Zero() {
    static const TropicalWeightTpl zero(Limits::PosInfinity());
    return zero;
  }

  static const TropicalWeightTpl<T> &One() {
    static const TropicalWeightTpl one(0.0F);
    return one;
  }

  static const TropicalWeightTpl<T> &NoWeight() {
    static const TropicalWeightTpl no_weight(Limits::NumberBad());
    return no_weight;
  }

  static const string &Type() {
    static const string *const type =
        new string(string("tropical") +
                   FloatWeightTpl<T>::GetPrecisionString());
    return *type;
  }

  bool Member() const {
    // First part fails for IEEE NaN.
    return Value() == Value() && Value() != Limits::NegInfinity();
  }

  TropicalWeightTpl<T> Quantize(float delta = kDelta) const {
    if (!Member() || Value() == Limits::PosInfinity()) {
      return *this;
    } else {
      return TropicalWeightTpl<T>(floor(Value() / delta + 0.5F) * delta);
    }
  }

  TropicalWeightTpl<T> Reverse() const { return *this; }

  static constexpr uint64 Properties() {
    return kLeftSemiring | kRightSemiring | kCommutative | kPath | kIdempotent;
  }
};

// Single precision tropical weight.
using TropicalWeight = TropicalWeightTpl<float>;

template <class T>
inline TropicalWeightTpl<T> Plus(const TropicalWeightTpl<T> &w1,
                                 const TropicalWeightTpl<T> &w2) {
  if (!w1.Member() || !w2.Member()) return TropicalWeightTpl<T>::NoWeight();
  return w1.Value() < w2.Value() ? w1 : w2;
}

// See comment at operator==(FloatWeightTpl<float>, FloatWeightTpl<float>)
// for why these overloads are present.
inline TropicalWeightTpl<float> Plus(const TropicalWeightTpl<float> &w1,
                                     const TropicalWeightTpl<float> &w2) {
  return Plus<float>(w1, w2);
}

inline TropicalWeightTpl<double> Plus(const TropicalWeightTpl<double> &w1,
                                      const TropicalWeightTpl<double> &w2) {
  return Plus<double>(w1, w2);
}

template <class T>
inline TropicalWeightTpl<T> Times(const TropicalWeightTpl<T> &w1,
                                  const TropicalWeightTpl<T> &w2) {
  using Limits = FloatLimits<T>;
  if (!w1.Member() || !w2.Member()) return TropicalWeightTpl<T>::NoWeight();
  const T f1 = w1.Value();
  const T f2 = w2.Value();
  if (f1 == Limits::PosInfinity()) {
    return w1;
  } else if (f2 == Limits::PosInfinity()) {
    return w2;
  } else {
    return TropicalWeightTpl<T>(f1 + f2);
  }
}

inline TropicalWeightTpl<float> Times(const TropicalWeightTpl<float> &w1,
                                      const TropicalWeightTpl<float> &w2) {
  return Times<float>(w1, w2);
}

inline TropicalWeightTpl<double> Times(const TropicalWeightTpl<double> &w1,
                                       const TropicalWeightTpl<double> &w2) {
  return Times<double>(w1, w2);
}

template <class T>
inline TropicalWeightTpl<T> Divide(const TropicalWeightTpl<T> &w1,
                                   const TropicalWeightTpl<T> &w2,
                                   DivideType typ = DIVIDE_ANY) {
  using Limits = FloatLimits<T>;
  if (!w1.Member() || !w2.Member()) return TropicalWeightTpl<T>::NoWeight();
  const T f1 = w1.Value();
  const T f2 = w2.Value();
  if (f2 == Limits::PosInfinity()) {
    return Limits::NumberBad();
  } else if (f1 == Limits::PosInfinity()) {
    return Limits::PosInfinity();
  } else {
    return TropicalWeightTpl<T>(f1 - f2);
  }
}

inline TropicalWeightTpl<float> Divide(const TropicalWeightTpl<float> &w1,
                                       const TropicalWeightTpl<float> &w2,
                                       DivideType typ = DIVIDE_ANY) {
  return Divide<float>(w1, w2, typ);
}

inline TropicalWeightTpl<double> Divide(const TropicalWeightTpl<double> &w1,
                                        const TropicalWeightTpl<double> &w2,
                                        DivideType typ = DIVIDE_ANY) {
  return Divide<double>(w1, w2, typ);
}

template <class T, class V>
inline TropicalWeightTpl<T> Power(const TropicalWeightTpl<T> &weight, V n) {
  if (n == 0) {
    return TropicalWeightTpl<T>::One();
  } else if (weight == TropicalWeightTpl<T>::Zero()) {
    return TropicalWeightTpl<T>::Zero();
  }
  return TropicalWeightTpl<T>(weight.Value() * n);
}

// Specializes the library-wide template to use the above implementation; rules
// of function template instantiation require this be a full instantiation.

template <>
inline TropicalWeightTpl<float> Power<TropicalWeightTpl<float>>(
    const TropicalWeightTpl<float> &weight, size_t n) {
  return Power<float, size_t>(weight, n);
}

template <>
inline TropicalWeightTpl<double> Power<TropicalWeightTpl<double>>(
    const TropicalWeightTpl<double> &weight, size_t n) {
  return Power<double, size_t>(weight, n);
}


// Log semiring: (log(e^-x + e^-y), +, inf, 0).
template <class T>
class LogWeightTpl : public FloatWeightTpl<T> {
 public:
  using typename FloatWeightTpl<T>::ValueType;
  using FloatWeightTpl<T>::Value;
  using ReverseWeight = LogWeightTpl;
  using Limits = FloatLimits<T>;

  constexpr LogWeightTpl() : FloatWeightTpl<T>() {}

  constexpr LogWeightTpl(T f) : FloatWeightTpl<T>(f) {}

  constexpr LogWeightTpl(const LogWeightTpl<T> &weight)
      : FloatWeightTpl<T>(weight) {}

  static const LogWeightTpl &Zero() {
    static const LogWeightTpl zero(Limits::PosInfinity());
    return zero;
  }

  static const LogWeightTpl &One() {
    static const LogWeightTpl one(0.0F);
    return one;
  }

  static const LogWeightTpl &NoWeight() {
    static const LogWeightTpl no_weight(Limits::NumberBad());
    return no_weight;
  }

  static const string &Type() {
    static const string *const type =
        new string(string("log") + FloatWeightTpl<T>::GetPrecisionString());
    return *type;
  }

  bool Member() const {
    // First part fails for IEEE NaN.
    return Value() == Value() && Value() != Limits::NegInfinity();
  }

  LogWeightTpl<T> Quantize(float delta = kDelta) const {
    if (!Member() || Value() == Limits::PosInfinity()) {
      return *this;
    } else {
      return LogWeightTpl<T>(floor(Value() / delta + 0.5F) * delta);
    }
  }

  LogWeightTpl<T> Reverse() const { return *this; }

  static constexpr uint64 Properties() {
    return kLeftSemiring | kRightSemiring | kCommutative;
  }
};

// Single-precision log weight.
using LogWeight = LogWeightTpl<float>;

// Double-precision log weight.
using Log64Weight = LogWeightTpl<double>;

namespace internal {

// -log(e^-x + e^-y) = x - LogPosExp(y - x), assuming x >= 0.0.
inline double LogPosExp(double x) {
  DCHECK(!(x < 0));  // NB: NaN values are allowed.
  return log1p(exp(-x));
}

// -log(e^-x - e^-y) = x - LogNegExp(y - x), assuming x > 0.0.
inline double LogNegExp(double x) {
  DCHECK_GT(x, 0);
  return log1p(-exp(-x));
}

// a +_log b = -log(e^-a + e^-b) = KahanLogSum(a, b, ...).
// Kahan compensated summation provides an error bound that is
// independent of the number of addends. Assumes b >= a;
// c is the compensation.
inline double KahanLogSum(double a, double b, double *c) {
  DCHECK_GE(b, a);
  double y = -LogPosExp(b - a) - *c;
  double t = a + y;
  *c = (t - a) - y;
  return t;
}

// a -_log b = -log(e^-a - e^-b) = KahanLogDiff(a, b, ...).
// Kahan compensated summation provides an error bound that is
// independent of the number of addends. Assumes b > a;
// c is the compensation.
inline double KahanLogDiff(double a, double b, double *c) {
  DCHECK_GT(b, a);
  double y = -LogNegExp(b - a) - *c;
  double t = a + y;
  *c = (t - a) - y;
  return t;
}

}  // namespace internal

template <class T>
inline LogWeightTpl<T> Plus(const LogWeightTpl<T> &w1,
                            const LogWeightTpl<T> &w2) {
  using Limits = FloatLimits<T>;
  const T f1 = w1.Value();
  const T f2 = w2.Value();
  if (f1 == Limits::PosInfinity()) {
    return w2;
  } else if (f2 == Limits::PosInfinity()) {
    return w1;
  } else if (f1 > f2) {
    return LogWeightTpl<T>(f2 - internal::LogPosExp(f1 - f2));
  } else {
    return LogWeightTpl<T>(f1 - internal::LogPosExp(f2 - f1));
  }
}

inline LogWeightTpl<float> Plus(const LogWeightTpl<float> &w1,
                                const LogWeightTpl<float> &w2) {
  return Plus<float>(w1, w2);
}

inline LogWeightTpl<double> Plus(const LogWeightTpl<double> &w1,
                                 const LogWeightTpl<double> &w2) {
  return Plus<double>(w1, w2);
}

template <class T>
inline LogWeightTpl<T> Times(const LogWeightTpl<T> &w1,
                             const LogWeightTpl<T> &w2) {
  using Limits = FloatLimits<T>;
  if (!w1.Member() || !w2.Member()) return LogWeightTpl<T>::NoWeight();
  const T f1 = w1.Value();
  const T f2 = w2.Value();
  if (f1 == Limits::PosInfinity()) {
    return w1;
  } else if (f2 == Limits::PosInfinity()) {
    return w2;
  } else {
    return LogWeightTpl<T>(f1 + f2);
  }
}

inline LogWeightTpl<float> Times(const LogWeightTpl<float> &w1,
                                 const LogWeightTpl<float> &w2) {
  return Times<float>(w1, w2);
}

inline LogWeightTpl<double> Times(const LogWeightTpl<double> &w1,
                                  const LogWeightTpl<double> &w2) {
  return Times<double>(w1, w2);
}

template <class T>
inline LogWeightTpl<T> Divide(const LogWeightTpl<T> &w1,
                              const LogWeightTpl<T> &w2,
                              DivideType typ = DIVIDE_ANY) {
  using Limits = FloatLimits<T>;
  if (!w1.Member() || !w2.Member()) return LogWeightTpl<T>::NoWeight();
  const T f1 = w1.Value();
  const T f2 = w2.Value();
  if (f2 == Limits::PosInfinity()) {
    return Limits::NumberBad();
  } else if (f1 == Limits::PosInfinity()) {
    return Limits::PosInfinity();
  } else {
    return LogWeightTpl<T>(f1 - f2);
  }
}

inline LogWeightTpl<float> Divide(const LogWeightTpl<float> &w1,
                                  const LogWeightTpl<float> &w2,
                                  DivideType typ = DIVIDE_ANY) {
  return Divide<float>(w1, w2, typ);
}

inline LogWeightTpl<double> Divide(const LogWeightTpl<double> &w1,
                                   const LogWeightTpl<double> &w2,
                                   DivideType typ = DIVIDE_ANY) {
  return Divide<double>(w1, w2, typ);
}

template <class T, class V>
inline LogWeightTpl<T> Power(const LogWeightTpl<T> &weight, V n) {
  if (n == 0) {
    return LogWeightTpl<T>::One();
  } else if (weight == LogWeightTpl<T>::Zero()) {
    return LogWeightTpl<T>::Zero();
  }
  return LogWeightTpl<T>(weight.Value() * n);
}

// Specializes the library-wide template to use the above implementation; rules
// of function template instantiation require this be a full instantiation.

template <>
inline LogWeightTpl<float> Power<LogWeightTpl<float>>(
    const LogWeightTpl<float> &weight, size_t n) {
  return Power<float, size_t>(weight, n);
}

template <>
inline LogWeightTpl<double> Power<LogWeightTpl<double>>(
    const LogWeightTpl<double> &weight, size_t n) {
  return Power<double, size_t>(weight, n);
}

// Specialization using the Kahan compensated summation.
template <class T>
class Adder<LogWeightTpl<T>> {
 public:
  using Weight = LogWeightTpl<T>;

  explicit Adder(Weight w = Weight::Zero())
      : sum_(w.Value()),
        c_(0.0) { }

  Weight Add(const Weight &w) {
    using Limits = FloatLimits<T>;
    const T f = w.Value();
    if (f == Limits::PosInfinity()) {
      return Sum();
    } else if (sum_ == Limits::PosInfinity()) {
      sum_ = f;
      c_ = 0.0;
    } else if (f > sum_) {
      sum_ = internal::KahanLogSum(sum_, f, &c_);
    } else {
      sum_ = internal::KahanLogSum(f, sum_, &c_);
    }
    return Sum();
  }

  Weight Sum() { return Weight(sum_); }

  void Reset(Weight w = Weight::Zero()) {
    sum_ = w.Value();
    c_ = 0.0;
  }

 private:
  double sum_;
  double c_;   // Kahan compensation.
};

// MinMax semiring: (min, max, inf, -inf).
template <class T>
class MinMaxWeightTpl : public FloatWeightTpl<T> {
 public:
  using typename FloatWeightTpl<T>::ValueType;
  using FloatWeightTpl<T>::Value;
  using ReverseWeight = MinMaxWeightTpl<T>;
  using Limits = FloatLimits<T>;

  MinMaxWeightTpl() : FloatWeightTpl<T>() {}

  MinMaxWeightTpl(T f) : FloatWeightTpl<T>(f) {}

  MinMaxWeightTpl(const MinMaxWeightTpl<T> &weight)
      : FloatWeightTpl<T>(weight) {}

  static const MinMaxWeightTpl &Zero() {
    static const MinMaxWeightTpl zero(Limits::PosInfinity());
    return zero;
  }

  static const MinMaxWeightTpl &One() {
    static const MinMaxWeightTpl one(Limits::NegInfinity());
    return one;
  }

  static const MinMaxWeightTpl &NoWeight() {
    static const MinMaxWeightTpl no_weight(Limits::NumberBad());
    return no_weight;
  }

  static const string &Type() {
    static const string *const type =
        new string(string("minmax") + FloatWeightTpl<T>::GetPrecisionString());
    return *type;
  }

  // Fails for IEEE NaN.
  bool Member() const { return Value() == Value(); }

  MinMaxWeightTpl<T> Quantize(float delta = kDelta) const {
    // If one of infinities, or a NaN.
    if (!Member() ||
        Value() == Limits::NegInfinity() || Value() == Limits::PosInfinity()) {
      return *this;
    } else {
      return MinMaxWeightTpl<T>(floor(Value() / delta + 0.5F) * delta);
    }
  }

  MinMaxWeightTpl<T> Reverse() const { return *this; }

  static constexpr uint64 Properties() {
    return kLeftSemiring | kRightSemiring | kCommutative | kIdempotent | kPath;
  }
};

// Single-precision min-max weight.
using MinMaxWeight = MinMaxWeightTpl<float>;

// Min.
template <class T>
inline MinMaxWeightTpl<T> Plus(const MinMaxWeightTpl<T> &w1,
                               const MinMaxWeightTpl<T> &w2) {
  if (!w1.Member() || !w2.Member()) return MinMaxWeightTpl<T>::NoWeight();
  return w1.Value() < w2.Value() ? w1 : w2;
}

inline MinMaxWeightTpl<float> Plus(const MinMaxWeightTpl<float> &w1,
                                   const MinMaxWeightTpl<float> &w2) {
  return Plus<float>(w1, w2);
}

inline MinMaxWeightTpl<double> Plus(const MinMaxWeightTpl<double> &w1,
                                    const MinMaxWeightTpl<double> &w2) {
  return Plus<double>(w1, w2);
}

// Max.
template <class T>
inline MinMaxWeightTpl<T> Times(const MinMaxWeightTpl<T> &w1,
                                const MinMaxWeightTpl<T> &w2) {
  if (!w1.Member() || !w2.Member()) return MinMaxWeightTpl<T>::NoWeight();
  return w1.Value() >= w2.Value() ? w1 : w2;
}

inline MinMaxWeightTpl<float> Times(const MinMaxWeightTpl<float> &w1,
                                    const MinMaxWeightTpl<float> &w2) {
  return Times<float>(w1, w2);
}

inline MinMaxWeightTpl<double> Times(const MinMaxWeightTpl<double> &w1,
                                     const MinMaxWeightTpl<double> &w2) {
  return Times<double>(w1, w2);
}

// Defined only for special cases.
template <class T>
inline MinMaxWeightTpl<T> Divide(const MinMaxWeightTpl<T> &w1,
                                 const MinMaxWeightTpl<T> &w2,
                                 DivideType typ = DIVIDE_ANY) {
  if (!w1.Member() || !w2.Member()) return MinMaxWeightTpl<T>::NoWeight();
  // min(w1, x) = w2, w1 >= w2 => min(w1, x) = w2, x = w2.
  return w1.Value() >= w2.Value() ? w1 : FloatLimits<T>::NumberBad();
}

inline MinMaxWeightTpl<float> Divide(const MinMaxWeightTpl<float> &w1,
                                     const MinMaxWeightTpl<float> &w2,
                                     DivideType typ = DIVIDE_ANY) {
  return Divide<float>(w1, w2, typ);
}

inline MinMaxWeightTpl<double> Divide(const MinMaxWeightTpl<double> &w1,
                                      const MinMaxWeightTpl<double> &w2,
                                      DivideType typ = DIVIDE_ANY) {
  return Divide<double>(w1, w2, typ);
}

// Converts to tropical.
template <>
struct WeightConvert<LogWeight, TropicalWeight> {
  TropicalWeight operator()(const LogWeight &w) const { return w.Value(); }
};

template <>
struct WeightConvert<Log64Weight, TropicalWeight> {
  TropicalWeight operator()(const Log64Weight &w) const { return w.Value(); }
};

// Converts to log.
template <>
struct WeightConvert<TropicalWeight, LogWeight> {
  LogWeight operator()(const TropicalWeight &w) const { return w.Value(); }
};

template <>
struct WeightConvert<Log64Weight, LogWeight> {
  LogWeight operator()(const Log64Weight &w) const { return w.Value(); }
};

// Converts to log64.
template <>
struct WeightConvert<TropicalWeight, Log64Weight> {
  Log64Weight operator()(const TropicalWeight &w) const { return w.Value(); }
};

template <>
struct WeightConvert<LogWeight, Log64Weight> {
  Log64Weight operator()(const LogWeight &w) const { return w.Value(); }
};

// This function object returns random integers chosen from [0,
// num_random_weights). The boolean 'allow_zero' determines whether Zero() and
// zero divisors should be returned in the random weight generation. This is
// intended primary for testing.
template <class Weight>
class FloatWeightGenerate {
 public:
  explicit FloatWeightGenerate(
      bool allow_zero = true,
      const size_t num_random_weights = kNumRandomWeights)
      : allow_zero_(allow_zero), num_random_weights_(num_random_weights) {}

  Weight operator()() const {
    const int n = rand() % (num_random_weights_ + allow_zero_);  // NOLINT
    if (allow_zero_ && n == num_random_weights_) return Weight::Zero();
    return Weight(n);
  }

 private:
  // Permits Zero() and zero divisors.
  const bool allow_zero_;
  // Number of alternative random weights.
  const size_t num_random_weights_;
};

template <class T>
class WeightGenerate<TropicalWeightTpl<T>>
    : public FloatWeightGenerate<TropicalWeightTpl<T>> {
 public:
  using Weight = TropicalWeightTpl<T>;
  using Generate = FloatWeightGenerate<Weight>;

  explicit WeightGenerate(bool allow_zero = true,
                          size_t num_random_weights = kNumRandomWeights)
      : Generate(allow_zero, num_random_weights) {}

  Weight operator()() const { return Weight(Generate::operator()()); }
};

template <class T>
class WeightGenerate<LogWeightTpl<T>>
    : public FloatWeightGenerate<LogWeightTpl<T>> {
 public:
  using Weight = LogWeightTpl<T>;
  using Generate = FloatWeightGenerate<Weight>;

  explicit WeightGenerate(bool allow_zero = true,
                          size_t num_random_weights = kNumRandomWeights)
      : Generate(allow_zero, num_random_weights) {}

  Weight operator()() const { return Weight(Generate::operator()()); }
};

// This function object returns random integers chosen from [0,
// num_random_weights). The boolean 'allow_zero' determines whether Zero() and
// zero divisors should be returned in the random weight generation. This is
// intended primary for testing.
template <class T>
class WeightGenerate<MinMaxWeightTpl<T>> {
 public:
  using Weight = MinMaxWeightTpl<T>;

  explicit WeightGenerate(bool allow_zero = true,
                          size_t num_random_weights = kNumRandomWeights)
      : allow_zero_(allow_zero), num_random_weights_(num_random_weights) {}

  Weight operator()() const {
    const int n = (rand() %  // NOLINT
                   (2 * num_random_weights_ + allow_zero_)) -
                  num_random_weights_;
    if (allow_zero_ && n == num_random_weights_) {
      return Weight::Zero();
    } else if (n == -num_random_weights_) {
      return Weight::One();
    } else {
      return Weight(n);
    }
  }

 private:
  // Permits Zero() and zero divisors.
  const bool allow_zero_;
  // Number of alternative random weights.
  const size_t num_random_weights_;
};

}  // namespace fst

#endif  // FST_FLOAT_WEIGHT_H_