/* -*- C++ -*-

  * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_LIN_EXPR_H

 #define LEMON_LIN_EXPR_H

 #include<vector>

 #include<map>

 ///\file

 ///\brief Classes to handle linear expressions

 namespace lemon {

   /// Class to handle sparse linear expressions

   template <class _V>

   class SparseLinExpr : public std::map<_V, typename _V::ExprValue>

   {

   public:

     typedef _V Var; 

     typedef typename _V::ExprValue Coeff;

   protected:

     typedef typename std::map<_V, typename _V::ExprValue> Base;

     Coeff const_comp;

   public:

     ///\e

     SparseLinExpr() : Base(), const_comp(0) { }

     ///\e

     SparseLinExpr(const Var &v) : const_comp(0) {

       Base::insert(std::make_pair(v, 1));

     }

     ///\e

     SparseLinExpr(const Coeff &v) : const_comp(v) {}

     ///\e

     void set(const Var &v,const Coeff &c) {

       return Base::insert(std::make_pair(v, c));

     }

 //     Coeff &operator[](const Var &v) { return data[v]; }

 //     const Coeff &operator[](const Var &v) const { return data[v]; }

     ///\e

     Coeff &constComp() { return const_comp; }

     ///\e

     const Coeff &constComp() const { return const_comp; }

     ///Removes the components with zero coefficient.

     void simplify() {

       for (typename Base::iterator i=Base::begin(); i!=Base::end();) {

 	typename Base::iterator j=i;

 	++j;

 	if ((*i).second==0) Base::erase(i);

 	j=i;

       }

     }

     ///\e

     SparseLinExpr &operator+=(const SparseLinExpr &e) {

       for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)

 	(*this)[j->first]+=j->second;

       ///\todo it might be speeded up using "hints"

       const_comp+=e.const_comp;

       return *this;

     }

     ///\e

     SparseLinExpr &operator-=(const SparseLinExpr &e) {

       for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)

 	(*this)[j->first]-=j->second;

       const_comp-=e.const_comp;

       return *this;

     }

     ///\e

     SparseLinExpr &operator*=(const Coeff &c) {

       for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)

 	j->second*=c;

       const_comp*=c;

       return *this;

     }

     ///\e

     SparseLinExpr &operator/=(const Coeff &c) {

       for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)

 	j->second/=c;

       const_comp/=c;

       return *this;

     }

   };

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,

 				const SparseLinExpr<V> &b) {

     SparseLinExpr<V> tmp(a);

     tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,

 				const SparseLinExpr<V> &b) {

     SparseLinExpr<V> tmp(a);

     tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator*(const typename V::ExprValue &c,

 			       const SparseLinExpr<V> &e) {

     SparseLinExpr<V> tmp(e);

     tmp*=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,

 			       const typename V::ExprValue &c) {

     SparseLinExpr<V> tmp(e);

     tmp*=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,

 			       const typename V::ExprValue &c) {

     SparseLinExpr<V> tmp(e);

     tmp/=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator+(const typename V::ExprValue &c,

 			     const SparseLinExpr<V> &e) {

     SparseLinExpr<V> tmp(e);

     tmp.constComp()+=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,

 			     const typename V::ExprValue &c) {

     SparseLinExpr<V> tmp(e);

     tmp.constComp()+=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {

     SparseLinExpr<V> tmp(e);

     tmp[v]+=1;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {

     SparseLinExpr<V> tmp(e);

     tmp[v]+=1;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator-(const typename V::ExprValue &c,

 			     const SparseLinExpr<V> &e) {

     SparseLinExpr<V> tmp(e);

     tmp*=-1;

     tmp.constComp()+=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,

 			     const typename V::ExprValue &c) {

     SparseLinExpr<V> tmp(e);

     tmp.constComp()-=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {

     SparseLinExpr<V> tmp(e);

     tmp*=-1;

     tmp[v]+=1;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {

     SparseLinExpr<V> tmp(e);

     tmp[v]-=1;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator+(const V &v1,const V &v2) {

     SparseLinExpr<V> tmp(v1);

     tmp[v2]+=1;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {

     SparseLinExpr<V> tmp;

     tmp[v]=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {

     SparseLinExpr<V> tmp;

     tmp[v]=c;

     return tmp;

   }

   ///\e

   ///\relates SparseLinExpr

   ///

   template <class V>

   SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {

     SparseLinExpr<V> tmp;

     tmp[v]=1/c;

     return tmp;

   }

 } //namespace lemon

 #endif //LEMON_LIN_EXPR_H