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