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=[]

##applique l'algorithme de Variable Ordering
def variableOrdering():
	NOEUDS.sort()

##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 de depart de la contrainte
##@param noeud2 le noeud d'arrive de la contrainte
##@ret toutes les contraintes bineaires ente n1 -> n2
def retourneContraintesBinaires(noeud1,noeud2):
	contraintes=[]
	for a in ARCS:
		if (a.refContrainte.depart==noeud1.refVar and a.refContrainte.arrive==noeud2.refVar):
			if a.refContrainte not in contraintes:
				contraintes.append(a.refContrainte)
	return contraintes

##verifie si deux noeud ayant chacun une valeur sont consitant avec les contraintes entre ces deux neouds
##@param n1 le noeud 1
##@param n2 le noeud 2
##@param contraintes contraintes entre n1 et n2
##@ret true <=> consistant; else False
def consistant(n1,n2,contraintes):
	if len(contraintes)==0:
		return True
	touteVraie = lambda x, y :  x and y
	resultat=map(libPSC.ContrainteBinaire.estValide, contraintes)
	const = reduce(touteVraie,resultat)
	return const
	

##verifie la consistance des varibles PAS ENCORE instantiee
##@param n1 le noeud 1 instantiee
##@param n2 le noeud a verifier si consitent,
##@param containtes les contraintes entre n1 et n2
def consistanceFuture(n1,n2,contraintes):
	if len(contraintes)==0:
		return True
	touteVraie = lambda x, y :  x and y
	n2.refVar.enleveDuLabel(n1.refVar.valeur)
	resultat=map(libPSC.ContrainteBinaire.estPossibleAvecLabel, contraintes)
	const = reduce(touteVraie,resultat)
	return const
   
	
##reinitialise le label de tous les variables
def initLabelDesVariables():
	for n in NOEUDS:
		n.refVar.initLabel()

##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"


##retourne le contenu des label de tous les noeuds dans un tableau
def retournelabels():
	labels=[]
	for n in NOEUDS:
		labels.append(copy.deepcopy(n.refVar.label))
	return labels

##met a jour les labels de tous les noeuds
##@param labels les nouveau labels
def metAJourlabels(labels):
	for i in range(0,len(NOEUDS)):
		 NOEUDS[i].refVar.label=copy.deepcopy(labels[i])

			
##gere tous les noeuds dans NOEUDS
class Noeuds:

	##initialise le tableau de noeuds	
	def __init__(self):
		del 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));  

	##retourne une liste d'instances initialisee a -1
	##utilise dans le backtrack et forward checking
	##@ret [-1,...,-1]
	def instances(self):
		inst=[]
		for n in NOEUDS:
			inst.append(-1)
		return inst

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


##gere tous les noeuds dans ARCS
class Arcs:

	##initialise le tableau des ARCS   
	def __init__(self):
		del 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
	afficheNbIteration(algo,k)
	if k >= len(NOEUDS):
		afficheSolution(algo,instances)
		SOLUTION.append(copy.deepcopy(instances))
		if not touteLesSolutions:
			return instances 
	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, initialise)
				if rest != ECHEC:
					return rest

	return ECHEC			


## 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 or initialise==True:
		ITERATION=0
		SOLUTION=[]
		libPSC.NBCONTRAINTE=0
		initLabelDesVariables()
		initialise=False
		
	ITERATION=ITERATION+1
	afficheNbIteration(algo,k)
	if k>(len(NOEUDS)-1):
		afficheSolution(algo,instances)
		SOLUTION.append(copy.deepcopy(instances))
		if not touteLesSolutions:
			return instances
		
	else:
		noeud = NOEUDS[k]
		labels = retournelabels()
		for d in noeud.refVar.label: ##domaine:
			noeud.refVar.metAJourValeur(d)   
			consistantFuturOK=True
			for i in range(k+1,len(NOEUDS)):
				##print "\t\tVerification de la consitance da la valeur", d, "avec la variable non instantie",NOEUDS[i] 
				if not consistanceFuture(noeud,NOEUDS[i],retourneContraintesBinaires(noeud,NOEUDS[i])):
					consistantFuturOK=False
			if consistantFuturOK:
				instances[k]=d
				rest = forwardChecking(instances,k+1,touteLesSolutions,initialise)
				if rest!= ECHEC:
					return rest
			metAJourlabels(labels)
	return ECHEC

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