# 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


# %% Pomoćne klase

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

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


# %% Implementacija pretrage

class Pretraživač:
    def __init__(self, mesta, putevi, početak, cilj, heuristika):
        self.mesta = mesta
        self.putevi = putevi
        self.početak = početak
        self.cilj = cilj
        self.heuristika = heuristika
        self.neobrađeno = []
        self.obrađeno = {}

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

        self.neobrađeno.append(
            ČvorPretrage(self.početak, None,
                         self.heuristika(self.početak, self.cilj)))
        
        while self.neobrađeno:
            korak += 1
            trenutni_čvor = self.neobrađeno.pop(0)

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

            if trenutni_čvor.naziv == self.cilj:
                rešenje = []
                cena = 0
                while trenutni_čvor is not None:
                    rešenje.append(trenutni_čvor.naziv)
                    if trenutni_čvor.nadređeni is not None:
                        m = self.mesta.index(trenutni_čvor.naziv)
                        n = self.mesta.index(trenutni_čvor.nadređeni.naziv)
                        cena += self.putevi[m][n]
                    trenutni_čvor = trenutni_čvor.nadređeni
                rešenje.reverse()
                return (rešenje, cena)
            
            indeks_trenutnog_čvora = self.mesta.index(trenutni_čvor.naziv)

            for i, put in enumerate(self.putevi[indeks_trenutnog_čvora]):
                if put > 0:
                    naziv_novog_čvora = self.mesta[i]
                    if (naziv_novog_čvora not in self.obrađeno and
                            not [a for a in self.neobrađeno if (
                                a.naziv == naziv_novog_čvora)]):
                        novi_čvor = ČvorPretrage(
                            naziv_novog_čvora, trenutni_čvor,
                            self.heuristika(naziv_novog_čvora, self.cilj))

                        for a, b in enumerate(self.neobrađeno):
                            if novi_čvor.vrednost < b.vrednost:
                                self.neobrađeno.insert(a, novi_čvor)
                                break
                        else:
                            self.neobrađeno.append(novi_čvor)

            self.obrađeno[trenutni_čvor.naziv] = trenutni_čvor

        return None


# %% Priprema podataka i heuristike

mesta = ["Beograd", "Milano", "Rim", "Barselona", "Madrid", "Malaga"]
print("Mesta")
print(mesta)
print("")

putevi = [
    [   0,  890,  730,   -1,   -1,   -1],
    [ 890,    0,   -1,  730,   -1,   -1],
    [ 730,   -1,    0,   -1, 1370, 1570],
    [  -1,  730,   -1,    0,  510,  780],
    [  -1,   -1, 1370,  510,    0,  420],
    [  -1,   -1, 1570,  780,  420,    0]
]
print("Putevi")
for red in putevi:
    print(red)
print("")

udaljenosti = [
    [   0,  890,  730, 1540, 2040,  2280],
    [ 890,    0,  480,  730, 1200,  1500],
    [ 730,  480,    0,  870, 1370,  1570],
    [1540,  730,  870,    0,  510,   780],
    [2040, 1200, 1370,  510,    0,   420],
    [2280, 1500, 1570,  780,  420,     0]
]
print("Udaljenosti")
for red in udaljenosti:
    print(red)
print("")

def heuristika(a, b):
    i = mesta.index(a)
    j = mesta.index(b)
    return udaljenosti[i][j]

print("Heuristika Beograd -> Rim: {}".format(
    heuristika("Beograd", "Rim")))
print("Heuristika Milano -> Barselona: {}".format(
    heuristika("Milano", "Barselona")))
print("Heuristika Barselona -> Madrid: {}".format(
    heuristika("Barselona", "Madrid")))
print("Heuristika Beograd -> Madrid: {}".format(
    heuristika("Beograd", "Madrid")))
print("")


# %% Izvođenje pretrage

pretraživači = [
    Pretraživač(mesta, putevi, "Madrid", "Madrid", heuristika),
    Pretraživač(mesta, putevi, "Madrid", "Malaga", heuristika),
    Pretraživač(mesta, putevi, "Beograd", "Malaga", heuristika),
    Pretraživač(mesta, putevi, "Malaga", "Beograd", heuristika),
    Pretraživač(mesta, putevi, "Milano", "Rim", heuristika)]

for pretraživač in pretraživači:
    print("Pretraga: početak='{}', cilj='{}'".format(
        pretraživač.početak, pretraživač.cilj))
    
    rešenje = pretraživač.pretraživanje()
    
    print("Rešenje: {}".format(rešenje if rešenje is not None else "/"))
    print("")