// Simplex.cpp: implementation of the Simplex class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Optima.h"
#include "Simplex.h"
#include "Fraction.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Simplex::Simplex()
{

}

Simplex::~Simplex()
{

}


void Simplex::FillSimplexTable()
{

no_of_svars=no_of_avars=0;

int i,j;
	char buffer[80];



//_______Check if some element in B is negative
for(i=0;i<no_of_const;i++)
{

	if (B[i]<(Fraction)0)
	{
		B[i]=-B[i];
		for(j=0;j<no_of_vars;j++)
			A[i][j]=-A[i][j];
		const_type[i]=-const_type[i];
	}
}



	no_of_rvars=no_of_vars;
//AfxMessageBox("Checking Vars");

//______Now check var consts________
	Fraction temp[MAX_VAR*2];
	int tnv=0;
	 j=0;
	//______Change C Matrix
	for(i=0;i<no_of_vars;i++)
	{
		
		if(var_const[i]==1) 
		{
			temp[j++]=C[i];
		//	AfxMessageBox(CString(C[i]));
			tnv++;
		}
		if(var_const[i]==2) 
		{
			temp[j++]=-C[i];
			tnv++;
		}
		if(var_const[i]==3) 
		{
			temp[j++]=C[i];
			temp[j++]=-C[i];
			tnv+=2;
		}
	}
	
	for(i=0;i<tnv;i++)
		C[i]=temp[i];


	//_________A Matrix______________
	for(int k=0;k<no_of_const;k++)
	{
	int j=0;

	//_________Each row of A
	//______Change A Matrix
	for(i=0;i<no_of_vars;i++)
	{
		if(var_const[i]==1) 
		{
			temp[j++]=A[k][i];
		
		}
		if(var_const[i]==2) 
		{
			temp[j++]=-A[k][i];
		
		}
		if(var_const[i]==3) 
		{
			temp[j++]=A[k][i];
			temp[j++]=-A[k][i];
	
		}
	}
	
	for(i=0;i<tnv;i++)
		A[k][i]=temp[i];


	}

	no_of_vars=tnv;



//	itoa(no_of_vars,buffer,10);
//	AfxMessageBox(CString(buffer));
	

	



//____________know no of slack_vars and art_vars______
for(i=0;i<no_of_const;i++)
{
	if(const_type[i]) no_of_svars++; //_____Inequality_______
	if(const_type[i]<=0) no_of_avars++;
}

total_vars=no_of_vars+no_of_svars+no_of_avars;


	
int s=0,a=0;	
int count=0;

//_______Fill the table_______
for(i=0;i<no_of_const;i++)
{
	
	table[i][0]=B[i];
	
	for(j=0;j<no_of_vars;j++)
		table[i][j+1]=A[i][j];

	for(j=no_of_vars;j<total_vars;j++)
		table[i][j+1]=0;

	//Now fill in the slack and the artificial variables
	if(const_type[i])  //_For slack variable
	{
		s++;
		table[i][no_of_vars+s]=(float)const_type[i];
		if(const_type[i]==1) 
		{
			basic_vars[i]=no_of_vars+s;
			C2[count++]=0;
		}
	}
	
	if(const_type[i]<=0) //______For artificial variable
	{
		a++;
		table[i][no_of_vars+no_of_svars+a]=1;
		basic_vars[i]=no_of_vars+no_of_svars+a;
		C2[count++]=-1;

	}
	
}



//__________Set Phase_______
if(no_of_avars>0) 
	phase_no=2;
else 
	phase_no=1;


//_______Fill the last row__________
if(phase_no==1)
{

table[no_of_const][0]=0;  //Z=0
for(j=0;j<total_vars;j++)
{
	if(j<no_of_vars)
	{
		table[no_of_const][j+1]=-C[j];

	}
	if(j>=no_of_vars)
	{
		table[no_of_const][j+1]=0;

	}

}

}
else  //_______if phase = 2
{
	for(j=0;j<=total_vars;j++)
	{
		if(j<=(no_of_vars+no_of_svars))
		{
			Fraction sum=0;
			for(int k=0;k<no_of_const;k++)
			{
				sum=sum+(Fraction)(table[k][j]*C2[k]);
				table[no_of_const][j]=sum;
			}

		}
		else
		{
		table[no_of_const][j]=0;
		}
	}
}
}

int Simplex::Iterate()
{
	char buffer[20];
	int mincol=ReturnMin();

	int i,j,k,l;
	
//	itoa(mincol,buffer,10);
//	AfxMessageBox(CString(buffer));

	//_______Check if optimality reached____
	if(table[no_of_const][mincol]>=Fraction(0)) 
	{
	
		if(phase_no==1)
			return 1;  //___Succesful

		if(phase_no==2)
		{
			if(table[no_of_const][0]!=Fraction(0))
				return -1;
			else //______Phase 1 has ended
			{
				phase_no=1;

				total_vars-=no_of_avars;
				//_______Change Last row____
				for(i=0;i<=total_vars;i++)
				{
					Fraction sum=0;

					for(j=0;j<no_of_const;j++)
					{
						sum=sum+C[basic_vars[j]-1]*table[j][i];
					}

					//_____Subtract Cj for objective vars
					if(i>0 && i<=no_of_vars)
						sum=sum-C[i-1];

					table[no_of_const][i]=sum;
				}


				return -2;
			}
		}

	}


	//________Now Iterate Table
	
	int pivotcol,pivotrow;

	pivotcol=mincol;
	
	//_____Find pivotrow
	pivotrow=0;
	Fraction min=9999999;
	
	int unbounded_flag=1;
	for(i=0;i<no_of_const;i++)
	{
		Fraction temp=table[i][0]/table[i][mincol];

		
		if(temp<min && table[i][mincol]>(Fraction)0)
		{
			min=temp;
			pivotrow=i;
			unbounded_flag=0;
		}
	}

	if(unbounded_flag) return 2;

	//_______Pivotrow and pivotcol have been found___

	//______Change basic variable
	basic_vars[pivotrow]=pivotcol;

	Fraction pivotelement=table[pivotrow][pivotcol];

	//AfxMessageBox((CString)"Pivot Element ="+pivotelement);


	//______Divide pivot row by pivot element
	for(i=0;i<=total_vars;i++)
		table[pivotrow][i]/=pivotelement;

	//______Perform row operations on other rows

	Fraction mult_factor;


	
	for(i=0;i<=no_of_const;i++)
	{
		if(i!=pivotrow)
		{
			mult_factor=table[i][pivotcol]/table[pivotrow][pivotcol];

			//AfxMessageBox("MFactor "+(CString)mult_factor);

			//_gcvt(mult_factor,5,buffer);
			//AfxMessageBox(CString(buffer));
			//________Change row ________
			for(j=0;j<=total_vars;j++)
				table[i][j]=table[i][j]-mult_factor*table[pivotrow][j];
		}
	}


	return 0;

}


//_____Returns colno in of min zj-cj in table
int Simplex::ReturnMin()
{

	Fraction t=table[no_of_const][1];
	int n=1;

	for(int i=1;i<=total_vars;i++)
		if(table[no_of_const][i]<t) 
		{
			t=table[no_of_const][i];
			n=i;
		}

	return n;

}



void Simplex::GenerateSolution()
{

	int i,j,k;

	for(i=0;i<=no_of_vars;i++)
		finalsol[i]=0;

	for(i=0;i<no_of_const;i++)
	{
		finalsol[basic_vars[i]]=table[i][0];
	}

	 j=1;
	for(i=1;i<=no_of_rvars;i++)
	{
		if(var_const[i-1]==1) 
		{
			finalsol[i]=finalsol[j++];
		};
		if(var_const[i-1]==2) 
		{
			finalsol[i]=-finalsol[j++];
			
		}
		if(var_const[i-1]==3) 
		{
			finalsol[i]=finalsol[j]-finalsol[j+1];
			j+=2;
			
		}

	}

	finalsol[0]=table[no_of_const][0];
	

}