// canvas size 
const cw = 1000;
const ch = 1000;
   
const root_x = cw / 2;
const root_y = ch / 10;
const ellipse_size = cw / 25;

// range of numbers
const MAX = 100;

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

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

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

function setup() {
  createCanvas(cw,ch);        
  // New tree
  var tree = new Tree();

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

  background("white");

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

}