// 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: TreeNode.java
// Path: eventbase/btree
// Description: Base class for B+ Tree Node

package eventbase.btree;

public abstract class TreeNode {

  protected int nodeType;
  protected int count;
  protected TreeNodeRecord recordArray[];

  // NodeType
  public static final int UNDEFINED = -1;
  public static final int INTERMEDIATE = 0;
  public static final int LEAF = 1;
  public static final int NUMRECORD = 32;
  public static final int degree = NUMRECORD/2; // NUMRECORD/2

  public TreeNode() {
    nodeType = UNDEFINED;
    count = -1;
  }

  public int getType() {
    return nodeType;
  }

  public boolean isLeaf() {
    return nodeType == LEAF;
  }

  public boolean hasSpace() {
    return (count < NUMRECORD);
  }

  public void addEntry(TreeNodeRecord record) {
    double key = record.getKey();
    int shiftFrom = findIndexToInsert(key);
    // error checking
    if (shiftFrom > count || shiftFrom == -1) {
      System.err.println("ERROR (LeafNode:AddEntry): index not found!!");
      return;
    }
    // if the record is to be inserted as last entry, no shift is needed
    if (shiftFrom < count) { // all member needs to shift right at "shiftFrom" index
      shiftMembersRight(shiftFrom);
    }
    recordArray[shiftFrom].copy(record);
    count++;
  }

  // return index where the new item should be at
  protected int findIndexToInsert (double key) {
    int index = -1;
    // search for the right place to put the entry
    if (count == 0 || key < recordArray[0].getKey()) { // key < smallest member in the list
      index = 0;
    } else {
      for (int i = 0; i < count - 1; i++) {
        // <= and >= handles duplicates
        if (recordArray[i].getKey() <= key && key < recordArray[i + 1].getKey())
          index = i + 1;
      }
    }

    // must be because key is greater than last item in list
    if (index == -1 &&
        recordArray[count-1].getKey() <= key)
      index = count; // place at the end
    return index;
  }

  // Shifting all members to the right from position (startPos)
  private void shiftMembersRight(int startPos) {
      int index = count;
      while (index > startPos) {
        recordArray[index].copy(recordArray[index -1]);
        index--;
      }
  }

  public void printContent() {
    if (isLeaf())
      System.out.print("Leaf Page ( ");
    else
      System.out.print("Intermediate Page ( ");
    for (int i = 0; i < count; i++) {
      System.out.print(recordArray[i].getKey() + " ");
    }
    System.out.println(")");
  }

  // returns reference to the newly splited treenode
  abstract public TreeNode split(TreeNodeRecord record);
}