// Carnegie Mellon University
//   Information Networking Institute and
//   School of Computer Science
//
// Master Thesis: A Monitoring Tool for Overlay Network
// By: TungFai Chan and Annie Cheng
//
// File: IntermediateNode.java
// Path: eventbase/btree
// Description: Defines the intermedate nodes

package eventbase.btree;

public class IntermediateNode extends TreeNode{

  private TreeNode leftChild;
  private boolean root;

  public IntermediateNode() {
    nodeType = INTERMEDIATE;
    leftChild = null;
    count = 0;
    root = false;
    recordArray = new IntermediateNodeRecord[NUMRECORD];
    for (int i = 0; i < this.NUMRECORD; i++) {
      this.recordArray[i] = new IntermediateNodeRecord();
    }
  }

  // Different from split operation in leaf node
  // first d key values and d+1 nodepointers stay
  // last d keys and d+1 pointers move to new node, N2;
  // leave the middle node to be pull up in old node [degree]
  public TreeNode split(TreeNodeRecord r) {
    int index = findIndexToInsert(r.getKey());
    IntermediateNode retVal = new IntermediateNode();
    int curIndex = degree-1;
    int i = NUMRECORD - 1;
    boolean newNodeCopied = false;
    // move half of the entries over to the new place
    while (curIndex >= 0) {
      if (index == i+1 && !newNodeCopied) {
        retVal.recordArray[curIndex].copy(r);
        i++;
        newNodeCopied = true;
        curIndex--;
      } else {
        retVal.recordArray[curIndex].copy(this.recordArray[i]);
        this.recordArray[i].clearRecord();
        this.count--;
        curIndex--;
      }
      i--;
      retVal.count++;
    }

    // insert the entry after split
    if (i == degree) { // new record already added to the new node
      // do nothing
    }else if (index == degree) { // new node is the one get pull up
      this.recordArray[degree].copy(r);
      this.count++;
    }else { // new record need to be added to old node
      this.addEntry(r);
    }

    // prepare for push up
    // push up node is always the node resite in this.recordArray[degree]
    // 1. set the left child of new splited node to point to the push-up node's
    //    right child
    // 2. set the push up node's right child to the newly split node
    retVal.setLeftChild(((IntermediateNodeRecord)this.recordArray[degree]).getRightChild());
    ((IntermediateNodeRecord)this.recordArray[degree]).setRightChild(retVal);
    return retVal;
  }

  // always push the degree key up
  public double pushUpKey() {
    double retVal = this.recordArray[degree].getKey();
    this.recordArray[degree].clearRecord();
    this.count--;
    return retVal;
  }

  // Choose subtree that qualify the following condition:
  //    find i such that Ki <= Entry's key value < Ki+1
  public TreeNode findSubTree(double key) {
    // When a tree is empty, just return the left child pointer -point to
    // an empty leaf node
    if (isEmptyTree() || key < recordArray[0].getKey())
      return leftChild;
    for (int i = 0; i < count - 1; i++) {
      if (recordArray[i].isEmpty() || recordArray[i+1].isEmpty())
        System.err.println("LOGIC ERROR: B+Tree findSubTree");
      if (recordArray[i].getKey() <= key && recordArray[i+1].getKey() > key)
        return ((IntermediateNodeRecord)recordArray[i]).getRightChild();
    }
    // return the right most child
    if (recordArray[count-1].isEmpty())
      System.err.println("Logic ERROR: B+ Tree findSubTree");
    if (recordArray[count-1].getKey() <= key)
      return ((IntermediateNodeRecord)recordArray[count-1]).getRightChild();
    return null;
  }

  private void setRoot() {
    root = true;
  }

  public boolean isRoot() {
    return root;
  }

  public void clearRoot() {
    root = false;
  }

  private void setLeftChild(TreeNode node) {
    this.leftChild = node;
  }

  public void createEmptyTree() {
    TreeNode firstChild = new LeafNode();
    setLeftChild(firstChild);
    this.setRoot();
  }

  public void createNewRoot (TreeNode leftNode, IntermediateNodeRecord entry) {
    this.setLeftChild(leftNode);
    if (entry != null) {
      this.recordArray[0].copy(entry);
      count++;
    }
    this.setRoot();
  }

  // when return ture, indicates the tree is an empty tree
  public boolean isEmptyTree() {
    return (count == 0);
  }

  public TreeNode getLeftChild() {
    return this.leftChild;
  }
}