/* BPlus Tree Project*/
/*  To Compile      g++ Bplustree.cpp -g -o Bplustree    */
/*  To Run          ./Bplustree  <inputs>                */
/*  By: Farah Khan
*/

/*
Project Description: This assignment is designed to learn how B++ trees are made, how to insert keys and their
values. The basic purpose of B+ Tree is to form indices to allow a fast and reliable search mechanism.
When running the program user has to put if they want duplicates in their B+ tree and if the debug mode is one.
Then the user has to input the keys and their values which will be stored in a file as a B+ Tree.
*/
/*
Input Formate
Running: ./Bplustree (filename) (1 - for duplicates, 0 - no duplicates) (1 - debug mode, 0 - no debug mode)
insert(key, pointer)
lookup(key)
lookup(key1,key2)
print tree
exit
*/

//Includes
#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <string.h>
#include <iostream>
#include "Bplustree.h"


//function that reads each block from the file
static void ReadBlock(int File, int Block, int Size, void *Addr) {

	if (DEBUG == 1)
		{
			cout <<"Read Block Function :- File:"<< File << " Block: " << Block;
			cout << " Size: "  << Size << " Address: " << Addr << endl;

		}

	if(lseek(File, Block * Size, SEEK_SET) == -1 || read(File, Addr, Size) == -1)
	{
	   	cout <<"Read Block Error :- File:"<< File << " Block: " << Block;
	   	cout << " Size: " << Size << endl;
	}

}

// function that writes each block to the file
static void WriteBlock(int File, int Block, int Size, void *Addr) {

	if (DEBUG == 1)
	{
		cout <<"Write Block Function :- File:"<< File << " Block: " << Block;
		cout << " Size: "  << Size << " Address: " << Addr << endl;

	}

	if(lseek(File, Block * Size, SEEK_SET) == -1 || write(File, Addr, Size) == -1)
	{
	   	cout <<"Write Block Error :- File:"<< File << " Block: " << Block;
	   	cout << " Size: " << Size << endl;
	}
}

//read head used only in the start of the program.
static void ReadHead(int Index) {
	HeadType HeadBlock;
	ReadBlock(File(Index), 0, BLKSIZE, &HeadBlock);
	Root(Index) = HeadBlock.RootBlock;
	Alloc(Index) = HeadBlock.AllocBlock;

}

//write head used only in the start of the program
static void WriteHead(int Index) {
	HeadType HeadBlock;
        int i;
	HeadBlock.RootBlock = Root(Index);
	HeadBlock.AllocBlock = Alloc(Index);
	WriteBlock(File(Index), 0, BLKSIZE, &HeadBlock);
}

//This function opens a new tree file as binary and intializing arugments as specified by the user.
// This function als makes sure if the file is going to be new or has it already been created.
int OpenTree(char *Name, int DupKeys) {
	if (DEBUG == 1)
		cout<<"Open New Tree Function"<<endl;
	int i;
	int j;
	for(i = 0; i < NIDX; i++)
		if(!Used(i)) break;
	Used(i) = 1;
	strcpy(IdxTab[i].Name, Name);
	Dups(i) = DupKeys;
	CBlk(i) = -1;
	if((File(i) = open(Name, O_RDWR|O_BINARY)) >= 0)
	{
		if (DEBUG == 1)
			cout<<"Read File that is already created"<<endl;
		ReadHead(i);
	}
	else
/*	if((File(i) = creat(Name, S_IREAD|S_IWRITE)) >= 0) {    */
        if((File(i) = open(Name, O_RDWR|O_CREAT|O_BINARY, 0644)) >= 0) {
			if (DEBUG == 1)
				cout<<"Open New File"<<endl;
		TreeNode Node;
		Root(i) = 1;
		Alloc(i) = 2;
		WriteHead(i);
		Node.LeafNode = 1;
		Node.KeyCount = 0;
	        for(j = 0; j < FANOUT-1; j++)
                  {
                    Node.Ptrs[j] = -1;
                    Node.Keys[j] = 0;
                   }
		Node.Ptrs[FANOUT - 1] = -1;
		WriteBlock(File(i), 1, BLKSIZE, &Node);
	} else {
		perror("Error in opening file/creating file");
		Used(i) = 0;
		i = -1;
	}
	return i;
}

//Used at the end of the program to end the program
void CloseTree(int Index) {
	WriteHead(Index);
	close(File(Index));
	Used(Index) = 0;
}

//Function used to find the key, this function is called by the look up function.
static int FindKey(TreeNode *Node, int Key) {
	if (DEBUG == 1)
	{
		cout << "Find Key Function" << endl;
		cout << "Node->KeyCount: " << Node->KeyCount << endl;
	}
	int k;
	for(k = 0; k < Node->KeyCount; k++)
	{
		if(Node->Keys[k] > Key)
		{
			if (DEBUG == 1)
					cout << "Node->Keys[k] > Key " << Node->Keys[k] <<  endl;

			break;
		}

	if (DEBUG == 1)
		cout << "Return Key Count: " << k <<  endl;

	}

	return k;
}

//check buckets is called when using duplicate indices. also used for look up
static void CheckBucket(int Index, TreeNode *Node, int *Key, int *Ptr) {
	if (DEBUG == 1)
			cout << "Check Bucket Function " << endl;
	*Ptr = -1;
	if(CBlk(Index) >= 0) {
		int NextPtr;
	*Key = Node->Keys[CKey(Index)-1];
	*Ptr = Node->Ptrs[CKey(Index)];
	if(Dups(Index)) {
/*		BucketType Bucket;   */
		ReadBlock(File(Index), *Ptr, BLKSIZE, &Bucket);
		if (DEBUG == 1)
			cout << "Reading Block with pointer as bucket number: " << Node->Ptrs[CKey(Index)] << endl;
		*Ptr = Bucket.Pointers[CPtr(Index)];
		if (DEBUG == 1)
			cout << "The New Pointer is: " << Bucket.Pointers[CPtr(Index)] << endl;
		CPtr(Index)++;
		NextPtr = Bucket.Pointers[CPtr(Index)];
		if (DEBUG == 1)
			cout << "Pointer to Next Bucket for Duplicates "<< NextPtr << endl;
	}
	if(!Dups(Index) || NextPtr < 0) {
		CPtr(Index) = 0;
		CKey(Index)++;
		if(CKey(Index) > Node->KeyCount) {
			CBlk(Index) = Node->Ptrs[0];
			if (DEBUG == 1)
				cout << "Not Duplicate or Next Pointer is < 0, Current Block is: "<< CBlk(Index) << endl;
			CKey(Index) = 1;
		}
	}

	}
}

//look up function that takes in the parameters to search for the key through the b+ tree
int Lookup(int Index, int Key) {
	if (DEBUG == 1)
		cout << "Lookup Key Function"<< endl;

	TreeNode Node;
	int Ptr;
	CBlk(Index) = Root(Index);
	if (DEBUG == 1)
			cout << "Root Block in Lookup is: "<< CBlk(Index) << endl;
	for(;;)
	{
		ReadBlock(File(Index), CBlk(Index), BLKSIZE, &Node);
		CKey(Index) = FindKey(&Node, Key);
		if (DEBUG == 1)
				cout << "The CKey Value is: " << CKey(Index) << endl;
		if(Node.LeafNode)
		{
			if (DEBUG == 1)
				cout << "Its a Leaf Node so break" << endl;
			break;
		}
		CBlk(Index) = Node.Ptrs[CKey(Index)];
		if (DEBUG == 1)
			cout<<" The new Current CBLK Lookup: "<< CBlk(Index) <<endl;

	}
	CPtr(Index) = 0;
	if(CKey(Index) == 0)
		CBlk(Index) = -1;
	CheckBucket(Index, &Node, &Key, &Ptr);
	cout << "Pointer is: " << Ptr << endl;
	return Ptr;
}

//The print function that prints out the whole tree according to its blocks and duplicate buckets.
int print(int Index, char *filename) {

		if (DEBUG == 1)
			cout << "Print Function"<< endl;
	TreeNode Node;


	struct stat results;
	if(stat(filename, &results) == 0)
	{
		if (DEBUG == 1)
			cout << "Getting File Size to get Number of Blocks"<< endl;
		FILE_SIZE = results.st_size;
		TOTAL_BLOCKS = (FILE_SIZE - 40)/40;
		if (DEBUG == 1)
		{
			cout<<"File Size: "<<FILE_SIZE<<endl;
			cout<<"Total Blocks: "<<TOTAL_BLOCKS<<endl;
		}
	}
	else
		cout<<"Error Opening File"<<endl;

    for(int i = 1; i <= TOTAL_BLOCKS; i++)
    {
		int k =0;
		cout << "\nBlock Number: " << i<<"       ";
		ReadBlock(File(Index), i, BLKSIZE, &Node);

		if (DEBUG == 1)
			cout << "Displaying Keys for non-leaf nodes"<< endl;
		if(Node.KeyCount!=0 && !Node.LeafNode)
		{
			CKey(Index) = k;
			cout << " pointer: " <<  Node.Ptrs[CKey(Index)];
		}
		else if(Node.KeyCount!=0 && Node.LeafNode)
		{
			CKey(Index) = k;
			cout << " pointer: " <<  Node.Ptrs[CKey(Index) + 1];

		}
		if (DEBUG == 1)
			cout << "Displaying keys and pointers for leaf nodes"<< endl;
		if(Node.LeafNode)
		{
			for(k = 0; k < Node.KeyCount; k++)
			{
				CKey(Index) = k;
				CBlk(Index) = Node.Ptrs[CKey(Index)+2];

				if(Node.LeafNode)
				{
					//CBlk(Index) = -1;
					if(k == (Node.KeyCount)-1)
					{
						CKey(Index) = 0;
						cout << " Key: " << Node.Keys[k];
						cout << " pointer: " <<  Node.Ptrs[CKey(Index)];
					}
					else
					{
						cout << " Key: " << Node.Keys[k];
						cout << " pointer: " <<  CBlk(Index);
					}

				}
			}
		}

		else if(!Node.LeafNode)
		{
			for(k = 0; k < Node.KeyCount; k++)
			{
				CKey(Index) = k;

				CBlk(Index) = Node.Ptrs[CKey(Index)+1];

					cout << " Key: " << Node.Keys[k];
					cout << " pointer: " <<  CBlk(Index);
				}

		}
		if (DEBUG == 1)
			cout << "Checking for Duplicates for display"<< endl;
   		 if(DUPLICATES == 1)
   			{
				int j = 0;
				if(Node.LeafNode){
					for(k = 0; k < Node.KeyCount; k++) {
						CKey(Index) = k;

						cout << "\nBucket: " << Node.Ptrs[CKey(Index) + 1]  << "        ";

							ReadBlock(File(Index), Node.Ptrs[CKey(Index) + 1], BLKSIZE, &Bucket);
							j=0;
							while (Bucket.Pointers[j] != -1)
							{
								CPtr(Index) = j;
								cout << "pointers:  " << Bucket.Pointers[CPtr(Index)] << "      ";
								j++;

							}

				}
			}
  		}
	} // end of for loop
	cout << "\n";
}

//This function is used when inserting new keys and their pointers. It performers all the necessary
// splits of the tree to make it balance and compli to the b+ tree algorithm
static int InsertKey(int Index, TreeNode *Node, int KIdx, int *Key, int *Ptr) {
	if (DEBUG == 1)
			cout << "Insert Key Function"<< endl;
	int Keys[FANOUT], Ptrs[FANOUT+1];
	int Count, Count1, Count2, k;
	Count = Node->KeyCount + 1;
	Count1 = Count < FANOUT ? Count : FANOUT/2;
	Count2 = Count - Count1;
	for(k = FANOUT/2; k < KIdx; k++) {
		Keys[k] = Node->Keys[k];
		Ptrs[k+1] = Node->Ptrs[k+1];
	}
	Keys[KIdx] = *Key;
	Ptrs[KIdx+1] = *Ptr;
	for(k = KIdx; k < Node->KeyCount; k++) {
		Keys[k+1] = Node->Keys[k];
		Ptrs[k+2] = Node->Ptrs[k+1];
	}
	for(k = KIdx; k < Count1; k++) {
		Node->Keys[k] = Keys[k];
		Node->Ptrs[k+1] = Ptrs[k+1];
	}
	Node->KeyCount = Count1;
	if(Count2) {
		int s, d;
		TreeNode NNode;
		NNode.LeafNode = Node->LeafNode;
		Count2 -= !Node->LeafNode;
		for(s = FANOUT/2 + !Node->LeafNode, d = 0; d < Count2; s++, d++) {
			NNode.Keys[d] = Keys[s];
			NNode.Ptrs[d] = Ptrs[s];
		}
		NNode.Ptrs[d] = Ptrs[s];
		NNode.KeyCount = Count2;
		*Key = Keys[FANOUT/2];
		*Ptr = Alloc(Index)++;
		if(Node->LeafNode) {  /* insert in sequential linked list */
			NNode.Ptrs[0] = Node->Ptrs[0];
			Node->Ptrs[0] = *Ptr;
		}
		if (DEBUG == 1)
			cout << "Write to Block Function where Block equals: " << *Ptr << endl;
		WriteBlock(File(Index), *Ptr, BLKSIZE, &NNode);
		WriteHead(Index);
	}
	return Count2;
}

//Used to creat new buckets when inserting duplicate keys.
static int NewBucket(int Index, int Ptr, int Next) {
	if (DEBUG == 1)
		cout << "New Bucket Function " << endl;

	int BBlk;
        int j;
	BucketType Bucket;

	Bucket.Pointers[0] = Ptr;
    Bucket.Pointers[1] = -1;
	Bucket.NextBucket = Next;
	Bucket.BucketId = BKTNUM + 1;
	if (DEBUG == 1)
		cout << "Bucket Id: " << Bucket.BucketId << endl;
	BBlk = Alloc(Index)++;
	WriteBlock(File(Index), BBlk, BLKSIZE, &Bucket);
	WriteHead(Index);
	return BBlk;
}

static int Error;

//Record Insert, is called by the insert funciton to insert the key at the right place and to split the tree
// if needed
static int RecInsert(int Index, int Block, int *Key, int *Ptr) {

	if (DEBUG == 1)
	{
		cout<<"RecInsert Function"<<endl;
	    cout<<"Block from Insert: "<< Block<<endl;
	}

	TreeNode Node;
	int KIdx, Split = 0;
	int EqualKey;

	ReadBlock(File(Index), Block, BLKSIZE, &Node);

	KIdx = FindKey(&Node, *Key);

	EqualKey = KIdx && Node.Keys[KIdx-1] == *Key;

	if (DEBUG == 1)
		cout << "The Key equals: " << EqualKey << endl;

	if(!Node.LeafNode)
	{
		Split = RecInsert(Index, Node.Ptrs[KIdx], Key, Ptr);
		if (DEBUG == 1)
			cout << "Not the Leaf Node, Call Split recursively: " << Split << endl;
	}

	if(Split || Node.LeafNode && !EqualKey)
	{
		if(Node.LeafNode && Dups(Index))
			*Ptr = NewBucket(Index, *Ptr, -1);

		Split = InsertKey(Index, &Node, KIdx, Key, Ptr);
		if (DEBUG == 1)
			cout << "Leaf Node, Call Split from Insert Key: " << Split << endl;
		WriteBlock(File(Index), Block, BLKSIZE, &Node);
	}
	else if(Node.LeafNode && Dups(Index))
	{
	 	if (DEBUG == 1)
	    	cout << "Inserting when considering Duplicate Keys" << endl;

		BucketType Bucket;
		int i;
		ReadBlock(File(Index), Node.Ptrs[KIdx], BLKSIZE, &Bucket);

		for(i = 0; i < BKTPTRS && Bucket.Pointers[i] >= 0; i++);
		if(i < BKTPTRS)
		{
		    Bucket.Pointers[i] = *Ptr;
		    if(i < BKTPTRS-1) Bucket.Pointers[i+1] = -1;
		    {
				if (DEBUG == 1)
					cout << "Write to Block Function where Block equals: " << Node.Ptrs[KIdx] << endl;
		    	WriteBlock(File(Index), Node.Ptrs[KIdx], BLKSIZE, &Bucket);
			}
		}
		else
		{
			cout << "ERROR: Bucket Overflow" << endl;
		}
	}
	else if(Node.LeafNode)
	{
		Error = -1;
	}
	return Split;
}

//first function called by the insert operation that initiliazes everything and assigne the appropriate variables
int Insert(int Index, int Key, int Ptr) {
	if (DEBUG == 1)
		cout << "Entering Insert Function" << endl;

	int Split;
	Error = 0;

	Split = RecInsert(Index, Root(Index), &Key, &Ptr);

	if(Split) {
		if (DEBUG == 1)
			cout << "Create New Tree Node if Split is true:" << Split << endl;
		TreeNode Node;
		Node.LeafNode = 0;
		Node.KeyCount = 1;
		Node.Keys[0] = Key;
		Node.Ptrs[1] = Ptr;
		Node.Ptrs[0] = Root(Index);
		Root(Index) = Alloc(Index)++;
		if (DEBUG == 1)
			cout << "Write to Block Function where Block equals: " << Root(Index) << endl;
		WriteBlock(File(Index), Root(Index), BLKSIZE, &Node);
		WriteHead(Index);
	}
	//cout<<"CBLK: "<< CBlk(Index)<<endl;

	CBlk(Index) = -1;
	//cout<<"CBLK: "<< CBlk(Index)<<endl;
	return Error;
}

//function is called to print out all the keys and their pointers as specified by the range
void LookupRange(int Index, int key1, int key2, char *filename )
{

	    int j;

		if (DEBUG == 1)
			cout << "Get values for a Range of Keys:" << endl;
		TreeNode Node;


		struct stat results;
		if(stat(filename, &results) == 0)
		{
			FILE_SIZE = results.st_size;
			TOTAL_BLOCKS = (FILE_SIZE - 40)/40;
			if (DEBUG == 1)
			{
				cout<<"Total Blocks: "<<TOTAL_BLOCKS<<endl;
				cout<<"File Size: "<<FILE_SIZE<<endl;
			}
		}
		else
			cout<<"Error Opening File"<<endl;

		for(int i = 1; i <= TOTAL_BLOCKS; i++)
		{
			ReadBlock(File(Index), i, BLKSIZE, &Node);

			if(Node.LeafNode)
			{
				if (DUPLICATES == 1)
				{
					for (int k = 0; k < Node.KeyCount; k++)
					{
						if(Node.Keys[k] >= key1 && Node.Keys[k] <= key2 )
						{
							CKey(Index) = k;
							cout << "\nKey: " << Node.Keys[k] << "  pointers:  ";
							ReadBlock(File(Index), Node.Ptrs[CKey(Index) + 1], BLKSIZE, &Bucket);
							j=0;
							while (Bucket.Pointers[j] != -1)
							{
								CPtr(Index) = j;
								cout << Bucket.Pointers[CPtr(Index)] << ", ";
								j++;

							}
						}

					}

				}

				else
				{
				 //cout << "Node.KeyCount " << Node.KeyCount
					for (int k = 0; k < Node.KeyCount; k++)
					{
						if(Node.Keys[k] >= key1 && Node.Keys[k] <= key2 )
						{
							CKey(Index) = k;
							cout << "\nKey: " << Node.Keys[k] << " Pointer: " << Node.Ptrs[CKey(Index) + 1];
						}

					}
			    }

			}

		}
		cout << "\n";

	return;
}

//MAIN

int main(int argc, char *argv[])
{
	//varaible decleration
	char inputToks[20][100];
	char inputText[50];
	char *token;
	int inserted_key;
	int lookup_key = 0;
	int lookup_key2 = 0;
	int data;
	int  XEntryNum;
	int RetnCode;
	int XPtr;
	int j;

	char *filename = argv[1];
	DUPLICATES  = atoi(argv[2]);
	DEBUG = atoi(argv[3]);


	if (DEBUG == 1)
		cout << "Debug mode is on:" << endl;

    XEntryNum = OpenTree(filename, DUPLICATES);

	cout << "XEntryNum = " << XEntryNum << endl;

	// while loop to get all the required information from the user and descarding unnessary characterss
	do
	{
		if (DEBUG == 1)
			cout << "Enter the command, Lookup or Insert" << endl;
		cin.getline(inputText,1000);
		token = strtok(inputText, " (,)");
		int numToks = 0;

		while(token != NULL)
		{
			strcpy(inputToks[numToks], token);
			token = strtok(NULL, " (,)");
			numToks++;
		}

		if(strcmp(strupr(inputToks[0]), "LOOKUP") == 0) // checking for look up and calling the functions
		{
			lookup_key2 = 0;

			lookup_key = atoi(inputToks[1]);
			lookup_key2 = atoi(inputToks[2]);

			if(lookup_key2 != 0 )
				LookupRange(XEntryNum,lookup_key,lookup_key2, filename);

			else
			{
				XPtr = Lookup(XEntryNum, lookup_key);



				// also print out single values for the first token.
				if (DUPLICATES == 0)
						 cout << "Key value is: " << lookup_key << " and Ptr value is: " << XPtr<< endl;

				if (DUPLICATES == 1) {
						 j = 0;
						 while (Bucket.Pointers[j] != -1)  {
							cout << "Ptr value is: " << Bucket.Pointers[j] << endl;
							j++;
						   }

				}
			}
		}
		else if (strcmp(strupr(inputToks[0]), "INSERT") == 0) // checking for insert and calling insert function
		{

			inserted_key = atoi(inputToks[1]);
			data = atoi(inputToks[2]);

			RetnCode = Insert(XEntryNum, inserted_key, data);

			if (RetnCode != 0)
              cout<<"Error During Key Insertion\n";

		}
		else if (strcmp(strupr(inputToks[0]), "EXIT") == 0) // to EXIT
		{
			cout << "Ending Program " << endl;
			CloseTree(XEntryNum);
		}
		else if (strcmp(strupr(inputToks[0]), "PRINT") == 0 &&
		strcmp(strupr(inputToks[1]), "TREE") == 0) // To PRINT TREE
		{
			//cout << "Print Tree " << endl;
			print(XEntryNum,filename);
		}
		else
		{
			cout << "Unknown Command: Please Try Again" << endl;
		}
	} while(strcmp(strupr(inputToks[0]), "EXIT") != 0);



return 0;
}