package tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Node {
    int datum;
    Node left, right;
    
    // Constructor with a value for the datum.
    public Node(int value) {
        datum = value;
        left = null;
        right = null;
    }

    // Default constructor
    public Node() {
        datum = 0;
        left = null;
        right = null;
    }
    
    /********************** For the students to implement ***********************/
    
    /*************  C O U N T   O F   Z E R O   D A T A   V A L U E S  **********
    The following function traverses the binary tree (this)and counts every node 
    whose datum value is zero.  The function returns that count as its value.  */

    static int countOfZeroDataValues (Node root) {
        // STUDENTS MUST SUPPLY THE CODE
        return 0;  // A "dummy instruction" that lets the program compile.
    } // countOfZeroDataValues()


    /***************************  H E I G H T  ********************************
    The following function calculates and returns the height of the binary
    tree (this).  The function is recursive.  
    !! Please avoid repeated recursive calls by storing the results of recursive 
    calls into local variables.
    This is a static function because we may want to know the height of an
    empty tree too.*/

    static int height (Node root) {
        // STUDENTS MUST SUPPLY THE CODE
        return 0;  // A "dummy instruction" that lets the program compile.
    } // height()

    /********************  I N C R E M E N T   E A C H   D A T U M  **************
    The following function traverses the binary tree (this) and replaces the datum 
    value in each node by the number that's greater by  1  in value.  
    The function is recursive.  */

    static void incrementEachDatum (Node root) {
        // STUDENTS MUST SUPPLY THE CODE
    } // incrementEachDatum()


    /****************************  R E V E R S E  ******************************
    This function replaces the binary tree (this) with its mirror image.  
    The function is recursive.  */

    void reverse () {
        // STUDENTS MUST SUPPLY THE CODE
    } // reverse()


    /*****************  S U M   O F   N E G A T I V E   D A T A ****************
    The following function traverses the binary tree (this),
    sums the data values that are negative, and returns that sum.  For example,
    if the tree contains nodes with data values  -2 , -6 , and -1 , and no
    other nodes contain negative data, then the function will return the 
    number  -9 .  If the tree contains no node with negative data value,
    then the function returns zero .  The function is recursive. */

    int sumOfNegativeData () {
        // STUDENTS MUST SUPPLY THE CODE
        return 0;  // A "dummy instruction" that lets the program compile.
    } // sumOfNegativeData()
    
    /************************* Additional functions **********************/
    
    // Checks whether the child is a left or a right child of the parent. 
    // Then replaces the left or right link of the parent with the new node. 
    static void replaceChild(Node parent, Node child, Node newNode) {
        if (parent == null)
            return;
        else if (parent.left == child)
            parent.left = newNode;
        else if (parent.right == child)
            parent.right = newNode;
    }
    
    // The following function prints a binary tree vertically graphically
    // showing the connections between parent and child nodes. The function
    // and support functions were written by D. Vrajitoru and C. George. 
    void graphPrint() {
        // create an array to hold the output as is it generated
        ArrayList<String> output = new ArrayList<String>();
        int [] pos = new int[1]; // mutable integer
        pos[0] = graphPrintWalk(this, pos, 0, output);

        // print the root Node
        System.out.println(makeString(pos[0], ' ') + twoDigit(datum));
            
        // print the other levels from top to bottom
        for (int i = 0; i < output.size(); i++) {
            System.out.println(output.get(i));
        }
    } 

    // This function walks through the tree in-order to calculate the x
    // position of each node in the tree. It then prints any child nodes
    // to the appropriate output string and also prints inner-connecting
    // links.
    static int graphPrintWalk(Node root, int[] pos, int level, ArrayList<String> output) {
        if (root == null)
            return pos[0];
        // Expand the size of the output array if this is the first
        // node on a new level
        if (output.size() <= level * 2) {
            output.add("");
            output.add("");
        }

        // Calculate the x position of both child nodes and the current node
        int leftPos = graphPrintWalk(root.left, pos, level + 1, output);

        int currPos = pos[0];
        String currDatum = twoDigit(root.datum);
        pos[0] += currDatum.length() + 1;

        int rightPos = graphPrintWalk(root.right, pos, level + 1, output);

        // initialize the output streams with the current output for the level

        String linkLine, nodeLine;

        linkLine = output.get(level * 2);
        nodeLine = output.get(level * 2 + 1);

        // calculate the center of the current node
        int currOffset = currPos + currDatum.length() / 2 - 1;

        // add the left node and its link to the current output for the level
        if (root.left != null) {
            // calculate the center of the left child node
            String leftDatum = twoDigit(root.left.datum);
            int leftOffset = leftPos + leftDatum.length() / 2 - 1;

            nodeLine += makeString(leftPos - nodeLine.length(), ' ') + leftDatum;

            // draw a link from this Node to the left child node
            linkLine += makeString(leftOffset+1 - linkLine.length(), ' ')
                + makeString(currOffset-(leftOffset+1), '_') + "/";
        }

        // add the right node and its link to the current output for the level
        if (root.right != null) {
            // calculate the center of the right child node
            String rightDatum = twoDigit(root.right.datum);
            int rightOffset = rightPos + (rightDatum.length() / 2) - 1;

            nodeLine += makeString(rightPos - nodeLine.length(), ' ') + rightDatum;

            // draw a link from this node to the right child node
            linkLine += makeString(currOffset+1 - linkLine.length(), ' ') + "\\"
                + makeString(rightOffset-1 - currOffset, '_') + " ";
        }

        // save the results for the current level
        output.set(level * 2, linkLine);
        output.set(level * 2 + 1, nodeLine);

        return currPos;
    }
    
    // Creates a string containing n copies of the character c.
    static String makeString(int n, char c) {
        if (n == 0)
            return "";
        else if (n < 0)
            n = -n;
        char [] copies = new char[n];
        Arrays.fill(copies,  c);
        return String.valueOf(copies);
    }
    
    static String twoDigit(int n) {
        String result = "";
        if (n < 0)
            return result + n;
        else if (n < 10)
            result += "0" + n;
        else
            result += n;
        return result;
    }
    
    /*****************  B U I L D   A   B I N A R Y   T R E E  ******************
    The following function allows an interactive user to construct a binary   
    tree whose nodes hold integer data values.  The function is recursive. 
    Written by D. Vrajitoru and W. Knight. */

    static Node buildABinaryTree (Node root, Node parent, Scanner scan) 
    {
        String action;
        Node local;

        while(true) { // Endless loop; there are two "return" statements in the loop.
            // They are executed whenever the user wants to move up the tree.
            if (root == null) { // The tree or subtree root is empty.
                do { // This loop continues until the user responds with 'U' or 'C'.
                    System.out.println("You are currently at an empty tree. If you wish to create");
                    System.out.println("a new Node at this position, type C and press Enter.");
                    System.out.println("Otherwise type U to go up to the parent Node (if any). ");
                    action = scan.nextLine();
                } while (action.length() == 0 || !"CcUu".contains(action.subSequence(0, 1)));
                            
                if (action.charAt(0) == 'U' || action.charAt(0) == 'u')
                    return root; // Return control to the calling function
                else {
                    local = new Node();
                    System.out.println("Enter an integer for the new Node:");
                    local.datum = scan.nextInt();
                    scan.nextLine(); // clear the empty line after this
                    // replaceChild(parent, root, local);
                    root = local;
                }
            }
            else { // tree is not NULL
                do { // This loop continues until user gives a suitable response.     
                    System.out.println("\nThe datum of the Node at which you have arrived is");
                    System.out.println("         " + root.datum);
                    System.out.println("Enter  U  to go up to the parent Node,");
                    System.out.println("       L  to go down to the left,");
                    System.out.println("       R  to go down to the right,");
                    System.out.println("       P  print the current subtree,");
                    System.out.println("       M  to modify value of the datum stored here,");
                    System.out.println("       D  to delete the whole subtree.");
                    action = scan.nextLine();
                }
                while (action.length() == 0 || !"UuLlRrMmPpDd".contains(action.subSequence(0, 1)));
                      
                switch (action.charAt(0)) { 
                case 'U': case 'u': 
                    return root;   // Go back to the calling function.
                case 'L': case 'l': 
                    root.left = buildABinaryTree (root.left, root, scan);  
                    break;
                case 'R': case 'r': 
                    root.right = buildABinaryTree (root.right, root, scan); 
                    break;
                case 'P': case 'p': 
                    root.graphPrint(); 
                    break;
                case 'M': case 'm': 
                    System.out.println("Enter a new datum value to replace the current value.");
                    root.datum = scan.nextInt();
                    break;
                case 'D': case 'd': 
                    replaceChild(parent, root, null); 
                    root = null;
                } // end of "switch"
            }   // end of "else"     
        }     // end of "while(true)"
    }       // end of function 
}