// Cloned by Himanshu Warekar on 14 Oct 2021 from World "Binary tree" by "Coding Train" project 
// Please leave this clone trail here.
 
// canvas size
const cw = 900;
const ch = 600;
   
const root_x = cw / 2;
const root_y = ch / 10;
const ellipse_size = cw / 25;

// range of numbers
const MAX = 30;

// how many nodes 
const NONODES = MAX / 2;

// console log how we build the tree or not 
const SHOWBUILD = true;


// Binary tree
var tree;


// TreeNode 
class Node {
    constructor(value, x, y) {
        this.value = value;
        this.left = null;
        this.right = null;
        // How far apart should the children nodes be
        // This will be based on "level" in the tree
        this.distance = 2;
        
        this.x = x;
        this.y = y;   
    }
    
    search(value) {
        if (value === this.value) {
            console.log("found!"); 
            return this;
        } else if (value < this.value ) {
            if (this.left !== null) {
                console.log ("go left"); 
                return this.left.search(value); 
            } else { 
                console.log ("search value lower but nothing to LHS - done"); 
                return null;
            }        
        } else if ( value > this.value ) {
            if (this.right !== null) { 
                console.log ("go right"); 
                return this.right.search(value); 
            } else { 
                console.log("search value higher but nothing to RHS - done"); 
                return null; 
            }
        }
    }
    
    visit(parent) {
  // Recursively go left
        if (this.left !== null) { 
            this.left.visit(this);
        }
        
        // Draw a line from the parent position (parent not drawn yet)
        // console.log( "drawing line from parent " + parent.value + " to this " + this.value);
        stroke("grey");
        line(parent.x, parent.y, this.x, this.y);
        
        // Draw a circle
        stroke("black");
        fill("black");
        ellipse(this.x, this.y, ellipse_size, ellipse_size);
        
        // Display the value
        fill("white");
        textAlign(CENTER);
        textSize(14);
        text(this.value, this.x,  this.y + (ellipse_size/6));
        
        // Go right
        if (this.right !== null) { 
            this.right.visit(this);
        }
    }
    
    addNode(n) {
        if (n.value === this.value) return;
        
        if (SHOWBUILD)  console.log ( "adding node " + n.value  + " to current node " + this.value );
        
        if (n.value < this.value) {
            if (this.left === null) {
                if ( SHOWBUILD ) console.log ("put it here on left");
                this.left = n;
                this.left.x = this.x - (cw / pow(2, n.distance));
                this.left.y = this.y + (ch / 10);
            } else {
                if ( SHOWBUILD ) console.log ("go left");
                n.distance++;             // change node.distance at each level 
                this.left.addNode(n)        // recusively keep going 
            }
        } else if (n.value > this.value) {
            if (this.right === null) {
                 if ( SHOWBUILD ) console.log ("put it here on right");
                 this.right = n;
                 this.right.x = this.x + (cw / pow(2, n.distance));
                 this.right.y = this.y + (ch / 10);
            } else {
                if ( SHOWBUILD ) console.log ("go right");
                n.distance++;
                this.right.addNode(n);
            }
        }
    }
}

// Tree
class Tree { 
    constructor() {
        // Just store the root
        this.root = null;    
    }
    
    traverse() {
        this.root.visit(this.root);
    }
    
    search(value) {
        //  console.log ("Tree.search: start at " + this.root.value );
        let found = this.root.search(val);
        return found;
    }
    
    addValue(value) {
        let n = new Node(value);
        if (this.root === null) {
            if ( SHOWBUILD )  console.log ( "root = " + n.value );
            this.root = n;
            // An initial position for the root node
            this.root.x = root_x;
            this.root.y = root_y;
        } else {
            this.root.addNode(n);
        }
    }
}


function setup()  {
    createCanvas(cw,ch);
    $.getScript("/uploads/codingtrain/node.js", function() {
        $.getScript("/uploads/codingtrain/tree.js", function() {
            tree = new Tree();

            console.log ("=== build tree =================");
            // Add random values
            for (var i = 0; i < NONODES; i++) {
                let n = floor(random(0, MAX));
                tree.addValue(n);
            }
            
            background("lightgreen");
            
            // Traverse the tree
            tree.traverse();
            
            // Search the tree for random number 
            let x = floor(random(0, MAX));
            AB.msg( "console log shows how we search a sorted tree quickly <br> search tree for " + x + "<br>" );
            console.log ( "=== search tree for " + x  + " ===================");
            
            tree.search(x) === null ?  AB.msg('not found', 2) : AB.msg('found', 2);
        });
    });
}