// Cloned by Michael Walsh on 4 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 = window.innerWidth;
const ch = window.innerHeight;
   
const root_x = cw / 2;
const root_y = 35;
const ellipse_size = 40;

// range of numbers
const MAX = 3000;

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

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

$("#w2m_runcontrols").html("<form onsubmit='console.log(this.elements[0].value);return false;'><input type='text'>")



// Binary tree
var tree;


function setup() 
{
  createCanvas(cw,ch);
  
  let startTime = new Date().getTime();

  // 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("white");

  // Traverse the tree
 // tree.traverse();

  let endBuildTime = new Date().getTime();
  
  console.log("Total build time: " + (endBuildTime - startTime));

  // Search the tree for random number 
  var x = floor(random(0, MAX));
  searchTree(x);
 
   let endSearchTime = new Date().getTime();
  
  console.log("Total search time: " + (endSearchTime - endBuildTime));
 
}

function searchTree(x) {
  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)   AB.msg('not found', 2);
  else                  AB.msg('found', 2);

  return result ? true : false;
}


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


// 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 )  { /*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 ) { /*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) { /*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 ("gray");
  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(24);
  textFont("times");
  text ( this.value, this.x,  this.y + (ellipse_size/6) );

  // Go right
  if (this.right) { /*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) 
    {
        //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) 
    {
     //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);
    }
  }
};



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

// 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) 
  {
    //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);
}