#if defined( _USE_STRING_ELEMINATION )bool SeqTree::IsContained( const struct PROJ_DB *proj_db, int * aSeqPtr ){	Sequence * aSeq;	SeqWrap * aSeqWrap;	aSeqWrap = new SeqWrap( aSeqPtr );	if( !(*aSeqWrap).IsEmpty() )	{		aSeq = new Sequence( proj_db, aSeqPtr );		return IsContained( aSeq );	} else {		return false;	}}#endif // defined( _USE_STRING_ELEMINATION )bool SeqTree::IsContained( Sequence * aSeq ){	int anItem;	ItemSet * LastItemSet;  NodeVector::iterator Itrtr;  //NodeList::iterator Itrtr;	if( (*aSeq).NumOfElements() == 0 ) return true;	(*aSeq).MoveLast();	LastItemSet = (*aSeq).Current();	// Just check for the item in the item list with shortest header list.	anItem = LeastFreqInHeader(LastItemSet);	if( Header[anItem].size() == 0 ) return false; 	for( Itrtr = Header[anItem].begin(); Itrtr != Header[anItem].end(); Itrtr++)	{		// Header list is sorted based on the level, 		// so stop as soon as level is less than # elements.		if( (*(*Itrtr)).Level < (*aSeq).NumOfElements() ) // 123			break; // 123		if( IsSubsetOfBranch( aSeq, (*Itrtr) ) )			return true;	}	return false;}// If aSeq is a superset of the sequence in the tree with aNode as its last element.bool SeqTree::IsSupersetOfBranch( Sequence * aSeq, TreeNode * aNode ){	int NumOfRemElmnts;	ItemSet * anItemSet;	TreeNode * CurNode;	NumIsMaxSubsetOf++;	if( (*aNode).NumOfChildren() > 0 || (*aNode).Level > (*aSeq).NumOfElements() )		return false;							(*aSeq).MoveLast();	anItemSet = (*aSeq).Current();	CurNode = aNode;	NumOfRemElmnts = (*aSeq).NumOfElements();	if( (*CurNode).Level > NumOfRemElmnts )		return false;		while( true )	{		if( (*CurNode).Level == 0 )			return false;		if( (*(*CurNode).Item).IsSubsetOf( anItemSet ) )		{			CurNode = (*CurNode).Parent;			(*aSeq).MovePrev();			anItemSet = (*aSeq).Current();			NumOfRemElmnts--;			if( (*CurNode).Level == 0 )				return true;		} else {			(*aSeq).MovePrev();			anItemSet = (*aSeq).Current();			NumOfRemElmnts--;			if( (*CurNode).Level > NumOfRemElmnts )				return false;		}	}}void SeqTree::PrintHeaderList( int anItem ){	printf(" ======= Size of the Header list for item %d =%d \n", anItem, Header[anItem].size() );  NodeVector::iterator myIt;  NodeVector::iterator BIt;  NodeVector::iterator EIt;  //NodeList::iterator myIt;  //NodeList::iterator BIt;  //NodeList::iterator EIt;	BIt = Header[anItem].begin();	EIt = Header[anItem].end();	EIt--;	//printf(" Head = " );	//(*(*(*BIt)).Item).Print();	//printf("\n End = " );	//(*(*(*EIt)).Item).Print();	//printf("\n" );	for( myIt = Header[anItem].begin(); myIt != Header[anItem].end(); myIt++)	{		try 		{			(*(*(*myIt)).Item).Print();			printf( "%d %d", (*(*myIt)).Level, (*myIt) ); 		}		catch(...) 		{			printf("*Err*" );		}	}	printf("\n =================== End\n" );}void SeqTree::DeleteSubsets( Sequence * aSeq ){	int anItem;	ItemSet * anItemSet;  ElementVector::iterator ElementItrtr;  NodeVector::iterator Itrtr;  //NodeList::iterator Itrtr;  NodeVector::iterator tmpItrtr;  //NodeList::iterator tmpItrtr;	// For each element, anItemSet, in aSeq.	for( ElementItrtr = (*aSeq).Elements.begin(); ElementItrtr != (*aSeq).Elements.end(); ElementItrtr++)	{		anItemSet = (*ElementItrtr);		// For each item, anItem, in anItemSet.		for( int i=0; i<(*anItemSet).NumOfItems(); i++ )		{			anItem = (*anItemSet).Items[i];			if( Header[anItem].size() > 0 )			{				Itrtr = Header[anItem].end() - 1;				while( Itrtr != Header[anItem].begin() - 1 )				{					try 					{						if( (*(*Itrtr)).Level > (*aSeq).NumOfElements() ) break; //123												if( IsSupersetOfBranch( aSeq, (*Itrtr) ) )						{							tmpItrtr = Itrtr;							tmpItrtr--;							NumOfDels++;							DeleteSequence( (*Itrtr) );							Itrtr = tmpItrtr;						} else 							Itrtr--;					} catch(...)	{						Itrtr--;						printf( " Error in Delete Subsets in SeqTree.\n" );					}				}			}		}	}}int SeqTree::AddSeq( Sequence * aSeq ){	TreeNode * tmp;	TreeNode * Current;	ItemSet * anItemSet;	bool * Duplicated;	int anItem;	int CurrentLevel;	//printf("==============>");	//(*aSeq).Print();	NumOfAddIfClosed++;	// aSeq was not added.	if( IsContained( aSeq ) ) return 1;	DeleteSubsets( aSeq );	Current = Root;	(*Current).Sup = (*aSeq).Sup;	Duplicated = (bool *)calloc( NumOfItems, sizeof(bool) );	(*aSeq).MoveFirst();	CurrentLevel = 1;	while( !(*aSeq).IsLast() )	{		anItemSet = (*aSeq).Current();		tmp = (*Current).FindChild( anItemSet );		if( !tmp )		{ // Add a new node to tree			tmp = new TreeNode( anItemSet );			(*tmp).Parent = Current;			(*tmp).Level = CurrentLevel;			(*Current).AddChild( tmp );		}		Current = tmp;		(*Current).Sup = (*aSeq).Sup;		(*aSeq).MoveNext();		CurrentLevel++;	}	(*Current).Sup = (*aSeq).Sup;	// Add the last instance of each item in the sequence to the header list.	while( Current != Root )	{		anItemSet = (*Current).Item;		for( int i=0; i<(*anItemSet).NumOfItems(); i++ )		{			anItem = (*anItemSet).Items[i];			if( !Duplicated[ anItem ] )			{				Header[anItem].push_back( Current );				// To keep the Header lists sorted.				inplace_merge( Header[anItem].begin(), Header[anItem].end()-1, Header[anItem].end(), TreeNodeLevelLess ); //123			}			Duplicated[ anItem ] = true;		}		Current = (*Current).Parent;	}	// aSeq was added.	NumOfAdds++;	return 0;}void SeqTree::Print( FILE * aFile ){  NodeVector::iterator Itrtr;  //NodeList::iterator Itrtr;	if( Root )		(*Root).Print( aFile );	fprintf( aFile, "\n Header Table:\n" );	for( int i=0; i<NumOfItems; i++ )	{		fprintf( aFile, "  List for %d (Len=%d) => ", i, Header[i].size() );		for( Itrtr = Header[i].begin(); Itrtr != Header[i].end(); Itrtr++)		{			fprintf( aFile, "  " );			if( (*(*Itrtr)).Item ) (*(*(*Itrtr)).Item).Print();		}		fprintf( aFile, " \n" );	}}void SeqTree::InternalPrintRules( FILE * aFile, TreeNode * InNode, Sequence * aSeq, SeqList * SortedSeqList ){	TreeNode * aNode;	TreeNode * aChild;	if( InNode )		aNode = InNode;	else {		aNode = Root;		NumOfSeqs = 0;	}	if( !aSeq )		aSeq = new Sequence();	if( !aNode ) return;	if( (*aNode).NumOfChildren() == 0 )	{		(*aSeq).Sup = (*aNode).Sup;				if( SortedSeqList == NULL )		{			(*aSeq).Print( aFile );		} else {			(*SortedSeqList).push_back( new Sequence( aSeq ) );			// To keep the List vector sorted.			inplace_merge( (*SortedSeqList).begin(), (*SortedSeqList).end()-1, (*SortedSeqList).end(), SeqGreater );			//(*(*(*SortedSeqList).begin())).Print();		}				NumOfSeqs++;	}	//fprintf( aFile, "\n Rules:\n" );	(*aNode).MoveFirst();	while( !(*aNode).IsLast() )	{		aChild = (*aNode).Current();		//(*(*aChild).Item).Print( aFile );		if( aChild )		{			(*aSeq).Add( (*aChild).Item );			InternalPrintRules( aFile, aChild, aSeq, SortedSeqList );		}		(*aSeq).Del();		(*aNode).MoveNext(); 		//if( !(*aNode).IsLast() )			//fprintf( aFile, " Support = %d\n", (*aNode).Sup );	}	if( (*aSeq).NumOfElements() == 0 )	{		//fprintf( aFile, " Support = %d\n", (*aNode).Sup );		delete aSeq;	}}void SeqTree::PrintRules( FILE * aFile, TreeNode * InNode, Sequence * aSeq ){		SeqList * SortedSeqList = NULL;	#if defined( _SORT_RESULTS )		SeqList::iterator ListItrtr;		SortedSeqList = new SeqList;	#endif	InternalPrintRules( aFile, InNode, aSeq, SortedSeqList );#if defined( _SORT_RESULTS )	fprintf( aFile, "\n" );	for( ListItrtr=(*SortedSeqList).begin(); ListItrtr<(*SortedSeqList).end(); ListItrtr++ )	{		(*(*ListItrtr)).Print( aFile );	}	delete SortedSeqList;#endif	fprintf( aFile, "\n" );	fprintf( aFile, "# of elements added %d\n", NumOfAdds );	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );	fprintf( aFile, "# of times AddIfMaxSeq called %d\n", NumOfAddIfClosed );	fprintf( aFile, "# of times IsMaxSubsetOf called %d\n", NumIsMaxSubsetOf );	fprintf( aFile, "# of elements in the list %d\n", NumOfSeqs );}SeqTree::~SeqTree(){	delete[] Header;	delete Root;}//************************//************************//************************//************************TreeNode::TreeNode( ItemSet * anItemSet, int Support ){	Item = anItemSet;	Sup = Support;	Parent = NULL;	Level = 0;}bool TreeNodeLess( TreeNode * a, TreeNode * b ){	return (*(*a).Item).IsLessThan( (*b).Item ) ;}void TreeNode::AddChild( TreeNode * Child ) { 	Children.push_back(Child); 	// To keep the children vector sorted.	inplace_merge( Children.begin(), Children.end()-1, Children.end(), TreeNodeLess );}int TreeNodeCompare( TreeNode ** a, TreeNode ** b ){	return (*(*(*a)).Item).Compare( (*(*b)).Item );}TreeNode * TreeNode::FindChild( ItemSet * anItem ){	TreeNode ** Res;	TreeNode * tmp = new TreeNode(anItem);	Res = (TreeNode **) bsearch( &tmp, Children.begin(), Children.size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );	if( Res )		return (*Res);	return NULL;}void TreeNode::DelChild( TreeNode * Child ){	TreeNode ** Res;	if( NumOfChildren() == 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) );		//return (*Res);	}}void TreeNode::Print( FILE * aFile ){  NodeVector::iterator Itrtr;	fprintf( aFile, "  Node = " );	if( Item ) (*Item).Print();	fprintf( aFile, "  Level=%d ", Level );	fprintf( aFile, " Suport = %d ) ", Sup );	fprintf( aFile, "   Children " );	for( Itrtr = Children.begin(); Itrtr != Children.end(); Itrtr++)	{		if (Itrtr != Children.end()-1 )		{			if( (*(*Itrtr)).Item ) (*((*(*Itrtr)).Item)).Print();			fprintf( aFile, " ," );		} else {			if( (*(*Itrtr)).Item ) (*((*(*Itrtr)).Item)).Print();		}	}	fprintf( aFile, "\n" );	for( Itrtr = Children.begin(); Itrtr != Children.end(); Itrtr++)	{		//fprintf( aFile, "    " );		(*(*Itrtr)).Print( aFile );	}	//fprintf( aFile, "\n" );}TreeNode::~TreeNode(){  NodeVector::iterator Itrtr;	if( Item ) 	{		delete Item;		Item = NULL;	}	for( Itrtr = Children.begin(); Itrtr != Children.end(); Itrtr++)		delete *Itrtr;}//************************//************************//************************//************************#else //if defined( _USE_MAX_TREE )//************************//************************SeqTree::SeqTree( int dummy ){	NumOfAdds = 0;	NumOfDels = 0;	NumOfAddIfMax = 0;	NumIsMaxSubsetOf = 0;}inline void SeqTree::Add( Sequence * aSeq ){	List.insert( List.end(), aSeq );	NumOfAdds++;}inline SeqList::iterator SeqTree::Del( SeqList::iterator anItr ){	NumOfDels++;	return List.erase( anItr );}// Tries to add aSeq to the list if non of the list elements// is a closed superset of aSeq.// Sequences in the list that are Max subset of aSeq// will be deleted from the list.// Returns true if aSeq is added.bool SeqTree::AddSeq( Sequence * aSeq ){	SeqList::iterator Itrtr;	bool IsSuper = false;	NumOfAddIfMax++;	for( Itrtr = List.begin(); Itrtr != List.end(); )	{		if( !IsSuper )		{			NumIsMaxSubsetOf++;			if( (*aSeq).IsMaxSubsetOf( (*Itrtr) ) )				return false;		}		NumIsMaxSubsetOf++;		if( (*(*Itrtr)).IsMaxSubsetOf( aSeq ) )		{			delete (*Itrtr) ;			IsSuper = true;			Itrtr = Del( Itrtr );		} else			Itrtr++;	}	Add( aSeq );	return true;}bool SeqTree::IsContained( const struct PROJ_DB *proj_db, int * aSeqPtr ){	bool temp;	Sequence * aSeq;	aSeq = new Sequence( proj_db, aSeqPtr );	temp = IsContained( aSeq );	//(*aSeq).Print();	//if( temp )	//	printf( "     Is contained in the resultset.\n" );	//else	//	printf( "     Is NOT contained in the resultset.\n" );	return temp;}bool SeqTree::IsContained( Sequence * aSeq ){	SeqList::iterator Itrtr;	for( Itrtr = List.begin(); Itrtr != List.end(); )	{		NumIsMaxSubsetOf++;		if( (*aSeq).IsMaxSubsetOf( (*Itrtr) ) )			return true;	}	return false;}void SeqTree::PrintRules( FILE *aFile ){	SeqList::iterator Itrtr;#if defined( _SORT_RESULTS )  SeqList::iterator ListItrtr;	SeqList * SortedSeqList = NULL;	SortedSeqList = new SeqList;#endif	fprintf( aFile, "\n" );	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)	{		#if defined( _SORT_RESULTS )			(*SortedSeqList).push_back( (*Itrtr) );			// To keep the List vector sorted.			inplace_merge( (*SortedSeqList).begin(), (*SortedSeqList).end()-1, (*SortedSeqList).end(), SeqGreater );		#else			(*(*Itrtr)).Print( aFile );		#endif	}#if defined( _SORT_RESULTS )	fprintf( aFile, "\n" );	for( ListItrtr=(*SortedSeqList).begin(); ListItrtr<(*SortedSeqList).end(); ListItrtr++ )	{		(*(*ListItrtr)).Print( aFile );	}	delete SortedSeqList;#endif	fprintf( aFile, "\n" );	fprintf( aFile, "# of elements added %d\n", NumOfAdds );	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );	fprintf( aFile, "# of times AddIfMaxSeq called %d\n", NumOfAddIfMax );	fprintf( aFile, "# of times IsMaxSubsetOf called %d\n", NumIsMaxSubsetOf );	fprintf( aFile, "# of elements in the list %d\n", List.size() );}SeqTree::~SeqTree(){	SeqList::iterator Itrtr;	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)		delete *Itrtr;}//************************//************************#endif // defined( _USE_MAX_TREE )//************************//************************#endif // defined( _FIND_MAX_SEQS )