# Univerzitet u Novom Sadu, Fakultet tehničkih nauka, Novi Sad, Srbija
# Studijski program OAS Informacioni inženjering
# Predmet Metode i tehnike nauke o podacima

# Pomoćni sadržaj


# %% Biblioteke

import math


# %% Pomoćne klase

class Graf:
    def __init__(self, nazivi_čvorova):
        self.mreža = {naziv: {} for naziv in nazivi_čvorova}

    def formiranje_grane(self, naziv_polaznog_čvora, naziv_odredišnog_čvora, 
                         težina=1):
        self.mreža[naziv_polaznog_čvora][naziv_odredišnog_čvora] = težina
        self.mreža[naziv_odredišnog_čvora][naziv_polaznog_čvora] = težina

    def __str__(self):
        redovi = []
        for k, s in self.mreža.items():
            redovi.append("'{}' : {}".format(k, s))
        return "\n".join(redovi)

class ČvorPretrage:
    def __init__(self, naziv, nadređeni, vrednost_g, vrednost_h):
        self.naziv = naziv
        self.nadređeni = nadređeni
        self.vrednost_g = vrednost_g
        self.vrednost_h = vrednost_h

    @property
    def vrednost_f(self):
        return self.vrednost_g + self.vrednost_h

    def __str__(self):
        return ("Čvor ({} | {} | {} | {})".format(
            self.naziv, 
            self.nadređeni if self.nadređeni is not None else "/", 
            self.vrednost_g,
            self.vrednost_h))


# %% Implementacija pretrage IDA*

class PretragaIDAZvezda:
    def __init__(self, graf, početak, cilj, heuristika):
        self.graf = graf
        self.početak = početak
        self.cilj = cilj
        self.heuristika = heuristika
        self.neobrađeno = []
        self.obrađeno = []

    def pretraživanje(self, prikaz=True):
        self.neobrađeno = []
        self.obrađeno = []

        iteracija = 0
        ograničenjе = -1
        ograničenje_kandidat = self.heuristika(self.početak, self.cilj)
        
        while ograničenje_kandidat > ograničenjе:
            iteracija += 1
            ograničenjе = ograničenje_kandidat

            if prikaz:
                print("\t", "{}. iteracija: ograničenjе={}".format(
                    iteracija, ograničenjе))

            korak = 0
            self.neobrađeno.clear()
            self.obrađeno.clear()

            self.neobrađeno.append(
                ČvorPretrage(self.početak, None, 0,
                             self.heuristika(self.početak, self.cilj)))

            while self.neobrađeno:
                korak += 1
                trenutni_čvor = self.neobrađeno.pop()

                if prikaz:
                    print("\t\t", "{}. trenutni čvor: {}".format(
                        korak, trenutni_čvor))

                if trenutni_čvor.naziv == self.cilj:
                    rešenje = []
                    cena = trenutni_čvor.vrednost_g

                    while trenutni_čvor is not None:
                        rešenje.append(trenutni_čvor.naziv)
                        trenutni_čvor = trenutni_čvor.nadređeni
                    rešenje.reverse()

                    return (rešenje, cena)

                for k, s in self.graf.mreža[trenutni_čvor.naziv].items():

                    vrednost_f = (trenutni_čvor.vrednost_g + s + 
                                  self.heuristika(k, self.cilj))

                    if vrednost_f > ograničenjе:
                        if (ograničenje_kandidat == ograničenjе) or (
                                ograničenje_kandidat > ograničenjе and 
                                ograničenje_kandidat > vrednost_f):
                            ograničenje_kandidat = vrednost_f
                    else:
                        novi_čvor = ČvorPretrage(k, trenutni_čvor,
                                                 trenutni_čvor.vrednost_g + s,
                                                 self.heuristika(k, self.cilj))
                        self.neobrađeno.append(novi_čvor)

        return None


# %% Formiranje grafa

graf = Graf(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"])

graf.formiranje_grane("A", "B", 2)
graf.formiranje_grane("A", "C", 3)
graf.formiranje_grane("A", "D", 4)

graf.formiranje_grane("B", "E", 3)
graf.formiranje_grane("B", "F", 4)
graf.formiranje_grane("C", "F", 5)
graf.formiranje_grane("D", "F", 2)
graf.formiranje_grane("D", "G", 3)

graf.formiranje_grane("E", "H", 3)
graf.formiranje_grane("F", "H", 2)
graf.formiranje_grane("F", "I", 5)
graf.formiranje_grane("F", "J", 3)
graf.formiranje_grane("G", "J", 2)

graf.formiranje_grane("H", "K", 4)
graf.formiranje_grane("I", "K", 4)
graf.formiranje_grane("J", "K", 2)

print("Graf")
print(graf)
print("")


# %% Definisanje heuristike

koordinate = {
    "A": (3, 5),
    "B": (2, 4),
    "C": (3, 4),
    "D": (4, 4),
    "E": (1, 3),
    "F": (3, 3),
    "G": (5, 3),
    "H": (2, 2),
    "I": (3, 2),
    "J": (4, 2),
    "K": (3, 1)
}

def heuristika(a, b):
    ka = koordinate[a]
    kb = koordinate[b]
    return round(math.sqrt((ka[0] - kb[0]) ** 2 + (ka[1] - kb[1]) ** 2), 2)

print("Heuristika A -> K: {}".format(heuristika("A", "K")))
print("Heuristika A -> G: {}".format(heuristika("A", "G")))
print("Heuristika E -> C: {}".format(heuristika("E", "C")))
print("Heuristika H -> D: {}".format(heuristika("H", "D")))
print("")


# %% Izvođenje pretrage IDA*

pretraga = PretragaIDAZvezda(graf, "A", "K", heuristika)

print("Pretraga")
rešenje = pretraga.pretraživanje()
print("")

print("Rešenje: {}".format(rešenje if rešenje is not None else "/"))