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