// noprotect

/*
  Tree constructor definition
*/
let Node = function() {
  //key of the node
  this.key = null;
  //value of the node
  this.value = null;
  //the index of the parent node in the nodeCache
  this.parent = null;
  //the index of the left node in the nodeCache
  this.left = null;
  //the index of the right node in the nodeCache
  this.right = null;
  //its own index in the nodeCache
  this.index = null;
};

Node.prototype.setLeftNode = function(node) {
  this.left = node.getIndex();
};

Node.prototype.setRightNode = function(node) {
  this.right = node.getIndex();
};

Node.prototype.getLeftNode = function(node) {
  return this.left;
};

Node.prototype.getRightNode = function(node) {
  return this.right;
};

Node.prototype.setValue = function(value) {
  this.value = value;
};

Node.prototype.getValue = function() {
  return this.value;
};

Node.prototype.setParentNode = function(node) {
  if (node) {
    this.parent = node.getIndex();
  }
};

Node.prototype.getParentNode = function() {
  return this.parent;
};

Node.prototype.setIndex = function(index) {
  this.index = index;
};

Node.prototype.getIndex = function() {
  return this.index;
};

Node.prototype.setKey = function(key) {
  this.key = key;
};

Node.prototype.getKey = function() {
  return this.key;
};
/*
  Binary search tree data strucutre implementation
*/
let BsTree = function(rootElm) {
  let nodeCache = [];
  let depth = 0;
  let self = this;
  let root = null;
  let init = function(rootElm) {
    root = new Node();
    root.setParentNode(null);
    root.setKey(rootElm.key);
    root.setValue(rootElm.value);
    nodeCache.push(root);
    root.setIndex(0);
  };

  let _appendNode = function(node, nodeToAppend) {
    let value = node.getValue();
    let current = nodeToAppend.getValue();
    if (current >= value) {
    let right = node.getRightNode();
    if (right !== null) {
      _appendNode(nodeCache[right], nodeToAppend);
    } else {
        nodeToAppend.setParentNode(node);
        node.setRightNode(nodeToAppend);
        node.rightNode = nodeToAppend;
        //hack to get depth of the tree
        if (node.getLeftNode() === null) {
          depth++;
        }
      }
    } else if (current < value) {
      let left = node.getLeftNode();
      if (left !== null) {
        _appendNode(nodeCache[left], nodeToAppend);
      } else {
        nodeToAppend.setParentNode(node);
        node.setLeftNode(nodeToAppend);
        node.leftNode = nodeToAppend;
        //hack to get depth of the tree
        if (node.getRightNode() === null) {
          depth++;
        }
      }
    }
  };

  let _getValue = function(node, givenValue) {
    if (node) {
      let key = node.getKey();
      let value = node.getValue();
      let leftNode = nodeCache[node.getLeftNode()];
      let rightNode = nodeCache[node.getRightNode()];
      if (givenValue === value) {
        return node;
      } else if (givenValue > value) {
        return _getValue(rightNode, givenValue);
      } else if (givenValue < value) {
        return _getValue(leftNode, givenValue);
      }
    } else {
      return null;
    }
  };

  this.createNode = function(obj) {
    let node = new Node();
    node.setKey(obj.key);
    node.setValue(obj.value);
    return node;
  };

  this.appendNode = function(data) {
    let node = this.createNode(data);
    node.setIndex(nodeCache.length);
    nodeCache.push(node);
    _appendNode(root, node);
  };

  this.createTree = function(data) {
    for(let i = 1; i < data.length; i++) {
      let obj = data[i];
      let node = new Node();
      node.setKey(obj.key);
      node.setValue(obj.value);
      node.setIndex(nodeCache.length);
      nodeCache.push(node);
      _appendNode(root, node);
    };
  };

  this.getNode = function(value) {
     return _getValue(root, value);
  };

  //TODO
  this.deleteNode = function(value) {

  };

  this.getNodeCache = function() {
    return nodeCache;
  };

  this.getDepth = function() {
    return depth;
  };

  init(rootElm);
};


/*
  create a sample data which can be
  used to construct a binary tree DS
*/
let setSampleData = function(noOfExamples) {
  const sampleDataset = [];
  for(let i = 0; i < noOfExamples; i++) {
    sampleDataset.push({
      // here key contains the metadata
      key: Math.random(),
      value: Math.random()
    });
  }
  return sampleDataset;
};

//create sample data set
const data = setSampleData(5);
let bsTree = new BsTree(data[0]);
const start = performance.now();
bsTree.createTree(data);
const end = performance.now();

const nodeCache = bsTree.getNodeCache();
const depth = bsTree.getDepth();
// since the tree is constructed via `value`
const node = bsTree.getNode(nodeCache[2].getValue());
console.log(nodeCache);
console.log(node);
console.log(depth);
console.log("time taken: " + (end - start));