/* -*- 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<lemon/error.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 by implemented to be 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;

 	}

       }

       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

     typedef double Value;

     /// \e 

     static const Value INF;

     ///\e

     class Col { protected: int id; friend class LpSolverBase; };

     ///\e

     class Row { protected: int id; friend class LpSolverBase; };

     typedef SparseLinExpr<Col, Value> Expr;

   protected:

     _FixId rows;

     _FixId cols;

     //MATRIX MANIPULATING FUNCTIONS

     /// \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 -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 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 -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 INF.

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

     /// \e

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

     ///\e

     ///\bug unimplemented!!!!

     void clearObj() {}

   public:

     ///\e

     virtual ~LpSolverBase() {}

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

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

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

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

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

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

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

     ///\param u upper bound (INF means no bound)

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

     ///a better one.

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

       Row r=addRow();

       std::vector<int> indices;

       std::vector<Value> values;

       indices.push_back(0);

       values.push_back(0);

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

 	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);

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

       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 -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 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 -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 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);

     }

   };  

 } //namespace lemon

 #endif //LEMON_LP_BASE_H