/*
 Name: Resvised Simplex Method
 Author: Rhohitman
 Date: 24/08/09 20:46
*/
 
# define TestModePassed
//# define CmdDis
 
# include <iostream>
using namespace std;
 
#ifdef MSWin
	#include<conio.h>
	#define cls system("cls")
#else
	#define cls system("clear")
 
	#include <termios.h>
	#include <unistd.h>
 
	int getch()
	{
		struct termios oldt,
		newt;
		int ch;
		tcgetattr(STDIN_FILENO, &oldt);
		newt= oldt;
		newt.c_lflag &= ~(ICANON| ECHO);
		tcsetattr(STDIN_FILENO, TCSANOW, &newt);
		ch=getchar();
		tcsetattr(STDIN_FILENO, TCSANOW, &oldt);
		return ch;
	}
 
	int getche()
	{
		int ch=getch();
		cout<<ch;
		return ch;
	}
#endif
 
# include <cstdlib>
 
# include <cmath>
 
# ifdef CmdDis
	# include <windows.h>
	HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
 
	void gotoxy(short,short);
	COORD findcursor(short *, short *);
 
	# define TxtAttrib(x) SetConsoleTextAttribute(hConsole, x)
	# define TagColor 11
/*
# else
	# define TxtAttrib(x)
	# define TagColor
*/
# endif
 
short x, y;
# define loop_limit 5
 
# define dtab 7
# define fix 2
 
char FRAC=0;
 
enum method { halt=0, maximize='1', minimize='2', dualmini='3', integer='9' };
 
typedef struct Table *Tptr;
struct Table
{
	unsigned short n, b, a;
					char* rTag; //attrib row tag
					float* C1;	float* C2;		float R;
	char* bvTag;	float* A;	float* BInv;	float* r;
 
	Table(short, short, short);
	Table(Tptr);
	void reveal();
};
 
Table::Table(short N, short B, short Ar)
{
	n=N;	b=B;	a=Ar;
				rTag=NULL;
				C1=NULL;	C2=NULL;
	bvTag=NULL;	A=NULL;		BInv=NULL;	r=NULL;
}
 
Table::Table(Tptr scr)
{
	n=scr->n; b=scr->b; a=scr->a;
 
	rTag = (char*)calloc(sizeof(char), 2*(b+n+a)+1);
	for(x=0; x<2*(b+n+a); x++) *(rTag+x)=*(scr->rTag+x);
	*(rTag+x)='\0';
 
	bvTag = (char*)calloc(sizeof(char), 2*b+1);
	for(x=0; x<2*b; x++) *(bvTag+x)=*(scr->bvTag+x);
	*(bvTag+x)='\0';
 
	C1=NULL;	C2=NULL;
	A=NULL;		BInv=NULL;	r=NULL;
}
 
void Table::reveal()
{
	cout<<"\nTable: "<<this;
	printf("\n\tn: %d b: %d a: %d", n, b, a);
	printf("\n\trTag: %p\tbvTag: %p", (void*)rTag, (void*)bvTag);
	cout<<"\n\tC1: "<<C1<<"\tC2: "<<C2<<" \tR: "<<R;
	cout<<"\n\tA: "<<A<<"\tBInv: "<<BInv<<"\tr: "<<r;
}
 
# define can_i_stop \
{\
	loop_count++;\
	if(loop_count>loop_limit)\
	{\
		printf("Get OFF !! off limit");\
		return 0;\
	}\
}
 
class RSimplex
{
	private:
		Tptr tb;
		short i, j;
		unsigned short pivot_i, pivot_j;
 
		float pivot;
		float Temp1, Temp2;
 
		float* Ex;
		float* Te;
		float* Cb;
		Tptr TTemp;
 
		char loop_count;
 
	public:
		void show(Tptr);
 
		void next_table(Tptr, Tptr);
 
		Tptr basicMax(Tptr);
		Tptr dualMin(Tptr);
		Tptr cutPlane(Tptr);
 
		void menu(char);
		char Samples(char);
		void TM_sim_max();
		void TM_dual_min();
		void TM_cut_plane();
};
 
int dtemp=1;
int ret;
 
int Dec2Fra(float dec_part)
{
	int int_part=(int)dec_part;
	dec_part-=int_part;
 
	if(dec_part<0.005) return int_part;
 
	ret=Dec2Fra(1/dec_part);
 
	int_part*=ret;
	int_part+=dtemp;
 
	dtemp=ret;
	return int_part;
}
 
char pfrac[6];
float diff;
void pno(float no)
{
	if(FRAC==1) goto kick;
	diff=no-(int)no;
	if(diff!=0 && fabs(diff)>.0005)
	{
		dtemp=1;
		if(no<0) sprintf(&pfrac[0], "-%d/%d", Dec2Fra(-no), dtemp);
		else sprintf(&pfrac[0], "%d/%d", Dec2Fra(no), dtemp);
		printf("%*s", dtab, pfrac);
	}
	else
kick:
	printf("%*.*f", dtab, fix, no);
}
 
float* matrixMul(float* M1, short I, short K, float* M2, short L, short J)
{
	if(K!=L)
	{
		printf(" %d,%d\t%d,%d ",I,K,L,J);
		cout<<"Error!! Incompatible Matrix\n";
		getch();
		return NULL;
	}
 
	float* M3=(float*)calloc(sizeof(float), I*J);
 
	for(short i=0;i<I;i++) //{
		for(short j=0;j<J;j++) //{
			for(short m=0;m<K;m++)
				*(M3+i*J+j)+= *(M1+i*K+m) * (*(M2+m*J+j));
			//pno(*(M3+i*J+j)); } cout<<endl; }
	return M3;
}
 
float* matrixAdd(float* M1, float* M2, short I, short J)  
{
	float* M3=(float*)calloc(sizeof(float), I*J);
	for(short i=0;i<I*J;i++) *(M3+i) = *(M1+i) + *(M2+i);    
 
	return M3;
}
 
void RSimplex::show(Tptr T)
{
#ifdef TestMode
	T->reveal();
#endif
 
	if(T==NULL)
	{
		cout<<"\nError!! No Table Found... Null Pointer\n";
		return;
	}
 
	printf("\n%*c", dtab,32);
 
# ifdef CmdDis
	TxtAttrib(TagColor);
# endif
 
	for(i=0; i< 2*((T->n)+(T->a)+(T->b)); i=i+2)
		printf("%c%*c", *(T->rTag+i), -dtab+1,*(T->rTag+i+1));
	printf("RHS\n z");
 
# ifdef CmdDis
	TxtAttrib(7);
# endif
 
	for(j=0; j<T->n; j++) pno(*(T->C1+j));
	for(j=0; j<T->b; j++) pno(*(T->C2+j));
	printf(" %c", 221);
	pno(T->R);
 
	for(i=0; i<T->b; i++)
	{
# ifdef CmdDis
		TxtAttrib(TagColor);
# endif
		printf("\n%c%c", *(T->bvTag+i*2), *(T->bvTag+1+i*2));
# ifdef CmdDis
		TxtAttrib(7);
# endif
		for(j=0; j<T->n; j++) pno(*(T->A+i*T->n+j));
		for(j=0; j<T->b; j++) pno(*(T->BInv+i*T->b+j));
		printf(" %c", 221);
		pno(*(T->r+i));
	}
# ifdef CmdDis
	findcursor(&x,&y);
# endif
}
 
Tptr RSimplex::cutPlane(Tptr T1)
{
	T1->reveal();
 
	cout<<"\n\nInteger Progam: ";
	Temp2=0;
 
	for(i=0; i<T1->b; i++)
	{
		Temp1=*(T1->r+i)-(int)*(T1->r+i);
		if(Temp1>Temp2)
		{
			Temp2=Temp1;
			pivot_i=i;
		}
	}
 
	if(Temp2==0.0 && Temp2 < .0005)
	{
		cout<<"\n>Solution is in approximate integer value";
		return T1;
	}
 
	cout<<"\n\nNew Table Creation>";
	Tptr T2=new Table(T1->n,T1->b+1,0); //allocating memory as size of T1
 
	T2->reveal();
 
	T2->rTag = (char*)calloc(sizeof(char), 2*((T2->n)+(T2->b)+(T2->a))+1);
	T2->bvTag = (char*)calloc(sizeof(char), 2*(T2->b)+1);
 
	T2->C2 = (float*)calloc(sizeof(float), (T2->b));
	T2->r = (float*)calloc(sizeof(float), (T2->b));
 
	T2->R=T1->R;
 
	char *marker=(char*)calloc(sizeof(char), (T2->n)+(T2->b)+(T2->a)+1);
 
	T2->A = (float*)calloc(sizeof(float), (T2->n)*(T2->b));
	T2->BInv = (float*)calloc(sizeof(float), (T2->b)*((T2->b)+(T2->a)));
 
//Basic Variables
	x=0;
	for(i=0; i<(T1->n)+(T1->b)+(T1->a); i++)
	{
		*(marker+i)='N';
		if(x<T1->b)
		{
			for(j=0; j< (T1->b); j++)
			{
				if(*(T1->rTag+2*i+1)!=*(T1->bvTag+2*j+1)) continue;
 
				*(marker+i)='F';
				*(T2->bvTag+2*x)=*(T1->bvTag+2*j);
				*(T2->bvTag+2*x+1)=*(T1->bvTag+2*j+1);
 
				*(T2->r+x)=*(T1->r+j);
 
				for(y=0; y<(T1->b); y++)
				{
					if(*(T1->rTag+2*i+1)<T1->n+49) *(T2->BInv+y*T2->b+x)=*(T1->A+y*T1->n+j);
					else *(T2->BInv+y*T2->b+x)=*(T1->BInv+y*T1->b+i-T1->n);
				}
 
				if(*(T2->bvTag+2*x+1)-49<T1->n) *(T2->C2+x)=*(T1->C1+j+T1->n);
				else *(T2->C2+x)=*(T1->C2+j+T1->n);
 
				*(T2->rTag+2*(T2->n+x))=*(T1->bvTag+2*j);
				*(T2->rTag+2*(T2->n+x)+1)=*(T1->bvTag+2*j+1);
 
				*(T2->r+x)=*(T1->r+j);
 
				x++;
				break;
			}
		}
	}
 
	*(T2->C2+x)=0;
 
	x*=2;	*(T2->bvTag+x)='x';
	x++;	*(T2->bvTag+x)=(T2->n)+(T2->b)+48;
	x++;	*(T2->bvTag+x)='\0';
 
	i*=2;	*(T2->rTag+i)='x';
	i++;	*(T2->rTag+i)=(T2->n)+(T2->b)+48;
	i++;	*(T2->rTag+i)='\0';
 
	T2->C1 = (float*)calloc(sizeof(float), (T2->n));
 
	y=0;
	cout<<endl;
	int z;
	for(i=0; i<(T1->n)+(T1->b)+(T1->a); i++)
	{
		if(y>T1->n) break;
		if(*(marker+i)=='F') continue;
 
		*(T2->rTag+2*+y)=*(T1->rTag+2*i);
		*(T2->rTag+2*+y+1)=*(T1->rTag+2*i+1);
 
		//printf("\ni%d: j", i);
 
		for(j=0; j<(T1->b); j++)
		{
			//printf(" %d", j);
			z=*(T1->bvTag+2*j+1)-49;
			cout<<" "<<z;
 
			if(*(T1->rTag+2*i+1)<T1->n+49) *(T2->A+j*T2->n+y)=*(T1->A+z*T1->n+i);
			else *(T2->A+j*T2->n+y)=*(T1->BInv+z*T1->b+i-T1->n);
		}
 
		if(*(T1->rTag+2*i+1)<T1->n+49) *(T2->C1+y)=*(T1->C1+i);
		else *(T2->C1+y)=*(T1->C2+i-T1->n);
 
		y++;
	}
 
	free(marker);
 
	cout<<endl;
	RSimplex::show(T2);
 
	return NULL;
}
 
Tptr RSimplex::dualMin(Tptr T1)
{
	loop_count=0;
 
	Tptr T2;
 
	free(Cb); Cb = (float*)calloc(sizeof(float), T1->b);
	for(i=0; i<T1->b; i++) *(Cb+i)= - *(T1->C2+i);
 
//Finding Leaving variable
re: Temp1=*(T1->r);
	pivot_i=0;
	for(i=1; i<T1->b; i++)
	{
		if(Temp1 > *(T1->r+i))
		{
			Temp2=Temp1;
			pivot_i=i;
		}
	}
	if(Temp1>0) //rhs Values are +ve
	{
		if(loop_count!=1) free(T2);
		return T1;
	}
 
//Finding Entering Variable
	Temp2=*(T1->C1) / *(T1->C1+pivot_i*T1->n);  if(Temp2<0) Temp2*=(-1.0);
	pivot_j=0;
	for(j=1; j<T1->n; j++)
	{
		Temp1= *(T1->C1+j) / *(T1->C1+pivot_i*(T1->n-1)+j);
 
		if(Temp1<0) Temp1*=(-1.0);
		if(Temp2> Temp1)
		{
			Temp1=*(T1->C1+j);
			pivot_j=j;
		}
	}
 
	if(loop_count==0) T2=new Table(T1);
 
	RSimplex::next_table(T1,T2);
 
	can_i_stop;
 
	if(loop_count==1) //1st run only
	{
		T1=T2;
		T2=new Table(T1);
		goto re;
	}
 
	TTemp=T2; T2=T1; T1=TTemp;
	goto re;
}
 
Tptr RSimplex::basicMax(Tptr T1)
{
	loop_count=0;
 
	Tptr T2;
 
	free(Cb); Cb = (float*)calloc(sizeof(float), T1->b);
	for(i=0; i<T1->b; i++) *(Cb+i)= - *(T1->C2+i);
 
//Finding Entering Variable
re: Temp1=*(T1->C1);
	pivot_j=0;
	for(j=1; j<T1->n; j++)
	{
		if(Temp1 > *(T1->C1+j))
		{
			Temp1=*(T1->C1+j);
			pivot_j=j;
		}
	}
	if(Temp1>=0) goto returning; //get C1 -ve
 
//Finding Leaving variable
	i=0;
reload:
	if(i>=T1->b) goto returning;
 
	if(*(T1->A+i*T1->n+pivot_j)!=0)
	{
		Temp1=*(T1->r+i) / *(T1->A+i*T1->n+pivot_j);
		if(Temp1>0) goto ok;
	}
	i++;
	goto reload;
////////////////////Code Break////////////////////
ok: pivot_i=i;
 
	for(i++; i<T1->b; i++)
	{
		if(*(T1->r+i)<=0 || *(T1->A+i*T1->n+pivot_j)<0) continue;
		Temp2=*(T1->r+i) / *(T1->A+i*T1->n+pivot_j);
		if(Temp1> Temp2)
		{
			Temp1=Temp2;
			pivot_i=i;
		}
	}
 
	if(loop_count==0) T2=new Table(T1);
 
	RSimplex::next_table(T1,T2);
 
	can_i_stop;
 
	if(loop_count==1) //1st run only
	{
		T1=T2;
		T2=new Table(T1);
		goto re;
	}
 
	TTemp=T2; T2=T1; T1=TTemp;
	goto re;
returning:
	if(loop_count!=1) free(T2);
	return T1;
}
 
void RSimplex::next_table(Tptr T1, Tptr T2)
{
	pivot=*(T1->A+pivot_i*T1->n+pivot_j);
 
# ifdef CmdDis
	findcursor(&i,&j);
	gotoxy((pivot_j*dtab)+2, y-(T1->b)+pivot_i+1);
	TxtAttrib(10);
	pno(pivot);
	TxtAttrib(7);
	gotoxy(i,j);
# else
	printf("\ni: %d j: %d %9.4f", pivot_i, pivot_j, pivot);
# endif
 
	*(T2->bvTag+2*pivot_i)=*(T1->rTag+2*pivot_j);
	*(T2->bvTag+2*pivot_i+1)=*(T1->rTag+2*pivot_j+1);
 
//Revised Simplex Method
//Cb
	for(i=0; i<T1->b; i++)
	{
		x=*(T2->bvTag+2*i+1);
		for(j=0; j< (tb->n)+(tb->b)+(tb->a); j++)
		{
			if(x==*(T2->rTag+2*j+1))
			{
				x=x-49;
				if(x>tb->n) *(Cb+i) = - *(tb->C2+x);
				else *(Cb+i) = - *(tb->C1+x);
			}
		}
		//pno(*(Cb+i));
	}
 
//Exchange Matrix
	free(Ex);
	Ex = (float*)calloc(sizeof(float), T1->b*T1->b);
 
	for(i=0; i<T1->b; i++)
	{
		for(j=0; j<T1->b; j++)
		{
			if(j==pivot_i) *(Ex+i*T1->b+j) =* (T1->A+i*T1->n+pivot_j)/pivot*-1.0;
			else if(i==j) *(Ex+i*T1->b+j)=1;
			else *(Ex+i*T1->b+j)=0;
			//pno(*(Ex+i*T1->b+j));
		}
		//cout<<endl;
	}
	*(Ex+pivot_i*T1->b+pivot_i) = 1.0 / pivot;
 
//BInverse Next
	free(T2->BInv); T2->BInv = matrixMul(Ex,T1->b,T1->b,T1->BInv,T1->b,T1->b);
 
//RHS
	free(T2->r);
	T2->r = matrixMul(T2->BInv,T1->b,T1->b,tb->r,T1->b,1);
 
//A
	free(T2->A);
	T2->A = matrixMul(T2->BInv,T1->b,T1->b,tb->A,tb->b,tb->n);
 
//Cb*BInv-C2
	free(Ex); Ex = matrixMul(Cb,1,T1->b,T2->BInv,T2->b,T2->b);
	free(T2->C2); T2->C2 = matrixAdd(Ex,tb->C2,1,T1->b);
 
//RHS
	T2->R = *(matrixMul(Ex,1,T1->b,tb->r,tb->b,1));
 
//Cb*BInv*A-C1
	free(Te); Te = matrixMul(Ex,1,T1->b,tb->A,tb->b,tb->n);
	free(T2->C1); T2->C1 = matrixAdd(Te,tb->C1,1,T2->n);
 
	cout<<endl;
	RSimplex::show(T2);
}
 
int main()
{
	RSimplex r;	
	r.menu(r.Samples('1'));
	return 0;
}
 
# define dont_Kill_tb if(loop_count!=0) free(Solution);    //avoid when solution=tb
 
void RSimplex::menu(char ch)
{
	Tptr Solution=NULL;
	Tptr Zombie;
	if(ch!=0) goto ch_chk;
 
Menu_loop:
	cls;
	cout<<"Revised Simplex Method\n"
		<<"\n0. Fill the table\n"
		<<"\n1. Max Optimizition"
		<<"\n3. Min Dual Method"
		<<"\n9. Integer Progamming"
		<<"\n\n*. Move solution to reprocess"
		<<"\n\nEnter your choice: ";
 
def:ch=getch();
	cls;
 
ch_chk:
	switch(ch)
	{
		/*
		case '0':
		free(tb);
		tb=Simplex::insert();
		break;
		*/
 
		case '1':
			cout<<">Maxmimize:";
			RSimplex::show(tb);
			dont_Kill_tb;
			Solution=RSimplex::basicMax(tb);
			Zombie=Solution;
			goto extended_view_sol;
 
		case '3':
			cout<<">Dual Method Minimize:";
			RSimplex::show(tb);
			dont_Kill_tb;
			Solution=RSimplex::dualMin(tb);
			Zombie=Solution;
			goto extended_view_sol;
 
		case '9':
			cout<<">Integer Method:";
			RSimplex::show(tb);
			//dont_Kill_tb;
			//Solution=
			RSimplex::cutPlane(tb);
			goto extended_view_sol;
 
		case '.':
			cout<<">Optimal Table:";
			Zombie=Solution;
			goto extended_view;
 
		case '`':
			free(tb); //clear the place before new values
			ch=Samples(0);
			goto ch_chk;
 
		case '*':
			if(loop_count==0) goto Menu_loop;    //avoid free(tb) when solution=tb
			tb=Solution;
			cout<<"\a";
			Zombie=tb;
			goto extended_view;
 
		case 13:
			cout<<">Orignal Table:";
			Zombie=tb;
			goto extended_view;
 
		case 27: return;
 
		case 'f':
		case 'F':
			FRAC=!FRAC;
			cout<<"\a";
 
		default: //for blinking
			goto Menu_loop;
			//goto def;
	}
	getch();
	goto Menu_loop;
 
extended_view:
	RSimplex::show(Zombie);
 
extended_view_sol:
	switch(getch())
	{
		case '.':
			FRAC=!FRAC;
			cout<<"\a\n";
			goto extended_view;
	}
	goto Menu_loop;
}
# ifdef CmdDis
	void gotoxy(short x, short y)
	{
		COORD CursorPosition={x,y};
		SetConsoleCursorPosition(hConsole, CursorPosition);
	}
 
	COORD findcursor(short *x, short *y)
	{
		CONSOLE_SCREEN_BUFFER_INFO window;
		GetConsoleScreenBufferInfo(hConsole, &window);
		*x=window.dwCursorPosition.X;
		*y=window.dwCursorPosition.Y;
		COORD CursorPosition = {*x,*y};
		return CursorPosition;
	}
# endif
 
void RSimplex::TM_sim_max()
{
	tb=new Table(2,4,0);
 
	static char rTag[] ="x1x2x3x4x5x6";			tb->rTag = &rTag[0];
	static char bvTag[] ="x3x4x5x6";			tb->bvTag = &bvTag[0];
 
	static float C1[]={-3,-2};					tb->C1 = &C1[0];
	static float C2[]={0,0,0,0};				tb->C2 = &C2[0];
	tb->R=0;
 
	static float A[] =
	{
	    1,   2,
	    2,   1,
	   -1,   1,
	    0,   1,
	};
 
	tb->A = &A[0];
 
	static float BInv[] =
	{
		1,	0,	0,	0,
		0,	1,	0,	0,
		0,	0,	1,	0,
		0,	0,	0,	1 
	};
	tb->BInv=&BInv[0];
 
	static float r[]={6, 8, 1, 2};
	tb->r=&r[0];
}
 
void RSimplex::TM_dual_min()
{
	tb=new Table(2,3,0);
 
	static char rTag[] ="x1x2x3x4x5";			tb->rTag = &rTag[0];
	static char bvTag[] ="x3x4x5";				tb->bvTag = &bvTag[0];
 
	static float C1[]={-3,-2};					tb->C1 = &C1[0];
	static float C2[]={0,0,0};					tb->C2 = &C2[0];
	tb->R=0;
 
	static float A[] =
	{
	   -3,  -1,
	   -4,  -3,
		1,   1,
	};
	tb->A = &A[0];
 
	static float BInv[] =
	{
		1,   0,   0,
		0,   1,   0,
		0,   0,   1
	};
 
	tb->BInv=&BInv[0];
 
	static float r[]={-3, -6, 3};
	tb->r=&r[0];
}
 
void RSimplex::TM_cut_plane()
{
	tb=new Table(2,2,0);
 
	static char rTag[] ="x1x2x3x4";				tb->rTag = &rTag[0];
	static char bvTag[] ="x3x4";				tb->bvTag = &bvTag[0];
 
	static float C1[]={-7,-9};					tb->C1 = &C1[0];
	static float C2[]={0,0};					tb->C2 = &C2[0];
	tb->R=0;
 
	static float A[] =
	{
	  -1,   3,
	   7,   1,
	};
	tb->A = &A[0];
 
	static float BInv[] =
	{
	   1,   0,
	   0,   1
	};
 
	tb->BInv=&BInv[0];
 
	static float r[]={6,35};
	tb->r=&r[0];
}
 
char RSimplex::Samples(char ch)
{
	printf(">Sample:");
	if(ch==0) ch=getche();	
 
	switch(ch)
	{
		case '1':
			TM_sim_max();
			ch=maximize;
			break;
 
		case '3':
			TM_dual_min();
			ch=dualmini;
			break;
 
		case '6':
			TM_cut_plane();
			cout<<">Integer Method>Maxmimize:";
			RSimplex::show(tb);
			RSimplex::cutPlane(RSimplex::basicMax(tb));
			getch();
			ch=halt;
			break;
 
		default: return halt;
	}
 
	return ch;
}