import libPSC
import copy
#################################################################################
print "Chargement du module PSC"
print "\t@version: 1.1  date: 24/04/2006 modified by the vincent.schickel-zuber@epfl.ch"
print "\t@author: vincent.schickel-zuber@epfl.ch date: 24/04/2006"
print "\t@copyright: EPFL-IC-IIF-LIA 2006"
#################################################################################

##contient tous les noeuds
NOEUDS=[]

##contient tous les arcs
ARCS=[]

##valeur retournee en cas d'echec
ECHEC='echec'

##contient le nombre d'iteration de l'algorithme
ITERATION = 0

##contient les solutions de l'algorithme
SOLUTION=[]

##retourne toutes les contraintes unaires pour un noeud donnne
##@param noeud le noeud
def retourneContraintesUnaires(noeud):
	contraintes=[]
	for a in ARCS:
		if a.refContrainte.depart==noeud.refVar and a.refContrainte.arrive==noeud.refVar:
			contraintes.append(a.refContrainte)
	return contraintes

##retourne toutes les contraintes binaires pour deux noeuds donnnes
##@param noeud1 le noeud 1
##@param noeud2 le noeud 2
##@ret toutes les contraintes bineaires ente n1 et n2
def retourneContraintesBinaires(noeud1,noeud2):
	contraintes=[]
	for a in ARCS:
		if (a.refContrainte.depart==noeud1.refVar and a.refContrainte.arrive==noeud2.refVar) or (a.refContrainte.depart==noeud2.refVar and a.refContrainte.arrive==noeud1.refVar):
			if a.refContrainte not in contraintes:
				contraintes.append(a.refContrainte)
	return contraintes



##affiche la solution avec queques informations utile
##@param algo le nom de l'algo
##@param solution la solution trouvee
def afficheSolution(algo,solution):
	print "\t",algo,": SOLUTION TROUVEE en ",ITERATION,"etapes et avec ",libPSC.NBCONTRAINTE," contraintes verifiees; SOLUTION=",solution

##affiche le nombre d'iteration  avec queques informations utile
##@param algo le nom de l'algo
##@param k la pronfondeur actuelle
def afficheNbIteration(algo,k):
	print algo,": Ieration:=",ITERATION," pronfondeur actuelle:=",k ,"et",libPSC.NBCONTRAINTE," contraintes verifiees"
			
##gere tous les noeuds dans NOEUDS
class Noeuds:

	##initialise le tableau de noeuds	
	def __init__(self):
		NOEUDS=[]

	##retourne le noeud referencant le variable ayant un nom=nom
	##@param nom le nom de la variable
	##@ret le noeud, -1 si pas trouvée
	def retourneNoeud(self, nom):
		for noeud in NOEUDS:
			if noeud.refVar.nomEstEgalle(nom):
				return noeud
		return -1

	##ajoute un noeud a la lite
	def ajouteNoeud(self,noeud):
		NOEUDS.append(noeud)

	##applique la consistance des noeuds
	def consistanceDesNoeuds(self):
		for n in NOEUDS:
			n.consistanceDuNoeud(retourneContraintesUnaires(n));  

	##affiche tous les noeuds
	def __str__(self):
		str = "Noeuds\n"
		for n in NOEUDS:
			str+="\t1. "+ n.__str__()+"\n"
		return str


##gere tous les noeuds dans ARCS
class Arcs:

	##initialise le tableau des ARCS   
	def __init__(self):
		ARCS=[]

	##ajoute un arc a la lite
	def ajouteArc(self,arc):
		ARCS.append(arc)

	##retourne tous les arcs unaire pour un noeud donnne
	##@param noeud le noeud
	def retourneArcs(noeud):
		arcs2
		for a in ARCS:
			if a.refContrainte.depart==noeud.refVar and a.refContrainte.arrive==noeud.refVar:
				arcs2.append(a)
		return arcs2

	##applique la consistance des arcs
	def consistanceDesArcs(self):
		modified = True
		while modified:
			modified = False
			for a in ARCS:
				if a.refContrainte.dimension() == 2 and a.reviser():
					modified = True

	##affiche tous les noeuds
	def __str__(self):
		str = "Arcs\n"
		for n in ARCS:
			str+="\t1. "+ n.__str__()+"\n"
		return str

## Algorithme de Bactrack simple 
## @param instances les n variables; rempli jusqu'a k
## @param k la pronfondeur de la recherce (commence a 0)
## @param toutesLesSolutions si True alors cherche TOUTES les solutions, sinon s'arrete a la premiere (valeur oar defaut)
## @param initialise initialise les variables gloabl ITEARTION et SOLUTION
## @ret instances contenant la solution OU echec si aucune solution trouvée
def backtrack(instances, k, touteLesSolutions=None, initialise=None):
	algo="bt"
	global ITERATION
	global SOLUTION
	 
	if touteLesSolutions==None:
		touteLesSolutions=False
	if initialise==None:
		ITERATION=0
		SOLUTION=[]
		libPSC.NBCONTRAINTE=0
		initialise=False
		
	ITERATION=ITERATION+1

	if k >= len(NOEUDS):
		if touteLesSolutions:
			SOLUTION = SOLUTION + instances
		else:
			SOLUTION = [instances]
			afficheSolution(algo,instances)
			return SOLUTION
	else:
		n = NOEUDS[k]
		for x in n.refVar.domaine:
			n.refVar.metAJourValeur(x)
			consistant = True
			for i in range(k):
				if not reduce(lambda x,y: x and y.estValide(), retourneContraintesBinaires(n, NOEUDS[i]), True):
					consistant = False
			if consistant:
				instances[k] = x
				rest = backtrack(instances, k+1, touteLesSolutions)
				if rest != ECHEC:
					return rest

	return ECHEC			

def initLabelDesVariables():
	for n in NOEUDS:
		n.refVar.label = n.refVar.domaine

## Algorithme de Forward Chekcing simple 
## @param instances les n variables; rempli jusqu'a k
## @param k la pronfondeur de la recherce (commence a 0)
## @param toutesLesSolutions si True alors cherche TOUTES les solutions, sinon s'arrete a la premiere (valeur oar defaut)
## @param initialise initialise les variables gloabl ITEARTION et SOLUTION, et le laebl des noeuds
## @ret instances contenant la solution OU echec si aucune solution trouvée
def forwardChecking(instances, k, touteLesSolutions=None, initialise=None):
	algo="ft"
	global ITERATION
	global SOLUTION
	if touteLesSolutions==None:
		touteLesSolutions=False
	if initialise==None:
		ITERATION=0
		SOLUTION=[]
		libPSC.NBCONTRAINTE=0
		initLabelDesVariables()
		initialise=False
		
	ITERATION=ITERATION+1
	afficheNbIteration(algo,k)

	# TODO
	if k >= len(NOEUDS):
		if touteLesSolutions:
			SOLUTION = SOLUTION + instances
		else:
			SOLUTION = [instances]
			afficheSolution(algo,instances)
			return SOLUTION
	else:
		n = NOEUDS[k]
		for x in n.refVar.label:
			# TODO
			n.refVar.metAJourValeur(x)
			consistant = True
			for i in range(k+1, len(NOEUDS)):
				# TODO
				if not reduce(lambda x,y: x and y.estValide(), retourneContraintesBinaires(n, NOEUDS[i]), True):
					# TODO
					consistant = False
			if consistant:
				instances[k] = x
				rest = forwardChecking(instances, k+1, touteLesSolutions, True)
				if rest != ECHEC:
					return rest
			for i in range(k+1, len(NOEUDS)):
				# TODO
				NOEUDS[i].refVar.label = NOEUDS[i].refVar.domaine


	return ECHEC

#execfile("testConsistance.py")
execfile("test.py")