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;
   5
   6 import org.svetovid.io.SvetovidReader;
   7 import org.svetovid.io.SvetovidWriter;
   8
   9 /*
  10  * Ova klasa sluzi za ucitavanje i snimanje stabala. Nije potrebno znati je,
  11  * i bice data, prilikom izrade prakticnih zadataka.
  12  *
  13  * Ocekivani format fajla je sledeci:
  14  *
  15  *   /-- desni
  16  * -(id) vrednost
  17  *   \-- levi
  18  *
  19  * Primer fajla je pretty.txt
  20  */
  21 public class StabloIOPretty implements StabloIO {
  22
  23     protected static final String EMPTY_SYMBOL = " ";
  24     protected static final String RIGHT_SYMBOL = "/";
  25     protected static final String VERTICAL_SYMBOL = "|";
  26     protected static final String LEFT_SYMBOL = "\\";
  27     protected static final String HORIZONTAL_SYMBOL = "-";
  28
  29     protected String nullSymbol;
  30     protected boolean separated;
  31     protected int length;
  32
  33     public StabloIOPretty() {
  34         this(null, false, 7);
  35     }
  36
  37     public StabloIOPretty(String nullSymbol, boolean separated, int length) {
  38         this.nullSymbol = nullSymbol;
  39         this.separated = separated;
  40         this.length = length;
  41     }
  42
  43     public String getNullSymbol() {
  44         return nullSymbol;
  45     }
  46
  47     public void setNullSymbol(String nullSymbol) {
  48         this.nullSymbol = nullSymbol;
  49     }
  50
  51     public boolean isSeparated() {
  52         return separated;
  53     }
  54
  55     public void setSeparated(boolean separated) {
  56         this.separated = separated;
  57     }
  58
  59     public int getLength() {
  60         return length;
  61     }
  62
  63     public void setLength(int length) {
  64         if (length < 3) {
  65             throw new IllegalArgumentException("length");
  66         }
  67         this.length = length;
  68     }
  69
  70     @Override
  71     public Stablo readStablo(SvetovidReader in) {
  72         return parseStablo(in, nullSymbol, length);
  73     }
  74
  75     protected Stablo parseStablo(SvetovidReader in, String nullSymbol, int length) {
  76         List<Stablo> elements = new ArrayList<>();
  77         List<Integer> levels = new ArrayList<>();
  78         Pattern levelPattern = Pattern.compile("[\\Q" + LEFT_SYMBOL + HORIZONTAL_SYMBOL + RIGHT_SYMBOL + "\\E]");
  79         String line = in.readLine();
  80         while ((line != null) && !line.isEmpty()) {
  81             Matcher matcher = levelPattern.matcher(line);
  82             int level = -1;
  83             if (matcher.find()) {
  84                 level = matcher.start();
  85             }
  86             if (level != -1 && (nullSymbol == null || !line.endsWith(nullSymbol))) {
  87                 Stablo stablo = parseStablo(line);
  88                 elements.add(stablo);
  89                 levels.add(level);
  90             }
  91             line = in.readLine();
  92         }
  93         Stablo stablo = formStablo(0, elements.size(), levels, elements);
  94         return stablo;
  95     }
  96
  97     private Stablo parseStablo(String line) {
  98         int id = -1;
  99         String vrednost = null;
 100         int beginIndex = line.indexOf('(');
 101         int endIndex = line.indexOf(')');
 102         if ((beginIndex != -1) && (endIndex != -1) && (beginIndex < endIndex)) {
 103             vrednost = line.substring(beginIndex + 1, endIndex);
 104             try {
 105                 id = Integer.parseInt(vrednost);
 106             } catch (NumberFormatException e) {
 107                 throw new NumberFormatException(line);
 108             }
 109             vrednost = line.substring(endIndex + 2);
 110         } else {
 111             throw new NumberFormatException(line);
 112         }
 113         Stablo stablo = new Stablo(id, vrednost);
 114         return stablo;
 115     }
 116
 117     private Stablo formStablo(int beginIndex, int endIndex, List<Integer> levels, List<Stablo> elements) {
 118         if (beginIndex >= endIndex) {
 119             return null;
 120         }
 121         int minIndex = beginIndex;
 122         int minLevel = levels.get(minIndex);
 123         for (int i = beginIndex + 1; i < endIndex; i++) {
 124             int level = levels.get(i);
 125             if (level < minLevel) {
 126                 minLevel = level;
 127                 minIndex = i;
 128             }
 129         }
 130         Stablo stablo = elements.get(minIndex);
 131         Stablo levi = formStablo(minIndex + 1, endIndex, levels, elements);
 132         Stablo desni = formStablo(beginIndex, minIndex, levels, elements);
 133         stablo.setLevi(levi);
 134         stablo.setDesni(desni);
 135         return stablo;
 136     }
 137
 138     @Override
 139     public void printStablo(SvetovidWriter out, Stablo stablo) {
 140         StringBuilder builder = new StringBuilder();
 141         appendTree(builder, stablo, nullSymbol, separated, length);
 142         out.print(builder.toString());
 143     }
 144
 145     protected void appendTree(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, int length) {
 146         String[] buildingBlocks = generateBuildingBlocks(length);
 147         appendRight(builder, stablo, nullSymbol, separated, buildingBlocks, true, buildingBlocks[5]);
 148         appendNode(builder, stablo, nullSymbol != null ? nullSymbol : "|", buildingBlocks[4]);
 149         appendLeft(builder, stablo, nullSymbol, separated, buildingBlocks, false, buildingBlocks[5]);
 150     }
 151
 152     protected void appendNode(StringBuilder builder, Stablo stablo, String nullSymbol, String prefix) {
 153         builder.append(prefix);
 154         if (stablo == null) {
 155             builder.append(nullSymbol);
 156         } else {
 157             builder.append("(");
 158             builder.append(stablo.getId());
 159             builder.append(") ");
 160             builder.append(stablo.getVrednost());
 161         }
 162         builder.append("\n");
 163     }
 164
 165     protected void appendRight(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, String[] buildingBlocks, boolean isRight, String prefix) {
 166         if (stablo == null) {
 167             return;
 168         }
 169         if ((nullSymbol != null) || (stablo.getDesni() != null)) {
 170             appendSubtree(builder, stablo.getDesni(), nullSymbol, separated, buildingBlocks, true, prefix);
 171             if (separated) {
 172                 appendEmpty(builder, buildingBlocks, prefix);
 173             }
 174         }
 175     }
 176
 177     protected void appendLeft(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, String[] buildingBlocks, boolean isRight, String prefix) {
 178         if (stablo == null) {
 179             return;
 180         }
 181         if ((nullSymbol != null) || (stablo.getLevi() != null)) {
 182             if (separated) {
 183                 appendEmpty(builder, buildingBlocks, prefix);
 184             }
 185             appendSubtree(builder, stablo.getLevi(), nullSymbol, separated, buildingBlocks, false, prefix);
 186         }
 187     }
 188
 189     protected void appendEmpty(StringBuilder builder, String[] buildingBlocks, String prefix) {
 190         builder.append(prefix);
 191         builder.append(buildingBlocks[2]);
 192         builder.append("\n");
 193     }
 194
 195     protected void appendSubtree(StringBuilder builder, Stablo stablo, String nullSymbol, boolean separated, String[] buildingBlocks, boolean isRight, String prefix) {
 196         String mojPrefix = prefix;
 197         if (isRight == true) {
 198             mojPrefix = mojPrefix + buildingBlocks[1];
 199         }
 200         if (isRight == false) {
 201             mojPrefix = mojPrefix + buildingBlocks[3];
 202         }
 203         String noviPrefix = prefix + (!isRight ? buildingBlocks[2] : buildingBlocks[0]);
 204         appendRight(builder, stablo, nullSymbol, separated, buildingBlocks, isRight, noviPrefix);
 205         appendNode(builder, stablo, nullSymbol, mojPrefix);
 206         noviPrefix = prefix + (isRight ? buildingBlocks[2] : buildingBlocks[0]);
 207         appendLeft(builder, stablo, nullSymbol, separated, buildingBlocks, isRight, noviPrefix);
 208     }
 209
 210     private String[] generateBuildingBlocks(int length) {
 211         String[] blocks = new String[6];
 212         blocks[0] = generateBlock(EMPTY_SYMBOL, EMPTY_SYMBOL, EMPTY_SYMBOL, length - 2);
 213         blocks[1] = generateBlock(EMPTY_SYMBOL, RIGHT_SYMBOL, HORIZONTAL_SYMBOL, length - 2);
 214         blocks[2] = generateBlock(EMPTY_SYMBOL, VERTICAL_SYMBOL, EMPTY_SYMBOL, length - 2);
 215         blocks[3] = generateBlock(EMPTY_SYMBOL, LEFT_SYMBOL, HORIZONTAL_SYMBOL, length - 2);
 216         blocks[4] = HORIZONTAL_SYMBOL;
 217         blocks[5] = EMPTY_SYMBOL;
 218         return blocks;
 219     }
 220
 221     protected String generateBlock(String emptySymbol, String startSymbol, String repeatSymbol, int repeatCount) {
 222         StringBuilder builder = new StringBuilder();
 223         builder.append(emptySymbol);
 224         builder.append(startSymbol);
 225         for (int i = 0; i < repeatCount; i++) {
 226             builder.append(repeatSymbol);
 227         }
 228         return builder.toString();
 229     }
 230 }