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

#include<lemon/utility.h>

///\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:

    typedef True IsLinExpression;

    ///\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 &v,const typename V::ExprValue &c) {

    SparseLinExpr<V> tmp(v);

    tmp.constComp()=c;

    return tmp;

  }

  ///\e

  ///\relates SparseLinExpr

  ///

  template <class V>

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

    SparseLinExpr<V> tmp(v);

    tmp.constComp()=-c;

    return tmp;

  }

  ///\e

  ///\relates SparseLinExpr

  ///

  template <class V>

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

    SparseLinExpr<V> tmp(v);

    tmp.constComp()=c;

    return tmp;

  }

  ///\e

  ///\relates SparseLinExpr

  ///

  template <class V>

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

    SparseLinExpr<V> tmp(c);

    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;

  }

  //////////////////////////////////////////////////////////////////////

  /// Constraints

  //////////////////////////////////////////////////////////////////////

  template <class E>

  class LinConstr

  {

  public:

    typedef E Expr;

    typedef typename E::Var Var;

    typedef typename E::Coeff Coeff;

    static const Coeff INF;

    static const Coeff NaN;

//     static const Coeff INF=0;

//     static const Coeff NaN=1;

    Expr expr;

    Coeff lb,ub;

    LinConstr() : expr(), lb(NaN), ub(NaN) {}

    LinConstr(Coeff _lb,const Expr &e,Coeff _ub) :

      expr(e), lb(_lb), ub(_ub) {}

    LinConstr(const Expr &e,Coeff _ub) : 

      expr(e), lb(NaN), ub(_ub) {}

    LinConstr(Coeff _lb,const Expr &e) :

      expr(e), lb(_lb), ub(NaN) {}

  };

  template<class E>

  const typename LinConstr<E>::Coeff LinConstr<E>::INF=

    std::numeric_limits<Coeff>::infinity();

  template<class E>

  const typename LinConstr<E>::Coeff LinConstr<E>::NaN=

    std::numeric_limits<Coeff>::quiet_NaN();

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator<=(const E &e,const E &f) 

  {

    return LinConstr<E>(-LinConstr<E>::INF,e-f,0);

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator>=(const E &e,const E &f) 

  {

    return LinConstr<E>(-LinConstr<E>::INF,f-e,0);

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator==(const E &e,const E &f) 

  {

    return LinConstr<E>(0,e-f,0);

  }

  //////////////////////////////

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator<=(const E &e,const typename E::Coeff &n) 

  {

    return LinConstr<E>(e,n);

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator>=(const E &e,const typename E::Coeff &n) 

  {

    return LinConstr<E>(n,e);

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator==(const E &e,const typename E::Coeff &n) 

  {

    return LinConstr<E>(n,e,n);

  }

  //////////////////////////////

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator<=(const typename E::Coeff &n,const E &e) 

  {

    return LinConstr<E>(n,e);

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator>=(const typename E::Coeff &n,const E &e) 

  {

    return LinConstr<E>(e,n);

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator==(const typename E::Coeff &n,const E &e) 

  {

    return LinConstr<E>(n,e,n);

  }

  //////////////////////////////

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator<=(const typename E::Coeff &n,const LinConstr<E> &c) 

  {

    LinConstr<E> tmp(c);

    if(tmp.lb!=tmp.NaN) throw LogicError();

    else tmp.lb=n;

    return tmp;

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator>=(const typename E::Coeff &n,const LinConstr<E> &c) 

  {

    LinConstr<E> tmp(c);

    if(tmp.ub!=tmp.NaN) throw LogicError();

    else tmp.ub=n;

    return tmp;

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator<=(const LinConstr<E> &c,const typename E::Coeff &n) 

  {

    LinConstr<E> tmp(c);

    if(tmp.ub!=tmp.NaN) throw LogicError();

    else tmp.ub=n;

    return tmp;

  }

  template<class E>

  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type

  operator>=(const LinConstr<E> &c,const typename E::Coeff &n) 

  {

    LinConstr<E> tmp(c);

    if(tmp.lb!=tmp.NaN) throw LogicError();

    else tmp.lb=n;

    return tmp;

  }

} //namespace lemon

#endif //LEMON_LIN_EXPR_H