// -*- c++ -*-

 #ifndef LEMON_EXPRESSION_H

 #define LEMON_EXPRESSION_H

 #include <iostream>

 #include <map>

 #include <limits>

 namespace lemon {

   /*! \brief Linear expression

     \c Expr<_Col,_Value> implements a class of linear expressions with the 

     operations of addition and multiplication with scalar. 

     \author Marton Makai

    */

   template <typename _Col, typename _Value>

   class Expr;

   template <typename _Col, typename _Value>

   class Expr {

 //  protected:

   public:

     typedef 

     typename std::map<_Col, _Value> Data; 

     Data data;

   public:

     void simplify() {

       for (typename Data::iterator i=data.begin(); 

 	   i!=data.end(); ++i) {

 	if ((*i).second==0) data.erase(i);

       }

     }

     Expr() { }

     Expr(_Col _col) { 

       data.insert(std::make_pair(_col, 1));

     }

     Expr& operator*=(_Value _value) {

       for (typename Data::iterator i=data.begin(); 

 	   i!=data.end(); ++i) {

 	(*i).second *= _value;

       }

       simplify();

       return *this;

     }

     Expr& operator+=(const Expr<_Col, _Value>& expr) {

       for (typename Data::const_iterator j=expr.data.begin(); 

 	   j!=expr.data.end(); ++j) {

 	typename Data::iterator i=data.find((*j).first);

 	if (i==data.end()) {

 	  data.insert(std::make_pair((*j).first, (*j).second));

 	} else {

 	  (*i).second+=(*j).second;

 	}

       }

       simplify();

       return *this;

     }

     Expr& operator-=(const Expr<_Col, _Value>& expr) {

       for (typename Data::const_iterator j=expr.data.begin(); 

 	   j!=expr.data.end(); ++j) {

 	typename Data::iterator i=data.find((*j).first);

 	if (i==data.end()) {

 	  data.insert(std::make_pair((*j).first, -(*j).second));

 	} else {

 	  (*i).second+=-(*j).second;

 	}

       }

       simplify();

       return *this;

     }

     template <typename _C, typename _V> 

     friend std::ostream& operator<<(std::ostream& os, 

 				    const Expr<_C, _V>& expr);

   };

   template <typename _Col, typename _Value>

   Expr<_Col, _Value> operator*(_Value _value, _Col _col) {

     Expr<_Col, _Value> tmp(_col);

     tmp*=_value;

     tmp.simplify();

     return tmp;

   }

   template <typename _Col, typename _Value>

   Expr<_Col, _Value> operator*(_Value _value, 

 			       const Expr<_Col, _Value>& expr) {

     Expr<_Col, _Value> tmp(expr);

     tmp*=_value;

     tmp.simplify();

     return tmp;

   }

   template <typename _Col, typename _Value>

   Expr<_Col, _Value> operator+(const Expr<_Col, _Value>& expr1, 

 			       const Expr<_Col, _Value>& expr2) {

     Expr<_Col, _Value> tmp(expr1);

     tmp+=expr2;

     tmp.simplify();

     return tmp;

   }

   template <typename _Col, typename _Value>

   Expr<_Col, _Value> operator-(const Expr<_Col, _Value>& expr1, 

 			       const Expr<_Col, _Value>& expr2) {

     Expr<_Col, _Value> tmp(expr1);

     tmp-=expr2;

     tmp.simplify();

     return tmp;

   }

   template <typename _Col, typename _Value>

   std::ostream& operator<<(std::ostream& os, 

 			   const Expr<_Col, _Value>& expr) {

     for (typename Expr<_Col, _Value>::Data::const_iterator i=

 	   expr.data.begin(); 

 	 i!=expr.data.end(); ++i) {

       os << (*i).second << "*" << (*i).first << " ";

     }

     return os;

   }

   template <typename _Col, typename _Value>

   class LConstr {

     //  protected:

   public:

     Expr<_Col, _Value> expr;

     _Value lo;

   public:

     LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) : 

       expr(_expr), lo(_lo) { }

   };

   template <typename _Col, typename _Value>

   LConstr<_Col, _Value> 

   operator<=(_Value lo, const Expr<_Col, _Value>& expr) {

     return LConstr<_Col, _Value>(expr, lo);

   }

   template <typename _Col, typename _Value>

   class UConstr {

     //  protected:

   public:

     Expr<_Col, _Value> expr;

     _Value up;

   public:

     UConstr(const Expr<_Col, _Value>& _expr, _Value _up) : 

       expr(_expr), up(_up) { }

   };

   template <typename _Col, typename _Value>

   UConstr<_Col, _Value> 

   operator<=(const Expr<_Col, _Value>& expr, _Value up) {

     return UConstr<_Col, _Value>(expr, up);

   }

   template <typename _Col, typename _Value>

   class Constr {

     //  protected:

   public:

     Expr<_Col, _Value> expr;

     _Value lo, up;

   public:

     Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) : 

       expr(_expr), lo(_lo), up(_up) { }

     Constr(const LConstr<_Col, _Value>& _lconstr) : 

       expr(_lconstr.expr), 

       lo(_lconstr.lo), 

       up(std::numeric_limits<_Value>::infinity()) { }

     Constr(const UConstr<_Col, _Value>& _uconstr) : 

       expr(_uconstr.expr), 

       lo(-std::numeric_limits<_Value>::infinity()), 

       up(_uconstr.up) { }

   };

   template <typename _Col, typename _Value>

   Constr<_Col, _Value> 

   operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) {

     return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up);

   }

   template <typename _Col, typename _Value>

   Constr<_Col, _Value> 

   operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) {

     return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up);

   }

   template <typename _Col, typename _Value>

   Constr<_Col, _Value> 

   operator==(const Expr<_Col, _Value>& expr, _Value value) {

     return Constr<_Col, _Value>(expr, value, value);

   }

 } //namespace lemon

 #endif //LEMON_EXPRESSION_H