// -*- 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