from Tkinter import *
import tsplib
import tspaco, mmtspaco
from math import asin, cos, sin, sqrt
import colours

#input_file = './data/br17.atsp'	# opt = 39
#input_file = './data/ft53.atsp'	# opt = 6905
#input_file = './data/ftv33.atsp'	# opt = 1286
#input_file = './data/ftv35.atsp'	# opt = 1473
#input_file = './data/ftv38.atsp'	# opt = 1530
#input_file = './data/ftv44.atsp'	# opt = 1613
#input_file = './data/p43.atsp'	# opt = 5620
#input_file = './data/ry48p.atsp'	# opt = 14422

#input_file = './data/a280.tsp'		# opt = 2579
#input_file = './data/berlin52.tsp'	# opt = 7542
#input_file = './data/bier127.tsp'	# opt = 118282
input_file = './data/eil51.tsp'	# opt = 426
#input_file = './data/eil76.tsp'	# opt = 538
#input_file = './data/rat99.tsp'	# opt = 1211

PAUSE = 1
WIDTH, HEIGHT = 500, 500
BACKGROUND = 'white'

draw_tour = True
draw_pheromones = True

class AntTSPSystem(object):
	def __init__(self, parent, world):
		self.world = world
		#self.xscale =
		#self.yscale = 
		self.steps = 0
		
		self.parent = parent
		canvas = Canvas(parent, width=WIDTH, height=HEIGHT, bg=BACKGROUND)
		canvas.pack(expand=YES, fill=BOTH)
		self.canvas = canvas
		
		self.dirty = []
		self.parent.after(PAUSE, self.update)
		
	def clear_canvas(self):
		for item in self.dirty:
			self.canvas.delete(item)
		self.dirty = []
		
	def draw(self):
		max_x, max_y = 0.0, 0.0
		locations = self.world.locations
		
		for location in locations.values():
			x, y = location
			if x > max_x: max_x = x
			if y > max_y: max_y = y
		if max_x == 0.0 or max_y == 0.0: return
		
		radius = 10
		scalex = (self.canvas.winfo_width() - 4 * radius) / max_x
		scaley = (self.canvas.winfo_height() - 4 * radius) / max_y
		
		if draw_pheromones:
			self.draw_pheromones(locations, scalex, scaley, radius)
		self.draw_cities(locations, scalex, scaley, radius)
		if draw_tour:
			self.draw_tour(locations, scalex, scaley, radius)
		self.draw_info()
		
	def draw_cities(self, locations, scalex, scaley, radius):
		for city_id, location in locations.items():
			x, y = location
			self.dirty.append(
				self.canvas.create_oval(
					(x * scalex - radius) + radius,
					(y * scaley - radius) + radius,
					(x * scalex + radius) + radius,
					(y * scaley + radius) + radius,
					#fill='white',
					#outline='white'
				)
			)
			self.dirty.append(
				self.canvas.create_text(
					x * scalex + radius,
					y * scaley + radius,
					text='%s' % city_id, fill='black'
				)
			)
			
	def draw_pheromones(self, locations, scalex, scaley, radius):
		tour, distance = self.world.best()
		tour_edges = []
		r = tour[0]
		for s in tour[1:] + [r]:
			tour_edges.append((r,s))
			r = s
			
		min_p, max_p = 1.0e34, 0.0
		for r in xrange(len(self.world.pheromones)):
			for s in xrange(len(self.world.pheromones)):
				max_p = max(max_p, self.world.pheromones[r][s])
				min_p = min(min_p, self.world.pheromones[r][s])
		p_max = max_p - min_p
		
		for r in xrange(len(self.world.pheromones)):
			x1, y1 = locations[r]
			
			for s in xrange(len(self.world.pheromones)):
				if r == s:
					continue
				
				if (r,s) in tour_edges:
					width = 2
				else:
					width = 1
				
				x2, y2 = locations[s]
				
				p = self.world.pheromones[r][s]
				
				if p > self.world.tau_0:
					sx1 = x1 * scalex + radius
					sy1 = y1 * scaley + radius
					sx2 = x2 * scalex + radius
					sy2 = y2 * scaley + radius

					sx1, sy1 = self.magic(sx2, sy2, sx1, sy1, radius)
					sx2, sy2 = self.magic(sx1, sy1, sx2, sy2, radius)
					
					#p_colour = p/p_max
					p_colour = (p - min_p)/p_max
					
					self.dirty.append(
						self.canvas.create_line(
							sx1,
							sy1,
							sx2,
							sy2,
							dash = (2, 4),
							fill=colours.to_hex_string(colours.to_colour(p_colour)),
							width=width,
						)
					)
			
	def draw_tour(self, locations, scalex, scaley, radius):
		tour, distance = self.world.best()
		x1, y1 = locations[tour[0]]
		for city in tour[1:] + [tour[0]]:
			location = locations[city]
			x2, y2 = location
			
			if x1 == x2 and y1 == y2: continue
			
			sx1 = x1 * scalex + radius
			sy1 = y1 * scaley + radius
			sx2 = x2 * scalex + radius
			sy2 = y2 * scaley + radius
			
			sx1, sy1 = self.magic(sx2, sy2, sx1, sy1, radius)
			sx2, sy2 = self.magic(sx1, sy1, sx2, sy2, radius)
			
			self.dirty.append(
				self.canvas.create_line(
					sx1,
					sy1,
					sx2,
					sy2,
					arrow=LAST,
					#fill='white'
				)
			)
			#print '%s:(%s, %s) --> %s(%s, %s)' % (s_city_id, s_x, s_y, city_id, x, y)
			x1, y1 = x2, y2
		
	def draw_info(self):
		tour, distance = self.world.best()
		self.dirty.append(
			self.canvas.create_text(
				self.canvas.winfo_width()/2,
				self.canvas.winfo_height()-10,
				text='STEPS: %s		DISTANCE: %s' % (self.steps, distance),
				fill='black'
			)
		)
			
	def magic(self, x1, y1, x2, y2, radius):
		"""
		Magic function that makes it so that arrows won't intersect nodes
		Start/End points will start on edge of circle and end on edge of circle
		"""
		dx = x1 - x2
		dy = y1 - y2
		h = sqrt(dx**2 + dy**2)
		
		if h == 0.0:
			return x1, y1
		
		theta = asin(dx / h)
		
		sgn = 1.0 if y2 < y1 else -1.0
		
		ret_h = h - radius
		ret_x = x1 - sin(theta) * ret_h
		ret_y = y1 - cos(theta) * ret_h * sgn
		
		return ret_x, ret_y
		
	def update(self):
		while True:
			self.clear_canvas()
			self.draw()
			self.world()
			self.steps += 1
			self.parent.update()
			
		#self.clear_canvas()
		#self.draw()
		#self.parent.update()


def main():
	#open file
	distance_matrix, city_locations = tsplib.load(input_file)
	world = tspaco.World(distances=distance_matrix, locations=city_locations, num_ants=0)
	#world = mmtspaco.MinMaxWorld(distances=distance_matrix, locations=city_locations, num_ants=0)
	world()
	
	root = Tk()
	root.title('ACO TSP Viewer')
	root.minsize(width=WIDTH, height=HEIGHT)
	display = AntTSPSystem(root, world)
	root.mainloop()
	
if __name__ == '__main__':
	main()