src/include/fst/float-weight.h

// float-weight.h

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Float weight set and associated semiring operation definitions.
//

#ifndef FST_LIB_FLOAT_WEIGHT_H__
#define FST_LIB_FLOAT_WEIGHT_H__

#include <limits>
#include <climits>
#include <sstream>
#include <string>

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


namespace fst {

// numeric limits class
template <class T>
class FloatLimits {
 public:
  static const T kPosInfinity;
  static const T kNegInfinity;
  static const T kNumberBad;
};

template <class T>
const T FloatLimits<T>::kPosInfinity = numeric_limits<T>::infinity();

template <class T>
const T FloatLimits<T>::kNegInfinity = -FloatLimits<T>::kPosInfinity;

template <class T>
const T FloatLimits<T>::kNumberBad = numeric_limits<T>::quiet_NaN();

// weight class to be templated on floating-points types
template <class T = float>
class FloatWeightTpl {
 public:
  FloatWeightTpl() {}

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

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

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

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

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

  size_t Hash() const {
    union {
      T f;
      size_t s;
    } u;
    u.s = 0;
    u.f = value_;
    return u.s;
  }

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

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

  inline static string GetPrecisionString() {
    int64 size = sizeof(T);
    if (size == sizeof(float)) return "";
    size *= CHAR_BIT;

    string result;
    Int64ToStr(size, &result);
    return result;
  }

 private:
  T value_;
};

// Single-precision float weight
typedef FloatWeightTpl<float> FloatWeight;

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;
}

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

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

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

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

inline bool operator!=(const FloatWeightTpl<float> &w1,
                       const FloatWeightTpl<float> &w2) {
  return operator!=<float>(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 ostream &operator<<(ostream &strm, const FloatWeightTpl<T> &w) {
  if (w.Value() == FloatLimits<T>::kPosInfinity)
    return strm << "Infinity";
  else if (w.Value() == FloatLimits<T>::kNegInfinity)
    return strm << "-Infinity";
  else if (w.Value() != w.Value())   // Fails for NaN
    return strm << "BadNumber";
  else
    return strm << w.Value();
}

template <class T>
inline istream &operator>>(istream &strm, FloatWeightTpl<T> &w) {
  string s;
  strm >> s;
  if (s == "Infinity") {
    w = FloatWeightTpl<T>(FloatLimits<T>::kPosInfinity);
  } else if (s == "-Infinity") {
    w = FloatWeightTpl<T>(FloatLimits<T>::kNegInfinity);
  } 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 FloatWeightTpl<T>::Value;

  typedef TropicalWeightTpl<T> ReverseWeight;

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

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

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

  static const TropicalWeightTpl<T> Zero() {
    return TropicalWeightTpl<T>(FloatLimits<T>::kPosInfinity); }

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

  static const TropicalWeightTpl<T> NoWeight() {
    return TropicalWeightTpl<T>(FloatLimits<T>::kNumberBad); }

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

  bool Member() const {
    // First part fails for IEEE NaN
    return Value() == Value() && Value() != FloatLimits<T>::kNegInfinity;
  }

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

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

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

// Single precision tropical weight
typedef TropicalWeightTpl<float> TropicalWeight;

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;
}

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) {
  if (!w1.Member() || !w2.Member())
    return TropicalWeightTpl<T>::NoWeight();
  T f1 = w1.Value(), f2 = w2.Value();
  if (f1 == FloatLimits<T>::kPosInfinity)
    return w1;
  else if (f2 == FloatLimits<T>::kPosInfinity)
    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) {
  if (!w1.Member() || !w2.Member())
    return TropicalWeightTpl<T>::NoWeight();
  T f1 = w1.Value(), f2 = w2.Value();
  if (f2 == FloatLimits<T>::kPosInfinity)
    return FloatLimits<T>::kNumberBad;
  else if (f1 == FloatLimits<T>::kPosInfinity)
    return FloatLimits<T>::kPosInfinity;
  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);
}


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

  typedef LogWeightTpl ReverseWeight;

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

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

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

  static const LogWeightTpl<T> Zero() {
    return LogWeightTpl<T>(FloatLimits<T>::kPosInfinity);
  }

  static const LogWeightTpl<T> One() {
    return LogWeightTpl<T>(0.0F);
  }

  static const LogWeightTpl<T> NoWeight() {
    return LogWeightTpl<T>(FloatLimits<T>::kNumberBad); }

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

  bool Member() const {
    // First part fails for IEEE NaN
    return Value() == Value() && Value() != FloatLimits<T>::kNegInfinity;
  }

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

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

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

// Single-precision log weight
typedef LogWeightTpl<float> LogWeight;
// Double-precision log weight
typedef LogWeightTpl<double> Log64Weight;

template <class T>
inline T LogExp(T x) { return log(1.0F + exp(-x)); }

template <class T>
inline LogWeightTpl<T> Plus(const LogWeightTpl<T> &w1,
                            const LogWeightTpl<T> &w2) {
  T f1 = w1.Value(), f2 = w2.Value();
  if (f1 == FloatLimits<T>::kPosInfinity)
    return w2;
  else if (f2 == FloatLimits<T>::kPosInfinity)
    return w1;
  else if (f1 > f2)
    return LogWeightTpl<T>(f2 - LogExp(f1 - f2));
  else
    return LogWeightTpl<T>(f1 - LogExp(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) {
  if (!w1.Member() || !w2.Member())
    return LogWeightTpl<T>::NoWeight();
  T f1 = w1.Value(), f2 = w2.Value();
  if (f1 == FloatLimits<T>::kPosInfinity)
    return w1;
  else if (f2 == FloatLimits<T>::kPosInfinity)
    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) {
  if (!w1.Member() || !w2.Member())
    return LogWeightTpl<T>::NoWeight();
  T f1 = w1.Value(), f2 = w2.Value();
  if (f2 == FloatLimits<T>::kPosInfinity)
    return FloatLimits<T>::kNumberBad;
  else if (f1 == FloatLimits<T>::kPosInfinity)
    return FloatLimits<T>::kPosInfinity;
  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);
}

// MinMax semiring: (min, max, inf, -inf)
template <class T>
class MinMaxWeightTpl : public FloatWeightTpl<T> {
 public:
  using FloatWeightTpl<T>::Value;

  typedef MinMaxWeightTpl<T> ReverseWeight;

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

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

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

  static const MinMaxWeightTpl<T> Zero() {
    return MinMaxWeightTpl<T>(FloatLimits<T>::kPosInfinity);
  }

  static const MinMaxWeightTpl<T> One() {
    return MinMaxWeightTpl<T>(FloatLimits<T>::kNegInfinity);
  }

  static const MinMaxWeightTpl<T> NoWeight() {
    return MinMaxWeightTpl<T>(FloatLimits<T>::kNumberBad); }

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

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

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

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

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

// Single-precision min-max weight
typedef MinMaxWeightTpl<float> MinMaxWeight;

// 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>::kNumberBad;
}

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);
}

//
// WEIGHT CONVERTER SPECIALIZATIONS.
//

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

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

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

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

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

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

}  // namespace fst

#endif  // FST_LIB_FLOAT_WEIGHT_H__