"""
Author:
file:
"""

import random
from Individual import *
import sys
import math
import time



class BasicTSP:
	def __init__(self, _fName, _popSize, _mutationRate, _maxIterations):
		"""
		Parameters and general variables
		"""

		self.population  = []
		self.matingPool  = []
		self.best		  = None
		self.popSize		= _popSize
		self.genSize		= None
		self.mutationRate   = _mutationRate
		self.maxIterations  = _maxIterations
		self.iteration	= 0
		self.fName		= _fName
		self.data		  = {}

		self.readInstance()
		self.initPopulation()


	def readInstance(self):
		"""
		Reading an instance from fName
		"""
		file = open(self.fName, 'r')
		self.genSize = int(file.readline())
		self.data = {}
		for line in file:
			(id, x, y) = line.split()
			self.data[int(id)] = (int(x), int(y))
		file.close()

	def initPopulation(self):
		"""
		Creating random individuals in the population
		"""
		for i in range(0, self.popSize):
			individual = Individual(self.genSize, self.data)
			individual.computeFitness()
			self.population.append(individual)

		self.best = self.population[0].copy()
		for ind_i in self.population:
			if self.best.getFitness() > ind_i.getFitness():
				self.best = ind_i.copy()
		print ("Best initial sol: ",self.best.getFitness())

	def updateBest(self, candidate):
		if self.best == None or candidate.getFitness() < self.best.getFitness():
			self.best = candidate.copy()
			print ("iteration: ",self.iteration, "best: ",self.best.getFitness())

	def randomSelection(self):
		"""
		Random (uniform) selection of two individuals
		"""

		indA = self.matingPool[ random.randint(0, self.popSize-1) ]
		indB = self.matingPool[ random.randint(0, self.popSize-1) ]
		return [indA, indB]

	def rouletteWheel(self):
		"""
		Your Roulette Wheel Selection Implementation
		"""
		population_total = 0
		#Sum up fitness values of all chromosomes in population:
		for sol in self.population:
			population_total += 1/sol.getFitness()

		#Generate a random number between 0 and total of fitness values, where fitness is 1/getFitness()
		roulette_number = random.uniform(0,population_total)

		#Sum up again and select the first one that makes the sum equal or cross our roulette_number
		select_total = 0
		for sol in self.population:
			select_total += 1/sol.getFitness()
			if (select_total >= roulette_number):
				return sol


		pass

	def uniformCrossover(self, indA, indB):
		"""
		Your Uniform Crossover Implementation
		This function returns one child Individual
		"""
		solutionSize = indA.genSize
		child1 = indA.copy()
		child2 = indA.copy()
		child1.genes =[None] * solutionSize
		child2.genes = [None] * solutionSize
		keep = []
		for i in range(0,solutionSize):
			keep.append(bool(random.getrandbits(1)))
		for i in range(0,indA.genSize):
			if keep[i]:
				child1.genes[i] = indA.genes[i]
				child2.genes[i] = indB.genes[i]

		for i in range(0,indA.genSize):
			if indA.genes[i] not in child2.genes:
				child2.genes[child2.genes.index(None)] = indA.genes[i]
			if indB.genes[i] not in child1.genes:
				child1.genes[child1.genes.index(None)] = indB.genes[i]
		child1.computeFitness()
		child2.computeFitness()

		if child1.getFitness() < child2.getFitness():

			self.updateBest(child1)
			return child1
		else:

			self.updateBest(child2)
			return child2



	def cycleCrossover(self, indA, indB):
		"""
		Your Cycle Crossover Implementation
		This function returns one child Individual
		"""
		#List will be used to tell us that we are in a previously discovered cycle
		discovered = []
		child1 = indA.copy()
		child2 = indA.copy()
		child1.genes = [None] * self.genSize
		child2.genes = [None] * self.genSize

		lookup = {}
		#Create lookup table for cycles
		for i in range(0,self.genSize):
			lookup[indA.genes[i]] = indB.genes[i]

		#Stop when children are full of values that are not None
		while (None in child1.genes) & (None in child2.genes):
			current_gene = indA.genes[0]
			for i in range(0,self.genSize):
				current_gene = indA.genes[i]
				#Initialise list containing the new cycle
				new_discover=[]


				while current_gene not in discovered:
					#Add valuies to known cycles
					discovered.append(current_gene)

					#Add values to be iterated over below
					new_discover.append(current_gene)

					#Go to next item in cycle
					current_gene = lookup[current_gene]
				#On the first iteration, we indA -> child1 and indB -> child2.
				if i == 0:
					for gene in new_discover:
						child1.genes[indA.genes.index(gene)] = gene
						child2.genes[indB.genes.index(gene)] = gene

				#Otherwise indA -> child2
				else:
					for gene in new_discover:
						child1.genes[indB.genes.index(gene)] = gene
						child2.genes[indA.genes.index(gene)] = gene

		child1.computeFitness()
		child2.computeFitness()
		#Return the better child
		if child1.getFitness() < child2.getFitness():
			return child1
		else:
			return child2


	def reciprocalExchangeMutation(self, indA):
		"""
		Your Reciprocal Exchange Mutation implementation
		Mutate an individual by swapping two cities with certain probability (i.e., mutation rate)
		"""
		if random.random() > self.mutationRate:
			return
		indexA = random.randint(0, self.genSize-1)
		indexB = random.randint(0, self.genSize-1)

		tmp = indA.genes[indexA]
		indA.genes[indexA] = indA.genes[indexB]
		indA.genes[indexB] = tmp

		indA.computeFitness()
		self.updateBest(indA)

	def scrambleMutation(self, indA):
		"""
		Your Scramble Mutation implementation
		"""
		if random.random() > self.mutationRate:
			return
		scramble = []
		scramble_size = random.randint(2,self.genSize)
		scramble_start = random.randint(0,self.genSize - scramble_size)
		scramble = indA.genes[scramble_start:scramble_start + scramble_size]
		new_scramble = scramble[:]
		while new_scramble == scramble:
			random.shuffle(new_scramble)

		indA.genes[scramble_start:scramble_start + scramble_size] = new_scramble

		indA.computeFitness()
		self.updateBest(indA)


	def crossover(self, indA, indB):
		"""
		Executes a 1 order crossover and returns a new individual
		"""
		child = []
		tmp = {}

		indexA = random.randint(0, self.genSize-1)
		indexB = random.randint(0, self.genSize-1)

		for i in range(0, self.genSize):
			if i >= min(indexA, indexB) and i <= max(indexA, indexB):
				tmp[indA.genes[i]] = False
			else:
				tmp[indA.genes[i]] = True
		aux = []
		for i in range(0, self.genSize):
			if not tmp[indB.genes[i]]:
				child.append(indB.genes[i])
			else:
				aux.append(indB.genes[i])
		child += aux
		return child

	def mutation(self, ind):
		"""
		Mutate an individual by swapping two cities with certain probability (i.e., mutation rate)
		"""
		if random.random() > self.mutationRate:
			return
		indexA = random.randint(0, self.genSize-1)
		indexB = random.randint(0, self.genSize-1)

		tmp = ind.genes[indexA]
		ind.genes[indexA] = ind.genes[indexB]
		ind.genes[indexB] = tmp

		ind.computeFitness()
		self.updateBest(ind)

	def updateMatingPool(self):
		"""
		Updating the mating pool before creating a new generation
		"""
		self.matingPool = []
		for i in range(0,self.popSize):
			self.matingPool.append( random.choice(self.population) )



	def newGeneration(self):
		"""
		Creating a new generation
		1. Selection
		2. Crossover
		3. Mutation
		"""
		self.population =[]
		for i in range(0,self.popSize):
			"""
			Depending of your experiment you need to use the most suitable algorithms for:
			1. Select two candidates
			2. Apply Crossover
			3. Apply Mutation
			"""
			indA,indB = self.randomSelection()
			newind = self.uniformCrossover(indA,indB)
			self.reciprocalExchangeMutation(newind)
			self.population.append(newind)



	def GAStep(self):
		"""
		One step in the GA main algorithm
		1. Updating mating pool with current population
		2. Creating a new Generation
		"""

		self.updateMatingPool()
		self.newGeneration()

	def search(self):
		"""
		General search template.
		Iterates for a given number of steps
		"""
		self.iteration = 0
		while self.iteration < self.maxIterations:
			self.GAStep()
			self.iteration += 1

		print ("Total iterations: ",self.iteration)
		print ("Best Solution: ", self.best.getFitness())

	def config1(self):
		self.iteration = 0
		while self.iteration < self.maxIterations:
			self.GAStep()
			print("Iteration:",self.iteration)
			self.iteration += 1

		print ("Total iterations: ",self.iteration)
		print ("Best Solution: ", self.best.getFitness())



if len(sys.argv) < 2:
	print ("Error - Incorrect input")
	print ("Expecting python BasicTSP.py [instance] ")
	sys.exit(0)


problem_file = sys.argv[1]

ga = BasicTSP(sys.argv[1], 300, 0.1, 300)

ga.config1()
#start_time = time.time()
#print("--- %s seconds ---" % (time.time() - start_time))