/* Filename: BTree.h
 *
 * Programmer: Papaloukopoulos K. George and S.Sioutas
 *
 * Date: June 23, 2006
 * Last Update: October 1, 2006
 * 
 */

#ifndef __LLNODE_H__
#define __LLNODE_H__

#include "Disk.h"

using namespace std;
const int MAX_KEYS = 8;
extern Disk * D;


/* Given:   Nothing.
 *           
 * Task:    
 *
 * Return:  The implicit LLNode object.
 */
template <class T>
class LLNode {
	public:
		long location;
		long prevNodeLoc;
		long nextNodeLoc;
		int nodeSize;
		int listSize;
		T keys[MAX_KEYS];
		
	public:
		LLNode ();
		LLNode<T> * search (T key);
		long insert (T key);
		long remove (T key);
		long getNodeLocation();
		T getNodeFirstKey();
		LLNode<T> * splitList (LLNode<T> * head);
		void fuseList (LLNode<T> * dest, LLNode<T> * with);
		void transferList (LLNode<T> * dest, LLNode<T> * from);

	private:
		void split (LLNode<T> * node);
		void fuse (LLNode<T> * dest, LLNode<T> * with);
		void transfer (LLNode<T> * dest, LLNode<T> * from);	
};

/* Given:   Nothing.
 *           
 * Task:    
 * 	
 * Return:  The implicit LLNode object.
 */
template <class T>
LLNode<T>::LLNode () {
	location = 0;
	prevNodeLoc = -1;
	nextNodeLoc = -1;
	nodeSize = 0;
	listSize = 0;
}

/* Given:   Nothing.
 *           
 * Task:    
 *
 * Return:  The location of this node into the disk.
 */
template <class T>
long LLNode<T>::getNodeLocation() {

	return this->location;
}

/* Given:   Nothing.
 *           
 * Task:    
 * 
 * Return:  The first key of this node.
 */
template <class T>
T LLNode<T>::getNodeFirstKey() {

	return this->keys[0];
}

/* Given:   A key.
 *           
 * Task:    
 *
 * Return:  
 */
template <class T>
LLNode<T> * LLNode<T>::search(T key) {

	int i = 0;

	//cout<<"LLNode: search = "<<location<<endl;
    	if (nodeSize == 0)
        	return this;

	for (i = 0; i < nodeSize && key < keys[i]; i++)
		return this;

	//if (nodeSize == MAX_KEYS && nextNodeLoc != -1) {
	if (nextNodeLoc != -1) {
		LLNode<T> * nextNode = new LLNode<T>();
		D->read((char *)nextNode, sizeof(LLNode<T>), nextNodeLoc);
		//cout<<"LLNode: search2 = "<<location<<endl;
		if (key < nextNode->keys[0])
			return this;
		else
			return nextNode->search(key);	//continue searching to the next LL node
	}
	else {
		//cout<<"LLNode: search return "<<endl;
		return this;
	}
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
long LLNode<T>::insert(T key) {

	int i = 0;
	LLNode<T> * node = new LLNode<T>();
	
	node = search(key);
	//cout<<"LLNode: loc = "<<node->location<<" nodeSize="<<node->nodeSize<<endl;
	//check if the key is already inserted
	for (i = 0; i < node->nodeSize; i++) {
		//cout<<node->keys[i]<<" ";
		if (node->keys[i] == key)
			return -1;
	}
	//cout<<endl;
	
	if (node->nodeSize < MAX_KEYS) {
		for (i = node->nodeSize; i >= 1 && key < node->keys[i-1]; i--)
			node->keys[i] = node->keys[i-1];

		node->keys[i] = key;
		node->nodeSize++;
		D->write((char *)node, sizeof(LLNode<T>), node->location);

        	//cout<<"LLNode: loc = "<<node->location<<endl;
		return node->location;
	}
	else {
		node->split(node);
		node->insert(key);
	}
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
long LLNode<T>::remove (T key) {

	int j = 0, i = 0;
	bool flag = false;
	LLNode<T> * node = new LLNode<T>();

	node = search(key);
	for (i = 0; i < node->nodeSize; i++) {		//find the key's position
		//cout<<node->keys[i]<<" ";
		if (key == node->keys[i]) {
			flag = true;
            		break;
		}
	}	
	if (flag == false) {	//the key is not into the node
		//cout<<"EMPTY"<<endl;
		//free(node);
		return -1;
	}
    	//cout<<endl<<"LLNode: remove nodeLoc = "<<node->location<<" nodeSize="<<node->nodeSize<<endl;
    	//cout<<"LLNode: remove key = "<<node->keys[i]<<" key="<<key<<endl;
	for (j = i; j < node->nodeSize-1; j++)					//shift the keys to the right position
		node->keys[j] = node->keys[j+1];

	node->nodeSize--;
	D->write((char *)node, sizeof(LLNode<T>), node->location);

	if (node->nodeSize < MAX_KEYS/2) {
		//cout<<"Node has few keys"<<endl;
		if (node->prevNodeLoc != -1) {
			LLNode<T> * prevNode = new LLNode<T>();
			D->read((char *)prevNode, sizeof(LLNode<T>), node->prevNodeLoc);

			if ((prevNode->nodeSize + node->nodeSize) <= MAX_KEYS) {
				//cout<<"Fuse node with prevNode"<<endl;
				fuse(prevNode, node);
			}
			else {
				//cout<<"Transfer keys from prevNode"<<endl;
				transfer(node, prevNode);
			}
			//free(prevNode);
		}
		else if (node->nextNodeLoc != -1) {
			LLNode<T> * nextNode = new LLNode<T>();
			D->read((char *)nextNode, sizeof(LLNode<T>), nextNodeLoc);

			if ((nextNode->nodeSize + node->nodeSize) <= MAX_KEYS) {
				//cout<<"Fuse node with nextNode"<<endl;
				fuse(node, nextNode);
			}
			else {
				//cout<<"Tranfer keys form nextNode"<<endl;
				transfer(node, nextNode);
			}
			//free(nextNode);
		}
	}
	//free(node);
	return 1;
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
void LLNode<T>::split (LLNode<T> * fullNode) {

	int i = 0;
	int j = MAX_KEYS/2;
	LLNode<T> * newNode = new LLNode<T>();

	for (i = 0; i < j; i++)
		newNode->keys[i] = fullNode->keys[j+i];

	newNode->location = D->getFreeDiskBlock(sizeof(LLNode<T>));				//freeDiskLoc
	newNode->nodeSize = fullNode->nodeSize = j;
	newNode->nextNodeLoc = fullNode->nextNodeLoc;
	newNode->prevNodeLoc = fullNode->location;
	fullNode->nextNodeLoc = newNode->location;

	//cout<<"LLNode: split = "<<newNode->keys[0]<<endl;
	D->write((char *)fullNode, sizeof(LLNode<T>), fullNode->location);		//mallon den xreiazetai, ginetai apo to insert
	D->write((char *)newNode, sizeof(LLNode<T>), newNode->location);
	//free(newNode);
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
void LLNode<T>::transfer (LLNode<T> * destNode, LLNode<T> * fromNode) {

	int i = 0;
	int j = (int)round((fromNode->nodeSize - MAX_KEYS/2)/2);

	if (fromNode->keys[0] < destNode->keys[0]) {	//transfer from prevNode
		
		for (i = destNode->nodeSize-1; i >= 0; i--) 
			destNode->keys[i+j] = destNode->keys[i];
		for (i = 0; i < j; i++)
			destNode->keys[i] = fromNode->keys[MAX_KEYS/2+j+i];
	}
	else {	//transfer from nextNode
		for (i = 0; i < j; i++)
			destNode->keys[destNode->nodeSize + i] = fromNode->keys[i];
		for (i = 0; i < fromNode->nodeSize-j; i++)
			fromNode->keys[i] = fromNode->keys[i+j];
	}

	destNode->nodeSize += j;
	fromNode->nodeSize -= j;

	D->write((char *)destNode, sizeof(LLNode<T>), destNode->location);
	D->write((char *)fromNode, sizeof(LLNode<T>), fromNode->location);
	//free(destNode);
	//free(fromNode);
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
void LLNode<T>::fuse (LLNode<T> * destNode, LLNode<T> * fromNode) {

	int i = 0;
	int j = fromNode->nodeSize;
	
	for (i = 0; i < j; i++) {
		destNode->keys[destNode->nodeSize + i] = fromNode->keys[i];

		destNode->nextNodeLoc = fromNode->nextNodeLoc;
		if (fromNode->nextNodeLoc != -1) {
			LLNode<T> * node = new LLNode<T>();
			D->read((char *)node, sizeof(LLNode<T>), fromNode->nextNodeLoc);
			node->prevNodeLoc = destNode->location;
			D->write((char *)node, sizeof(LLNode<T>), node->location);
			//free(node);
		}
	}
	destNode->nodeSize += fromNode->nodeSize;

	D->write((char *)destNode, sizeof(LLNode<T>), destNode->location);
	//free(destNode);
	//free(fromNode);
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
LLNode<T> * LLNode<T>::splitList (LLNode<T> * head) {

	int i = 0;
	int sum = head->nodeSize;
	int listSize = head->listSize;
	LLNode<T> * dummy = new LLNode<T>();
	LLNode<T> * newHeadList = new LLNode<T>();


	dummy = head;
	while(sum < listSize/2 && (listSize/2 - sum) >= MAX_KEYS/2) {
		D->read ((char *)dummy, sizeof(LLNode<T>), dummy->nextNodeLoc);
		sum += dummy->nodeSize;
	}
	head->listSize = sum;
	D->read ((char *)newHeadList, sizeof(LLNode<T>), dummy->nextNodeLoc);
	newHeadList->listSize = listSize - sum;
	head->nextNodeLoc = newHeadList->prevNodeLoc = -1;

	D->write((char *)head, sizeof(LLNode<T>), head->location);
	D->write((char *)newHeadList, sizeof(LLNode<T>), newHeadList->location);
	//free(dummy);
	
	return newHeadList;
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
void LLNode<T>::fuseList (LLNode<T> * dest, LLNode<T> * with) {

	LLNode<T> * dummy = new LLNode<T>();

	dummy = dest;
	while (dummy->nextNodeLoc != -1)
		D->read ((char *)dummy, sizeof(LLNode<T>), dummy->nextNodeLoc);
	
	dummy->nextNodeLoc = with->location;
	with->prevNodeLoc = dummy->location;
	dest->listSize += with->listSize;
	//cout<<"Fuse dummy->keys[0]="<<dummy->keys[0]<<" dummy->nextNodeLoc="<<dummy->nextNodeLoc<<endl;
	//cout<<"Fuse dummy->location="<<dummy->location<<" dest->location="<<dest->location<<endl;
	D->write((char *)dummy, sizeof(LLNode<T>), dummy->location);

	//if (dummy->location != dest->location)
	D->write((char *)dest, sizeof(LLNode<T>), dest->location);
	D->write((char *)with, sizeof(LLNode<T>), with->location);
	//free(dummy);
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <class T>
void LLNode<T>::transferList (LLNode<T> * dest, LLNode<T> * from) {

	int sum = 0;
	int tmp = from->nodeSize;
	LLNode<T> * dummy = new LLNode<T>();
	LLNode<T> * tail = new LLNode<T>();

	if (dest->keys[0] < from->keys[0]) {			//borrow keys from the next list 	

		tail = dest;
		while (tail->nextNodeLoc != -1)
			D->read ((char *)tail, sizeof(LLNode<T>), tail->nextNodeLoc);

		tail->nextNodeLoc = from->location;
		if (tail->location != dest->location)
			D->write((char *)tail, sizeof(LLNode<T>), tail->location);

		from->prevNodeLoc = tail->location;

		dest->listSize += from->nodeSize;

		D->read ((char *)dummy, sizeof(LLNode<T>), from->nextNodeLoc);
		dummy->listSize = from->listSize - from->nodeSize;
		from->nextNodeLoc = -1;
		D->write((char *)from, sizeof(LLNode<T>), from->location);
		dummy->prevNodeLoc = -1;

		*from = *dummy;
		//cout<<"1).From->keys[0]="<<from->keys[0]<<endl;
	}
	else { 							//borrow keys from the previous list
		
		tail = from;
		while (tail->nextNodeLoc != -1)
			D->read ((char *)tail, sizeof(LLNode<T>), tail->nextNodeLoc);

		tail->nextNodeLoc = dest->location;
		dest->prevNodeLoc = tail->location;
		D->write((char *)dest, sizeof(LLNode<T>), dest->location);

		tail->listSize = dest->listSize + tail->nodeSize;
		
		if (tail->prevNodeLoc != from->location) {
			D->read ((char *)dummy, sizeof(LLNode<T>), tail->prevNodeLoc);
			dummy->nextNodeLoc = -1;
			D->write((char *)dummy, sizeof(LLNode<T>), dummy->location);
		}
		else
			from->nextNodeLoc = -1;

		from->listSize -= tail->nodeSize;
		tail->prevNodeLoc = -1;

		*dest = *tail;
		//cout<<"1).Dest->keys[0]="<<dest->keys[0]<<endl;
	}
	D->write((char *)from, sizeof(LLNode<T>), from->location);
	D->write((char *)dest, sizeof(LLNode<T>), dest->location);
	//free(dummy);
	//free(tail);
}


#endif
