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

HashiCorp Vault Integration with Ansible Etower using approle

Image
HashiCorp Vault is  a secrets management tool specifically designed to control access to sensitive credentials in a low-trust environment . It can be used to store sensitive values and at the same time dynamically generate access for specific services/applications on lease.  Integrating the vault with Ansible Etower provides robust and secure automation. Following is the step-by-step guide for the integration. Enable key-value secret engine in Hashi Vault (also known as "kv" engine). Let's call the engine, the "kv" engine. Create a secret inside "kv". A secret can be a collection of key-value pairs or a JSON for nested structure.            Lets assume that secrets are stored as JSON  in the format   { "my_app":{ "service_account_name": "some_service", "service_account_password": "some_password" } } Create a secret policy defining what can be done with the above-defined secret. Create an
Read more

utility to extract date from text with java

Image
A date pattern recognition algorithm to not only identify date pattern but also fetches probable date in Java date format. This algorithm is very fast and lightweight. The processing time is linear and all dates are identified in a single pass. Algorithm resolves date using tree traverse mechanism. Tree data structures are custom created to build supported date, time and month patterns. Following Trees are used (Note: ^ sign denotes complete pattern) DATE PATTERN TREE Month Pattern Tree (Jan and January both are valid, identified using ^ sign) Time pattern (Identified as suffix to Date, $ sign indicates SPACE character) Tree structures are used in the following algorithm.  Date Part Identification algorithm flowchart Time part identification algorithm flowchart These flow charts are self-explanatory in most part. --> sign is used to denote next match in respective tree structures. The algorithm also acknowledges multipl
Read more