# -*- encoding: iso-8859-15 -*-
import libRecherche
import copy
#################################################################################
print "Chargement du module de recherche"
#################################################################################
class VILLE_PAS_TROUVE(Exception):
	def __init__(self,nom):
		self.nom=nom

ECHEC='echec'

CARTE={}


class Ville(libRecherche.Element):
	## Constructeur
	## @param nom le nom de l'objet ATTENTION Utilisez comme identificateur!!!!
	## @param posX la position sur l'axe X
	## @param posY la position sur l'axe Y
	## @param voisins autre object accesible depuis self par un arc
	def __init__ (self, nom, posX, posY):
		libRecherche.Element.__init__(self, nom, posX, posY)

	## retourne une representation en string
	def __str__ (self):
		return ("ville <%s, %d, %d>" % (self.nom, self.posX, self.posY))

class retourner:

	def __init__(self, object):
		self.object = object

	def __getattr__(self, name):
		def proxy(*args, **kwds):
			getattr(self.object, name)(*args, **kwds)
			return self.object
		return proxy


class Villes:
	## Constructeur
	## instantie un attribut villes qui sera un dictionnaire avec la clef=ville.nom et valeur=objet_ville
	def __init__(self):
		CARTE = {}

	## Construit et ajoute la ville au dictionnaire villes		
	## param nom le nom de la ville
	## @param posX la position de la ville sur l'axe X
	## @param posY la position de la ville sur l'axe Y
	def construitVille(self,nom, posX, posY):
		v = Ville(nom, posX, posY)
		CARTE[nom] = v

	## chereche et retourne la ville associé a un nom
	## @param nom le nom de la ville
	## @ret la ville se elle est dans le dictionnaire; sinon -1
	def chercheVille(self,nom):
		return CARTE.get(nom, VILLE_PAS_TROUVE)

	## definit une route ( un arc) entre deux villes
	## @param nom_ville1 le nom  de la ville no 1
	## @param nom_ville2 le nom la ville no 2
	def construitRoute(self,nom_ville1,nom_ville2):
		a = self.chercheVille(nom_ville1)
		b = self.chercheVille(nom_ville2)
		a.ajouteVoisin(b)
		b.ajouteVoisin(a)
		

	## imprime toutes less villes avec leur connection			
	def imprimeLesVilles(self):
		for v in CARTE.itervalues():
			print v

## Algorithm de recherche
## @param depart ville de depart
## @param but ville d'arrivee
## @param methode la méthode utilisee (DFS,BFS,A*)
def recherche(depart, but, methode):
	Q = [libRecherche.Noeud(depart)]
	but = libRecherche.Noeud(but)
	while Q:
		n = Q.pop(0)
		#print "working on: %s\n" % n
		if n.refElement.nom == but.refElement.nom:
			return n
		else:
			S = n.successeurs(but)
			Q = ajouteSuccesseurs(Q,S,methode)
	return ECHEC

## Algorithm de recherche optimise
## Verifie chaque noeud ne soit visité qu'une seule fois
## @param depart ville de depart
## @param but ville d'arrivee
## @param methode la méthode utilisee (DFS,BFS,A*)
def rechercheOptimisee(depart, but, methode):
	pass


## ajoute les succeseurs S a Q suivant la methode de recherche
## @param Q la liste initiale
## @param S la liste des successeurs
## @param methode la màthode de recherche				
def ajouteSuccesseurs(Q,S,methode):
	if methode == "DFS":
		return S + Q
	if methode == "BFS":
		return Q + S
	if methode == "A*":
		Q = Q + S
		return Q.sort()
	return ECHEC


execfile("carte.py")
villes=Villes()
villes.imprimeLesVilles()
start=villes.chercheVille("A")
print "Début=", start
fin = villes.chercheVille("P")
print "But=", fin
print "Recherche avec DFS=\n", recherche(start,fin,"DFS")
print "Recherche avec BFS=\n", recherche(start,fin,"BFS")
print "Recherche optimisée avec BFS=\n", rechercheOptimisee(start,fin,"BFS")
print "Recherche avec A*=\n", recherche(start,fin,"A*")
print "Recherche optimisée avec A*=\n", rechercheOptimisee(start,fin,"A*")