#!/usr/bin/env python
# encoding=utf-8 (pep 0263)

""" Implementace algoritmu A* """

from linked_lists import Cons, Nil, member

class BestSearch(object):
    def __init__(self, bound, is_goal, move_anyYC, h):
        self.total = 0
        self.bound = bound
        self.is_goal = is_goal
        self.move_anyYC = move_anyYC
        self.h = h

    def search(self, start):
        self.total = 0
        for _, solved, sol in self.expand(Nil, (start, 0, 0), self.bound):
            if solved == "yes":
                yield sol

    def expand(self, path, tree, bound):
        if len(tree) == 3: # a leaf
            node, f_, g = tree
            if self.is_goal(node):
                yield (None, "yes", Cons(node, path))
            if f_ <= bound:
                succ = Nil
                for m, c in self.move_anyYC(node):
                    if not member(m, path):
                        self.total = self.total + 1
                        succ = Cons((m, c), succ)
                if succ == Nil:
                    yield (None, "never", None)
                else:
                    trees = self.succlist(g, succ)
                    f1 = self.bestf(trees)
                    for tree1, solved, sol in self.expand(path, (node, f1, g, trees), bound):
                        yield (tree1, solved, sol)
            elif f_ > bound:
                yield (tree, "no", None)
        else: # a tree
            node, f_, g, trees = tree
            if trees == Nil:
                yield (None, "never", None)
            else:
                if f_ <= bound:
                    bound1 = min(bound, self.bestf(trees.tail))
                    for t1, solved1, sol1 in self.expand(Cons(node, path), trees.head, bound1):
                        for tree1, solved, sol in self.continue_(path, (node, f_, g,
                                                                        Cons(t1, trees.tail)),
                                                                 bound, solved1, sol1):
                            yield (tree1, solved, sol)
                elif f_ > bound:
                    yield (tree, "no", None)

    def continue_(self, path, tree, bound, subtr_solved, sol):
        node, _, g, trees = tree
        if subtr_solved == "yes":
            yield (None, "yes", sol)
        elif subtr_solved == "no":
            nts = self.insert(trees.head, trees.tail)
            f1 = self.bestf(nts)
            for tree1, solved, sol in self.expand(path, (node, f1, g, nts), bound):
                yield (tree1, solved, sol)
        elif subtr_solved == "never":
            f1 = self.bestf(trees.tail)
            for tree1, solved, sol in self.expand(path, (node, f1, g, trees.tail), bound):
                yield (tree1, solved, sol)

    def succlist(self, g0, succ):
        if succ == Nil:
            return Nil
        n, c = succ.head
        g = g0 + c
        f_ = g + self.h(n)
        ts1 = self.succlist(g0, succ.tail)
        ts = self.insert((n, f_, g), ts1)
        return ts

    def bestf(self, trees):
        if trees == Nil:
            return self.bound
        return f(trees.head)

    def insert(self, t, ts):
        if f(t) <= self.bestf(ts):
            return Cons(t, ts)
        return Cons(ts.head, self.insert(t, ts.tail))

def f(tree):
    if len(tree) == 3: # a leaf
        _, f_, _ = tree
    else: # a tree
        _, f_, _, _ = tree
    return f_