/* -*- C++ -*-

  * src/lemon/lp_base.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_LP_BASE_H

 #define LEMON_LP_BASE_H

 #include<vector>

 #include<map>

 #include<limits>

 #include<math.h>

 #include<lemon/utility.h>

 #include<lemon/error.h>

 #include<lemon/invalid.h>

 //#include"lin_expr.h"

 ///\file

 ///\brief The interface of the LP solver interface.

 namespace lemon {

   ///Internal data structure to convert floating id's to fix one's

   ///\todo This might be implemented to be also usable in other places.

   class _FixId 

   {

     std::vector<int> index;

     std::vector<int> cross;

     int first_free;

   public:

     _FixId() : first_free(-1) {};

     ///Convert a floating id to a fix one

     ///\param n is a floating id

     ///\return the corresponding fix id

     int fixId(int n) {return cross[n];}

     ///Convert a fix id to a floating one

     ///\param n is a fix id

     ///\return the corresponding floating id

     int floatingId(int n) { return index[n];}

     ///Add a new floating id.

     ///\param n is a floating id

     ///\return the fix id of the new value

     ///\todo Multiple additions should also be handled.

     int insert(int n)

     {

       if(n>=int(cross.size())) {

 	cross.resize(n+1);

 	if(first_free==-1) {

 	  cross[n]=index.size();

 	  index.push_back(n);

 	}

 	else {

 	  cross[n]=first_free;

 	  int next=index[first_free];

 	  index[first_free]=n;

 	  first_free=next;

 	}

 	return cross[n];

       }

       ///\todo Create an own exception type.

       else throw LogicError(); //floatingId-s must form a continuous range;

     }

     ///Remove a fix id.

     ///\param n is a fix id

     ///

     void erase(int n) 

     {

       int fl=index[n];

       index[n]=first_free;

       first_free=n;

       for(int i=fl+1;i<int(cross.size());++i) {

 	cross[i-1]=cross[i];

 	index[cross[i]]--;

       }

       cross.pop_back();

     }

     ///An upper bound on the largest fix id.

     ///\todo Do we need this?

     ///

     std::size_t maxFixId() { return cross.size()-1; }

   };

   ///Common base class for LP solvers

   class LpSolverBase {

   public:

     ///\e

     enum SolutionType {

       ///\e

       INFEASIBLE = 0,

       ///\e

       UNBOUNDED = 1,

       ///\e

       OPTIMAL = 2,

       ///\e

       FEASIBLE = 3,

     };

     ///The floating point type used by the solver

     typedef double Value;

     ///The infinity constant

     static const Value INF;

     ///The not a number constant

     static const Value NaN;

     ///Refer to a column of the LP.

     ///This type is used to refer to a column of the LP.

     ///

     ///Its value remains valid and correct even after the addition or erase of

     ///other columns.

     ///

     ///\todo Document what can one do with a Col (INVALID, comparing,

     ///it is similar to Node/Edge)

     class Col {

     protected:

       int id;

       friend class LpSolverBase;

     public:

       typedef Value ExprValue;

       typedef True LpSolverCol;

       Col() {}

       Col(const Invalid&) : id(-1) {}

       bool operator<(Col c) const  {return id<c.id;}

       bool operator==(Col c) const  {return id==c.id;}

       bool operator!=(Col c) const  {return id==c.id;}

     };

     ///Refer to a row of the LP.

     ///This type is used to refer to a row of the LP.

     ///

     ///Its value remains valid and correct even after the addition or erase of

     ///other rows.

     ///

     ///\todo Document what can one do with a Row (INVALID, comparing,

     ///it is similar to Node/Edge)

     class Row {

     protected:

       int id;

       friend class LpSolverBase;

     public:

       typedef Value ExprValue;

       typedef True LpSolverRow;

       Row() {}

       Row(const Invalid&) : id(-1) {}

       typedef True LpSolverRow;

       bool operator<(Row c) const  {return id<c.id;}

       bool operator==(Row c) const  {return id==c.id;}

       bool operator!=(Row c) const  {return id==c.id;} 

    };

     ///Linear expression of variables and a constant component

     ///This data structure strores a linear expression of the variables

     ///(\ref Col "Col"s) and also has a constant component.

     ///

     ///There are several ways to access and modify the contents of this

     ///container.

     ///- Its it fully compatible with \c std::map<Col,double>, so for expamle

     ///if \c e is an Expr and \c v and \c w are of type \ref Col then you can

     ///read and modify the coefficients like

     ///these.

     ///\code

     ///e[v]=5;

     ///e[v]+=12;

     ///e.erase(v);

     ///\endcode

     ///or you can also iterate through its elements.

     ///\code

     ///double s=0;

     ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)

     ///  s+=i->second;

     ///\endcode

     ///(This code computes the sum of all coefficients).

     ///- Numbers (<tt>double</tt>'s)

     ///and variables (\ref Col "Col"s) directly convert to an

     ///\ref Expr and the usual linear operations are defined so  

     ///\code

     ///v+w

     ///2*v-3.12*(v-w/2)+2

     ///v*2.1+(3*v+(v*12+w+6)*3)/2

     ///\endcode

     ///are valid expressions. The usual assignment operations are also defined.

     ///\code

     ///e=v+w;

     ///e+=2*v-3.12*(v-w/2)+2;

     ///e*=3.4;

     ///e/=5;

     ///\endcode

     ///- The constant member can be set and read by \ref constComp()

     ///\code

     ///e.constComp()=12;

     ///double c=e.constComp();

     ///\endcode

     ///

     ///\note that \ref clear() not only sets all coefficients to 0 but also

     ///clears the constant components.

     class Expr : public std::map<Col,Value>

     {

     public:

       typedef LpSolverBase::Col Key; 

       typedef LpSolverBase::Value Value;

     protected:

       typedef std::map<Col,Value> Base;

       Value const_comp;

   public:

       typedef True IsLinExpression;

       ///\e

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

       ///\e

       Expr(const Key &v) : const_comp(0) {

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

       }

       ///\e

       Expr(const Value &v) : const_comp(v) {}

       ///\e

       void set(const Key &v,const Value &c) {

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

       }

       ///\e

       Value &constComp() { return const_comp; }

       ///\e

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

       ///Removes the components with zero coefficient.

       void simplify() {

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

 	  Base::iterator j=i;

 	  ++j;

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

 	  j=i;

 	}

       }

       ///Sets all coefficients and the constant component to 0.

       void clear() {

 	Base::clear();

 	const_comp=0;

       }

       ///\e

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

 	for (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

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

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

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

 	const_comp-=e.const_comp;

 	return *this;

       }

       ///\e

       Expr &operator*=(const Value &c) {

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

 	  j->second*=c;

 	const_comp*=c;

 	return *this;

       }

       ///\e

       Expr &operator/=(const Value &c) {

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

 	  j->second/=c;

 	const_comp/=c;

 	return *this;

       }

     };

     ///Linear constraint

     //typedef LinConstr<Expr> Constr;

     class Constr

     {

     public:

       typedef LpSolverBase::Expr Expr;

       typedef Expr::Key Key;

       typedef Expr::Value Value;

       static const Value INF;

       static const Value NaN;

       //     static const Value INF=0;

       //     static const Value NaN=1;

     protected:

       Expr _expr;

       Value _lb,_ub;

     public:

       ///\e

       Constr() : _expr(), _lb(NaN), _ub(NaN) {}

       ///\e

       Constr(Value lb,const Expr &e,Value ub) :

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

       ///\e

       Constr(const Expr &e,Value ub) : 

 	_expr(e), _lb(NaN), _ub(ub) {}

       ///\e

       Constr(Value lb,const Expr &e) :

 	_expr(e), _lb(lb), _ub(NaN) {}

       ///\e

       Constr(const Expr &e) : 

 	_expr(e), _lb(NaN), _ub(NaN) {}

       ///\e

       void clear() 

       {

 	_expr.clear();

 	_lb=_ub=NaN;

       }

       ///\e

       Expr &expr() { return _expr; }

       ///\e

       const Expr &expr() const { return _expr; }

       ///\e

       Value &lowerBound() { return _lb; }

       ///\e

       const Value &lowerBound() const { return _lb; }

       ///\e

       Value &upperBound() { return _ub; }

       ///\e

       const Value &upperBound() const { return _ub; }

       ///\e

       bool lowerBounded() const { return std::isfinite(_lb); }

       ///\e

       bool upperBounded() const { return std::isfinite(_ub); }

     };

   protected:

     _FixId rows;

     _FixId cols;

     /// \e

     virtual int _addCol() = 0;

     /// \e

     virtual int _addRow() = 0;

     /// \e

     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)

     ///

     virtual void _setRowCoeffs(int i, 

 			       int length,

                                int  const * indices, 

                                Value  const * values ) = 0;

     /// \e

     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)

     ///

     virtual void _setColCoeffs(int i, 

 			       int length,

                                int  const * indices, 

                                Value  const * values ) = 0;

     /// \e

     /// The lower bound of a variable (column) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or -\ref INF.

     virtual void _setColLowerBound(int i, Value value) = 0;

     /// \e

     /// The upper bound of a variable (column) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or \ref INF.

     virtual void _setColUpperBound(int i, Value value) = 0;

     /// \e

     /// The lower bound of a linear expression (row) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or -\ref INF.

     virtual void _setRowLowerBound(int i, Value value) = 0;

     /// \e

     /// The upper bound of a linear expression (row) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or \ref INF.

     virtual void _setRowUpperBound(int i, Value value) = 0;

     /// \e

     virtual void _setObjCoeff(int i, Value obj_coef) = 0;

     ///\e

     ///\bug Wrong interface

     ///

     virtual SolutionType _solve() = 0;

     ///\e

     ///\bug Wrong interface

     ///

     virtual Value _getSolution(int i) = 0;

     ///\e

     ///\bug unimplemented!!!!

     void clearObj() {}

   public:

     ///\e

     virtual ~LpSolverBase() {}

     ///\name Building up and modification of the LP

     ///@{

     ///Add a new empty column (i.e a new variable) to the LP

     Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}

     ///\brief Fill the elements of a container with newly created columns

     ///(i.e a new variables)

     ///

     ///This magic function takes a container as its argument

     ///and fills its elements

     ///with new columns (i.e. variables)

     ///\param t can be

     ///- a standard STL compatible iterable container with

     ///\ref Col as its \c values_type

     ///like

     ///\code

     ///std::vector<LpSolverBase::Col>

     ///std::list<LpSolverBase::Col>

     ///\endcode

     ///- a standard STL compatible iterable container with

     ///\ref Col as its \c mapped_type

     ///like

     ///\code

     ///std::map<AnyType,LpSolverBase::Col>

     ///\endcode

     ///- an iterable lemon \ref concept::WriteMap "write map" like 

     ///\code

     ///ListGraph::NodeMap<LpSolverBase::Col>

     ///ListGraph::EdgeMap<LpSolverBase::Col>

     ///\endcode

     ///\return The number of the created column.

     ///\bug Iterable nodemap hasn't been implemented yet.

 #ifdef DOXYGEN

     template<class T>

     int addColSet(T &t) { return 0;} 

 #else

     template<class T>

     typename enable_if<typename T::value_type::LpSolverCol,int>::type

     addColSet(T &t,dummy<0> = 0) {

       int s=0;

       for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}

       return s;

     }

     template<class T>

     typename enable_if<typename T::value_type::second_type::LpSolverCol,

 		       int>::type

     addColSet(T &t,dummy<1> = 1) { 

       int s=0;

       for(typename T::iterator i=t.begin();i!=t.end();++i) {

 	i->second=addCol();

 	s++;

       }

       return s;

     }

     template<class T>

     typename enable_if<typename T::ValueSet::value_type::LpSolverCol,

 		       int>::type

     addColSet(T &t,dummy<2> = 2) { 

       ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.

       int s=0;

       for(typename T::ValueSet::iterator i=t.valueSet().begin();

 	  i!=t.valueSet().end();

 	  ++i)

 	{

 	  *i=addCol();

 	  s++;

 	}

       return s;

     }

 #endif

     ///Add a new empty row (i.e a new constaint) to the LP

     ///This function adds a new empty row (i.e a new constaint) to the LP.

     ///\return The created row

     Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}

     ///Set a row (i.e a constaint) of the LP

     ///\param r is the row to be modified

     ///\param l is lower bound (-\ref INF means no bound)

     ///\param e is a linear expression (see \ref Expr)

     ///\param u is the upper bound (\ref INF means no bound)

     ///\bug This is a temportary function. The interface will change to

     ///a better one.

     void setRow(Row r, Value l,const Expr &e, Value u) {

       std::vector<int> indices;

       std::vector<Value> values;

       indices.push_back(0);

       values.push_back(0);

       for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)

 	if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!

 	  indices.push_back(cols.floatingId((*i).first.id));

 	  values.push_back((*i).second);

 	}

       _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,

 		    &indices[0],&values[0]);

       _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());

       _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());

     }

     ///Set a row (i.e a constaint) of the LP

     ///\param r is the row to be modified

     ///\param c is a linear expression (see \ref Constr)

     void setRow(Row r, const Constr &c) {

       setRow(r,

 	     c.lowerBounded()?c.lowerBound():-INF,

 	     c.expr(),

 	     c.upperBounded()?c.upperBound():INF);

     }

     ///Add a new row (i.e a new constaint) to the LP

     ///\param l is the lower bound (-\ref INF means no bound)

     ///\param e is a linear expression (see \ref Expr)

     ///\param u is the upper bound (\ref INF means no bound)

     ///\return The created row.

     ///\bug This is a temportary function. The interface will change to

     ///a better one.

     Row addRow(Value l,const Expr &e, Value u) {

       Row r=addRow();

       setRow(r,l,e,u);

       return r;

     }

     ///Add a new row (i.e a new constaint) to the LP

     ///\param c is a linear expression (see \ref Constr)

     ///\return The created row.

     Row addRow(const Constr &c) {

       Row r=addRow();

       setRow(r,c);

       return r;

     }

     /// Set the lower bound of a column (i.e a variable)

     /// The upper bound of a variable (column) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or -\ref INF.

     virtual void setColLowerBound(Col c, Value value) {

       _setColLowerBound(cols.floatingId(c.id),value);

     }

     /// Set the upper bound of a column (i.e a variable)

     /// The upper bound of a variable (column) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or \ref INF.

     virtual void setColUpperBound(Col c, Value value) {

       _setColUpperBound(cols.floatingId(c.id),value);

     };

     /// Set the lower bound of a row (i.e a constraint)

     /// The lower bound of a linear expression (row) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or -\ref INF.

     virtual void setRowLowerBound(Row r, Value value) {

       _setRowLowerBound(rows.floatingId(r.id),value);

     };

     /// Set the upper bound of a row (i.e a constraint)

     /// The upper bound of a linear expression (row) have to be given by an 

     /// extended number of type Value, i.e. a finite number of type 

     /// Value or \ref INF.

     virtual void setRowUpperBound(Row r, Value value) {

       _setRowUpperBound(rows.floatingId(r.id),value);

     };

     ///Set an element of the objective function

     void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };

     ///Set the objective function

     ///\param e is a linear expression of type \ref Expr.

     ///\todo What to do with the constant component?

     void setObj(Expr e) {

       clearObj();

       for (Expr::iterator i=e.begin(); i!=e.end(); ++i)

 	setObjCoeff((*i).first,(*i).second);

     }

     ///@}

     ///\name Solving the LP

     ///@{

     ///\e

     SolutionType solve() { return _solve(); }

     ///@}

     ///\name Obtaining the solution LP

     ///@{

     ///\e

     Value solution(Col c) { return _getSolution(cols.floatingId(c.id)); }

     ///@}

   };  

   ///\e

   ///\relates LpSolverBase::Expr

   ///

   inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,

 				      const LpSolverBase::Expr &b) 

   {

     LpSolverBase::Expr tmp(a);

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

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Expr

   ///

   inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,

 				      const LpSolverBase::Expr &b) 

   {

     LpSolverBase::Expr tmp(a);

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

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Expr

   ///

   inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,

 				      const LpSolverBase::Value &b) 

   {

     LpSolverBase::Expr tmp(a);

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

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Expr

   ///

   inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,

 				      const LpSolverBase::Expr &b) 

   {

     LpSolverBase::Expr tmp(b);

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

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Expr

   ///

   inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,

 				      const LpSolverBase::Value &b) 

   {

     LpSolverBase::Expr tmp(a);

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

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,

 					 const LpSolverBase::Expr &f) 

   {

     return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,

 					 const LpSolverBase::Expr &f) 

   {

     return LpSolverBase::Constr(e,f);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,

 					 const LpSolverBase::Value &f) 

   {

     return LpSolverBase::Constr(e,f);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,

 					 const LpSolverBase::Expr &f) 

   {

     return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,

 					 const LpSolverBase::Expr &f) 

   {

     return LpSolverBase::Constr(f,e);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,

 					 const LpSolverBase::Value &f) 

   {

     return LpSolverBase::Constr(f,e);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,

 					 const LpSolverBase::Expr &f) 

   {

     return LpSolverBase::Constr(0,e-f,0);

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,

 					 const LpSolverBase::Constr&c) 

   {

     LpSolverBase::Constr tmp(c);

     ///\todo Create an own exception type.

     if(!isnan(tmp.lowerBound())) throw LogicError();

     else tmp.lowerBound()=n;

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,

 					 const LpSolverBase::Value &n)

   {

     LpSolverBase::Constr tmp(c);

     ///\todo Create an own exception type.

     if(!isnan(tmp.upperBound())) throw LogicError();

     else tmp.upperBound()=n;

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,

 					 const LpSolverBase::Constr&c) 

   {

     LpSolverBase::Constr tmp(c);

     ///\todo Create an own exception type.

     if(!isnan(tmp.upperBound())) throw LogicError();

     else tmp.upperBound()=n;

     return tmp;

   }

   ///\e

   ///\relates LpSolverBase::Constr

   ///

   inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,

 					 const LpSolverBase::Value &n)

   {

     LpSolverBase::Constr tmp(c);

     ///\todo Create an own exception type.

     if(!isnan(tmp.lowerBound())) throw LogicError();

     else tmp.lowerBound()=n;

     return tmp;

   }

 } //namespace lemon

 #endif //LEMON_LP_BASE_H