marci@1097: // -*- c++ -*-
marci@1097: #ifndef LEMON_EXPRESSION_H
marci@1097: #define LEMON_EXPRESSION_H
marci@1097: 
marci@1097: #include <iostream>
marci@1097: #include <map>
marci@1144: #include <limits>
marci@1097: 
marci@1097: namespace lemon {
marci@1097: 
marci@1097:   /*! \brief Linear expression
marci@1097: 
marci@1097:     \c Expr<_Col,_Value> implements a class of linear expressions with the 
marci@1097:     operations of addition and multiplication with scalar. 
marci@1097: 
marci@1097:     \author Marton Makai
marci@1097:    */
marci@1097:   template <typename _Col, typename _Value>
marci@1097:   class Expr;
marci@1097: 
marci@1097:   template <typename _Col, typename _Value>
marci@1097:   class Expr {
marci@1099: //  protected:
marci@1099:   public:
marci@1097:     typedef 
marci@1097:     typename std::map<_Col, _Value> Data; 
marci@1097:     Data data;
marci@1097:   public:
marci@1099:     void simplify() {
marci@1099:       for (typename Data::iterator i=data.begin(); 
marci@1099: 	   i!=data.end(); ++i) {
marci@1099: 	if ((*i).second==0) data.erase(i);
marci@1099:       }
marci@1099:     }
marci@1097:     Expr() { }
marci@1097:     Expr(_Col _col) { 
marci@1097:       data.insert(std::make_pair(_col, 1));
marci@1097:     }
marci@1097:     Expr& operator*=(_Value _value) {
marci@1097:       for (typename Data::iterator i=data.begin(); 
marci@1097: 	   i!=data.end(); ++i) {
marci@1097: 	(*i).second *= _value;
marci@1097:       }
marci@1099:       simplify();
marci@1097:       return *this;
marci@1097:     }
marci@1097:     Expr& operator+=(const Expr<_Col, _Value>& expr) {
marci@1097:       for (typename Data::const_iterator j=expr.data.begin(); 
marci@1097: 	   j!=expr.data.end(); ++j) {
marci@1097: 	typename Data::iterator i=data.find((*j).first);
marci@1097: 	if (i==data.end()) {
marci@1097: 	  data.insert(std::make_pair((*j).first, (*j).second));
marci@1097: 	} else {
marci@1097: 	  (*i).second+=(*j).second;
marci@1097: 	}
marci@1097:       }
marci@1099:       simplify();
marci@1099:       return *this;
marci@1099:     }
marci@1099:     Expr& operator-=(const Expr<_Col, _Value>& expr) {
marci@1099:       for (typename Data::const_iterator j=expr.data.begin(); 
marci@1099: 	   j!=expr.data.end(); ++j) {
marci@1099: 	typename Data::iterator i=data.find((*j).first);
marci@1099: 	if (i==data.end()) {
marci@1099: 	  data.insert(std::make_pair((*j).first, -(*j).second));
marci@1099: 	} else {
marci@1099: 	  (*i).second+=-(*j).second;
marci@1099: 	}
marci@1099:       }
marci@1099:       simplify();
marci@1097:       return *this;
marci@1097:     }
marci@1097:     template <typename _C, typename _V> 
marci@1097:     friend std::ostream& operator<<(std::ostream& os, 
marci@1097: 				    const Expr<_C, _V>& expr);
marci@1097:   };
marci@1097: 
marci@1097:   template <typename _Col, typename _Value>
marci@1097:   Expr<_Col, _Value> operator*(_Value _value, _Col _col) {
marci@1097:     Expr<_Col, _Value> tmp(_col);
marci@1097:     tmp*=_value;
marci@1099:     tmp.simplify();
marci@1097:     return tmp;
marci@1097:   }
marci@1097: 
marci@1097:   template <typename _Col, typename _Value>
marci@1097:   Expr<_Col, _Value> operator*(_Value _value, 
marci@1097: 			       const Expr<_Col, _Value>& expr) {
marci@1097:     Expr<_Col, _Value> tmp(expr);
marci@1097:     tmp*=_value;
marci@1099:     tmp.simplify();
marci@1097:     return tmp;
marci@1097:   }
marci@1097: 
marci@1097:   template <typename _Col, typename _Value>
marci@1097:   Expr<_Col, _Value> operator+(const Expr<_Col, _Value>& expr1, 
marci@1097: 			       const Expr<_Col, _Value>& expr2) {
marci@1097:     Expr<_Col, _Value> tmp(expr1);
marci@1097:     tmp+=expr2;
marci@1099:     tmp.simplify();
marci@1099:     return tmp;
marci@1099:   }
marci@1099: 
marci@1099:   template <typename _Col, typename _Value>
marci@1099:   Expr<_Col, _Value> operator-(const Expr<_Col, _Value>& expr1, 
marci@1099: 			       const Expr<_Col, _Value>& expr2) {
marci@1099:     Expr<_Col, _Value> tmp(expr1);
marci@1099:     tmp-=expr2;
marci@1099:     tmp.simplify();
marci@1097:     return tmp;
marci@1097:   }
marci@1097: 
marci@1097:   template <typename _Col, typename _Value>
marci@1097:   std::ostream& operator<<(std::ostream& os, 
marci@1097: 			   const Expr<_Col, _Value>& expr) {
marci@1097:     for (typename Expr<_Col, _Value>::Data::const_iterator i=
marci@1097: 	   expr.data.begin(); 
marci@1097: 	 i!=expr.data.end(); ++i) {
marci@1097:       os << (*i).second << "*" << (*i).first << " ";
marci@1097:     }
marci@1097:     return os;
marci@1097:   }
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   class LConstr {
marci@1144:     //  protected:
marci@1144:   public:
marci@1144:     Expr<_Col, _Value> expr;
marci@1144:     _Value lo;
marci@1144:   public:
marci@1144:     LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) : 
marci@1144:       expr(_expr), lo(_lo) { }
marci@1144:   };
marci@1144:   
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   LConstr<_Col, _Value> 
marci@1144:   operator<=(_Value lo, const Expr<_Col, _Value>& expr) {
marci@1144:     return LConstr<_Col, _Value>(expr, lo);
marci@1144:   }
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   class UConstr {
marci@1144:     //  protected:
marci@1144:   public:
marci@1144:     Expr<_Col, _Value> expr;
marci@1144:     _Value up;
marci@1144:   public:
marci@1144:     UConstr(const Expr<_Col, _Value>& _expr, _Value _up) : 
marci@1144:       expr(_expr), up(_up) { }
marci@1144:   };
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   UConstr<_Col, _Value> 
marci@1144:   operator<=(const Expr<_Col, _Value>& expr, _Value up) {
marci@1144:     return UConstr<_Col, _Value>(expr, up);
marci@1144:   }
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   class Constr {
marci@1144:     //  protected:
marci@1144:   public:
marci@1144:     Expr<_Col, _Value> expr;
marci@1144:     _Value lo, up;
marci@1144:   public:
marci@1144:     Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) : 
marci@1144:       expr(_expr), lo(_lo), up(_up) { }
marci@1144:     Constr(const LConstr<_Col, _Value>& _lconstr) : 
marci@1144:       expr(_lconstr.expr), 
marci@1144:       lo(_lconstr.lo), 
marci@1144:       up(std::numeric_limits<_Value>::infinity()) { }
marci@1144:     Constr(const UConstr<_Col, _Value>& _uconstr) : 
marci@1144:       expr(_uconstr.expr), 
marci@1144:       lo(-std::numeric_limits<_Value>::infinity()), 
marci@1144:       up(_uconstr.up) { }
marci@1144:   };
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   Constr<_Col, _Value> 
marci@1144:   operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) {
marci@1144:     return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up);
marci@1144:   }
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   Constr<_Col, _Value> 
marci@1144:   operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) {
marci@1144:     return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up);
marci@1144:   }
marci@1144: 
marci@1144:   template <typename _Col, typename _Value>
marci@1144:   Constr<_Col, _Value> 
marci@1144:   operator==(const Expr<_Col, _Value>& expr, _Value value) {
marci@1144:     return Constr<_Col, _Value>(expr, value, value);
marci@1144:   }
marci@1097:   
marci@1097: } //namespace lemon
marci@1097: 
marci@1097: #endif //LEMON_EXPRESSION_H