gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/Stabla/StabloOpstegTipa/StabloIOPretty.java b/Stabla/StabloOpstegTipa/StabloIOPretty.java
--- /dev/null
@@ -0,0 +1,223 @@
+import java.util.ArrayList;\r
+import java.util.List;\r
+import java.util.regex.Matcher;\r
+import java.util.regex.Pattern;\r
+\r
+import org.svetovid.io.SvetovidReader;\r
+import org.svetovid.io.SvetovidWriter;\r
+\r
+@interface DatoNaVezbama {}\r
+\r
+// Ako bude potrebna, ova klasa ce biti data na testu\r
+@DatoNaVezbama\r
+public class StabloIOPretty<T> {\r
+\r
+ protected static final String EMPTY_SYMBOL = " ";\r
+ protected static final String RIGHT_SYMBOL = "/";\r
+ protected static final String VERTICAL_SYMBOL = "|";\r
+ protected static final String LEFT_SYMBOL = "\\";\r
+ protected static final String HORIZONTAL_SYMBOL = "-";\r
+\r
+ protected Konverter<T> konverter;\r
+ protected String nullSymbol;\r
+ protected int separation;\r
+ protected int length;\r
+\r
+ public StabloIOPretty(Konverter<T> konverter) {\r
+ this(konverter, null, 1, 7);\r
+ }\r
+\r
+ public StabloIOPretty(Konverter<T> konverter, String nullSymbol, int separation, int length) {\r
+ this.konverter = konverter;\r
+ this.nullSymbol = nullSymbol;\r
+ this.separation = separation;\r
+ this.length = length;\r
+ }\r
+\r
+ public Konverter<T> getKonverter() {\r
+ return konverter;\r
+ }\r
+\r
+ public void setKonverter(Konverter<T> konverter) {\r
+ this.konverter = konverter;\r
+ }\r
+\r
+ public String getNullSymbol() {\r
+ return nullSymbol;\r
+ }\r
+\r
+ public void setNullSymbol(String nullSymbol) {\r
+ this.nullSymbol = nullSymbol;\r
+ }\r
+\r
+ public int getSeparation() {\r
+ return separation;\r
+ }\r
+\r
+ public void setSeparation(int separation) {\r
+ this.separation = separation;\r
+ }\r
+\r
+ public int getLength() {\r
+ return length;\r
+ }\r
+\r
+ public void setLength(int length) {\r
+ if (length < 3) {\r
+ throw new IllegalArgumentException("length");\r
+ }\r
+ this.length = length;\r
+ }\r
+\r
+ public BinarnoStablo<T> readStablo(SvetovidReader in) {\r
+ return parseStablo(in, konverter, nullSymbol, length);\r
+ }\r
+\r
+ protected BinarnoStablo<T> parseStablo(SvetovidReader in, Konverter<T> konverter, String nullSymbol, int length) {\r
+ List<BinarnoStablo<T>> elements = new ArrayList<>();\r
+ List<Integer> levels = new ArrayList<>();\r
+ Pattern levelPattern = Pattern.compile("[\\Q" + LEFT_SYMBOL + HORIZONTAL_SYMBOL + RIGHT_SYMBOL + "\\E]");\r
+ String line = in.readLine();\r
+ while ((line != null) && !line.isEmpty()) {\r
+ Matcher matcher = levelPattern.matcher(line);\r
+ int level = -1;\r
+ if (matcher.find()) {\r
+ level = matcher.start();\r
+ }\r
+ if (level != -1 && (nullSymbol == null || !line.endsWith(nullSymbol))) {\r
+ BinarnoStablo<T> stablo = parseStablo(konverter, line);\r
+ elements.add(stablo);\r
+ levels.add(level);\r
+ }\r
+ line = in.readLine();\r
+ }\r
+ BinarnoStablo<T> stablo = formStablo(0, elements.size(), levels, elements);\r
+ return stablo;\r
+ }\r
+\r
+ private BinarnoStablo<T> parseStablo(Konverter<T> konverter, String line) {\r
+ String vrednost;\r
+ int beginIndex = line.indexOf('(');\r
+ int endIndex = line.indexOf(')');\r
+ if ((beginIndex != -1) && (endIndex != -1) && (beginIndex < endIndex)) {\r
+ vrednost = line.substring(endIndex + 2);\r
+ } else {\r
+ throw new NumberFormatException(line);\r
+ }\r
+ T element = konverter.fromString(vrednost);\r
+ BinarnoStablo<T> stablo = new BinarnoStablo<>(element);\r
+ return stablo;\r
+ }\r
+\r
+ private BinarnoStablo<T> formStablo(int beginIndex, int endIndex, List<Integer> levels, List<BinarnoStablo<T>> elements) {\r
+ if (beginIndex >= endIndex) {\r
+ return null;\r
+ }\r
+ int minIndex = beginIndex;\r
+ int minLevel = levels.get(minIndex);\r
+ for (int i = beginIndex + 1; i < endIndex; i++) {\r
+ int level = levels.get(i);\r
+ if (level < minLevel) {\r
+ minLevel = level;\r
+ minIndex = i;\r
+ }\r
+ }\r
+ BinarnoStablo<T> stablo = elements.get(minIndex);\r
+ BinarnoStablo<T> levo = formStablo(minIndex + 1, endIndex, levels, elements);\r
+ BinarnoStablo<T> desno = formStablo(beginIndex, minIndex, levels, elements);\r
+ stablo.setLevoPodstablo(levo);\r
+ stablo.setDesnoPodstablo(desno);\r
+ return stablo;\r
+ }\r
+\r
+ public void printStablo(SvetovidWriter out, BinarnoStablo<T> stablo) {\r
+ StringBuilder builder = new StringBuilder();\r
+ appendTree(builder, stablo, konverter, nullSymbol, separation, length);\r
+ out.print(builder.toString());\r
+ }\r
+\r
+ protected void appendTree(StringBuilder builder, BinarnoStablo<T> stablo, Konverter<T> konverter, String nullSymbol, int separation, int length) {\r
+ String[] buildingBlocks = generateBuildingBlocks(length);\r
+ appendRight(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, true, buildingBlocks[5]);\r
+ appendNode(builder, stablo, konverter, nullSymbol != null ? nullSymbol : "|", buildingBlocks[4]);\r
+ appendLeft(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, false, buildingBlocks[5]);\r
+ }\r
+\r
+ protected void appendNode(StringBuilder builder, BinarnoStablo<T> stablo, Konverter<T> konverter, String nullSymbol, String prefix) {\r
+ builder.append(prefix);\r
+ if (stablo == null) {\r
+ builder.append(nullSymbol);\r
+ } else {\r
+ builder.append("(o) ");\r
+ String vrednost = konverter.toString(stablo.getElement());\r
+ builder.append(vrednost);\r
+ }\r
+ builder.append("\n");\r
+ }\r
+\r
+ protected void appendRight(StringBuilder builder, BinarnoStablo<T> stablo, Konverter<T> konverter, String nullSymbol, int separation, String[] buildingBlocks, boolean isRight, String prefix) {\r
+ if (stablo == null) {\r
+ return;\r
+ }\r
+ if ((nullSymbol != null) || (stablo.getDesnoPodstablo() != null)) {\r
+ appendSubtree(builder, stablo.getDesnoPodstablo(), konverter, nullSymbol, separation, buildingBlocks, true, prefix);\r
+ for (int i = 0; i < separation; i++) {\r
+ appendEmpty(builder, buildingBlocks, prefix);\r
+ }\r
+ }\r
+ }\r
+\r
+ protected void appendLeft(StringBuilder builder, BinarnoStablo<T> stablo, Konverter<T> konverter, String nullSymbol, int separation, String[] buildingBlocks, boolean isRight, String prefix) {\r
+ if (stablo == null) {\r
+ return;\r
+ }\r
+ if ((nullSymbol != null) || (stablo.getLevoPodstablo() != null)) {\r
+ for (int i = 0; i < separation; i++) {\r
+ appendEmpty(builder, buildingBlocks, prefix);\r
+ }\r
+ appendSubtree(builder, stablo.getLevoPodstablo(), konverter, nullSymbol, separation, buildingBlocks, false, prefix);\r
+ }\r
+ }\r
+\r
+ protected void appendEmpty(StringBuilder builder, String[] buildingBlocks, String prefix) {\r
+ builder.append(prefix);\r
+ builder.append(buildingBlocks[2]);\r
+ builder.append("\n");\r
+ }\r
+\r
+ protected void appendSubtree(StringBuilder builder, BinarnoStablo<T> stablo, Konverter<T> konverter, String nullSymbol, int separation, String[] buildingBlocks, boolean isRight, String prefix) {\r
+ String mojPrefix = prefix;\r
+ if (isRight == true) {\r
+ mojPrefix = mojPrefix + buildingBlocks[1];\r
+ }\r
+ if (isRight == false) {\r
+ mojPrefix = mojPrefix + buildingBlocks[3];\r
+ }\r
+ String noviPrefix = prefix + (!isRight ? buildingBlocks[2] : buildingBlocks[0]);\r
+ appendRight(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, isRight, noviPrefix);\r
+ appendNode(builder, stablo, konverter, nullSymbol, mojPrefix);\r
+ noviPrefix = prefix + (isRight ? buildingBlocks[2] : buildingBlocks[0]);\r
+ appendLeft(builder, stablo, konverter, nullSymbol, separation, buildingBlocks, isRight, noviPrefix);\r
+ }\r
+\r
+ private String[] generateBuildingBlocks(int length) {\r
+ String[] blocks = new String[6];\r
+ blocks[0] = generateBlock(EMPTY_SYMBOL, EMPTY_SYMBOL, EMPTY_SYMBOL, length - 2);\r
+ blocks[1] = generateBlock(EMPTY_SYMBOL, RIGHT_SYMBOL, HORIZONTAL_SYMBOL, length - 2);\r
+ blocks[2] = generateBlock(EMPTY_SYMBOL, VERTICAL_SYMBOL, EMPTY_SYMBOL, length - 2);\r
+ blocks[3] = generateBlock(EMPTY_SYMBOL, LEFT_SYMBOL, HORIZONTAL_SYMBOL, length - 2);\r
+ blocks[4] = HORIZONTAL_SYMBOL;\r
+ blocks[5] = EMPTY_SYMBOL;\r
+ return blocks;\r
+ }\r
+\r
+ protected String generateBlock(String emptySymbol, String startSymbol, String repeatSymbol, int repeatCount) {\r
+ StringBuilder builder = new StringBuilder();\r
+ builder.append(emptySymbol);\r
+ builder.append(startSymbol);\r
+ for (int i = 0; i < repeatCount; i++) {\r
+ builder.append(repeatSymbol);\r
+ }\r
+ return builder.toString();\r
+ }\r
+}\r