// optymlizacja-szegowanie.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#define max 8
using namespace std;

class processes
{
public:

	int **proc,**perm,min,n,k,p;

	processes(int a, int b);
	~processes();
	
	void fill();
	int target(int a);
	void optimize();
	void show_perm();
	void show_proc();
	void permute();

	void permute(int a[], int b[], int c);
	int factoral(int a);
};
processes::processes(int a, int b)
{
	min = 0;
	n = a;
	if (b != 3)
		p = 3;
	else
		p = b;

	if ( n < max )
	{
		perm = new int *[factoral(n)];

		for (int i = 0; i < factoral(n); i++)
		{
			perm[i] = new int [n+1];
			for (int j = 0; j < n + 1; j++)
				perm[i][j] = 0;
		}
	}
	else
	{
		min = 1;
		perm = new int *[3];
		perm[0] = new int [n+1];
		perm[1] = new int [n+1];
		perm[2] = new int [n+1];

		for (int j = 0; j < n + 1; j++)
			perm[0][j] = perm[1][j] = perm[2][j] = 0;
	}

	proc = new int *[n];
	for (int i = 0; i < n; i++)
	{
		proc[i] = new int[p];
	}
}

processes::~processes()
{	

	for (int i = 0; i < n; i++)
	{
		delete [] proc[i];
	}
	delete proc;

	if ( n < max )
	{
		for (int i = 0; i < factoral(n); i++)
		{
			delete [] perm[i];
		}
	}
	else
	{
		delete perm[0];
		delete perm[1];
	}
		
	delete [] perm;
}

void processes::fill()
{
	srand( (unsigned)time( NULL ));
	for (int i = 0; i < n; i++)
	{
		proc[i][0] = rand() % 50 + 1;
		proc[i][1] = proc[i][0] * (rand() % 3 + 1);
		proc[i][2] = rand() % 5 + 1;
	}
}

int processes::target(int a) 
{
	int ret = 0,delay = 0;

	for (int i = 0; i < n; i++)
	{
		delay += proc[perm[a][i]][0];	

		if (delay > proc[perm[a][i]][1])
		{
			ret += (delay - proc[perm[a][i]][1])	* proc[perm[a][i]][2];
		}
	}
	return ret;
}
void processes::permute()
{
	for (int i = 0; i < n; i++)
			perm[0][i] = i;

	k=0;
	cout << endl;

	permute(NULL, perm[0], n);
}

void processes::permute(int a[], int b[], int c)
{
	if (c == 0) {

		if (n < max) {
			for (int i = 0; i < n; i++)
				perm[k][i] = a[i];

			perm[k][n] = target(k);

			if (perm[min][n] > perm[k][n])
			{
				min = k;
			}
			k++;
		}
		else
		{
			for (int i = 0; i < n; i++)	{
				perm[1][i] = a[i];
				//cout << a[i] << " ";
			}
			//cout << endl;

				perm[1][n] = target(1);

			if (perm[2][n] > perm[1][n])
			{
				for (int i = 0; i <= n; i++)
				{
					perm[2][i] = perm[1][i];
				}
			}
		}
	}
	
	for( int i = 0; i < c; i++ )
	{
		int *aa = new int[n - c + 1];
		int *bb = new int[c - 1];

		for (int j = 0; j < n - c; j++) 
		{
			aa[j] = a[j];
		}
		aa[ n - c ] = b[i];
		
		for (int j = 0; j < c; j++) 
		{
			if (j < i)
				bb[j] = b[j];
			if (j > i)
				bb[j-1] = b[j];
		}
		
		permute(aa, bb, c-1);

		delete aa;
		delete bb;
	}
}


void processes::optimize()
{
	cout << endl << "rozwiazanie optymalne: " << endl << endl << " " << min << " ";
	cout << "[ ";
	for ( int j = 0; j < n; j++ )
	{
		cout << perm[min][j] << " ";
	}
	cout << "]" << endl << endl;
	cout << "minimalna kara: " << perm[min][n] << endl;
	
}
void processes::show_perm()
{
	cout << endl;
	for (int i = 0; i < factoral(n); i++)
	{
		if ( i < 10 )
			cout << " ";

		if (i < 100 )
			cout << " ";

		cout << i << " | ";
		for (int j = 0; j <= n; j++)
		{
			if (j == n)
				cout << " | ";
			cout << " " << perm[i][j] << " ";
		}
				cout << endl;
	}

}
void processes::show_proc()
{
	cout << endl;
	for (int i = 0; i < n; i++)
	{
		if ( i < 10 )
			cout << " ";

		if (i < 100 )
			cout << " ";

		cout << i << " | ";
		for (int j = 0; j < p; j++)
		{
			cout << " " << proc[i][j] << " ";
		}
		cout << endl;
	}

}
int processes::factoral(int a)
{
	int temp = 1;
	
	for (int i = a; i > 0; i--)
	{
		temp *= i;
	}

	return temp;
}

int _tmain(int argc, _TCHAR* argv[])
{	
	int i;
	char c;
	cout << "podaj liczbe procesow: ";
	cin >> i;

	cout << endl << " -tworzenie klasy"; 
	processes test(i,NULL);
	test.fill();

	cout << endl << " -wylicznie permutacji"; 
	test.permute();

	test.optimize();
	
	if (test.n < max)
	{
		cout << endl << "wyswietlic tablice permutacji? [t/N]";
		do 
		{
			c = _getch();
			if (c == 13)
				c = 'n';
		}
		while (c != 't' && c != 'n');

		if (c == 't')
			test.show_perm();
	}
	cout << endl << "wyswietlic tablice procesow? [t/N]";
	do 
	{
		c = _getch();
		if (c == 13)
			c = 'n';
	}
	while (c != 't' && c != 'n');

	if (c == 't')
		test.show_proc();
	
	cout << endl << endl << "nacisnij dowolny klawisz aby zakonczyc" << endl;
	_getch();
	cout << endl << " -zwalnianie pamieci, prosze czekac.";
	return 0;
}
