#include <cstdlib>
#include <iostream>
#include <cmath>
#include "simplex.h"

using namespace std;

simplex::simplex(const vector<fracao> & c, const vector<fracao> & b, const vector< vector<fracao> > & A){
          n=c.size();
          m=b.size();
          linhaFO.resize(m+n);
          valores.resize(m);
          for (size_t i = 0; i <m; i++){
              if (b[i] < nula){
              	 cout << "o coeficiente e negativo" << endl;
                 system ("PAUSE");
                 exit (1);
              }
          }
          for(size_t i=0; i<m; i++){
          vector <fracao> h;
              for(size_t j=0; j<n+m; j++){
                      fracao nula1;
                      h.push_back(nula1);
              }
              quadro.push_back(h);
          }
          fracao nula2;
          for(size_t i=0; i<n; i++) linhaFO[i]=-c[i];
          for(size_t i=n; i<n+m; i++) linhaFO[i]=nula;
          for(size_t i=0; i<m; i++) valores[i]=b[i];

          for(size_t i=0; i<m; i++){
              for(size_t j=0; j<n; j++){
                      quadro[i][j]=A[i][j];
              }
          }
          for(size_t i=0; i<m; i++){
              for(size_t j=n; j<n+m; j++){
                      quadro[i][j] = 0;
              }
          }
          for(size_t i=0; i<m; i++){
             quadro[i][n+i]=1;
          }
          for(size_t i=n; i<m+n;i++){
             VB.push_back(i+1);
          }
          fracao nula;
          Z=nula;
}

void simplex :: resolver (){

    int menores = 2;
    iteracoes =0;

    while(menores != 0){

	int entra = 0;
        fracao nula;
        for (size_t i =1; i < n+m; i++){
            if (linhaFO[entra]<nula && linhaFO[i]<nula){
                        if (linhaFO[entra] > linhaFO[i]) entra = i;
            }
            else if (linhaFO[entra]>nula && linhaFO[i]<nula){
                     entra = i;
            }
      //cout << "entra = " << entra+1 << endl;

        }
        int escolhidos =0;
        int sai =0;
        while (escolhidos < 1){
        //cout << "tou dentro do while!!!" << endl;
        for (size_t i =0; i<m; i++){
        	//cout << "tou dentro do for!!!" << endl;

                  if (quadro[i][entra] > nula) {
                  	 //cout << "tou dentro do if!!!" << endl;
                     sai = i;
                     cout << "i = " << i << endl;
                     escolhidos ++;
                  }
            }
        }
        //cout << "sai = " << sai+1 << endl;
        for (size_t i =0; i<m; i++){

            if (quadro [i][entra] >nula){

            	//cout << "quadro [i][entra] = " << quadro [i][entra] << endl;
                if (valores[sai]/quadro[sai][entra] > valores[i]/quadro [i][entra]) sai = i;
                //cout << "valores / quadro = " << valores[sai]/quadro[sai][entra] << " e  valores[i]/quadro [i][entra] = " << valores[i]/quadro [i][entra] << endl;
        	}
        }

    fracao pivot;
    pivot = quadro[sai][entra];
    //cout << " sai = " << sai + 1 << endl;
    //cout << " entra = " << entra + 1 << endl;
    //cout << "o pivot e " << pivot << "!!!!! " << endl;

    VB [sai] = entra + 1;
    for (size_t i =0; i<m; i++){
	//cout << " VB [i] = " << VB[i] << endl;
	}

	Z = Z - ((valores[sai]*linhaFO[entra])/pivot);
    //cout << " Z = " << Z << endl ;

	for (size_t i = 0; i < m+n; i++){
		  if (int (i) != entra){
		  //cout << "linhaFO [i]" << linhaFO[i] << " - quadro[sai][i] " << quadro[sai][i] << " * linhaFO[entra]" << linhaFO[entra] << " / PIVOT " << pivot<< endl;
          linhaFO[i] = linhaFO [i] - ((quadro[sai][i]*linhaFO[entra])/pivot);
      	  }
    }
	linhaFO[entra]=nula;
	//cout << "linhaFO[entra]" << linhaFO[entra];
    for (size_t i = 0; i < m+n; i++){
          //cout << "linhaFO[i] = "<< linhaFO[i] << endl ;
    }

	for (size_t i = 0; i < m; i++){
          if (int (i) != sai){
		  valores [i] = valores [i] - ((quadro[i][entra]*valores[sai])/pivot);
          //cout << "valores [i] =  " << valores[i] << endl;
      	  }
    }

    for (size_t i = 0; i < m; i++){
      for (size_t j=0; j < n+m; j++){
          if (int(i)!= sai && int(j)!= entra) {
		  quadro [i][j] = quadro [i][j] - ((quadro[i][entra]*quadro[sai][j])/pivot);
      	  }
	  }
	}

    for (size_t i = 0; i < m; i++){
    	  if (int (i) != sai) quadro [i][entra] = nula;
	}

    for (size_t i= 0; i < m+n; i++){
      quadro [sai][i] = quadro[sai][i]/pivot;
    }

    for (size_t i = 0; i < m; i++){
      for (size_t j=0; j < n+m; j++){
        //cout << "quadro[" << i+1 << "][" << j+1 << "] = " << quadro[i][j] << endl;
      }
    }

    for (size_t i= 0; i < m+n; i++){
      //cout << "quadro [sai][i]/pivot = " << quadro [sai][i] << endl;
    }
    valores[sai] = valores[sai]/pivot;
      //cout << "valores [sai] = " << valores [sai] << endl;


	//fracao nula;
    menores=0;
    for (size_t i =0; i < n+m; i++){
          if (linhaFO [i] < nula) menores++;
    }
    cout << "menores = " << menores << endl;
	iteracoes ++;
	if (iteracoes > 50){
		cout << "e degenerado!!!!!!!!!, o valor de uma variavel basica é zero, o que leva a um ciclo infinito de repeticoes " << endl;
		system ("PAUSE");
		exit (1);
	}
    }
    cout << "interacoes = " << iteracoes;
}


ostream &operator <<(ostream & os , const simplex & A ){
    os << " VB ";
    for (size_t i = 0; i< A.m+A.n; i++){
        os << "|  x" << i + 1 << "  ";
    }
    os << "|  Valores";
    os << endl;
    os << "------------------------------------------------------------------" << endl;
    os << " Z  ";
    for (size_t i = 0; i< A.m+A.n; i++){
          os << "|   " << A.linhaFO[i] << "  ";
    }
    os << "|  " << A.Z << endl;
    os << "------------------------------------------------------------------" << endl;
    for (size_t i=0; i < A.m; i++){
        os << " X" << A.VB[i] << " |";
        for (size_t j=0; j < A.m+A.n; j++){
            os << "    " << A.quadro [i][j] << "  ";
        }
    os << " |  " << A.valores [i] << endl;
    }
    return os;
}

void simplex :: solucao (){
	for (size_t i=0; i < m; i++){
		cout<< "X " << VB[i] << " = " << valores[i] << endl;
	}

	cout << "Z = " << Z << endl;

	cout << "Foram feitas " << iteracoes << " iteracoes!" << endl;
}