# Modulo: tree_search
#
# Fornece um conjunto de classes para suporte a resolucao de
# problemas por pesquisa em arvore:
#    SearchDomain  - dominios de problemas
#    SearchProblem - problemas concretos a resolver
#    SearchNode    - nos da arvore de pesquisa
#    SearchTree    - arvore de pesquisa, com metodos para
#                    a respectiva construcao
#
#  (c) Luis Seabra Lopes, Introducao a Inteligencia Artificial, 2012-2014


# Dominios de pesquisa
# Permitem calcular
# as accoes possiveis em cada estado, etc
class SearchDomain:
    # construtor
    def __init__(self):
        abstract

    # lista de accoes possiveis num estado
    def actions(self, state):
        abstract

    # resultado de uma accao num estado, ou seja, o estado seguinte
    def result(self, state, action):
        abstract

    # custo de uma accao num estado
    def cost(self, state, action):
        abstract

    # custo estimado de chegar de um estado a outro
    def heuristic(self, state, goal_state):
        abstract


# Problemas concretos a resolver
# dentro de um determinado dominio
class SearchProblem:
    def __init__(self, domain, initial, goal):
        self.domain = domain
        self.initial = initial
        self.goal = goal

    def goal_test(self, state):
        return state == self.goal


# Nos de uma arvore de pesquisa
class SearchNode:
    def __init__(self, state, parent, depth, heuristica, cost):
        self.state = state
        self.parent = parent
        self.depth = depth
        self.heuristica = heuristica
        self.cost = cost

    def __str__(self):
        return "no(" + str(self.state) + "," + str(self.parent) + ")"

    def __repr__(self):
        return str(self)


# Arvores de pesquisa
class SearchTree:
    # construtor
    def __init__(self, problem, strategy='greedy', limit=500):
        self.problem = problem
        self.limit = limit
        root = SearchNode(problem.initial, None, 0, 0, 0)
        self.open_nodes = [root]
        self.strategy = strategy

    # obter o caminho (sequencia de estados) da raiz ate um no
    def get_path(self, node):
        if node.parent == None:
            return ([], 0)
        path = self.get_path(node.parent)
        return (path[0] + [node.state], node.depth)

    # procurar a solucao
    def search(self):
        opened_states={}
        possiveis=[]
        while self.open_nodes != [] and len(possiveis)<10:
            node = self.open_nodes[0]
            if (((node.depth > self.limit) and self.limit != -1) or (self.problem.goal_test(node.state))):
                #return self.get_path(node)
                possiveis.append( node )
                continue
            self.open_nodes[0:1] = []
            lnewnodes = []
            for a in self.problem.domain.actions(node.state):
                newstate = self.problem.domain.result(node.state, a)
                if (opened_states.get(newstate) != True):
                    lnewnodes += [SearchNode(newstate,
                                             node, node.depth + 1,
                                             self.problem.domain.heuristic(newstate, self.problem.goal),
                                             node.cost + self.problem.domain.cost(node.state, a)
                                             )]
            self.add_to_open(lnewnodes)
            opened_states[node.state] = True
        if possiveis != []:
            possiveis.sort(key = lambda x : x.cost)
            return self.get_path(possiveis[0])
        return None

    # juntar novos nos a lista de nos abertos de acordo com a estrategia
    def add_to_open(self, lnewnodes):
        self.open_nodes.extend(lnewnodes)
        # Greedy
        # self.open_nodes.sort(key = lambda x : x.heuristica)
        # A*
        self.open_nodes.sort(key=lambda x: x.cost + x.heuristica*0.6)