/afs/cs.wisc.edu/u/n/w/nwilliam/private/workspace/Quut/src/btree.cpp

#include "btree.h"
#include "filescan.h"
#include "exceptions/bad_index_info_exception.h"
#include "exceptions/bad_opcodes_exception.h"
#include "exceptions/bad_scanrange_exception.h"
#include "exceptions/no_such_key_found_exception.h"
#include "exceptions/scan_not_initialized_exception.h"
#include "exceptions/index_scan_completed_exception.h"
#include "exceptions/file_not_found_exception.h"
#include "exceptions/end_of_file_exception.h"
#include "exceptions/page_not_pinned_exception.h"


//#define DEBUG

namespace badgerdb
{
// -----------------------------------------------------------------------------
// BTreeIndex::fillLeafNodes 
// -----------------------------------------------------------------------------
template <class T>
int BTreeIndex::fillLeafNodes( 
    std::deque< PageKeyPair< T > > &thisLevelNodes,
    std::deque< RIDKeyPair< T > > &dataList)
{
  bool firstPage = true;
  PageKeyPair< T > tempPair;
  PageId pageNo = 0;
  PageId lastPageNo=0;
  Page* currentPage = NULL;
  Page* lastPage = NULL;
  int currentPageIndex = 0;
  
  //while there are elements on list
  while( dataList.size() != 0 )
  {
    //allocate a page if no space left on current page and then put 1st value and page number into list
    if( currentPage == NULL || currentPageIndex >= (leafOccupancy+1)/2 )
    {
      //save the value of the last page allocated so that its right sib
      //ptr can be set once we allocate this new page
      lastPageNo = pageNo;
      lastPage = currentPage;
      //allocate a new page
      bufMgr->allocPage( file, pageNo, currentPage );

      zeroOutLeaf(currentPage);
      //can only set the right sib ptr once the second page has been 
      //allocated. so skip the first time
      if( !firstPage)
      {
        copySibPtr( pageNo, lastPage );
        bufMgr->unPinPage( file, lastPageNo, true);
      }
      currentPageIndex = 0;
      //so entries in thisLevelNodes have keys corresponding to first entries in leaf nodes
      tempPair.set( pageNo, dataList.front().key ); 
      thisLevelNodes.push_back( tempPair );
    }
    #ifdef DEBUG
      std::cout << "Adding data: " << dataList.front().key << " to page " << pageNo << std::endl;
    #endif
    
    // put the values into the page
    copyKey<T>( dataList.front().key, currentPage, currentPageIndex, true);
    copyRid( dataList.front().rid, currentPage, currentPageIndex);
    firstPage = false;
    
    //delete data off of list
    dataList.pop_front();
    currentPageIndex++;
  }
  //set the right sib ptr of the last page allocated to 0
  if( currentPage!= NULL ) copySibPtr( 0, currentPage );
  if( currentPage!= NULL ) bufMgr->unPinPage( file, pageNo, true);
  return pageNo;
}

// -----------------------------------------------------------------------------
// BTreeIndex::fillNonLeafNodes
// -----------------------------------------------------------------------------
template <class T>
int BTreeIndex::fillNonLeafNodes( 
  std::deque< PageKeyPair< T > > &thisLevelNodes,
  std::deque< PageKeyPair< T > > &lastLevelNodes,
  const int level)
{
  PageKeyPair< T > tempPair;
  PageId pageNo;
  PageId lastPageNo;
  Page* currentPage = NULL;
  int currentPageIndex = 0;
  bool firstPage = true;
  
  //while there are elements on list
  while( lastLevelNodes.size() != 0 )
  {
    //allocate a page if no space left on current page and then put 1st value and page number into list
    if( currentPage == NULL || currentPageIndex >= (nodeOccupancy+1)/2 )
    {
      lastPageNo = pageNo;
      bufMgr->allocPage( file, pageNo, currentPage );
      zeroOutNonLeaf(currentPage);
      if( !firstPage) 
      {
        bufMgr->unPinPage( file, lastPageNo, true);
      }     
      currentPageIndex = 0;
      tempPair.set( pageNo, lastLevelNodes.front().key ) ;
      thisLevelNodes.push_back( tempPair );
      //first entry is just the pageno, key corresponding to it is passed to the parent page, 
      //so first page has keys greater than or equal to parent's key for this page
      copyPageNo( lastLevelNodes.front().pageNo, currentPage, 0 );
      copyLevel( level, currentPage );
      #ifdef DEBUG
        std::cout << "Creating Page # " << pageNo << std::endl;
      #endif
    }
    // Otherwise, copy key as well
    else
    {
      copyPageNo( lastLevelNodes.front().pageNo, currentPage, currentPageIndex );
      //NOTE -1 BELOW 
      copyKey( lastLevelNodes.front().key, currentPage, currentPageIndex-1, false );
    }
    //delete data off of list
    #ifdef DEBUG
      std::cout << "Adding data: " << lastLevelNodes.front().key << " that points to Page: " 
      << lastLevelNodes.front().pageNo << std::endl;
    #endif
    lastLevelNodes.pop_front();
    currentPageIndex++;
    firstPage = false;
  }
  if( currentPage!= NULL ) bufMgr->unPinPage( file, pageNo, true);
  return pageNo;
}

// -----------------------------------------------------------------------------
// BTreeIndex::BtreeTemplateConstructor
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::BTreeTemplateConstructor(const std::string & relationName,
    std::string & outIndexName,
    const int attrByteOffset,
    const Datatype attrType)
{
  Page* metap;
  IndexMetaInfo* metaPage;
  scanExecuting = false;

  #ifdef DEBUG
    std::cout << "Initializing constructor" << std::endl;
  #endif
  // Set Class values
  switch( attrType ){
    case INTEGER:
      leafOccupancy = INTARRAYLEAFSIZE; 
      nodeOccupancy = INTARRAYNONLEAFSIZE; 
      break;
    case DOUBLE:
      leafOccupancy = DOUBLEARRAYLEAFSIZE; 
      nodeOccupancy = DOUBLEARRAYNONLEAFSIZE; 
      break;
    case STRING:
      leafOccupancy = STRINGARRAYLEAFSIZE; 
      nodeOccupancy = STRINGARRAYNONLEAFSIZE; 
      break;
    default: break;
  }
  attributeType = attrType;
  
  //create indexfile name
  std::ostringstream idxStr;
  idxStr << relationName << '.' << attrByteOffset;
  outIndexName = idxStr.str(); // indexName is the name of the index file

  //check to see if the indexfile already exists and if so open it
  //Sandeep::TODO delete file when done
  file = 0;
  try
  {
    file = new BlobFile(outIndexName, false/*open*/); //open file

    //if the file opened successfully return from constructor
    bufMgr->readPage( file, 1, metap);
    metaPage = (IndexMetaInfo*) metap;

    //check to make sure that the relationname input matches the relation
    //name stored in the metapage for the index
    if( strncmp(metaPage->relationName, relationName.c_str(), 20) )
    {
      throw BadIndexInfoException("Index relation name doesn't match parameters");
    }
    //check the attrByteOffset input with the one stored for the key value 
    //for which the tree was created.
    else if( metaPage->attrByteOffset != attrByteOffset )
    {
      throw BadIndexInfoException("Index attrByteOffset doesn't match parameters");
    }
    //make sure the types match
    else if( metaPage->attrType != attrType )
    {
      throw BadIndexInfoException("Index attribute type doesn't match parameters");
    }
    else
    {
      //if the index was openned and is indeed for this relation
      //store the value of the rootpageno so that the tree can be 
      //searched and inserted into
      rootPageNum = metaPage->rootPageNo;
    }

    bufMgr->unPinPage( file, 1, false);
    return;
  }
  catch(FileNotFoundException e)
  {
  }

  //if the file did not open create a file and store the index
  #ifdef DEBUG
    std::cout << "File " << outIndexName << " does not exist." << std::endl;
  #endif

  file = new BlobFile(outIndexName, true/*create*/);  //create file

  //scan the heap file for all records and store the <index key,rid>
  //in an array 
  FileScan fileScan(relationName, bufMgr);
  
  RecordId currentRID;
  std::string currentRecord;
  
  std::deque< RIDKeyPair< T > > dataList;

  try
  {
    while(1)
    {
      fileScan.scanNext(currentRID);
      currentRecord = fileScan.getRecord();
      dataList.push_back( copyRecordToRidKeyPair<T>( currentRecord, currentRID, attrByteOffset) );
    }
  }
  catch(EndOfFileException e)
  {
    //THIS IS EXPECTED
    //if an error occured and we didnt reach the end of the file 
    //delete file;  //this will call the file destructor and close the file
    //file = 0;
    //File::remove(outIndexName);
    //return;
  }

  //sort the datalist deque 
  sort(dataList.begin(), dataList.end());
  if(dataList.size() == 0)
  {
    bufMgr->flushFile(file);
    delete file;  //this will call the file destructor and close the file
    file = 0;
    File::remove(outIndexName);
    return;
  } 

  PageId pageNo = 0;
  //allocate a page for the meta information - will always be page 1
  bufMgr->allocPage( file, pageNo, metap );
  metaPage = (IndexMetaInfo*)(metap);
  headerPageNum = pageNo;
  PageId nextLevelNode = 1;
  
  //when creating a level each value not placed into node is placed into
  //this deqeu and then once the current level is created this deque becomes
  //lastlevelnodes and is used to create the next level
  std::deque< PageKeyPair< T > > thisLevelNodes;
  //contains the values that will be used to create a level above the last level created
  std::deque< PageKeyPair< T > > lastLevelNodes;
  #ifdef DEBUG
    std::cout << "Filling Leaf Nodes" << std::endl;
  #endif
  pageNo = fillLeafNodes( lastLevelNodes, dataList);
  //Create all non-root nodes
  //keeps creating levels of the tree till we dont reach a point where
  // the lastLevelNodes only has enough entries to make one node
  //for the next level as that means that level is the root and we done.
  while( lastLevelNodes.size() > static_cast<unsigned int>((nodeOccupancy+1)/2) )
  {
    fillNonLeafNodes<T>( thisLevelNodes, lastLevelNodes, nextLevelNode);
    lastLevelNodes = thisLevelNodes;
    thisLevelNodes.clear();
    nextLevelNode = 0;
  }
  
  // Create root node
  rootPageNum = fillNonLeafNodes<T>( thisLevelNodes, lastLevelNodes, nextLevelNode);
  // assign pageNo and other information to metapage
  strncpy( metaPage->relationName, relationName.c_str(), 20);
  metaPage->attrByteOffset = attrByteOffset;
  metaPage->attrType = attrType;
  metaPage->rootPageNo = rootPageNum;
  bufMgr->unPinPage( file, headerPageNum, true);
  //printTreeExternal();
}

// -----------------------------------------------------------------------------
// BTreeIndex::BTreeIndex -- Constructor
// -----------------------------------------------------------------------------
BTreeIndex::BTreeIndex(const std::string & relationName,
    std::string & outIndexName,
    BufMgr *bufMgrIn,
    const int attrByteOffset,
    const Datatype attrType)
{
  bufMgr = bufMgrIn;
  //call the appropriate templated version of the BtreeTemplateConstructor based
  //on the attr type
  switch( attrType ){
    case INTEGER:
      BTreeTemplateConstructor< int >(relationName, outIndexName, attrByteOffset, attrType);
      break;
    case DOUBLE:
      BTreeTemplateConstructor< double >(relationName, outIndexName, attrByteOffset, attrType);
      break;
    case STRING:
      BTreeTemplateConstructor< std::string >(relationName, outIndexName, attrByteOffset, attrType);
      break;
    default:
      // Print Error
      break;
  }
}


// -----------------------------------------------------------------------------
// BTreeIndex::~BTreeIndex -- destructor
// -----------------------------------------------------------------------------

BTreeIndex::~BTreeIndex()
{
  if( scanExecuting )
  {
    try
    {
      endScan();
    }
    catch(ScanNotInitializedException e)
    {
    }
  }

  if(file)
    bufMgr->flushFile(file);

  delete file;
}

// -----------------------------------------------------------------------------
// BTreeIndex::insertEntry
// -----------------------------------------------------------------------------

const void BTreeIndex::insertEntry(const void *value, const RecordId rid) 
{
  //helps keep track of what level of the tree we are at during the 
  //execution of insertEntry
  //if the value at the top of the stack is 1 we know that we are handling
  //leaf nodes. otherwise we handling non leaf nodes.
  std::stack<int> treePath;
  RecordId ridValue = rid;
  
  #ifdef DEBUG
      std::cout<<"*******************************************"<<std::endl;
      std::cout << "Root Page Number: " << rootPageNum <<std::endl;
  #endif
  
  //call the templated insertEntry function with values based on the type
  //of tree we are working with here
  if(attributeType == INTEGER)
  {
    #ifdef DEBUG
      std::cout <<" Inserting integer"<<std::endl;
    #endif
    int key = *((int*)value);
    PageKeyPair<int> newPageKeyPair;
    //pageNo for this dummy newPageKeyPair will be set to 0 in insertInto as necessary, might be safe doing that in the constructor
    insertInto<int>(rootPageNum, key, newPageKeyPair, 
                              ridValue, treePath);
  }
  if(attributeType == DOUBLE)
  {
    #ifdef DEBUG
      std::cout <<" Inserting double"<<std::endl;
    #endif
    double key = *((double*)value);
    PageKeyPair<double> newPageKeyPair; 
    insertInto<double>(rootPageNum, key, newPageKeyPair, 
                            ridValue, treePath);
  }
  if(attributeType == STRING)
  {
    #ifdef DEBUG
      std::cout <<" Inserting string"<<std::endl;
    #endif
    std::string key;
    for(int i=0; i<10; i++)
      key+= *( ((char*)value)+i );
       
    PageKeyPair<std::string> newPageKeyPair;  
    insertInto<std::string>(rootPageNum, key, newPageKeyPair, 
                              ridValue, treePath);
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::startScan
// -----------------------------------------------------------------------------
const void BTreeIndex::startScan(const void* lowValParm,
           const Operator lowOpParm,
           const void* highValParm,
           const Operator highOpParm)
{
  //make sure that there's no current scan.  If there is, end it. 
  if( scanExecuting )
    endScan();
  //check to make sure the op values are used the correct way for ranges
  if( ( lowOpParm != GT && lowOpParm != GTE ) || ( highOpParm != LT && highOpParm != LTE ) )
    throw BadOpcodesException();

  // Set member variables for scan
  lowOp = lowOpParm;
  highOp = highOpParm;

  //set to root before scan starts
  currentPageNum = rootPageNum;

  switch( attributeType ){
    case INTEGER:
      setHighLowVal<int>(highValParm, true);
      setHighLowVal<int>(lowValParm, false);
      templateStartScan<int>();
      return;
      break;
    case DOUBLE:
      setHighLowVal<double>(highValParm, true);
      setHighLowVal<double>(lowValParm, false);
      templateStartScan<double>();
      return;
      break;
    case STRING:
      setHighLowVal<std::string>(highValParm, true);
      setHighLowVal<std::string>(lowValParm, false);
      templateStartScan<std::string>();
      return;
      break;
    default: break;
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::templateStartScan
// -----------------------------------------------------------------------------

template <class T>
const void BTreeIndex::templateStartScan()
{
  #ifdef DEBUG
    std::cout << "Begin: Start Scan." << std::endl
    << "Low = " << getHighLowVal<T>( false ) << " High = " << getHighLowVal<T>( true ) << std::endl;
  #endif
  // set local variables
  int nextLevelLeaf = 0;
  PageId lastPageNum;
  nextEntry = 0;
  RecordId tempRid;
  T tempKey;
  PageId tempPageNo;
  
  //make sure the upper bound specified is greater than the lower bound specified
  if( getHighLowVal<T>( false ) > getHighLowVal<T>( true ) )
    throw BadScanrangeException();

  scanExecuting = true;

  //go down the tree along the appropriate path based on the lower bound value input
  //loop goes through all the non leaf nodes in the path 
  do
  {
    #ifdef DEBUG
      std::cout << "Searching Node" << std::endl;
    #endif
    //read page for node in path
    bufMgr->readPage( file, currentPageNum, currentPageData );

    //get the level so that we only go upto the last non leaf level
    extractLevel( nextLevelLeaf, currentPageData );
    lastPageNum = currentPageNum;
    //figure out next node to go to in the path
    currentPageNum = findPageNoInNonLeaf( currentPageData, getHighLowVal<T>( false ) ); 
    bufMgr->unPinPage( file, lastPageNum, false );
  }while( nextLevelLeaf != 1 );

  // currentPageNum is now a leaf
  bufMgr->readPage( file, currentPageNum, currentPageData );
  nextEntry = 0;
  //figure out the first value for the scan
  while( extractKey<T>( tempKey, currentPageData, nextEntry, true ) < getHighLowVal<T>( false ) 
    && extractRid( tempRid, currentPageData, nextEntry ).page_number != 0
    && nextEntry < INTARRAYLEAFSIZE )
  {
    nextEntry++;
  }
  
  //if we went beyond the page this means the first value of the scan is the first value 
  //of the next page.
  //if there is no right sib it means the lower bound is the larger than all values in the index
  //???????????????? why so
  if( extractRid( tempRid, currentPageData, nextEntry ).page_number == 0 || nextEntry >= INTARRAYLEAFSIZE )
  {
    // If it is last entry of last page, return error
    if(extractSibPtr( tempPageNo, currentPageData) == 0)
    {
      bufMgr->unPinPage( file, currentPageNum, false );

      scanExecuting = false;
      throw NoSuchKeyFoundException();
    }
    else
    {
      //set next entry to the first entry of the right sib page
      lastPageNum = currentPageNum;
      currentPageNum = extractSibPtr( tempPageNo, currentPageData);
      bufMgr->unPinPage( file, lastPageNum, false );
      bufMgr->readPage( file, currentPageNum, currentPageData );
      nextEntry = 0;
    }
  }
  else
  {
    // If we wanted greater than and we are at an equal, move nextEntry over
    if( extractKey<T>( tempKey, currentPageData, nextEntry, true ) == getHighLowVal<T>( false ) 
      && lowOp == GT )
    {
    #ifdef DEBUG
      std::cout << "Shifting nextEntry" << std::endl;
    #endif
      try
      {
        scanNext(tempRid);
      }
      catch(IndexScanCompletedException e)
      {
        bufMgr->unPinPage( file, currentPageNum, false );
        scanExecuting = false;
        throw NoSuchKeyFoundException();
      }
    }
  }
  #ifdef DEBUG
    std::cout << "End: Start Scan" << std::endl;
  #endif
}

// -----------------------------------------------------------------------------
// BTreeIndex::scanNext
// -----------------------------------------------------------------------------
//throws and rethrows IndexScanCompletedException
const void BTreeIndex::scanNext(RecordId& outRid) 
{
  //check to make sure a scan is in progress
  if(!scanExecuting )
    throw ScanNotInitializedException();

  //to check if the scan is over
  if(nextEntry == -1)
    throw IndexScanCompletedException();
  
  //call templated function with the appropriate type   
  switch(attributeType){
    case INTEGER:
      templateScanNext<int>( outRid );
      return; 
      break;
    case DOUBLE:
      templateScanNext<double>( outRid );
      return;
      break;
    case STRING:
      templateScanNext<std::string>( outRid );
      return;
      break;
    default: break;
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::templateScanNext
// -----------------------------------------------------------------------------
template <class T>
const void BTreeIndex::templateScanNext(RecordId& outRid) 
{
  #ifdef DEBUG
    std::cout << "Begin: Scan Next" << std::endl;
  #endif
  
  PageId lastPageNum = 0;
  T tempKey;
  PageId tempPageNo;
  RecordId tempRid;
  
  // See if we've gone beyond range
  if( ( highOp == LTE && extractKey<T>( tempKey, currentPageData, nextEntry, true ) > getHighLowVal<T>(true) )
    || ( highOp == LT && extractKey<T>( tempKey, currentPageData, nextEntry, true ) >= getHighLowVal<T>(true) ) )
  {
    nextEntry = -1;
    throw IndexScanCompletedException();
  }
  
  //otherwise, set outRid and increment nextEntry
  #ifdef DEBUG
    std::cout << "key = " << extractKey<T>( tempKey, currentPageData, nextEntry, true ) << std::endl
    << "RID = " << extractRid( outRid, currentPageData, nextEntry).page_number << std::endl;
  #endif
  
  extractRid(outRid, currentPageData, nextEntry);
  nextEntry++;

  //see if we have to change the page
  if( nextEntry >= INTARRAYLEAFSIZE || extractRid( tempRid, currentPageData, nextEntry).page_number == 0 )
  {
    //if there is no right sib the scan has ended
    if( extractSibPtr( tempPageNo, currentPageData) == 0)
    {
      nextEntry = -1;
    }
    else
    {
      #ifdef DEBUG
        std::cout << "Moving to sibling page : " << extractSibPtr( tempPageNo, currentPageData ) << std::endl;
      #endif
      lastPageNum = currentPageNum;
      currentPageNum = extractSibPtr( tempPageNo, currentPageData);
      nextEntry = 0;
      bufMgr->readPage( file, currentPageNum, currentPageData ); 
      bufMgr->unPinPage( file, lastPageNum, false );
    }
  }
  #ifdef DEBUG
    std::cout << "End: Scan Next" << std::endl;
  #endif
}

// -----------------------------------------------------------------------------
// BTreeIndex::endScan
// -----------------------------------------------------------------------------
const void BTreeIndex::endScan() 
{
  //check to make sure there is a scan running 
  if( !scanExecuting )
    throw ScanNotInitializedException();

  bufMgr->unPinPage( file, currentPageNum, false );

  scanExecuting = false;
}

// -----------------------------------------------------------------------------
// BTreeIndex::insertInto
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::insertInto(PageId pageNo, T key, PageKeyPair<T> &newPageKeyPair, 
                              RecordId &rid, std::stack<int> &treePath)
{
  //this function will always be called with the pageNo set to 
  //the root page no to begin with and then subsequent recursive calls
  //will set the appropriate pageNo values depending on the path followed
  PageId tempPageNo;
  T tempKey;
  Page* currentNode;
  int level;
  bool isLeaf = false;  
  bool isRoot = false;
  
  //variable to figure out if a given node is full or not
  //if not full it indicated which index can be used next to add data
  //it represents the index in the pageNo array - NOT THE KEY ARRAY
  int lastIndexUsed = 0;
  
  //read the page in from the buffer manager
  bufMgr->readPage(file, pageNo, currentNode);
  
  #ifdef DEBUG
    std::cout << "InsertInto called on pageNo: " << pageNo <<std::endl;
  #endif
  
  //check to see if its a leaf node or non leaf node
  if( treePath.size() != 0 && treePath.top() == 1)
  {
    #ifdef DEBUG
      std::cout << "Recursive call has reached the leaf node level." <<std::endl;
    #endif
    isLeaf = true;
  }
  else
  {
    memcpy( &level, currentNode, sizeof(int) );
    treePath.push(level);
    #ifdef DEBUG
      std::cout << "Inserting level: " <<level<<" into the treePath stack" << std::endl;
    #endif    
  }
    
  //if node is a non leaf node
  if( !isLeaf )
  {
    #ifdef DEBUG
      std::cout << "Current level is a non leaf level" <<std::endl;
    #endif

    //find the next pageno to determine the path down the btree
    PageId nextPageNo = findPageNoInNonLeaf<T>( currentNode, key );
    
    #ifdef DEBUG
      std::cout << "Next page in path being followed is: " << nextPageNo << std::endl;
    #endif

    //call insert on the page number found above, the key input and
    //newPageNo)
    #ifdef DEBUG
      std::cout << "Making recursive call with for the above pageNo" <<std::endl;
    #endif

    insertInto<T>(nextPageNo, key, newPageKeyPair, rid, treePath);
    
    #ifdef DEBUG
      std::cout << std::endl << "Returning from recursive call for pageNo:" << nextPageNo <<std::endl;
    #endif

    /*if(status != OK )
    {
      #ifdef DEBUG
        std::cout << "Error occured on return from recursive call" <<endl;
      #endif
      //even though error has occured need to make sure we unpin the page
      //no change was made to this page, so hasnt been dirtied
      bufMgr->unPinPage(file, pageNo, 0);
      return;
    }*/

    //check if we have been through all the recursive calls and have reached the
    //the root
    if( treePath.size() == 1 )
    { 
      #ifdef DEBUG
        std::cout << "We have reached back to the root after going all the way down" <<std::endl;
      #endif
      isRoot = true;
    }

    treePath.pop();
      
    //on return from this recursive call check to see if a split occured
    //in the level below by checking the value of pageNo in newPageKeyPair
    //if newPageKeyPair.pageNo =0 then no split occured
    if( newPageKeyPair.pageNo == 0 )
    { 
      #ifdef DEBUG
        std::cout << "Lower level was not split" <<std::endl;
      #endif
      //no change was made to this page, so hasnt been dirtied
      bufMgr->unPinPage(file, pageNo, 0);
      return;
    }
    // else a split has occured 
  
    //check to see if there is space in this level to
    //accomadate the split and place the key in the parent node
    isNonLeafFull(currentNode, lastIndexUsed);
    if( lastIndexUsed < nodeOccupancy )
    {
      #ifdef DEBUG
        std::cout << "non leaf node is not full, inserting into the node" <<std::endl;
      #endif
      //there is place in the node to add the new key
      insertPageKeyPair<T>( currentNode, newPageKeyPair, lastIndexUsed );

      //set the newPageKeyPair.pageNo = 0 so that if no further split
      //the higher recursive calls dont think there are more splits
      newPageKeyPair.pageNo = 0;
      
      //change has been made to this page, so set dirty flag while unpinning
      bufMgr->unPinPage(file, pageNo, 1);
      return;
    }
    
    //the currentNode needs to be split due to lack of space to add new 
    //keypageno pair
    #ifdef DEBUG
      std::cout << "Need to split node, creating new node" <<std::endl;
    #endif
    //allocate a new page for the new node
    PageId newPageNo;
    Page *newNode;
    bufMgr->allocPage( file, newPageNo, newNode );  

    //set the level
    #ifdef DEBUG
      std::cout << "Setting the level of the new node to: " <<*(int*)currentNode<<std::endl;
    #endif

    //first item in all NonLeafNodeInt/Double/String structs is the level variable
    //it is just called a page* though its actually not pointing to object of Page class
    //or even though it is we are not using that Page as a Page object instead we are using that as a NonLeafNode pointer 
    //since its also of the same size as Page object but then calls to any method on these modified objects would fail?????
    *(int*)(newNode) = *(int*)currentNode;
    extractKey<T>(tempKey, currentNode , nodeOccupancy/2, false);
    
    #ifdef DEBUG
      std::cout << "Value being pushed up one level:" << tempKey << std::endl;
    #endif

    //put all the remaining elements of the node being split into new node
    splitNonLeafNode<T>(currentNode, newNode );

    //check to see if the key from lower level goes into old node or the new node created
    if( newPageKeyPair.key < tempKey )
    {
      #ifdef DEBUG
        std::cout <<" Inserting page no:"<<newPageKeyPair.key<<std::endl;
      #endif
      isNonLeafFull( currentNode, lastIndexUsed);
      insertPageKeyPair<T>( currentNode, newPageKeyPair, lastIndexUsed );
    }
    else
    {
      isNonLeafFull( newNode, lastIndexUsed);
      insertPageKeyPair<T>( newNode, newPageKeyPair, lastIndexUsed );
    }
    
    //set the newPageKeyPair.pageNo to the 
    //the new pageno that has been just allocated for the split
    newPageKeyPair.pageNo = newPageNo;
    newPageKeyPair.key = tempKey;
    
    //if the node that was just split was the root 
    if( isRoot )
    {
      #ifdef DEBUG
        std::cout << "splitting the root" <<std::endl;
      #endif

      //allocate a new page for the new root node
      PageId newRootPageNo;
      Page *newRootNode;
      bufMgr->allocPage( file, newRootPageNo, newRootNode );
      
      zeroOutNonLeaf(newRootNode);
      
      //set the level
      *(int*)(newRootNode) = 0;
    
      //set the p0 pointer to the pageno that was split
      copyPageNo(pageNo, newRootNode , 0);
      
      //set the key value to the element being pushed up to the new root
      copyKey<T>(tempKey, newRootNode , 0 , false);
      
      //set the p1 pointer to the the pageno of new node resulting from the split
      copyPageNo(newPageNo, newRootNode , 1);
      
      //update the meta information - need to decide when this is written back
      //to the meta information page !!!!
      /****************************************************************/
      rootPageNum = newRootPageNo;
      
      //change was made to this page, so has been dirtied
      bufMgr->unPinPage(file, newRootPageNo, 1);
      
      //dont return here as the only thing happening next is the unpinning and return of status
      //which is what would be done in the return here anyways
      
      Page* metaPage;
      bufMgr->readPage(file, 1, metaPage);
      ((IndexMetaInfo*)metaPage)->rootPageNo = rootPageNum;
      bufMgr->unPinPage(file, 1, 1);
    }
    //change was made to this page, so has been dirtied
    #ifdef DEBUG
      std::cout << "unpinning "<< pageNo<<std::endl;
    #endif
    bufMgr->unPinPage(file, pageNo, 1);
    //change was made to this page, so has been dirtied
    #ifdef DEBUG
      std::cout << "unpinning "<< newPageNo<<std::endl;
    #endif
    bufMgr->unPinPage(file, newPageNo, 1);
    return;
  }
      
  //HANDLE INSERTION INTO A LEAF NODE
  
  #ifdef DEBUG
    std::cout << "Handling leaf level" <<std::endl;
  #endif

  //make an ridkey pair
  RIDKeyPair<T> keyRidPair;
  keyRidPair.set( rid, key);
  
  isLeafFull(currentNode, lastIndexUsed);
  
  //check to see if there is place in the node to add the key value
  if( lastIndexUsed < leafOccupancy-1 )
  {
    #ifdef DEBUG
      std::cout << "Inserting into the leaf level node" <<std::endl;
    #endif

    insertKeyRidPair<T>( currentNode, keyRidPair, lastIndexUsed );
    newPageKeyPair.pageNo = 0;
    bufMgr->unPinPage(file, pageNo, 1);
    return;
  }
  
  //need to split the currentNode
  #ifdef DEBUG
    std::cout << "Splitting leaf level node" <<std::endl;
  #endif


  //create a new node
  PageId newPageNo;
  Page *newLeafNode;
  bufMgr->allocPage( file, newPageNo, newLeafNode );  
  
  //first split the the node and then figure out where the new keyRidPair should go
  
  //split the node
  splitLeafNode<T>( currentNode, newLeafNode, lastIndexUsed);
  
  //set the sibling pointer in the new node to the sibling pointer in the old
  //node and set the old nodes sibling pointer to this new node
  extractSibPtr( tempPageNo, currentNode);
  copySibPtr( tempPageNo, newLeafNode);
  copySibPtr( newPageNo, currentNode);
  
  //figure out which node , current or new node created is going to be used
  //to insert the new key value into by looking at the first value in the new node
  
  extractKey<T>(tempKey, newLeafNode , 0, true);
  if( keyRidPair.key < tempKey )
  {
    #ifdef DEBUG
      std::cout << "!!!placing into in old page" <<std::endl;
    #endif
    isLeafFull( currentNode,lastIndexUsed);
    insertKeyRidPair<T>( currentNode, keyRidPair, lastIndexUsed );
  }
  else
  {
    #ifdef DEBUG
      std::cout << "!!!placing into in new page" <<std::endl;
    #endif
    isLeafFull( newLeafNode,lastIndexUsed);
    insertKeyRidPair<T>( newLeafNode, keyRidPair, lastIndexUsed );
  } 
  
  #ifdef DEBUG
    std::cout <<"after insert"<<std::endl;
  #endif

  extractKey<T>(tempKey, newLeafNode , 0, true);
  newPageKeyPair.key = tempKey;
  newPageKeyPair.pageNo = newPageNo;
  
  bufMgr->unPinPage(file, pageNo, 1);
  bufMgr->unPinPage(file, newPageNo, 1);
  return;
}

// -----------------------------------------------------------------------------
// BTreeIndex::splitNonLeafNode
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::splitNonLeafNode(Page* currentNode, Page* newNode )
{
  int nonLeafNodeSize = nodeOccupancy;
  T tempKey;
  PageId tempPageNo;
  char zero[11] = "0000000000";
  //INTARRAYNONLEAFSIZE = 4
  //0   0   1   1   2   2   3   3   4
  //p0  k1  p1  k2  p2  k3  p3  k4  p4

  //copy the second half of the node being split ( minus the first element
  //that has been pushed up) in this new node
  
  //zero out the key at this index as it is the one being pushed up to
  //the non leaf level above the level at which this split is taking place
  if( attributeType != STRING)
    copyKey<T>(0, currentNode , nonLeafNodeSize/2, false);
  else
    copyKey<std::string>(zero, currentNode , nonLeafNodeSize/2, false);
    
  int j =0;
  for( int i = nonLeafNodeSize/2 + 1; i < nonLeafNodeSize ; ++i)
  {           
    extractKey<T>(tempKey, currentNode, i , false);
    copyKey<T>(tempKey, newNode , j, false);
      
    extractPageNo(tempPageNo, currentNode, i);
    copyPageNo(tempPageNo, newNode , j);
    ++j;
    
    //zero out the values that have been copied to the new node
    if(attributeType != STRING)
      copyKey<T>(0, currentNode , i, false);
    else
      copyKey<std::string>(zero, currentNode , i, false);
      
    copyPageNo(0, currentNode , i);
  }
  
  //set the last pointer in the new node
  extractPageNo(tempPageNo, currentNode, nonLeafNodeSize);
  copyPageNo(tempPageNo, newNode , j);
  copyPageNo(0, currentNode , nonLeafNodeSize);
  
  if( attributeType != STRING)
  {
    //zero out the rest of the node entries
    copyKey<T>(0, newNode , j, false);
    for(int i = j+1; i<nonLeafNodeSize;++i)
    {
      copyKey<T>(0, newNode , i, false);
      copyPageNo(0, newNode , i);
    }
  
    copyPageNo(0, newNode , nonLeafNodeSize);
  }
  else
  {
    //zero out the rest of the node entries
    copyKey<std::string>(zero, newNode , j, false);
    for(int i = j+1; i<nonLeafNodeSize;++i)
    {
      copyKey<std::string>(zero, newNode , i, false);
      copyPageNo(0, newNode , i);
    }
  
    copyPageNo(0, newNode , nonLeafNodeSize); 
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::splitLeafNode
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::splitLeafNode(Page* currentNode, Page* newLeafNode, int &newNodeIndexNotUsed)
{
  int leafNodeSize = leafOccupancy;
  T tempKey;
  RecordId tempRid;
  newNodeIndexNotUsed = 0;
  RecordId zeroRid;
  zeroRid.page_number = 0;
  char zero[11] = "0000000000";
  
  for( int i = leafNodeSize/2 + 1; i < leafNodeSize ; ++i )
  {
    extractKey<T>(tempKey, currentNode, i , true);
    copyKey<T>(tempKey, newLeafNode , newNodeIndexNotUsed, true);

    extractRid(tempRid, currentNode, i);
    copyRid(tempRid, newLeafNode , newNodeIndexNotUsed++);
    
    if(attributeType != STRING)
      copyKey<T>(0, currentNode , i, true);
    else
      copyKey<std::string>(zero, currentNode , i, true);
      
    copyRid(zeroRid, currentNode , i);
  } 
  
  if( attributeType != STRING )
  {
    //zero out the rest of the new leaf node entries
    copyKey<T>(0, newLeafNode , newNodeIndexNotUsed, true);
    copyRid(zeroRid, newLeafNode , newNodeIndexNotUsed);
    
    for(int i = newNodeIndexNotUsed+1; i<leafNodeSize;++i)
    {
      copyKey<T>(0, newLeafNode , i, true);
      copyRid(zeroRid, newLeafNode , i);
    }
  }
  else
  {
    //zero out the rest of the new leaf node entries
    copyKey<std::string>(zero, newLeafNode , newNodeIndexNotUsed, true);
    copyRid(zeroRid, newLeafNode , newNodeIndexNotUsed);
    
    for(int i = newNodeIndexNotUsed+1; i<leafNodeSize;++i)
    {
      copyKey<std::string>(zero, newLeafNode , i, true);
      copyRid(zeroRid, newLeafNode , i);
    }
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::isNonLeafFull
// -----------------------------------------------------------------------------
void BTreeIndex::isNonLeafFull(Page* currentNode, int &lastIndexUsed)
{
  int nonLeafNodeSize = nodeOccupancy;
  PageId tempPageNo;
  int indexCounter = 0;
  for( indexCounter = 0; indexCounter < nonLeafNodeSize; ++indexCounter )
  {
    extractPageNo(tempPageNo, currentNode, indexCounter + 1);
    //if page no is 0 the last page no index was the last index with
    //valid data in it
    if( tempPageNo == 0 )
    {
      lastIndexUsed = indexCounter;
      return;
    } 
  }
  //the node is full, so set the lastIndexUsed to the nonLeafNodeSize
  lastIndexUsed = nonLeafNodeSize;
}

// -----------------------------------------------------------------------------
// BTreeIndex::isLeafFull
// -----------------------------------------------------------------------------
void BTreeIndex::isLeafFull( Page* currentNode, int &lastIndexUsed)
{
  int leafNodeSize = leafOccupancy;
  RecordId tempRid;
  int indexCounter = 0;
  for( indexCounter = 0; indexCounter < leafNodeSize; ++indexCounter )
  {
    //if the page no is 0 the last page no index was the last index with valid
    //data in it
    extractRid(tempRid, currentNode, indexCounter);
    if( tempRid.page_number == 0 )
    {
      lastIndexUsed = indexCounter-1;
      return;
    } 
  }
  //the node is full and so set the lastIndexUsed to the leafNodeSize - 1
  lastIndexUsed = leafNodeSize-1;
}

// -----------------------------------------------------------------------------
// BTreeIndex::insertKeyRidPair
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::insertKeyRidPair( Page* currentNode, RIDKeyPair<T> keyRidPair, int lastIndexUsed )
{
  int keyIter;
  int ridIter = 0;
  
  T tempKey;
  RecordId rid;
  
  for( keyIter = 0; keyIter <= lastIndexUsed; ++keyIter)
  {
    extractKey<T>( tempKey, currentNode, keyIter, true);
    if( keyRidPair.key < tempKey )
    {
      //shift everything starting from lastIndexUsed to the right
      //to make place for the values being inserted
      for(int subIter = lastIndexUsed; subIter >= keyIter ; --subIter )
      {
        extractKey<T>(tempKey, currentNode, subIter , true);
        copyKey<T>(tempKey, currentNode , subIter+1, true);
        
        extractRid(rid, currentNode, subIter);
        copyRid(rid, currentNode , subIter+1);
      }
      
      //insert the new values in the appropriate position
      copyKey<T>(keyRidPair.key, currentNode , keyIter, true);
      copyRid(keyRidPair.rid, currentNode, keyIter);
      
      return;
    }
    ++ridIter;
  }
  
  //key being inserted is the largest in the node 
  copyKey<T>(keyRidPair.key, currentNode , lastIndexUsed+1, true);
  copyRid(keyRidPair.rid, currentNode, lastIndexUsed+1);
}


// -----------------------------------------------------------------------------
// BTreeIndex::insertPageKeyPair
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::insertPageKeyPair( Page* currentNode, PageKeyPair<T> keyPagePair, int lastIndexUsed )
{
  int pageNoIter = 0; 

  T tempValue;
  PageId pageNo;
  
  for( int keyIter=0; keyIter < lastIndexUsed; ++keyIter )
  {
    extractKey<T>(tempValue, currentNode, keyIter, false);
    if( keyPagePair.key < tempValue )
    {
      //shift everything starting from lastIndexUsed to the right
      //to make place for the values being inserted
      for(int subIter = lastIndexUsed; subIter >= keyIter ; --subIter )
      {
        extractKey<T>(tempValue, currentNode, subIter-1 , false);
        copyKey<T>(tempValue, currentNode , subIter, false);
        
        extractPageNo(pageNo, currentNode, subIter );
        copyPageNo(pageNo, currentNode , subIter+1 );
      }
      
      //insert the new values in the appropriate position
      copyKey<T>(keyPagePair.key, currentNode , keyIter, false);
      copyPageNo(keyPagePair.pageNo, currentNode , keyIter+1);
      return;
    } 
    ++pageNoIter;
  } 
  
  //value to be inserted is bigger than everything else in the node
  #ifdef DEBUG
    std::cout << "lastIndex Value being inserted into" << lastIndexUsed << std::endl;
    std::cout << "keyPagePair.key value "<< keyPagePair.key<<std::endl;
    std::cout << "keyPagePair.pageNo "<< keyPagePair.pageNo<<std::endl;
  #endif
  copyKey<T>(keyPagePair.key, currentNode , lastIndexUsed, false);
  copyPageNo(keyPagePair.pageNo, currentNode , lastIndexUsed+1);
}

// -----------------------------------------------------------------------------
// BTreeIndex::findPageNoInNonLeaf
// -----------------------------------------------------------------------------
template <class T>
PageId BTreeIndex::findPageNoInNonLeaf( Page *currentNode,  T key )
{
  PageId pageNo;
  int lastIndexUsed;
  //figure out the last valid index in the node
  isNonLeafFull( currentNode, lastIndexUsed);

  T higherValue;
  for( int i=0; i <= lastIndexUsed ; i++)
  {
    extractKey<T>(higherValue, currentNode, i, false);
    //if the current value of i is the same as the lastindex used then
    //this is the path we must follow, or if the value of the key
    //at this index is less than the higherValue we know that this
    //is the path we want to follow
    if( i == lastIndexUsed || key < higherValue )
    {
      extractPageNo( pageNo, currentNode, i);
      #ifdef DEBUG
        std::cout << "$$pageNo chosen" << pageNo << std::endl;
      #endif
      return pageNo;
    } 
  }
  return 0;
}

// -----------------------------------------------------------------------------
// BTreeIndex::setHighLowVal
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::setHighLowVal( const void* val, bool high)
{
  //set the appropriate member values depending on the type of
  //index being scanned at this point
  if( attributeType == INTEGER )
  {
    if( high ) highValInt = *(int*)( (char*)val );
    else       lowValInt = *(int*)( (char*)val );
  }
  else if( attributeType == DOUBLE )
  {
    if( high ) highValDouble = *(double*)( (char*)val );
    else       lowValDouble = *(double*)( (char*)val );
  }
  else if( attributeType == STRING )
  {
    if( high )
    {
      highValString.clear();
      for( int i = 0; i < 10; i++ )
        highValString += *((char*)val + i );
    }
    else
    {
      lowValString.clear();
      for( int i = 0; i < 10; i++ )
        lowValString += *((char*)val + i );
    }
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyRecordToRidKeyPair
// -----------------------------------------------------------------------------
template <class T>
RIDKeyPair<T> BTreeIndex::copyRecordToRidKeyPair(std::string rec, RecordId rid, const int attrByteOffset )
{
  RIDKeyPair<T> ridKeyVal;
  T key;

  //copy the key and rid value for the given RID into a ridKeyVal object
  key = *(T*)(rec.c_str() + attrByteOffset);  
  ridKeyVal.set( rid, key);
  return ridKeyVal;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyRecordToRidKeyPair
// string version of above templatized function
// -----------------------------------------------------------------------------
template <>
RIDKeyPair<std::string> BTreeIndex::copyRecordToRidKeyPair<std::string>(std::string rec, RecordId rid ,const int attrByteOffset )
{
  RIDKeyPair<std::string> ridKeyVal;
  std::string key = rec.substr(attrByteOffset, 10);
  ridKeyVal.set(rid, key);
  return ridKeyVal;
}

// -----------------------------------------------------------------------------
// BTreeIndex::getHighLowVal
// -----------------------------------------------------------------------------
template <class T>
T BTreeIndex::getHighLowVal(bool high)
{
  if( high ) return highValInt;
  else       return lowValInt;
}

// -----------------------------------------------------------------------------
// BTreeIndex::getHighLowVal
// double version of above templatized function
// -----------------------------------------------------------------------------
template<>
double BTreeIndex::getHighLowVal<double>(bool high)
{
  if( high ) return highValDouble;
  else       return lowValDouble;
}

// -----------------------------------------------------------------------------
// BTreeIndex::getHighLowVal
// string version of above templatized function
// -----------------------------------------------------------------------------
template<>
std::string BTreeIndex::getHighLowVal<std::string>(bool high)
{
  if( high ) return highValString;
  else       return lowValString;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyKey
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::copyKey( T key, Page *nodePagePtr , int index, bool leaf)
{
  if( leaf ) ( (LeafNodeInt*)(nodePagePtr) ) -> keyArray[index] = key;
  else       ( (NonLeafNodeInt*)(nodePagePtr) ) -> keyArray[index] = key;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyKey
// double version of above templatized function
// -----------------------------------------------------------------------------
template <>
void BTreeIndex::copyKey<double>( double key, Page *nodePagePtr, int index, bool leaf)
{
  if( leaf ) ( (LeafNodeDouble*)(nodePagePtr) ) -> keyArray[index] = key;
  else       ( (NonLeafNodeDouble*)(nodePagePtr) ) -> keyArray[index] = key;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyKey
// string version of above templatized function
// -----------------------------------------------------------------------------
template <>
void BTreeIndex::copyKey<std::string>( std::string key, Page *nodePagePtr, int index, bool leaf)
{
  if( leaf )
  {
    for( int i = 0; i < 10; i++ )
      ( (LeafNodeString*)(nodePagePtr) ) -> keyArray[index][i] = key[i];
  } 
  else
  {
    for( int i = 0; i < 10; i++ )
      ( (NonLeafNodeString*)(nodePagePtr) ) -> keyArray[index][i] = key[i];
  }
  key.clear();
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractKey
// -----------------------------------------------------------------------------
template <class T>
T BTreeIndex::extractKey(T &value, Page *nodePagePtr , int index, bool leaf)
{
  if( leaf ) value = ( (LeafNodeInt*)(nodePagePtr) ) -> keyArray[index];
  else       value = ( (NonLeafNodeInt*)(nodePagePtr) ) -> keyArray[index];
  return value;
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractKey
// double version of above templatized function
// -----------------------------------------------------------------------------
template <>
double BTreeIndex::extractKey<double>( double &value, Page *nodePagePtr, int index, bool leaf)
{
  if( leaf ) value = ( (LeafNodeDouble*)(nodePagePtr) ) -> keyArray[index];
  else       value = ( (NonLeafNodeDouble*)(nodePagePtr) ) -> keyArray[index];
  return value;
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractKey
// string version of above templatized function
// -----------------------------------------------------------------------------
template <>
std::string BTreeIndex::extractKey<std::string>( std::string &value, Page *nodePagePtr, int index, bool leaf)
{
  value.clear();
  if( leaf )
  {
    for( int i = 0; i < 10; i++ )
      value+= ( (LeafNodeString*)(nodePagePtr) ) -> keyArray[index][i];
  }
  else
  {
    for( int i = 0; i < 10; i++ )
      value+= ( (NonLeafNodeString*)(nodePagePtr) ) -> keyArray[index][i];
  }
  return value;
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractPageNo
// -----------------------------------------------------------------------------
PageId BTreeIndex::extractPageNo( PageId &pageNo, Page *nodePagePtr, int index)
{
  if( attributeType == INTEGER )
    pageNo = ( (NonLeafNodeInt*)(nodePagePtr) ) -> pageNoArray[index];
  if( attributeType == DOUBLE )
    pageNo = ( (NonLeafNodeDouble*)(nodePagePtr) ) -> pageNoArray[index];
  if( attributeType == STRING )
    pageNo = ( (NonLeafNodeString*)(nodePagePtr) ) -> pageNoArray[index];
  return pageNo;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyPageNo
// -----------------------------------------------------------------------------
void BTreeIndex::copyPageNo( PageId pageNo, Page *nodePagePtr, int index)
{
  if( attributeType == INTEGER )
    ( (NonLeafNodeInt*)(nodePagePtr) ) -> pageNoArray[index] = pageNo;
  if( attributeType == DOUBLE )
    ( (NonLeafNodeDouble*)(nodePagePtr) ) -> pageNoArray[index] = pageNo;
  if( attributeType == STRING )
    ( (NonLeafNodeString*)(nodePagePtr) ) -> pageNoArray[index] = pageNo;
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractLevel
// -----------------------------------------------------------------------------
int BTreeIndex::extractLevel( int &level, Page *nodePagePtr)
{
  if( attributeType == INTEGER )
    level = ( (NonLeafNodeInt*)(nodePagePtr) ) -> level;
  if( attributeType == DOUBLE )
    level = ( (NonLeafNodeDouble*)(nodePagePtr) ) -> level;
  if( attributeType == STRING )
    level = ( (NonLeafNodeString*)(nodePagePtr) ) -> level;
  return level;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyLevel
// -----------------------------------------------------------------------------
void BTreeIndex::copyLevel( int level, Page *nodePagePtr)
{
  if( attributeType == INTEGER )
    ( (NonLeafNodeInt*)(nodePagePtr) ) -> level = level;
  if( attributeType == DOUBLE )
    ( (NonLeafNodeDouble*)(nodePagePtr) ) -> level = level;
  if( attributeType == STRING )
    ( (NonLeafNodeString*)(nodePagePtr) ) -> level = level;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copyRid
// -----------------------------------------------------------------------------
void BTreeIndex::copyRid( RecordId rid, Page *nodePagePtr, int index)
{
  if( attributeType == INTEGER )
    ( (LeafNodeInt*)(nodePagePtr) ) -> ridArray[index] = rid;
  if( attributeType == DOUBLE )
    ( (LeafNodeDouble*)(nodePagePtr) ) -> ridArray[index] = rid;
  if( attributeType == STRING )
    ( (LeafNodeString*)(nodePagePtr) ) -> ridArray[index] = rid;
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractRid
// -----------------------------------------------------------------------------
RecordId BTreeIndex::extractRid( RecordId &rid, Page *nodePagePtr, int index)
{
  if( attributeType == INTEGER )
    rid = ( (LeafNodeInt*)(nodePagePtr) ) -> ridArray[index];
  if( attributeType == DOUBLE )
    rid = ( (LeafNodeDouble*)(nodePagePtr) ) -> ridArray[index];
  if( attributeType == STRING )
    rid = ( (LeafNodeString*)(nodePagePtr) ) -> ridArray[index];
  return rid;
}

// -----------------------------------------------------------------------------
// BTreeIndex::copySibPtr
// -----------------------------------------------------------------------------
void BTreeIndex::copySibPtr(PageId pageNo, Page *nodePagePtr)
{
  if( attributeType == INTEGER )
    ( (LeafNodeInt*)(nodePagePtr) ) -> rightSibPageNo = pageNo;
  if( attributeType == DOUBLE )
    ( (LeafNodeDouble*)(nodePagePtr) ) -> rightSibPageNo = pageNo;
  if( attributeType == STRING )
    ( (LeafNodeString*)(nodePagePtr) ) -> rightSibPageNo = pageNo;
}

// -----------------------------------------------------------------------------
// BTreeIndex::extractSibPtr
// -----------------------------------------------------------------------------
PageId BTreeIndex::extractSibPtr(PageId &pageNo, Page *nodePagePtr)
{
  if( attributeType == INTEGER )
    pageNo = ( (LeafNodeInt*)(nodePagePtr) ) -> rightSibPageNo;
  if( attributeType == DOUBLE )
    pageNo = ( (LeafNodeDouble*)(nodePagePtr) ) -> rightSibPageNo;
  if( attributeType == STRING )
    pageNo = ( (LeafNodeString*)(nodePagePtr) ) -> rightSibPageNo;
  return pageNo;
}

// -----------------------------------------------------------------------------
// BTreeIndex::zeroOutNonLeaf
// -----------------------------------------------------------------------------
void BTreeIndex::zeroOutNonLeaf(Page *currentNode)
{
  char zero[11] = "0000000000";
  if( attributeType == INTEGER )  
  { 
    for(int i = 0; i<INTARRAYNONLEAFSIZE; ++i)
    {
      copyKey<int>(0, currentNode , i, false);
      copyPageNo(0, currentNode , i);
    }
  }
  
  if( attributeType == DOUBLE ) 
  { 
    for(int i = 0; i<DOUBLEARRAYNONLEAFSIZE; ++i)
    {
      copyKey<double>(0, currentNode , i, false);
      copyPageNo(0, currentNode , i);
    }
  }
  
  if( attributeType == STRING ) 
  { 
    for(int i = 0; i<STRINGARRAYNONLEAFSIZE; ++i)
    {
      copyKey<std::string>(zero, currentNode , i, false);
      copyPageNo(0, currentNode , i);
    }
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::zeroOutNonLeaf
// -----------------------------------------------------------------------------
void BTreeIndex::zeroOutLeaf(Page *currentNode)
{
  RecordId zeroRid;
  zeroRid.page_number = 0;
  char zero[11] = "0000000000";
  if( attributeType == INTEGER )  
  { 
    for(int i = 0; i<INTARRAYLEAFSIZE; ++i)
    {
      copyKey<int>(0, currentNode , i, true);
      copyRid(zeroRid, currentNode , i);
    }
  }
  
  if( attributeType == DOUBLE ) 
  { 
    for(int i = 0; i<DOUBLEARRAYLEAFSIZE; ++i)
    {
      copyKey<double>(0, currentNode , i, true);
      copyRid(zeroRid, currentNode , i);
    }
  }
  
  if( attributeType == STRING )
  { 
    for(int i = 0; i<STRINGARRAYLEAFSIZE; ++i)
    {
      copyKey<std::string>(zero, currentNode , i, true);
      copyRid(zeroRid, currentNode , i);
    }
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::printTreeExternal
// -----------------------------------------------------------------------------
void BTreeIndex::printTreeExternal()
{
  switch(attributeType)
  {
    case INTEGER: printTree<int>( rootPageNum, false); break;
    case DOUBLE: printTree<double>( rootPageNum, false); break;
    case STRING: printTree<std::string>( rootPageNum, false); break;
    default: break;
  }
}

// -----------------------------------------------------------------------------
// BTreeIndex::printTree
// -----------------------------------------------------------------------------
template <class T>
void BTreeIndex::printTree(PageId pageNum , bool isLeaf)
{
  int lastIndexUsed;
  Page *currentNode;
  PageId pNum1;
  T tKey1;
  bufMgr->readPage( file, pageNum , currentNode );
  
  if( !isLeaf )
  {
    if(*(int*)currentNode == 0)
    { 
      isNonLeafFull( currentNode, lastIndexUsed);
    
      for(int i=0; i< lastIndexUsed;i++)
      {
        extractPageNo(pNum1, currentNode, i );  
        std::cout << pNum1 << " | ";
        extractKey<T>(tKey1, currentNode, i , false); 
        std::cout << tKey1 << " | ";
      }
      extractPageNo(pNum1, currentNode, lastIndexUsed );  
      std::cout << pNum1 << " ";
      std::cout << std::endl;
      
      for(int i=0; i< lastIndexUsed;i++)
      {
        extractPageNo(pNum1, currentNode, i );  
        printTree<T>(pNum1, false);
      }
      extractPageNo(pNum1, currentNode, lastIndexUsed );  
      printTree<T>(pNum1, false);
      bufMgr->unPinPage(file, pageNum, 0);
    }
    else
    {
      isNonLeafFull( currentNode, lastIndexUsed);
    
      for(int i=0; i< lastIndexUsed;i++)
      {
        extractPageNo(pNum1, currentNode, i );  
        std::cout << pNum1 << " | ";
        extractKey<T>(tKey1, currentNode, i , false); 
        std::cout << tKey1 << " | ";
      }
      extractPageNo(pNum1, currentNode, lastIndexUsed );  
      std::cout << pNum1 << " ";
      std::cout << std::endl;
      
      for(int i=0; i< lastIndexUsed;i++)
      {
        extractPageNo(pNum1, currentNode, i );  
        printTree<T>(pNum1, true);
      }
      extractPageNo(pNum1, currentNode, lastIndexUsed );  
      printTree<T>(pNum1, true);
      bufMgr->unPinPage(file, pageNum, 0);
    }
    return;
  }
  
  //for leafNode
  isLeafFull( currentNode,lastIndexUsed);
  for(int i=0; i<= lastIndexUsed;i++)
  {
    extractKey<T>(tKey1, currentNode, i , true);  
    std::cout << tKey1 << " ";
  }
  std::cout << std::endl;
  bufMgr->unPinPage(file, pageNum, 0);
}

}