Print multi tree data structure ascii visualization on console with java

I was struggling with a debugging problem in one of my programs, which showed intermittent bugs when working on a huge amount of text data. The program was performing pattern matching using a tree prediction as discussed in my other blog at http://coffeefromme.blogspot.com/2015/10/to-extract-date-from-given-text-with.html

Since debugging huge set of text data is very hard, I required my tree to show on console visually to help me find the bug source. I tried to find available algorithms to print tree on the console. There were programs which could print binary trees, but not for the multi-children tree. So I created the following code to print the tree.

Sample Tree using text in class Test
Class : Test (To build and print the tree)

import java.util.ArrayList;
import java.util.List;


public class Test {

    public static void main(String a[]) {
        List<String> l = new ArrayList<String>();
        l.add("DDDD*DD*DD");
        l.add("DDDD*D*DD");
        l.add("DDDD*DD*D");
        l.add("DDDD*D*D");
        l.add("DD*DD*DD");
        l.add("DD*D*DD");
        l.add("DD*DD*D");
        l.add("DD*D*D");
        l.add("DD*DD*DDDD");
        l.add("D*DD*DDDD");
        l.add("DD*D*DDDD");
        l.add("D*D*DDDD");
        l.add("DD*DD*DD");
        l.add("D*DD*DD");
        l.add("DD*D*DD");
        l.add("D*D*DD");
        l.add("DDDD*M*DD");
        l.add("DDDD*M*D");
        l.add("DD*M*DD");
        l.add("DD*M*D");
        l.add("DD*M*DDDD");
        l.add("D*M*DDDD");
        l.add("DD*M*DD");
        l.add("D*M*DD");
        l.add("M*DD*DDDD");
        l.add("M*D*DDDD");
        l.add("M*DD*DD");
        l.add("M*D*DD");
        
        PredictionModelNode tree = new PredictionModelNode();
        Dictionary.buildTree(l, tree);
        Dictionary.printTree(tree);
    }
}

Class : PredictionModelNode


import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Vaibhav Singh
 * This class creates multi tree data structure
 */
public class PredictionModelNode {

    public char charcter;
    boolean isDigit = false;
    public int level;
    public List<PredictionModelNode> childern;
    public PredictionModelNode parent;
    public boolean explictDateFragment=false;

    public PredictionModelNode getChild(char c) {
        if (childern == null) {
            return null;
        }
        for (PredictionModelNode child : childern) {
            if (c == child.charcter) {
                return child;
            }
        }
        return null;
    }

    public void addChild(PredictionModelNode child) {
        if (childern == null) {
            childern = new ArrayList<PredictionModelNode>();
        }
        child.level=this.level+1;
        childern.add(child);
    }
    
    public boolean hasChildern(){
         if (childern == null) {
             return false;
         }else{
             return true;
         }
    }
    
    public int childrenCount(){
         if (childern == null) {
             return 0;
         }else{
             return childern.size();
         }
    }
    
    
}


Class : TreeChar

/**
 * To create a bit map type structure for lietrals of the tree
 * @author Vaibhav Singh
 *
 */
public class TreeChar implements Comparable<TreeChar>{
    
    public String symbol="";
    
    public int leftSpace=0;
    
    public int level=0;

    public TreeChar(String symbol, int leftSpace, int level) {
        super();
        this.symbol = symbol;
        this.leftSpace = leftSpace;
        this.level = level;
    }

    public TreeChar(String symbol) {
        super();
        this.symbol = symbol;
    }

    @Override
    public int compareTo(TreeChar arg0) {
        if(level>arg0.level){
            return 1;
        }
        if(level<arg0.level){
            return -1;
        }
        return 0;
    }
}

Class : Dictionary

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * This class helps to build the tree data structure using PredictionModelNode class and helps to print it.
 * @author Vaibhav Singh
 */
public class Dictionary {

    /* only used to print tree on console */
    public static final int HOROZONTAL_PRINT_GAP = 3;
    public static final int VERTICAL_PRINT_GAP = 2;


    public static void buildTree(List<String> itemList, PredictionModelNode parentNode) {
        for (String s : itemList) {
            PredictionModelNode parent = parentNode;
            parentNode.charcter = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                PredictionModelNode node = parent.getChild(c);
                if (node == null) {
                    PredictionModelNode child = new PredictionModelNode();
                    child.charcter = c;
                    if (i + 1 == s.length()) {
                        child.explictDateFragment = true;
                    }
                    parent.addChild(child);
                    parent = child;
                } else {
                    if (i + 1 == s.length()) {
                        node.explictDateFragment = true;
                    }
                    parent = node;
                }
            }
        }
    }

    public static void printTree(PredictionModelNode tree) {

        tree = sortTree(tree);

        DisplayObject displyObject = displayBuilder(new DisplayObject(), tree);

        StringBuffer printBuffer = new StringBuffer();

        String line = getBlankLine(displyObject.width);

        int prevLevel = 0;
        for (TreeChar tc : displyObject.displayBuffer) {
            if (prevLevel == tc.level) {
                line = line.substring(0, tc.leftSpace) + tc.symbol + line.substring(tc.leftSpace + 1);
            } else {
                line = line.replaceAll("\\s+$", "") + System.lineSeparator();
                printBuffer.append(line);
                line = getBlankLine(displyObject.width);
                line = line.substring(0, tc.leftSpace) + tc.symbol + line.substring(tc.leftSpace + 1);
                prevLevel = tc.level;
            }
        }
        printBuffer.append(line);
        System.out.println(printBuffer.toString());

    }

    /**
     * 
     * @param disply
     * @param tree
     * @return
     */
    private static DisplayObject displayBuilder(DisplayObject display, PredictionModelNode tree) {
        if (isFamilyUnit(tree)) {
            return familyDisplayBuilder(tree);
        }

        DisplayObject horizontalDisply = new DisplayObject();
        for (PredictionModelNode kid : tree.childern) {
            DisplayObject recusiveDisplay = displayBuilder(horizontalDisply, kid);
            horizontalDisply = adjustHorizontalDisplay(horizontalDisply, recusiveDisplay);
        }

        Collections.sort(horizontalDisply.displayBuffer);

        DisplayObject verticalDisplay = new DisplayObject();
        int[] dadJoints = new int[tree.childrenCount()];

        int j = 0;
        for (TreeChar tc : horizontalDisply.displayBuffer) {
            if (tc.level > 0 || j > dadJoints.length) {
                break;
            }
            if (!(tc.symbol.matches("/|\\\\|_|\\|") || "".equals(tc.symbol.trim()))) {
                dadJoints[j++] = tc.leftSpace;
            }
        }

        if (tree.childrenCount() == 0) {
            return horizontalDisply;
        }
        if (tree.childrenCount() == 1) {
            TreeChar tc = new TreeChar(String.valueOf(tree.charcter), dadJoints[0], 0);
            verticalDisplay.displayBuffer.add(tc);

        } else {
            Arrays.sort(dadJoints);
            String symbol = "_";
            int papaPosition = dadJoints.length % 2 == 0 ? 1+(dadJoints[dadJoints.length - 1] + dadJoints[0]) / 2 : dadJoints[dadJoints.length / 2] + 1;
            // improve visualization
            papaPosition--;
            for (int k = dadJoints[0] + 1; k <= dadJoints[dadJoints.length - 1] + 1 - 2; k++) {
                TreeChar tc;
                if (k == papaPosition) {
                    String s = "".equals(String.valueOf(tree.charcter).trim()) ? "$" : String.valueOf(tree.charcter);
                    tc = new TreeChar(s, k, 0);
                } else {
                    tc = new TreeChar(symbol, k, 0);
                }
                verticalDisplay.displayBuffer.add(tc);
            }
        }

        for (int i = 0; i < dadJoints.length; i++) {
            for (int m = 0; m < VERTICAL_PRINT_GAP; m++) {
                TreeChar tc = new TreeChar("|", dadJoints[i], m + 1);
                verticalDisplay.displayBuffer.add(tc);
            }
        }

        display = adjustVerticalDisplay(horizontalDisply, verticalDisplay);

        return display;
    }

    private static DisplayObject adjustVerticalDisplay(DisplayObject horizontalDisply, DisplayObject verticalDisplay) {
        if (horizontalDisply.displayBuffer.size() == 0) {
            return verticalDisplay;
        }
        Collections.sort(verticalDisplay.displayBuffer);
        for (TreeChar tc : horizontalDisply.displayBuffer) {
            tc.level += VERTICAL_PRINT_GAP + 1;
            verticalDisplay.displayBuffer.add(tc);
        }
        verticalDisplay.width = horizontalDisply.width;
        return verticalDisplay;
    }

    /**
     * 
     * @param display
     * @param kidDisplay
     * @return
     */
    private static DisplayObject adjustHorizontalDisplay(DisplayObject display, DisplayObject kidDisplay) {
        if (display.displayBuffer.size() == 0) {
            return kidDisplay;
        }

        int leftPos = display.width;
        for (TreeChar tc : kidDisplay.displayBuffer) {
            tc.leftSpace += (leftPos + HOROZONTAL_PRINT_GAP);
            int i = 0;
            int displayBufferSize = display.displayBuffer.size();
            for (TreeChar displayTc : display.displayBuffer) {
                if (displayBufferSize == i + 1) {
                    display.displayBuffer.add(displayBufferSize, tc);
                    break;
                } else if (displayTc.level <= tc.level) {
                    i++;
                    continue;
                }
                display.displayBuffer.add(i - 1, tc);
                break;
            }
        }
        display.height = display.height >= kidDisplay.height ? display.height : kidDisplay.height;
        display.width = display.width + kidDisplay.width + HOROZONTAL_PRINT_GAP;
        return display;

    }

    private static DisplayObject familyDisplayBuilder(PredictionModelNode tree) {
        DisplayObject displyObject = new DisplayObject();
        int kids = tree.childrenCount();
        String charVal = String.valueOf(tree.charcter);
        if (kids == 1) {
            displyObject.displayBuffer.add(new TreeChar(charVal, 0, 0));
            displyObject.displayBuffer.add(new TreeChar("|", 0, 1));
            String kidChar = String.valueOf(tree.childern.get(0).charcter);
            displyObject.displayBuffer.add(new TreeChar(kidChar, 0, 2));
            displyObject.width = 1;
            displyObject.height = 3;
        } else if (kids % 2 == 0) {
            displyObject = evenKidCountTree(displyObject, tree);
        } else {
            displyObject = oddKidCountTree(displyObject, tree);
        }
        return displyObject;
    }

    /**
     * 
     * @param displayBuffer
     * @param tree
     * @return
     */
    public static DisplayObject evenKidCountTree(DisplayObject displyObject, PredictionModelNode tree) {
        int kids = tree.childrenCount();
        int papaPosition = kids / 2;
        String charVal = String.valueOf(tree.charcter);
        displyObject.displayBuffer.add(new TreeChar(charVal, papaPosition, 0));
        displyObject.height = papaPosition + 2;
        displyObject.width = kids + 1;
        // Iterate to add tree structure elements '/','|','\'
        for (int i = 0; i < kids / 2; i++) {
            // Iterate to add columns
            int markers = (i + 1) * 2;
            int coeffiecient = 1;
            for (int j = 0; j < markers; j++) {
                // reset the coefficient once halfway is crossed
                if (coeffiecient == markers / 2 + 1) {
                    coeffiecient = 1;
                }
                // half of markers will be on left
                if (j < markers / 2) {
                    // String symbol = "/";
                    String symbol = "|";
                    int leftpos = papaPosition - coeffiecient++;
                    /*
                     * if (leftpos == papaPosition - 1 && i != 0) { symbol =
                     * "|"; }
                     */
                    if (j == markers / 2 - 1) {
                        symbol = "/";
                    }
                    displyObject.displayBuffer.add(new TreeChar(symbol, leftpos, i + 1));
                } else {
                    int rightpos = papaPosition + coeffiecient++;
                    // String symbol = "\\";
                    String symbol = "|";
                    /*
                     * if (rightpos == papaPosition + 1 && i != 0) { symbol =
                     * "|"; }
                     */
                    if ((j == markers - 1 && i != 0) || markers < 3) {
                        symbol = "\\";
                    }
                    displyObject.displayBuffer.add(new TreeChar(symbol, rightpos, i + 1));
                }
            }

        }
        // Iterate to add children to tree
        for (int i = 0; i < kids; i++) {
            String kidVal = String.valueOf(tree.childern.get(i).charcter);
            if (i < kids / 2) {
                displyObject.displayBuffer.add(new TreeChar(kidVal, i, kids / 2 + 1));
            } else {
                displyObject.displayBuffer.add(new TreeChar(kidVal, i + 1, kids / 2 + 1));
            }
        }
        return displyObject;
    }

    /**
     * 
     * @param displayBuffer
     * @param tree
     * @return
     */
    public static DisplayObject oddKidCountTree(DisplayObject displyObject, PredictionModelNode tree) {
        int kids = tree.childrenCount();
        int papaPosition = (kids - 1) / 2;
        String charVal = String.valueOf(tree.charcter);
        displyObject.displayBuffer.add(new TreeChar(charVal, papaPosition, 0));
        displyObject.height = papaPosition + 2;
        displyObject.width = kids;
        // Iterate to add tree structure elements '/','|','\'
        for (int i = 0; i < (kids - 1) / 2; i++) {
            // Iterate to add columns
            int markers = 2 * i + 3;
            int coeffiecient = 1;
            for (int j = 0; j < markers; j++) {
                // reset the coefficient once halfway is crossed
                if (coeffiecient == markers / 2 + 1) {
                    coeffiecient = 1;
                }
                // half of markers will be on left
                if (j < markers / 2) {
                    // String symbol = "/";
                    String symbol = "|";
                    int leftpos = papaPosition - coeffiecient++;
                    /*
                     * if (leftpos == papaPosition - 1 && i != 0) { symbol =
                     * "|"; }
                     */
                    if (j == markers / 2 - 1 && markers > 2) {
                        symbol = "/";
                    }
                    displyObject.displayBuffer.add(new TreeChar(symbol, leftpos, i + 1));
                } else if (j == markers / 2) {
                    displyObject.displayBuffer.add(new TreeChar("|", papaPosition, i + 1));
                } else {
                    int rightpos = papaPosition + coeffiecient++;
                    // String symbol = "\\";
                    String symbol = "|";
                    /*
                     * if (rightpos == papaPosition + 1 && i != 0) { symbol =
                     * "|"; }
                     */
                    if (j == markers - 1 && markers > 2) {
                        symbol = "\\";
                    }
                    displyObject.displayBuffer.add(new TreeChar(symbol, rightpos, i + 1));
                }
            }

        }
        // Iterate to add children to tree
        for (int i = 0; i < kids; i++) {
            String kidVal = String.valueOf(tree.childern.get(i).charcter);
            displyObject.displayBuffer.add(new TreeChar(kidVal, i, kids / 2 + 1));
        }
        return displyObject;
    }

    private static int getMaxTreeHeight(PredictionModelNode tree) {
        if (tree.hasChildern()) {
            int[] height = new int[tree.childrenCount()];
            for (int i = 0; i < tree.childrenCount(); i++) {
                PredictionModelNode child = tree.childern.get(i);
                height[i] = getMaxTreeHeight(child);
            }
            int max = height[0];
            for (int j = 1; j < height.length; j++) {
                if (max < height[j]) {
                    max = height[j];
                }
            }
            return max + 1;
        }
        return 0;
    }

    private static PredictionModelNode sortTree(PredictionModelNode tree) {
        if (tree.hasChildern()) {
            for (PredictionModelNode child : tree.childern) {
                child = sortTree(child);
            }
            boolean swapped = true;
            if (tree.childrenCount() <= 1) {
                return tree;
            }
            while (swapped) {
                swapped = false;
                for (int i = 0; i < tree.childrenCount() - 1; i++) {
                    int thisHeight = getMaxTreeHeight(tree.childern.get(i));
                    int nextHeight = getMaxTreeHeight(tree.childern.get(i + 1));
                    if (thisHeight < nextHeight) {
                        swapped = true;
                        PredictionModelNode tempChild = tree.childern.get(i);
                        tree.childern.set(i, tree.childern.get(i + 1));
                        tree.childern.set(i + 1, tempChild);
                    }
                }
            }
            return tree;
        }
        return tree;
    }

    /**
     * 
     * @param tree
     * @return
     */
    private static boolean isFamilyUnit(PredictionModelNode tree) {
        if (tree.hasChildern()) {
            for (PredictionModelNode node : tree.childern) {
                if (node.hasChildern()) {
                    return false;
                }
            }
            return true;
        }
        return true;
    }

    private static String getBlankLine(int i) {
        String str = new String();
        str = " ";
        for (int j = 0; j < i; j++) {
            str = " " + str;
        }
        return str;
    }

}

Comments

  1. AnonymousSeptember 9, 2017 at 5:31 AM

    wow, its brilliant and helps a lot in debugging complex tree structures.

    ReplyDelete

Post a Comment

Popular posts from this blog

Delete horizontal, vertical and angled lines from an image using Python to clear noise and read text with minimum errors

I was working on an algorithm to detect lines in a image. I found many solutions online, but none of them seem to work to my satisfaction. Thereafter, I decided to write an algorithm, which can work to my satisfaction. This algorithm can detect horizontal, vertical and angled lines. Following is the pseudo code of the algorithm. The implementation is in Python and it uses third party code. pix_array = Convert the image into 2D pixel array  Mono chromate the pixel array by setting values between 0-200 as 0 (black) and greater than 200 as 255(white) as  image_width = length of pix_array[0] image_height = length of pix_array Loop through pix_array, i.e. 1 pixel high horizontal slice of image: h = x coordinate of current pixel k = y coordinate of current pixel choose a value of radius as r draw a circle taking h,k as center using equation (X-h)^2 + (Y-k)^2 = r^2 derive values of X and Y and check if pix_arrY[X][Y] is black (0) if black add them to possible line c...
Read more

Unordered JSON compare for differences using javascript

Sometimes we need to programmatically compare JSON from two or more sources and determine what's the difference between them. The program below can do deep compare JSON even if they are not in the same order or conatins substructures and arrays. It provides the detailed list of mismatches and misses in both JSON's by calling out attributes with the same keys and different values or missing keys. const obj1={ "k1":"aq", "k2":"b", "k3":"c", "k4":{ "kk1":"aq", "kk2":"b", "kk3":"c", "kk4":{ "kkk1":"" }, "kk5":"abc" }, "k5":[{"kk5":"abc","kk6":"53"},{"kk5":"abc","kk6":"54"}] } const obj2={ "k1":"a", "k2...
Read more

Java Currency Formatter Changing $ to ¤

 Java currency formatting problem. Following code shows the conditions when the currency symbol is replaced by an alt currency symbol. public class Test { public static void main(String[] args){ double num = 1323.526; Locale eng = new Locale("", ""); NumberFormat engFormat = NumberFormat.getCurrencyInstance(eng); System.out.println(engFormat.format(num)); eng = new Locale("en", ""); engFormat = NumberFormat.getCurrencyInstance(eng); System.out.println(engFormat.format(num)); eng = new Locale("en", "en_US"); engFormat = NumberFormat.getCurrencyInstance(eng); System.out.println(engFormat.format(num)); eng = new Locale("", "US"); engFormat = NumberFormat.getCurrencyInstance(eng); System.out.println(engFormat.format(num)); eng = new Locale(...
Read more