// -*- c++ -*-

 #ifndef LEMON_EXPRESSION_H

 #define LEMON_EXPRESSION_H

 #include <iostream>

 #include <map>

 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:

     typedef 

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

     Data data;

   public:

     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;

       }

       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;

 	}

       }

       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;

     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;

     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;

     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;

   }

 } //namespace lemon

 #endif //LEMON_EXPRESSION_H