#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

class City
{
private:
	int x;
	int y;

public:
	//constructs a city at chosen x,y location
	City(int x, int y)
	{
		this->x = x;
		this->y = y;
	}

	int getX()
	{
		return this->x;
	}

	int getY()
	{
		return this->y;
	}

	double distanceTo(City city)
	{
		int xDistance = abs(getX() - city.getX());
		int yDistance = abs(getY() - city.getY());
		double distance = sqrt((xDistance*xDistance) + (yDistance*yDistance));

		return distance;
	}
};

class TourManager
{
private:
	//holds the cities

	// удерживает города
	vector<City> destinationCities;

public:
	//adds a destination city
	//добавляет город назначения
	void addCity(City city)
	{
		destinationCities.push_back(city);
	}

	//get a city
	// получить город
	City getCity(int index)
	{
		return (City)destinationCities.at(index);
	}

	//get the number of destination city
	// получить номер города назначения
	int numberOfCities()
	{
		return (int)destinationCities.size();
	}
};

class Tour
{
private:
	//holds our tour of cities
	// проводит тур по городам
	vector<City> tour;
	double fitness = 0;
	int distance = 0;
	TourManager tourManager;

public:
	//constructs a blank tour
	//создает пустой тур
	Tour()
	{
		City *city = new City(0, 0);
		for (int i = 0; i < tourManager.numberOfCities(); ++i)
		{
			tour.push_back(*city);
		}
	}

	Tour(vector<City> tour)
	{
		this->tour = tour;
	}

	//generates a random individual
	// генерирует случайную особь
	void generateIndividual()
	{
		//loop through all our destinations cities and add them to our tour
		// цикл через все наши города назначения и добавить их в наш тур
		for (int cityIndex = 0; cityIndex < tourManager.numberOfCities(); ++cityIndex)
		{
			setCity(cityIndex, tourManager.getCity(cityIndex));
		}
		//randomly reorder the tour
		// случайным образом изменить порядок тура
		random_shuffle(tour.begin(), tour.end(), tour);
	}

	City getCity(int tourPosition)
	{
		return (City)tour.at(tourPosition);
	}

	void setCity(int tourPosition, City city)
	{
		//CAUTION: not sure if the line below will work!
		// Внимание: не уверен, что строка ниже будет работать!
		tour.insert(tour.begin() + tourPosition, city);

		//if the tour has been altered we need to reset fitness and distance
		//если тур был изменен, нам нужно сбросить Фитнес и расстояние
		fitness = 0;
		distance = 0;
	}

	//gets the tours fitness (fitness = cost?)
	//получает туры фитнес (фитнес = стоимость?)
	double getFitness()
	{
		if (fitness == 0)
		{
			fitness = 1 / (double)getDistance();
		}

		return fitness;
	}

	// Gets the total distance of the tour
	// Получает общее расстояние тураw
	int getDistance()
	{
		if (distance == 0)
		{
			int tourDistance = 0;

			// Loop through our tour's cities
			// цикл по городам нашего тура
			for (int cityIndex = 0; cityIndex < tourSize(); cityIndex++)
			{
				// Get city we're travelling from
				// Получить город, из которого мы едем
				City fromCity = getCity(cityIndex);

				// City we're travelling to
				// Город, в который мы едем
				City *destinationCity = new City(0, 0);

				// Check we're not on our tour's last city, if we are set our
				// tour's final destination city to our starting city
				// Проверьте, что мы не в последнем городе нашего тура, если мы установили
				//конечный город нашего тура в наш стартовый город
				if (cityIndex + 1 < tourSize())
				{
					*destinationCity = getCity(cityIndex + 1);
				}
				else
				{
					*destinationCity = getCity(0);
				}

				// Get the distance between the two cities
				// Получить расстояние между двумя городами
				tourDistance += fromCity.distanceTo(*destinationCity);
			}
			distance = tourDistance;
		}
		return distance;
	}

	//get the number of cities on our tour
	// получить количество городов в нашем туре
	int tourSize()
	{
		return (int)tour.size();
	}

	// Check if the tour contains a city
	// Проверьте, содержит ли тур город
	bool containsCity(City city)
	{
		for (int i = 0; i < tourSize(); ++i)
		{
			if ((tour[i].getX() == city.getX()) && (tour[i].getY() == city.getY()))
				return true;
		}

		return false;
	}
};

class Population
{
private:
	//hold population of tours
	// держать население туров
	vector<Tour> tours;

public:
	//contructs a population
	//построить популяцию
	Population(int populationSize, bool initialize)
	{
		tours.resize(populationSize);

		//if we need to initialize a population then do so
		//если нам нужно инициализировать популяцию, сделайте это
		if (initialize)
		{
			for (int i = 0; i < populationSize; ++i)
			{
				Tour *newTour = new Tour();
				newTour->generateIndividual();
				saveTour(i, *newTour);
			}
		}
	}

	// Saves a tour
	// Сохранение тура
	void saveTour(int index, Tour tour)
	{
		tours[index] = tour;
	}

	// Gets a tour from population
	// Получает тур от популяции
	Tour getTour(int index)
	{
		return tours[index];
	}

	// Gets the best tour in the population
	//Получает лучший тур из популяции
	Tour getFittest()
	{
		Tour fittest = tours[0];

		// Loop through individuals to find fittest
		// цикл по особям, чтобы найти наиболее приспособленных
		for (int i = 1; i < populationSize(); i++)
		{
			if (fittest.getFitness() <= getTour(i).getFitness())
			{
				fittest = getTour(i);
			}
		}
		return fittest;
	}

	// Gets population size
	//Получает размер популяции
	int populationSize()
	{
		return (int)tours.size();
	}
};

class GA
{
private:

	/* GA parameters */
	double mutationRate = 0.015;
	int tournamentSize = 5;
	bool elitism = true;

public:

	//Evolves a population over one generation
	// Эволюция популяции в течение одного поколения
	Population evolvePopulation(Population pop)
	{
		Population* newPopulation = new Population(pop.populationSize(), false);

		//keep our best individual if elitism is enabled
		// получаем наш лучшую особь, если элитарность включена
		int elitismOffset = 0;
		if (elitism)
		{
			newPopulation->saveTour(0, pop.getFittest());
			elitismOffset = 1;
		}

		// Crossover population
		// Loop over the new population's size and create individuals from
		// Current population
		// Кроссовер популяции
		// Цикл над новой численностью популяции и создание особей
		// Нынешняя популяция
		for (int i = 0; i < newPopulation->populationSize(); ++i)
		{
			//select parents
			//выбор родителей
			Tour parent1 = tournamentSelection(pop);
			Tour parent2 = tournamentSelection(pop);

			//crossover parents
			//кроссовер родителей
			Tour child = crossover(parent1, parent2);

			//add child to new population
			//добавление детей в новую популяцию
			newPopulation->saveTour(i, child);
		}

		//mutate the new population a bit to add some new genetic material
		// мутация новой популяции, чтобы добавить новый генетический материал
		for (int i = elitismOffset; i < newPopulation->populationSize(); ++i)
		{
			mutate(newPopulation->getTour(i));
		}

		return *newPopulation;
	}

	//applies crossover to a set of parents and creates offspring
	// применяет кроссовер к набору родителей и создает потомство
	Tour crossover(Tour parent1, Tour parent2)
	{
		//create the new child
		//создание нового ребенка
		Tour* child = new Tour();
		City* cityBlank = new City(0, 0);

		//get start and end sub tour positions for parents1's tour
		// начало и конец sub ваши позиции для родителей 1-х тур
		int startPos = (int)(rand() * parent1.tourSize());
		int endPos = (int)(rand() * parent1.tourSize());

		// Loop and add the sub tour from parent1 to our child
		// Loop и добавить суб тур от parent1 к нашему ребенку
		for (int i = 0; i < child->tourSize(); i++)
		{
			// if our start position is less than the end position
			// если наша стартовая позиция-это меньше, чем конечное положение
			if (startPos < endPos && i > startPos && i < endPos)
			{
				child->setCity(i, parent1.getCity(i));
			}
			// If our start position is larger
			// Если наша стартовая позиция больше
			else if (startPos > endPos)
			{
				if (!(i < startPos && i > endPos))
				{
					child->setCity(i, parent1.getCity(i));
				}
			}
		}

		// Loop through parent2's city tour
		// Цикл по городам тура родителя 2
		for (int i = 0; i < parent2.tourSize(); i++)
		{
			// If child doesn't have the city add it
			//Если у ребенка нет города, добавьте его
			if (!child->containsCity(parent2.getCity(i)))
			{
				// Loop to find a spare position in the child's tour
				//Цикл, чтобы найти запасную позицию в детском туре
				for (int ii = 0; ii < child->tourSize(); ii++)
				{
					// Spare position found, add city
					// CHECK HERE!
					//Запасная позиция найдена, добавить город

					// ПРОВЕРЬТЕ ЗДЕСЬ!
					if (child->getCity(ii).getX() == cityBlank->getX() && child->getCity(ii).getY() == cityBlank->getY())
					{
						child->setCity(ii, parent2.getCity(i));
						break;
					}
				}
			}
		}
		return *child;
	}

	// Mutate a tour using swap mutation
	//Мутировать тур с помощью swap mutation
	void mutate(Tour tour)
	{
		// Loop through tour cities
		//Цикл по городам тура
		for (int tourPos1 = 0; tourPos1 < tour.tourSize(); tourPos1++)
		{
			// Apply mutation rate
			//Применить скорость мутации
			if (rand() < mutationRate)
			{
				// Get a second random position in the tour
				// Получить вторую случайную позицию в туре
				int tourPos2 = (int)(tour.tourSize() * rand());

				// Get the cities at target position in tour
				// Получить города в целевом положении в туре
				City city1 = tour.getCity(tourPos1);
				City city2 = tour.getCity(tourPos2);

				// Swap them around
				// Поменять их местами
				tour.setCity(tourPos2, city1);
				tour.setCity(tourPos1, city2);
			}
		}
	}

	// Selects candidate tour for crossover
	// Выбор тура-кандидата для кроссовера
	Tour tournamentSelection(Population pop)
	{
		// Create a tournament population
		// Создание популяции турнира
		Population* tournament = new Population(tournamentSize, false);

		// For each place in the tournament get a random candidate tour and add it
		// Для каждого места в турнире получите случайный тур кандидата и добавьте его
		for (int i = 0; i < tournamentSize; i++)
		{
			//int randomId = (int)(rand() * pop.populationSize());
			int randomId = (int)(rand() % pop.populationSize());
			tournament->saveTour(i, pop.getTour(randomId));
		}

		// Get the fittest tour
		// Получите самый подходящий тур
		Tour fittest = tournament->getFittest();

		return fittest;
	}
};

int main()
{
	TourManager tourmanager;
	GA ga;

	City *city1 = new City(60, 200);
	tourmanager.addCity(*city1);

	City *city2 = new City(180, 200);
	tourmanager.addCity(*city2);

	City *city3 = new City(80, 180);
	tourmanager.addCity(*city3);

	City *city4 = new City(140, 180);
	tourmanager.addCity(*city4);

	City *city5 = new City(20, 160);
	tourmanager.addCity(*city5);

	//initialize population
	//инициализация популяции
	Population *pop = new Population(50, true);
	cout << "Initial distance: " << pop->getFittest().getDistance() << endl;

	// Evolve population for 50 generations
	// Эволюция населения в течение 50 поколений
	*pop = ga.evolvePopulation(*pop);
	for (int i = 0; i < 10; i++)
	{
		*pop = ga.evolvePopulation(*pop);
	}

	// Print final results
	// Печать окончательных результатов

	cout << "Finished" << endl;
	cout << "Final distance: " << pop->getFittest().getDistance() << endl;
  //  std:ostream& operator<<(std::ostream&, const Tour&);
//	Tour t = pop->getFittest();
//	cout << "Solution:  Distance = " << t.getDistance()<<". Fitness = "<<t.getFitness() << endl;
	system("pause");

}