// fk_tree.cpp: implementation of the prefix tree class: FK_tree
//////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <assert.h>
//#include <math.h>
#include <iostream>
#include <memory.h>
#include "buffer.h"
#include "common.h"
#include "fk_tree.h"
//#include "hash_table.h"
#include "ec_storage.h"

//////////////////////////////////////////////////////
//	Internal variables
//////////////////////////////////////////////////////
int *testSet=NULL;
int *subSet=NULL;
int *localSupp=NULL;
int *globalSupp=NULL;
//int *subSupp = NULL;
//int sslen=0;

//int* local_order_item; //note, necessary?
//int* local_item_order;
//int* local_order_support;

bool* current_fi;   //to be use for maximal or close patterns.
int*  compact;      //the current itemset, represented by the set of orders in current table.
int*  supp;         //use in conditional_pattern_base  to store support temporarily

//int* ITlen;        //the number of itemset with a specific length //not necessary
int* bran;         //the number of nodes in each level
int* prefix;       //just used in enumerate itemset

int LOCAL_ITEM_NO;

static int KNODEPTRSIZE=sizeof(Knode*);
static int KNODESIZE=sizeof(Knode);
static int FKTREESIZE=sizeof(FK_tree);

//bool FK_tree::bClass= false;
//int  FK_tree::posItem=-1;
//bool Rprune = false;
//int RpruneDepth = 0;

//for debug only
int treeNo = 0;

////////////////////////////////////////////////
//	external variables & functions
////////////////////////////////////////////////
extern int* order_support;
//extern hash_table *patternTable;
//extern closeHashTable *patternTable;
extern ec_storage *ECstorage;

//////////////////////////////////////////////////////
//	Internal functions --- sorting
//////////////////////////////////////////////////////

#define SORTHRESH 9

template <class T> void swap(T* k, T* j)
{
	T temp;
	temp = *j;
	*j = *k;
	*k = temp;
}

int findpivot(const int& i, const int& j) {return (i+j)/2;}

int partition(int* array, int* temp, int l, int r, int pivot)
{
	do {
		while (array[++l] > pivot);
		while (r && array[--r] < pivot);
		swap(array+l, array+r);
		swap(temp+l, temp+r);
	}while (l < r);
	swap(array + l, array + r);
	swap(temp + l, temp + r);
	return l;
}


//Bug! Dec. 4, 2003
void inssort(int* array, int* temp, int i, int j)
{
	for (int k=i+1; k<=j; k++)
		for (int m=k; (m>i) && (array[m] > array[m-1]); m--)
		{
			swap(array+m, array+m-1);
			swap(temp+m, temp+m-1);
		}
}


void sort(int *array, int* temp, int i, int j)
{
	if(j-i < SORTHRESH) inssort(array, temp, i, j);
	else
	{
		int pivotindex = findpivot(i, j);
		swap(array+pivotindex, array+j);
		swap(temp+pivotindex, temp+j);
		int k = partition(array, temp, i-1, j, array[j]);
		swap(array+k, array+j);
		swap(temp+k, temp+j);
		if((k-i)>1) sort(array, temp, i, k-1);
		if((j-k)>1) sort(array, temp, k+1, j);
	}
}

/////////////////////////////////////////////////
//  class stack
/////////////////////////////////////////////////

stack::stack(int length, bool close)
{
	top= 0; 
	FS = new int[length];
	if(close)
		counts = new int[length];   //should change here
	else
		counts = NULL;
}


stack::~stack()
{
	delete []FS;

	if(counts) //added for memory leak
		delete counts;
}

/////////////////////////////////////
/// FK_tree functions
////////////////////////////////////

////////// public functions ////////////////////

void FK_tree::init(int old_itemno, int new_itemno)
{
	int i;
	Root = (Knode*)fp_buf->newbuf(1, KNODESIZE);
	//Root->init(NULL, -1, 0, 0);
	Root->init(NULL, -1, 0);

	if(old_itemno!=-1)
	{
		order = (int*)fp_buf->newbuf(NET_ITEM_NO, INTSIZE);
		count = (int*)fp_buf->newbuf(old_itemno, INTSIZE);
		table = (int*)fp_buf->newbuf(old_itemno, INTSIZE);
		for (i=0; i<old_itemno; i++)
		{
			order[i]=-1;
			count[i] = 0;
			table[i] = i;
		}
		for (; i<NET_ITEM_NO; i++)
			order[i]=-1;

		if(list->top==0)
			//cout<<"stack is empty, no prefix exist!"<<endl;
			printf("stack is empty, no prefix exist!\n");
		else
			prefixCount=list->counts[list->top-1-new_itemno];  //error here, 
	}      

	itemno = new_itemno;
	if(new_itemno!=0)
		head = (Knode**)fp_buf->newbuf(itemno, KNODEPTRSIZE);

	fullSet=NULL;
	fullSize=0;
	prefixSet=NULL;
	prefixSize=0;
}

FK_tree::~FK_tree()
{
}

int FK_tree::initArray(int net_itemno)
{
	int i;
	//init local parameters
	//prefixCount = TRANSACTION_NO;
	itemno = net_itemno;

	//declare local arrays
	order = (int*)fp_buf->newbuf(itemno, INTSIZE);
	table = (int*)fp_buf->newbuf(itemno, INTSIZE);
	count = (int*)fp_buf->newbuf(itemno, INTSIZE);

	//init header table, count, table, order
	head =(Knode**)(fp_buf->newbuf(itemno, KNODEPTRSIZE));

	array = NULL;

	assert(order!=NULL && table != NULL && count != NULL && head!=NULL);

	// The following is for the case when ITEM_NO is very big and fptree->itemno is very small
	for(i=0; i<itemno; i++)
	{
		table[i]=i;  //transfer the name
		order[i]=i;
		count[i] = item_support[order_item[i]];

		head[i] = (Knode*)fp_buf->newbuf(1, KNODESIZE);
		((Knode *)head[i])->init(NULL, i, count[i]);
	}


	//internal array init
	testSet=(int *)fp_buf->newbuf(itemno,INTSIZE);
	subSet=(int *)fp_buf->newbuf(itemno,INTSIZE);
	localSupp=(int *)fp_buf->newbuf(itemno,INTSIZE);
	globalSupp=(int *)fp_buf->newbuf(itemno,INTSIZE);

	bran = (int *)fp_buf->newbuf(itemno,INTSIZE); //not nessessary? note
	compact = (int *)fp_buf->newbuf(itemno,INTSIZE); //not nessessary? note
	prefix = (int *)fp_buf->newbuf(itemno,INTSIZE); //not nessessary? note

	current_fi = (bool *)fp_buf->newbuf(itemno,INTSIZE);
	supp=(int *)fp_buf->newbuf(itemno,INTSIZE);	//for keeping support of items

	for(i=0;i<itemno;i++)
	{
		localSupp[i]=0;
		globalSupp[i]=0;
		bran[i] = 0;
		supp[i] = 0;
		current_fi[i] = false;
	}

	list=new stack(itemno, true); //not nessessary? note


	return 1;
}

int FK_tree::outputTree(FSout *fsout)
{
	if(fsout == NULL)
		return 0;

	//output tree structure
	fsout->printString("# "); //# stands for fptree root

	Knode* temp = Root;

	printTree(fsout, temp->leftchild);

	return 1;
}

void FK_tree::scan1_DB(Data* fdat, double threshold)
{
	int i;
	int tranCount= 0;
	int net_itemno, max_item = NET_ITEM_NO-1;

	Transaction *Tran = new Transaction;
	assert(Tran!=NULL);

	int start=0;

	//scan through db_upd
	while((tranCount < NEW_TRAN_NO) && (Tran = fdat->getNextTransaction(Tran, true)))
	{	
		for(i=start; i<Tran->length; i++) 
		{

			if(max_item<Tran->t[i])
				max_item = Tran->t[i];

			item_support[Tran->t[i]]++;
			//item_support_new[Tran->t[i]]++;
		}

		TRANSACTION_NO++;
		tranCount++;

		if(Tran->length>MAX_TRAN_LEN)
			MAX_TRAN_LEN = Tran->length;
	}

	if(tranCount < NEW_TRAN_NO) //for user defined new_tran_no
		NEW_TRAN_NO = tranCount;

	prefixCount=TRANSACTION_NO;
	net_itemno = max_item+1; //new net_itemno

	if(net_itemno > NET_ITEM_NO+ITEMBUFF)
	{
		printf("new net_itemno error!\n");
		scanf("exit");
		exit(1);
	}

	initOrder(net_itemno); //detect new items

	NET_ITEM_NO = net_itemno;

	ITEM_NO=0;
	for(i=0; i<NET_ITEM_NO;i++)
	{
		if(item_support[i]>= THRESHOLD)
			ITEM_NO++;
	}

	if(Tran)
		delete Tran;
}

void FK_tree::insertTransaction(tranStore* ts)
{
	int j, has =0;
	int* origin;  //a vector of orders in current head table for frequent items.

	//origin = new int[NET_ITEM_NO];
	origin = testSet;
	//assert(origin!=NULL);
	for(j=0; j<NET_ITEM_NO; j++) origin[j]=-1;

	int start=0; //starting point may be 1 for multiple class cases

	for(j=start; j<ts->length; j++) 
	{
		if(item_order[ts->t[j]]!=-1) //exclude full item
		{
			if(origin[item_order[ts->t[j]]]!=-1) //for debug only
			{
				printf("repeated item detected.\n");
				scanf("exit");
				exit(1);
			}

			has++;

			origin[item_order[ts->t[j]]] = item_order[ts->t[j]];
		}

	}

	if(has)
	{
		fill_count(origin, NET_ITEM_NO, 1);
		insert(compact, 1, has);

		//transform incremental transactions
		memcpy(ts->t, compact, has*INTSIZE);
		ts->length = has;

	}

	//delete []origin;

}

void FK_tree::deleteTransaction(tranStore* ts) //delete decremental transaction to fk tree
{
	int j, has =0;
	int* origin;  //a vector of orders in current head table for frequent items.

	//origin = new int[NET_ITEM_NO];
	origin = testSet;
	//assert(origin!=NULL);
	for(j=0; j<NET_ITEM_NO; j++) origin[j]=-1;

	int start=0; //starting point may be 1 for multiple class cases

	for(j=start; j<ts->length; j++)
	{
		if(item_order[ts->t[j]]!=-1) //exclude full item
		{
			if(origin[item_order[ts->t[j]]]!=-1) //for debug only
			{
				printf("repeated item detected.\n");
				scanf("exit");
				exit(1);
			}

			has++;

			origin[item_order[ts->t[j]]] = item_order[ts->t[j]];
		}
	}

	if(has)
	{
		fill_count(origin, NET_ITEM_NO, 1);
		deletePath(compact, 1, has);

		//transform incremental transactions
		memcpy(ts->t, compact, has*INTSIZE);
		ts->length = has;
	}

	//delete []origin;
}

int FK_tree::genClose(int* keyset, int klen, int& support, int*& closeset, int& clen)
{
	if(keyset == NULL)
		return 0;

	//int *tempSet = new int[NET_ITEM_NO];
	int* tempSet = testSet;
	int tlen = 0, pos = klen-1, i;
	int sup = 0;
	int lmin, lmax, gmin, gmax; //for localSupp and globalSupp access n clearing up

	gmin = keyset[0];
	gmax = keyset[pos];
	lmin = 0;
	lmax =0;
	support =0;

	Knode* current = head[keyset[pos]]->next;
	Knode* curr;


	//traverse for close patterns and potential enumeration candidates
	//travel horizontally
	while(current!=NULL)
	{
		tlen = 0;
		sup = current->count;

		//travel up
		pos = klen-2;
		curr =  current->par;

		while(curr != NULL && curr->itemname != -1)
		{
			if(pos >=0 && curr->itemname < keyset[pos])
				break;

			if(pos >=0 && curr->itemname == keyset[pos])
			{
				pos--;
				curr = curr->par;
				continue;
			}

			tempSet[tlen++] = curr->itemname; //record nodes on the path
			curr = curr->par;
		}

		if(pos<0) //matched
		{
			//update support
			support += sup;

			if(tlen)
			{
				if(tempSet[tlen-1]<gmin)
					gmin =  tempSet[tlen-1];

				//record support of nodes on match path
				for(i=0; i<tlen; i++)
					globalSupp[tempSet[i]]+=sup;
			}

			//travel down
			CheckSubtree(current, localSupp, lmin, lmax, globalSupp); //update e support of tails

			for(i=lmin; i<=lmax; i++) //clear up localSupp for it is nt needed
				localSupp[i] = 0;

			if(lmax>=lmin && lmax>gmax)
				gmax = lmax;	
		}

		current = current->next;
	}

	//if(support>=THRESHOLD)
	//it is definately frequent
	//{

	//capture closed pattern	
	tlen = 0; //reset tempSet

	for(i=0; i<klen;i++)
		Insert(tempSet, tlen, keyset[i]); //include keyset items into closed pattern first

	for(i=gmin; i<=gmax; i++)
	{
		if(globalSupp[i] == support)
			Insert(tempSet, tlen, i);

		globalSupp[i] = 0;  //clear up globalSupp
	}

	closeset = (int*)buf->newbuf(tlen, INTSIZE);
	clen = tlen;
	memcpy(closeset, tempSet, clen*INTSIZE);

	//}
	//else
	//{
	//	for(i=gmin; i<=gmax; i++)
	//		globalSupp[i] = 0;  //clear up globalSupp
	//}


	//delete []tempSet;
	return 1;
}

int FK_tree::genNewKey(KeyHashNode* curr, int& support, int *&closeset, int& clen, int* enumlist, int enumlen)
{
	if(curr==NULL)
		return 0;

	int i, len=0;
	bool blKey;

	genClose(curr->iset, curr->length, support, closeset, clen, enumlist, enumlen);

	Copy(testSet+1, len, curr->iset, curr->length);

	for(i=0; i<enumlen; i++)
	{
		if(supp[i]<support) //possible candidate
		{
			testSet[0] = enumlist[i];
			blKey=keyCheck(testSet,len+1,supp[i],testSet[0]);

			if(blKey)
			{
				int* keySet = (int*)buf->newbuf(len+1, INTSIZE);
				memcpy(keySet, testSet, (len+1)*INTSIZE);

				ECstorage->insertNBG(keySet, len+1, supp[i]);
			}
		}
	}

	return 1;
}

void FK_tree::DecScan1_DB(Data* fdat)
{
	int i, tranCount=0;
	int net_itemno, max_item = NET_ITEM_NO-1;

	Transaction *Tran = new Transaction;
	assert(Tran!=NULL);

	int start=0;

	//scan through db_upd
	while((tranCount < DEC_TRAN_NO) && (Tran = fdat->getNextTransaction(Tran, true)))
	{	
		for(i=start; i<Tran->length; i++) 
		{
			item_support[Tran->t[i]]--;
			//item_support_new[Tran->t[i]]++;
		}

		TRANSACTION_NO--;
		tranCount++;
	}

	//if(tranCount < NEW_TRAN_NO) //for user defined new_tran_no
	
	DEC_TRAN_NO = tranCount;

	prefixCount=TRANSACTION_NO;

	ITEM_NO=0;
	for(i=0; i<NET_ITEM_NO;i++)
	{
		if(item_support[i]>= THRESHOLD)
			ITEM_NO++;
	}

	if(Tran)
		delete Tran;
}

bool FK_tree::GlobalKeyCheck(int *iSet, int length, int support)
{
	int i;
	if(length<=1)
		return true;

	int currSupport=0;
	for(i=1;i<length;i++)
		subSet[i-1]=iSet[i];
	for(i=0;i<length;i++)
	{
		if(i>0)
			subSet[i-1]=iSet[i-1];

		int index=ECstorage->findKey(subSet,length-1, currSupport);
		if(index<0)
			return false;
		if(support>=currSupport)
			return false;
	}
	return true;
} //should not copy the itemset.

////////// protected functions ////////////////////

int FK_tree::printTree(FSout *fsout, Knode* current)
{
	if(fsout == NULL || current == NULL)
		return 0;

	Knode* temp = current;
	while(temp != NULL)
	{
		fsout->printDigit(temp->itemname);
		fsout->printString(":");
		fsout->printDigit(temp->count);
		fsout->printString(" ");

		if(temp->leftchild)
			printTree(fsout, temp->leftchild);

		fsout->printString("/");
		temp = temp->rightsibling;
	}

	//fsout->printString("/");
	return 1;
}

int FK_tree::initOrder(int net_itemno)
{

	int i;

	//capture new items
	if(net_itemno > NET_ITEM_NO) //here, net_itemno is e updated one, NET_ITEM_NO is the previous one
	{ 
		for(i=NET_ITEM_NO;i<net_itemno;i++)
		{
			item_order[i] = VALID_ITEM_NO;
			order_item[VALID_ITEM_NO] = i;
			VALID_ITEM_NO++;
		}
	}

	return 1;
}

void FK_tree::fill_count(int* origin, int len, int support)
{
	int i, j=0;
	for(i=0; i<len; i++)
	{
		if(origin[i]!=-1)
		{
			compact[j++]=i; //just save the new order
			origin[i] = -1;
		}
	}

	/*if(array)
	{
		int comp_len = j;
		for(i=comp_len-1; i>0 && compact[i]>SUDDEN; i--)
			for(j=i-1; j>=0; j--)
				array[itemno-1-compact[i]][compact[i]-compact[j]-1]+=support;
	}*/
}

Knode *FK_tree::insert(int* compact, int counts, int current)
{
	Knode* child = (Knode *)Root;
	Knode* temp, *temp1=NULL;
	int i=0;

	while(i<current)
	{
		for(temp=child->leftchild; temp!=NULL; temp =temp->rightsibling)
		{
			if(temp->itemname==table[compact[i]])break;
			if(temp->rightsibling==NULL)temp1 = temp;
		}

		if(!temp)break;

		temp->count+=counts;
		child=temp;
		i++;
	}
	while(i<current)
	{   
		child = child->append(this, temp1, table[compact[i]], counts);
		bran[i]++;
		i++;
	}

	return child;
}

Knode *FK_tree::deletePath(int* compact, int counts, int current)
{
	Knode* child = (Knode *)Root;
	Knode* temp, *temp1=NULL;
	int i=0;

	while(i<current)
	{
		for(temp=child->leftchild; temp!=NULL; temp =temp->rightsibling)
		{
			if(temp->itemname==table[compact[i]])break;
			if(temp->rightsibling==NULL)
			{
				printf("delete path error!\n");
				scanf("exit");
				exit(1);
			}

			temp1 = temp; //record the node one e left of target node
		}

		temp->count-=counts;
		head[temp->itemname]->count-=counts;

		if(temp->count==0)
		{
			//detach the subtree from glotree
			temp->detach(this, temp1);

			break;
		}

		child=temp;
		i++;
	}

	return child;
}

bool FK_tree::CheckSubtree(Knode *node, int *localSupp, int &start, int &end, int *sumSupp)
{
	start=node->itemname;
	end=node->itemname;
	int i;

	Knode *curr=node;
	while(curr!=NULL)
	{
		localSupp[curr->itemname]+=curr->count; 
		if(curr->itemname<start)
			start=curr->itemname;
		if(curr->itemname>end)
			end=curr->itemname;
		bool bStop=false;


		int support=curr->tailSupport;
		//int support = 0;
		Knode *temp=curr->leftchild;
		while(temp!=NULL)
		{
			support=support+temp->count;
			temp=temp->rightsibling;
		}
		if(support<curr->count)
			bStop=true;

		if(!bStop)
		{
			for(int i=0;i<curr->tailSize;i++)
			{
				localSupp[curr->tailSet[i]]+=curr->tailSupport; 
				if(curr->tailSet[i]<start)
					start=curr->tailSet[i];
				if(curr->tailSet[i]>end)
					end=curr->tailSet[i];
			}//should change this part.
		}//end handling nonempty tail*/

		if(curr->leftchild==NULL)
			bStop=true;
		if(!bStop)
		{
			curr=curr->leftchild;
			continue;
		}
		if(curr==node)
			break;
		if(curr->rightsibling!=NULL)
		{
			curr=curr->rightsibling;
			continue;
		}
		//finish the current tree;
		while((curr->rightsibling==NULL)&&(curr!=node))
			curr=curr->par;
		if(curr==node)
			break;
		curr=curr->rightsibling;
	}//end while
	localSupp[node->itemname]=0; 
	sumSupp[node->itemname]=0;
	for(i=start;i<=end;i++)
	{
		if(localSupp[i]!=node->count)
		{
			start++;
			localSupp[i]=0;
			sumSupp[i]=0;
		}else 
			break;
	}
	for(i=end;i>=start;i--)
	{
		if(localSupp[i]!=node->count)
		{
			end--;
			localSupp[i]=0;
			sumSupp[i]=0;
		}else
			break;
	}
	for(i=start; i<=end;i++)
	{
		if(localSupp[i]==node->count)
			sumSupp[i]+=localSupp[i];  
	}
	return true;
}

int FK_tree::genClose(int* keyset, int klen, int &support, int*& closeset, int& clen, int* enumlist, int enumlen)
{
	if(keyset==NULL)
		return 0;
	//int *tempSet = new int[NET_ITEM_NO];
	int* tempSet = testSet;
	int tlen = 0, pos = klen-1, i, j;
	int sup = 0;
	int lmin, lmax, gmin, gmax; //for localSupp and globalSupp access n clearing up

	gmin = keyset[0];
	gmax = keyset[pos];
	lmin = 0;
	lmax =0;
	support =0;

	Knode* current = head[keyset[pos]]->next;
	Knode* curr;


	//traverse for close patterns and potential enumeration candidates
	//travel horizontally
	while(current!=NULL)
	{
		tlen = 0;
		sup = current->count;

		//travel up
		pos = klen-2;
		curr =  current->par;

		while(curr != NULL && curr->itemname != -1)
		{
			if(pos >=0 && curr->itemname < keyset[pos])
				break;

			if(pos >=0 && curr->itemname == keyset[pos])
			{
				pos--;
				curr = curr->par;
				continue;
			}

			tempSet[tlen++] = curr->itemname; //record nodes on the path
			curr = curr->par;
		}

		if(pos<0) //matched
		{
			//update support
			support += sup;

			if(tlen)
			{
				if(tempSet[tlen-1]<gmin)
					gmin =  tempSet[tlen-1];

				//record support of nodes on match path
				for(i=0; i<tlen; i++)
					globalSupp[tempSet[i]]+=sup;
			}

			//travel down
			CheckSubtree(current, localSupp, lmin, lmax, globalSupp); //update e support of tails

			for(i=lmin; i<=lmax; i++) //clear up localSupp for it is nt needed
				localSupp[i] = 0;

			if(lmax>=lmin && lmax>gmax)
				gmax = lmax;	
		}

		current = current->next;
	}

	//if(support>=THRESHOLD)
	//{
	
	//capture closed pattern & record support for enumlist items
	tlen = 0; //reset tempSet
	j=0;

	for(i=0; i<klen;i++)
		Insert(tempSet, tlen, keyset[i]); //include keyset items into closed pattern first

	
	for(i=0; i<enumlen;i++)
	{
		if(enumlist[i]<gmin)
		{
			supp[i]=0;
			continue;
		}

		if(enumlist[i]>gmax)
		{
			supp[i]=0;
			break;
		}

		supp[i] = globalSupp[enumlist[i]];

	}

	for(i=gmin; i<=gmax; i++)
	{
		/*if(j < enumlen && i == enumlist[j]) //capture support of enum items
		{
			supp[j] = globalSupp[i];
			j++;
		}*/
		
		if(globalSupp[i] == support)
			Insert(tempSet, tlen, i);

		globalSupp[i] = 0;  //clear up globalSupp
	}

	closeset = (int*)buf->newbuf(tlen, INTSIZE);
	clen = tlen;
	memcpy(closeset, tempSet, clen*INTSIZE);

	//}
	//else
	//{
	//	for(i=gmin; i<=gmax; i++)
	//		globalSupp[i] = 0;  //clear up globalSupp
	//}


	//delete []tempSet;
	return 1;
}

bool FK_tree::keyCheck(int *iSet, int length, int support, int newItem)
{
	int i;
	if(length<=2)
		return true;

	int currSupport=0;
	for(i=1;i<length;i++)
		subSet[i-1]=iSet[i];
	for(i=0;i<length;i++)
	{
		if(i>0)
			subSet[i-1]=iSet[i-1];
		if(iSet[i]==newItem)
			continue;//skip the last one 

		int index=ECstorage->findKey(subSet,length-1, currSupport);
		if(index<0)
			return false;
		if(support>=currSupport)
			return false;
	}
	return true;
} //should not copy the itemset.