semiring

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

1 files changed, 203 insertions, 0 deletions

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