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