semiring

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@608 ec762483-ff6d-05da-a07a-a48fb63a330f

4 files changed, 353 insertions, 21 deletions

diff --git a/utils/logval.h b/utils/logval.h
index b337cf0e..868146de 100644
--- a/utils/logval.h
+++ b/utils/logval.h
@@ -8,20 +8,32 @@
 #include <cstdlib>
 #include <cmath>
 #include <limits>
+#include "semiring.h"
 
+//TODO: template for supporting negation or not - most uses are for nonnegative "probs" only; probably some 10-20% speedup available
 template <class T>
 class LogVal {
  public:
-  LogVal() : s_(), v_(-std::numeric_limits<T>::infinity()) {}
+  typedef LogVal<T> Self;
+
+  LogVal() : s_(), v_(LOGVAL_LOG0) {}
   explicit LogVal(double x) : s_(std::signbit(x)), v_(s_ ? std::log(-x) : std::log(x)) {}
+  LogVal(init_minus_1) : s_(true),v_(0) {  }
+  LogVal(init_1) : s_(),v_(0) {  }
+  LogVal(init_0) : s_(),v_(LOGVAL_LOG0) {  }
   LogVal(int x) : s_(x<0), v_(s_ ? std::log(-x) : std::log(x)) {}
   LogVal(unsigned x) : s_(0), v_(std::log(x)) { }
   LogVal(double lnx,bool sign) : s_(sign),v_(lnx) {}
-  static LogVal<T> exp(T lnx) { return LogVal(lnx,false); }
+  LogVal(double lnx,init_lnx) : s_(),v_(lnx) {}
+  static Self exp(T lnx) { return Self(lnx,false); }
+
+  // maybe the below are faster than == 1 and == 0.  i don't know.
+  bool is_1() const { return v_==0&&s_==0; }
+  bool is_0() const { return v_==LOGVAL_LOG0; }
 
-  static LogVal<T> One() { return LogVal(1); }
-  static LogVal<T> Zero() { return LogVal(); }
-  static LogVal<T> e() { return LogVal(1,false); }
+  static Self One() { return Self(1); }
+  static Self Zero() { return Self(); }
+  static Self e() { return Self(1,false); }
   void logeq(const T& v) { s_ = false; v_ = v; }
 
   std::size_t hash_impl() const {
@@ -29,8 +41,21 @@ class LogVal {
     return hash_value(v_)+s_;
   }
 
-  LogVal& operator+=(const LogVal& a) {
-    if (a.v_ == -std::numeric_limits<T>::infinity()) return *this;
+  // just like std::signbit, negative means true.  weird, i know
+  bool signbit() const {
+    return s_;
+  }
+  friend inline bool signbit(Self const& x) { return x.signbit(); }
+
+  Self& besteq(const Self& a) {
+    assert(!a.s_ && !s_);
+    if (a.v_ < v_)
+      v_=a.v_;
+    return *this;
+  }
+
+  Self& operator+=(const Self& a) {
+    if (a.is_0()) return *this;
     if (a.s_ == s_) {
       if (a.v_ < v_) {
         v_ = v_ + log1p(std::exp(a.v_ - v_));
@@ -48,31 +73,31 @@ class LogVal {
     return *this;
   }
 
-  LogVal& operator*=(const LogVal& a) {
+  Self& operator*=(const Self& a) {
     s_ = (s_ != a.s_);
     v_ += a.v_;
     return *this;
   }
 
-  LogVal& operator/=(const LogVal& a) {
+  Self& operator/=(const Self& a) {
     s_ = (s_ != a.s_);
     v_ -= a.v_;
     return *this;
   }
 
-  LogVal& operator-=(const LogVal& a) {
-    LogVal b = a;
-    b.invert();
+  Self& operator-=(const Self& a) {
+    Self b = a;
+    b.negate();
     return *this += b;
   }
 
-  // LogVal(fabs(log(x)),x.s_)
-  friend LogVal abslog(LogVal x) {
+  // Self(fabs(log(x)),x.s_)
+  friend Self abslog(Self x) {
     if (x.v_<0) x.v_=-x.v_;
     return x;
   }
 
-  LogVal& poweq(const T& power) {
+  Self& poweq(const T& power) {
 #if LOGVAL_CHECK_NEG
     if (s_) {
       std::cerr << "poweq(T) not implemented when s_ is true\n";
@@ -83,26 +108,50 @@ class LogVal {
     return *this;
   }
 
-  void invert() { s_ = !s_; }
+  //remember, s_ means negative.
+  inline bool lt(Self const& o) const {
+    return s_ ? (!o.s_ || o.v_<v_) : (o.s_ || v_<o.v_);
+  }
+  inline bool gt(Self const& o) const {
+    return s_ ? (o.s_ && v_<o.v_) : (!o.s_ && o.v_<v_);
+  }
 
-  LogVal pow(const T& power) const {
-    LogVal res = *this;
+  Self operator-() const {
+    return Self(v_,-s_);
+  }
+  void negate() { s_ = !s_; }
+
+  Self inverse() const { return Self(-v_,s_); }
+
+  Self pow(const T& power) const {
+    Self res = *this;
     res.poweq(power);
     return res;
   }
 
-  LogVal root(const T& root) const {
+  Self root(const T& root) const {
     return pow(1/root);
   }
 
   operator T() const {
     if (s_) return -std::exp(v_); else return std::exp(v_);
   }
+  T as_float() const {
+    if (s_) return -std::exp(v_); else return std::exp(v_);
+  }
 
   bool s_;
   T v_;
 };
 
+template <class T>
+struct semiring_traits<LogVal<T> > : default_semiring_traits<LogVal<T> > {
+  static const bool has_logplus=true;
+  static const bool has_besteq=true;
+  static const bool has_subtract=true;
+  static const bool has_negative=true;
+};
+
 // copy elision - as opposed to explicit copy of LogVal<T> const& o1, we should be able to construct Logval r=a+(b+c) as a single result in place in r.  todo: return std::move(o1) - C++0x
 template<class T>
 LogVal<T> operator+(LogVal<T> o1, const LogVal<T>& o2) {
diff --git a/utils/logval_test.cc b/utils/logval_test.cc
index 1a23177d..4aa452f2 100644
--- a/utils/logval_test.cc
+++ b/utils/logval_test.cc
@@ -26,13 +26,19 @@ TEST_F(LogValTest,Order) {
   EXPECT_FALSE(a < a);
 }
 
-TEST_F(LogValTest,Invert) {
+TEST_F(LogValTest,Negate) {
   LogVal<double> x(-2.4);
   LogVal<double> y(2.4);
-  y.invert();
+  y.negate();
   EXPECT_FLOAT_EQ(x,y);
 }
 
+TEST_F(LogValTest,Inverse) {
+  LogVal<double> x(1/2.4);
+  LogVal<double> y(2.4);
+  EXPECT_FLOAT_EQ(x,y.inverse());
+}
+
 TEST_F(LogValTest,Minus) {
   LogVal<double> x(12);
   LogVal<double> y(2);
diff --git a/utils/max_plus.h b/utils/max_plus.h
new file mode 100755
index 00000000..5136b881
--- /dev/null
+++ b/utils/max_plus.h
@@ -0,0 +1,203 @@
+#ifndef MAX_PLUS_H_
+#define MAX_PLUS_H_
+
+#include
+// max-plus algebra.  ordering a > b really means that (i.e. default a<b sorting will do worst (closest to 0) first.  so get used to passing predicates like std::greater<MaxPlus<T> > around
+// x+y := max{x,y}
+// x*y := x+y
+// 0 := -inf
+// 1 := 0
+// additive inverse does not, but mult. does. (inverse()) and x/y := x-y = x+y.inverse()
+//WARNING: default order is reversed, on purpose, i.e. a<b means a "better than" b, i.e. log(p_a)>log(p_b).  sorry.  defaults in libs are to order ascending, but we want best first.
+
+#include <boost/functional/hash.hpp>
+#include <iostream>
+#include <cstdlib>
+#include <cmath>
+#include <limits>
+#include "semiring.h"
+#define TROPICAL_DEBUG(x)
+#undef LOGVAL_LOG0
+#define LOGVAL_LOG0 -std::numeric_limits<T>::infinity()
+
+template <class T>
+class MaxPlus {
+ public:
+  typedef MaxPlus<T> Self;
+  MaxPlus() : v_(LOGVAL_LOG0) {}
+  explicit MaxPlus(double x) : v_(std::log(x)) {}
+  MaxPlus(init_1) : v_(0) {  }
+  MaxPlus(init_0) : v_(LOGVAL_LOG0) {  }
+  MaxPlus(int x) : v_(std::log(x)) {}
+  MaxPlus(unsigned x) : v_(std::log(x)) { }
+  MaxPlus(double lnx,bool sign) : v_(lnx) { TROPICAL_DEBUG(assert(!sign)); }
+  MaxPlus(double lnx,init_lnx) : v_(lnx) {}
+  static Self exp(T lnx) { return MaxPlus(lnx,false); }
+
+  // maybe the below are faster than == 1 and == 0.  i don't know.
+  bool is_1() const { return v_==0; }
+  bool is_0() const { return v_==LOGVAL_LOG0; }
+
+  static Self One() { return Self(init_1()); }
+  static Self Zero() { return Self(init_0()); }
+  static Self e() { return Self(1,false); }
+  void logeq(const T& v) { v_ = v; }
+  bool signbit() const { return false; }
+
+  std::size_t hash_impl() const {
+    using namespace boost;
+    return hash_value(v_);
+  }
+
+  Self& logpluseq(const Self& a) {
+    if (a.is_0()) return *this;
+    if (a.s_ == s_) {
+      if (a.v_ < v_) {
+        v_ = v_ + log1p(std::exp(a.v_ - v_));
+      } else {
+        v_ = a.v_ + log1p(std::exp(v_ - a.v_));
+      }
+    } else {
+      if (a.v_ < v_) {
+        v_ = v_ + log1p(-std::exp(a.v_ - v_));
+      } else {
+        v_ = a.v_ + log1p(-std::exp(v_ - a.v_));
+        s_ = !s_;
+      }
+    }
+    return *this;
+  }
+
+  Self& besteq(const Self& a) {
+    if (a.v_ < v_)
+      v_=a.v_;
+    return *this;
+  }
+
+  Self& operator+=(const Self& a) {
+    if (a.v_ < v_)
+      v_=a.v_;
+    return *this;
+  }
+
+  Self& operator*=(const Self& a) {
+    v_ += a.v_;
+    return *this;
+  }
+
+  Self& operator/=(const Self& a) {
+    v_ -= a.v_;
+    return *this;
+  }
+
+  // Self(fabs(log(x)),x.s_)
+  friend Self abslog(Self x) {
+    if (x.v_<0) x.v_=-x.v_;
+    return x;
+  }
+
+  Self& poweq(const T& power) {
+    v_ *= power;
+    return *this;
+  }
+
+  Self inverse() const {
+    return Self(-v_,false);
+  }
+
+  Self pow(const T& power) const {
+    Self res = *this;
+    res.poweq(power);
+    return res;
+  }
+
+  Self root(const T& root) const {
+    return pow(1/root);
+  }
+
+// copy elision - as opposed to explicit copy of Self const& o1, we should be able to construct Logval r=a+(b+c) as a single result in place in r.  todo: return std::move(o1) - C++0x
+  friend inline operator+(Self a,Self const& b) {
+    a+=b;
+    return a;
+  }
+  friend inline operator*(Self a,Self const& b) {
+    a*=b;
+    return a;
+  }
+  friend inline operator/(Self a,Self const& b) {
+    a/=b;
+    return a;
+  }
+  friend inline T log(Self const& a) {
+    return a.v_;
+  }
+  friend inline T pow(Self const& a,T const& e) {
+    return a.pow(e);
+  }
+
+  // intentionally not defining an operator < or operator > - because you may want to default (for library convenience) a<b means a better than b (i.e. gt)
+  inline bool lt(Self const& o) const {
+    return v_<o.v_;
+  }
+  inline bool gt(Self const& o) const {
+    return o.v_<v_;
+  }
+  friend inline bool operator==(Self const& lhs, Self const&rhs) {
+    return lhs.v_ == rhs.v_;
+  }
+  friend inline bool operator!=(Self const& lhs, Self const&rhs) {
+    return lhs.v_ != rhs.v_;
+  }
+/*
+  operator T() const {
+    return std::exp(v_);
+  }
+*/
+  T as_float() const {
+    return std::exp(v_);
+  }
+
+  T v_;
+};
+
+template <class T>
+struct semiring_traits<MaxPlus<T> > : default_semiring_traits<MaxPlus<T> > {
+  static const bool has_logplus=true;
+  static const bool has_besteq=true;
+};
+
+
+template <class T>
+
+#if 0
+template <class T>
+bool operator<=(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+  return (lhs.v_ <= rhs.v_);
+}
+
+template <class T>
+bool operator>(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+  return (lhs.v_ > rhs.v_);
+}
+
+template <class T>
+bool operator>=(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+  return (lhs.v_ >= rhs.v_);
+}
+#endif
+
+
+template <class T>
+std::size_t hash_value(const MaxPlus<T>& x) { return x.hash_impl(); }
+
+template <class T>
+bool operator==(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+  return (lhs.v_ == rhs.v_) && (lhs.s_ == rhs.s_);
+}
+
+template <class T>
+bool operator!=(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+  return !(lhs == rhs);
+}
+
+#endif
diff --git a/utils/semiring.h b/utils/semiring.h
new file mode 100755
index 00000000..5007994c
--- /dev/null
+++ b/utils/semiring.h
@@ -0,0 +1,74 @@
+#ifndef SEMIRING_H
+#define SEMIRING_H
+
+struct init_1 {  };
+struct init_0 {  };
+struct init_minus_1 { };
+struct init_lnx {  };
+
+#undef LOGVAL_LOG0
+#define LOGVAL_LOG0 -std::numeric_limits<T>::infinity()
+
+/* if T is a semiring,
+
+   then constructors:
+   T() := T(init_0)
+   T(init_0()) := semiring 0
+   T(init_1()) := semiring 1
+   (copy constructor, equality, assignment also)
+   T(other initializers) - semiring dependent e.g. T(double lnx,bool is_negative); T(double lnx,init_lnx); T(double x) := T(log(fabs(x)),signbit(x))
+
+   optional: T(init_minus_1()) := -1, assuming additive inverse
+
+   if T a,b;
+   then a+b := semiring + - commutative monoid with 0
+   a*b := semiring * with identity 1 - monoid with 1
+   * distributes over +
+   0*a=a*0=0
+
+   also a+= a*=
+
+   optional: commutative multiplication (commutative semiring)
+
+   non-semiring concepts you may also have:
+   order (a<b)
+   logplus(a,b), logpluseq(a,b), T::exp(lnx), log(a)
+   a-b, usually with a-b := a+T(init_minus_1())*b
+   a.inverse() : a*a.inverse() = 1
+   a.left_inverse() : a.left_inverse()*a = 1 (define if not commuatative and it exists)
+   signbit(a) := a<0
+   pow(a,2) := a*a
+   pow(a,2.3)
+*/
+
+template <class T>
+struct default_semiring_traits {
+  static const T One;
+  static const T Zero;
+  static inline bool is_1(T const& x) { return x==One; }
+  static inline bool is_0(T const& x) { return x==Zero; }
+  static const bool commutative=true;
+  static const bool has_inverse=true; // multiplicative, that is
+//  static const bool has_left_inverse=false; // note: not intended to imply that inverse isn't a left_inverse
+  static const bool has_order=false; // we usually don't defined < > <= >= although == != must exist
+  static const bool has_ltgt=true; // but we will probably give a a.lt(b) x.gt(y) which are a<b and x>y resp.
+  static const bool has_subtract=false; // e.g. tropical can't do this
+  static const bool has_logplus=false;
+  static const bool has_pow=true;
+  static const bool has_init_float=true; // implies you can T a; T a.as_float() as well as T(float f)
+  static const bool has_negative=false;
+  static const bool has_ostream=false; // we could provide these but for some reason we usually don't
+  static const bool has_istream=false;
+};
+
+template <class T>
+struct semiring_traits : default_semiring_traits<T> {
+};
+
+
+template <class T>
+const T default_semiring_traits<T>::One=init_1();
+template <class T>
+const T default_semiring_traits<T>::Zero=init_0();
+
+#endif