// -*- c++ -*-

 #ifndef LEMON_LP_SOLVER_WRAPPER_H

 #define LEMON_LP_SOLVER_WRAPPER_H

 ///\ingroup misc

 ///\file

 ///\brief Dijkstra algorithm.

 // #include <stdio.h>

 #include <stdlib.h>

 // #include <stdio>

 //#include <stdlib>

 extern "C" {

 #include "glpk.h"

 }

 #include <iostream>

 #include <vector>

 #include <string>

 #include <list>

 #include <memory>

 #include <utility>

 //#include <sage_graph.h>

 //#include <lemon/list_graph.h>

 //#include <lemon/graph_wrapper.h>

 #include <lemon/invalid.h>

 //#include <bfs_dfs.h>

 //#include <stp.h>

 //#include <lemon/max_flow.h>

 //#include <augmenting_flow.h>

 //#include <iter_map.h>

 using std::cout;

 using std::cin;

 using std::endl;

 namespace lemon {

   /// \addtogroup misc

   /// @{

   /// \brief A partitioned vector with iterable classes.

   ///

   /// This class implements a container in which the data is stored in an 

   /// stl vector, the range is partitioned into sets and each set is 

   /// doubly linked in a list. 

   /// That is, each class is iterable by lemon iterators, and any member of 

   /// the vector can bo moved to an other class.

   template <typename T>

   class IterablePartition {

   protected:

     struct Node {

       T data;

       int prev; //invalid az -1

       int next; 

     };

     std::vector<Node> nodes;

     struct Tip {

       int first;

       int last;

     };

     std::vector<Tip> tips;

   public:

     /// The classes are indexed by integers from \c 0 to \c classNum()-1.

     int classNum() const { return tips.size(); }

     /// This lemon style iterator iterates through a class. 

     class ClassIt;

     /// Constructor. The number of classes is to be given which is fixed 

     /// over the life of the container. 

     /// The partition classes are indexed from 0 to class_num-1. 

     IterablePartition(int class_num) { 

       for (int i=0; i<class_num; ++i) {

 	Tip t;

 	t.first=t.last=-1;

 	tips.push_back(t);

       }

     }

   protected:

     void befuz(ClassIt it, int class_id) {

       if (tips[class_id].first==-1) {

 	if (tips[class_id].last==-1) {

 	  nodes[it.i].prev=nodes[it.i].next=-1;

 	  tips[class_id].first=tips[class_id].last=it.i;

 	}

       } else {

 	nodes[it.i].prev=tips[class_id].last;

 	nodes[it.i].next=-1;

 	nodes[tips[class_id].last].next=it.i;

 	tips[class_id].last=it.i;

       }

     }

     void kifuz(ClassIt it, int class_id) {

       if (tips[class_id].first==it.i) {

 	if (tips[class_id].last==it.i) {

 	  tips[class_id].first=tips[class_id].last=-1;

 	} else {

 	  tips[class_id].first=nodes[it.i].next;

 	  nodes[nodes[it.i].next].prev=-1;

 	}

       } else {

 	if (tips[class_id].last==it.i) {

 	  tips[class_id].last=nodes[it.i].prev;

 	  nodes[nodes[it.i].prev].next=-1;

 	} else {

 	  nodes[nodes[it.i].next].prev=nodes[it.i].prev;

 	  nodes[nodes[it.i].prev].next=nodes[it.i].next;

 	}

       }

     }

   public:

     /// A new element with data \c t is pushed into the vector and into class 

     /// \c class_id.

     ClassIt push_back(const T& t, int class_id) { 

       Node n;

       n.data=t;

       nodes.push_back(n);

       int i=nodes.size()-1;

       befuz(i, class_id);

       return i;

     }

     /// A member is moved to an other class.

     void set(ClassIt it, int old_class_id, int new_class_id) {

       kifuz(it.i, old_class_id);

       befuz(it.i, new_class_id);

     }

     /// Returns the data pointed by \c it.

     T& operator[](ClassIt it) { return nodes[it.i].data; }

     /// Returns the data pointed by \c it.

     const T& operator[](ClassIt it) const { return nodes[it.i].data; }

     ///.

     class ClassIt {

       friend class IterablePartition;

     protected:

       int i;

     public:

       /// Default constructor.

       ClassIt() { }

       /// This constructor constructs an iterator which points

       /// to the member of th container indexed by the integer _i.

       ClassIt(const int& _i) : i(_i) { }

       /// Invalid constructor.

       ClassIt(const Invalid&) : i(-1) { }

     };

     /// First member of class \c class_id.

     ClassIt& first(ClassIt& it, int class_id) const {

       it.i=tips[class_id].first;

       return it;

     }

     /// Next member.

     ClassIt& next(ClassIt& it) const {

       it.i=nodes[it.i].next;

       return it;

     }

     /// True iff the iterator is valid.

     bool valid(const ClassIt& it) const { return it.i!=-1; }

   };

   /*! \e

    */

   class LPSolverBase {

   public:

     /// \e

     typedef IterablePartition<int>::ClassIt RowIt;

     /// \e

     typedef IterablePartition<int>::ClassIt ColIt;

   protected:

     /// \e

     IterablePartition<int> row_iter_map;

     /// \e

     IterablePartition<int> col_iter_map;

     /// \e

     const int VALID_ID;

     /// \e

     const int INVALID_ID;

   public:

     /// \e

     LPSolverBase() : row_iter_map(2), 

 		     col_iter_map(2), 

 		     VALID_ID(0), INVALID_ID(1) { }

     /// \e

     virtual ~LPSolverBase() { }

     /// \e

     virtual void setMinimize() = 0;

     /// \e

     virtual void setMaximize() = 0;

     /// \e

     virtual RowIt addRow() = 0;

     /// \e

     virtual ColIt addCol() = 0;

     /// temporally, glpk style indexing

     virtual void setRowCoeffs(RowIt row_it, int num, 

 			      int* indices, double* doubles) = 0;

     //pair<RowIt, double>-bol kell megadni egy std range-et

     /// \e

     template <typename Begin, typename End>

     void setRowCoeffs(RowIt row_it, Begin begin, End end) {

       int mem_length=1+colNum();

       int* indices = new int[mem_length];

       double* doubles = new double[mem_length];

       int length=0;

       for ( ; begin!=end; ++begin) {

 	++length;

 	indices[length]=col_iter_map[begin->first];

 	doubles[length]=begin->second;

       }

       setRowCoeffs(row_it, length, indices, doubles);

       delete [] indices;

       delete [] doubles;

     }

     /// temporally, glpk style indexing

     virtual void setColCoeffs(ColIt col_it, int num, 

 			      int* indices, double* doubles) = 0;

     //pair<ColIt, double>-bol kell megadni egy std range-et

     /// \e

     template <typename Begin, typename End>

     void setColCoeffs(ColIt col_it, Begin begin, End end) {

       int mem_length=1+rowNum();

       int* indices = new int[mem_length];

       double* doubles = new double[mem_length];

       int length=0;

       for ( ; begin!=end; ++begin) {

 	++length;

 	indices[length]=row_iter_map[begin->first];

 	doubles[length]=begin->second;

       }

       setColCoeffs(col_it, length, indices, doubles);

       delete [] indices;

       delete [] doubles;

     }

     /// \e

     virtual void eraseCol(const ColIt& col_it) = 0;

     /// \e

     virtual void eraseRow(const RowIt& row_it) = 0;

     /// \e

     virtual void setColBounds(const ColIt& col_it, int bound_type, 

 			      double lo, double up) =0; 

     /// \e

     virtual double getObjCoef(const ColIt& col_it) = 0;

     /// \e

     virtual void setRowBounds(const RowIt& row_it, int bound_type, 

 			      double lo, double up) = 0;

     /// \e

     virtual void setObjCoef(const ColIt& col_it, double obj_coef) = 0;

     /// \e

     virtual void solveSimplex() = 0;

     /// \e

     virtual void solvePrimalSimplex() = 0;

     /// \e

     virtual void solveDualSimplex() = 0;

     /// \e

     virtual double getPrimal(const ColIt& col_it) = 0;

     /// \e

     virtual double getObjVal() = 0;

     /// \e

     virtual int rowNum() const = 0;

     /// \e

     virtual int colNum() const = 0;

     /// \e

     virtual int warmUp() = 0;

     /// \e

     virtual void printWarmUpStatus(int i) = 0;

     /// \e

     virtual int getPrimalStatus() = 0;

     /// \e

     virtual void printPrimalStatus(int i) = 0;

     /// \e

     virtual int getDualStatus() = 0;

     /// \e

     virtual void printDualStatus(int i) = 0;

     /// Returns the status of the slack variable assigned to row \c row_it.

     virtual int getRowStat(const RowIt& row_it) = 0;

     /// \e

     virtual void printRowStatus(int i) = 0;

     /// Returns the status of the variable assigned to column \c col_it.

     virtual int getColStat(const ColIt& col_it) = 0;

     /// \e

     virtual void printColStatus(int i) = 0;

   };

   /// \brief Wrappers for LP solvers

   /// 

   /// This class implements a lemon wrapper for glpk.

   /// Later other LP-solvers will be wrapped into lemon.

   /// The aim of this class is to give a general surface to different 

   /// solvers, i.e. it makes possible to write algorithms using LP's, 

   /// in which the solver can be changed to an other one easily.

   class LPSolverWrapper : public LPSolverBase {

   public:

     typedef LPSolverBase Parent;

     //   class Row {

     //   protected:

     //     int i;

     //   public:

     //     Row() { }

     //     Row(const Invalid&) : i(0) { }

     //     Row(const int& _i) : i(_i) { }

     //     operator int() const { return i; }

     //   };

     //   class RowIt : public Row {

     //   public:

     //     RowIt(const Row& row) : Row(row) { }

     //   };

     //   class Col {

     //   protected:

     //     int i;

     //   public:

     //     Col() { }

     //     Col(const Invalid&) : i(0) { }

     //     Col(const int& _i) : i(_i) { }

     //     operator int() const { return i; }

     //   };

     //   class ColIt : public Col {

     //     ColIt(const Col& col) : Col(col) { }

     //   };

   public:

     /// \e

     LPX* lp;

   public:

     /// \e

     LPSolverWrapper() : LPSolverBase(), 

 			lp(lpx_create_prob()) {

       lpx_set_int_parm(lp, LPX_K_DUAL, 1);

     }

     /// \e

     ~LPSolverWrapper() {

       lpx_delete_prob(lp);

     }

     /// \e

     void setMinimize() { 

       lpx_set_obj_dir(lp, LPX_MIN);

     }

     /// \e

     void setMaximize() { 

       lpx_set_obj_dir(lp, LPX_MAX);

     }

     /// \e

     ColIt addCol() {

       int i=lpx_add_cols(lp, 1);  

       ColIt col_it;

       col_iter_map.first(col_it, INVALID_ID);

       if (col_iter_map.valid(col_it)) { //van hasznalhato hely

 	col_iter_map.set(col_it, INVALID_ID, VALID_ID);

 	col_iter_map[col_it]=i;

 	//col_id_to_lp_col_id[col_iter_map[col_it]]=i;

       } else { //a cucc vegere kell inzertalni mert nincs szabad hely

 	//col_id_to_lp_col_id.push_back(i);

 	//int j=col_id_to_lp_col_id.size()-1;

 	col_it=col_iter_map.push_back(i, VALID_ID);

       }

       //    edge_index_map.set(e, i);

       //    lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);

       //    lpx_set_obj_coef(lp, i, cost[e]);    

       return col_it;

     }

     /// \e

     RowIt addRow() {

       int i=lpx_add_rows(lp, 1);  

       RowIt row_it;

       row_iter_map.first(row_it, INVALID_ID);

       if (row_iter_map.valid(row_it)) { //van hasznalhato hely

 	row_iter_map.set(row_it, INVALID_ID, VALID_ID);

 	row_iter_map[row_it]=i;

       } else { //a cucc vegere kell inzertalni mert nincs szabad hely

 	row_it=row_iter_map.push_back(i, VALID_ID);

       }

       return row_it;

     }

     using Parent::setRowCoeffs;

     void setRowCoeffs(RowIt row_it, int length, 

 		      int* indices, double* doubles) {

       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);

     }

     using Parent::setColCoeffs;

     void setColCoeffs(ColIt col_it, int length, 

 		      int* indices, double* doubles) {

       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);

     }

     //     //pair<RowIt, double>-bol kell megadni egy std range-et

     //     /// \e

     //     template <typename Begin, typename End>

     //     void setColCoeffs(const ColIt& col_it, 

     // 		      Begin begin, End end) {

     //       int mem_length=1+lpx_get_num_rows(lp);

     //       int* indices = new int[mem_length];

     //       double* doubles = new double[mem_length];

     //       int length=0;

     //       for ( ; begin!=end; ++begin) {

     // 	++length;

     // 	indices[length]=row_iter_map[begin->first];

     // 	doubles[length]=begin->second;

     //       }

     //       lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);

     //       delete [] indices;

     //       delete [] doubles;

     //     }

     //     //pair<ColIt, double>-bol kell megadni egy std range-et

     //     /// \e

     //     template <typename Begin, typename End>

     //     void setRowCoeffs(const RowIt& row_it, 

     // 		      Begin begin, End end) {

     //       int mem_length=1+lpx_get_num_cols(lp);

     //       int* indices = new int[mem_length];

     //       double* doubles = new double[mem_length];

     //       int length=0;

     //       for ( ; begin!=end; ++begin) {

     // 	++length;

     // 	indices[length]=col_iter_map[begin->first];

     // 	doubles[length]=begin->second;

     //       }

     //       lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);

     //       delete [] indices;

     //       delete [] doubles;

     //     }

     /// \e

     void eraseCol(const ColIt& col_it) {

       col_iter_map.set(col_it, VALID_ID, INVALID_ID);

       int cols[2];

       cols[1]=col_iter_map[col_it];

       lpx_del_cols(lp, 1, cols);

       col_iter_map[col_it]=0; //glpk specifikus

       ColIt it;

       for (col_iter_map.first(it, VALID_ID); 

 	   col_iter_map.valid(it); col_iter_map.next(it)) {

 	if (col_iter_map[it]>cols[1]) --col_iter_map[it];

       }

     }

     /// \e

     void eraseRow(const RowIt& row_it) {

       row_iter_map.set(row_it, VALID_ID, INVALID_ID);

       int rows[2];

       rows[1]=row_iter_map[row_it];

       lpx_del_rows(lp, 1, rows);

       row_iter_map[row_it]=0; //glpk specifikus

       RowIt it;

       for (row_iter_map.first(it, VALID_ID); 

 	   row_iter_map.valid(it); row_iter_map.next(it)) {

 	if (row_iter_map[it]>rows[1]) --row_iter_map[it];

       }

     }

     /// \e

     void setColBounds(const ColIt& col_it, int bound_type, 

 		      double lo, double up) {

       lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);

     }

     /// \e

     double getObjCoef(const ColIt& col_it) { 

       return lpx_get_obj_coef(lp, col_iter_map[col_it]);

     }

     /// \e

     void setRowBounds(const RowIt& row_it, int bound_type, 

 		      double lo, double up) {

       lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);

     }

     /// \e

     void setObjCoef(const ColIt& col_it, double obj_coef) { 

       lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);

     }

     /// \e

     void solveSimplex() { lpx_simplex(lp); }

     /// \e

     void solvePrimalSimplex() { lpx_simplex(lp); }

     /// \e

     void solveDualSimplex() { lpx_simplex(lp); }

     /// \e

     double getPrimal(const ColIt& col_it) {

       return lpx_get_col_prim(lp, col_iter_map[col_it]);

     }

     /// \e

     double getObjVal() { return lpx_get_obj_val(lp); }

     /// \e

     int rowNum() const { return lpx_get_num_rows(lp); }

     /// \e

     int colNum() const { return lpx_get_num_cols(lp); }

     /// \e

     int warmUp() { return lpx_warm_up(lp); }

     /// \e

     void printWarmUpStatus(int i) {

       switch (i) {

       case LPX_E_OK: cout << "LPX_E_OK" << endl; break;

       case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;	

       case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;

       case LPX_E_SING: cout << "LPX_E_SING" << endl; break;

       }

     }

     /// \e

     int getPrimalStatus() { return lpx_get_prim_stat(lp); }

     /// \e

     void printPrimalStatus(int i) {

       switch (i) {

       case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;

       case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;	

       case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;

       case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;

       }

     }

     /// \e

     int getDualStatus() { return lpx_get_dual_stat(lp); }

     /// \e

     void printDualStatus(int i) {

       switch (i) {

       case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;

       case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;	

       case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;

       case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;

       }

     }

     /// Returns the status of the slack variable assigned to row \c row_it.

     int getRowStat(const RowIt& row_it) { 

       return lpx_get_row_stat(lp, row_iter_map[row_it]); 

     }

     /// \e

     void printRowStatus(int i) {

       switch (i) {

       case LPX_BS: cout << "LPX_BS" << endl; break;

       case LPX_NL: cout << "LPX_NL" << endl; break;	

       case LPX_NU: cout << "LPX_NU" << endl; break;

       case LPX_NF: cout << "LPX_NF" << endl; break;

       case LPX_NS: cout << "LPX_NS" << endl; break;

       }

     }

     /// Returns the status of the variable assigned to column \c col_it.

     int getColStat(const ColIt& col_it) { 

       return lpx_get_col_stat(lp, col_iter_map[col_it]); 

     }

     /// \e

     void printColStatus(int i) {

       switch (i) {

       case LPX_BS: cout << "LPX_BS" << endl; break;

       case LPX_NL: cout << "LPX_NL" << endl; break;	

       case LPX_NU: cout << "LPX_NU" << endl; break;

       case LPX_NF: cout << "LPX_NF" << endl; break;

       case LPX_NS: cout << "LPX_NS" << endl; break;

       }

     }

   };

   /// @}

 } //namespace lemon

 #endif //LEMON_LP_SOLVER_WRAPPER_H