gitweb on Svarog

projekti pod git sistemom za održavanje verzija -- projects under the git version control system
Sortiranje, Domaci, dodat prvi zadatak za mozganje
[spa2-materijali.git] / Stabla / Primeri za test / StabloIOPretty.java
1 import java.util.ArrayList;
2 import java.util.List;
3 import java.util.regex.Matcher;
4 import java.util.regex.Pattern;
6 import org.svetovid.io.SvetovidReader;
7 import org.svetovid.io.SvetovidWriter;
9 /**
10 * Format:
11 * /-- desni
12 * -(id) vrednost
13 * \-- levi
14 */
15 public class StabloIOPretty implements StabloIO {
17 protected static final String EMPTY_SYMBOL = " ";
18 protected static final String RIGHT_SYMBOL = "/";
19 protected static final String VERTICAL_SYMBOL = "|";
20 protected static final String LEFT_SYMBOL = "\\";
21 protected static final String HORIZONTAL_SYMBOL = "-";
23 protected String nullSymbol;
24 protected boolean separated;
25 protected int length;
27 public StabloIOPretty() {
28 this(null, false, 7);
29 }
31 public StabloIOPretty(String nullSymbol, boolean separated, int length) {
32 this.nullSymbol = nullSymbol;
33 this.separated = separated;
34 this.length = length;
35 }
37 public String getNullSymbol() {
38 return nullSymbol;
39 }
41 public void setNullSymbol(String nullSymbol) {
42 this.nullSymbol = nullSymbol;
43 }
45 public boolean isSeparated() {
46 return separated;
47 }
49 public void setSeparated(boolean separated) {
50 this.separated = separated;
51 }
53 public int getLength() {
54 return length;
55 }
57 public void setLength(int length) {
58 if (length < 3) {
59 throw new IllegalArgumentException("length");
60 }
61 this.length = length;
62 }
64 @Override
65 public Stablo readStablo(SvetovidReader in) {
66 return parseStablo(in, nullSymbol, length);
67 }
69 protected Stablo parseStablo(SvetovidReader in, String nullSymbol, int length) {
70 List<Stablo> elements = new ArrayList<>();
71 List<Integer> levels = new ArrayList<>();
72 Pattern levelPattern = Pattern.compile("[\\Q" + LEFT_SYMBOL + HORIZONTAL_SYMBOL + RIGHT_SYMBOL + "\\E]");
73 String line = in.readLine();
74 while ((line != null) && !line.isEmpty()) {
75 Matcher matcher = levelPattern.matcher(line);
76 int level = -1;
77 if (matcher.find()) {
78 level = matcher.start();
79 }
80 if (level != -1 && (nullSymbol == null || !line.endsWith(nullSymbol))) {
81 Stablo stablo = parseStablo(line);
82 elements.add(stablo);
83 levels.add(level);
84 }
85 line = in.readLine();
86 }
87 Stablo stablo = formStablo(0, elements.size(), levels, elements);
88 return stablo;
89 }
91 private Stablo parseStablo(String line) {
92 int id = -1;
93 String vrednost = null;
94 int beginIndex = line.indexOf('(');
95 int endIndex = line.indexOf(')');
96 if ((beginIndex != -1) && (endIndex != -1) && (beginIndex < endIndex)) {
97 vrednost = line.substring(beginIndex + 1, endIndex);
98 try {
99 id = Integer.parseInt(vrednost);
100 } catch (NumberFormatException e) {
101 throw new NumberFormatException(line);
103 vrednost = line.substring(endIndex + 2);
104 } else {
105 throw new NumberFormatException(line);
107 Stablo stablo = new Stablo(id, vrednost);
108 return stablo;
111 private Stablo formStablo(int beginIndex, int endIndex, List<Integer> levels, List<Stablo> elements) {
112 if (beginIndex >= endIndex) {
113 return null;
115 int minIndex = beginIndex;
116 int minLevel = levels.get(minIndex);
117 for (int i = beginIndex + 1; i < endIndex; i++) {
118 int level = levels.get(i);
119 if (level < minLevel) {
120 minLevel = level;
121 minIndex = i;
124 Stablo stablo = elements.get(minIndex);
125 Stablo levi = formStablo(minIndex + 1, endIndex, levels, elements);
126 Stablo desni = formStablo(beginIndex, minIndex, levels, elements);
127 stablo.levi = levi;
128 stablo.desni = desni;
129 return stablo;
132 @Override
133 public void printStablo(SvetovidWriter out, Stablo stablo) {
134 StringBuilder builder = new StringBuilder();
135 appendTree(builder, stablo, nullSymbol, separated, length);
136 out.print(builder.toString());
139 protected void appendTree(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, int length) {
140 String[] buildingBlocks = generateBuildingBlocks(length);
141 appendRight(builder, stablo, nullSymbol, separated, buildingBlocks, true, buildingBlocks[5]);
142 appendNode(builder, stablo, nullSymbol != null ? nullSymbol : "|", buildingBlocks[4]);
143 appendLeft(builder, stablo, nullSymbol, separated, buildingBlocks, false, buildingBlocks[5]);
146 protected void appendNode(StringBuilder builder, Stablo stablo, String nullSymbol, String prefix) {
147 builder.append(prefix);
148 if (stablo == null) {
149 builder.append(nullSymbol);
150 } else {
151 builder.append("(");
152 builder.append(stablo.id);
153 builder.append(") ");
154 builder.append(stablo.vrednost);
156 builder.append("\n");
159 protected void appendRight(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, String[] buildingBlocks, boolean isRight, String prefix) {
160 if (stablo == null) {
161 return;
163 if ((nullSymbol != null) || (stablo.desni != null)) {
164 appendSubtree(builder, stablo.desni, nullSymbol, separated, buildingBlocks, true, prefix);
165 if (separated) {
166 appendEmpty(builder, buildingBlocks, prefix);
171 protected void appendLeft(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, String[] buildingBlocks, boolean isRight, String prefix) {
172 if (stablo == null) {
173 return;
175 if ((nullSymbol != null) || (stablo.levi != null)) {
176 if (separated) {
177 appendEmpty(builder, buildingBlocks, prefix);
179 appendSubtree(builder, stablo.levi, nullSymbol, separated, buildingBlocks, false, prefix);
183 protected void appendEmpty(StringBuilder builder, String[] buildingBlocks, String prefix) {
184 builder.append(prefix);
185 builder.append(buildingBlocks[2]);
186 builder.append("\n");
189 protected void appendSubtree(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, String[] buildingBlocks, boolean isRight, String prefix) {
190 String mojPrefix = prefix;
191 if (isRight == true) {
192 mojPrefix = mojPrefix + buildingBlocks[1];
194 if (isRight == false) {
195 mojPrefix = mojPrefix + buildingBlocks[3];
197 String noviPrefix = prefix + (!isRight ? buildingBlocks[2] : buildingBlocks[0]);
198 appendRight(builder, stablo, nullSymbol, separated, buildingBlocks, isRight, noviPrefix);
199 appendNode(builder, stablo, nullSymbol, mojPrefix);
200 noviPrefix = prefix + (isRight ? buildingBlocks[2] : buildingBlocks[0]);
201 appendLeft(builder, stablo, nullSymbol, separated, buildingBlocks, isRight, noviPrefix);
204 private String[] generateBuildingBlocks(int length) {
205 String[] blocks = new String[6];
206 blocks[0] = generateBlock(EMPTY_SYMBOL, EMPTY_SYMBOL, EMPTY_SYMBOL, length - 2);
207 blocks[1] = generateBlock(EMPTY_SYMBOL, RIGHT_SYMBOL, HORIZONTAL_SYMBOL, length - 2);
208 blocks[2] = generateBlock(EMPTY_SYMBOL, VERTICAL_SYMBOL, EMPTY_SYMBOL, length - 2);
209 blocks[3] = generateBlock(EMPTY_SYMBOL, LEFT_SYMBOL, HORIZONTAL_SYMBOL, length - 2);
210 blocks[4] = HORIZONTAL_SYMBOL;
211 blocks[5] = EMPTY_SYMBOL;
212 return blocks;
215 protected String generateBlock(String emptySymbol, String startSymbol, String repeatSymbol, int repeatCount) {
216 StringBuilder builder = new StringBuilder();
217 builder.append(emptySymbol);
218 builder.append(startSymbol);
219 for (int i = 0; i < repeatCount; i++) {
220 builder.append(repeatSymbol);
222 return builder.toString();
Svarog.pmf.uns.ac.rs/gitweb maintanance Doni Pracner