Stabla, dodati komentari i ideje za veliki test

[spa2-materijali.git] / Stabla / Primeri za test / StabloProgram.java

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

// Tip podataka koji predstavlja binarno stablo
// ID svakog cvora je tipa int a vrednost sadrzana u njemu tipa String
// Na velikom testu, studenti ce dobiti ovu klasu
class Stablo {

    private final int id;
    private String vrednost;
    private Stablo levi;
    private Stablo desni;

    public Stablo(int id) {
        this(id, null);
    }

    public Stablo(int id, String vrednost) {
        this(id, vrednost, null, null);
    }

    public Stablo(int id, String vrednost, Stablo levi, Stablo desni) {
        this.id = id;
        this.vrednost = vrednost;
        this.levi = levi;
        this.desni = desni;
    }

    public int getId() {
        return id;
    }

    public String getVrednost() {
        return vrednost;
    }

    public void setVrednost(String vrednost) {
        this.vrednost = vrednost;
    }

    public Stablo getLevi() {
        return levi;
    }

    public void setLevi(Stablo levi) {
        this.levi = levi;
    }

    public Stablo getDesni() {
        return desni;
    }

    public void setDesni(Stablo desni) {
        this.desni = desni;
    }

    @Override
    public String toString() {
        return "(" + id + " \"" + vrednost + "\"" + (levi == null ? "" : " " + levi) + (desni == null ? "" : " " + desni) + ")";
    }

    @Override
    public int hashCode() {
        final int prostBroj = 31;
        int rezultat = 1;
        rezultat = rezultat * prostBroj + id;
        rezultat = rezultat * prostBroj + ((vrednost == null) ? 0 : vrednost.hashCode());
        rezultat = rezultat * prostBroj + ((levi == null) ? 0 : levi.hashCode());
        rezultat = rezultat * prostBroj + ((desni == null) ? 0 : desni.hashCode());
        return rezultat;
    }

    @Override
    public boolean equals(Object obj) {

        // Objekat je jednak ako je identican
        if (this == obj) {
            return true;
        }

        // Null je razlicit od svih objekata
        if (obj == null) {
            return false;
        }

        // Ako su klase objekata razlicite, onda su i objekti razliciti
        if (getClass() != obj.getClass()) {
            return false;
        }

        // Pretvorimo prosledjeni objekat u stablo
        Stablo that = (Stablo) obj;

        // Razlicit ID znaci da su objekti razliciti
        if (this.id != that.id) {
            return false;
        }

        // Takodje i vrednost
        if (Objects.equals(this.vrednost, that.vrednost)) {
            return false;
        }

        // Potom levo podstablo
        if (Objects.equals(this.levi, that.levi)) {
            return false;
        }

        // Pa desno podstablo
        if (Objects.equals(this.desni, that.desni)) {
            return false;
        }

        // Sva polja se poklapaju
        return true;

    }
}

// Glavni program
// Na velikom testu ce biti dat kostur koji ucitava potrebno stablo
// Od studenata ce se ocekivati da implementiraju neki algoritam poput
// statickih metoda koje se pozivaju u ovoj klasi
public class StabloProgram {

    public static void main(String[] args) {

        // Ucitavanje stabla iz fajla u "pretty" formatu
        // StabloIO inIO = new StabloIOPretty();
        // Stablo stablo = inIO.readStablo(Svetovid.in("pretty.txt"));

        // Generisanje random stabla
        StabloIO inIO = new StabloIORandom(12345);
        Stablo stablo = inIO.readStablo(null);

        // Ispisivanje stabla na ekran
        StabloIO outIO = new StabloIOPretty();
        outIO.printStablo(Svetovid.out, stablo);
        Svetovid.out.println();

        // Broj nivoa
        int brojNivoa = brojNivoa(stablo);
        Svetovid.out.println("Broj nivoa:", brojNivoa);
        Svetovid.out.println();

        // Broj elemenata
        int brojElementata = brojElementata(stablo);
        Svetovid.out.println("Broj elementata:", brojElementata);
        Svetovid.out.println();

        // Najduza String vrednost u stablu
        String najduzaVrednost = najduzaVrednost(stablo);
        Svetovid.out.println("Najduza vrednost:", najduzaVrednost);
        Svetovid.out.println();

        // Svi Putevi od korena do listova
        sviPutevi(stablo, new ArrayList<>(brojNivoa));
        Svetovid.out.println();

        // Obrnuto stablo
        Stablo obrnuto = obrni(stablo);
        outIO.printStablo(Svetovid.out, obrnuto);
        Svetovid.out.println();

        // Implementacije ovih algoritama su date ispod kao staticki metodi
        // Za veliki test, od studenata ce se ocekivati da na isti nacin
        // implementiraju algoritam koji se bude trazio u zadatku.
        //
        // Pored ovde implementiranih algoritama, sledi i par ideja za vezbanje:
        // - Ispisati vrednosti cvorova sa parnim IDom
        // - Ispisati sve vrednosti cvorova na nivou koji se ucitava sa tastature
        // - Utvrditi da li postoji postoji putanja od korena do lista koja sadrzi
        //   string duzine 5
        // - Napraviti novo stablo iste strukture ali sa svim vrednostima ALL CAPS
        // - Proveriti da li je dato stablo binarno stablo pretrazivanj, tj. da
        //   su sve vrednosti u levom podstablu leksikografski pre vrednosti u
        //   korenu, svi elementi u desnom leksikografski posle, i ovo takodje
        //   vazi za oba podstabla
        // - Koliko ima cvorova na nivou 7
        // - Koliko se puta string "abc" javlja u stablu

    }

    // Vraca ukupan broj elemenata u stablu
    private static int brojElementata(Stablo stablo) {
        if (stablo == null) {
            return 0; // Prazno stablo ima 0 elemenata
        }
        return 1 + brojElementata(stablo.getLevi()) + brojElementata(stablo.getDesni());
    }

    // Vraca visinu stabla
    private static int brojNivoa(Stablo stablo) {
        if (stablo == null) {
            return 0; // Prazno stablo je visine 0
        }
        return 1 + Math.max(brojNivoa(stablo.getLevi()), brojNivoa(stablo.getDesni()));
    }

    // Vraca najduzi string sadrzan kao vrednos u nekom od cvorova
    private static String najduzaVrednost(Stablo stablo) {
        if (stablo == null) {
            return null; // Prazno stablo ne sadrzi vrednosti
        }
        String rezultat = stablo.getVrednost();
        String levaVrednost = najduzaVrednost(stablo.getLevi());
        String desnaVrednost = najduzaVrednost(stablo.getDesni());
        if (rezultat == null || (levaVrednost != null && rezultat.length() < levaVrednost.length())) {
            rezultat = levaVrednost;
        }
        if (rezultat == null || (desnaVrednost != null && rezultat.length() < desnaVrednost.length())) {
            rezultat = desnaVrednost;
        }
        return rezultat;
    }

    // Ispisuje sve puteve od korena do listova
    private static void sviPutevi(Stablo stablo, List<String> put) {
        if (stablo == null) {
            return;
        }
        put.add(stablo.getVrednost());
        if ((stablo.getLevi() == null) && (stablo.getDesni() == null)) {
            Svetovid.out.println("Put: " + put);
        }
        sviPutevi(stablo.getLevi(), put);
        sviPutevi(stablo.getDesni(), put);
        put.remove(put.size() - 1);
    }

    // Vraca obrnuto stablo od datog
    private static Stablo obrni(Stablo stablo) {
        if (stablo == null) {
            return null;
        }
        Stablo levi = obrni(stablo.getLevi());
        Stablo desni = obrni(stablo.getDesni());
        Stablo obrnuto = new Stablo(stablo.getId(), stablo.getVrednost(), desni, levi);
        return obrnuto;
    }
}