#################################################################################
print "Chargement du module objet et noeud pour la recherche"
#################################################################################
import math
import copy

class 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
	def __init__(self, nom, posX, posY):
		self.nom = nom
		self.posX = posX
		self.posY = posY
		self.voisins = []

	## ajoute un voisin à la liste
	## @param voisin le voisin à ajouter
	def ajouteVoisin(self,voisin):
		self.voisins.append(voisin)

	## verfie si un objet a un nom egale a un_nom
	## @param un_nom le lnom que l'on veut verifier
	## @ret true <=> self a un nom = a un_nom
	def verifieNom(self,un_nom):
		return un_nom == self.nom

	## retourne la distance euclidienne entre self et un object passé en parametre
	## @param objet l'object eu question
	## @ret distance euclidienne entre self et objet
	def distanceEuclidienne(self,other):
		return math.sqrt(pow(self.posX-other.posX, 2)+pow(self.posY-other.posY,2))

class Noeud:

	## Constructeur
	## @param refElementt une reference à un element qui represente le noeud
	## @param coutC le cout c(n)
	## @param coutF le cout c(n)+h(n)
	## compare deux objets
	def __init__(self, refElement, coutC=0,coutF=0):
		self.refElement = refElement
		self.coutC = coutC
		self.coutF = coutF

	 ## retourne une representation en string
	def __str__(self):
		return ("noeud <%s,%s,%s>" % (self.refElement.nom, self.coutC, self.coutF))

	## compare deux objets
	def __cmp__(self, n2):
		return cmp(self.coutF, n2.coutF)


	## test si un noeud est une solition
	## @param refElement l'element reference equivalent à la destination final
	## @ret true <=>  self est l'objet final
	def estUneSolution(self,refElement):
		return self.refElement == refElement

	## met à jour le cout c(n) du noeud passée en parametre
	## @param succ le noeud à mettre à jour
	def metAJourCoutC(self,succ):
		succ.coutC = self.coutC + self.refElement.distanceEuclidienne(succ.refElement)

	## met à jour le cout f(n)=c(n)+h(n) du noeud passée en parametre
	## h(n)=distance euclidienne entre self et le but
	## @param succ le noeud à mettre à jour
	def metAJourCoutF(self,succ):
		succ.coutF = succ.coutC + self.refElement.distanceEuclidienne(succ.refElement)

	## retourne tous les voisins du noeud
	## param but la ville de dstination
	def successeurs(self,but):
		l = []
		for ro in self.refElement.voisins:
			n = Noeud(ro)
			self.metAJourCoutC(n)
			but.metAJourCoutF(n)
			l.append(n)

		return l