# -*- encoding:iso-8859-15  -*-
#################################################################################
#################################################################################

##La variable globale utilsee pour signifier un ECHEC
echec='ECHEC'

################################################################################
## retourne True si le symbole est une liste (cad: [])
## @param x le symbole a tester
## @ret True <=> x est une liste
################################################################################
def testeListe(x):
    return type(x)==type([])
################################################################################

################################################################################
## retourne True si le symbole est une liste vide (cad: [])
## @param x le symbole a tester
## @ret True <=> x est une liste vide
################################################################################
def testeListeVide(x):
    return (type(x)==type([]) and len(x)==0)
################################################################################

###############################################################################
##retourne True si le symbole est un atome (i.e.: ' ')
## @param x le symbole a tester
## @ret True <=> x est un atome
#################################################################################
################################################################################
def testeAtome(x):
    return type(x)==type('')
################################################################################

################################################################################
## retourne True si le symbole est une variable; i.e.:commence par ?
## @param x le symbole à tester
## @ret True <=> x est une variable
## '?toto' => True
## 'toto' => False
################################################################################
def testeVariable(x):
    return (testeAtome(x) and x[0]=='?')
################################################################################

################################################################################
## retourne le symbol x dans une liste
## @param x le symbole 
## @ret [x]
################################################################################
def retourneListe(x):
    return [x]
###############################################################################

################################################################################
## retourne True si le symbole est une substitution
## @param x le symbole à tester
## @ret True <=> x est une substitution
################################################################################
def testeSub(x):
    return type(x)==type({})
################################################################################

###############################################################################
## construit et retourne une substitution entre une variable et une expression
## @param variable la variable
## @param datum préposition sans variable
## @ret une substitution {variable:datum}
################################################################################
def construitSub(variable, datum):
	return {variable: datum}
################################################################################

###############################################################################
## retourne la variable d'une substitution
## @param substitution la substitution
## @ret la variable de la substitution
################################################################################
def retourneVariable(sub):
	return sub.keys()[0]
################################################################################

###############################################################################
## retourne la valeur d'une substitution
## @param substitution la substitution
## @ret la valeur de la substitution
################################################################################
def retourneValeur(sub):
	return sub.values()[0]
################################################################################

###############################################################################
## retourne la substitution associee a une variable, càd: {variable:definition_de_la_variable}
## @param variable la variable
## @param substitutions la liste des substitutions
## @ret la substitution associee à la variable si elle existe dans substituions, sinon retourne False
################################################################################
def trouveSub(variable, subs):
	if testeSub(subs) and subs.has_key(variable):
		return {variable: subs[variable]}
	else:
		return False
################################################################################

###############################################################################
## construit l'union de deux substitutions
## @param substitution1 la premiere substitution
## @param substitution2 la deuxieme substitution
## @ret substitution1 UNION substitution2; echec if substitution1 ou substitution2 ne sont pas des substitutions
###############################################################################
def unionSub(sub1,sub2):
	if testeSub(sub1) and testeSub(sub2):
		sub1.update(sub2)
		return sub1
	else:
		return echec
################################################################################ 
    
###############################################################################
## retourne la proposition avec les variables remplacees par leurs valeurs
## @param pattern la proposition (contient des variables, atomes,... sous forme [' ',' ', ' '] OU ' ' ou ['[]'...])
## @param substitutions la liste des substitutions {a:b, c:d,...}
## @ret la proposition avec les variables remplacees par leur valeurs
################################################################################
def substitueVariables(pattern , subs):
	if testeListe(pattern):
		return [substitueVariables(x, subs) for x in pattern]
	else:
		z = trouveSub(pattern, subs)
		#return subs.get(pattern, pattern)
		if z:
			return retourneValeur(z)
		else:
			return pattern
################################################################################    

################################################################################
## filtrage
## @param datum la propopsition SANS variable
## @param pattern la proposition AVEC variables
## @ret les substitution  <=> le filtrage a reussi: {'?x':'a',...}, 'ECHEC' sinon
################################################################################
def filtrage(datum,pattern):
	if pattern == [] and datum == []:
		return {}
	if pattern == [] or datum == []:
		return echec
	if testeAtome(pattern):
		if pattern == datum:
			return {}
		else:
			if testeVariable(pattern):
				return {pattern: datum}
			else:
				return echec
	else:
		if testeAtome(datum):
			return echec
	
	f1 = datum[0]
	t1 = datum[1:]
	f2 = pattern[0]
	t2 = pattern[1:]
	z1 = filtrage(f1, f2)
	if z1 == echec:
		return echec
	g1 = t1
	g2 = substitueVariables(t2, z1)
	z2 = filtrage(g1, g2)
	if z2 == echec:
		return echec
	return unionSub(z1, z2)

################################################################################ 

#################################################################################
## fait le pattern macthing
## @param datum un datum
## @param pattern une proposition pouvant contenir des variables
## @param environement un environement {}, valeur par defaut={}
## @ret filtrage(proposition,datum) si OK else FAIL
#################################################################################        
def match(datum,pattern, env={}):
	fs = filtrage(substitueVariables(datum, env), substitueVariables(pattern, env))
	if fs == echec:
		return echec
	return unionSub(fs, env)
################################################################################