#include <assert.h>#include "../Global.h"#include "../ProjDB.h"#if defined(_ANOTHER_CLOSED_APPROACH)#include "ClosedTree.h"ItemSet supSet;ItemSet subSet;int zzz=0;bool TreeNodeLess( TreeNode * a, TreeNode * b ){	if( (*a).ItemIsIntra == (*b).ItemIsIntra )		return (*a).Item < (*b).Item; 	else if( (*a).ItemIsIntra && !(*b).ItemIsIntra )		return true;	else		return false;}int TreeNodeCompare( TreeNode ** a, TreeNode ** b ){	if( (*(*a)).ItemIsIntra == (*(*b)).ItemIsIntra )		if( (*(*a)).Item == (*(*b)).Item )			return 0;		else if( (*(*a)).Item < (*(*b)).Item )			return -1;		else			return 1;	else if( (*(*a)).ItemIsIntra && !(*(*b)).ItemIsIntra )		return -1;	else		return 1;}inline TreeNode * GetLastItemSet(TreeNode * treeNode, ItemSet *itemSet){	int *itemArray=itemSet->ItemArray;	int i=0;	itemSet->reset();	do {		itemArray[i++]=treeNode->Item;		if (!treeNode->ItemIsIntra)			break;		else			treeNode=treeNode->Parent;	} while (treeNode->Items > 0);		itemSet->Count=i;	return (treeNode->Parent);}inline int isContained_DBSizeEqual(struct PROJ_DB *pDB, TreeNode *currentLevel, TreeNode *candidate) {		int		myItem = pDB->Item;	bool	myItemIsIntra = pDB->ItemIsIntra;	int		dir;	bool	isContained;	TreeNode *supNode;	TreeNode *subNode;	if ((myItem != candidate->Item) || (candidate->Items == (currentLevel->Items+1))) 		return 0;	if ( candidate->Items > (currentLevel->Items + 1))		dir=1;	else		dir=-1;	if (candidate->ItemIsIntra) {		if (myItemIsIntra) {			candidate=candidate->Parent;		}		else {			//in this case, supNode must be candidate, subNode must be currentLevel			while (candidate->ItemIsIntra && candidate->Items >0)				candidate = candidate ->Parent;			candidate=candidate->Parent;			if ((candidate->Items < currentLevel->Items) || (candidate->ItemsetNumber < currentLevel->ItemsetNumber))				return 0;					}	}	else {		if (myItemIsIntra) {			//in this case, supNode must be currentLevel, subNode must be candidate			while (currentLevel->ItemIsIntra && currentLevel->Items >0)				currentLevel = currentLevel ->Parent;			currentLevel=currentLevel->Parent;			if ((candidate->Items > currentLevel->Items) || (candidate->ItemsetNumber > currentLevel->ItemsetNumber))				return 0;					}		else {			candidate=candidate->Parent;		}	}		if (currentLevel->Items == 0) {		return 1;	}	if (candidate->Items == 0) {		return -1;	}	if ( dir == 1) {		supNode=candidate;		subNode=currentLevel;		}	else {		supNode=currentLevel;		subNode=candidate;	}	isContained=false;	supNode=GetLastItemSet(supNode, &supSet);	subNode=GetLastItemSet(subNode, &subSet);	while (1) {		if (subSet.IsSubsetOf(&supSet)) {			if (subNode->Items == 0) {				isContained=true;				break;			}			if ((supNode->Items >= subNode->Items) && (supNode->ItemsetNumber >= subNode->ItemsetNumber)) {				supNode=GetLastItemSet(supNode, &supSet);				subNode=GetLastItemSet(subNode, &subSet);			}			else				break;		}		else {			if (supNode->Items == 0) // unnecessary to check any more.				break;			if ((supNode->Items >= subNode->Items) && (supNode->ItemsetNumber >= subNode->ItemsetNumber)) {				supNode=GetLastItemSet(supNode, &supSet);			}			else				break;		}	}	if (isContained)		return dir;	else		return 0;}void updateNodeInfo(TreeNode *treeNode, int extraItems, int extraItemsetNumber){	NodeVector::iterator it, endit;	treeNode->Items += extraItems;	treeNode->ItemsetNumber += extraItemsetNumber;	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {		if ((*it)->Parent == treeNode)				updateNodeInfo((*it), extraItems, extraItemsetNumber);	}}void updateOldNodeInfo(TreeNode* parent, TreeNode *pNode, TreeNode *qNode){	TreeNode **Res;	Res = (TreeNode **) bsearch( &pNode, &(*(parent->Children))[0], (*(parent->Children)).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );	*Res=qNode;}void checkNodeInfo(TreeNode *treeNode){		int items;	int itemset_number;	TreeNode *parent = treeNode->Parent;	NodeVector::iterator it, endit;	if( treeNode->ItemIsIntra ) {		itemset_number = parent->ItemsetNumber;		items = parent->Items + 1;	}	else {		itemset_number = parent->ItemsetNumber + 1;		items = parent->Items + 1;	}	if ((items != treeNode->Items) || (itemset_number != treeNode->ItemsetNumber))		printf("Node Info: Items or ItemsetNumber Error");	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {		if ((*it)->Parent == treeNode)			checkNodeInfo((*it));	}		}//int qqq;int addSequence(struct PROJ_DB *pDB, TreeNode **currentLevelp, ReverseHashTable *reverseTable){	TreeNode   *pNode, *qNode;	TreeNode *currentLevel=*currentLevelp;	ReverseMap pMap;	ReverseHashTable::iterator it, endit;	int ret, myNumOfItems;		/*printf("SSN: %d Item: %d\n", ++qqq, pDB->Item);	if (qqq == 20496) {		printf("hello\n");	}*/		//myNumOfItems=pDB->NumOfItems + pDB->m_nMaxSup - pDB->m_nSup;	myNumOfItems=pDB->NumOfItems + pDB->m_nMaxSup;	//myNumOfItems=pDB->NumOfItems;	/*if (myNumOfItems == 3378012)			printf("GUGU\n");	*/	pMap=(*reverseTable).equal_range(myNumOfItems);	for (it=pMap.first, endit=pMap.second; it != endit; it++) {		pNode=(*it).second;		if (pNode->Support != pDB->m_nMaxSup)			continue;		ret=isContained_DBSizeEqual(pDB, currentLevel, pNode);		switch (ret) {			case 0:				continue;			case 1:  //Backward SubPattern				//(*(currentLevel->Children)).push_back(pNode);				//(*(currentLevel->IntraChildren))[pDB->Item]=pNode;				//qNode is a mirror of pNode, but has slight different				//the major goal is to let closed_maxPruning much easier				qNode= new TreeNode();				qNode= currentLevel->AddChildWithoutChecking( pDB->Item, pDB->ItemIsIntra, pDB->m_nMaxSup);				qNode->SetProjDBSize(myNumOfItems);				qNode->Children=pNode->Children;				return EQUAL_PROJECT_DB_SIZE;			case -1: //Backward SuperPattern				qNode= new TreeNode(pNode);				updateOldNodeInfo(pNode->Parent, pNode, qNode);				if (pDB->ItemIsIntra) {					updateNodeInfo(pNode, 								   currentLevel->Items - pNode->Parent->Items,								   currentLevel->ItemsetNumber - pNode->Parent->ItemsetNumber);					//checkNodeInfo(currentLevel);					pNode->ItemIsIntra=true;					pNode->Parent=currentLevel;					(*(currentLevel->Children)).push_back(pNode);					inplace_merge((*(currentLevel->Children)).begin(), (*(currentLevel->Children)).end()-1, 								  (*(currentLevel->Children)).end(), TreeNodeLess );				}				else {					updateNodeInfo(pNode, 								   currentLevel->Items - pNode->Parent->Items,								   currentLevel->ItemsetNumber - pNode->Parent->ItemsetNumber);					//checkNodeInfo(currentLevel);					//pNode->Parent->Children->erase(pNode);					pNode->ItemIsIntra=false;					pNode->Parent=currentLevel;					(*(currentLevel->Children)).push_back(pNode);					inplace_merge((*(currentLevel->Children)).begin(), (*(currentLevel->Children)).end()-1, 								  (*(currentLevel->Children)).end(), TreeNodeLess );				}								//reverseTable->erase(it);				//reverseTable->insert(ReverseHashTable::value_type(myNumOfItems, qNode));									return EQUAL_PROJECT_DB_SIZE;			default:				break;		}	}		zzz++;	pNode= new TreeNode();	pNode= currentLevel->AddChildWithoutChecking( pDB->Item, pDB->ItemIsIntra, pDB->m_nMaxSup);	pNode->SetProjDBSize(myNumOfItems);	(*currentLevelp)=pNode;	reverseTable->insert(ReverseHashTable::value_type(myNumOfItems, pNode));	return INEQUAL_PROJECT_DB_SIZE;}void closed_maxChecking(TreeNode *pNode, TreeNode *pNode_parent, TreeNode *qNode){	NodeVector::iterator it, endit;	if (pNode == NULL)		return;	if (pNode->Parent != pNode_parent)		return;#if defined (_ANOTHER_MAX_APPROACH)		pNode->max=false;#else	if (pNode->Support == qNode->Support)		pNode->closed = false;#endif	for (it=qNode->Children->begin(), endit=qNode->Children->end(); it != endit; it++) 		closed_maxChecking (pNode->FindChild((*it)->Item, (*it)->ItemIsIntra), pNode, (*it));}void closed_maxPruning(TreeNode *treeNode, TreeNode *parent){	NodeVector::iterator it, endit, ti;	bool myItemIsIntra=treeNode->ItemIsIntra;	TreeNode *pNode;#if defined (_ANOTHER_MAX_APPROACH)