#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#       chemin.py
#       
#       Copyright 2011 Johannes ter Haak <jojo@jojo3>
#       
#       This program is free software; you can redistribute it and/or modify
#       it under the terms of the GNU General Public License as published by
#       the Free Software Foundation; either version 2 of the License, or
#       (at your option) any later version.
#       
#       This program is distributed in the hope that it will be useful,
#       but WITHOUT ANY WARRANTY; without even the implied warranty of
#       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#       GNU General Public License for more details.
#       
#       You should have received a copy of the GNU General Public License
#       along with this program; if not, write to the Free Software
#       Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#       MA 02110-1301, USA.
#       
#       to do: graph oriented? ... l. 245-256 a->B & b->A 

import pygame , sys



## *********************************************************
## 				FONCTIONS
## *********************************************************
def nextelement(w,wege):
	t = []
	if [w[0]+1,w[1]] in wege:
		t.append( [w[0]+1,w[1]] )
	if [w[0]-1,w[1]] in wege:
		t.append( [w[0]-1,w[1]] )
	if [w[0],w[1]+1] in wege:
		t.append( [w[0],w[1]+1] )
	if [w[0],w[1]-1] in wege:
		t.append( [w[0],w[1]-1] )
	return t


def find_nodes(wege):
	nodes = []
	for w in wege:
		t = []
		if [w[0]+1,w[1]] in wege:
			t.append(w)
		if [w[0]-1,w[1]] in wege:
			t.append(w)
		if [w[0],w[1]+1] in wege:
			t.append(w)
		if [w[0],w[1]-1] in wege:
			t.append(w)
		if len(t) > 2:
			nodes.append(w)
	return nodes
	

def find_all_roads(wege,nodes):
	roads = []
	### itère chaque croisement
	for n in nodes:
		### initialisation du premier bout de chemin / définition des directions a prendre 
		nwege = nextelement(n,wege)
		nwege2 = [] 		 
		### cherche dans chaque direction 
		for w in nwege:
			nw = w					# première case du chemin
			nwege2.append([])		# ajoute un chemin possible au croisement
			stop = False			 
			nwege2[-1].append(n)	# ajoute le croisement actuel dans le chemin
			
			### cherche le chemin jusqu'à ce que on te dit de stoper donc jusqu'à ce que on tombe sur un croisement
			while stop == False:
				
				### redéfini nw (cases chemin possibles)
				nwege2[-1].append(nw)	# ajoute le dernier morceau trouvé
				nw = nextelement(nw,wege)			# prochain morceau
				###  diminu nw jusqu'a ce qu'il reste plus que une case a ajouter
				
				# tout ce qui n'est pas croisement: <-o-> chemin normal a 2 directions
				if len(nw) < 3:							
					stop2 = True							# sert a stoper si nw devient nul
					for nww in nw:							# itère chaque case possible 
						if nwege2[-1].count(nww) == 0:				# si la case n'a pas encore été ajoutée au chemin 
							nw = nww								# RéCURENCE , nw sera reutilisé dans le prochain passage
							stop2 = False							# ne stope pas, nw n'est pas nul
					# si nw est nul --> chemin trouvé (cul-de-sac)
					if stop2 == True:
						stop = True	
						
				# si on tombe sur un croisement alors chemin trouvé	
				else:
					stop = True	
		### ajoute le chemin trouvé a la liste des chemins				
		roads.extend(nwege2)
		
	#print "roads: " + str(roads)

	### 	filtrage des chemins croisement --> croisement
	###		malheureusement les cul-de-sac se perdent 
	roads2 = []
	for r in roads:
		if ((nodes.count(r[0]) != 0) and (nodes.count(r[-1]) != 0)) and len(r) != 1: 	# si soit la fin soit le début du chemin est un croisement et que le chemin est plus long que 1
			r2= r[:]		# copie de r
			r2.reverse()	# invers de r
			if roads2.count(r2) == 0:	# si on a pas déjà conté l'invers (donc le même chemin) --> elimination des chemins double
				roads2.append(r)			# alors ajoute le chemin 
	roads = roads2

	return roads
	

# Code is from
# http://thomas.pelletier.im/2010/02/dijkstras-algorithm-python-implementation/


def dijkstra(graph, start, end):
    """
    Dijkstra's algorithm Python implementation.

    Arguments:
        graph: Dictionnary of dictionnary (keys are vertices).
        start: Start vertex.
        end: End vertex.

    Output:
        List of vertices from the beggining to the end.
    
    Example:
    
    >>> graph = {
    ...     'A': {'B': 10, 'D': 4, 'F': 10},
    ...     'B': {'E': 5, 'J': 10, 'I': 17},
    ...     'C': {'A': 4, 'D': 10, 'E': 16},
    ...     'D': {'F': 12, 'G': 21},
    ...     'E': {'G': 4},
    ...     'F': {'H': 3},
    ...     'G': {'J': 3},
    ...     'H': {'G': 3, 'J': 5},
    ...     'I': {},
    ...     'J': {'I': 8},
    ... }    
    >>> dijkstra(graph, 'C', 'I')
    ['C', 'A', 'B', 'I']

    """
    D = {} # Final distances dict
    P = {} # Predecessor dict

    # Fill the dicts with default values
    for node in graph.keys():
        D[node] = -1 # Vertices are unreachable
        P[node] = "" # Vertices have no predecessors
    
    D[start] = 0 # The start vertex needs no move

    unseen_nodes = graph.keys() # All nodes are unseen

    while len(unseen_nodes) > 0:
        # Select the node with the lowest value in D (final distance)
        shortest = None
        node = ''
        for temp_node in unseen_nodes:
            if shortest == None:
                shortest = D[temp_node]
                node = temp_node
            elif D[temp_node] < shortest:
                shortest = D[temp_node]
                node = temp_node
            
		# Remove the selected node from unseen_nodes
        unseen_nodes.remove(node)
        #print unseen_nodes
        # For each child (ie: connected vertex) of the current node
        for child_node, child_value in graph[node].items():
            if D[child_node] < D[node] + child_value:
                D[child_node] = D[node] + child_value
                # To go to child_node, you have to go through node
                P[child_node] = node
            
    # Set a clean path
    path = []

    # We begin from the end
    node = end
    # While we are not arrived at the beginning
    while not (node == start):
        if path.count(node) == 0:
			path.insert(0, node) # Insert the predecessor of the current node
			if node == '':
				return []
			node = P[node] # The current node becomes its predecessor
        else:
            break

    path.insert(0, start) # Finally, insert the start vertex
    return path

def nodes_to_list(chem2,roads):
	# Koordinatenliste aus der Knoten-liste erstellen 
	chem3 =[]
	for i in range(0,len(chem2)-1):		# durch jede Kreuzung gehen , wegen next_node ohne letztes Element
		next_node = chem2[i+1]				# nexte Kreuzung
		for r in roads:							# durchsuche alle Wege
			# ist der Wegabschnitt den, den wir suchen (also Anfang und Ene gleich (jedes Ende ist ein Knoten))
			if (r[-1] == next_node) and (r[0] == chem2[i]):		
				# Wegelemente hinzufügen
				# um Dopplungen zu vermeiden wird geprüft ob das Ende des Gesamtweges bereits im Anfang des hinzuzufügenden Wegeabschnittes ist
				if chem3 != []:		# sonst chem[-1] nicht definiert
					if chem3[-1] == r[0]:
						chem3.extend(r[1:])										
					else:
						chem3.extend(r)
				else:
					chem3.extend(r)
			# Wird der Weg den wir suchen un die Andere Richtung gelaufen, so drehe alles einfach um
			elif (r[0] == next_node) and (r[-1] == chem2[i]):		
				r2 = r[:]		# Kopie des Wegeelements
				r2.reverse()	# Umdrehen:  123 --> 321	
				# gleiches Vorgehen wie Oben
				if chem3 != []:
					if chem3[-1] == r2[0]:
						chem3.extend(r2[1:])
					else:
						chem3.extend(r2)
				else:
					chem3.extend(r2)
	return chem3 

def graph_data(nodes,roads):
	graph={}
	for n in nodes:					# itère chaque croisement
		p = {}							# p sont les croisement que l'on peut atteindre en partant de n
		for r in roads:					# irère chaque route 
			if (r[0] == n):				# si la route commence par le croisement actuel
				if graph.get(str(r[-1])) == None: 		# graph oriented ?
					p[str(r[-1])]= len(r)			# en partant de n, il faut len(r) cases pour aller a r[-1]	
			elif (r[-1] == n):				# ou si la route fini avec ce croisement
				if graph.get(str(r[0])) == None:
					p[str(r[0])]= len(r)
		#if p != {}:
		graph[str(n)] = p
	return graph


def convert_str_to_list(chem):
	# convertir des coordonnés de str à list
	chem2 = []
	for e in chem:
		e = e.strip("[]")
		e=e.split(",")
		e[0] = int(e[0])
		e[1] = int(e[1])
		chem2.append(e)
	
	return chem2



# EXEMPLE
"""
wege=[  [0,0] , [1,0] , [2,0], [3,0], [4,0], [5,0] , [2,1] ,[2,2] ,[2,3] ,[2,4] , [2,5], [1,3], [0,3], [0,4], [0,5], [0,6], [0,7], [5,1], [5,2], [6,2], [7,2], [7,1], [8,1], [9,1], [10,1] , [10,2] , [10,3] , [10,4] , [11,2], [12,2] , [3,5], [4,5], [5,5], [5,4], [6,4], [7,4], [8,4], [9,4] , [1,7], [2,7], [2,8], [3,8], [4,8], [5,8], [6,8], [7,8], [8,8], [9,8], [10,8], [11,8], [12,8], [13,8], [14,8], [15,8], [16,8], [5,6], [5,7], [8,5], [8,6], [9,6], [10,6], [11,6], [12,6], [9,7]]

dep = [2,0]		# coordonnés du départ
arr = [9,6]	# coordonnés de l'arrivée

nodes = find_nodes(wege)

if dep not in nodes:
	nodes.append(dep)
if arr not in nodes:
	nodes.append(arr)

roads = find_all_roads(wege,nodes)

graph = graph_data(nodes,roads)

chem = dijkstra(graph, str(dep),str(arr))

chem = convert_str_to_list(chem)

chem = nodes_to_list(chem,roads)

print chem

print "depart : " + str(dep)
print "arrivée : " + str(arr)
"""


