#!/usr/bin/env python2.6
#coding=utf8

import re

COLOR_MAPPING = {
	1: 'gold',
	2: 'blue',
	3: 'gold4',
	30: 'deepskyblue', # Ligne 3b
	4: 'hotpink3',
	5: 'orange',
	6: 'springgreen2',
	7: 'pink1',
	8: 'darkorchid2',
	9: 'yellow3',
	11: 'tan4',
	12: 'springgreen4',
	13: 'skyblue',
	14: 'indigo',
}

def slugify(name):
	chars = u'abcdefghijklmnopqrstuvwxyz'
	special_chars = {
		u'é': u'e', u'è': u'e', u'â': u'a',
		u'ê': u'e', u'î': u'i', u'ô': u'o',
		u'ç': u'c', u'ü': u'u', u'—': u' '
	}
	sluged_string = ''
	for char in name.lower():
		if char in chars:
			sluged_string += char
		elif char in special_chars:
			sluged_string += special_chars[char]
	return sluged_string


class Node(object):
	def __init__(self, name):
		self.name = name
		self.reset()

	def reset(self):
		self.previous = None
		self.traveled = float('inf')
		self.line_nb = None
	
	def __repr__(self):
		return '<Node: %s (%s)>' % (self.name.encode('utf8'), self.traveled)
	
class Edge(object):
	def __init__(self, node1, node2, weight, line_nb):
		self.node1 = node1
		self.node2 = node2
		self.weight = weight
		self.line_nb = line_nb
	
	def give_other_node(self, node):
		'''Return the other node'''
		if node is self.node1:
			return self.node2
		elif node is self.node2:
			return self.node1
	
	def __repr__(self):
		return '<Edge: %s -%s- %s>' % (self.node1.name, self.weight, self.node2.name)

class Graph(object):

	regex_import = re.compile(r'(?P<line_nb>\d+): "(?P<station1>.+?)" -(?P<weight>\d+)- "(?P<station2>.+?)"')
	
	def __init__(self):
		self.nodes = []
		self.edges = []
		self.edge_start = None
	
	def add_node(self, node):
		if not node in self.nodes:
			self.nodes.append(node)
	
	def add_edge(self, edge):
		if not edge in self.edges:
			self.edges.append(edge)

	def search_station(self, name):
		selection = [n for n in self.nodes if slugify(name.decode('utf8')) in slugify(n.name)]
		if len(selection) == 1:
			return [selection[0]]
		elif not selection:
			return []
		for node in selection:
			if slugify(name.decode('utf8')) == slugify(node.name):
				return [node]
		else:
			return selection

	def import_from_file(self, filename):
		
		stations = {}
		edges = []
		
		for line in open(filename, 'r'):
			m = self.regex_import.match(line)
			if m:
				line_nb = int(m.group('line_nb'))
				station1 = m.group('station1').decode('utf8')
				weight = int(m.group('weight'))
				station2 = m.group('station2').decode('utf8')
				
				if not station1 in stations:
					stations[station1] = Node(station1)
				if not station2 in stations:
					stations[station2] = Node(station2)
				
				edges.append(Edge(stations[station1], stations[station2], weight, line_nb))
		
		self.edges = edges
		self.nodes = stations.values()

	def give_connected_edges(self, node):
		edges = []
		for edge in self.edges:
			if node is edge.node1 or node is edge.node2:
				edges.append(edge)
		
		return edges

	def init_dijkstra(self, node_start):
		for node in self.nodes:
			node.reset()
		
		self.node_start = node_start
		
		self.node_start.traveled = 0
		nodes_not_traveled = list(self.nodes)
		
		while nodes_not_traveled:
			n1 = min(nodes_not_traveled, key=lambda x: x.traveled)
			nodes_not_traveled.remove(n1)
						
			for edge in self.give_connected_edges(n1):
				if n1.line_nb and n1.line_nb != edge.line_nb:
					changing_malus = 300
				else:
					changing_malus = 0
				n2 = edge.give_other_node(n1)
				if n2.traveled > n1.traveled + edge.weight + changing_malus:
					n2.traveled = n1.traveled + edge.weight + changing_malus
					n2.previous = n1
					n2.line_nb = edge.line_nb
	
	def best_path_dijkstra(self, node_end):
		if self.node_start not in self.nodes:
			raise ValueError('Dijkstra not initialized')
		path = []
		current_node = node_end
		while current_node is not self.edge_start:
			path.insert(0, current_node)
			current_node = current_node.previous
		
		return path
	
	def export_graphviz(self):
		lines = ['graph {']
		for node in self.nodes:
			lines.append('	"%s";' % node.name)
		for edge in self.edges:
			lines.append('	"%s" -- "%s" [label="%s", color="%s"];' % (edge.node1.name, edge.node2.name, edge.weight, COLOR_MAPPING[edge.line_nb]))
		lines.append('}')
		
		return '\n'.join(lines)
		
			
if __name__ == '__main__':
	
	g = Graph()
	g.import_from_file('paris.gph')
	
	print 'Bienvenue dans le programme de calcul d\'itinéraires'
	print
	print 'Entrez une station de départ'
	while True:
		station_start = raw_input('>')
		stations_found = g.search_station(station_start)
		if not len(stations_found):
			print 'Aucune station trouvée, recommencez.'
			continue
		elif len(stations_found) == 1:
			station_start = stations_found[0]
			break
		else:
			print 'Plusieurs stations trouvées :'
			for i, st in enumerate(stations_found):
				print '  - %s : %s' % (i+1, st.name.encode('utf8'))
			print
			print 'Entrez le numéro de la station voulue :'
			while True:
				nb_station = input('>')-1
				if 0 < nb_station <= len(stations_found):
					break
				else:
					print 'Mauvais numéro, recommencez.'
			station_start = stations_found[nb_station]
			break
	
	print 'Station %s selectionnée pour le départ.' % station_start.name.encode('utf8')
	print
	print 'Entrez une station d\'arrivée'
	while True:
		station_end = raw_input('>')
		stations_found = g.search_station(station_end)
		if not len(stations_found):
			print 'Aucune station trouvée, recommencez.'
			continue
		elif len(stations_found) == 1:
			station_end = stations_found[0]
			break
		else:
			print 'Plusieurs stations trouvées :'
			for i, st in enumerate(stations_found):
				print '  - %s : %s' % (i+1, st.name.encode('utf8'))
			print
			print 'Entrez le numéro de la station voulue :'
			while True:
				nb_station = input('>')-1
				if 0 <= nb_station <= len(stations_found):
					break
				else:
					print 'Mauvais numéro, recommencez.'
			station_end = stations_found[nb_station]
			break

	print 'Station %s selectionnée pour l\'arrivée.' % station_end.name.encode('utf8')

	print
	print 'Itinéraire :'
	print '============'
	print
	g.init_dijkstra(station_start)
	
	path = g.best_path_dijkstra(station_end)
	
	last_line = 0
	last_sta = None
	
	for n in path:
		if not n.line_nb:
			print ' - Entrez dans la station %s et prenez le métro (sans blague)' % n.name.encode('utf8')
		elif last_line and n.line_nb != last_line:
			print ' - Changez à %s et prendre la ligne %s' % (last_sta.name.encode('utf8'), n.line_nb)
		last_line = n.line_nb
		last_sta = n
	print ' - Arrivée à %s (trop bien \o)' % n.name.encode('utf8')