/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2006

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, 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_UTILS_H

 #define LEMON_LP_UTILS_H

 #include <lemon/lp_base.h>

 #include <lemon/lemon_reader.h>

 #include <lemon/lemon_writer.h>

 namespace lemon {

   class LpReader : public LemonReader::SectionReader {

     typedef LemonReader::SectionReader Parent;

   public:

     /// \brief Constructor.

     ///

     /// Constructor for LpReader. It creates the LpReader and attach

     /// it into the given LemonReader. The lp reader will add

     /// variables, constraints and objective function to the

     /// given lp solver.

     LpReader(LemonReader& _reader, LpSolverBase& _lp, 

              const std::string& _name = std::string())

       : Parent(_reader), lp(_lp), name(_name) {} 

     /// \brief Destructor.

     ///

     /// Destructor for NodeSetReader.

     virtual ~LpReader() {}

   private:

     LpReader(const LpReader&);

     void operator=(const LpReader&);

   protected:

     /// \brief Gives back true when the SectionReader can process 

     /// the section with the given header line.

     ///

     /// It gives back true when the header line starts with \c \@lp,

     /// and the header line's name and the nodeset's name are the same.

     virtual bool header(const std::string& line) {

       std::istringstream ls(line);

       std::string command;

       std::string id;

       ls >> command >> id;

       return command == "@lp" && name == id;

     }

   private:

     enum Relation {

       LE, EQ, GE

     };

     std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {

       char x;

       LpSolverBase::Expr e1, e2;

       Relation op1;

       is >> std::ws;

       readExpression(is, e1);

       is >> std::ws;

       readRelation(is, op1);

       is >> std::ws;

       readExpression(is, e2);

       if (!is.get(x)) {

         if (op1 == LE) {

           c = e1 <= e2;

         } else if (op1 == GE) {

           c = e1 >= e2;

         } else {

           c = e1 == e2;

         }

       } else {

         is.putback(x);

         LpSolverBase::Expr e3;

         Relation op2;

         readRelation(is, op2);

         is >> std::ws;

         readExpression(is, e3);

         if (!e1.empty() || !e3.empty()) {

           throw DataFormatError("Wrong range format");

         }

         if (op2 != op1 || op1 == EQ) {

           throw DataFormatError("Wrong range format");

         }

         if (op1 == LE) {

           c = e1.constComp() <= e2 <= e3.constComp();

         } else {

           c = e1.constComp() >= e2 >= e3.constComp();

         }

       }

     }

     std::istream& readExpression(std::istream& is, LpSolverBase::Expr& e) {

       LpSolverBase::Col c;

       double d;

       char x;

       readElement(is, c, d);

       if (c != INVALID) {

         e += d * c;

       } else {

         e += d;

       }

       is >> std::ws;

       while (is.get(x) && (x == '+' || x == '-')) {

         is >> std::ws;

         readElement(is, c, d);

         if (c != INVALID) {

           e += (x == '+' ? d : -d) * c;

         } else {

           e += (x == '+' ? d : -d);

         }

         is >> std::ws;

       }

       if (!is) {

         is.clear();

       } else {

         is.putback(x);

       }

       return is;

     }

     std::istream& readElement(std::istream& is, 

                               LpSolverBase::Col& c, double& d) { 

       d = 1.0;

       c = INVALID;

       char x, y;

       if (!is.get(x)) throw DataFormatError("Cannot find lp element");

       if (x == '+' || x == '-') {

         is >> std::ws;

         d *= x == '-' ? -1 : 1;

         while (is.get(x) && (x == '+' || x == '-')) {

           d *= x == '-' ? -1 : 1;

           is >> std::ws;

         }

         if (!is) throw DataFormatError("Cannot find lp element");

       }

       if (numFirstChar(x)) {

         is.putback(x);

         double e;

         readNum(is, e);

         d *= e;

       } else if (varFirstChar(x)) {

         is.putback(x);

         LpSolverBase::Col f;

         readCol(is, f);

         c = f;

       } else {

         throw DataFormatError("Invalid expression format");          

       }

       is >> std::ws;

       while (is.get(y) && (y == '*' || y == '/')) {

         is >> std::ws;

         if (!is.get(x)) throw DataFormatError("Cannot find lp element");

         if (x == '+' || x == '-') {

           is >> std::ws;

           d *= x == '-' ? -1 : 1;

           while (is.get(x) && (x == '+' || x == '-')) {

             d *= x == '-' ? -1 : 1;

             is >> std::ws;

           }

           if (!is) throw DataFormatError("Cannot find lp element");

         }

         if (numFirstChar(x)) {

           is.putback(x);

           double e;

           readNum(is, e);

           if (y == '*') {

             d *= e;

           } else {

             d /= e;

           }

         } else if (varFirstChar(x)) {

           is.putback(x);

           LpSolverBase::Col f;

           readCol(is, f);

           if (y == '*') {

             if (c == INVALID) {

               c = f;

             } else {

               throw DataFormatError("Quadratic element in expression");

             }

           } else {

             throw DataFormatError("Division by variable");

           }

         } else {

           throw DataFormatError("Invalid expression format");          

         }

         is >> std::ws;

       }

       if (!is) {

         is.clear();

       } else {

         is.putback(y);

       }

       return is;

     }

     std::istream& readCol(std::istream& is, LpSolverBase::Col& c) {

       char x;

       std::string var;

       while (is.get(x) && varChar(x)) {

         var += x;

       }

       if (!is) {

         is.clear();

       } else {

         is.putback(x);

       }

       ColMap::const_iterator it = cols.find(var);

       if (cols.find(var) != cols.end()) {

         c = it->second;

       } else {

         c = lp.addCol();

         cols.insert(std::make_pair(var, c));

         lp.colName(c, var);

       }

       return is;

     }

     std::istream& readNum(std::istream& is, double& d) {

       is >> d;

       if (!is) throw DataFormatError("Wrong number format");

       return is;

     }

     std::istream& readRelation(std::istream& is, Relation& op) {

       char x, y;

       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {

         throw DataFormatError("Wrong relation operator");

       }

       if (!is.get(y) || y != '=') {

         throw DataFormatError("Wrong relation operator");

       }

       switch (x) {

       case '<': op = LE; 

         break;

       case '=': op = EQ; 

         break;

       case '>': op = GE; 

         break;

       }

       return is;

     }

     static bool relationFirstChar(char c) {

       return c == '<' || c == '=' || c == '>';

     }

     static bool varFirstChar(char c) {

       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

     }

     static bool numFirstChar(char c) {

       return (c >= '0' && c <= '9') || c == '.';

     }

     static bool varChar(char c) {

       return (c >= '0' && c <= '9') || 

         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

     }

     void addConstraint(const LpSolverBase::Constr& constr) {

       if (constr.expr().size() != 1) {

         lp.addRow(constr);

       } else {

         Lp::Expr e = constr.expr();

         LpSolverBase::Col col = e.begin()->first;

         double coeff = e.begin()->second;

         double lb = LpSolverBase::NaN;

         double ub = LpSolverBase::NaN;

         if (coeff > 0) {

           if (constr.upperBounded()) {

             lb = (constr.lowerBound() - e.constComp()) / coeff;

           }

           if (constr.lowerBounded()) {

             ub = (constr.upperBound() - e.constComp()) / coeff;

           }

         } else if (coeff < 0) {

           if (constr.upperBounded()) {

             lb = (constr.upperBound() - e.constComp()) / coeff;

           }

           if (constr.lowerBounded()) {

             ub = (constr.lowerBound() - e.constComp()) / coeff;

           }

         } else {

           lb = -LpSolverBase::INF;

           ub = LpSolverBase::INF;

         }

         lp.colLowerBound(col, lb);

         lp.colUpperBound(col, ub);

       }

     }

   protected:

     /// \brief Reader function of the section.

     ///

     /// It reads the content of the section.

     virtual void read(std::istream& is) {

       std::string line;

       while (getline(is, line)) {

         std::istringstream ls(line);

         std::string sense;

         ls >> sense;

         if (sense == "min" || sense == "max") {

           LpSolverBase::Expr expr;

           ls >> std::ws;

           readExpression(ls, expr);

           lp.setObj(expr);

           if (sense == "min") {

             lp.min();

           } else {

             lp.max();

           }

         } else {

           ls.str(line);

           LpSolverBase::Constr constr;

           ls >> std::ws;

           readConstraint(ls, constr);

           addConstraint(constr);

         }        

       }

     }

     virtual void missing() {

       ErrorMessage msg;

       msg << "Lp section not found in file: @lp " << name;

       throw IoParameterError(msg.message());

     }

   private:

     typedef std::map<std::string, LpSolverBase::Col> ColMap;

     LpSolverBase& lp;

     std::string name;

     ColMap cols;

   };

 //   class LpWriter : public LemonWriter::SectionWriter {

 //     typedef LemonWriter::SectionWriter Parent;

 //   public:

 //     /// \brief Constructor.

 //     ///

 //     /// Constructor for LpWriter. It creates the LpWriter and attach

 //     /// it into the given LemonWriter. The lp writer will add

 //     /// variables, constraints and objective function to the

 //     /// given lp solver.

 //     LpWriter(LemonWriter& _writer, LpSolverBase& _lp, 

 //              const std::string& _name = std::string())

 //       : Parent(_writer), lp(_lp), name(_name) {} 

 //     /// \brief Destructor.

 //     ///

 //     /// Destructor for NodeSetWriter.

 //     virtual ~LpWriter() {}

 //   private:

 //     LpWriter(const LpWriter&);

 //     void operator=(const LpWriter&);

 //   protected:

 //     /// \brief Gives back true when the SectionWriter can process 

 //     /// the section with the given header line.

 //     ///

 //     /// It gives back the header line of the \c \@lp section.

 //     virtual std::string header() {

 //       std::ostringstream ls(line);

 //       ls << "@lp " << name;

 //       return ls.str();

 //     }

 //   private:

 //     std::ostream& writeConstraint(std::ostream& is, LpSolverBase::Constr& c) {

 //       char x;

 //       LpSolverBase::Expr e1, e2;

 //       Relation op1;

 //       is >> std::ws;

 //       writexpression(is, e1);

 //       is >> std::ws;

 //       writeRelation(is, op1);

 //       is >> std::ws;

 //       writexpression(is, e2);

 //       if (!is.get(x)) {

 //         if (op1 == LE) {

 //           c = e1 <= e2;

 //         } else if (op1 == GE) {

 //           c = e1 >= e2;

 //         } else {

 //           c = e1 == e2;

 //         }

 //       } else {

 //         is.putback(x);

 //         LpSolverBase::Expr e3;

 //         Relation op2;

 //         writeRelation(is, op2);

 //         is >> std::ws;

 //         writexpression(is, e3);

 //         if (!e1.empty() || !e3.empty()) {

 //           throw DataFormatError("Wrong range format");

 //         }

 //         if (op2 != op1 || op1 == EQ) {

 //           throw DataFormatError("Wrong range format");

 //         }

 //         if (op1 == LE) {

 //           c = e1.constComp() <= e2 <= e3.constComp();

 //         } else {

 //           c = e1.constComp() >= e2 >= e3.constComp();

 //         }

 //       }

 //     }

 //     std::ostream& writexpression(std::ostream& is, LpSolverBase::Expr& e) {

 //       LpSolverBase::Col c;

 //       double d;

 //       char x;

 //       writelement(is, c, d);

 //       if (c != INVALID) {

 //         e += d * c;

 //       } else {

 //         e += d;

 //       }

 //       is >> std::ws;

 //       while (is.get(x) && (x == '+' || x == '-')) {

 //         is >> std::ws;

 //         writelement(is, c, d);

 //         if (c != INVALID) {

 //           e += (x == '+' ? d : -d) * c;

 //         } else {

 //           e += (x == '+' ? d : -d);

 //         }

 //         is >> std::ws;

 //       }

 //       if (!is) {

 //         is.clear();

 //       } else {

 //         is.putback(x);

 //       }

 //       return is;

 //     }

 //     std::ostream& writelement(std::ostream& is, 

 //                               LpSolverBase::Col& c, double& d) { 

 //       d = 1.0;

 //       c = INVALID;

 //       char x, y;

 //       if (!is.get(x)) throw DataFormatError("Cannot find lp element");

 //       if (x == '+' || x == '-') {

 //         is >> std::ws;

 //         d *= x == '-' ? -1 : 1;

 //         while (is.get(x) && (x == '+' || x == '-')) {

 //           d *= x == '-' ? -1 : 1;

 //           is >> std::ws;

 //         }

 //         if (!is) throw DataFormatError("Cannot find lp element");

 //       }

 //       if (numFirstChar(x)) {

 //         is.putback(x);

 //         double e;

 //         writeNum(is, e);

 //         d *= e;

 //       } else if (varFirstChar(x)) {

 //         is.putback(x);

 //         LpSolverBase::Col f;

 //         writeCol(is, f);

 //         c = f;

 //       } else {

 //         throw DataFormatError("Invalid expression format");          

 //       }

 //       is >> std::ws;

 //       while (is.get(y) && (y == '*' || y == '/')) {

 //         is >> std::ws;

 //         if (!is.get(x)) throw DataFormatError("Cannot find lp element");

 //         if (x == '+' || x == '-') {

 //           is >> std::ws;

 //           d *= x == '-' ? -1 : 1;

 //           while (is.get(x) && (x == '+' || x == '-')) {

 //             d *= x == '-' ? -1 : 1;

 //             is >> std::ws;

 //           }

 //           if (!is) throw DataFormatError("Cannot find lp element");

 //         }

 //         if (numFirstChar(x)) {

 //           is.putback(x);

 //           double e;

 //           writeNum(is, e);

 //           if (y == '*') {

 //             d *= e;

 //           } else {

 //             d /= e;

 //           }

 //         } else if (varFirstChar(x)) {

 //           is.putback(x);

 //           LpSolverBase::Col f;

 //           writeCol(is, f);

 //           if (y == '*') {

 //             if (c == INVALID) {

 //               c = f;

 //             } else {

 //               throw DataFormatError("Quadratic element in expression");

 //             }

 //           } else {

 //             throw DataFormatError("Division by variable");

 //           }

 //         } else {

 //           throw DataFormatError("Invalid expression format");          

 //         }

 //         is >> std::ws;

 //       }

 //       if (!is) {

 //         is.clear();

 //       } else {

 //         is.putback(y);

 //       }

 //       return is;

 //     }

 //     std::ostream& writeCol(std::ostream& is, LpSolverBase::Col& c) {

 //       char x;

 //       std::string var;

 //       while (is.get(x) && varChar(x)) {

 //         var += x;

 //       }

 //       if (!is) {

 //         is.clear();

 //       } else {

 //         is.putback(x);

 //       }

 //       ColMap::const_iterator it = cols.find(var);

 //       if (cols.find(var) != cols.end()) {

 //         c = it->second;

 //       } else {

 //         c = lp.addCol();

 //         cols.insert(std::make_pair(var, c));

 //         lp.colName(c, var);

 //       }

 //       return is;

 //     }

 //     std::ostream& writeNum(std::ostream& is, double& d) {

 //       is >> d;

 //       if (!is) throw DataFormatError("Wrong number format");

 //       return is;

 //     }

 //     std::ostream& writeRelation(std::ostream& is, Relation& op) {

 //       char x, y;

 //       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {

 //         throw DataFormatError("Wrong relation operator");

 //       }

 //       if (!is.get(y) || y != '=') {

 //         throw DataFormatError("Wrong relation operator");

 //       }

 //       switch (x) {

 //       case '<': op = LE; 

 //         break;

 //       case '=': op = EQ; 

 //         break;

 //       case '>': op = GE; 

 //         break;

 //       }

 //       return is;

 //     }

 //     static bool relationFirstChar(char c) {

 //       return c == '<' || c == '=' || c == '>';

 //     }

 //     static bool varFirstChar(char c) {

 //       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

 //     }

 //     static bool numFirstChar(char c) {

 //       return (c >= '0' && c <= '9') || c == '.';

 //     }

 //     static bool varChar(char c) {

 //       return (c >= '0' && c <= '9') || 

 //         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');

 //     }

 //     void addConstraint(const LpSolverBase::Constr& constr) {

 //       if (constr.expr().size() != 1) {

 //         lp.addRow(constr);

 //       } else {

 //         Lp::Expr e = constr.expr();

 //         LpSolverBase::Col col = e.begin()->first;

 //         double coeff = e.begin()->second;

 //         double lb = LpSolverBase::NaN;

 //         double ub = LpSolverBase::NaN;

 //         if (coeff > 0) {

 //           if (constr.upperBounded()) {

 //             lb = (constr.lowerBound() - e.constComp()) / coeff;

 //           }

 //           if (constr.lowerBounded()) {

 //             ub = (constr.upperBound() - e.constComp()) / coeff;

 //           }

 //         } else if (coeff < 0) {

 //           if (constr.upperBounded()) {

 //             lb = (constr.upperBound() - e.constComp()) / coeff;

 //           }

 //           if (constr.lowerBounded()) {

 //             ub = (constr.lowerBound() - e.constComp()) / coeff;

 //           }

 //         } else {

 //           lb = -LpSolverBase::INF;

 //           ub = LpSolverBase::INF;

 //         }

 //         lp.colLowerBound(col, lb);

 //         lp.colUpperBound(col, ub);

 //       }

 //     }

 //   protected:

 //     /// \brief Writer function of the section.

 //     ///

 //     /// It writes the content of the section.

 //     virtual void write(std::ostream& is) {

 //       std::string line;

 //       std::map<std::string, LpSolverBase::Col> vars;

 //       while (getline(is, line)) {

 //         std::istringstream ls(line);

 //         std::string sense;

 //         ls >> sense;

 //         if (sense == "min" || sense == "max") {

 //           LpSolverBase::Expr expr;

 //           ls >> std::ws;

 //           writeExpression(ls, expr);

 //           lp.setObj(expr);

 //           if (sense == "min") {

 //             lp.min();

 //           } else {

 //             lp.max();

 //           }

 //         } else {

 //           ls.str(line);

 //           LpSolverBase::Constr constr;

 //           ls >> std::ws;

 //           writeConstraint(ls, constr);

 //           addConstraint(constr);

 //         }        

 //       }

 //     }

 //     virtual void missing() {

 //       ErrorMessage msg;

 //       msg << "Lp section not found in file: @lp " << name;

 //       throw IoParameterError(msg.message());

 //     }

 //   private:

 //     typedef std::map<std::string, LpSolverBase::Col> ColMap;

 //     LpSolverBase& lp;

 //     std::string name;

 //     ColMap cols;

 //   };

 }

 #endif