// Cloned by Colin Ekedigwe on 3 Oct 2022 from World "Binary tree (clone by Colin Ekedigwe)" by Colin Ekedigwe 
// Please leave this clone trail here.
 


// Cloned by Colin Ekedigwe on 3 Oct 2022 from World "Binary tree" by "Coding Train" project 
// Please leave this clone trail here.
 

// Modified port of "01_binary_tree_viz" from AI course by Daniel Shiffman
// https://github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/tree/master/week1-graphs

// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning

// 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 = 50;

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

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


// Binary tree
var tree;


function setup() 
{
  createCanvas(cw,ch);


$.getScript ( "/uploads/codingtrain/node.js", function() {
   // console.log ("Got node");
    
$.getScript ( "/uploads/codingtrain/tree.js", function() {
      //  console.log ("Got tree");
        
        
  // New tree
  tree = new Tree();

  console.log ("=== build tree =================");
  // Add random values
  for (var i = 0; i < NONODES; i++) 
  {
      var n = floor(random(0, MAX));
      // console.log ("adding node: " + n);
      tree.addValue(n);
  }

  background("beige");

  // Traverse the tree
  tree.traverse();

  // Search the tree for random number 
  var 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  + " ===================");
   
  var result = tree.search(x);
  if (result == null)   AB.msg('not found', 2);
  else                  AB.msg('found', 2);
  
  
} );
} );

}

// Node in the tree
function Node(val, x, y) 
{
  this.value = val;
  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 the tree for a value
Node.prototype.search = function(val) 
{
    console.log ("current " + this.value );
  if ( val == this.value )   { console.log ( "found!" ); return this; }
  
  if ( val < this.value )
    if ( this.left != null )  { console.log ("go left"); return this.left.search(val); }
    else { console.log ("search value lower but nothing to LHS - done"); return null; }
    
  if ( val > this.value )
    if ( this.right != null ) { console.log ("go right"); return this.right.search(val); }
    else { console.log ("search value higher but nothing to RHS - done"); return null; }
}


Node.prototype.visit = function(parent)         // for drawing the graph 
{
  // Recursively go left
  if (this.left != null) { /*console.log ("go left");*/ 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");
  // console.log ("drawing node " + this.value );
  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) { /*console.log ("go right");*/ this.right.visit(this); }
}


// Add a new Node
Node.prototype.addNode = function(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;
      // Exponentially shrink the distance between nodes for each level
      // minus 1/4 of the width
      // minus 1/8 of the width
      // ....
        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 object
function Tree() 
{
  // Just store the root
  this.root = null;
}

// Start by visiting the root
Tree.prototype.traverse = function() 
{
  this.root.visit(this.root);
}

// Start by searching the root
Tree.prototype.search = function(val) 
{
  //  console.log ("Tree.search: start at " + this.root.value );
  var found = this.root.search(val);
  return found;
}

// Add a new value to the tree
Tree.prototype.addValue = function(val) 
{
  var n = new Node(val);
  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);
}