import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;

class Filsystem {
    Mappe hovedmappe;

    public Filsystem(String mappenavn) {
        hovedmappe = new Mappe(mappenavn);
    }

    public Mappe hentHovedmappe() {
        return hovedmappe;
    }

    // Vi l?ser oppgaven med et dybde-f?rst-s?k, slik dere har gjort ved innlevering 3
    public String finnFilstiR(String filnavn, Mappe mappe) {
        for (Fil fil : mappe.hentFiler()) {
            if (fil.hentNavn().equals(filnavn)) {
                return "/" + mappe.hentNavn() + "/" + fil.hentNavn();
            }
        }

        for (Mappe underMappe : mappe.hentMapper()) {
            String filsti = finnFilstiR(filnavn, underMappe);
            if (filsti != null) {
                return "/" + mappe.hentNavn() + filsti;
            }
        }

        return null;
    }

    // Vi kan l?se oppgaven iterativt ved ? bruke et bredde-f?rst-s?k (dette er ikke pensum i IN1010, men for spesielt interesserte)
    public String finnFilstiI(String filnavn, Mappe mappe) {
        String filbane = "/";
        ArrayList<Mappe> sti = new ArrayList<>();
        sti.add(mappe);
        ArrayDeque<ArrayList<Mappe>> stier = new ArrayDeque<>();
        stier.offer(sti);
        while (!stier.isEmpty()) {
            sti = stier.poll();
            mappe = sti.get(sti.size()-1);
    
    
            for (Fil fil : mappe.hentFiler()) {
                if (fil.hentNavn().equals(filnavn)) {
                    for (Mappe m : sti) {
                        filbane += m.hentNavn() + "/";
                    }
                    return filbane + fil.hentNavn();
                }
            }
    
            for (Mappe underMappe : mappe.hentMapper()) {
                ArrayList<Mappe> nySti = new ArrayList<>(sti);
                nySti.add(underMappe);
                stier.offer(nySti); 
            }
    
        }
        return null;
    }

}

class Mappe {
    String navn;
    HashSet<Mappe> mapper = new HashSet<>();
    HashSet<Fil> filer = new HashSet<>();

    public Mappe(String navn) {
        this.navn = navn;
    }

    public void leggTil(Mappe mappe) {
        mapper.add(mappe);
    }

    //Overloader
    public void leggTil(Fil fil) {
        filer.add(fil);
    }

    public HashSet<Mappe> hentMapper() {
        return mapper;
    }

    public HashSet<Fil> hentFiler() {
        return filer;
    }

    public String hentNavn() {
        return navn;
    }
}

class Fil {
    String navn;

    public Fil(String navn) {
        this.navn = navn;
    }

    public String hentNavn() {
        return navn;
    }
}