/* Filename: BTree.h
 *
 * Programmer: Papaloukopoulos K. George and S.Sioutas
 *
 * Date: June 23, 2006
 *
 * This header file implements the BTree template class. It contains 
 * a nested template class named BTNode which is the structural element 
 * of the the external B-tree. It has been modified for the Lazy B-tree.
 */

#ifndef __BTREE_H__
#define __BTREE_H__

#include <iostream>
#include "Disk.h"

using namespace std;

namespace btr {
				//the operation codes used for the rebalancing operations:
const int NON = 0;		//it is not necessary to be done any rebalancing operation
const int INFE = 1;		//it is necessary to be done split operations
const int DNFE = 2;		//it is necessary to be done merge/transfer operations
	
const int SIZE = 5;		
const int HALF_KEYS = SIZE-1;	//minimum numbers of keys to be stored into a B-tree node
const int MAX_KEYS = 2*SIZE-1;	//maximum numbers of keys to be stored into a B-tree node
const int MAX_PTRS = 2*SIZE;	//maximum numbers of pointers to be stored into a B-tree node

long rootLocation;		//the offset which is stored the root of the tree into the file
int numOfNodes;			//the number of nodes which are stored into the file
int opCode;			//the operation code used for the rebalancing operations
Disk * D;			//an instance of disk class


/* Given:   Nothing.
 *           
 * Task:    Defines the prototype classes BTree and BTNode.
 *	    Also defines the methods and the data members of 
 *	    those classes.	
 * Return:  The implicity BTree object.
 */
template <class T>
class BTree {
	
	private:
		template <class U>
		class BTNode {

			public:
				BTNode();
				void insert (U key, long bucketLoc);
				void remove (U key);
				bool search (U key);
			
				//void deleteFullEnough (U key);
				void split (BTNode<U> * parent, int position);
				void moveKey (int keyPos, BTNode<U> * sibling, int parentPos, BTNode<U> * parent, int position);
				void merge (BTNode<U> * sibling, BTNode<U> * parent, int position);
		
			public:
				long location;			//the offset where the node has been stored
				long parentLoc;			//parent's offset	
				bool isLeaf;			//true if it is leaf
				int num;			//how many keys are stored in this node	
				U keys[MAX_KEYS];		//the keys which are stored
				long childLoc[MAX_PTRS];	//locations which point to node's children
		};

	protected:
		BTNode<T> * root;				//pointer to the root of the tree	
		BTNode<T> * rebNode;				//node which has to be rebalanced
		T rebKey;					//the deleted key which cause the rebalancing
	public:
		BTree();
		~BTree();
		bool isEmpty ();				//true if the data structure is empty
		void rebalancing( );				//it is necessary to be done after insertion or deletion
		void insert(T key, long bucketLoc);		//insert a representative key o a bucket and its location
		void remove(T key);				//remove a key from the data structure
		long find(T key);				//return the offset of a node where the key lie
		void display ();				//display the data structure
		BTNode<T> * search(T key);			//return the node where the key lie
		void replaceKey(T repKey, T key);		//replace a key into one node
	private:
		void insertNotFullEnough (BTNode<T> * splitNode);
		void deleteNotFullEnough (BTNode<T> * parent, T key, BTNode<T> * child);
};

/* Given:   Nothing. 
 *           
 * Task:    This is the constructor. Look if there are arleady stored data 	
 *	    and if so, read the root of the tree. If not, then instantiate
 *	    a disk object and construct the root of the tree.
 * Return:  The implicity BTNode object.
 */
template <class T>
BTree<T>::BTree() {

	FILE * file = fopen("BT.bin","r");
	
	if (file) {		
		fclose(file);
		D = new Disk("BT.bin");
		D->read((char *)&rootLocation, sizeof(long), 0);	
		D->read((char *)&numOfNodes, sizeof(int), sizeof(long));
		//cout<<"~ "<<rootLocation<<" "<<numOfNodes<<endl;
		root = new BTNode<T>();
		D->read((char *)root, sizeof(BTNode<T>), rootLocation);
	}
	else {
		D = new Disk("BT.bin");
		numOfNodes = 1;
		rootLocation = sizeof(BTNode<T>);		
		//cout<<"$$ "<<rootLocation<<" S "<<sizeof(BTNode<T>)<<endl;
		root = new BTNode<T>();						
		root->location = root->parentLoc = rootLocation;
		root->childLoc[0] = 0;						//!!! it is for the fist bucket
		D->write((char *)root, sizeof(BTNode<T>), rootLocation);
	}
}


/* Given:   Nothing.
 *           
 * Task:    This is the deconstructor. Look if any rebalancing operation is need 
 *	    to be done and if so, the do it. Then store the root location and the
 *	    number of nodes at the beginig of the file. Also call the deconstructor
 *	    of the Disk class to close the io streams.
 * Return:  Nothing.
 */
template <class T>
BTree<T>::~BTree() {

	while (opCode != NON)
		rebalancing();

	//cout<<"END-->"<<rootLocation<<" "<<numOfNodes<<endl;
	D->write((char *)&rootLocation, sizeof(long), 0);
	D->write((char *)&numOfNodes, sizeof(int), sizeof(long));	
	//cout<<"OK"<<endl;
	D->~Disk();
}

/* Given:   Nothing.
 *           
 * Task:    Check if the data structure is empty, if so, returns true, else returns false
 *	    
 * Return:  true or false.
 */
template <class T>
bool BTree<T>::isEmpty() {

	if (root->num == 0)
		return true;
	else
		return false;
}


/* Given:   Key, the value we want to store into the tree.
 *          bucketLoc, the offset into the disk which is stored the apropriate bucket. 
 * Task:    Check if there is already exist this key. If not then find the node where 
 *	    the key must be stored and do the operation. If the key exist, return.	
 * Return:  Nothing.
 */
template <class T>
void BTree<T>::insert (T key, long bucketLoc) {
	
	BTNode<T> * inNode = new BTNode<T>();
	rebNode = inNode = search (key);
	//cout<<"location: "<<inNode->location<<endl;
	if (!inNode->search(key))
		inNode->insert (key, bucketLoc);

	while (opCode != NON)						//these lines are not necessary if the data structure
		rebalancing();						//is not part of the LBT
	//cout<<"** "<<key<<endl;
}


/* Given:   Key, the value we want to remove from the tree.
 *          
 * Task:    Check if there is into the tree. If yes then remove it.
 * 	    If not, return. 	
 * Return:  Nothing.
 */
template <class T>
void BTree<T>::remove (T key) {

	BTNode<T> * reNode = new BTNode<T>();
	rebNode = reNode = search (key);
	/*cout<<"Key: "<<key<<endl;
	for (int i = 0; i < reNode->num; i++)
		cout<<reNode->keys[i]<<" ";
	cout<<endl;*/
	if (reNode->search(key)) {
		//cout<<"R"<<key<<endl;
		reNode->remove (key);
	}

	rebKey = key;
	while (opCode != NON)					//these lines are necessary if the data structure
		rebalancing();					//is part of the LBT
}


/* Given:   Key, the value we want to find.
 *           
 * Task:    Check if there is exist this key into the tree. If exists,  
 *	    then return the the specified node.	
 * Return:  Returns the node which is stored the key.
 */
template <class T>
BTree<T>::BTNode<T> * BTree<T>::search (T key) {

	int i = 1;
	BTNode<T> * node = new BTNode<T>();	
	D->read((char *)node, sizeof(BTNode<T>), rootLocation);

	while (!node->isLeaf) {

		while (i <= node->num && key > node->keys[i-1]) 
			i += 1;

		D->read((char *)node, sizeof(BTNode<T>), node->childLoc[i-1]);
		i = 1;
	}
	return node;
}


/* Given:   Key, the value we want to find.
 *           
 * Task:    Search into the tree until reach to the corresponding leaf.  
 * 	    Then search into the corresponding node to find the bucket
 * 	    where the key must be stored.
 * Return:  Returns the offset where the bucket is stored.
 */
template <class T>
long BTree<T>::find (T key) {

	int i = 1;
	BTNode<T> * node = new BTNode<T>();	
	D->read((char *)node, sizeof(BTNode<T>), rootLocation);

    	//cout<<"BTREE: find rootLocation= "<<rootLocation<<endl;
	while (!node->isLeaf) {

		while (i <= node->num && key > node->keys[i-1]) 
			i += 1;

		D->read((char *)node, sizeof(BTNode<T>), node->childLoc[i-1]);
		i = 1;
	}
	
	i = 0;
	//BTNode<T> * node = this;
	while (i < node->num && key > node->keys[i])
		i++;
	
    	//cout<<"BTREE: childLoc = "<<node->childLoc[i]<<endl;
	return node->childLoc[i];
}

template <class T>
void BTree<T>::replaceKey(T repKey, T key) {

	int i = 0;
	BTNode<T> * node = search(repKey);

	for (i = 0; i < node->num; i++)
		if (node->keys[i] == repKey)
			node->keys[i] = key;

	D->write((char *)node, sizeof(BTNode<T>), node->location);
}

/* Given:   Nothing.
 *           
 * Task:    To look for if it is need to be done any reballancing operation.
 *	    If so, then do the apropriate operation. With this method we 
 *	    achieve to rebalance the B-tree step by step, without to be nessecery
 *	    to be done in one step. Its a trick used by the Lazy B-tree.
 * Return:  Nothing.
 */
template <class T>
void BTree<T>::rebalancing() {
	
	if (opCode == NON)
		return;
	else if (opCode == INFE)
		insertNotFullEnough (rebNode);
	else if (opCode == DNFE) {
		BTNode<T> * parent = new BTNode<T>();
		D->read((char *)parent, sizeof(BTNode<T>), rebNode->parentLoc);
		deleteNotFullEnough(parent, rebKey, rebNode);
	}
}

/* Given:   SplitNode, a pointer to a BTNode object. This node
 *          needs rebalancing, split. 
 * Task:    Check if the given node is the current root of the tree and check
 *	    if it is full. If it is full then split it. This means that the height 
 *	    of the tree grows up by one and a new root is constructing. Else check
 *	    if the given root is full and split it, if so.
 * Return:  Nothing.
 */
template <class T>
void BTree<T>::insertNotFullEnough(BTNode<T> * splitNode) {

	int i = splitNode->num;
	
	opCode = NON;
	//cout<<"RL "<<rootLocation<<" loc "<<splitNode->location<<endl;
	if (rootLocation  == splitNode->location && splitNode->num == MAX_KEYS) {		//root is full and it is need to be split
		BTNode<T> * newRoot = new BTNode<T>();
		numOfNodes++;
		newRoot->location = numOfNodes*sizeof(BTNode<T>);		//new root
		newRoot->isLeaf = false;
		newRoot->num = 0;
		newRoot->childLoc[0] = splitNode->location;
		newRoot->parentLoc = newRoot->location;			//root has not parent

		//this->split(newRoot, 0);
		splitNode->split(newRoot, 0);
		
		rootLocation = newRoot->location;
		D->read((char *)root, sizeof(BTNode<T>), rootLocation);
	}
	else if (splitNode->num == MAX_KEYS) {				//check if the leaf is full

		//find the parent node of leaf
		BTNode<T> * parentNode = new BTNode<T>();
		D->read((char *)parentNode, sizeof(BTNode<T>), splitNode->parentLoc);

		i = parentNode->num;
		while (i >= 1 && splitNode->keys[HALF_KEYS] < parentNode->keys[i-1])	//find the place where the leaf's midle key will be placed
			i--;

		splitNode->split(parentNode, i);
		opCode = INFE;
		rebNode = parentNode;
		//parentNode->insertNotFull();
	}
}         

/* Given:   Key, the value to look for in the current node.
 *           
 * Task:    To look for in the current node if exists.
 *
 * Return:  Nothing.
 */
template <class T>
void BTree<T>::deleteNotFullEnough(BTNode<T> * parent, T key, BTNode<T> * child) {
	
	int i = 1;
	BTNode<T> * leftSibling = new BTNode<T> (); 
	BTNode<T> * rightSibling = new BTNode<T> ();
	//Node * grandFather = new Node ();

	opCode = NON;
	while ( i <= parent->num && key > parent->keys[i-1] )
		i++;

	if (i >= 2)
		D->read((char *)leftSibling, sizeof(BTNode<T>), parent->childLoc[i-2]);
	if (i <= parent->num)
		D->read((char *)rightSibling, sizeof(BTNode<T>), parent->childLoc[i]);

	if (leftSibling->num > HALF_KEYS)
		child->moveKey(leftSibling->num-1, leftSibling, i-2, parent, 0);
	else if (rightSibling->num > HALF_KEYS)
		child->moveKey(0, rightSibling, i-1, parent, child->num);
	else if (leftSibling->num > 0) 
		leftSibling->merge(child, parent, i-2); 
	else 
		child->merge(rightSibling, parent, i-1);	

	if (parent->num < HALF_KEYS && parent->location != root->location) {
		//cout<<"----"<<endl;
		//read((char *)grandFather, sizeof(Node), parent->parentLoc);
		//parent->deleteNotFullEnough(grandFather, key);
		opCode = DNFE;
		rebNode = parent;
		//rebKey = key;
	}

	//BTNode<U> * root = new BTNode<U>();
	D->read((char *)root, sizeof(BTNode<T>), rootLocation);
	
	if (root->num == 0 && !root->isLeaf) {
		rootLocation = root->childLoc[0];		//reduce height of tree 
		D->read((char *)root, sizeof(BTNode<T>), rootLocation);
		//root->parentLoc = rootLocation;
		//D->write((char *)root, sizeof(BTNode<T>), rootLocation);
	}
	//cout<<"root->num: "<<root->num<<"    key: "<<key<<endl;
}

/* Given:   Nothing.
 *           
 * Task:    It displays all the nodes of the tree and their contents.
 *	    It is used for checking and testing. 
 * Return:  Nothing.
 */
template <class T>
void BTree<T>::display () {

	int j = 0;
	Disk * D = new Disk("BT.bin");

	BTNode<int> n[numOfNodes];
	
	for (int j = 0; j < numOfNodes; j++) {
		//n[j]= new BTNode<int>();

		D->read((char *)&n[j], sizeof(BTNode<int>), (j+1)*sizeof(BTNode<int>));
		
		if (n[j].num != 0) {
			cout<<"------ Node-"<<j<<" -----"<<endl;
			cout<<"leaf: "<<n[j].isLeaf<<endl;
			cout<<"parent: "<<n[j].parentLoc<<endl;
			cout<<"location: "<<n[j].location<<endl;
			//if (!n[j]->isLeaf) {
				cout<<"child_location: ";
				for (int i = 0; i<= n[j].num; i++)
					cout<<" "<<n[j].childLoc[i];
				cout<<endl;
			//}
			cout<<"num: "<<n[j].num<<endl;
			cout<<"key:";
			for (int i = 0; i < n[j].num; i++)
				cout<<" "<<n[j].keys[i];
			cout<<endl;
		}
		
	}
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*		METHOD DEFINITION OF NESTED CLASS BTNODE                 */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* Given:   Key, the value to look for in the current node.
 *           
 * Task:    To look for in the current node if there is exist.
 *
 * Return:  Nothing.
 */
template <class T>
template <class U>
BTree<T>::BTNode<U>::BTNode () {
	
	isLeaf = true;
	num = 0;
}


/* Given:   Key, the value to look for in the current node.
 *           
 * Task:    To look for in the current node if it is exist.
 *	    If it finds returns true otherwise false.
 * Return:  True if the key is in this node otherwise false.
 */
template <class T>
template <class U>
bool BTree<T>::BTNode<U>::search(U key) {

	int i = 1;
 	/*static BTNode * nextNode = new BTNode();	

	//cout<<"this->location: "<<location<<endl;
	while (i <= num && key > keys[i-1])
		i += 1;
	 
	if (!isLeaf) {
		D->read((char *)nextNode, sizeof(Node), childLoc[i-1]);
		return nextNode->search(key);
	}
	else 
		return this;
	*/

	for (i = 0; i < num; i++) 
		if (key == keys[i])
			return true;
	if (i == num)
		return false;
}

/* Given:   parent, a pointer to BTNode object. It is the the parent node of the current node.
 *          position, is the position of the key into the parent's node which drives to the current node.
 * Task:    Construct a new node and by spliting the current to two equal size nodes and put into
 *	    the parent node the represantative key of the new node at the position+1. 
 * Return:  Nothing.
 */
template <class T>
template <class U>
void BTree<T>::BTNode<U>::split(BTNode<U> * parent, int position) {

	int j;
				
	BTNode<U> * z = new BTNode<U>();
	numOfNodes++;
	z->location = numOfNodes*sizeof(BTNode<U>);		
	z->isLeaf = isLeaf;
	z->num = HALF_KEYS;
	parentLoc = parent->location;
	z->parentLoc = parent->location;
	
	for (j = 0; j < HALF_KEYS; j++) {
		z->keys[j] = keys[j+HALF_KEYS+1];
		z->childLoc[j] = childLoc[j+HALF_KEYS+1];
	}
	z->childLoc[j] = childLoc[j+HALF_KEYS+1];
	
	
	/*for (j = 0; j <= HALF_KEYS; j++)
		z->childLoc[j] = childLoc[j+HALF_KEYS+1];
	*/
	if (!isLeaf) 
	for (j = 0; j <= z->num; j++) {					
		BTNode<U> * child = new BTNode<U>();
		D->read((char *)child, sizeof(BTNode<U>), z->childLoc[j]);
		child->parentLoc = z->location;
		D->write((char *)child, sizeof(BTNode<U>), child->location);
	}
	
	/*num = HALF_KEYS+1;		
	if (!isLeaf) 
		num = HALF_KEYS;
	*/	
	num = HALF_KEYS;
	for (j = parent->num; j > position; j--) {
		parent->keys[j] = parent->keys[j-1];
		parent->childLoc[j+1] = parent->childLoc[j];
	}
	parent->childLoc[position+1] = z->location;
	parent->keys[position] = keys[HALF_KEYS];
	parent->num += 1;

	/*
	for (j = parent->num; j > position; j--)
		parent->keys[j] = parent->keys[j-1];
	parent->keys[position] = keys[HALF_KEYS];
	*/

	//cout<<"z "<<z->location<<endl;
	//cout<<"parent "<<parent->location<<endl;
	//cout<<"this "<<location<<endl;
	D->write((char *)this, sizeof(BTNode<U>), location);
	D->write((char *)parent, sizeof(BTNode<U>), parent->location);
	D->write((char *)z, sizeof(BTNode<U>), z->location);
}


/* Given:   Key, the value we want to insert into the node.
 *          bucketLoc, the offset which is stored the corresponding bucket. 
 * Task:    Inserts the key and the bucket's location into the current node.
 *
 * Return:  Nothing.
 */
template <class T>
template <class U>
void BTree<T>::BTNode<U>::insert(U key, long bucketLoc) {

	int i = num;
	
	while(i >= 1 && key < keys[i-1]) {			//put the key in the right place into the leaf
		keys[i] = keys[i-1];				//shift right
		childLoc[i+1] = childLoc[i];
		i--;
	}
	keys[i] = key;
	childLoc[i+1] = bucketLoc;
	num += 1;

	if (key == INT_MIN)
		num--;

	//cout<<num<<endl;
	D->write((char *)this, sizeof(BTNode<U>), location);

	opCode = INFE;
	//this->insertNotFull();
}


/* Given:   keyPos, is the position of the key into the sibling node which will be moved to its parent.
 *          sibling, is a pointer to BTNode object. Is the left/right sibling of the current node.
 *          parentPos, is the position of the represantative key which drives to the the current node.
 *          parent, is a pointer to BTNode object. Is the parent of the current node.
 *          pos, is the position in the current node where will put the moved key.
 * Task:    Moves a key from the sibling node to the parent node and from the parent 
 * 	    node to the current node.
 * Return:  Nothing.
 */
template <class T>
template <class U>
void BTree<T>::BTNode<U>::moveKey (int keyPos, BTNode<U> * sibling, int parentPos, BTNode<U> * parent, int pos) {

	int i;
	U temp;
	long childLocation = 0;
	
	if (keyPos == sibling->num-1) {		//take a key from the left site
		if (!sibling->isLeaf) {
			temp = parent->keys[parentPos];
			childLocation = sibling->childLoc[sibling->num];		
			parent->keys[parentPos] = sibling->keys[keyPos];
		}
		else {
			temp = sibling->keys[keyPos];
			parent->keys[parentPos] = sibling->keys[keyPos-1];
			childLocation = sibling->childLoc[sibling->num];
		}
	}
	else {
		temp = sibling->keys[keyPos];
		childLocation = sibling->childLoc[0];
		for (i = 0; i < sibling->num-1; i++) {
			sibling->keys[i] = sibling->keys[i+1];
			sibling->childLoc[i] = sibling->childLoc[i+1];
		}
		sibling->childLoc[i] = sibling->childLoc[i+1];
		/*if (!sibling->isLeaf) {
			childLocation = sibling->childLoc[0];			//if it's not leaf!	
			for (i = 0; i < sibling->num; i++)
				sibling->childLoc[i] = sibling->childLoc[i+1];
		}*/
	}
	sibling->num--;

	if (pos == num) {
		keys[pos] = temp;
		if (!isLeaf) 
			keys[pos] = parent->keys[parentPos];

		childLoc[pos+1] = childLocation;//		
		parent->keys[parentPos] = temp;
		num++;
	}
	else {
		for (i = num; i > 0; i--) {
			keys[i] = keys[i-1];
			childLoc[i+1] = childLoc[i];
		}
		childLoc[i+1] = childLoc[i];
		childLoc[0] = childLocation;
		keys[0] = temp;
		num++;
		/*if (!isLeaf) {
			for (i = num; i >= 0; i--)
				childLoc[i+1] = childLoc[i];
			childLoc[0] = childLocation;
		}*/
	}		
	
	if (!isLeaf) {
		BTNode<U> * child = new BTNode<U> ();	
		D->read((char *)child, sizeof(BTNode<U>), childLocation);
		child->parentLoc = location;
		D->write((char *)child, sizeof(BTNode<U>), child->location);
	}

	D->write((char *)parent, sizeof(BTNode<U>), parent->location);
	D->write((char *)sibling, sizeof(BTNode<U>), sibling->location);
	D->write((char *)this, sizeof(BTNode<U>), location);
}


/* Given:   sibling, a pointer to BTNode object. Is the left/right sibling node which will be merged with the current node.
 *          parent, a pointer to BTNode object. Is the parent node of the current node.
 *          position, is the position inside the parent node which determines the path which must be followed to find the
 *          left/right sibling.
 * Task:    Shift all the sibling's node keys and pointers to the current node. Also removes the corresponding
 *	    key, given by the variable position, from the parent node.	
 * Return:  Nothing.
 */
template <class T>
template <class U>
void BTree<T>::BTNode<U>::merge (BTNode<U> * sibling, BTNode<U> * parent, int position) {

	int j, i = num;	
	BTNode<U> * child = new BTNode<U> ();

	/*if (sibling->isLeaf) {
		for (j = 0; j < sibling->num; j++) 
			keys[num+j] = sibling->keys[j];		//move the keys from the node 'from' to the new node 'to'	
		num += sibling->num;
	}
	else {
	*/
	if (parent->num == 1)
		position = 0;
	keys[num] = parent->keys[position];			
	for (j = 0; j < sibling->num; j++) {
		keys[num+j+1] = sibling->keys[j];
		childLoc[num+j+1] = sibling->childLoc[j];
	}
	childLoc[num+j+1] = sibling->childLoc[j]; //sibling->childLoc[j+1];
	num += sibling->num + 1;
	//}

	if (!sibling->isLeaf) 			//if the node 'from' is internal node it is necessary to take care its children
	for (j = 0; j <= sibling->num; j++) {		//the parent location of these children will be assigned to the node location 'to'
		D->read((char *)child, sizeof(BTNode<U>), sibling->childLoc[j]);
		child->parentLoc = location;
		D->write((char *)child, sizeof(BTNode<U>), child->location);
	}
	
	for (j = position; j < parent->num-1; j++) {			//set the new order of keys at the parent node
		parent->keys[j] = parent->keys[j+1];
		parent->childLoc[j+1] = parent->childLoc[j+2];
	}
	parent->num--;
	
	//if (parent->num == 0) { 
	//	parentLoc = location;
	//	root->num = 0;
	//}
	if (parent->num == 0){ 
		BTNode<U> * root = new BTNode<U>();
		D->read((char *)root, sizeof(BTNode<U>), parent->location);
		root->num = 0;
		D->write((char *)root, sizeof(BTNode<U>), parent->location);
		rootLocation = parentLoc = location;
	}
		
	
	//-------------------
	//if a node has not any children is trash-node
	sibling->num = 0;
	D->write((char *)sibling, sizeof(BTNode<U>), sibling->location);
	//-------------------
	
	D->write((char *)parent, sizeof(BTNode<U>), parent->location);
	D->write((char *)this, sizeof(BTNode<U>), location);
}

/* Given:   Key, the value to remove form the current node.
 *           
 * Task:    To look for in the current node if there is exist.
 *	    If exist, then remove it by shiftin the other keys
 *	    to the right place and reduce the number of elements.
 * Return:  Nothing.
 */
template <class T>
template <class U>
void BTree<T>::BTNode<U>::remove (U key) {
	
	//deleteFullEnough (key);
	int j = 0;

	//cout<<"RM->"<<key<<" "<<num-1<<endl;
	for (j = 0; j < num-1; j++) 
		if (key <= keys[j]) {
			keys[j] = keys[j+1];
			childLoc[j+1] = childLoc[j+2];
		}

	num--;
	D->write((char *)this, sizeof(BTNode<U>), location);
	
	opCode = NON;
	if (num < HALF_KEYS && location != parentLoc) {	
		opCode = DNFE;
		//BTNode<U> * parent = new BTNode<U>();
		//D->read((char *)parent, sizeof(BTNode<U>), parentLoc);
		//deleteNotFullEnough(parent, key);
	}
}

}

#endif
