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

Caused by: java.sql.SQLTimeoutException: ORA-01013: user requested cancel of current operation

Many times we encounter this error and think that there might be some JPA issue or network issue. However, the error is pretty explicit in its nature, but still not clear to ring the bell very first time. As the error says there is a timeout, and since Oracle is saying, we shall accept it. Another clue is "user requested cancel of current operation". This means that the connection was closed by the application server not the database server, hence it can be safely concluded that application has configured timeouts on transactions at its end. However, if you feel that this transaction should have been concluded within the application server limits, your doubt might be true. This problem can arise in case there is a lock on the record being updated by JPA or lock on the table in which JPA is attempting to insert. The lock is most probably being held by some other application, and since application server configuration is on aggressive SLA, the transaction is waiting its...
Read more

pandas dataframe add missing date from range in a multi-dimensional structure with duplicate index

This solution demonstrates how to fill in the missing dates in a given range in a multi-index pandas dataframe. The complexity is added by the presence of duplicate dates in the given data, where the date is considered as an index. In case you try to reindex a data frame with duplicate indexes, you will get the following error. ValueError : cannot reindex from a duplicate axis To resolve this situation and to achieve the end goal of refitting dataset with missing indexes, following pseudo code can be used. Read multidimensional data into pandas dataframe (dataset), with date column as an index (only one index). Transform dataframe index created above into datetime index type Create a new dataframe (d) with the required date range, and value of other records as null Append 'd' into 'dataset' Set index of 'dataset' to include more column to create a multi-level index Reindex to 'dataset', and fill the desired value. The example python co...
Read more

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