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

#pragma once

#include <iostream>
#include <string>
#include "string.h"
#include <sstream>
#include <list>
#include <algorithm>
#include <deque>
#include <stack>

#include "types.h"
#include "page.h"
#include "file.h"
#include "buffer.h"

namespace badgerdb
{

#define MAXKEYSIZE 12 //why 12??????????

//constants used by the BTreeIndex class that are calculated
//based on the type of data being used to create the index
const  int STRINGSIZE = 10;

//                                                sibling ptr           key               rid
const  int INTARRAYLEAFSIZE = ( Page::SIZE - sizeof( PageId ) ) / ( sizeof( int ) + sizeof( RecordId ) );
const  int DOUBLEARRAYLEAFSIZE = ( Page::SIZE - sizeof( PageId ) ) / ( sizeof( double ) + sizeof( RecordId ) );
const  int STRINGARRAYLEAFSIZE = ( Page::SIZE - sizeof( PageId ) ) / ( 10 * sizeof(char) + sizeof( RecordId ) );
//                                                    level        extra page pointer        key       page pointer
const  int INTARRAYNONLEAFSIZE = ( Page::SIZE - sizeof( int ) - sizeof( PageId ) ) / ( sizeof( int ) + sizeof( PageId ) );
const  int DOUBLEARRAYNONLEAFSIZE = (( Page::SIZE - sizeof( int ) - sizeof( PageId ) ) / ( sizeof( double ) + sizeof( PageId ) ))-1;
const  int STRINGARRAYNONLEAFSIZE = ( Page::SIZE - sizeof( int ) - sizeof( PageId ) ) / ( 10 * sizeof(char) + sizeof( PageId ) );

/*
Structure to store a key-rid pair.
It is used to pass the pair to functions that 
add to or make changes to the leaf node pages of the tree.
Is templated for the key member.
*/
template <class T>
class RIDKeyPair{
public:
  RecordId rid;
  T key;
  void set( RecordId r, T k)
  {
    rid = r;
    key = k;
  }
};

/*
Structure to store a key page pair which is used to pass the key and page to functions that make 
any modifications to the non leaf pages of the tree.
*/
template <class T>
class PageKeyPair{
public:
  PageId pageNo;
  T key;
  void set( int p, T k)
  {
    pageNo = p;
    key = k;
  }
};

/*
Overloaded operator to compare the key values of two rid-key pairs
and if they are the same compares to see if the first pair has
a smaller rid.pageNo value.
*/
template <class T>
bool operator<( const RIDKeyPair<T>& r1, const RIDKeyPair<T>& r2 )
{
  if( r1.key != r2.key )
    return r1.key < r2.key;
  else
    return r1.rid.page_number < r2.rid.page_number;
}

/*
The meta page is always page 1 of the btree index file and is cast
to the following structure to store or retrieve information from it.
Contains the relation name for which the index is created, the byte offset
of the key value on which the index is made, the type of the key and the page no
of the root page. Root page starts as page 2 but since a split can occur
at the root the root page may get moved up and get a new page no.
*/
struct IndexMetaInfo{
  char relationName[20];
  int attrByteOffset;
  Datatype attrType;
  PageId rootPageNo;
};

/*
Each node is a page, so once we read the page in we just cast
the pointer to the page to this struct and use it to access the parts
These structures basically are the format in which the information
is stored in the pages for the index file depending on what kind of 
node they are.
The level memeber of each non leaf structure seen below is set to 1 if the
nodes at this level are just above the leaf nodes. Otherwise set to 0.
*/

/*
Structure for all non leaf nodes that have the key value as int.
Used to place information into a leaf node and then retrieve it 
as well. 
*/
struct NonLeafNodeInt{
  int level;  
  int keyArray[ INTARRAYNONLEAFSIZE ];
  PageId pageNoArray[ INTARRAYNONLEAFSIZE + 1 ];
};

/*
Structure for all non leaf nodes that have the key value as double.
Used to place information into a leaf node and then retrieve it 
as well.
*/
struct NonLeafNodeDouble{
  int level;
  double keyArray[ DOUBLEARRAYNONLEAFSIZE ];
  PageId pageNoArray[ DOUBLEARRAYNONLEAFSIZE + 1 ];
};

/*
Structure for all non leaf nodes that have the key value as string.
Used to place information into a leaf node and then retrieve it 
as well.
*/
struct NonLeafNodeString{

  int level;
  char keyArray[ STRINGARRAYNONLEAFSIZE ][ STRINGSIZE ];
  PageId pageNoArray[ STRINGARRAYNONLEAFSIZE + 1 ];
};

/*
Structure for all leaf nodes that have the key value as int.
Used to place information into a leaf node and then retrieve it 
as well. 
*/
struct LeafNodeInt{
  int keyArray[ INTARRAYLEAFSIZE ];
  RecordId ridArray[ INTARRAYLEAFSIZE ];
  PageId rightSibPageNo;
};

/*
Structure for all leaf nodes that have the key value as double.
Used to place information into a leaf node and then retrieve it 
as well. 
*/
struct LeafNodeDouble{
  double keyArray[ DOUBLEARRAYLEAFSIZE ];
  RecordId ridArray[ DOUBLEARRAYLEAFSIZE ];
  PageId rightSibPageNo;
};

/*
Structure for all leaf nodes that have the key value as string.
Used to place information into a leaf node and then retrieve it 
as well. 
*/
struct LeafNodeString{
  char keyArray[ STRINGARRAYLEAFSIZE ][ STRINGSIZE ];
  RecordId ridArray[ STRINGARRAYLEAFSIZE ];
  PageId rightSibPageNo;
};

// -----------------------------------------------------------------------------
// BTreeIndex
//   A class which implements a B+ Tree index on a single attribute of one 
//   relation.  This index supports only one scan at a time.
// -----------------------------------------------------------------------------
class BTreeIndex {

private:

  File        *file;           // file object for this index
  BufMgr      *bufMgr;        //buffer manager instance
  PageId      headerPageNum;  // number of header page in file
  PageId      rootPageNum;    // page number of root page
  Datatype    attributeType;  
  int         leafOccupancy;  // maximum size of leaf node
  int         nodeOccupancy;  // maximum size of non-leaf node

// Members specific to scanning

  bool        scanExecuting;          // is an index scan currently executing?
  int         nextEntry;              // offset of the next entry to be scanned
  PageId      currentPageNum;         // page number of pinned page
  Page*       currentPageData;
  int         lowValInt;        //variable that define the range based on which
  double      lowValDouble;     //type of index is being used for the scan
  std::string lowValString;
  int         highValInt;
  double      highValDouble;
  std::string highValString;
  
  Operator    lowOp;                  // GT (>) or GTE (>=)
  char        highVal[MAXKEYSIZE];    // comparison value of filter
  Operator    highOp;                 // LT (<) or LTE (<=)

  //other meta info read in from page 1 of the file 
  int attrByteOffset;

  //constructor helper functions//
/*
This function is called by the actual btreeindex constructor. It reads the
data from the actual heap file using HeapFileScan, stores the key rid 
pairs into a deque and then sorts it. After sorting the data it calls 
the fillLeafNodes to create all the required leaf nodes of the index and
then calls the fillNonLeaf nodes till the it reached the point at which
it has created the root 
It also creates the meta page and stores all the required information for the
index being created.
Uses BULK LOADING ALGORITHM 
Parameters- 
  relationName : name of relation for which tree is being created
        outIndexName : name of index file that is being created
  attrByteOffset: offset of record that is the key for the index
  attrType: attribute type
  
  status: to report any errors is set and can be used by calling function
*/  
  template <class T> 
  void BTreeTemplateConstructor(const std::string & relationName,
      std::string & outIndexName,
      const int attrByteOffset,
      const Datatype attrType);
  
/*
This function is called by the function above, it basically goes through the
dataList deque which contains all the data entries and starts
placing them in leafNodes. It allocates space for nodes and fills them up with the
data entries. While doing so it fills the the thisLevelNodes deque placing
the first data entry that was into each leaf node being created.
The nodes are filled up based on the number of entries we have calculated
each node as being able to contain. We only fill the nodes upto half the
capacity calculated.
Parameters-
  thisLevelNodes: is set by this function to tell the calling function
      which values need to placed in the levels above
      for the balanced tree to be created
  datalist: all the key values and rids for the records to be added to the leaf level
Return Value: returns last page number assigned
*/
  template <class T>
  int fillLeafNodes( 
    std::deque< PageKeyPair< T > > &thisLevelNodes,
    std::deque< RIDKeyPair< T > > &dataList);
  
/*
Once the leaf nodes are created, this function is called in a loop. It takes each
entry in the thisLevelNodes, and places it into a nonLeaf node. Once the nonLeafnode
is half full, it places the next entry into the lastLevelNodes deque, creates another 
nonLead node and starts filling it up until its half full and keeps going on like this.
After it has been through the whole thisLevelNodes deque it set the thisLevelNodes deque
equal to the lastLevelNodes deque so that the next time fillNonLeafNodes is called in
the while loop of the bulk loading algorithm it uses that as we are going to be creating
the level right above the one just created.
Parameters-
  thisLevelNodes- indicates all the entries that were not placed
      in this level but will be placed into levels above
  lastLevelNodes- indicates all entries that go into this level or levels 
      above
  level- indicates the level being populated
  status - set by the function and can be read by the calling function
  
*/
  template <class T>
  int fillNonLeafNodes( 
    std::deque< PageKeyPair< T > > &thisLevelNodes,
    std::deque< PageKeyPair< T > > &lastLevelNodes,
    const int level);
  
/*
This functions helps copy the key and rid from a record into a RIDKeyPair object 
based on the type of the data being used for the current index.
Parameters- 
  rec: record whose key pair is to be extracted
  rid: the rid for this record
  attrByteOffset: the offset of the key value in the record
Return Value: returns the ridKey pair
*/
  template <class T>
  RIDKeyPair<T> copyRecordToRidKeyPair( std::string rec, RecordId rid, const int attrByteOffset );

  //Scan Helper Functions//
/*
Starts a scan for the user. If a previous scan is still running, ends it and starts the
new scan. It first checks to make sure that the op values used are allowed and correct. It 
then goes down the index tree looking for the lower bound specified and finds the leaf node
page it should be in. Then the functions parses the node till entries are smaller than the lower
bound specified. If this value is not found in the page, we know the lowest value for this scan is the first
value of the next page. Next, the range parameters are checked based on which the we set the nextEntry value.
The nextentry values is moved up using the scanNext function.
Return Value: returns the status 
*/
  template <class T>
  const void templateStartScan();

/*
Basically checks the next entry in the leaf Node we are at and if we are at the end of the node
checks the right sibling pointer and sets the next entry to the first entry in that page. It also
checks to make sure we are still in the range specified by scanStart. 
*/
  template <class T>
  const void templateScanNext(RecordId& outRid);  // returned record id

  //Insert Helper Functions// 
/*
called by the insertEntry function based on the type of tree being inserted into setting
the appropriate size parameters and is always sent the root page number the first time.
It starts at the root and goes down the tree along the path based on the value being inserted. 
Once it gets to the right leaf node page, if it can insert it there it does so, and if it is full
it splits it and places the keyrid pair into either the old page that was halved or the new page
depending on where it belongs and then this split is propogated back up each level. When it
returns from the insertInto call that inserted the keyrid into the leaf it takes the first entry
of the new page that was created because of the split and places it into the non leaf node. And again
does a split if needed. This goes all the way upto the root. If the root is split, we the meta data
is changed and this function handles that by writing the new information to the metapage. 
Parameters-
  pageNo: next page number of the path being followed along the tree for insert
  key: key value being inserted
  rid: rid value for the record whose key is being inserted
  treePath: stack to indicated what the last level that was inserted is
Return Value- returns the status after insert
*/
  template <class T>
  void insertInto(PageId pageNo,  T key, PageKeyPair<T> &newPageKeyPair, 
         RecordId &rid, std::stack<int> &treePath);
        
/*
Finds the next page in the path down the index based on the key value we are trying to look 
for in the leaf nodes.  
Parameters-
  currentNode: pointer to the page being looked at to determing the next page in the path
Return Value- pageNo for the path to be followed down the tree
*/
  template <class T>
  PageId findPageNoInNonLeaf( Page *currentNode, T key );
  
/*
Called to place a key page pair into a non leaf node if its not full. First checks to see
where it should go based on the sort order, then shifts everything over one and places
the key page pair into the appropriate position.
Parameters-
  currentNode: page into which the keypage pair is being inserted
  keyPagePair: key and page that need to be inserted
  lastIndexUsed:index of last valid entry in the page
*/
  template <class T>
  void insertPageKeyPair( Page* currentNode, PageKeyPair<T> keyPagePair, int lastIndexUsed );
  
/*
Same as above except for the fact that it is called for leaf pages instead and places
the key rid pair into the node
Parameters-
  currentNode:node into which the key rid need to be inserted
  RIDKeyPair: pair of key and rid that need to be inserted into the node
  lastIndexUsed: last index that is valid in the node
*/
  template <class T>
  void insertKeyRidPair( Page* currentNode, RIDKeyPair<T> keyRidPair, int lastIndexUsed );
  
/*
If a non leaf node is full, this function is called. It keeps the first half in the original
node and takes the rest of the values and places it into the newly created node while zeroing
out the entries from the original node and then also makes sure it zeros out the entries in the new
nodes that are not used.  
Parameters-
  currentNode:node that needs to be split
  newNode:page ptr to the new node into which half the current node values will be placed
*/
  template <class T>
  void splitNonLeafNode(Page* currentNode, Page* newNode);
  
/*
Same as function above for the leaf nodes.
Parameters-
  currentNode: node that needs to split
  newLeafNode: node ptr to place the second half of currentNode into
  newNodeIndexNotUsed:first index that is invalid in the node 
*/
  template <class T>
  void splitLeafNode(Page* currentNode, Page* newLeafNode, int &newNodeIndexNotUsed);
  
/*
Indicates whether the non leaf node is full and if its not tells the calling function what the index is
of the last entry that has valid data. We check the page no and if it is 0 that means the data is 
valid upto the page entry before that.
Parameters-
  curentNode: node being checked for free space
  lastIndexUsed: index of last valid entry in the node
*/
  void isNonLeafFull( Page* currentNode, int &lastIndexUsed);
  
/*
Same as function above for leaf nodes.  
Parameters-
  currentNode:node being checked for free space
  lastIndexUsed: index of last valid entry of the node
*/
  void isLeafFull( Page* currentNode,  int &lastIndexUsed);
  
/*
Function to set the right high and low val members of the class object based on the type
of index being scanned  
Parameters-
  val- value to set the high/low val variable to
  high- if true set the high val, else set the low val
*/
  template <class T>
  void setHighLowVal(const void* val, bool high);
  
/*
Function to get the righr high and low val members of the class object based on the type of the
index being scanned.  
Parameters-
  high:if true get the high val, else get the low val
*/
  template <class T>
  T getHighLowVal(bool high);
  
/*
Function to copy the key value to the appropriate index of a non leaf or leaf node.
It takes the node and casts it to the right type of structure so that we can get
access to the right part of the node that we want to write to.
Parameters-
  key:key to copy into the index of the node
  nodePagePtr:node into which key needs to be copied
  index: index into which the key needs to be copied
  leaf:whether the node being inserted into is a leaf node or not
*/
  template <class T>
  void copyKey(T key, Page *nodePagePtr , int index, bool leaf);

/*
Gets the key values stored at the index specified for a leaf or non leaf node.  
Return Value- returns the key value extracted
*/
  template <class T>
  T extractKey(T &value, Page *nodePagePtr , int index, bool leaf);

/*
Gets the page no from the appropriate index of a non leaf page. 
Parameters-
  pageNo-value of the pageNo that is at the index specified in the node
  nodePagePtr:node from which the pageNo needs to be extracted
  index:index of entry being extracted
Return Value- returns the pageNo extracted too
*/
  PageId extractPageNo(PageId &pageNo, Page *nodePagePtr, int index);
  
/*
Copies the page no into the appropriate index of a non leaf page. 
Parameters-
  pageNo:pageno to be placed in the node
  nodePagePtr:node into which the pageno needs to be inserted
  index: index at which the pageno needs to be inserted
*/
  void copyPageNo(PageId pageNo, Page *nodePagePtr, int index);

/*
Extracts the level from the non leaf page.  
Parameters-
  pageNo:set to the level of the node
  nodePagePtr:node whose level is needed
Return Value-returns the level of the node
*/
  int extractLevel(int &level, Page *nodePagePtr);
  
/*
Sets the level value for the non leaf page.
*/
  void copyLevel( int level, Page *nodePagePtr );
  
/*
Sets the rid of the appropriate index of the leaf node.
*/
  void copyRid(RecordId rid, Page *nodePagePtr, int index);
  
/*
Extracts the rid from the appropriateindex of a leaf page.  
*/
  RecordId extractRid(RecordId &rid, Page *nodePagePtr, int index);
  
/*
Set the right sib ptr of a leaf node.
*/
  void copySibPtr(PageId pageNo, Page *nodePagePtr);
  
/*
Get the right sib ptr of a leaf node.
*/
  PageId extractSibPtr(PageId &pageNo, Page *nodePagePtr);
  
/*
Zero out everything in the node.
*/
  void zeroOutNonLeaf(Page *currentNode);

/*
Zero out everything in the node.
*/  
void zeroOutLeaf(Page *currentNode);
  
/*
Debug help function to print the state of the tree at any given point.
*/
  template <class T>
  void printTree(PageId pageNum , bool isLeaf);
  
public:

// ---------------------------------------------------------------------------
// Public interface methods
// ---------------------------------------------------------------------------

// Check to see if the specified index file exists. If so, open the file.
// If not, create it and insert an entry for every tuple in the base relation
// Keep the header page pinned in memory.

  BTreeIndex(const std::string & relationName,      // name of relation file to index
    std::string & outIndexName,            // name of index file
    BufMgr *bufMgrIn,                     //buffer manager instance
    const int attrByteOffset,         // offset to attrtibute in tuple
    const Datatype attrType);
  

// Unpin the header page and close the file.  (do not delete the index file)

  ~BTreeIndex();

// Insert a new entry using the pair <value,rid>.  Check for unique values.

  const void insertEntry(const void* value,  // value to insert
      const RecordId rid);     // corresponding tuple rid

// Begin a filtered scan of the index.  For example, if the method is called 
// using ("a",GT,"d",LTE) then we should seek all entries with a value 
// greater than "a" and less than or equal to "d".

  const void startScan(const void* lowVal,     // low value of range
        const Operator lowOp,   // operation (GT, GTE)
        const void* highVal,    // high value of range
        const Operator highOp); // operation (LT, LTE)

// Fetch the record id of the next index entry that matches the scan.

  const void scanNext(RecordId& outRid);  // returned record id

// Terminate the current scan

  const void endScan();
  
/*
Public function to allow for a public interface to print the index B+-Tree
Useful for testindex
*/
  void printTreeExternal();

};

}