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