#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>  //para limitar casas decimais print do float

using namespace std;



//Tipos criados
typedef vector< vector<float> > Matrix;
typedef vector<float> Row;
typedef vector<float> Values;


//Variaveis
int numeroRestricoes = 0;
bool maximizacao = false;
int escolha = 0;

int numeroVariaveis = 0;
float coefVariavel = 0;
int colunaPivo = 0;
int linhaPivo = 0;
float coefPivoDeCadaLinha = 0;
float menorElementolinhaZ = 0;
float menorElementoColunaDivisaoLD = 0;
float elementoPivo = 0;
bool continuarExecucao = true;
int numeroIteracoes = 0;
bool houveErros = false;

vector<int> colunaVariaveis(0, 0); //variaveis atualmente na tabela
vector<int> linhaVariaveis(0, 0); // todas variaveis
Matrix matrix;
Matrix tabelaSimplex;
Values colunaValores;
Values linhaZ;


//Funcoes
void menu();
void preencherMatriz();
void imprimirMatriz();
void preencherValoresRestricao();  // preencher coluna apos o "="
void aplicarSimplex();
void preencheLinhaZ();
void imprimeLinhaZ();
void imprimeLinhaZcomVariaveis();
void procuraMenorValorLinhaZ();
void posicionarVariaveisDeFolga();
void imprimeMatrizSimplex();
void procuraLinhaPivo();
void trocaLinhaPivoPorColunaPivo();
void alterarLinhas();
void imprimeResultados();
bool verificarFinal();

/// Main code
int main() {
	menu();

	system("PAUSE");
	return 0;
}



void menu() {
	cout << "Defina qual o tipo do problema:" << endl << "1 - Maximizacao" << endl << "2 - Minimizacao" << endl;
	cin >> escolha;
	if (escolha == 1) { maximizacao = true; }
	else { maximizacao = false; }
	cout << "Numero de restricoes: " << endl;
	cin >> numeroRestricoes;
	cout << "Informe o numero de variaveis: " << endl;
	cin >> numeroVariaveis;

	cout << fixed;
	cout << setprecision(3); //limita print do float para 4 casas

	preencheLinhaZ();
	preencherMatriz();
	preencherValoresRestricao();
	imprimirMatriz();
	imprimeLinhaZcomVariaveis();
	aplicarSimplex();

}

void preencheLinhaZ() {
	int aux = 0;
	cout << "Infome a equacao Z:" << endl;
	for (size_t i = 0; i < numeroVariaveis; i++) {
		cout << "Coeficiente de X" << i << ":" << endl;
		cin >> aux;
		linhaZ.push_back(aux);
	}
}

void imprimeLinhaZcomVariaveis() {
	cout << endl << "-----------------------------------------------------------------" << endl;
	cout << "Z:";
	for (size_t i = 0; i < numeroVariaveis; i++) {
		cout << linhaZ[i] << "X" << i << " ";
	}
	cout << endl;
}

void imprimeLinhaZ() {
	cout << endl << "-----------------------------------------------------------------" << endl;
	for (size_t i = 0; i < numeroVariaveis + numeroRestricoes+1; i++) {
		cout << linhaZ[i] << "\t";
	}
	cout << endl;
}


void preencherMatriz() {
	for (size_t i = 0; i < numeroRestricoes; ++i)
	{
		cout << "Restricao " << i << ":" << endl;
		Row row(numeroVariaveis);
		for (size_t j = 0; j < numeroVariaveis; ++j)
		{
			cout << "Coeficiente da variavel x" << j << ": ";
			cin >> coefVariavel;
			row[j] = coefVariavel;
		}
		matrix.push_back(row); // coloca a linha na matriz apos ser preenchida
	}
}

void preencherValoresRestricao() {
	//Values colunaValores(numeroRestricoes);
	cout << "Informe os valores apos o '>=' ou '<=' " << endl;
	int aux = 0;
	for (size_t i = 0; i < numeroRestricoes; i++) {
		//para cada restricao, adicionar um valor apos o =
		cout << "Restricao " << i << ": ";
		cin >> aux;
		colunaValores.push_back(aux);
	}
}

void imprimirMatriz() {
	cout << endl << "-----------------------------------------------------------------" << endl;
	cout << "Matriz de restricoes: " << endl;
	for (size_t i = 0; i < numeroRestricoes; ++i) {
		for (size_t j = 0; j < numeroVariaveis; ++j) {
			cout << matrix[i][j] << " ";
			if (numeroVariaveis == j+1) {
				if (maximizacao) { cout << ">= " << colunaValores[i] << endl; }
				else { cout << "<= " << colunaValores[i] << endl; }
			}
		}
	}
	cout << endl;
}

void procuraMenorValorLinhaZ() {
	for (size_t i = 0; i < numeroVariaveis + numeroRestricoes; i++) {
		if (i == 0) {
			colunaPivo = i;
			menorElementolinhaZ = linhaZ[0];
		} //sendo o primeiro a verificar, sera o menor
		else {
			if (linhaZ[i]<linhaZ[colunaPivo]) {
				colunaPivo = i;
				menorElementolinhaZ = linhaZ[colunaPivo];
			}
		}
	}
}

void posicionarVariaveisDeFolga() {
	int contadorvariaveis = numeroVariaveis;
	for (size_t i = 0; i < numeroRestricoes; i++) {
		contadorvariaveis++; //posicao onde sera colocada a variavel de folga
		for (size_t j = numeroVariaveis + 1; j <= numeroVariaveis + numeroRestricoes; j++) {
			if (j == contadorvariaveis) { tabelaSimplex[i].push_back(1); }
			else { tabelaSimplex[i].push_back(0); }
		}
		tabelaSimplex[i].push_back(colunaValores[i]);
	}
}

void imprimeMatrizSimplex() {
	cout << endl << "-----------------------------------------------------------------" << endl;
	cout << "Matriz do Simplex: " << endl;
	imprimeLinhaZ();
	for (size_t i = 0; i < numeroRestricoes; ++i) {
		for (size_t j = 0; j<(numeroVariaveis + numeroRestricoes + 1); j++) {
			cout << tabelaSimplex[i][j] << "\t";
		}
		cout << endl;
	}
}

void procuraLinhaPivo() {
	//cout << endl << "Tamaho de cada linha: " << tabelaSimplex[0].size(); //para acessar, usar tamanho-1 pois indice comeca em 0
	int indiceUltimoElemento = tabelaSimplex[0].size() - 1;
	float aux = 0;
	bool todosValoresNegativos = true;
	for (size_t i = 0; i < numeroRestricoes; i++) {
		if ((tabelaSimplex[i][colunaPivo]) > 0) {
			todosValoresNegativos = false; //entrou uma vez, ha um valor positivo na coluna pivo
			if (i == 0) {
				menorElementoColunaDivisaoLD = (tabelaSimplex[0][indiceUltimoElemento]) / (tabelaSimplex[0][colunaPivo]);
				linhaPivo = 0;
			}
			else {
				aux = (tabelaSimplex[i][indiceUltimoElemento]) / (tabelaSimplex[i][colunaPivo]);
				if (aux < menorElementoColunaDivisaoLD) {
					menorElementoColunaDivisaoLD = aux;
					linhaPivo = i;
				}
			}
		}
	}
	if (todosValoresNegativos) { continuarExecucao = false; }
	elementoPivo = tabelaSimplex[linhaPivo][colunaPivo];
	cout << "Elemento pivo: " << elementoPivo << endl;

	if (elementoPivo == 0) {
		cout << "Erro! Elemento Pivo é zero!";
		continuarExecucao = false;
	};
}

void trocaLinhaPivoPorColunaPivo() {
	//dividir a linhaPivo pelo elemento pivo
	int tamanhoLinha = tabelaSimplex[0].size();
	for (size_t i = 0; i < tamanhoLinha; i++) {
		if(elementoPivo != 0){ tabelaSimplex[linhaPivo][i] = (tabelaSimplex[linhaPivo][i]) / elementoPivo; }
		else { tabelaSimplex[linhaPivo][i] = 0; }
	}
	
	colunaVariaveis[linhaPivo] = linhaVariaveis[colunaPivo];
}

void alterarLinhas() {
	int tamanhoLinha = tabelaSimplex[0].size();
	for (size_t i = 0; i < numeroRestricoes; i++) {
		if (i != linhaPivo) {
			coefPivoDeCadaLinha = tabelaSimplex[i][colunaPivo]; //salva coef pra cada linha, para nao ser alterado durante calculos
			for (size_t j = 0; j < tamanhoLinha; j++) {
				 tabelaSimplex[i][j] = (tabelaSimplex[i][j]) - ((coefPivoDeCadaLinha) * tabelaSimplex[linhaPivo][j]);
			}
		}
	}
	coefPivoDeCadaLinha = linhaZ[colunaPivo];
	for (size_t i = 0; i < tamanhoLinha;i++) {
		linhaZ[i] = linhaZ[i] - (coefPivoDeCadaLinha * tabelaSimplex[linhaPivo][i]);
	}
}

bool verificarFinal() {
	int tamanhoLinha = linhaZ.size();
	for (size_t i = 0; i < tamanhoLinha; i++) {
		if (linhaZ[i] < 0) {
			return true; 
		}
	}
	return false;
}

void imprimeResultados() {
	int indiceUltimoElemento = tabelaSimplex[0].size() - 1;
	cout << endl << "Variaveis atualmente na tabela: " << endl;
	cout << fixed;
	cout << setprecision(0); //limita print do float para 4 casas
	cout << "Z = " << linhaZ[indiceUltimoElemento] << endl;
	cout << fixed;
	cout << setprecision(3); //limita print do float para 4 casas
	for (size_t i = 0; i < numeroRestricoes; i++) {
		cout << "X" << colunaVariaveis[i] << "=" << tabelaSimplex[i][indiceUltimoElemento] << endl;
	}
}

void aplicarSimplex() {
	//posicionar os 0 da variaveis de folga em Z e do LD
	for (size_t i = 0; i < numeroRestricoes+1; i++) {
		linhaZ.push_back(0);
	}
	cout << "Aplicando variaveis de folga e movendo todos coeficientes para mesmo lado da equacao:" << endl << "Z ";
	for (size_t i = 0; i < numeroVariaveis+numeroRestricoes; i++) {
		linhaZ[i] = linhaZ[i] * (-1);
		cout << linhaZ[i] << "X" << i << " ";
	}

	//Coluna das variaveis presentes na tabela, no comeco, é somente as variaveis de folga
	for (size_t i = numeroVariaveis; i < numeroVariaveis + numeroRestricoes; i++) {
		colunaVariaveis.push_back(i); //coloca os indices de qual variavel esta na coluna. ex: 3 variaveis (0 a 2), vai adicionar as variaveis a partir da 3, qeu sao as de folga
	}
	for (size_t i = 0; i < numeroVariaveis + numeroRestricoes;i++) {
		linhaVariaveis.push_back(i); //indices de todas variaveis
	}

	//Monta tabela do simplex
	tabelaSimplex = matrix;

	//Posicionar variaveis de folga
	posicionarVariaveisDeFolga();

	//Imprimir matriz do simplex e linha Z acima
	imprimeMatrizSimplex();

	//Loop de iteracoes

	while (continuarExecucao) {
		cout << endl << "-----------------------------------------------------------------" << endl;
		cout << "Iteracao " << numeroIteracoes << ":" << endl;
		numeroIteracoes++;

		//procura menor valor de Z
		procuraMenorValorLinhaZ();
		cout << "Menor valor da linha Z: " << menorElementolinhaZ << " Com indices i: 0 e j: " << colunaPivo << endl;

		//Dividir cada valor do LD (lado direito) pelo valor da coluna pivo e achar o menor destas divisoes. Assim acha o elemento pivo
		procuraLinhaPivo();

		//Se o elemento pivo encontrado foi zero, a execucao deve parar
		if (!continuarExecucao) { break; }


		//Trocar linhaPivo por ColunaPivo
		trocaLinhaPivoPorColunaPivo();

		//Aplicar iteracao ao resto das linhas
		alterarLinhas();

		//Imprimir nova tabela
		imprimeMatrizSimplex();

		//Verifica se existe valor negativo em Z, se houver repete todos os passos, senao tem a resposta
		continuarExecucao = verificarFinal();
	}

	if (!houveErros) { imprimeResultados(); };
}