#ifndef __DLLNODE_H__
#define __DLLNODE_H__

#include "LLNode.h"

const int HALF_KEYS = MAX_KEYS/2;


/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>
class DLLNode {

	public:
		long location;
		long nextNodeLoc;
		long prevNodeLoc;
		int nodeSize;
		T keys[MAX_KEYS];
		long list[MAX_KEYS];

	public:
		DLLNode ();
		void insert (LLNode<T> * List);
		void remove (LLNode<T> * List);
		LLNode<T> * findLList (T key);
		DLLNode<T> * search (T key);
		void split(DLLNode<T> * fullNode);
	private:
		void fuse(DLLNode<T> * destNode, DLLNode<T> * fromNode);
		void transfer(DLLNode<T> * destNode, DLLNode<T> * fromNode);	
};

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>	
DLLNode<T>::DLLNode () {

	location = 0;
	prevNodeLoc = -1;
	nextNodeLoc = -1;
	nodeSize = 0;
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>
LLNode<T> * DLLNode<T>::findLList(T key) {
	
	int i = 0, flag = 0;
	LLNode<T> * listHead = new LLNode<T>();
	DLLNode<T> * node = new DLLNode<T>();
	DLLNode<T> * nextNode = new DLLNode<T>();

	node = this;
	//cout<<"FindList: node->keys[0]="<<node->keys[0]<<endl;
	while (true) {
		//cout<<"FindList: node->keys[0]="<<node->keys[0]<<endl;
		for (i = 0; i < node->nodeSize; i++)
			if (key < node->keys[i]) {
				D->read((char *)listHead, sizeof(LLNode<T>), node->list[i-1]);
				flag = 1;
				break;
			}
		if (flag == 1)
			break;

		if (node->nextNodeLoc == -1 && i != 0) {
			D->read((char *)listHead, sizeof(LLNode<T>), node->list[i-1]);
			//cout<<"OK"<<listHead->location<<endl;
            		break;
		}
		else {
			i = node->list[node->nodeSize-1];
			D->read((char *)nextNode, sizeof(DLLNode<T>), node->nextNodeLoc);
			//cout<<"##############"<<nextNode->keys[0]<<endl;
			//cout<<"##############"<<node->keys[node->nodeSize-1]<<endl;
			if (key < nextNode->keys[0]) {
				D->read((char *)listHead, sizeof(LLNode<T>), i);
				break;
			}
			else
				node = nextNode;
		}
	}

	return listHead;
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>
DLLNode<T> * DLLNode<T>::search(T key) {
	
	int i = 0, flag = 0;
	DLLNode<T> * node = new DLLNode<T>();
	DLLNode<T> * nextNode = new DLLNode<T>();
	DLLNode<T> * prevNode = new DLLNode<T>();

	node = this;
	while (true) {
		for (i = 0; i < node->nodeSize; i++)
			if (key < node->keys[i]) {
				flag = 1;
				break;
			}

		if (flag == 1 || node->nextNodeLoc == -1) 
			break;
		else {
			D->read((char *)nextNode, sizeof(DLLNode<T>), node->nextNodeLoc);
			if (key < nextNode->keys[0]) {
				D->read((char *)node, sizeof(DLLNode<T>), nextNode->prevNodeLoc);
				break;
			}
			else
				node = nextNode;
		}
	}
	return node;
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>
void DLLNode<T>::insert(LLNode<T> * listHead) {

	int i = 0;
	T key = listHead->getNodeFirstKey();
	DLLNode<T> * node = new DLLNode<T>();

	node = search(key);

	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->list[i] = node->list[i-1];
		}

		node->keys[i] = key;
		node->list[i] = listHead->getNodeLocation();
		node->nodeSize++;

		D->write((char *)node, sizeof(DLLNode<T>), node->location);
	}
	else {
		node->split(this);
		node->insert(listHead);
	}
}

/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>
void DLLNode<T>::remove(LLNode<T> * listHead) {

	int i = 0, l;
	T key = listHead->getNodeFirstKey();
	DLLNode<T> * node = new DLLNode<T>();
	
	//cout<<"Dlln remove key="<<key<<endl;
	node = search(key);
	//cout<<"Dlln search key..."<<endl;
	for (i = 0; i < node->nodeSize; i++) {		//find the key's position
		//cout<<node->keys[i]<<" ";
		if (key == node->keys[i]) 
			break;
		else if (key < node->keys[i]) {	
			i--;			//the corresponding index key for this list may be different,
			break;			//this happens when we have remove the first key of the list 
		}				//and then we make a fussion (in this case we dont change this index,)
	}					//as we do when we make transfer.
	//cout<<endl;
	for (l = i; l < nodeSize-1; l++) {		//shift the keys to the right position
		node->keys[l] = node->keys[l+1];
		node->list[l] = node->list[l+1];
	}
	//cout<<endl;
	node->nodeSize--;
	D->write((char *)node, sizeof(DLLNode<T>), node->location);

	//cout<<"Dlln removed key="<<key<<endl;

	if (node->nodeSize < HALF_KEYS) {

		if (node->prevNodeLoc != -1) {
			DLLNode<T> * prevNode = new DLLNode<T>();
			D->read((char *)prevNode, sizeof(DLLNode<T>), node->prevNodeLoc);
			if ((prevNode->nodeSize + node->nodeSize) <= MAX_KEYS)
				fuse(prevNode, node);
			else
				transfer(node, prevNode);
			//free(prevNode);
		}
		else if (node->nextNodeLoc != -1) {
			DLLNode<T> * nextNode = new DLLNode<T>();
			D->read((char *)nextNode, sizeof(DLLNode<T>), node->nextNodeLoc);
			if ((nextNode->nodeSize + node->nodeSize) <= MAX_KEYS)
				fuse(node, nextNode);
			else
				transfer(node, nextNode);
			//free(nextNode);
		}
	}
}


/* Given:   
 *           
 * Task:    
 *	    
 * Return:  
 */
template <typename T>
void DLLNode<T>::split(DLLNode<T> * fullNode) {
	
	int i = 0;
	int j = HALF_KEYS;
	DLLNode<T> * newNode = new DLLNode<T>();
	
	for (i = 0; i < j; i++) {
		newNode->keys[i] = fullNode->keys[j+i];
		newNode->list[i] = fullNode->list[j+i];
	}

	newNode->location = D->getFreeDiskBlock(sizeof(DLLNode<T>));				//freeDiskLoc
	newNode->nodeSize = fullNode->nodeSize = j;
	newNode->nextNodeLoc = fullNode->nextNodeLoc;
	newNode->prevNodeLoc = fullNode->location;
	fullNode->nextNodeLoc = newNode->location;
	if (newNode->nextNodeLoc != -1) {
		DLLNode<T> * node = new DLLNode<T>();
		D->read((char *)node, sizeof(DLLNode<T>), newNode->nextNodeLoc);
		node->prevNodeLoc = newNode->location;
		D->write((char *)node, sizeof(DLLNode<T>), node->location);
		//free(node);
	}
	
	//cout<<"DLL split:"<<fullNode->nextNodeLoc<<" "<<newNode->nextNodeLoc<<" "<<newNode->keys[0]<<endl;
	
	D->write((char *)fullNode, sizeof(DLLNode<T>), fullNode->location);
	D->write((char *)newNode, sizeof(DLLNode<T>), newNode->location);
}

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

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

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

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

	D->write((char *)destNode, sizeof(DLLNode<T>), destNode->location);
}


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

	int i = 0;

	if (destNode->keys[0] < fromNode->keys[0]) {
		destNode->keys[destNode->nodeSize] = fromNode->keys[0];
		destNode->list[destNode->nodeSize] = fromNode->list[0];
		for (i = 0; i < fromNode->nodeSize-1; i++) {
			fromNode->keys[i] = fromNode->keys[i+1];
			fromNode->list[i] = fromNode->list[i+1];
		}
	}
	else {
		for (i = destNode->nodeSize; i > 0; i--) {
			destNode->keys[i] = destNode->keys[i-1];
			destNode->list[i] = destNode->list[i-1];
		}
		destNode->keys[0] = fromNode->keys[fromNode->nodeSize-1];
		destNode->list[0] = fromNode->list[fromNode->nodeSize-1];
	}
	
	destNode->nodeSize++;
	fromNode->nodeSize--;

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

#endif
