// ec_storage.cpp: implementation of the key_index, key_map 
// classes.
//////////////////////////////////////////////////////////////////////
#include <memory.h>
#include "common.h"
#include "ec_storage.h"
#include "fk_tree.h"

//int version =0;

////////////////////////////////////////////////
//	external variables & functions
////////////////////////////////////////////////
extern int* subSet;

bool compareSet(int * iset1, int length1, int *iset2, int length2);

////////////////////////////////////////////////
//	ec_storage class functions
////////////////////////////////////////////////

////////// public functions ////////////////////
ec_storage::ec_storage()
{
	closeHash = NULL;
	keyHash = NULL;
	gKeyTree = NULL;
	//keyMap = NULL;
	//closeTree = NULL;
	
	//diffSet = NULL;
	//diffLen = 0;
	//shareSet = NULL;
	//shareLen = 0;
}

ec_storage::~ec_storage()
{
	if(closeHash)
		closeHash->releaseTable();
	
	//if(keyMap)
	//	keyMap->releaseKeyMap();
	
	if(keyHash)
		keyHash->releaseTable();
	
	//if(closeTree)
	//	closeTree = NULL;
}

int ec_storage::init()
{
	//init close hash table
	closeHash = (closeHashTable*)buf->newbuf(1, sizeof(closeHashTable));
	//closeHash->initTable(NET_ITEM_NO+ITEMBUFF, INITSIZE);
	closeHash->initTable(NET_ITEM_NO, INITSIZE);
	
	//init key hash table
	keyHash = (keyHashTable*)buf->newbuf(1, sizeof(keyHashTable));
	keyHash->initTable(NET_ITEM_NO, INITSIZE);
	
	//init gKeyTree;
	gKeyTree = (GloK_tree*) buf->newbuf(1, sizeof(GloK_tree));
	gKeyTree->init(NET_ITEM_NO);

	//init fkTree;
	fkTree = NULL;

	//init negBorder
	//negBorder = (neg_border*)buf->newbuf(1, sizeof(neg_border));
	//negBorder->init();
	
	//diffSet = NULL;
	//diffLen = 0;
	//shareSet = NULL;
	//shareLen = 0;
	
	return 1;
}

int ec_storage::insertEC(int *&iCloseSet, int clen, int support, int *iKeySet, int iLen)
{
	if(iCloseSet == NULL)
		return -1;
	
	int cindex, kindex;
	
	//insert ec into hashtable
	cindex = closeHash->insert(iCloseSet, clen, support, iKeySet, iLen);
	
	//insert key into hashtable
	if(iKeySet)
		kindex = keyHash->insert(iKeySet, iLen, support, cindex);
	
	//insert key into keyMap
	//if(iKeySet)
	//	keyMap->insert(iKeySet, iLen, support, cindex);
	
	if(iKeySet)
		gKeyTree->insertKey(iKeySet, iLen, support, kindex);
	
	//insert close into closeTree
	//closeTree->insertClose(iCloseSet, clen, cindex);
	
	return cindex;
}

int ec_storage::insertEC(int *&iCloseSet, int clen, int support, K_tree* ktree, int index)
{
	if(iCloseSet == NULL)
		return -1;
	
	int cindex;
	//insert ec into hashtable
	cindex = closeHash->insert(iCloseSet, clen, support, ktree, index);
	
	//insert close into closeTree
	//closeTree->insertClose(iCloseSet, clen, cindex);
	
	return index;
}

int ec_storage::insertKey(int *&iKeySet, int klen, int support, int cindex)
{
	if(iKeySet==NULL)
		return -1;
	
	int kindex;
	
	kindex = keyHash->insert(iKeySet, klen, support, cindex);
	gKeyTree->insertKey(iKeySet, klen, support, kindex);
	
	//return keyMap->insert(iKeySet, klen, support, cindex);
	return kindex;
}

int ec_storage::insertNBG(int *&iKeySet, int klen, int support)
{
	if(iKeySet==NULL)
		return -1;
	
	int kindex;
	
	kindex = keyHash->insert(iKeySet, klen, support, -1);
	gKeyTree->insertNBG(iKeySet, klen, support, kindex);
	//negBorder->insertNegGen(iKeySet, klen, support);
	//return keyMap->insert(iKeySet, klen, support, cindex);
	return kindex;
}

int ec_storage::outputNGB(FSout *fout)
{
	if(fout==NULL)
		return 0;

	gKeyTree->outputNGB(fout);

	return 1;
}


int ec_storage::outputEC(FSout *fout, double &closeNum, double &keyNum)
{
	if(fout==NULL)
		return 0;
	
	closeHash->outputClose(fout, closeNum);
	
	return 1;
}


int ec_storage::outputKey(FSout *fout, FSout *foutNGB, double &keyNum)
{
	if(fout == NULL)
		return 0;
	
	gKeyTree->outputKeys(fout,foutNGB, keyNum);
	//keyHash->outputKey(fout, keyNum);
	
	return 1;
}

int ec_storage::findEC(int* closeset, int len, int &support)
{
	return closeHash->find(closeset, len, support);
}

int ec_storage::findEC(int* keyset, int klen)
{	
	KeyHashNode* keypointer = findKey(keyset, klen);
	
	if(keypointer)
		return keypointer->closeIndex;
	
	return -1;
}

CloseHashNode* ec_storage::findECpt(int* closeset, int len, int &support)
{
	return closeHash->find(closeset, len);
}

CloseHashNode* ec_storage::findECpt(int* keyset, int klen)
{
	KeyHashNode* keypt = findKey(keyset, klen);
	
	if(keypt == NULL)
		return NULL;
	
	return closeHash->find(keypt->closeIndex);
}

int ec_storage::findKey(int* iset, int len, int &support)
{
	//return keyMap->find(iset, len, support);
	return keyHash->find(iset, len, support);
}

KeyHashNode* ec_storage::findKey(int* iset, int len)
{
	//return keyMap->find(iset, len);
	return keyHash->find(iset, len);
}

KeyHashNode* ec_storage::findKey(int index)
{
	return keyHash->find(index);
}

int ec_storage::readOldEC(Data* fdat)
{
	if(fdat == NULL)
	{
		printf("input file error!");
		scanf("exit");
		exit(1);
	}
	
	EquiClass *ec = new EquiClass(VALID_ITEM_NO);
	
	int* closeSet;
	int support=0, index = -255;
	K_tree* ktree = NULL;
	
	//for debug
	int tranCount=0;
	
	while(ec = fdat->getNextEC(ec, support, index, ktree))
	{	
		tranCount++;
		
		if(index == -1 || ec->clen==0) //ec is infreq or fullset
			continue;
		
		closeSet =(int*)buf->newbuf(ec->clen, sizeof(int));
		memcpy(closeSet, ec->closeSet, sizeof(int)*ec->clen);
		
		insertEC(closeSet, ec->clen, support, ktree, index);
		
		ktree = NULL;
	}
	delete ec;
	
	return 1;
}

int ec_storage::updateEC(Data *fdat)
{
	if(fdat == NULL)
	{
		printf("incremental data error!");
		scanf("exit");
		exit(1);
	}
	
	int i;
	
	//initialization
	tranStore* current = fdat->ts;
	
	//diffSet = (int*)buf->newbuf(MAX_TRAN_LEN, sizeof(int));
	//shareSet = (int*)buf->newbuf(MAX_TRAN_LEN, sizeof(int));
	
	while(current)
	{
		//update glotree
		fkTree->insertTransaction(current);
		
		for(i=0; i<current->length;i++)
			in_map1[current->t[i]] = 1; //set in_map1
		
		UPDATE_VERSION++;
		updateKeyWithTransaction(current->t, current->length);
		
		for(i=0; i<current->length;i++)
			in_map1[current->t[i]] = 0; //reset in_map1
		
		current = current->next;
	}
	
	return 1;
}

void ec_storage::expandNGB()
{
	
	gKeyTree->genNewKeyfrNGB(fkTree);
}

int ec_storage::DecUpdateEC(Data *fdat)
{
	int i;

	int start=0;
	
	//initialization
	tranStore* current = fdat->ts;
	
	//scan through db_upd
	while(current)
	{
		//update gloTree
		fkTree->deleteTransaction(current);

		//update ecs
		UPDATE_VERSION++;

		for(i=0; i<current->length;i++)
			in_map1[current->t[i]] = 1; //set in_map1

		DecUpdateKeyWithTransaction(current->t, current->length);

		for(i=0; i<current->length;i++)
			in_map1[current->t[i]] = 0; //reset in_map1

		current = current->next;
	}
	
	return 1;
}
////////// private functions ////////////////////

int ec_storage::updateKeyWithTransaction(int* t, int length)
{
	if(t == NULL)
		return 0;
	
	int i;
	for(i=0; i<length; i++)
		updateKeyTree(t, length, i, 1);
	
	return 1;
}

int ec_storage::updateKeyTree(int* t, int length, int pos, int support)
{
	int item = t[pos]; //the last item of keys to be updated
	
	KeyHashNode* node; //key hashNode pointer
	GK_node* topNode;
	GK_node* knode = gKeyTree->Root->leftchild;
	int depth;

	//find the top node
	while(knode && knode->itemName!=item)
		knode = knode->rightsibling;

	if(!knode) //no keys qualified & no maintenance required
		return 0;

	topNode = knode;
	
	
	knode->support+=support;
	
	//if(knode->index<0) //for debug only
	//{
	//	printf("key index error!");
	//	scanf("exit");
	//	exit(1);
	//}
	
	node = keyHash->find(knode->index);

	//INV_GEN++; //for statistical study

	//update top node
	if(knode->blborder) //update ngb
	{
		updateNBGnode(knode, node);

		return 0;
	}
	else //update key
		updateKeyNode(node);

	//update subsequent nodes
	knode = knode->leftchild;
	depth = 1;

	while(knode && depth <= pos)
	{	
		node = keyHash->find(knode->index);

		if(isSubset(node->iset, node->length))
		{
			knode->support+=support; //update tree node support value
			//INV_GEN++; //for statistical study
			
			if(!knode->blborder) //update key n ecs
			{	
				updateKeyNode(node);
				
				if(knode->leftchild)
				{
					knode = knode->leftchild;
					depth++;
					continue;
				}		
			}
			else //update the count of ngb
			{
				updateNBGnode(knode, node);
				
			}
		}

		while(!knode->rightsibling)
		{
			knode = knode->par;
			depth--;

			if(knode == topNode)
				return 1; //update has finished
		}

		knode = knode->rightsibling;
		
	}
	
	return 1;
}

int ec_storage::updateKeyNode(KeyHashNode* node, int count)
{
	if(node == NULL)
		return 0;

	//update key support
	node->support += count;

	CloseHashNode* closeNode; //close hashnode pointer
	
	//update corresponding ec
	closeNode = closeHash->find(node->closeIndex); //access e ec
				
	//if(closeNode==NULL) //for debug only
	//{
	//	printf("key ec association error!\n");
	//	scanf("exit");
	//	exit(1);
	//}
				
	if(closeNode->versionNo == UPDATE_VERSION) //corresponds the case where the ec remains 
		return 1;								//and the support of ec has already been updated

	if(closeNode->splite_versionNO == UPDATE_VERSION) //shareset n diffset has been updated
	{
		//split ec
		splitEC(node, closeNode);
		
		return 1;
	}
	
	//compare closeSet with brachSet
	if(!compSetNBranch(closeNode))
	{
		//split ec
		splitEC(node, closeNode);

		closeNode->splite_versionNO = UPDATE_VERSION;
	}
	else
	{
		//update closeNode support		
		closeNode->support = node->support;
		closeNode->versionNo = UPDATE_VERSION;
	}
				
	return 1;
}


int ec_storage::splitEC(KeyHashNode* keyNode, CloseHashNode *closeNode)
{
	//update existing ec
	//closeNode->keys->splitKey(keyNode->iset, keyNode->length, closeNode->support);
	closeNode->keys->splitKey(keyNode->iset, keyNode->length, closeNode);

	//create splitted out ec
	int support=0;
	int index = 0;
	CloseHashNode* cNode;
	int* shareSet = closeNode->shareSet;
	int shareLen = closeNode->shareLen;

	index = findEC(shareSet, shareLen, support);
	//cNode = findECpt(shareSet, shareLen, support);
	
	if(index < 0) //new splitted out ec
	{
		//insert ec into hashtable
		int* closeSet = (int*)buf->newbuf(shareLen, sizeof(int));
		memcpy(closeSet, shareSet, shareLen*sizeof(int));
		
		index = closeHash->insert(closeSet, shareLen, keyNode->support, keyNode->iset, keyNode->length);
		
	}
	else //existing splitted out ec
	{
		cNode = closeHash->find(index);
		cNode->keys->insertKey(keyNode->iset, keyNode->length);
	}
	keyNode->closeIndex = index; 
	
	return 1;
}

bool ec_storage::compSetNBranch(CloseHashNode* closeNode)
{
	if(closeNode == NULL)
		return false;
	
	bool blresult = true;
	closeNode->shareLen = 0;
	closeNode->diffLen = 0;
	
	for(int i=0; i<closeNode->length; i++)
	{
		if(in_map1[closeNode->iset[i]])
		{
			closeNode->shareSet[closeNode->shareLen++] = closeNode->iset[i];
		}
		else
		{
			closeNode->diffSet[closeNode->diffLen++] = closeNode->iset[i];
			blresult = false;
		}
	}
	
	return blresult;
}

bool ec_storage::isSubset(int *iset, int ilen)
{
	if(iset == NULL)
		return false;
	
	for(int i=0; i<ilen-1;i++) //ignore the last item, for it is always included
	{
		if(!in_map1[iset[i]])
			return false;
	}
	
	return true;
}

int ec_storage::updateNBGnode(GK_node* knode, KeyHashNode* hnode, int count)
{
	if(knode==NULL || hnode == NULL)
		return 0;

	//update support
	hnode->support += count;

	if(hnode->support>=THRESHOLD)//newly emerged generator
	{
		
		knode->blborder = false;
		int cindex, support, clen=0;
		int* closet;

		if(knode->itemName ==0) //no need enumeration
		{
			fkTree->genClose(hnode->iset, hnode->length, support, closet, clen);
			cindex = insertEC(closet, clen, support, hnode->iset, hnode->length);
			hnode->closeIndex = cindex;

			//if(support!=knode->support) //for debug only
			//{
			//	printf("genClose suppor error!");
			//	scanf("exit");
			//	exit(1);
			//}
		}
		else
		{
			enumNewKey(knode, hnode, closet, clen);

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

	}
	return 1;
}

int ec_storage::enumNewKey(GK_node* knode, KeyHashNode* hnode, int*& closet, int& clen)
{
	if(knode==NULL || hnode == NULL)
		return 0;

	//tree nodes
	GK_node* par = knode->par;
	GK_node* node = par->leftchild;
	GK_node* sib = NULL;

	int mSup=0;
	int support;//, kindex, cindex;
	
	//store candidates into enumlist
	//int* enumlist = new int[knode->itemName];
	int* enumlist = gKeyTree->enumList;
	int enumlen = 0;

	while(node && node != knode)
	{
		enumlist[enumlen++] = node->itemName;
		node= node->rightsibling;
	}
	
	if(enumlen)
	{
		//enum new nbg
		fkTree->genNewKey(hnode, support, closet, clen, enumlist, enumlen);
	}
	else
		fkTree->genClose(hnode->iset, hnode->length, support, closet, clen);
	

	//if(knode->support!=support || hnode->support != support) //for debug only
	//{
	//	printf("new key support inconsistant.\n");
	//	scanf("exit");
	//	exit(1);
	//}

	//delete []enumlist;

	return 1;
}

int ec_storage::DecUpdateKeyWithTransaction(int* t, int length)
{
	if(t == NULL)
		return 0;
	
	int i;
	for(i=0; i<length; i++)
		DecUpdateKeyTree(t, length, i);
	
	return 1;
}

int ec_storage::DecUpdateKeyTree(int* t, int length, int pos, int support)
{
	int item = t[pos]; //the last item of keys to be updated
	
	KeyHashNode* node; //key hashNode pointer
	GK_node* topNode;
	GK_node* knode = gKeyTree->Root->leftchild;
	int depth;

	//find the top node
	while(knode && knode->itemName!=item)
		knode = knode->rightsibling;

	if(!knode) //no keys qualified & no maintenance required
		return 0;

	topNode = knode;
	
	knode->support-=support; //update support
	
	//if(knode->index<0) //for debug only
	//{
	//	printf("key index error!");
	//	scanf("exit");
	//	exit(1);
	//}
	
	node = keyHash->find(knode->index);

	//INV_GEN++; //for statistical study

	//update top node
	DecUpdateKeyNode(node);

	//update subsequent nodes
	knode = knode->leftchild;
	depth = 1;

	while(knode && depth <= pos)
	{	
		node = keyHash->find(knode->index);

		if(isSubset(node->iset, node->length))
		{
			knode->support-=support; //update tree node support value
			//INV_GEN++; //for statistical study
			
			DecUpdateKeyNode(node);

			if(knode->leftchild)
			{
				knode = knode->leftchild;
				depth++;
				continue;
			}		
		}

		while(!knode->rightsibling)
		{
			knode = knode->par;
			depth--;

			if(knode == topNode)
				return 1; //update has finished
		}

		knode = knode->rightsibling;
		
	}
	
	return 1;
}

int ec_storage::DecUpdateKeyNode(KeyHashNode* node, int count)
{
	if(node == NULL)
		return 0;

	//update key support
	node->support -= count;

	if(node->closeIndex<0) //ngb keys
		return 1;

	CloseHashNode* closeNode; //close hashnode pointer
	
	//update corresponding ec
	closeNode = closeHash->find(node->closeIndex); //access e ec
				
	//if(closeNode==NULL) //for debug only
	//{
	//	printf("key ec association error!\n");
	//	scanf("exit");
	//	exit(1);
	//}
				
	if(closeNode->versionNo == UPDATE_VERSION) //corresponds the case where the ec remains 
		return 1;								//and the support of ec has already been updated
	else
	{
		//update closeNode support		
		closeNode->support = node->support;
		closeNode->versionNo = UPDATE_VERSION;
	}
				
	return 1;
}