// hash_table.cpp: implementation of the hash_table, closeHashTable 
// & keyHashTable classes.
//////////////////////////////////////////////////////////////////////

#include <iostream>
#include <memory.h>
#include <math.h>
#include "common.h"
//#include "tree.h"
//#include "hash_table.h"
#include "ec_storage.h"

////////////////////////////////////////////////
//	external variables & functions
////////////////////////////////////////////////

//extern bool compareSet(int * iset1, int length1, int *iset2, int length2);
extern void inssort(int* array, int i, int j);

extern ec_storage *ECstorage;

bool compareSet(int * iset1, int length1, int *iset2, int length2)
{
	if(length1!=length2)
		return false;
	for(int i=length1-1;i>=0;i--)
	{
		if(iset1[i]!=iset2[i]) return false;
	}
	return true;
}

////////////////////////////////////////////////
//	hash_table class functions
////////////////////////////////////////////////

////////// public functions ////////////////////
hash_table::hash_table()
{
/*	hashTable = NULL;

	maxSize=0;
	currNodeNum=0;
	int threshold=0;

	hashMap=NULL;
	hashMapSize=0;

	localHashMap = false;*/
}

hash_table::~hash_table()
{
/*	releaseTable();
	if(hashTable)
		delete hashTable;
	if(localHashMap)
	{
		delete hashMap;
		hashMap = NULL;
	}*/
}

int  hash_table::getPrime(int start)
{
	int iCurr=start;
	while(1)
	{
		if(isPrime(iCurr))
			return iCurr;
		iCurr++;
	}
	
	return -1;
}

bool hash_table::isPrime(int num)
{
	if(num<=2) return false;
	
	for(int i=2;i<(num/2);i++)
		if((num %i)==0) return false;
		
		return true;
}

bool  hash_table::initModMap(int num, int * & map, int prime)
{
	localHashMap = true;
	
	if(hashMapSize>0)
	{
		if(map!=NULL)
			delete map;
	}
	map=new int[num];
	hashMapSize=num;
	for(int i=0;i<num;i++)
		map[i]=single_mod(i,prime);
	
	return true;
}

bool hash_table::initModMap(int* map, int mapLen)
{
	if(map == NULL)
		return false;

	hashMap = map;
	hashMapSize = mapLen;

	return true;
}

int  hash_table::single_mod(int i, int prime)
{
	int ret=-1;
	if(i<0) return -1;
	unsigned long pValue=0;
	if(i<MAXPOWER)
		ret=(unsigned long)(pow(2.0,i)) % prime;
	else
		ret=(2*single_mod(i-1, prime)) % prime;
	
	if(ret<0)
	{
		//cout<<"single mod return negative"<<ret<<endl;
		printf("single mod return negative %d", ret);
	}
	return ret;
}

int  hash_table::set_mod(int *iset, int length, int order, int *map, int size)
{
	int sum=0;
	
	for(int i=0;i<length;i++)
	{
		//if(order==0)
		if(iset[i]>=0) //ignore removed transactions
			sum=sum+map[iset[i]];
		while(sum>=size)
			sum=sum-size;
		//else
		//     sum=sum+secModMap[iset[i]];
	}
	//if(order==0)
	//else
	//  ret=sum % (size+OFFSET);
	
	return sum;
}

/*void hash_table::releaseTable()
{
	for(int i=0;i<maxSize;i++)
	{
		if(hashTable[i]!=NULL)
		{
			delete hashTable[i];
			hashTable[i]=NULL;
			currNodeNum--;
		}
	}
}*/

////////////////////////////////////////////////
//	closeHashMap class functions
////////////////////////////////////////////////

////////// public functions ////////////////////
closeHashTable::closeHashTable()
{
	hashTable = NULL;
	
	closeTable = NULL;
	maxSize=0;
	currNodeNum=0;
	threshold=0;

	hashMap=NULL;
	hashMapSize=0;
}

closeHashTable::~closeHashTable()
{
	releaseTable();
	if(closeTable)
		delete closeTable;
	if(localHashMap)
		delete hashMap;
}

void closeHashTable::releaseTable()
{
	
	/*for(int i=0; i<maxSize;i++)
	{
		if(closeTable[i])
		{
			delete closeTable[i];
			currNodeNum--;
		}
	}*/

	delete closeTable;
	closeTable = NULL;
	maxSize =0;
}


void closeHashTable::initTable(int *map, int maplength, int tableSize)
{
	if(map==NULL)
	{
		printf("Mod map error.");
		scanf("exit");
		exit(1);
	}

	initModMap(map,maplength);

	closeTable=new LPCloseHashNode[tableSize];
	for( int i=0;i<tableSize;i++)
	{
		closeTable[i]=NULL; 
	}
	
	maxSize = tableSize;
	currNodeNum = 0;

	threshold = (int)(LOADFACTOR*maxSize);
}

void closeHashTable::initTable(int itemno, int tableSize)
{
	initModMap(itemno, hashMap, tableSize);

	if(hashMap==NULL)
	{
		printf("Mod map error.");
		scanf("exit");
		exit(1);
	}

	closeTable=new LPCloseHashNode[tableSize];
	for( int i=0;i<tableSize;i++)
	{
		closeTable[i]=NULL; 
	}
	
	maxSize = tableSize;
	currNodeNum = 0;

	threshold = (int)(LOADFACTOR*maxSize);
}

int   closeHashTable::insert(int * & iCloseSet, int cLen, int support, int *iKeySet, int kLen)
{
	int i=0;
	int initIndex=0;
	int index;
	initIndex=set_mod(iCloseSet,cLen,0,hashMap, maxSize);
	index=initIndex;
	
	while(i<maxSize)
	{	
		if(closeTable[index]==NULL)
		{
			//LPCloseHashNode lpNode=new CloseHashNode;
			LPCloseHashNode lpNode=(LPCloseHashNode) buf->newbuf(1, sizeof(CloseHashNode));
			lpNode->iset=iCloseSet;
			lpNode->length=cLen;
			lpNode->support=support;
			//lpNode->posCount=posCount;
			//lpNode->head=lpKeyNode;
			if(iKeySet)
			{
				lpNode->keys = (K_tree*)buf->newbuf(1, sizeof(K_tree));
				lpNode->keys->init(index);
				lpNode->keys->insertKey(iKeySet, kLen);
			}
			
			//for maintenance
			lpNode->versionNo = 0; //note?
			lpNode->splite_versionNO = 0;
			
			lpNode->diffSet = (int*)buf->newbuf(cLen, INTSIZE);
			lpNode->diffLen = 0;
			
			lpNode->shareSet = (int*)buf->newbuf(cLen, INTSIZE);
			lpNode->shareLen = 0;

			closeTable[index]=lpNode;
			currNodeNum++;
			if(currNodeNum>threshold)
			{
				printf("now rehash close hash table from %d\n", currNodeNum);	
				rehashTable();
			}
			//maxtree->insertClose(iCloseSet, cLen, index);
			return index;
		}else
		{
			LPCloseHashNode lpNode=closeTable[index];
			bool bEqual=compareSet(iCloseSet,cLen, lpNode->iset, lpNode->length);
			if(bEqual)
			{
				//lpKeyNode->next=lpNode->head;
				//lpNode->head=lpKeyNode;
				if(iKeySet)
					lpNode->keys->insertKey(iKeySet, kLen);
				//delete iCloseSet; //added by mengling for memory leak
				return index;
			}    
		}
		i++;
		index=initIndex+INCREMENT(i);  
		while(index>=maxSize)
		{
			index=index-maxSize;
		}
		
	}
	
	return -1;
}

int closeHashTable::insert(int *&iCloseSet, int clen, int support, K_tree* ktree, int index)
{
	if(index<0 || iCloseSet == NULL)
		return 0;

	if(closeTable[index])
	{
		printf("index of ec error.\n");
		scanf("exit");
		exit(1);
	}

	//LPCloseHashNode lpNode=new CloseHashNode;
	LPCloseHashNode lpNode=(LPCloseHashNode)buf->newbuf(1,sizeof(CloseHashNode));
	lpNode->iset = iCloseSet;
	lpNode->length = clen;
	lpNode->support = support;
	lpNode->keys = ktree;
	lpNode->versionNo = 0; //note?

	if(ktree)
		ktree->setCindex(index);

	//for maintenance
	lpNode->versionNo = 0; //note?
	lpNode->splite_versionNO = 0;

	lpNode->diffSet = (int*)buf->newbuf(clen, INTSIZE);
	lpNode->diffLen = 0;

	lpNode->shareSet = (int*)buf->newbuf(clen, INTSIZE);
	lpNode->shareLen = 0;

	closeTable[index] = lpNode;

	return 1;
}

int closeHashTable::find(int *iset, int length, int &support)
{
	int i=0;
	int initIndex=0;
	int index;
	
	initIndex=set_mod(iset,length,0,hashMap,maxSize);
	index=initIndex;
	while(i<maxSize)
	{
		LPCloseHashNode lpNode=closeTable[index];
		if(lpNode!=NULL)
		{
			//bool bEqual = true; //for debug only
			bool bEqual=compareSet(iset,length, lpNode->iset, lpNode->length);
			if(bEqual)
			{
				support=lpNode->support;
				return index;
			}
		}
		else
		{
			return -1;
		}
		i++;
		//int index=getProbe(iset, length, i);   	
		index=initIndex+INCREMENT(i);  
		while(index>=maxSize)
		{
			index=index-maxSize;
		}	
	}
	return -1;
}

LPCloseHashNode closeHashTable::find(int* iset, int length)
{
	if(iset == NULL)
		return NULL;
	
	int sup;
	int index = find(iset, length, sup);

	if(index>=0)	
		return find(index);
	else
		return NULL;
}

void closeHashTable::outputClose(FSout* fout, double &closeNum)
{
	for(int i=0; i<maxSize;i++)
	{
		LPCloseHashNode lpCloseNode=closeTable[i];
		
		if(lpCloseNode==NULL)	
			continue;
		
		//output support
		int support = getCloseSupport(lpCloseNode);
		//support = lpCloseNode->support;

		if(support!= lpCloseNode->support)
		{
			//printf("closenode support error!");
			//scanf("exit");
			//exit(1);
		}

		if(support < THRESHOLD)
			continue;

		//output index
		fout->printString("[");
		fout->printDigit(i);
		fout->printString("]");
		
		//output closed pattern
		//fout->printOrderSet(lpCloseNode->length, lpCloseNode->iset, 0);
		fout->printSet(lpCloseNode->length, lpCloseNode->iset, support);
		
		//output key patterns
		K_tree* ktree = lpCloseNode->keys;
		if(ktree)
			ktree->outputKeys(fout, lpCloseNode->length);
		
		fout->printString("\n");
		closeNum++;
	}
}

/*int closeHashTable::readStat(Data* fdat)
{
	if(fdat == NULL)
	{
		printf("input file error!");
		scanf("exit");
		exit(1);
	}

	int i,j;
	Transaction *Tran = new Transaction;
	//assert(Tran!=NULL);
	
	//capture dataset informations
	for(i=0; i<2; i++)
	{
		fdat->getNextTransaction(Tran);
		switch(i)
		{
			case 0:
				TRANSACTION_NO = Tran->t[0];
				OLD_TRAN_NO = Tran->t[0];

				NET_ITEM_NO = Tran->t[1];
				ITEM_NO = Tran->t[2];
				fullNum = Tran->t[3];
				break;
			case 1:
				item_support = (int*) buf->newbuf(NET_ITEM_NO+ITEMBUFF, sizeof(int));
				memcpy(item_support, Tran->t, sizeof(int)*NET_ITEM_NO);
				for(j=NET_ITEM_NO;j<NET_ITEM_NO+ITEMBUFF;j++)
				item_support[j] = 0;
			break;

		}
	}

	return 1;
}

int closeHashTable::readClose(Data *fdat)
{
	if(fdat == NULL)
	{
		printf("input file error!");
		scanf("exit");
		exit(1);
	}

	EquiClass *ec = new EquiClass(ITEM_NO);
	
	//initialize hash_table
	//initTable(NET_ITEM_NO+ITEMBUFF);

	int* closeSet;
	int support=0, index = -255;
	K_tree* ktree = NULL;
	bool infreqEC=false;

	while(ec = fdat->getNextEC(ec, support, index, ktree))
	{	
		//hash record
		//closeSet =(int*)buf->newbuf(Tran->length+fullNum, sizeof(int));
		if(index == -1) //ec is infreq
			continue;
		
		closeSet =(int*)buf->newbuf(ec->clen, sizeof(int));
		memcpy(closeSet, ec->closeSet, sizeof(int)*ec->clen);

		LPCloseHashNode lpNode=new CloseHashNode;
		lpNode->iset = closeSet;
		//lpNode->length = Tran->length+fullNum;
		lpNode->length = ec->clen;
		lpNode->support = support;
		lpNode->keys = ktree;
		//lpNode->tids = NULL;

		closeTable[index] = lpNode;
		
		ktree = NULL;
	}
	delete ec;

	return 1;
}*/

////////// private functions ////////////////////
bool closeHashTable::rehashTable()
{
	printf("close hash table is full.\n");
	scanf("exit");
	exit(1);

	return false;
}


int closeHashTable::getCloseSupport(LPCloseHashNode closeNode)
{
	if(closeNode == NULL)
		return 0;
	
	if(closeNode->keys == NULL) //fullset
		return TRANSACTION_NO;

	K_node* node = closeNode->keys->header;

	int support=0, len =0;
	int* iset = new int[closeNode->length];
	
	while(node->itemName!=-1)
	{
		iset[len++] = node->itemName;
		node = node->par;
	}
	int kindex; //for debug
	if(len)
	{
		inssort(iset, 0, len-1);

		kindex = ECstorage->findKey(iset, len, support);
	}

	delete iset;

	return support;

}

////////////////////////////////////////////////
//	keyHashTable class functions
////////////////////////////////////////////////

////////// public functions ////////////////////
keyHashTable::keyHashTable()
{
	hashTable = NULL;
	
	keyTable = NULL;
	maxSize=0;
	currNodeNum=0;
	threshold=0;

	hashMap=NULL;
	hashMapSize=0;
}

keyHashTable::~keyHashTable()
{
	releaseTable();
	if(keyTable)
		delete keyTable;
	if(localHashMap)
		delete hashMap;
}

void keyHashTable::initTable(int *map, int maplength, int tableSize)
{
	if(map==NULL)
	{
		printf("Mod map error.");
		scanf("exit");
		exit(1);
	}

	initModMap(map,maplength);

	keyTable=new LPKeyHashNode[tableSize];
	for( int i=0;i<tableSize;i++)
	{
		keyTable[i]=NULL; 
	}
	
	maxSize = tableSize;
	currNodeNum = 0;

	threshold = (int)(LOADFACTOR*maxSize);

	currPos = 0;
	returnedNodeNum = 0;
}

void keyHashTable::initTable(int itemno, int tableSize)
{
	initModMap(itemno, hashMap, tableSize);

	if(hashMap==NULL)
	{
		printf("Mod map error.");
		scanf("exit");
		exit(1);
	}

	keyTable=new LPKeyHashNode[tableSize];
	for( int i=0;i<tableSize;i++)
	{
		keyTable[i]=NULL; 
	}
	
	maxSize = tableSize;
	currNodeNum = 0;

	threshold = (int)(LOADFACTOR*maxSize);

	currPos = 0;
	returnedNodeNum = 0;
}

int   keyHashTable::insert(int &keynum, int *&iKeySet, int klen, int support, int cindex)
{
	int r = insert(iKeySet, klen, support, cindex);

	if(r>=0)
		keynum++;

	return r;
}

int   keyHashTable::insert(int *&iKeySet, int klen, int support, int cindex)
{
	int i=0;
	int initIndex=0;
	int index;
	
	initIndex=set_mod(iKeySet,klen,0,hashMap,maxSize);
	index=initIndex;

	while(i<maxSize)
	{
		
		if(keyTable[index]==NULL)
		{
			//LPKeyHashNode lpNode=new KeyHashNode;
			LPKeyHashNode lpNode=(LPKeyHashNode)buf->newbuf(1,sizeof(KeyHashNode));
			lpNode->iset=iKeySet;
			lpNode->length=klen;
			lpNode->support=support;
			//lpNode->blFront=false;
			keyTable[index]=lpNode;
			
			lpNode->closeIndex = cindex;
			
			currNodeNum++;
			if(currNodeNum>threshold)
			{
				printf("now rehash key table from %d\n",currNodeNum);
				rehashTable();
			}
			//keynum++;
			return index;
		}
		else
		{
			LPKeyHashNode lpNode=keyTable[index];
			bool bEqual=compareSet(iKeySet,klen, lpNode->iset, lpNode->length);
			if(bEqual)
			{
				lpNode->closeIndex = cindex;
				//delete iKeySet; //added by mengling for memory leak
				//return -1;
				return index;
			}    
		}
		i++;
		//clash++;
		index=initIndex+INCREMENT(i);  
		while(index>=maxSize)
		{
			index=index-maxSize;
		}
		
	}
	return -255;
}

int keyHashTable::find(int *iset, int length, int &support)
{
	int i=0;
	int initIndex=0;
	int index;
	
	initIndex=set_mod(iset,length,0,hashMap,maxSize);
	index=initIndex;
	while(i<maxSize)
	{
		LPKeyHashNode lpNode=keyTable[index];
		if(lpNode!=NULL)
		{
			//bool bEqual = true; //for debug only
			bool bEqual=compareSet(iset,length, lpNode->iset, lpNode->length);
			if(bEqual)
			{
				support=lpNode->support;
				return index;
			}
		}
		else
		{
			return -1;
		}
		i++;
		//int index=getProbe(iset, length, i);   	
		index=initIndex+INCREMENT(i);  
		while(index>=maxSize)
		{
			index=index-maxSize;
		}	
	}
	return -1;
}

LPKeyHashNode keyHashTable::find(int* iset, int length)
{
	if(iset==NULL)
		return NULL;
	
	int sup;
	int index = find(iset, length, sup);

	return keyTable[index];
}

void keyHashTable::outputKey(FSout* fout, double &keyNum)
{
	for(int i=0; i<maxSize;i++)
	{
		LPKeyHashNode lpKeyNode=keyTable[i];
		
		if(lpKeyNode==NULL)	
			continue;
		
		//output support
		int support = 0;
		support = lpKeyNode->support;

		if(support < THRESHOLD)
			continue;

		//output index
		fout->printString("[");
		fout->printDigit(i);
		fout->printString("]");
		
		//output key pattern
		fout->printKeySet(lpKeyNode->length, lpKeyNode->iset, 0);
		
		fout->printString("(");
		fout->printDigit(support);
		fout->printString(")");
		
		fout->printString("\n");
		keyNum++;
	}
}

void keyHashTable::releaseTable()
{
	/*for(int i=0; i<maxSize;i++)
	{
		if(keyTable[i])
		{
			delete keyTable[i];
			currNodeNum--;
		}
	}*/
	if(hashMap && (*hashMap>=0))
	{
		delete []hashMap;
		hashMap = NULL;
		hashMapSize = 0;
	}

	delete keyTable;
	keyTable = NULL;
	maxSize =0;
}

KeyHashNode* keyHashTable::getNext()
{
	KeyHashNode* kn;
	
	if(returnedNodeNum == currNodeNum)
	{
		currPos = 0;
		returnedNodeNum = 0; //reset
		return NULL;
	}
	
	for(;currPos<maxSize;currPos++)
	{
		if(keyTable[currPos])
		{
			returnedNodeNum++;
			kn = keyTable[currPos++];
			return kn;
		}
	}

	currPos = 0;
	returnedNodeNum = 0; //reset
	return NULL;
}

////////// private functions ////////////////////
bool keyHashTable::rehashTable()
{
	printf("key hash table is full.\n");
	scanf("exit");
	exit(1);

	return false;
}