# 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, tekst, nadređeni, vrednost):
        self.tekst = tekst
        self.nadređeni = nadređeni
        self.vrednost = vrednost

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


# %% Implementacija pretrage u širinu

class PretragaŠirina:
    def __init__(self, početak, cilj):
        self.početak = početak
        self.cilj = cilj
        self.neobrađeno = []
        self.obrađeno = {}

    def pretraživanje(self, prikaz=True, unapređeno=False):
        
        if len(self.početak) == 0:
            if prikaz:
                print("\t", "početni string mora sadržati barem jedan znak")
            return None
        elif len(self.cilj) == 0:
            if prikaz:
                print("\t", "ciljni string mora sadržati barem jedan znak")
            return None
        elif len(self.početak) != len(self.cilj):
            if prikaz:
                print("\t", "početni i ciljni string nisu iste dužine")
            return None
        elif len(self.početak) == 1:
            if self.početak == self.cilj:
                rešenje = []
                rešenje.append(self.cilj)
                cena = 0
                return (rešenje, cena)
            else:
                if prikaz:
                    print("\t", "nema rešenja")
                return None
        elif sorted(list(self.početak)) != sorted(list(self.cilj)):
            if prikaz:
                print("\t", "nema rešenja")
            return None
        
        korak = 0
        self.neobrađeno = []
        self.obrađeno = {}
        
        self.neobrađeno.append(ČvorPretrage(self.početak, None, 0))
        
        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.tekst == self.cilj:
                rešenje = []
                cena = 0
                while trenutni_čvor is not None:
                    rešenje.append(trenutni_čvor.tekst)
                    if trenutni_čvor.nadređeni is not None:
                        cena += 1
                    trenutni_čvor = trenutni_čvor.nadređeni
                rešenje.reverse()
                return (rešenje, cena)
            
            for indeks in range(len(trenutni_čvor.tekst) - 1):
                tekst = list(trenutni_čvor.tekst)
                tekst[indeks] = trenutni_čvor.tekst[indeks + 1]
                tekst[indeks + 1] = trenutni_čvor.tekst[indeks]
                
                novi_čvor = ČvorPretrage("".join(tekst), trenutni_čvor, 
                                    trenutni_čvor.vrednost + 1)
                
                if unapređeno:
                    tekst_među_obrađenim = novi_čvor.tekst in self.obrađeno
                    if not tekst_među_obrađenim:
                        tekst_među_neobrađenim = False
                        for neobrađeni in self.neobrađeno:
                            if neobrađeni.tekst == novi_čvor.tekst:
                                tekst_među_neobrađenim = True
                                break        
                        if not tekst_među_neobrađenim:
                            self.neobrađeno.append(novi_čvor)
                else:
                    self.neobrađeno.append(novi_čvor)

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

        if prikaz:
            print("\t", "nema rešenja")

        return None


# %% Izvođenje pretrage u širinu

postavke = [
    {"početak": "", "cilj": "", "prikaz": True, "unapređeno": False},
    {"početak": "A", "cilj": "", "prikaz": True, "unapređeno": False},
    {"početak": "A", "cilj": "A", "prikaz": True, "unapređeno": False},
    {"početak": "A", "cilj": "B", "prikaz": True, "unapređeno": False},
    {"početak": "AB", "cilj": "AB", "prikaz": True, "unapređeno": False},
    {"početak": "ABC", "cilj": "BAC", "prikaz": True, "unapređeno": False},
    {"početak": "ABC", "cilj": "BCA", "prikaz": True, "unapređeno": False},
    {"početak": "ACE", "cilj": "BD", "prikaz": True, "unapređeno": False},
    {"početak": "ACE", "cilj": "ADE", "prikaz": True, "unapređeno": False},
    {"početak": "ABCD", "cilj": "ACBD", "prikaz": True, "unapređeno": False},
    {"početak": "ABCDE", "cilj": "ACBED", "prikaz": True, "unapređeno": True},
    {"početak": "ABCDE", "cilj": "EDACB", "prikaz": True, "unapređeno": True}]

for postavka in postavke:    
    početak = postavka["početak"]
    cilj = postavka["cilj"]
    prikaz = postavka["prikaz"]
    unapređeno = postavka["unapređeno"]
    
    print("Zadatak: početak='{}', cilj='{}'".format(početak, cilj))
    
    pretraga = PretragaŠirina(početak, cilj)
    
    print("Verzija: {}".format("unapređena" if unapređeno else "osnovna"))
    print("Detalji: {}".format("da" if prikaz else "ne"))
    
    rešenje = pretraga.pretraživanje(prikaz=prikaz, unapređeno=unapređeno)
    
    print("Rešenje: {}".format(rešenje if rešenje is not None else "/"))
    print("")