#include "Algorytm.h"

//zero-jedynkowy addytywny Algorytm BALASA
 void Balas(PARAMETRY *pomocnicza)
{
	//zmienne pomocnicze
	int alfa, beta, gamma, i, j, mnr, nr, p, r, r1, r2, s, t, z;
	int inf = 1000;

	//zmienne lokalne zmienione w związku z dynamiczną alokacją pamięci
	int *y, *w, *zr;
	int *ii, *jj, *xx;
	int *kk;
	
	y = (int*)malloc(pomocnicza->M * sizeof(int));
	w = (int*)malloc(pomocnicza->M * sizeof(int));
	zr = (int*)malloc(pomocnicza->M * sizeof(int));
	
	ii = (int*)malloc(pomocnicza->N * sizeof(int));
	jj = (int*)malloc(pomocnicza->N * sizeof(int));
	xx = (int*)malloc(pomocnicza->N * sizeof(int));
	
	kk = (int*)malloc((pomocnicza->N+1) * sizeof(int));

	for(i=0; i<pomocnicza->M; i++) y[i] = pomocnicza->tab_B[i];
	z = 1;
	for(j=0; j<pomocnicza->N; j++)
	{
		xx[j] = 0;
		z = z + pomocnicza->tab_C[j];
	}
	pomocnicza->FVAL = z+z;
	s = t = z = 0;
	kk[0] = 0;
	pomocnicza->EXIST = FALSE;

jeden:
	p = mnr = 0;
	for(i=0; i<pomocnicza->M; i++)
	{
		r = y[i];
		if(r < 0)  //infeasible constraint I
		{
			p++;
			gamma = 0;
			alfa = r;
			beta = -inf;
			for(j=0; j<pomocnicza->N; j++)
				if(xx[j] <= 0)
				if((pomocnicza->tab_C[j] + z) >= pomocnicza->FVAL)
				{
					xx[j] = 2;
					kk[s]++;
					t++;
					jj[t-1] = j+1;
				}
				else
				{
					r1 = pomocnicza->tab_A[i*(pomocnicza->N) +j];
					if(r1 < 0)
					{
						alfa = alfa - r1;
						gamma = gamma + pomocnicza->tab_C[j];
						if(beta < r1) beta = r1;
					}
				}
			if(alfa < 0) goto dwa;
			
			if(alfa + beta < 0)
			{
				if((gamma + z) >= pomocnicza->FVAL) goto dwa;
				for(j=0; j<pomocnicza->N; j++)
				{
					r1 = pomocnicza->tab_A[i*pomocnicza->N +j];
					r2 = xx[j];
					if(r1 < 0)
					{
						if(r2 == 0)
						{
							xx[j] = -2;
							for(nr=0; nr<mnr; nr++)
							{
								zr[nr] = zr[nr] - pomocnicza->tab_A[(w[nr]-1)*pomocnicza->N +j];
								if(zr[nr] < 0) goto dwa;
							}
						}
					}
					else
						if(r2 < 0)
						{
							alfa = alfa - r1;
							if(alfa < 0) goto dwa;
							gamma = gamma + pomocnicza->tab_C[j];
							if((gamma + z) >= pomocnicza->FVAL) goto dwa;
						}
				}
				mnr++;
				w[mnr-1] = i+1; 
				zr[mnr - 1] = alfa;
			}
		}
	}

	// updating the best solution
	if(p == 0)
	{
		pomocnicza->FVAL = z;
		pomocnicza->EXIST = true;
		for(j=0; j<pomocnicza->N; j++)
		{
			if(xx[j] == 1)
			{
				pomocnicza->tab_X[j] = 1;
			}
			else
			{
				pomocnicza->tab_X[j] = 0;
			}
		}
		goto dwa;
	}

	if(mnr == 0)
	{
		p = 0;
		gamma = -inf;
		for(j=0; j<pomocnicza->N; j++)
			if(xx[j] == 0)
			{
				beta = 0;
				for(i=0; i<pomocnicza->M; i++)
				{
					r = y[i];
					r1 = pomocnicza->tab_A[pomocnicza->N*i + j];
					if(r < r1) beta = beta + r - r1;
				}
				r = pomocnicza->tab_C[j];
				if((beta > gamma) || (beta == gamma) && (r < alfa))
				{
					alfa = r;
					gamma = beta;
					p = j+1;
				}
			}
		if(p == 0) goto dwa;
		s++;
		kk[s] = 0; 
		t++;
		jj[t-1] = p;
		ii[s-1] = 1;
		xx[p-1] = 1;
		z = z + pomocnicza->tab_C[p-1];
		
		for(i=0; i<pomocnicza->M; i++)
			y[i] = y[i] - pomocnicza->tab_A[pomocnicza->N*i + p-1];
	}
	else
	{
		s++;
		ii[s-1] = 0;
		kk[s] = 0;
		for(j=0; j<pomocnicza->N; j++)
			if(xx[j] < 0)
			{
				t++;
				jj[t-1] = j+1;
				ii[s-1] = ii[s-1] - 1;
				z = z + pomocnicza->tab_C[j];
				xx[j] = 1;
				for(i=0; i<pomocnicza->M; i++)
					y[i] = y[i] - pomocnicza->tab_A[i*pomocnicza->N +j];
			}
	}
	goto jeden;

//backtracking
dwa:
	for(j=0; j<pomocnicza->N; j++)
		if(xx[j] < 0)
			xx[j] = 0;
	if(s > 0)
		do
		{
			p = t;
			t = t - kk[s];
			for(j=t; j<p; j++)
				xx[jj[j]-1] = 0;
			p = abs(ii[s-1]);
			kk[s-1] = kk[s-1] + p; 
			
			for(j=t-p; j<t; j++)
			{
				p = jj[j];
				xx[p-1] = 2;
				z = z - pomocnicza->tab_C[p-1];
				for(i=0; i<pomocnicza->M; i++)
					y[i] = y[i] + pomocnicza->tab_A[pomocnicza->N*i + p-1];
			}
			
			s--;
			if(ii[s] >= 0) goto jeden;
		}while(s != 0);

		//zwalniam przydzieloną pamięć dla zmiennych lokalnych
		free(y); free(w); free(zr);
		free(ii); free(jj); free(xx);
		free(kk); 
}