// 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: btree.java
// Path: eventbase/btree
// Description: B+ tree implementation

package eventbase.btree;

public class BTree {

  private LeafNode recordIterator;
  private IntermediateNode root;
  private LeafNode leafIterator;

  public BTree() {
    // makeBasicTree
    root = new IntermediateNode();
    root.createEmptyTree();
    leafIterator = null;
  }

  // Inserts entry into subtree rooted at 'nodepointer' of a B+ tree of
  // degree d; 'newchildentry' is null upon return unless child is split
  public void Insert(TreeNode nodePtr, LeafNodeRecord entry,
                     IntermediateNodeRecord newChildEntry) {
    if (nodePtr.isLeaf()) {
      if (nodePtr.hasSpace()) {
        nodePtr.addEntry(entry);
        newChildEntry.clearRecord();
      } else {
        double firstKey;
        TreeNode newLeaf = nodePtr.split(null);
        // find to insert entry in old node or new node
        firstKey = ((LeafNode)newLeaf).getFirstRecord().getKey();
        if (entry.getKey() < firstKey) // insert in old node
          nodePtr.addEntry(entry);
        else  // insert in new node
          newLeaf.addEntry(entry);
        // shouldn't need to get first Key again becuase entry's key
        // is greater than or equal to the first key of new node
        newChildEntry.setRecord(firstKey, newLeaf);
      }
      return;
    }

    if (!nodePtr.isLeaf()) {
      TreeNode subTree = ((IntermediateNode)nodePtr).findSubTree(entry.getKey());
      if (subTree == null) {
        System.err.println ("ERROR: BTREE:Insert()");
        System.err.println ("       SubTree not found Insert FAILED !!!!!");
        return;
      }
      Insert(subTree, entry,  newChildEntry);
      if (newChildEntry.isEmpty())
        return;
      else {  // we split child, must insert newchildentry in Intermediate nodePtr
        if (nodePtr.hasSpace()) {
          // put newChildEntry in it
          nodePtr.addEntry(newChildEntry);
          // important to set to null
          newChildEntry.clearRecord();
          return;
        } else { // note difference with splitting of leaf pages!
          TreeNode newIntermediate = nodePtr.split(newChildEntry);
          newChildEntry.setRecord(((IntermediateNode)nodePtr).pushUpKey(),
                                    newIntermediate);

          if (((IntermediateNode)nodePtr).isRoot()) {
            IntermediateNode newRoot = new IntermediateNode();
            newRoot.createNewRoot(nodePtr, newChildEntry);
            ((IntermediateNode)nodePtr).clearRoot();
            root = newRoot;
          }
        }
      }
    }
  }

  public IntermediateNode getRoot() {
    return root;
  }

  public void printTree(TreeNode nodePtr) {
    if (nodePtr.isLeaf()) {
      nodePtr.printContent();
      return;
    } else { // intermediate node
      printTree(((IntermediateNode)nodePtr).getLeftChild());
      for (int i = 0; i < nodePtr.count; i++) {
        printTree(((IntermediateNodeRecord)nodePtr.recordArray[i]).getRightChild());
        System.out.println("Finishing index(" + i + ")");
      }
      nodePtr.printContent();
    }
  }

  // return to you the leaf tree node where the value should resite on
  // of course, the exact value may not be found there
  private TreeNode treeSearch(TreeNode nodePtr, double key) {
    if (nodePtr.isLeaf())
      return nodePtr;
    else {
      TreeNode subTree = ((IntermediateNode)nodePtr).findSubTree(key);
      return treeSearch(subTree, key);
    }
  }

  // return the node that contains <pgno, rid> pair
  // this search for exact match, if no exact match has been found
  // return null;
  public LeafNodeRecord getRID (double key) {
    LeafNode nodePtr = (LeafNode) treeSearch(root, key);
    LeafNodeRecord retVal = null;
    if (nodePtr != null)
      retVal = nodePtr.getRecord(key);
    return retVal;
  }

  // set the iteration pointer at a correct spot for traversing purpose.
  public void setIterationPointer (double key) {
      //    printTree(root);
    this.leafIterator = (LeafNode) treeSearch(root, key);
    //    System.out.println("**************************** key " + key);
    this.leafIterator.getNextRecordInit(key);
    this.handle_duplicate();
  }

  public LeafNodeRecord getPrevRID() {
    // already used up all prevs in this leaf node, move leafIterator backword
    // and try again
    LeafNodeRecord retVal = this.leafIterator.getPrevRecord();
    if (retVal == null) {
      if (this.leafIterator.prev == null)
        return null;  // no more
      leafIterator = leafIterator.prev;
      leafIterator.setIteratorToLastRecord();
      retVal = this.leafIterator.getPrevRecord();
    }
    return retVal;
  }

  public LeafNodeRecord getNextRID() {
    LeafNodeRecord retVal = this.leafIterator.getNextRecord();
    if (retVal == null) {
      if (this.leafIterator.next == null)
        return null;
      this.leafIterator = leafIterator.next;
      this.leafIterator.setIteratorToFirstRecord();
      retVal = this.leafIterator.getNextRecord();
    }
    return retVal;
  }

  // when there is duplicate, the getIteratorIndex()
  // returns at the last element of duplicated value
  // so for example, if we are search for 15 for backword
  // (14, 15, 15, 15), the iterator stop at the 3rd 15
  // but for backword we just want 14, so we need to get rid of 3 15s
  // and for forward,  we want to have all 3 15s.
  // so we need to move getIteratorIndex backword
  private void handle_duplicate() {
    int index = this.leafIterator.getIteratorIndex();
    if (index == -1) // ahcheng: empty tree 09/02 bug fix
      return;
    LeafNodeRecord prevRecord;
    LeafNodeRecord thisRecord;
    if (index >= this.leafIterator.count) {// at last element of this node
      if (this.leafIterator.next == null) // no more record in tree
        return;
      thisRecord = this.leafIterator.next.getFirstRecord();
      prevRecord = (LeafNodeRecord) this.leafIterator.recordArray[index-1];
    } else {
      thisRecord = (LeafNodeRecord) this.leafIterator.recordArray[index];
      if (index == 0) {// find previous entry
        if (this.leafIterator.prev == null)
          return; // first entry in the tree
        prevRecord = this.leafIterator.prev.getLastRecord();
      } else
        prevRecord = (LeafNodeRecord) this.leafIterator.recordArray[index-1];
    }
    if (prevRecord.getKey() == thisRecord.getKey()) { // duplicate found
     double keyToGetRid = prevRecord.getKey();
     LeafNodeRecord temp;
     while (((temp = this.getPrevRID()) != null) && temp.getKey() == keyToGetRid);
     this.getNextRID();
    }
  }

  /* MEMO 08/17
     Implementation now assume that insertion most of time always happen at
     the very end of leafNodes list.  As a result, we assume that the iterator
     will not be moved because of the insertion.  The BTree manager will hold up
     the user with a few second delay so that the iterator will never goto
     the unstable zone.
  */
}