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

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 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 testeSubstitution(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]=='?')
################################################################################


###############################################################################
## 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 construitSubstitution(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 associé une variable
## @param variable la variable
## @param substituions la liste des substituion
## @ret la substitution associé à la varibale si elle existe, sinon retourn False
################################################################################
def trouveSubstitution(variable, subs):
	if testeSubstitution(subs) and subs.has_key(variable):
		return {variable: subs[variable]}
	else:
		return False
################################################################################
    
########################..#######################################################
## verifie que la variable est dans les substitutions
## @param variable la variable
## @param substituions la liste des substituion
## @ret True <=> variable est dans les substitutions; else False
################################################################################
def variableDansSubstitutions(variable, subs):
	return subs.has_key(variable)
################################################################################

###############################################################################
## 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 unionSubstitution(sub1,sub2):
	if testSubstitution(sub1) and testeSubstitution(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 , substitutions):  
    ## test si on a pattern est un atome
    if testeAtome(pattern):
        if testeVariable(pattern) and substitutions.has_key(pattern):
            return substitueVariables(retourneValeur(trouveSubstitution(pattern,substitutions)),substitutions)
    else:
        for x in pattern[:]:
            pattern.append(substitueVariables(x , substitutions))
            pattern.pop(0)            
    return pattern
#####################################################################    

###############################################################################
## fait l'unification entre deux proposition passées en parametres
## ATTENTION Les propositions peuvent contenire des variables
## @param proposition1 proposition 1 avec variable
## @param proposition2 porposition 2 avec variable  
## @ret substitution dans un dico is le filtrage reussi : {'?x':'a',...}, 'FAIL' sinon
###############################################################################
def unifit(pat1, pat2):
	if testeAtome(pat1) or testeAtome(pat2):
		if not testeAtome(pat1):
			pat1, pat2 = pat2, pat1

		if pat1 == pat2:
			return {}
		else:
			if testeVariable(pat1):
				if ::
					return echec
				else:
					return {pat1: pat2}
			else:
				if testeVariable(pat2):
					return {pat2: pat2}
				else:
					return echec
	else:
		f1 = pat1[0]
		t1 = pat1[1:]
		f2 = pat2[0]
		t2 = pat2[1:]
		z1 = unifit(f1, f2)
		if z1 == echec:
			return echec
		g1 = substitueVariables(t1, z1)
		g2 = substitueVariables(t2, z1)
		z2 = unifit(g1, g2)
		if z2 == echec:
			return echec
		return unionSubstitution(z1, z2)
                    
###############################################################################

################################################################################
## fait l'unification entre deux proposition passées en parametres
## ATTENTION Les propositions peuvent contenire des variables
## @param proposition1 proposition 1 avec variable
## @param proposition2 porposition 2 avec variable
## @param ênvironement un environement {'?x':'a',...}   
## @ret substitution dans un dico is le filtrage reussi : {'?x':'a',...}, 'ECHEC' sinon
###############################################################################
def unifcation(proposition1, proposition2, environement=None):
    if environement is None:
        environement={}
    if environement==echec:
        return echec
    else :
        proposition1 = substitueVariables(proposition1,environement)
        proposition2 = substitueVariables(proposition2,environement)
        return unionSubstitution(environement,unifit(proposition1, proposition2))
##############################################################################
execfile("testSubstitueVariables.py")
execfile("testUnifit.py")
execfile("testUnificateur.py")