//***************************************************************
//
//  batoh.cpp
//    Reseni problemu batohu
//
//***************************************************************
#include <stdio.h> 
#include <fstream.h>
#include <string.h>
#include <sys/stat.h>
#include <time.h>


//definice NULL
#ifndef NULL
#define NULL 0
#endif


/////////////////////////////////////////////////////////////////
// MNOZINA VECI 

	// data ----------------------
	//prvek mnoziny veci
	struct ThingItem
	{
		int weight;   //vaha veci
		int price;    //cena veci
	};

	//mnozina (pole) veci
	ThingItem  *things = NULL;

	// funkce --------------------
	//iniciace mnoziny veci
	void InitThings(ThingItem *_things)
	{
	  if (things != NULL)
			delete[] things;
		things = _things;
	}

	//zruseni veci
	void DestroyThings()
	{
	  if (things != NULL)
			delete[] things;
		things = NULL;
	}


//////////////////////////////////////////////////////////
// BATOH
  // data -----------------------
	int		_count;			//pocet veci
  int   _size;			//velikost pole
  int   capacity;   //kapacita batohu
  bool* presence = NULL;   //pritomnost veci v batohu
  int   price;      //cena veci v batohu
  int   remain;     //zbyvajici kapacita

  // metody ----------------------
	//zruseni batohu
	void DestroySack()
	{
	  if (presence != NULL)
		  delete[] presence;
		presence = NULL;
		_size = 0;
	}

	//vyprazdneni celeho batohu - pritomnost vsech veci na false
	void _ClearSack(int count)
	{
		for (int i = 0; i < count; i++)
			presence[i] = false;
	}
	
	//iniciace batohu
	void InitSack(int capac, int count)
	{
		//? nutno pretvorit pole
		if ((presence != NULL) && (_size < count))
			DestroySack();
		//? nutno vyrobit pole
		if (presence == NULL) {
			presence = new bool[count];
			_size = count;
		}
		capacity = capac;
		_count = count;
		remain = capac;
		price = 0;
		_ClearSack(count);		//"vyprazdneni batohu" - nastaveni na false
	}

	//pridani veci do batohu
	// vraci false pokud vec jiz pridana nebo se nevejde
	bool Add(int index)
	{
		if ((presence[index]) || (remain < things[index].weight))
			return false;
	  presence[index] = true;
		price += things[index].price;
	  remain -= things[index].weight;
		return true;
	}

	//odebrani veci z batohu
	//vraci false pokud vec neni pridana
	bool Remove(int index)
	{
		if (! presence[index])
			return false;
		presence[index] = false;
		price -= things[index].price;
	  remain += things[index].weight;
		return true;
	}


////////////////////////////////////////////////////////////////
// NACITANI VSTUPNICH DAT

	// data -----------------------------------------------
	//struktura dat instance problemu - nactena data
	struct InstanceData
	{
		int	 ID;				//ID zadani
		int	 count;			//pocet veci
		int  capacity;	//kapacita batohu
		ThingItem *things;
	};

	struct ResultData
	{
		int ID;
		int count;
		int price;
		bool *presence;
	};
	
	//streamy vstupnich souboru
	ifstream input;
	ifstream check;
	//spravny vysledek aktualniho reseni
	ResultData bestResult;

	// metody ---------------------------------------------
	//otevreni vstupniho souboru
	// false pri nepovedeni
	bool OpenSourceFiles(char *inputFile, char *checkFile)
	{
	  input.open(inputFile, ios::in, S_IREAD);
		check.open(checkFile, ios::in, S_IREAD);
		bestResult.ID = 0;
		bestResult.presence = NULL;
		return (input != NULL);
	}

	//uzavreni souboru
	void CloseSourceFiles()
	{
		input.close();
		check.close();
	}

	//nacteni spravneho vysledku pro kontrolu
	void _LoadResult(int instanceID)
	{
		//? je otevren soubor
		if ( (check == NULL) || (check.eof()) ) {
			bestResult.ID = 0;
			return;
		}
		//vysledek
		check >> bestResult.ID;
		if (bestResult.ID != instanceID) {
			bestResult.ID = 0;
			return;
		}
		check >> bestResult.count;
		check >> bestResult.price;
		//parametry veci
		bool *things = new bool[bestResult.count];
		for (int i = 0; i < bestResult.count; i++)
		{
			int presence;
			check >> presence;
			things[i] = (presence != 0);
		}
		if (bestResult.presence != NULL)
			delete[] bestResult.presence;
		bestResult.presence = things;
	}
	
	//nacteni dat ze souboru
	bool LoadData(InstanceData &data)
	{
		//? je otevren soubor
		if ( (input == NULL) || (input.eof()) )
			return false;
		//informace o instanci
		input >> data.ID;
		if (input.eof())	//posledni radek prazdny
			return false;
		input >> data.count;
		input >> data.capacity;
		//parametry veci
		ThingItem *things = new ThingItem[data.count];
		for (int i = 0; i < data.count; i++)
		{
			input >> things[i].weight;
			input >> things[i].price;
		}
		data.things = things;
		//nacteni spravneho vysledku pro kontrolu
		_LoadResult(data.ID);
		return true;
	}


///////////////////////////////////////////////////////////////
// VYPIS VYSTUPNICH DAT

	// data ------------------
	ofstream output;		//vystup jednotlivych reseni
	ofstream table;			//vystup jen vysledku + casu

	const char *DEL = " ";		//oddelovac polozek

	// metody ----------------
	//otevreni vstupniho souboru
	// false pri nepovedeni
	bool OpenOutputFiles(char *outputFile, char *resultFile)
	{
		output.open(outputFile, ios::out, S_IWRITE);
		table.open(resultFile, ios::out, S_IWRITE);
		return ((output != NULL) && (table != NULL));
	}

	//uzavreni souboru
	void CloseOutputFiles()
	{
		output.close();
		table.close();
	}

	//zaneseni vysledku metody - ulozeni do vyst. souboru
	// vraci relativni chybu vypoctu
	double SaveResult(const ResultData &result, const double time)
	{
		//vypis celeho reseni
		output << result.ID << DEL << result.count << DEL << result.price << DEL; 
		for (int i = 0; i < result.count; i++)
		{
			if (result.presence[i])
				output << "1" << DEL;
			else
				output << "0" << DEL;
		}
		output << endl;
		//vypis vysledku
		double error = -1.0;
		table << result.ID << DEL << time << DEL;
		if (bestResult.ID != result.ID)
			table << "wrong ID";
		else
		{
			table << result.price << DEL << bestResult.price << DEL;
			error = (bestResult.price - result.price) / (double)bestResult.price;
			table << error;
		}
		table << endl;
		return error;
	}


///////////////////////////////////////////////////////////////
// SPOUSTENI A SPOLECNA DATA METOD

	// data ----------------
	//prubezne nejlepsi vysledek
	ResultData result;	

	// metody --------------------
	//adresare se zadanimi / vysledky
	const char
		*INSTANCE = "inst/",		//adresar se zadanimi
		*CHECK	 = "sol/",			//spravne vysledky
		*OUTPUT	 = "output/",		//me vysledky
		*TABLE	 = "table/";		//shrnuti vysledku v tabulce

	// metody ---------------
	//priprava dat ve vysledku pred spustenim metody
	void PrepareResult(int ID, int count)
	{
		result.ID = ID;
		result.count = count;
		result.price = 0;
		if (result.presence != NULL)
			delete[] result.presence;
		result.presence = new bool[count];
	}

	//ulozeni aktualniho nastaveni do vysledku
	void SaveData()
	{
		result.price = price;
		for (int i = 0; i < result.count; i++)
			result.presence[i] = presence[i];
	}

	//spusteni dane metody s danymi soubory
	//vraci pocet bezchybnych behu
	int RunMethod(const char *file, void (*methodFunction)(), const char *methodName)
	{
		char
			input[25],
			check[25],
			output[35],
			resFile[35];
		double sumTime = 0.0;
		int runCount = 0;
//
		int goodCount = 0;
		//create filenames
		strcpy(input, INSTANCE);
		strcat(input, file);
		
		strcpy(check, CHECK);
		strcat(check, file);
		
		strcpy(output, methodName);
		strcat(output, "/");
		strcat(output, OUTPUT);
		strcat(output, file);
		
		strcpy(resFile, methodName);
		strcat(resFile, "/");
		strcat(resFile, TABLE);
		strcat(resFile, file);
		//init files
		OpenSourceFiles(input, check);
		OpenOutputFiles(output, resFile);
		InstanceData data;
		//load instances serially
		while(LoadData(data))
		{
			//printf("ID: %d   N: %d   M: %d\n", data.ID, data.count, data.capacity);
			//initialization
			InitThings(data.things);
			InitSack(data.capacity, data.count);
			PrepareResult(data.ID, data.count);
			//method processing
			clock_t start = clock();
			methodFunction();
			clock_t end = clock();
			//result saving
			double milis = ((double)(end-start) * 1000.0) / CLOCKS_PER_SEC;
			printf("%d: %f\n", data.ID, milis);
			sumTime += milis;
			runCount++;
			double res = SaveResult(result, milis);
//			//pocitani bezchybnych behu
			if (res == 0.0)
				goodCount++;
//			break;		//jen jeden beh
		}
		//close files
		CloseSourceFiles();
		CloseOutputFiles();
		return goodCount;
//		return sumTime / runCount;
	}


///////////////////////////////////////////////////////////////
// RESENI HRUBOU SILOU - BrutalPower
// Ciste pouziti hrube sily bez okolnich podminek

	//pripadne ulozeni vysledku na konci vetve
	void _CheckResult()
	{
		if (price > result.price)
			SaveData();
	}

	//zkouseni jednotlivych veci
	void _BPTryThing(int index)
	{
		//? neni posledni vec
		if (index < result.count)
		{
			//zkusit s
			if ( Add(index) ) {
				_BPTryThing(index + 1);
				Remove(index);
			}
			//zkusit bez
			_BPTryThing(index + 1);
		}
		//za posledni veci - ulozeni
		else
			_CheckResult();
	}
	
	//hlavni metoda reseni
	void BrutalPower()
	{
		_BPTryThing(0);
	}
	
	
///////////////////////////////////////////////////////////////
// RESENI HRUBOU SILOU S RAZENIM DLE VAHY
// Veci jsou serazeny od nejlehci - pokud se vec nevejde, nevejde
// se ani zadna po ni

	//pole indexu pro razeni
	int *indexes = NULL;

	//zkouseni jednotlivych veci
	void _BWTryThing(int index)
	{
		//? neni posledni vec (pokud se vejdou vsechny)
		if (index < result.count)
		{
			int myindex = indexes[index];
			//? vejde se
			if ( Add(myindex) )
			{
				//zkusit s
				_BWTryThing(index + 1);
				//zkusit bez
				Remove(myindex);
				_BWTryThing(index + 1);
				return;	//kontrola bude dal
			}
		}
		//nevejdu se, tedy nikdo jiny, nebo vsechno pridano - konec
		_CheckResult();
	}

	//serazeni veci VZESTUPNE dle vahy
	// vraci pointr na pole indexu
	int* WeightSort(int count)
	{
		int *array = new int[count];
		//vyplneni pole postupnymi indexy
		for (int in = 0; in < count; in++)
			array[in] = in;
		//serazeni
		for (int i = 0; i < count - 1; i++)
		{
			int
				minIndex = i,
				min = things[array[i]].weight;
			//nalezeni minima
			for (int j = i + 1; j < count; j++)
			{
				if (things[array[j]].weight < min)
				{
					min = things[array[j]].weight;
					minIndex = j;
				}
			}
			//ulozeni minima
			int pom = array[i];
			array[i] = array[minIndex];
			array[minIndex] = pom;
		}
		return array;
	}
	
	//hlavni metoda reseni
	void BrutalWeight()
	{
		if (indexes != NULL)
			delete[] indexes;
		indexes = WeightSort(result.count);
		_BWTryThing(0);
		delete[] indexes;
		indexes = NULL;
	}

	
///////////////////////////////////////////////////////////////
// RESENI HEURISTIKOU DLE POMERU CENA/VAHA
// Veci se usporadaji sestupne dle pomeru cena/vaha a berou
// se, dokud neni batoh plny.

	//serazeni dle pomeru cena/vaha
	int* PriceWeightSort(int count)
	{
		int *array = new int[count];
		double *key = new double[count];
		int i;
		//iniciace poli
		for (i = 0; i < count; i++)
		{
			array[i] = i;
			key[i] = (double)things[i].price / things[i].weight;
		}
		//razeni
		for (i = 0; i < count - 1; i++)
		{
			int maxIndex = i;
			double max = key[array[i]];
			//nalezeni maxima
			for (int j = i + 1; j < count; j++)
			{
				if (key[array[j]] > max)
				{
					max = key[array[j]];
					maxIndex = j;
				}
			}
			//ulozeni minima
			int pom = array[i];
			array[i] = array[maxIndex];
			array[maxIndex] = pom;
		} //for i
		delete[] key;
		return array;
	}
	
	//hlavni fce metody
	void PriceWeightHeuristic()
	{
		if (indexes != NULL)
			delete[] indexes;
		//usporadani
		indexes = PriceWeightSort(result.count);
		//pridavani
		for (int i = 0; i < result.count; i++)
		{
			if (!	Add(indexes[i]) )
				break;
		}
		SaveData();
		delete[] indexes;
		indexes = NULL;
	}

///////////////////////////////////////////////////////////////
// SPOUSTENI PROGRAMU

//spusteni metody s vice vstupnimi soubory
void RunFiles(char* *files, int count, void (*function)(), const char *name)
{
	int *goodCount = new int[count];
	int i;
	for (i = 0; i < count; i++)
	{
		cout << files[i] << " (" << name << ") --------------------" << endl;
		goodCount[i] = RunMethod(files[i], function, name);
	}
	cout << endl << "Pocty dobrych vysledku" << endl;
	for (i = 0; i < count; i++)
	{
		cout << files[i] << "  " << goodCount[i] << endl;
	}
	delete[] goodCount;
}

//hlavni metoda	
void main()
{
	const int count = 12;
	char *files[count];
	files[0] = "knap_4.txt";
	files[1] = "knap_10.txt";
	files[2] = "knap_15.txt";
	files[3] = "knap_20.txt";
	files[4] = "knap_22.txt";
	files[5] = "knap_25.txt";
	files[6] = "knap_27.txt";
	files[7] = "knap_30.txt";
	files[8] = "knap_32.txt";
	files[9] = "knap_35.txt";
	files[10] = "knap_37.txt";
	files[11] = "knap_40.txt";
	RunFiles(files, count, PriceWeightHeuristic, "heur_pw");
	//RunFiles(files, count, BrutalPower, "brutal");
	//RunFiles(files, count, BrutalWeight, "brutalw");
	//RunMethod("knap_4.txt", BrutalWeight, "brutalw");
	//RunMethod("knap_27.txt", BrutalPower, "brutal");
}