# 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 sys


# %% 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 dubinu

class PretragaDubina:
    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, obrnuto_proširenje=True):
                    
        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()

            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)
            
            novi_čvorovi = []
            
            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)
                
                novi_čvorovi.append(novi_čvor)

            if obrnuto_proširenje:
                novi_čvorovi.reverse()
            
            self.neobrađeno.extend(novi_čvorovi)

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

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

        return None


# %% Izvođenje pretrage u dubinu

polazna_maksimalna_dubina_rekurzije = sys.getrecursionlimit()
nova_maksimalna_dubina_rekurzije = 100
sys.setrecursionlimit(nova_maksimalna_dubina_rekurzije)

postavke = [
    {"početak": "", "cilj": "", "prikaz": True},
    {"početak": "A", "cilj": "A", "prikaz": True},
    {"početak": "A", "cilj": "B", "prikaz": True},
    {"početak": "AB", "cilj": "AB", "prikaz": True},
    {"početak": "ABC", "cilj": "BAC", "prikaz": True},
    {"početak": "ABC", "cilj": "BCA", "prikaz": True}]

try:
    for postavka in postavke:
        početak = postavka["početak"]
        cilj = postavka["cilj"]
        prikaz = postavka["prikaz"]
    
        print("Zadatak: početak='{}', cilj='{}'".format(početak, cilj))
    
        pretraga = PretragaDubina(početak, cilj)
        
        print("Detalji: {}".format("da" if prikaz else "ne"))
    
        rešenje = pretraga.pretraživanje(prikaz=prikaz)
    
        print("Rešenje: {}".format(rešenje if rešenje is not None else "/"))
        print("")
except RecursionError:
    print("Problem: narušeno ograničenje dubine rekurzije ({})".format(
        sys.getrecursionlimit()))

sys.setrecursionlimit(polazna_maksimalna_dubina_rekurzije)