// tree.cpp: implementation of the K_tree and GloK_tree
// classes.
//////////////////////////////////////////////////////////////////////

#include <assert.h>
#include <memory.h>
//#include "tree.h"
//#include "hash_table.h"
#include "ec_storage.h"
//#include "buffer.h"
//#include "common.h"
#include "fk_tree.h"

//////////////////////////////////////////////////////////////////////
// external variables
//////////////////////////////////////////////////////////////////////

extern memory* buf;
extern int TRANSACTION_NO;
extern int ITEM_NO;
extern int NET_ITEM_NO;
extern int* order_item;
//extern hash_table *patternTable;
extern int* fullItem;
extern int fullNum;

//bool blMap = false;
extern ec_storage *ECstorage;
extern int* subSet;

//////////////////////////////////////////////////////////////////////
// Functions of GloK_tree Class
//////////////////////////////////////////////////////////////////////

////////// public functions ////////////////////
void GloK_tree::init(int itemno)
{
	Root = (GK_node*)buf->newbuf(1, sizeof(GK_node));
	Root->init(NULL, -1);

	header = (GK_node**)buf->newbuf(itemno, sizeof(GK_node*));
	for(int i=0; i<itemno; i++)
		header[i] = NULL;

	negStart = NULL;
	negEnd = NULL;

	//sibList = (GK_node**)buf->newbuf(VALID_ITEM_NO, sizeof(GK_node*));
	//sibLen = 0; //reset the top of sibList

	enumList = (int*)buf->newbuf(VALID_ITEM_NO, INTSIZE);
	enumLen = 0;
}

GloK_tree::~GloK_tree()
{
}

GK_node* GloK_tree::insertKey(int *keySet, int len, int support, int index)
{
	if(keySet==NULL)
		return NULL;

	GK_node* child = Root;
	GK_node* temp, *temp1=NULL;
	int i=0;

	while(i<len)
	{
		for(temp=child->leftchild; temp!=NULL; temp = temp->rightsibling)
		{
			if(temp->itemName==keySet[len-i-1])
			{
				temp1=NULL;
				break;
			}

			if(temp->itemName < keySet[len-i-1]) //find point to insert
				temp1 = temp;
			else
			{
				temp = NULL;
				break;
			}
			//if(temp->rightsibling == NULL) temp1 = temp;
		}

		if(!temp)break;

		child=temp;
		i++;
	}

	while(i<len)
	{
		child = child->append(this, temp1, keySet[len-i-1]);
		child->next = header[keySet[len-i-1]]; //update header table
		header[keySet[len-i-1]] = child;
		i++;
		//temp1 = NULL; //just to confirm
	}
	child->index = index;
	child->support = support;

	return child;
}

GK_node* GloK_tree::insertNBG(int *keySet, int len, int support, int index)
{
	if(keySet == NULL)
		return NULL;

	GK_node* node = insertKey(keySet, len, support, index);
	node->blborder = true;

	//for debug
	/*if(node->par->itemName!=-1 && node->par->index<0)
	{
		printf("ngb error!\n");
		scanf("exit");
		exit(1);
	}*/

	//insert nbg to nbg linklist
	if(negEnd)
	{
		negEnd->negNext = node;
		negEnd = node;
	}
	else
	{
		negStart = node;
		negEnd = node;
	}

	return node;
}

int GloK_tree::outputKeys(FSout *fsout, FSout *fsoutNGB, double& keyNum)
{
	if(fsout==NULL)
		return 0;

	GK_node* current = Root->leftchild;
	//negStart = NULL;
	//negEnd = NULL;

	while(current)
	{
		if(current->index>=0)
		{
			KeyHashNode* keyNode = ECstorage->findKey(current->index);

			if(keyNode==NULL)
			{
				printf("key storage error!");
				scanf("exit");
				exit(1);
			}

			if(current->support>=THRESHOLD) //freq key
			{
				//for debug
				bool blkey = ECstorage->fkTree->GlobalKeyCheck(keyNode->iset, keyNode->length, keyNode->support);
				
				if(fsout && blkey)
				{
					fsout->printString("[");
					fsout->printDigit(current->index);
					fsout->printString("]");

					fsout->printKeySet(keyNode->length, keyNode->iset, keyNode->support);
					fsout->printString("\n");
					keyNum++;
				}
				
			}
			else
			//if(current->leftchild==NULL) //ngb
			{
				/*if(current->blborder!=true) //for debug only
				{
					printf("blborder reading not consisten\n");
					scanf("exit");
					exit(1);
				}*/
				//for debug
				bool blkey = ECstorage->fkTree->GlobalKeyCheck(keyNode->iset, keyNode->length, keyNode->support);

				if(fsoutNGB && blkey)
				{
					fsoutNGB->printOrderSet(keyNode->length, keyNode->iset, keyNode->support);
					//for debug
					//fsoutNGB->printKeySet(keyNode->length, keyNode->iset, keyNode->support);
					
					fsoutNGB->printString("\n");
				}
				

				//stop going down
				current->leftchild = NULL;
			}
		}

		if(current->leftchild)
		{
			current = current->leftchild;
			continue;
		}
		else
		{
			while(current && !current->rightsibling)
			{
				current= current->par;
			}

			if(!current)
				break; //end

			current = current->rightsibling;

		}
	}

	return 1;
}

int GloK_tree::outputNGB(FSout *fsout)
{
	if(fsout == NULL)
	{
		printf("output file error!");
		scanf("exit");
		exit(1);
	}


	GK_node* curr = negStart;
	KeyHashNode* node;

	while(curr)
	{
		node = ECstorage->findKey(curr->index);
		fsout->printOrderSet(node->length, node->iset, node->support);

		fsout->printString("\n");

		curr = curr->negNext;
	}

	return 1;
}

int GloK_tree::genNewKeyfrNGB(FK_tree* tree)
{
	GK_node* curr = Root->leftchild;

	int* closet;
	int clen, support,cindex;
	KeyHashNode* knode;

	curr = negStart;

	while(curr)
	{
		if(curr->support>=THRESHOLD) //newly freq key
		{
			knode = ECstorage->findKey(curr->index);
			//INV_GEN++; //for statistical study

			if(curr->itemName == 0) //no need enum
			{
				tree->genClose(knode->iset, knode->length, support, closet, clen);
				cindex = ECstorage->insertEC(closet, clen, support, knode->iset, knode->length);
				knode->closeIndex = cindex;
			}
			else
			{
				enumNewKey(curr, knode, tree, closet, clen);

				cindex = ECstorage->insertEC(closet, clen, curr->support, knode->iset, knode->length);
				knode->closeIndex = cindex;

			}
		}

		curr = curr->negNext;
	}

	
	return 1;
}

int GloK_tree::enumNewKey(GK_node* curr, KeyHashNode* knode, FK_tree* tree, int*& closet, int& clen)
{
	if(curr==NULL || tree == NULL)
		return 0;

	//tree nodes
	GK_node* par = curr->par;
	GK_node* node = par->leftchild;
	int support;

	//init enumList
	enumLen = 0;

	while(node && node != curr)
	{
		enumList[enumLen++] = node->itemName;
		node= node->rightsibling;
	}

	//enumerate new keys from the border
	tree->genNewKey(knode, support, closet, clen, enumList, enumLen);

	return 1;
}
////////// private functions ////////////////////




//////////////////////////////////////////////////////////////////////
// Functions of K_tree Class
//////////////////////////////////////////////////////////////////////

////////// public functions ////////////////////
void K_tree::init(int index)
{
	Root = (K_node*)buf->newbuf(1, sizeof(K_node));
	Root->init(NULL, -1);

	header = NULL;

	cindex = index;
	//support = s;
}

K_tree::~K_tree()
{
}

K_node* K_tree::insertKey(int *keySet, int len)
{
	if(keySet==NULL)
		return NULL;

	K_node* child = Root;
	K_node* temp, *temp1=NULL;
	int i=0;

	while(i<len)
	{
		for(temp=child->leftchild; temp!=NULL; temp = temp->rightsibling)
		{
			if(temp->itemName==keySet[i])break;
			if(temp->rightsibling==NULL)temp1 = temp;
		}

		if(!temp)break;

		child=temp;
		i++;
	}

	if(child != Root && child->leftchild == NULL)
		return NULL; //target keyset is superset of one of the exisitn key

	while(i<len)
	{
		child = child->append(this, temp1, keySet[i]);
		i++;
	}
	child->next = header;
	header = child;

	return child;
}

int K_tree::outputKeys(FSout* fsout, int maxlen)
{
	if(fsout == NULL)
		return 0;

	K_node *temp1, *temp;
	temp = header;
	int *key = new int[maxlen];
	int keylen;

	while(temp !=NULL)
	{
		keylen =0;
		temp1 = temp;
		while(temp1 != Root)
		{
			key[keylen++] = temp1->itemName;
			//fsout->printItem(temp1->itemName);
			temp1 = temp1->par;
		}
		//for(;keylen>0;keylen--)
		//	fsout->printItem(key[keylen-1]);
		fsout->printKeySet(keylen, key,0);

		fsout->printString(";");
		temp = temp->next;
	}

	delete []key;

	return 1;
}


int K_tree::splitKey(int *keySet, int klen, CloseHashNode* closeNode)
{
	if(keySet == NULL)
		return 0;

	int i;
	K_node* keyNode = findKey(keySet, klen);

	if(keyNode==NULL)
	{
		printf("wrong association of key n ec!\n");
		scanf("exit");
		exit(1);
	}

	//init in_map;
	for(i=0;i<klen;i++)
		//in_map[keySet[i]]=keySet[i];
		in_map[keySet[i]]=1;

	//remove the key
	removeKey(keyNode);

	//generate new keys if they exits
	//genNewKeys(keyNode, keySet, klen, ksupp);
	genNewKeys(keyNode, keySet, klen, closeNode);


	//clear in_map
	for(i=0;i<klen;i++)
		in_map[keySet[i]]=0;

	 return 1;
}

////////// private functions ////////////////////
K_node* K_tree::findKey(int *keySet, int klen)
{
	if(keySet==NULL)
		return NULL;

	K_node* current = Root->leftchild;
	int pos=0;

	do{
		if(current->itemName == keySet[pos])
		{
			pos++;

			if(pos==klen && current->leftchild == NULL)
				return current;

			current= current->leftchild; //move vertically
			continue;
		}

		current = current->rightsibling; //move horizontally
	}while(current);

	return NULL;
}

bool K_tree::isSuperset(K_node* exception)
{
	if(in_map==NULL)
	{
		printf("intersection map error!\n");
		scanf("exit");
		exit(1);
	}

	//bool blreturn = false;


	K_node* current = Root->leftchild;

	while(current)
	{
		if(in_map[current->itemName])
		{
			current =  current->leftchild; //travel down

			if(current == NULL)
				return true;
		}
		else
		{

			while(current->rightsibling == NULL)
			{
				current = current->par; //travle up

				if(current == Root)
					return false;
			}

			current= current->rightsibling; //travel side
		}
	}

	/*K_node* current = header, *temp;

	while(current)
	{
		if(current != exception)
		{
			temp = current;
			while(temp->itemName!=-1)
			{
				if(!in_map[temp->itemName])
					break;

				temp = temp->par;
			}

			if(temp->itemName==-1)
			{
				blreturn = true;
				break;
			}
		}

		current = current->next;
	}*/

	//return blreturn;
	return false;

}

int K_tree::genNewKeys(K_node* keyNode, int* keySet, int klen, CloseHashNode* closeNode)
{
	if(keyNode == NULL
		|| keySet == NULL)
		return 0;

	int i,dlen=closeNode->diffLen, ilen;
	int* diffset=closeNode->diffSet;
	int* iset;

	//ECstorage->getDiffSet(diffset, dlen);

	for(i=0; i<dlen; i++)
	{
		//map diffset[i]
		//in_map[diffset[i]] = diffset[i];
		in_map[diffset[i]] = 1;

		if(isSuperset(keyNode))
		{
			//reset in_map
			in_map[diffset[i]] = 0;
			continue;
		}

		//init new key
		iset = (int*)buf->newbuf(klen+1, sizeof(int));
		memcpy(iset, keySet, klen*sizeof(int));
		ilen = klen;
		Insert(iset, ilen, diffset[i]);

		insertKey(iset, ilen);
		ECstorage->insertKey(iset, ilen, closeNode->support, cindex);

		//INV_GEN++;

		//reset in_map
		in_map[diffset[i]] = 0;
	}

	return 1;
}

int K_tree::removeKey(K_node *keyNode)
{
	if(keyNode == NULL)
		return 0;

	K_node* current = header;
	K_node* previous = NULL, *curr, *par;

	while(current && current!=keyNode)
	{
		previous = current;
		current = current->next;
	}

	if(current ==NULL)
	{
		printf("key tree header error!\n");
		scanf("exit");
		exit(1);
	}

	//remove keyNode from header linked list
	if(!previous) //keyNode == header
		header = keyNode->next;
	else
		previous->next = keyNode->next;

	//note?
	current = keyNode;
	par = current->par;

	while(current->itemName!=-1) //root
	{
		curr=par->leftchild;
		previous = NULL;

		if(curr->rightsibling)
		{
			while(curr!=current)
			{
				previous = curr;
				curr = curr->rightsibling;
			}
			//remove nodes of key from sibling linked list
			if(!previous)
				par->leftchild = current->rightsibling;
			else
				previous->rightsibling = current->rightsibling;

			break;
		}

		par->leftchild = NULL; //remove e nodes of e key
		//current->par = NULL;
		//current->rightsibling = NULL;

		current = par;
		par =par->par; //move up
	}

	return 1;
}

//////////////////////////////////////////////////////////////////////
// Functions of C_tree Class
//////////////////////////////////////////////////////////////////////
void C_tree::init(int totalItemNo)
{
	Root = (C_node*)buf->newbuf(1, sizeof(C_node));
	Root->init(NULL, -1);
	Root->level = 0;

	header = (C_node**)buf->newbuf(totalItemNo, sizeof(C_node*));
	for(int i = 0; i < totalItemNo; i++)
	{
		header[i] = (C_node*)buf->newbuf(1, sizeof(C_node));
		header[i]->init(NULL, i);
	}
}

C_tree::~C_tree()
{
}