# %% Osnovne klase

class Graph:
    def __init__(self, node_names):
        self.network = {name: {} for name in node_names}

    def form_edge(self, source_name, destination_name, weight=1):
        self.network[source_name][destination_name] = weight
        self.network[destination_name][source_name] = weight


class SearchNode:
    def __init__(self, name, parent, value):
        self.name = name
        self.parent = parent
        self.value = value

    def __str__(self):
        return ("SNode (" + str(self.name) + " | " + str(self.parent) + 
                " | " + str(self.value) + ")")

# %% Implementacija pohlepne pretrage


class GreedySearch:
    def __init__(self, graph, name_source, name_destination, heuristics):
        self.graph = graph
        self.name_source = name_source
        self.name_destination = name_destination
        self.heuristics = heuristics
        self.searching = []
        self.searched = {}

    def search(self, verbose=True):
        self.searching = []
        self.searched = {}
        
        self.searching.append(
            SearchNode(self.name_source,
                       None,
                       self.heuristics(self.name_source,
                                       self.name_destination)))
        while self.searching:
            current = self.searching.pop(0)

            if verbose:
                print("\t", "current: ", current)

            if current.name == self.name_destination:
                solution = []
                cost = 0
                while current is not None:
                    solution.append(current.name)
                    if current.parent is not None:
                        cost += (self.graph.network[current.parent.name]
                                 [current.name])
                    current = current.parent
                solution.reverse()
                return (solution, cost)

            for k, s in self.graph.network[current.name].items():
                if (k not in self.searched and 
                    not [a for a in self.searching if a.name == k]):
                    new = SearchNode(k,
                                     current,
                                     self.heuristics(k,
                                                     self.name_destination))
                    for a, b in enumerate(self.searching):
                        if new.value < b.value:
                            self.searching.insert(a, new)
                            break
                    else:
                        self.searching.append(new)

            self.searched[current.name] = current

        return None