#include <assert.h>#include "../Global.h"#include "../ProjDB.h"#if !defined( _FIND_MAX_SEQS ) && !defined( _FIND_FREQUENT_SEQS )//#include "SequenceList.h"void RTATest( const struct PROJ_DB * pDB );///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////#if defined( _USE_OUTPUT_BUFFER )void EmptyBuffer( SequenceList * aList, Sequence * aSeq ){	Sequence * aBuf;	Sequence * aParent;	int tmpSup = 0;	if( n_max_mem < n_total_mem )		n_max_mem = n_total_mem;	aBuf = aSeq;	while( aBuf != NULL )	{		aParent = (*aBuf).Parent;		(*aBuf).ReferenceCount--;		if( (*aBuf).ReferenceCount <= 0 )		{			if( (*aBuf).Support > tmpSup )			{				tmpSup = (*aBuf).Support;				(*aList).AddIfClosedSeq( aBuf );			} else {				delete aBuf;			}		} else			break;		aBuf = aParent;	}		// Ignor parent sequences that have the same support, when traversing through their other children.	while( aBuf != NULL && (*aBuf).Support <= tmpSup )	{		(*aBuf).Support = -1;		aBuf = (*aBuf).Parent;	}}#endif///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////void main1( int argc, char** argv ){	printf( "This is SequenceList running!!!\n" );}//************************//************************Sequence::Sequence(){	StartPtr = NULL;	Support = 0;	Len = 0;#if defined( _USE_OUTPUT_BUFFER )	Parent = NULL;	ReferenceCount = 0;#endif}// No last -1, and -2 are presented.Sequence::Sequence( int * Ptr, int Len, int Sup ){	int tmp;	Support = Sup;	(*this).Len = Len;#if defined( _USE_OUTPUT_BUFFER )	Parent = NULL;	ReferenceCount = 0;#endif	tmp = (*this).Len * sizeof( int );	StartPtr = (int*) memalloc( tmp );	n_total_mem += ( tmp  + sizeof( *this ) );	memcpy( StartPtr, Ptr, tmp );}inline bool Sequence::EndOfSequence( int * aPtr ){	return (aPtr-StartPtr >= Len);}inline bool Sequence::EndOfItemSet( int * aPtr ){	return (*aPtr==-1) || (aPtr-StartPtr >= Len);}inline int Sequence::NumOfItemSets(){	int * ItemPtr;	int Result = 0;	if( Len>0 )		Result = 1;	for( ItemPtr = StartPtr; !EndOfSequence( ItemPtr ); ItemPtr++ )	{		if( *ItemPtr == -1 )			Result++;	}	return Result;}// Returns the address of the next itemset in aSeq, if itemset pointed to by ThisStart// is the subset of the itemset pointed to by SeqStart.inline int * Sequence::IsItemSetSubsetOf( int * ThisStart, int * SeqStart, Sequence * aSeq ){	int * aSeqPtr = SeqStart;	int * thisPtr = ThisStart;	while( !(*aSeq).EndOfSequence(aSeqPtr) )	{		if( *aSeqPtr == *thisPtr )		{			thisPtr++;			if( EndOfItemSet(thisPtr) )			{				while( !(*aSeq).EndOfItemSet(aSeqPtr) )					aSeqPtr++;				return ++aSeqPtr;			}		}		aSeqPtr++;		if( (*aSeq).EndOfItemSet(aSeqPtr) )			thisPtr = ThisStart;	}	return NULL;}// Returns true if this sequence is the closed subset of aSeq.bool Sequence::IsClosedSubsetOf( Sequence * aSeq ){	int * aSeqPtr = (*aSeq).StartPtr;	int * thisPtr = StartPtr;	if( Len == 0 )		return true;	if( (*aSeq).Len >= Len && (*aSeq).Len > 0 && (*aSeq).Support >= Support )	{		while( !(*aSeq).EndOfSequence(aSeqPtr) )		{			aSeqPtr = IsItemSetSubsetOf( thisPtr, aSeqPtr, aSeq );			if( aSeqPtr == NULL )				return false;			else {				while( !EndOfItemSet(thisPtr) )					thisPtr++;				if( EndOfSequence(++thisPtr) )					return true;			}		}	}	return false;}void Sequence::Print( FILE *aFile ){	int * TmpPtr = NULL;	fprintf( aFile, " <" );	TmpPtr = StartPtr;	if( TmpPtr!=NULL )		fprintf( aFile, " (" );	while( TmpPtr != NULL && TmpPtr-StartPtr <= Len )	{		if( TmpPtr-StartPtr == Len )			fprintf( aFile, ") " );		else if( *TmpPtr == -1 )		{				fprintf( aFile, ")  (" );		} else {			fprintf( aFile, " %d ", *TmpPtr );		}		TmpPtr++;	}	fprintf( aFile, "> " );	fprintf( aFile, "  Support = %d\n", Support );}Sequence::~Sequence(){	int tmp;	tmp = (*this).Len * sizeof( int );	n_total_mem -= ( tmp  + sizeof( *this ) );	freemem( (void**) &StartPtr );}//************************//************************//************************//************************#define _CONSIDER_LENinline bool SeqGreater( Sequence * a, Sequence * b ){#if defined( _CONSIDER_LEN )	if( (*a).Support > (*b).Support )		return true;	else if( (*a).Support < (*b).Support )		return false;	else if( (*a).Len > (*b).Len )		return true;	else if( (*a).Len < (*b).Len )		return false;	for( int i=0; i<(*a).Len; i++ )	{		if( *((*a).StartPtr+i) > *((*b).StartPtr+i) )			return true;		if( *((*a).StartPtr+i) < *((*b).StartPtr+i) )			return false;	}	return false;#else	return (*a).Support > (*b).Support;#endif}inline bool SeqGreaterEqual( Sequence * a, Sequence * b ){#if defined( _CONSIDER_LEN )	if( (*a).Support > (*b).Support )		return true;	else if( (*a).Support < (*b).Support )		return false;	else		return (*a).Len >= (*b).Len;#else	return (*a).Support >= (*b).Support;#endif}inline bool SeqEqual( Sequence * a, Sequence * b ){#if defined( _CONSIDER_LEN )	return ( (*a).Support == (*b).Support ) && ( (*a).Len == (*b).Len );#else	return (*a).Support == (*b).Support;#endif}#if _NEW_SEQUENCE_LIST > 0 && _NEW_SEQUENCE_LIST < 20inline bool LenGreater( Sequence * a, Sequence * b ){	if( (*a).Len > (*b).Len )		return true;	else if( (*a).Len < (*b).Len )		return false;	for( int i=0; i<(*a).Len; i++ )	{		if( *((*a).StartPtr+i) > *((*b).StartPtr+i) )			return true;		if( *((*a).StartPtr+i) < *((*b).StartPtr+i) )			return false;	}	return false;}#endif // _NEW_SEQUENCE_LIST > 0 && _NEW_SEQUENCE_LIST < 20#if defined( _NEW_SEQUENCE_LIST )#if _NEW_SEQUENCE_LIST < 20SequenceList::SequenceList(){	NumOfAdds = 0;	NumOfDels = 0;	NumOfAddIfClosed = 0;	NumIsClosedSubsetOf = 0;}inline void SequenceList::AddSeq( Sequence * aSeq ){	NumOfAdds++;#if _NEW_SEQUENCE_LIST > 0	SeqMap::iterator Itrtr;	SeqList * tmpSeqList;	Itrtr = List.find( (*aSeq).Support );	if( Itrtr != List.end() )	{		tmpSeqList = (*Itrtr).second;	} else {		tmpSeqList = new SeqList();		List.insert( SeqMap::value_type( (*aSeq).Support, tmpSeqList ) );	}	(*tmpSeqList).push_back( aSeq );	// To keep the List vector sorted.	inplace_merge( (*tmpSeqList).begin(), (*tmpSeqList).end()-1, (*tmpSeqList).end(), LenGreater );#else //_NEW_SEQUENCE_LIST > 0	List.push_back( aSeq );	// To keep the List vector sorted.	inplace_merge( List.begin(), List.end()-1, List.end(), SeqGreater );#endif //_NEW_SEQUENCE_LIST > 0}inline SeqList::iterator SequenceList::Del( SeqList::iterator anItr ){	NumOfDels++;#if _NEW_SEQUENCE_LIST > 0#else //_NEW_SEQUENCE_LIST > 0	return List.erase( anItr );#endif //_NEW_SEQUENCE_LIST > 0}// 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 closed subset of aSeq// will be deleted from the list.// Returns true if aSeq is added.bool SequenceList::AddIfClosedSeq( Sequence * aSeq ){	NumOfAddIfClosed++;#if _NEW_SEQUENCE_LIST > 0	SeqMap::iterator Itrtr;	SeqList::iterator ListItrtr;	SeqList * aList;	for( Itrtr = List.begin(); Itrtr != List.end() && (*Itrtr).first>=(*aSeq).Support; Itrtr++ )	{		aList = (*Itrtr).second;		for( ListItrtr = (*aList).begin(); ListItrtr != (*aList).end() && (*(*ListItrtr)).Len>=(*aSeq).Len; )		{			NumIsClosedSubsetOf++;			if( (*aSeq).IsClosedSubsetOf( (*ListItrtr) ) )				return false;			if( (*aSeq).Support == (*Itrtr).first && (*(*ListItrtr)).Len == (*aSeq).Len )			{				NumIsClosedSubsetOf++;				if( (*(*ListItrtr)).IsClosedSubsetOf( aSeq ) )				{					delete (*ListItrtr);					NumOfDels++;										ListItrtr = (*aList).erase( ListItrtr );				} else					ListItrtr++;			} else				ListItrtr++;		}	}	// Go to the list with equal support with aSeq.	if( Itrtr != List.begin() ) 	{		Itrtr--; 		if( (*(Itrtr)).first != (*aSeq).Support )			Itrtr++; 	}	while( Itrtr != List.end() ) 	{		aList = (*Itrtr).second;		for( ListItrtr = (*aList).end()-1; ListItrtr >= (*aList).begin() && (*(*ListItrtr)).Len<=(*aSeq).Len; )		{			NumIsClosedSubsetOf++;			if( (*(*ListItrtr)).IsClosedSubsetOf( aSeq ) )			{				delete (*ListItrtr);				NumOfDels++;									ListItrtr = (*aList).erase( ListItrtr ) - 1;			} else				ListItrtr--;		}		Itrtr++;	}	AddSeq( aSeq );	return true;#else //_NEW_SEQUENCE_LIST > 0	SeqList::iterator Itrtr;	Itrtr = List.begin();	while( Itrtr != List.end() && SeqGreaterEqual( (*Itrtr), aSeq ) ) 	{		NumIsClosedSubsetOf++;		if( (*aSeq).IsClosedSubsetOf( (*Itrtr) ) )			return false;		if( SeqEqual( aSeq, (*Itrtr) ) )		{			NumIsClosedSubsetOf++;			if( (*(*Itrtr)).IsClosedSubsetOf( aSeq ) )			{				delete (*Itrtr);				Itrtr = Del( Itrtr );			} else				Itrtr++;		} else			Itrtr++;	}	while( Itrtr != List.end() ) 	{		NumIsClosedSubsetOf++;		if( (*(*Itrtr)).IsClosedSubsetOf( aSeq ) )		{			delete (*Itrtr);			Itrtr = Del( Itrtr );		} else			Itrtr++;	}	AddSeq( aSeq );	return true;#endif //_NEW_SEQUENCE_LIST > 0}void SequenceList::Print( FILE *aFile ){	int ListSize = 0;	fprintf( aFile, "\n" );#if _NEW_SEQUENCE_LIST > 0	SeqMap::iterator Itrtr;	SeqList::iterator ListItrtr;	SeqList * aList;	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)	{		aList = (*Itrtr).second;		for( ListItrtr = (*aList).begin(); ListItrtr != (*aList).end(); ListItrtr++)		{			(*(*ListItrtr)).Print( aFile );			ListSize++;		}	}#else //_NEW_SEQUENCE_LIST > 0	SeqList::iterator Itrtr;	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)	{		(*(*Itrtr)).Print( aFile );		//fprintf( aFile, "\n" );	}	ListSize = List.size();#endif //_NEW_SEQUENCE_LIST > 0	fprintf( aFile, "\n" );	fprintf( aFile, "# of elements added %d\n", NumOfAdds );	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );	fprintf( aFile, "# of times AddIfClosedSeq called %d\n", NumOfAddIfClosed );	fprintf( aFile, "# of times IsClosedSubsetOf called %d\n", NumIsClosedSubsetOf );	fprintf( aFile, "# of elements in the list %d\n", ListSize );}SequenceList::~SequenceList(){#if _NEW_SEQUENCE_LIST > 0	SeqMap::iterator Itrtr;	SeqList::iterator ListItrtr;	SeqList * aList;	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)	{		aList = (*Itrtr).second;		for( ListItrtr = (*aList).begin(); ListItrtr != (*aList).end(); ListItrtr++)		{			delete (*ListItrtr);		}		delete aList;	}#else //_NEW_SEQUENCE_LIST > 0	SeqList::iterator Itrtr;	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)		delete (*Itrtr);#endif //_NEW_SEQUENCE_LIST > 0}//************************//************************#else // _NEW_SEQUENCE_LIST < 20//************************//************************//************************************//************************************//************************************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;