# -*- coding: iso-8859-15 -*-

## Liste des opérateurs:
operators = []

## Description de la situation initiale:
initialState = []

## Liste des états encore à explorer:
openList = []

## Heuristique d'ordonnancement pour A*:
heuristicFn = []

## Fonction vérifiant la consistence d'un noeud, càd si ses buts sont
## cohérents:
consistentFn = []

## Liste des solutions trouvées:
plannerSolutions = []

###===================================================================
###   OPERATEURS
###===================================================================

class Operator:

	## Constructeur
	## @param action Action effectuée
	## @param preconds Liste des préconditions
	## @param addList Liste ajoutée
	## @param deleteList liste enlevée
	## @cost cost Coût de l'opérateur.
	def __init__(self, action, preconds, addList, deleteList, cost):
		self.action=action
		self.preconds=preconds
		self.addList=addList
		self.deleteList=deleteList
		self.cost=cost

	## Retourne une représentation en string des caractéristiques de l'opérateur
	def __str__(self):
		out = ("<Operator %s; Preconds=%s; Add-List=%s; Delete-List=%s; cost=%s>\n" % (self.action, self.preconds, self.addList, self.deleteList, self.cost))
		return out

## Définit un nouvel opérateur d'après sa <description> et l'ajoute
## a la variable globale operators.
## @param description Liste [action preconditions add-list delete-list coût]
def defOperator(description):
	global operators
	op = Operator(description[0],description[1],description[2],description[3],description[4])
	operators.append(op)


###===================================================================
###   ETATS (STATES)
###===================================================================

class State:

	## Constructeur
	## @param goals Les buts de l'état.
	## @param operators La liste des opérateurs appliqués à cet état pour parvenir a l'état final
	## @param cost Le coût de cet état
	def __init__(self, goals, ops, cost=0):
		self.goals = goals
		self.operators = ops
		self.cost = cost

	## Compare deux états
	## @param other L'autre état à comparer
	def __cmp__(self, other):
		return self.cost - other.cost

	## Retourne une représentation en string avec les caractéristiques de l'état
	def __str__(self):
		out = ("<State: Goals=%s; operators=%s; cost=%s>\n" % (self.goals, self.operators, self.cost))
		return out

	## Retourne True ssi l'état est une solution, càd si ses buts
	## font partie de l'état initial.
	def isSolution(self):
		global initialState
		return set(self.goals).issubset(set(initialState))

	## Calcule le coût de l'état d'après la fonction heuristique
	## heuristicFn et retourne l'état.
	def computeCost(self):
		global heuristicFn
		self.cost = apply(heuristicFn, [self])
		return self

	## Retourne tous les nouveaux états que l'on peut obtenir en
	## appliquant les opérateurs à l'état .
	## @param ops Les opérateurs à appliquer
	def applyOperators(self, ops):
		rs = []
		for o in ops:
			s = self.applyOperator(o)
			if isinstance(s, State):
				rs.append(s)
		return rs

	## Applique l'opérateur <op> a l'état s'il est applicable et
	## retourne le nouvel état.
	## @param op L'opérateur à appliquer
	def applyOperator(self, op):
		global consistentFn
		x = self.applicable(op)
		if x:
			newGoals = list(set(self.goals).union(set(op.preconds)).difference(set(x)))
			newOperators = self.operators[:]
			newOperators.append(op)
			newState = State(newGoals, newOperators)
			newState.computeCost()
			if apply(consistentFn, [newState]):
				return newState
		return []
	
	## Verifie que l'opérateur op peut s'appliquer a l'état, càd que:
	## - aucun prédicat de la deleteList de op ne fait partie des
	##	 buts de l'état.
	## - au moins un but de l'état est satisfait par un prédicat de
	##	 l'addList de op.
	## Retourne la liste des buts satisfaits par op.
	## @param op L'opérateur à appliquer
	def applicable(self,op):
		if len(set(self.goals).intersection(set(op.deleteList))) < 1:
			return set(self.goals).intersection(set(op.addList))
		else:
			return []

	## Analyse moyens-buts; retourne le nombre de buts de l'état 
	## qui ne sont pas satisfaits par l'état initial initialState.
	def meansEnds(self):
		global initialState
		return len(set(initialState).difference(set(self.goals)))

	## Retourne la somme des coûts des opérateurs appliqués a l'état
	## final pour obtenir l'état.
	def opCost(self):
		if self.operators:
			return reduce(lambda x,y: x + y.cost, self.operators, self.cost)
		else:
			return self.cost
	
	## Affiche la solution
	def printPlannerSolution(self):
		print("== PLANNER SOLUTION ==")
		i = 0
		for op in self.operators:
			print("Action %s: %s" % (i, op.action))
			i = i+1
  


###===================================================================
###   INITIALISATION et CONSTRUCTION
###===================================================================

## Initialise et construit un nouveau planificateur.
## @param initState L'état initial	  
## @param goals Les buts
## @param ops La description des opérateurs
## @param consistent La fonction de consistance
## @param heuristic La fonction heuristique utilisée par A*
def buildPlanner(initState, goals, ops, consistent, heuristic):
	global operators		
	global initialState
	global plannerSolutions
	global openList
	global consistentFn
	global heuristicFn
	operators = []			
	initialState = initState
	plannerSolutions = []
	openList = [State(goals,[],0)]
	consistentFn = consistent
	heuristicFn = heuristic
	for op in ops:
		defOperator(op)
	return openList[0]


###===================================================================
###   RECHERCHE
###===================================================================

## Recherche une solution en explorant au plus <max-steps> états.
## @param maxSteps Le nombre maximal de pas
def findPlan(maxSteps=1000):
	global plannerSolutions
	sol, steps = AStarSearch(maxSteps)
	if isinstance(sol,State):
		print("FOUND A SOLUTION IN %s STEPS\n" % (steps))
		plannerSolutions = [sol] + plannerSolutions
		sol.printPlannerSolution()
		return sol
	elif steps < 0:
		print("NO MORE SOLUTIONS (open list exhausted)\n")
	else:
		print("NO SOLUTION FOUND IN %s STEPS\n" % (steps))

## Algorithme de recherche A*. Effectue au maximum <max-steps> pas
## de recherche. N'utilise pas de closed-list.
## Retourne 2 valeurs:
## - la solution trouvée ou [] si aucune solution n'a été
##	 trouvée.
## - le nombre de pas de recherche effectués. Si openList a
##	 été "vidée" (càd il n'y a plus de solutions), cette
##	 deuxieme valeur sera -1.
## @param maxSteps Le nombre maximal de pas
def AStarSearch(maxsteps):
	global openList
	step = 0
	while len(openList) > 0:
		s = openList[0]
		openList = openList[1:]
		if s.isSolution():
			return s, step
		openList = openList + s.applyOperators(operators)
		openList.sort()
		step = step + 1
		if step == maxsteps:
			return [], step
	return [], -1


###===================================================================
###   UTILITAIRES
###===================================================================

## Affiche toutes les solutions trouvées par le planificateur
def printPlannerSolutions():
	global plannerSolutions
	print(">>> FOUND %s PLANS <<<" % (len(plannerSolutions)))
	for sol in plannerSolutions.revers():
		sol.printPlannerSolution()