// Copyright (C) 2005, International Business Machines
// Corporation and others.  All Rights Reserved.
#if defined(_MSC_VER)
// Turn off compiler warning about long names
#  pragma warning(disable:4786)
#endif

#ifdef NDEBUG
#undef NDEBUG
#endif

#include <cassert>

#include "CoinMpsIO.hpp"
#include "CoinModel.hpp"
#include "CoinHelperFunctions.hpp"
#include  "CoinTime.hpp"

//#############################################################################

/* Build a model in some interesting way
   
   Nine blocks defined by 4 random numbers
   If next random number <0.4 addRow next possible
   If <0.8 addColumn if possible
   Otherwise do by element
   For each one use random <0.5 to add rim at same time
   At end fill in rim at random

*/
void buildRandom(CoinModel & baseModel, double random, double & timeIt, int iPass)
{
  CoinModel model;
  int numberRows = baseModel.numberRows();
  int numberColumns = baseModel.numberColumns();
  int numberElements = baseModel.numberElements();
  // Row numbers and column numbers
  int lastRow[4];
  int lastColumn[4];
  int i;
  lastRow[0]=0;
  lastColumn[0]=0;
  lastRow[3]=numberRows;
  lastColumn[3]=numberColumns;
  for ( i=1;i<3;i++) {
    int size;
    size = (int) ((0.25*random+0.2)*numberRows);
    random = CoinDrand48();
    lastRow[i]=lastRow[i-1]+size;
    size = (int) ((0.25*random+0.2)*numberColumns);
    random = CoinDrand48();
    lastColumn[i]=lastColumn[i-1]+size;
  }
  // whether block done 0 row first
  char block[9]={0,0,0,0,0,0,0,0,0};
  // whether rowRim done
  char rowDone[3]={0,0,0};
  // whether columnRim done
  char columnDone[3]={0,0,0};
  // Save array for deleting elements
  CoinModelTriple * dTriple = new CoinModelTriple[numberElements];
  numberElements=0;
  double time1 = CoinCpuTime();
  for (int jBlock=0;jBlock<9;jBlock++) {
    int iType=-1;
    int iBlock=-1;
    if (random<0.4) {
      // trying addRow
      int j;
      for (j=0;j<3;j++) {
        int k;
        for (k=0;k<3;k++) {
          if (block[3*j+k])
            break; //already taken
        }
        if (k==3) {
          // can do but decide which one
          iBlock = 3*j + (int) (CoinDrand48()*0.3);
          iType=0;
          break;
        }
      }
    }
    if (iType==-1&&random<0.8) {
      // trying addRow
      int j;
      for (j=0;j<3;j++) {
        int k;
        for (k=0;k<3;k++) {
          if (block[j+3*k])
            break; //already taken
        }
        if (k==3) {
          // can do but decide which one
          iBlock = j + 3*((int) (CoinDrand48()*0.3));
          iType=1;
          break;
        }
      }
    }
    if (iType==-1) {
      iType=2;
      int j;
      for (j=0;j<9;j++) {
        if (!block[j]) {
          iBlock=j;
          break;
        }
      }
    }
    random=CoinDrand48();
    assert (iBlock>=0&&iBlock<9);
    assert (iType>=0);
    assert (!block[iBlock]);
    block[iBlock]=static_cast<char>(1+iType);
    int jRow = iBlock/3;
    int jColumn = iBlock%3;
    bool doRow = (CoinDrand48()<0.5)&&!rowDone[jRow];
    bool doColumn = (CoinDrand48()<0.5&&!columnDone[jColumn]);
    if (!iType) {
      // addRow
      int * column = new int[lastColumn[jColumn+1]-lastColumn[jColumn]];
      double * element = new double[lastColumn[jColumn+1]-lastColumn[jColumn]];
      for (i=lastRow[jRow];i<lastRow[jRow+1];i++) {
        int n=0;
        CoinModelLink triple=baseModel.firstInRow(i);
        while (triple.column()>=0) {
          if (triple.column()>=lastColumn[jColumn]&&triple.column()<lastColumn[jColumn+1]) {
            column[n]=triple.column();
            element[n++]=triple.value();
          }
          triple=baseModel.next(triple);
        }
        assert (i>=model.numberRows());
        if (i>model.numberRows()) {
          assert (i==lastRow[jRow]);
          printf("need to fill in rows\n");
          for (int k=0;k<jRow;k++) {
            int start = CoinMax(lastRow[k],model.numberRows());
            int end = lastRow[k+1];
            bool doBounds = rowDone[k];
            for (int j=start;j<end;j++) {
              if (doBounds)
                model.addRow(0,NULL,NULL,baseModel.rowLower(j),
                                baseModel.rowUpper(j),baseModel.rowName(j));
              else
                model.addRow(0,NULL,NULL);
            }
          }
        }
        if (doRow)
          model.addRow(n,column,element,baseModel.rowLower(i),
                       baseModel.rowUpper(i),baseModel.rowName(i));
        else
          model.addRow(n,column,element);
      } 
      if (doRow) {
        rowDone[jRow]=1;
      }
      delete [] column;
      delete [] element;
    } else if (iType==1) {
      // addColumn
      int * row = new int[lastRow[jRow+1]-lastRow[jRow]];
      double * element = new double[lastRow[jRow+1]-lastRow[jRow]];
      for (i=lastColumn[jColumn];i<lastColumn[jColumn+1];i++) {
        int n=0;
        CoinModelLink triple=baseModel.firstInColumn(i);
        while (triple.row()>=0) {
          if (triple.row()>=lastRow[jRow]&&triple.row()<lastRow[jRow+1]) {
            row[n]=triple.row();
            element[n++]=triple.value();
          }
          triple=baseModel.next(triple);
        }
        assert (i>=model.numberColumns());
        if (i>model.numberColumns()) {
          assert (i==lastColumn[jColumn]);
          printf("need to fill in columns\n");
          for (int k=0;k<jColumn;k++) {
            int start = CoinMax(lastColumn[k],model.numberColumns());
            int end = lastColumn[k+1];
            bool doBounds = columnDone[k];
            for (int j=start;j<end;j++) {
              if (doBounds)
                model.addColumn(0,NULL,NULL,baseModel.columnLower(j),
                                baseModel.columnUpper(j),baseModel.objective(j),
                                baseModel.columnName(j),baseModel.isInteger(j));
              else
                model.addColumn(0,NULL,NULL);
            }
          }
        }
        if (doColumn)
          model.addColumn(n,row,element,baseModel.columnLower(i),
                       baseModel.columnUpper(i),baseModel.objective(i),
                          baseModel.columnName(i),baseModel.isInteger(i));
        else
          model.addColumn(n,row,element);
      } 
      if (doColumn) {
        columnDone[jColumn]=1;
      }
      delete [] row;
      delete [] element;
    } else {
      // addElement
      // Which way round ?
      if (CoinDrand48()<0.5) {
        // rim first
        if (doRow) {
          for (i=lastRow[jRow];i<lastRow[jRow+1];i++) {
            model.setRowLower(i,baseModel.getRowLower(i));
            model.setRowUpper(i,baseModel.getRowUpper(i));
            model.setRowName(i,baseModel.getRowName(i));
          }
          rowDone[jRow]=1;
        }
        if (doColumn) {
          for (i=lastColumn[jColumn];i<lastColumn[jColumn+1];i++) {
            model.setColumnLower(i,baseModel.getColumnLower(i));
            model.setColumnUpper(i,baseModel.getColumnUpper(i));
            model.setColumnName(i,baseModel.getColumnName(i));
            model.setColumnObjective(i,baseModel.getColumnObjective(i));
            model.setColumnIsInteger(i,baseModel.getColumnIsInteger(i));
          }
          columnDone[jColumn]=1;
        }
        if (CoinDrand48()<0.3) {
          // by row
          for (i=lastRow[jRow];i<lastRow[jRow+1];i++) {
            CoinModelLink triple=baseModel.firstInRow(i);
            while (triple.column()>=0) {
              int iColumn = triple.column();
              if (iColumn>=lastColumn[jColumn]&&iColumn<lastColumn[jColumn+1])
                model(i,triple.column(),triple.value());
              triple=baseModel.next(triple);
            }
          }
        } else if (CoinDrand48()<0.6) {
          // by column
          for (i=lastColumn[jColumn];i<lastColumn[jColumn+1];i++) {
            CoinModelLink triple=baseModel.firstInColumn(i);
            while (triple.row()>=0) {
              int iRow = triple.row();
              if (iRow>=lastRow[jRow]&&iRow<lastRow[jRow+1])
                model(triple.row(),i,triple.value());
              triple=baseModel.next(triple);
            }
          }
        } else {
          // scan through backwards
          const CoinModelTriple * elements = baseModel.elements();
          for (i=baseModel.numberElements()-1;i>=0;i--) {
            int iRow = (int) elements[i].row;
            int iColumn = elements[i].column;
            if (iRow>=lastRow[jRow]&&iRow<lastRow[jRow+1]&&
                iColumn>=lastColumn[jColumn]&&iColumn<lastColumn[jColumn+1])
              model(iRow,iColumn,elements[i].value);
          }
        }
      } else {
        // elements first
        if (CoinDrand48()<0.3) {
          // by row
          for (i=lastRow[jRow];i<lastRow[jRow+1];i++) {
            CoinModelLink triple=baseModel.firstInRow(i);
            while (triple.column()>=0) {
              int iColumn = triple.column();
              if (iColumn>=lastColumn[jColumn]&&iColumn<lastColumn[jColumn+1])
                model(i,triple.column(),triple.value());
              triple=baseModel.next(triple);
            }
          }
        } else if (CoinDrand48()<0.6) {
          // by column
          for (i=lastColumn[jColumn];i<lastColumn[jColumn+1];i++) {
            CoinModelLink triple=baseModel.firstInColumn(i);
            while (triple.row()>=0) {
              int iRow = triple.row();
              if (iRow>=lastRow[jRow]&&iRow<lastRow[jRow+1])
                model(triple.row(),i,triple.value());
              triple=baseModel.next(triple);
            }
          }
        } else {
          // scan through backwards
          const CoinModelTriple * elements = baseModel.elements();
          for (i=baseModel.numberElements()-1;i>=0;i--) {
            int iRow = (int) elements[i].row;
            int iColumn = elements[i].column;
            if (iRow>=lastRow[jRow]&&iRow<lastRow[jRow+1]&&
                iColumn>=lastColumn[jColumn]&&iColumn<lastColumn[jColumn+1])
              model(iRow,iColumn,elements[i].value);
          }
        }
        if (doRow) {
          for (i=lastRow[jRow];i<lastRow[jRow+1];i++) {
            model.setRowLower(i,baseModel.getRowLower(i));
            model.setRowUpper(i,baseModel.getRowUpper(i));
            model.setRowName(i,baseModel.getRowName(i));
          }
          rowDone[jRow]=1;
        }
        if (doColumn) {
          for (i=lastColumn[jColumn];i<lastColumn[jColumn+1];i++) {
            model.setColumnLower(i,baseModel.getColumnLower(i));
            model.setColumnUpper(i,baseModel.getColumnUpper(i));
            model.setColumnName(i,baseModel.getColumnName(i));
            model.setColumnObjective(i,baseModel.getColumnObjective(i));
            model.setColumnIsInteger(i,baseModel.getColumnIsInteger(i));
          }
          columnDone[jColumn]=1;
        }
      }
    }
    // Mess up be deleting some elements
    if (CoinDrand48()<0.3&&iPass>10) {
      double random2=CoinDrand48();
      double randomDelete = 0.2 + 0.5*random2; // fraction to delete
      //model.validateLinks();
      if (random2<0.2) {
        // delete some rows
        for (int j=lastRow[jRow];j<lastRow[jRow+1];j++) {
          //model.validateLinks();
          if (CoinDrand48()<randomDelete) {
            // save and delete
            double rowLower = model.rowLower(j);
            double rowUpper = model.rowUpper(j);
            char * rowName = CoinStrdup(model.rowName(j));
            CoinModelLink triple=model.firstInRow(j);
            while (triple.column()>=0) {
              int iColumn = triple.column();
              assert (j==triple.row());
              dTriple[numberElements].row = static_cast<unsigned>(j);
              dTriple[numberElements].column=iColumn;
              dTriple[numberElements].value = triple.value();
              numberElements++;
              triple=model.next(triple);
            }
            model.deleteRow(j);
            if (rowDone[jRow]) {
              // put back rim
              model.setRowLower(j,rowLower);
              model.setRowUpper(j,rowUpper);
              model.setRowName(j,rowName);
            }
            free(rowName);
          }
        }
      } else if (random2<0.4) {
        // delete some columns
        for (int j=lastColumn[jColumn];j<lastColumn[jColumn+1];j++) {
          //model.validateLinks();
          if (CoinDrand48()<randomDelete) {
            // save and delete
            double columnLower = model.columnLower(j);
            double columnUpper = model.columnUpper(j);
            double objective = model.objective(j);
            bool integer = model.isInteger(j)!=0;
            char * columnName = CoinStrdup(model.columnName(j));
            CoinModelLink triple=model.firstInColumn(j);
            while (triple.column()>=0) {
              int iRow = triple.row();
              assert (j==triple.column());
              dTriple[numberElements].column = j;
              dTriple[numberElements].row=static_cast<unsigned>(iRow);
              dTriple[numberElements].value = triple.value();
              numberElements++;
              triple=model.next(triple);
            }
            model.deleteColumn(j);
            if (columnDone[jColumn]) {
              // put back rim
              model.setColumnLower(j,columnLower);
              model.setColumnUpper(j,columnUpper);
              model.setObjective(j,objective);
              model.setIsInteger(j,integer);
              model.setColumnName(j,columnName);
            }
            free(columnName);
          }
        }
      } else {
        // delete some elements
        //model.validateLinks();
        const CoinModelTriple * elements = baseModel.elements();
        for (i=0;i<model.numberElements();i++) {
          int iRow = (int) elements[i].row;
          int iColumn = elements[i].column;
          if (iRow>=lastRow[jRow]&&iRow<lastRow[jRow+1]&&
              iColumn>=lastColumn[jColumn]&&iColumn<lastColumn[jColumn+1]) {
            if (CoinDrand48()<randomDelete) {
              dTriple[numberElements].column = iColumn;
              dTriple[numberElements].row=static_cast<unsigned>(iRow);
              dTriple[numberElements].value = elements[i].value;
              int position = model.deleteElement(iRow,iColumn);
              if (position>=0)
                numberElements++;
            }
          }
        }
      }
    }
  }
  // Do rim if necessary
  for (int k=0;k<3;k++) {
    if (!rowDone[k]) {
      for (i=lastRow[k];i<lastRow[k+1];i++) {
        model.setRowLower(i,baseModel.getRowLower(i));
        model.setRowUpper(i,baseModel.getRowUpper(i));
        model.setRowName(i,baseModel.getRowName(i));
      }
    }
    if (!columnDone[k]) {
      for (i=lastColumn[k];i<lastColumn[k+1];i++) {
        model.setColumnLower(i,baseModel.getColumnLower(i));
        model.setColumnUpper(i,baseModel.getColumnUpper(i));
        model.setColumnName(i,baseModel.getColumnName(i));
        model.setColumnObjective(i,baseModel.getColumnObjective(i));
        model.setColumnIsInteger(i,baseModel.getColumnIsInteger(i));
      }
    }
  }
  // Put back any elements
  for (i=0;i<numberElements;i++) {
    model(dTriple[i].row,dTriple[i].column,dTriple[i].value);
  }
  delete [] dTriple;
  timeIt +=  CoinCpuTime()-time1;
  model.setLogLevel(1);
  assert (!model.differentModel(baseModel,false));
}
//--------------------------------------------------------------------------
// Test building a model
void
CoinModelUnitTest(const std::string & mpsDir,
                  const std::string & netlibDir, const std::string & testModel)
{
  
  // Get a model
  CoinMpsIO m;
  std::string fn = mpsDir+"exmip1";
  int numErr = m.readMps(fn.c_str(),"mps");
  assert( numErr== 0 );

  int numberRows = m.getNumRows();
  int numberColumns = m.getNumCols();

  // Build by row from scratch
  {
    CoinPackedMatrix matrixByRow = * m.getMatrixByRow();
    const double * element = matrixByRow.getElements();
    const int * column = matrixByRow.getIndices();
    const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();
    const int * rowLength = matrixByRow.getVectorLengths();
    const double * rowLower = m.getRowLower();
    const double * rowUpper = m.getRowUpper();
    const double * columnLower = m.getColLower();
    const double * columnUpper = m.getColUpper();
    const double * objective = m.getObjCoefficients();
    int i;
    CoinModel temp;
    for (i=0;i<numberRows;i++) {
      temp.addRow(rowLength[i],column+rowStart[i],
                  element+rowStart[i],rowLower[i],rowUpper[i],m.rowName(i));
    }
    // Now do column part
    for (i=0;i<numberColumns;i++) {
      temp.setColumnBounds(i,columnLower[i],columnUpper[i]);
      temp.setColumnObjective(i,objective[i]);
      if (m.isInteger(i))
        temp.setColumnIsInteger(i,true);;
    }
    // write out
    temp.writeMps("byRow.mps");
  }

  // Build by column from scratch and save
  CoinModel model;
  {
    CoinPackedMatrix matrixByColumn = * m.getMatrixByCol();
    const double * element = matrixByColumn.getElements();
    const int * row = matrixByColumn.getIndices();
    const CoinBigIndex * columnStart = matrixByColumn.getVectorStarts();
    const int * columnLength = matrixByColumn.getVectorLengths();
    const double * rowLower = m.getRowLower();
    const double * rowUpper = m.getRowUpper();
    const double * columnLower = m.getColLower();
    const double * columnUpper = m.getColUpper();
    const double * objective = m.getObjCoefficients();
    int i;
    for (i=0;i<numberColumns;i++) {
      model.addColumn(columnLength[i],row+columnStart[i],
                      element+columnStart[i],columnLower[i],columnUpper[i],
                      objective[i],m.columnName(i),m.isInteger(i));
    }
    // Now do row part
    for (i=0;i<numberRows;i++) {
      model.setRowBounds(i,rowLower[i],rowUpper[i]);
    }
    // write out
    model.writeMps("byColumn.mps");
  }

  // model was created by column - play around
  {
    CoinModel temp;
    int i;
    for (i=numberRows-1;i>=0;i--) 
      temp.setRowLower(i,model.getRowLower(i));
    for (i=0;i<numberColumns;i++) {
      temp.setColumnUpper(i,model.getColumnUpper(i));
      temp.setColumnName(i,model.getColumnName(i));
    }
    for (i=numberColumns-1;i>=0;i--) {
      temp.setColumnLower(i,model.getColumnLower(i));
      temp.setColumnObjective(i,model.getColumnObjective(i));
      temp.setColumnIsInteger(i,model.getColumnIsInteger(i));
    }
    for (i=0;i<numberRows;i++) {
      temp.setRowUpper(i,model.getRowUpper(i));
      temp.setRowName(i,model.getRowName(i));
    }
    // Now elements
    for (i=0;i<numberRows;i++) {
      CoinModelLink triple=model.firstInRow(i);
      while (triple.column()>=0) {
        temp(i,triple.column(),triple.value());
        triple=model.next(triple);
      }
    }
    // and by column
    for (i=numberColumns-1;i>=0;i--) {
      CoinModelLink triple=model.lastInColumn(i);
      while (triple.row()>=0) {
        assert (triple.value()==temp(triple.row(),i));
        temp(triple.row(),i,triple.value());
        triple=model.previous(triple);
      }
    }
    // check equal
    model.setLogLevel(1);
    assert (!model.differentModel(temp,false));
  }
  // Try creating model with strings
  {
    CoinModel temp;
    int i;
    for (i=numberRows-1;i>=0;i--) {
      double value = model.getRowLower(i);
      if (value==-1.0)
        temp.setRowLower(i,"minusOne");
      else if (value==1.0)
        temp.setRowLower(i,"sqrt(plusOne)");
      else if (value==4.0)
        temp.setRowLower(i,"abs(4*plusOne)");
      else
        temp.setRowLower(i,value);
    }
    for (i=0;i<numberColumns;i++) {
      double value;
      value = model.getColumnUpper(i);
      if (value==-1.0)
        temp.setColumnUpper(i,"minusOne");
      else if (value==1.0)
        temp.setColumnUpper(i,"plusOne");
      else
        temp.setColumnUpper(i,value);
      temp.setColumnName(i,model.getColumnName(i));
    }
    for (i=numberColumns-1;i>=0;i--) {
      temp.setColumnLower(i,model.getColumnLower(i));
      temp.setColumnObjective(i,model.getColumnObjective(i));
      temp.setColumnIsInteger(i,model.getColumnIsInteger(i));
    }
    for (i=0;i<numberRows;i++) {
      double value = model.getRowUpper(i);
      if (value==-1.0)
        temp.setRowUpper(i,"minusOne");
      else if (value==1.0)
        temp.setRowUpper(i,"plusOne");
      else
        temp.setRowUpper(i,value);
      temp.setRowName(i,model.getRowName(i));
    }
    // Now elements
    for (i=0;i<numberRows;i++) {
      CoinModelLink triple=model.firstInRow(i);
      while (triple.column()>=0) {
        double value = triple.value();
        if (value==-1.0)
          temp(i,triple.column(),"minusOne");
        else if (value==1.0)
          temp(i,triple.column(),"plusOne");
        else if (value==-2.0)
          temp(i,triple.column(),"minusOne-1.0");
        else if (value==2.0)
          temp(i,triple.column(),"plusOne+1.0+minusOne+(2.0-plusOne)");
        else
          temp(i,triple.column(),value);
        triple=model.next(triple);
      }
    }
    temp.associateElement("minusOne",-1.0);
    temp.associateElement("plusOne",1.0);
    temp.setProblemName("fromStrings");
    temp.writeMps("string.mps");
    
    // check equal
    model.setLogLevel(1);
    assert (!model.differentModel(temp,false));
  }
  // Test with various ways of generating
  {
    // Get a model
    CoinMpsIO m;
    std::string fn = netlibDir+testModel;
    double time1 = CoinCpuTime();
    int numErr = m.readMps(fn.c_str(),"");
    if ( numErr== 0 ) {
      printf("Time for readMps is %g seconds\n",
             CoinCpuTime()-time1);
      int numberRows = m.getNumRows();
      int numberColumns = m.getNumCols();
      // Build model
      CoinModel model;
      CoinPackedMatrix matrixByRow = * m.getMatrixByRow();
      const double * element = matrixByRow.getElements();
      const int * column = matrixByRow.getIndices();
      const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();
      const int * rowLength = matrixByRow.getVectorLengths();
      const double * rowLower = m.getRowLower();
      const double * rowUpper = m.getRowUpper();
      const double * columnLower = m.getColLower();
      const double * columnUpper = m.getColUpper();
      const double * objective = m.getObjCoefficients();
      int i;
      for (i=0;i<numberRows;i++) {
        model.addRow(rowLength[i],column+rowStart[i],
                     element+rowStart[i],rowLower[i],rowUpper[i],m.rowName(i));
      }
      // Now do column part
      for (i=0;i<numberColumns;i++) {
        model.setColumnBounds(i,columnLower[i],columnUpper[i]);
        model.setColumnObjective(i,objective[i]);
        model.setColumnName(i,m.columnName(i));
        if (m.isInteger(i))
          model.setColumnIsInteger(i,true);;
      }
      // Test
      CoinSeedRandom(11111);
      time1 = 0.0;
      int nPass=50;
      for (i=0;i<nPass;i++) {
        double random = CoinDrand48();
        int iSeed = (int) (random*1000000);
        //iSeed = 776151;
        CoinSeedRandom(iSeed);
        printf("before pass %d with seed of %d\n",i,iSeed);
        buildRandom(model,CoinDrand48(),time1,i);
        model.validateLinks();
      }
      printf("Time for %d CoinModel passes is %g seconds\n",
             nPass,time1);
    }
  }
}





