#include "stdafx.h"
#include "Animal.h"

#include <algorithm>

#define PI 3.14159265f

std::vector<Animal*> dogs;
std::vector<Animal*> cats;
std::vector<Animal*> mice;

std::vector<Animal*> dogHull;
std::vector<Animal*> catHull;

Animal* dogPivot;
Animal* catPivot;

struct AnimalCircle
{
	double X, Y, RadiusSq;
};

AnimalCircle* dogMax;
AnimalCircle* catMax;

AnimalCircle* dogInsideHull;
AnimalCircle* catInsideHull;

void FillCoordinate(const char* str, Animal* animal)
{
	int stringLength = -1;

	while(str[++stringLength] != 0)
	{
	}

	int pow = 1;
	int space = 0;

	for(int l = stringLength - 1; l >= 0; l--)
	{
		if(str[l] == ' ')
		{
			pow = 1;
			animal->Y = animal->X;
			animal->X = 0;
			space = l;
		}
		else if(str[l] >= 48)
		{
			animal->X += (str[l] - 48) * pow;
			pow *= 10;
		}
	}

	if(str[0] == '-')
		animal->X *= -1;
	if(str[space + 1] == '-')
		animal->Y *= -1;
}

Animal* testPivot;
int testCallCount = 0;



inline bool Test(const Animal* a, const Animal* b)
{
	testCallCount++;	

	if(a->Angle < b->Angle)
		return true;
	else if(a->Angle > b->Angle)
		return false;
	else
	{
		double aDistSq = ((testPivot->X - a->X) * (testPivot->X - a->X)) + ((testPivot->Y - a->Y) * (testPivot->Y - a->Y));
		double bDistSq = ((testPivot->X - b->X) * (testPivot->X - b->X)) + ((testPivot->Y - b->Y) * (testPivot->Y - b->Y));

		if(aDistSq < bDistSq)
			return true;
		else if(aDistSq > bDistSq)
			return false;
		else
			return false;
	}
}

double sortTime;

void SortAnimalsByCartesianAngle(std::vector<Animal*>& animals, Animal& pivot)
{
	sortTime = 0;

	LARGE_INTEGER freq;
	QueryPerformanceFrequency(&freq);

	LARGE_INTEGER start;
	QueryPerformanceCounter(&start);

	for(std::vector<Animal*>::iterator iter = animals.begin(); iter != animals.end(); iter++)
	{
		Animal* animal = *iter;

		double dX = animal->X - pivot.X;
		double dY = animal->Y - pivot.Y;

		if (dX > 0 && dY > 0)
            animal->Angle = atan(dY / dX);// * _180BYPI;
        else if (dX < 0 && dY > 0)
            animal->Angle = atan(-dX / dY) + (PI / 2);// * _180BYPI + 90.f;
        else if (dX < 0 && dY < 0)
            animal->Angle = atan(dY / dX) + PI;// * _180BYPI + 180.f;
        else if (dX > 0 && dY < 0)
            animal->Angle = atan(-dX / dY) + (PI * 1.5f);// * _180BYPI + 270.f;
        else if (dX == 0 && dY > 0)
            animal->Angle = (PI / 2);
        else if (dX < 0 && dY == 0)
            animal->Angle = PI;
        else if (dX == 0 && dY < 0)
            animal->Angle = PI * 1.5f;
        else
            animal->Angle = 0;
	}

	testPivot = &pivot;

	//bool(*fn_pt)(const Animal*, const Animal*) = Test;

	//multiset<Animal*, bool(*)(const Animal*, const Animal*)> ms(fn_pt);

	//for(int i = 0; i< animals.size(); i++)
	//	ms.insert(animals[i]);

	sort(animals.begin(), animals.end(), Test);

	LARGE_INTEGER end;
	QueryPerformanceCounter(&end);

	
	double diff = (double)end.QuadPart - (double)start.QuadPart;
	double timeD = diff / (double)freq.QuadPart;
	sortTime = timeD;

	//cout << "Sort time: " << (timeD * 1000) << "ms." << endl;
}

void GenerateConvexHull(std::vector<Animal*>& animals, std::vector<Animal*>& hull, Animal& pivot)
{
	SortAnimalsByCartesianAngle(animals, pivot);

	hull.push_back(animals[0]);
	hull.push_back(animals[1]);

	unsigned int i = 2;
	int first = 1;
	int second = 0;

	while(i < animals.size())
	{
		if(hull.size() > 1)
		{
			Animal* a = hull[second];
			Animal* b = hull[first];
			Animal* c = animals[i];

			double orin = (b->X - a->X) * (c->Y - a->Y) - (c->X - a->X) * (b->Y - a->Y);

			if(orin > 0)
			{
				hull.push_back(animals[i++]);
				first++;
				second++;
			}
			else
			{
				hull.erase(hull.begin() + first);
				first--;
				second--;
			}
		}
		else
		{
			hull.push_back(animals[i++]);
			first++;
			second++;
		}
	}

	hull.push_back(animals[0]);
}

bool IsContainedInConvex(vector<Animal*>& animals, Animal* mouse)
{
	for(unsigned int i = 0; i < animals.size() - 1; i++)
	{
		Animal* a = animals[i];
		Animal* b = animals[i + 1];

		double orin = (b->X - a->X) * (mouse->Y - a->Y) - (mouse->X - a->X) * (b->Y - a->Y);

		if(orin < 0)
			return false;
	}

	return true;
}

AnimalCircle* GenerateMaxBoundingCircle(vector<Animal*>& animals)
{
	double totalX = 0;
	double totalY = 0;
	double maxRadiusSq = 0;

	int numAnimals = animals.size();

	for(unsigned int i = 0; i < numAnimals; i++)
	{
		Animal* animal = animals[i];

		totalX += animal->X;
		totalY += animal->Y;
	}

	totalX /= numAnimals;
	totalY /= numAnimals;

	for(unsigned int i = 0; i < numAnimals; i++)
	{
		Animal* animal = animals[i];

		double distSq = ((totalX - animal->X) * (totalX - animal->X)) + ((totalY - animal->Y) * (totalY - animal->Y));

		if(distSq > maxRadiusSq)
			maxRadiusSq = distSq;
	}

	AnimalCircle* circle = new AnimalCircle();
	circle->X = totalX;
	circle->Y = totalY;
	circle->RadiusSq = maxRadiusSq;

	return circle;
}

AnimalCircle* GenerateInsideHullCircle(vector<Animal*>& animals, double midX, double midY)
{
	AnimalCircle* insideCircle = new AnimalCircle();
	insideCircle->X = midX;
	insideCircle->Y = midY;

	int numAnimals = animals.size();
	double nearestDistSq = DBL_MAX;

	for(int i = 0; i < numAnimals - 1; i++)
	{
		Animal* a = animals[i];
		Animal* b = animals[i+1];

		double lengthSq = (b->X - a->X) * (b->X - a->X) + (b->Y - a->Y) * (b->Y - a->Y);
		double u = ((midX - a->X) * (b->X - a->X) + (midY - a->Y) * (b->Y - a->Y)) / lengthSq;

		double ipX = a->X + u * (b->X - a->X);
		double ipY = a->Y + u * (b->Y - a->Y);

		double distSq = (ipX - midX) * (ipX - midX) + (ipY - midY) * (ipY - midY);

		if(distSq < nearestDistSq)
			nearestDistSq = distSq;
	}
	
	insideCircle->RadiusSq = nearestDistSq;
	return insideCircle;
}

bool IsInsideCircle(AnimalCircle* circle, Animal* animal)
{
	double distSq = ((circle->X - animal->X) * (circle->X - animal->X)) + ((circle->Y - animal->Y) * (circle->Y - animal->Y));

	if(distSq < circle->RadiusSq)
		return true;
	else
		return false;
}

int numEaten = 0;
int numNeither = 0;
int numSafe = 0;
double earlyOutDogs = 0;
double earlyOutCats = 0;
int numCHDogs = 0;
int numCHCats = 0;

void SolveProblem(int dataSetNum)
{
	numEaten = 0;
	numNeither = 0;
	numSafe = 0;
	earlyOutDogs = 0;
	earlyOutCats = 0;
	numCHDogs = 0;
	numCHCats = 0;

	for(unsigned int m = 0; m < mice.size(); m++)
	{
		if(IsInsideCircle(dogInsideHull, mice[m]))
		{
			numSafe++;
			continue;
		}
		else
		{
			if(IsInsideCircle(dogMax, mice[m]))
			{
				numCHDogs++;
				if(IsContainedInConvex(dogHull, mice[m]))
				{
					numSafe++;
					continue;
				}
			}
		}

		//If here, not saved by dogs

		if(IsInsideCircle(catInsideHull, mice[m]))
		{
			numEaten++;
			continue;
		}
		else
		{
			if(IsInsideCircle(catMax, mice[m]))
			{
				numCHCats++;
				if(IsContainedInConvex(catHull, mice[m]))
				{
					numEaten++;
					continue;
				}
			}
		}

		//If here, neither

		numNeither++;
	}	
}

void DeleteStuff()
{
	for(int d = 0; d < dogs.size(); d++)
	{
		delete dogs[d];
	}

	for(int c = 0; c < cats.size(); c++)
	{
		delete cats[c];
	}

	for(int m = 0; m < mice.size(); m++)
	{
		delete mice[m];
	}

	delete dogPivot;
	delete catPivot;
	delete dogMax;
	delete catMax;
	delete dogInsideHull;
	delete catInsideHull;
}

int main(int argc, char* argv[])
{
	if(argc > 1)
	{
		double lowestTime = DBL_MAX;

		LARGE_INTEGER freq;
		QueryPerformanceFrequency(&freq);

		while(true)
		{
			LARGE_INTEGER start;
			QueryPerformanceCounter(&start);
			
			std::ifstream dataFile(argv[1]);

			if(dataFile.is_open())
			{
				//cout << "Load Started.\n";

				dataFile.seekg(0, std::ios_base::end);
				const size_t file_size = dataFile.tellg();
				dataFile.seekg(0, std::ios_base::beg);

				//cout << "Found file size.\n";

				std::vector<char> buf(file_size);
				buf.resize(file_size);
				//cout << "Resized buffer.\n";
				dataFile.read(&buf[0], file_size);

				
				//cout << "Read into char buffer.\n";

				typedef std::vector<char*> vcs;
				vcs lines;
				std::vector<char>::iterator it = buf.begin();

				//cout << "Load progressed...\n";

				while (it != buf.end())
				{
					lines.push_back(&*it);
					it = std::find(it, buf.end(), '\n');
					if (it != buf.end())
						*it++ = 0;
				}
				
				LARGE_INTEGER loadEnd;
				QueryPerformanceCounter(&loadEnd);
				//cout << "Load Complete.\n";

				double loadDiff = (double)loadEnd.QuadPart - (double)start.QuadPart;
				double loadTime = loadDiff / (double)freq.QuadPart;

				int lineNum = 0;
				int numLines = lines.size();
				int dataSetNum = 0;

				while(lineNum < numLines)
				{
					dogHull.clear();
					catHull.clear();
					dogs.clear();
					cats.clear();
					mice.clear();

					string setHeader(lines[lineNum++]);

					int firstSpace = setHeader.find_first_of(" ");
					int secondSpace = setHeader.find_first_of(" ", firstSpace + 1);
					
					int numDogs = atoi(&setHeader[0]);
					int numCats = atoi(&setHeader[firstSpace + 1]);
					int numMice = atoi(&setHeader[secondSpace + 1]);

					if(numDogs + numCats + numMice == 0)
						break;

					Animal* dogPivot = new Animal();
					Animal* catPivot = new Animal();
					dogPivot->Y = FLT_MAX;
					catPivot->Y = FLT_MAX;
					
					for(int d = 0; d < numDogs; d++)
					{					
						Animal* dog = new Animal();
						FillCoordinate(lines[lineNum++], dog);
						
						if(dog->Y < dogPivot->Y)
							dogPivot = dog;

						dogs.push_back(dog);
					}

					for(int c = 0; c < numCats; c++)
					{					
						Animal* cat = new Animal();
						FillCoordinate(lines[lineNum++], cat);

						if(cat->Y < catPivot->Y)
							catPivot = cat;

						cats.push_back(cat);
					}

					for(int m = 0; m < numMice; m++)
					{
						Animal* mouse = new Animal();
						FillCoordinate(lines[lineNum++], mouse);
							
						mice.push_back(mouse);
					}

					LARGE_INTEGER time;
					QueryPerformanceCounter(&time);
					double loadTimeDiff = (double)time.QuadPart - (double)start.QuadPart;
					double loadTimeD = loadTimeDiff / (double)freq.QuadPart;
					
					testCallCount = 0;
					double dogSortTime, catSortTime;

					GenerateConvexHull(dogs, dogHull, *dogPivot);
					dogSortTime = sortTime;
					GenerateConvexHull(cats, catHull, *catPivot);
					catSortTime = sortTime;

					dogMax = GenerateMaxBoundingCircle(dogHull);
					catMax = GenerateMaxBoundingCircle(catHull);

					dogInsideHull = GenerateInsideHullCircle(dogHull, dogMax->X, dogMax->Y);
					catInsideHull = GenerateInsideHullCircle(catHull, catMax->X, catMax->Y);

					QueryPerformanceCounter(&time);
					double ppTimeDiff = (double)time.QuadPart - (double)start.QuadPart;
					double ppTimeD = ppTimeDiff / (double)freq.QuadPart;

					SolveProblem(dataSetNum++);

					LARGE_INTEGER veryEnd;
					QueryPerformanceCounter(&veryEnd);

					double diff2 = (double)veryEnd.QuadPart - (double)start.QuadPart;
					double time2 = diff2 / (double)freq.QuadPart;

					if(time2 < lowestTime)
					{
						lowestTime = time2;
						cout << "----- NEW FASTEST RUN -----" << endl;
						cout << "Load time: " << (loadTimeD * 1000) << "ms." << endl;
						cout << "PP time: " << ((ppTimeD - loadTimeD) * 1000) << "ms." << endl;
						cout << "Proc time: " << (time2 - loadTimeD - (ppTimeD - loadTimeD)) * 1000 << "ms.\n";
						cout << "Total time: " << (time2 * 1000) << "ms." << endl;
						cout << "Eaten: " << numEaten << ", Neither: " << numNeither << ", Safe: " << numSafe << "\n";
						//cout << "Dog C.H. Tests: " << numCHDogs << "\n";
						//cout << "Cat C.H. Tests: " << numCHCats << "\n";
						//cout << "Dog Sort Time: " << dogSortTime * 1000 << "ms\n";
						//cout << "Cat Sort Time: " << catSortTime * 1000 << "ms\n";
						//cout << "TestCallCount: " << testCallCount << "\n";
						cout << "---------------------------" << endl;
					}
					//else
					//{
					//	cout << "---------------------------" << endl;
					//	cout << "Load time: " << (loadTimeD * 1000) << "ms." << endl;
					//	cout << "PP time: " << ((ppTimeD - loadTimeD) * 1000) << "ms." << endl;
					//	cout << "Proc time: " << (time2 - loadTimeD - (ppTimeD - loadTimeD)) * 1000 << "ms.\n";
					//	cout << "Total time: " << (time2 * 1000) << "ms." << endl;
					//	cout << "Eaten: " << numEaten << ", Neither: " << numNeither << ", Safe: " << numSafe << "\n";
					//	//cout << "Dog C.H. Tests: " << numCHDogs << "\n";
					//	//cout << "Cat C.H. Tests: " << numCHCats << "\n";
					//	cout << "Dog Sort Time: " << dogSortTime * 1000 << "ms\n";
					//	cout << "Cat Sort Time: " << catSortTime * 1000 << "ms\n";
					//	//cout << "TestCallCount: " << testCallCount << "\n";
					//	cout << "---------------------------" << endl;
					//}

					DeleteStuff();
				}

				buf.clear();
				lines.clear();
			}
			//cout << "Done deleting.\n";

			dataFile.close();
		}
	}
	return 0;
}