class Node {
    constructor(value){
        this.value = value;
        this.parent = null;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(node){
        this.root = node;
    }
    
    // Insert Node
    insert(node, root){
        if (node.value == root.value){
            return ;
        }
        else if(node.value < root.value){
            // check if left subtree is null
            if (root.left != null){
                this.insert(node, root.left);  
            }
            else{
                root.left = node;
                node.parent = root;
            }
        } else {
            // check if right subtree is null
            if (root.right != null){
                this.insert(node, root.right); 
            }
            else{
                root.right = node; 
                node.parent = root;
            }
        }    
    }
}

function myXOR(a,b) {
    return ( a || b ) && !( a && b );
}

// Main Program
(function(){
    var numbers = [9,7,8,15];

    var node = new Node(5);
    var tree = new BinarySearchTree(node);

    for (i in numbers){
        tree.insert(new Node(numbers[i]), tree.root);
    }    
    
    // Set dimensions and margins for diagram
    var margin = {top: 40, bottom: 80},
        width = 400,
        height = 400 - margin.top - margin.bottom;

    // append the svg object to the body of the page
    // appends a 'group' element to 'svg'
    // moves the 'group' element to the top left margin   
    var svg = d3.select("body").append("svg")
        // .attr("width", "100%")
        .attr("height", height + margin.top + margin.bottom)
        .attr("viewBox","0 0 400 400")
        .append("g")
        .attr("transform", "translate(0," + margin.top + ")");
                    
    var i = 0,      
        duration = 750,
        root;

    // Declares a tree layout and assigns the size
    var treemap = d3.tree().size([width, height]);

    // Assigns parent, children, height, depth, and coordinates
    root = d3.hierarchy(tree.root, function(d){

        d.children=[];
        if (d.left){
            d.children.push(d.left);
            if (myXOR(d.left, d.right)){
                d.children.push(new Node("e"));
            }
        }
        if (d.right){
            if (myXOR(d.left, d.right)){
                d.children.push(new Node("e"));
            }
            d.children.push(d.right);
        }
        return d.children; 
    });
    
	
    root.x0 = width / 2;
    root.y0 = 0;

    // Collapse after the second level
    // root.children.forEach(collapse);

    update(root);

    // Collapse the node and all it's children
    function collapse(d){
        if(d.children){
            d._children = d.children
            d._children.forEach(collapse)
            d.children = null;
        }
    }

    // Update
    function update(source){
        // Assigns the x and y position for the nodes
        var treeData = treemap(root);
        
        // Compute the new tree layout.
        var nodes = treeData.descendants(),
            links = treeData.descendants().slice(1);
            
        // Normalize for fixed-depth
        nodes.forEach(function(d){ d.y = d.depth*100 });    
        
        // **************** Nodes Section ****************
        
        // Update the nodes...
        var node = svg.selectAll('g.node')
             .data(nodes, function(d) {return d.id || (d.id = ++i); });
             
        // Enter any new nodes at the parent's previous position.
        var nodeEnter = node.enter().append('g')
                         .attr('class', 'node')
                         .attr("transform", function(d){
                             return "translate(" + source.x0 + "," + source.y0 + ")";
                         })
                         .on('click', click);
                         
        // Add Circle for the nodes
        nodeEnter.append('circle')
            .attr('class', function(d) {
              if (isNaN(d.value)) {
                return "node hidden";
              }
                return 'node';
            })
            .attr('r', 1e-6)
            .style("fill", function(d){
                return d._children ? "lightsteelblue" : "#fff";
            });
        
        // Add labels for the nodes
        nodeEnter.append('text')
            .attr("dy", ".35em")
            .attr("x", function(d){
                return d.children || d._children ? -13 : 13;
            })
            .attr("text-anchor", function(d){
                return d.children || d._children ? "end" : "start";
            })
            .text(function(d){ return d.data.value; });
        
        // Update
        var nodeUpdate = nodeEnter.merge(node);
        
        // Transition to the proper position for the nodes
        nodeUpdate.transition()
            .duration(duration)
            .attr("transform", function(d) {
                return "translate(" + d.x + "," + d.y + ")";
            });
        
        // Update the node attributes and style
        nodeUpdate.select('circle.node')
            .attr('r', 10)
            .style("fill", function(d){
                return d._children ? "lightsteelblue" : "#fff";
            })
            .attr('cursor', 'pointer');
            
        // Remove any exiting nodes
        nodeExit = node.exit().transition()
            .duration(duration)
            .attr("transform", function(d){
                return "translate(" + source.x +","+ source.y +")";
            })
            .remove();
            
        // On exit reduce the node circles size to 0
        nodeExit.select('circle')
            .attr('r', 1e-6);
        
        // On exit reduce the opacity of text lables  
        nodeExit.select('text')
            .style('fill-opacity', 1e-6)
            
        // **************** Links Section ****************
        
        // Update the links...
        var link = svg.selectAll('path.link')
            .data(links, function(d){ return d.id; });
            
        // Enter any new links at the parent's previous position
        var linkEnter = link.enter().insert('path', "g")
            .attr("class", function(d) {
                if (isNaN(d.value)) {
                    return "link hidden "
                }
                return "link";
            })
            .attr('d', function(d){
                var o = {x: source.x0, y: source.y0};
                return diagonal(o,o);
            });
        
        // Update
        var linkUpdate = linkEnter.merge(link);
        
        // Transition back to the parent element position
        linkUpdate.transition()
            .duration(duration)
            .attr('d', function(d){ return diagonal(d, d.parent) });
        
        // Remove any existing links
            var linkExit = link.exit().transition()
                .duration(duration)
                .attr('d', function(d){
                    var o = {x: source.x, y: source.y};
                })
                .remove();
        
        // Store the old positions for transition.
        nodes.forEach(function(d){
            d.x0 = d.x;
            d.y0 = d.y;
        });
        
        // Create a curved (diagonal) path from parent to the child nodes
        function diagonal(s,d){
            path = `M ${s.x} ${s.y}
            C ${(s.x + d.x) / 2} ${s.y},
              ${(s.x + d.x) / 2} ${d.y},
              ${d.x} ${d.y}`

            return path;
        }

        // Toggle children on click
        function click(d){
            if (d.children){
                d._children = d.children;
                d.children = null;
            }
            else{
                d.children = d._children;
                d._children = null;
            }
            update(d);
        }
    }
    
})()