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