}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;}TreeNode::TreeNode( int anItem, bool IsIntra, int Sup, TreeNode * aParent ){	Children = NULL;	Parent = aParent;	ItemsetNumber = 0;	Item = anItem;	ItemIsIntra = IsIntra;	Support = Sup;}inline TreeNode * TreeNode::FindChild( int anItem, bool Intra ){	TreeNode ** Res;	TreeNode * tmp = new TreeNode( anItem, Intra );	Res = (TreeNode **) bsearch( &tmp, (*Children).begin(), (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );	delete tmp;	if( Res )		return (*Res);	else		return NULL;}inline TreeNode * TreeNode::FindChild( TreeNode * Child ){	TreeNode ** Res;	Res = (TreeNode **) bsearch( &Child, (*Children).begin(), (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );	if( Res )		return (*Res);	else		return NULL;}inline void TreeNode::DelChild( TreeNode * Child ){	TreeNode ** Res;	if( Children==NULL )		return;	if( (*Children).size() == 1 )	{		Res = (*Children).begin();	} else {		Res = (TreeNode **) bsearch( &Child, (*Children).begin(), (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );	}	if( Res )	{		(*Children).erase( (Res) );	}}TreeNode * TreeNode::AddChild( TreeNode * Child ) { 	TreeNode * Result = NULL;	if( Children == NULL )	{		Children = new NodeVector();		(*Children).push_back( Child );		Result = Child;		(*Child).Parent = this;		if( (*Child).ItemIsIntra )			(*Child).ItemsetNumber = ItemsetNumber;		else			(*Child).ItemsetNumber = ItemsetNumber + 1;	} else {		Result = FindChild( Child );		if( Result == NULL )		{			Result = Child;			(*Children).push_back( Child ); 			// To keep the children vector sorted.			inplace_merge( (*Children).begin(), (*Children).end()-1, (*Children).end(), TreeNodeLess );			(*Child).Parent = this;			if( (*Child).ItemIsIntra )				(*Child).ItemsetNumber = ItemsetNumber;			else				(*Child).ItemsetNumber = ItemsetNumber + 1;		} else {			if( (*Child).Support > (*Result).Support )				(*Result).Support = (*Child).Support;			delete Child;		}	}	return Result;}inline int TreeNode::NumOfChildren(){	if( Children==NULL )		return 0;	else		return (*Children).size();}inline int TreeNode::MaxChildSupport(){	int MaxChildSup = 0;  NodeVector::iterator Itrtr;	if( Children==NULL )		return 0;	for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++ )		if( (*(*Itrtr)).Support > MaxChildSup )			MaxChildSup = (*(*Itrtr)).Support;	return MaxChildSup;}bool TreeNode::LastItemOfSequence(){	if( Children==NULL )		return true;	if( MaxChildSupport() < Support )		return true;	return false;}void TreeNode::PrintRules( FILE * aFile, int * SeqBuf, int SeqLen, SequenceList * aSeqTree, SeqList * aSeqList, int NumOfItems ){	Sequence * aSeq;	int MaxChildSupport = 0;  NodeVector::iterator Itrtr;	SeqBuf[ SeqLen ] = Item;	if( Children != NULL )	{		for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++ )		{			if( !(*(*Itrtr)).ItemIsIntra )			{				SeqBuf[ SeqLen + 1 ] = -1;				(*(*Itrtr)).PrintRules( aFile, SeqBuf, SeqLen + 2, aSeqTree, aSeqList, NumOfItems + 1 );			} else {				(*(*Itrtr)).PrintRules( aFile, SeqBuf, SeqLen + 1, aSeqTree, aSeqList, NumOfItems + 1 );			}			if( (*(*Itrtr)).Support > MaxChildSupport )			{				MaxChildSupport = (*(*Itrtr)).Support;			} 		}		if( MaxChildSupport < Support )		{			aSeq = new Sequence( SeqBuf, SeqLen + 1, Support );			gnResSizeCount[NumOfItems]++;			if( aSeqList==NULL )			{				(*aSeq).Print( aFile );				delete aSeq;			} else {				(*aSeqList).push_back( aSeq );				// To keep the List vector sorted.				inplace_merge( (*aSeqList).begin(), (*aSeqList).end()-1, (*aSeqList).end(), SeqGreater );			}			(*aSeqTree).Size++;		}	} else {		aSeq = new Sequence( SeqBuf, SeqLen + 1, Support );		gnResSizeCount[NumOfItems]++;		if( aSeqList==NULL )		{			(*aSeq).Print( aFile );			delete aSeq;		} else {			(*aSeqList).push_back( aSeq );			// To keep the List vector sorted.			inplace_merge( (*aSeqList).begin(), (*aSeqList).end()-1, (*aSeqList).end(), SeqGreater );		}		(*aSeqTree).Size++;	}}void TreeNode::Print( char * PrefixString, FILE * aFile ){  NodeVector::iterator Itrtr;	if( ItemIsIntra )		fprintf( aFile, "%sNode = _%d   Support = %d   ItemsetNumber = %d\n", PrefixString, Item, Support, ItemsetNumber );	else		fprintf( aFile, "%sNode =  %d   Support = %d   ItemsetNumber = %d\n", PrefixString, Item, Support, ItemsetNumber );	if( Children != NULL && NumOfChildren() > 0 )	{		char tmpString[256] = "   ";		fprintf( aFile, "  %sChildren\n", PrefixString );		strncat( tmpString, PrefixString, 250 );		//strcat( tmpString, "  " );		for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++ )		{			//fprintf( aFile, "    " );			(*(*Itrtr)).Print( tmpString, aFile );		}	}	//fprintf( aFile, "\n" );}TreeNode::~TreeNode(){	NodeVector::iterator Itrtr;	if( Children )		for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++)			delete *Itrtr;}//************************//************************//************************//************************bool HdrTreeNodeLess( TreeNode * a, TreeNode * b ){	return a > b;}int HdrTreeNodeCompare( TreeNode ** a, TreeNode ** b ){	if( *a < *b )		return 1;	else if( *a > *b )		return -1;	else   		return 0;}SequenceList::SequenceList( int ItemsCount ){	PeakNumOfTreeNodes = 0;	NumOfTreeNodes = 0;	Root = new TreeNode();	IncNumOfTreeNodes();	NumOfItems = ItemsCount;	Header = new NodeVector[ NumOfItems ];	NumOfAdds = 0;	NumOfDels = 0;	NumOfAddIfClosed = 0;	NumIsClosedSubsetOfBranch = 0;	NumIsClosedSupersetOfBranch = 0;}inline void SequenceList::IncNumOfTreeNodes(){	NumOfTreeNodes++;	if( NumOfTreeNodes > PeakNumOfTreeNodes )		PeakNumOfTreeNodes = NumOfTreeNodes;}inline void SequenceList::DecNumOfTreeNodes(){	NumOfTreeNodes--;}// Returns the item in the last itemset of aSeq, with shortest header list.int SequenceList::LeastFreqInHeader( Sequence * aSeq ){	int * ItemPtr;	int Res = -1;	int Min = 10000000;	int HeaderSize;	for( ItemPtr=(*aSeq).StartPtr+(*aSeq).Len-1; *ItemPtr!=-1 && ItemPtr>=(*aSeq).StartPtr; ItemPtr-- )	{		HeaderSize = Header[*ItemPtr].size();		if( HeaderSize < Min )		{			Min = HeaderSize;			Res = *ItemPtr;		}		if( Min==0 ) break;	}	return Res;}// Returns true, if aSeq is a subset of the sequence in the tree with aNode as its last Item.bool SequenceList::IsClosedSubsetOfBranch( Sequence * aSeq, TreeNode * aNode ){	int * ItemPtr;	int * EndOfItemset;	int NumOfRemItemsets;	TreeNode * CurNode = aNode;	NumIsClosedSubsetOfBranch++;	NumOfRemItemsets = (*aSeq).NumOfItemSets();	if( (*CurNode).ItemsetNumber < NumOfRemItemsets || (*aSeq).Support > (*CurNode).Support )		return false;	ItemPtr = (*aSeq).StartPtr+(*aSeq).Len-1;	EndOfItemset = ItemPtr;	// For all itemsets in the sequence.	while( ItemPtr >= (*aSeq).StartPtr )	{		// For this itemset.		while( true )		{			if( (*CurNode).Item == *ItemPtr )			{				ItemPtr--;				if( ItemPtr < (*aSeq).StartPtr )					return true;				// Check previous itemset in the sequence.				if( *ItemPtr == -1 )				{					ItemPtr--;					break;				}			}			if( !(*CurNode).ItemIsIntra )			{				if( (*CurNode).ItemsetNumber <= NumOfRemItemsets )					return false;				ItemPtr = EndOfItemset;			}			CurNode = (*CurNode).Parent;		}		NumOfRemItemsets--;		//Move to the end of the previous itemset.		while( (*CurNode).ItemIsIntra && (*CurNode).Parent!=NULL )			CurNode = (*CurNode).Parent;		CurNode = (*CurNode).Parent;		EndOfItemset = ItemPtr;	}	return false;}// Returns true, if aSeq is a superset of the sequence in the tree with aNode as its last element.bool SequenceList::IsClosedSupersetOfBranch( Sequence * aSeq, TreeNode * aNode ){	int * ItemPtr;	TreeNode * EndOfItemset;	int NumOfRemItemsets;	TreeNode * CurNode = aNode;	NumIsClosedSupersetOfBranch++;	NumOfRemItemsets = (*aSeq).NumOfItemSets();	if( (*CurNode).ItemsetNumber > NumOfRemItemsets || (*CurNode).Support > (*aSeq).Support )		return false;	ItemPtr = (*aSeq).StartPtr+(*aSeq).Len-1;	EndOfItemset = aNode;	while( ItemPtr >= (*aSeq).StartPtr )	{		// For this itemset.		//while( true )		while( ItemPtr >= (*aSeq).StartPtr )		{			if( (*CurNode).Item == *ItemPtr )			{				//if( (*(*CurNode).Parent).ItemsetNumber == 0 )				if( (*(*CurNode).Parent).ItemsetNumber <= 0 )					return true;				// Check previous itemset in the sequence.				if( !(*CurNode).ItemIsIntra )				{					CurNode = (*CurNode).Parent;					break;				}				CurNode = (*CurNode).Parent;			}			if( *ItemPtr == -1 )			{				NumOfRemItemsets--;				if( (*CurNode).ItemsetNumber > NumOfRemItemsets )					return false;				CurNode = EndOfItemset;			}			ItemPtr--;		}		//Move to the end of the previous itemset.		while( *ItemPtr!=-1 && ItemPtr >= (*aSeq).StartPtr )			ItemPtr--;		ItemPtr--;		EndOfItemset = CurNode;	}	return false;}bool SequenceList::IsContained( Sequence * aSeq ){	int NumOfItemSets;	int anItem;  NodeVector::iterator Itrtr;	if( (*aSeq).Len == 0 )		return true;	// Just check for the item in the item list with shortest header list.	//anItem = LeastFreqInHeader( aSeq );	anItem = *((*aSeq).StartPtr+(*aSeq).Len-1); // Last Item of the sequence.	if( Header[anItem].size() == 0 )		return false; 	NumOfItemSets = (*aSeq).NumOfItemSets();	for( Itrtr = Header[anItem].begin(); Itrtr != Header[anItem].end(); Itrtr++ )	{		if( (*(*Itrtr)).ItemsetNumber < NumOfItemSets || (*(*Itrtr)).Support < (*aSeq).Support )			continue;				if( IsClosedSubsetOfBranch( aSeq, (*Itrtr) ) )			return true;	}	return false;}void SequenceList::RemoveFromHeaderList( TreeNode * aNode ){  NodeVector::iterator Itrtr;	Itrtr = FindInHeaderList( aNode ) ;	while( Itrtr!=NULL )	{		Header[(*aNode).Item].erase( Itrtr );		Itrtr = FindInHeaderList( aNode ) ;	}/*	for( Itrtr = Header[(*aNode).Item].begin(); Itrtr<Header[(*aNode).Item].end(); Itrtr++ )	{		if( (*Itrtr) == aNode )			Itrtr = Header[(*aNode).Item].erase( Itrtr );	}*/}void SequenceList::DeleteSequence( TreeNode * aNode ){	TreeNode * tmpNode;	TreeNode * tmpChildNode;	int aSup;	int NewSup;	aSup = (*aNode).Support;	tmpNode = aNode;	while( (*tmpNode).Support==aSup && (*tmpNode).Parent!=NULL && (*tmpNode).NumOfChildren() == 0 )	{		RemoveFromHeaderList( tmpNode );		tmpChildNode = tmpNode;		tmpNode = (*tmpNode).Parent;		(*tmpNode).DelChild( tmpChildNode );		delete tmpChildNode;		DecNumOfTreeNodes();	}	if( (*tmpNode).Support==aSup && (*tmpNode).Parent!=NULL )	{		NewSup = (*tmpNode).MaxChildSupport();		(*tmpNode).Support = NewSup;		tmpNode = (*tmpNode).Parent;	}	while( (*tmpNode).Support==aSup && (*tmpNode).Parent!=NULL )	{		if( (*tmpNode).Support > (*tmpNode).MaxChildSupport() )			(*tmpNode).Support = NewSup;		tmpNode = (*tmpNode).Parent;	}}void SequenceList::DeleteClosedSubsets( Sequence * aSeq ){