From 8ce9bb7b0e2a94776b901111b90f2070734267d7 Mon Sep 17 00:00:00 2001 From: Ivan Pribela Date: Sat, 7 Nov 2015 18:44:57 +0100 Subject: [PATCH] Stabla, dodati komentari i ideje za veliki test --- Stabla/Primeri za test/StabloIO.java | 5 + Stabla/Primeri za test/StabloIOClassic.java | 39 +++-- Stabla/Primeri za test/StabloIOIndent.java | 21 ++- Stabla/Primeri za test/StabloIOPretty.java | 26 ++-- Stabla/Primeri za test/StabloIORandom.java | 10 +- Stabla/Primeri za test/StabloProgram.java | 163 +++++++++++++++++--- 6 files changed, 204 insertions(+), 60 deletions(-) diff --git a/Stabla/Primeri za test/StabloIO.java b/Stabla/Primeri za test/StabloIO.java index 59984d3..f0cab85 100644 --- a/Stabla/Primeri za test/StabloIO.java +++ b/Stabla/Primeri za test/StabloIO.java @@ -1,6 +1,11 @@ import org.svetovid.io.SvetovidReader; import org.svetovid.io.SvetovidWriter; +/* + * Ovaj interfejs i klase koje ga implementiraju sluze za ucitavanje i + * snimanje stabala. Nije potrebno znati ih, i bice dati, prilikom izrade + * prakticnih zadataka. + */ public interface StabloIO { public Stablo readStablo(SvetovidReader in); diff --git a/Stabla/Primeri za test/StabloIOClassic.java b/Stabla/Primeri za test/StabloIOClassic.java index dcf1d9f..d6b0445 100644 --- a/Stabla/Primeri za test/StabloIOClassic.java +++ b/Stabla/Primeri za test/StabloIOClassic.java @@ -3,11 +3,16 @@ import java.util.NoSuchElementException; import org.svetovid.io.SvetovidReader; import org.svetovid.io.SvetovidWriter; -/** - * Format: +/* + * Ova klasa sluzi za ucitavanje i snimanje stabala. Nije potrebno znati je, + * i bice data, prilikom izrade prakticnih zadataka. + * + * Ocekivani format fajla je sledeci: * * br * id leviId desniId vrednost (x br) + * + * Primer fajla je classic.txt */ public class StabloIOClassic implements StabloIO { @@ -32,13 +37,13 @@ public class StabloIOClassic implements StabloIO { if (stablo == null) { return element; } - Stablo found = find(stablo, element.id); + Stablo found = find(stablo, element.getId()); if (found == null) { - throw new NoSuchElementException("id: " + element.id); + throw new NoSuchElementException("id: " + element.getId()); } - found.vrednost = element.vrednost; - found.levi = element.levi; - found.desni = element.desni; + found.setVrednost(element.getVrednost()); + found.setLevi(element.getLevi()); + found.setDesni(element.getDesni()); return stablo; } @@ -46,14 +51,14 @@ public class StabloIOClassic implements StabloIO { if (stablo == null) { return null; } - if (stablo.id == id) { + if (stablo.getId() == id) { return stablo; } - Stablo rezultat = find(stablo.levi, id); + Stablo rezultat = find(stablo.getLevi(), id); if (rezultat != null) { return rezultat; } - return find(stablo.desni, id); + return find(stablo.getDesni(), id); } @Override @@ -67,19 +72,19 @@ public class StabloIOClassic implements StabloIO { if (stablo == null) { return 0; } - return 1 + count(stablo.levi) + count(stablo.desni); + return 1 + count(stablo.getLevi()) + count(stablo.getDesni()); } private static void iterate(SvetovidWriter out, Stablo stablo) { if (stablo == null) { return; } - int id = stablo.id; - int leviId = stablo.levi == null ? -1 : stablo.levi.id; - int desniId = stablo.desni == null ? -1 : stablo.desni.id; - String vrednost = stablo.vrednost; + int id = stablo.getId(); + int leviId = stablo.getLevi() == null ? -1 : stablo.getLevi().getId(); + int desniId = stablo.getDesni() == null ? -1 : stablo.getDesni().getId(); + String vrednost = stablo.getVrednost(); out.println(id, leviId, desniId, vrednost); - iterate(out, stablo.levi); - iterate(out, stablo.desni); + iterate(out, stablo.getLevi()); + iterate(out, stablo.getDesni()); } } diff --git a/Stabla/Primeri za test/StabloIOIndent.java b/Stabla/Primeri za test/StabloIOIndent.java index 8e9dc83..dede26b 100644 --- a/Stabla/Primeri za test/StabloIOIndent.java +++ b/Stabla/Primeri za test/StabloIOIndent.java @@ -2,12 +2,17 @@ import org.svetovid.SvetovidFormatException; import org.svetovid.io.SvetovidReader; import org.svetovid.io.SvetovidWriter; -/** - * Format: +/* + * Ova klasa sluzi za ucitavanje i snimanje stabala. Nije potrebno znati je, + * i bice data, prilikom izrade prakticnih zadataka. + * + * Ocekivani format fajla je sledeci: * * id vrednost - * levi - * desni + * levi + * desni + * + * Primer fajla je indent.txt */ public class StabloIOIndent implements StabloIO { @@ -63,11 +68,11 @@ public class StabloIOIndent implements StabloIO { out.println(prefix + nullSymbol); return; } - int id = stablo.id; - String vrednost = stablo.vrednost; + int id = stablo.getId(); + String vrednost = stablo.getVrednost(); out.print(prefix); out.println(id, vrednost); - write(out, stablo.levi, nullSymbol, indent, prefix + indent); - write(out, stablo.desni, nullSymbol, indent, prefix + indent); + write(out, stablo.getLevi(), nullSymbol, indent, prefix + indent); + write(out, stablo.getDesni(), nullSymbol, indent, prefix + indent); } } diff --git a/Stabla/Primeri za test/StabloIOPretty.java b/Stabla/Primeri za test/StabloIOPretty.java index 6fcc069..2df3c03 100644 --- a/Stabla/Primeri za test/StabloIOPretty.java +++ b/Stabla/Primeri za test/StabloIOPretty.java @@ -6,11 +6,17 @@ import java.util.regex.Pattern; import org.svetovid.io.SvetovidReader; import org.svetovid.io.SvetovidWriter; -/** - * Format: +/* + * Ova klasa sluzi za ucitavanje i snimanje stabala. Nije potrebno znati je, + * i bice data, prilikom izrade prakticnih zadataka. + * + * Ocekivani format fajla je sledeci: + * * /-- desni * -(id) vrednost * \-- levi + * + * Primer fajla je pretty.txt */ public class StabloIOPretty implements StabloIO { @@ -124,8 +130,8 @@ public class StabloIOPretty implements StabloIO { Stablo stablo = elements.get(minIndex); Stablo levi = formStablo(minIndex + 1, endIndex, levels, elements); Stablo desni = formStablo(beginIndex, minIndex, levels, elements); - stablo.levi = levi; - stablo.desni = desni; + stablo.setLevi(levi); + stablo.setDesni(desni); return stablo; } @@ -149,9 +155,9 @@ public class StabloIOPretty implements StabloIO { builder.append(nullSymbol); } else { builder.append("("); - builder.append(stablo.id); + builder.append(stablo.getId()); builder.append(") "); - builder.append(stablo.vrednost); + builder.append(stablo.getVrednost()); } builder.append("\n"); } @@ -160,8 +166,8 @@ public class StabloIOPretty implements StabloIO { if (stablo == null) { return; } - if ((nullSymbol != null) || (stablo.desni != null)) { - appendSubtree(builder, stablo.desni, nullSymbol, separated, buildingBlocks, true, prefix); + if ((nullSymbol != null) || (stablo.getDesni() != null)) { + appendSubtree(builder, stablo.getDesni(), nullSymbol, separated, buildingBlocks, true, prefix); if (separated) { appendEmpty(builder, buildingBlocks, prefix); } @@ -172,11 +178,11 @@ public class StabloIOPretty implements StabloIO { if (stablo == null) { return; } - if ((nullSymbol != null) || (stablo.levi != null)) { + if ((nullSymbol != null) || (stablo.getLevi() != null)) { if (separated) { appendEmpty(builder, buildingBlocks, prefix); } - appendSubtree(builder, stablo.levi, nullSymbol, separated, buildingBlocks, false, prefix); + appendSubtree(builder, stablo.getLevi(), nullSymbol, separated, buildingBlocks, false, prefix); } } diff --git a/Stabla/Primeri za test/StabloIORandom.java b/Stabla/Primeri za test/StabloIORandom.java index d3a98ca..f5880c4 100644 --- a/Stabla/Primeri za test/StabloIORandom.java +++ b/Stabla/Primeri za test/StabloIORandom.java @@ -5,6 +5,10 @@ import java.util.concurrent.atomic.AtomicInteger; import org.svetovid.io.SvetovidReader; import org.svetovid.io.SvetovidWriter; +/* + * Ova klasa sluzi za generisanje random stabala. Nije potrebno znati je, + * i bice data, prilikom izrade prakticnih zadataka. + */ public class StabloIORandom implements StabloIO { protected long seed; @@ -58,9 +62,9 @@ public class StabloIORandom implements StabloIO { } private Stablo readStablo(Random random, AtomicInteger sequence, int length, int depth) { - if (depth <= 0) { - return null; - } + if (depth <= 0) { + return null; + } int id = sequence.addAndGet(1 + random.nextInt(9)); String vrednost = new BigInteger(length, random).toString(36); Stablo desni = readStablo(random, sequence, length + random.nextInt(5), depth - random.nextInt(5)); diff --git a/Stabla/Primeri za test/StabloProgram.java b/Stabla/Primeri za test/StabloProgram.java index 148ce7b..ee70ace 100644 --- a/Stabla/Primeri za test/StabloProgram.java +++ b/Stabla/Primeri za test/StabloProgram.java @@ -1,12 +1,16 @@ 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 { - public final int id; - public String vrednost; - public Stablo levi; - public Stablo desni; + private final int id; + private String vrednost; + private Stablo levi; + private Stablo desni; public Stablo(int id) { this(id, null); @@ -23,17 +27,110 @@ class Stablo { 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 + // 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); @@ -47,12 +144,12 @@ public class StabloProgram { Svetovid.out.println("Broj nivoa:", brojNivoa); Svetovid.out.println(); - // Broj nivoa + // Broj elemenata int brojElementata = brojElementata(stablo); Svetovid.out.println("Broj elementata:", brojElementata); Svetovid.out.println(); - // Broj nivoa + // Najduza String vrednost u stablu String najduzaVrednost = najduzaVrednost(stablo); Svetovid.out.println("Najduza vrednost:", najduzaVrednost); Svetovid.out.println(); @@ -66,29 +163,49 @@ public class StabloProgram { 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; + return 0; // Prazno stablo ima 0 elemenata } - return 1 + brojElementata(stablo.levi) + brojElementata(stablo.desni); + return 1 + brojElementata(stablo.getLevi()) + brojElementata(stablo.getDesni()); } + // Vraca visinu stabla private static int brojNivoa(Stablo stablo) { if (stablo == null) { - return 0; + return 0; // Prazno stablo je visine 0 } - return 1 + Math.max(brojNivoa(stablo.levi), brojNivoa(stablo.desni)); + 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; + return null; // Prazno stablo ne sadrzi vrednosti } - String rezultat = stablo.vrednost; - String levaVrednost = najduzaVrednost(stablo.levi); - String desnaVrednost = najduzaVrednost(stablo.desni); + 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; } @@ -98,26 +215,28 @@ public class StabloProgram { return rezultat; } + // Ispisuje sve puteve od korena do listova private static void sviPutevi(Stablo stablo, List put) { if (stablo == null) { return; } - put.add(stablo.vrednost); - if ((stablo.levi == null) && (stablo.desni == null)) { + put.add(stablo.getVrednost()); + if ((stablo.getLevi() == null) && (stablo.getDesni() == null)) { Svetovid.out.println("Put: " + put); } - sviPutevi(stablo.levi, put); - sviPutevi(stablo.desni, 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.levi); - Stablo desni = obrni(stablo.desni); - Stablo obrnuto = new Stablo(stablo.id, stablo.vrednost, desni, levi); + Stablo levi = obrni(stablo.getLevi()); + Stablo desni = obrni(stablo.getDesni()); + Stablo obrnuto = new Stablo(stablo.getId(), stablo.getVrednost(), desni, levi); return obrnuto; } } -- 2.25.1