#include "../Global.h"#include "../ProjDB.h"#include "SeqTree.h"#if defined( _FIND_MAX_SEQS )// Assumes itemsets have the same size.inline bool ItemSetGreater( ItemSet * a, ItemSet * b ){	if( (*a).NumOfItems() > (*b).NumOfItems() )		return true;	else if( (*a).NumOfItems() < (*b).NumOfItems() )		return false;	for( int i=0; i<(*a).NumOfItems(); i++ )	{		if( (*a).Items[i] > (*b).Items[i] )			return true;		if( (*a).Items[i] < (*b).Items[i] )			return false;	}	return false;}inline bool SeqGreater( Sequence * a, Sequence * b ){	ElementVector::iterator aItrtr;	ElementVector::iterator bItrtr;	if( (*a).Sup > (*b).Sup )		return true;	else if( (*a).Sup < (*b).Sup )		return false;	else if( (*a).Elements.size() > (*b).Elements.size() )		return true;	else if( (*a).Elements.size() < (*b).Elements.size() )		return false;	bItrtr = (*b).Elements.begin();	for( aItrtr = (*a).Elements.begin(); aItrtr != (*a).Elements.end(); aItrtr++)	{		if( ItemSetGreater( *aItrtr, *bItrtr ) )			return true;		if( ItemSetGreater( *bItrtr, *aItrtr ) )			return false;		bItrtr++;	}	return false;}//************************//************************ItemSet::ItemSet( int NumItems, int * Itms ){	int i;	Count = NumItems;	Items = new int[Count];	if( Itms )		for( i=0; i<Count; i++ )		{			Items[i]=Itms[i];		}}ItemSet::ItemSet( ItemSet * anItemSet ){	int i;	Count = (*anItemSet).NumOfItems();	Items = new int[Count];	if( (*anItemSet).Items )		for( i=0; i<Count; i++ )		{			Items[i]=(*anItemSet).Items[i];		}}inline bool ItemSet::IsSubsetOf( ItemSet * anItemSet ){	int j;	int MyCnt;	int OtherCnt;	MyCnt = NumOfItems();	OtherCnt = (*anItemSet).NumOfItems();	if( MyCnt > OtherCnt )		return false;	j = 0;	for( int i=0; i<MyCnt; i++ )	{		while( Items[i] != (*anItemSet).Items[j] )		{			j++;			if( OtherCnt-j < MyCnt-i ) 				return false;		}	}	return true;}inline bool ItemSet::IsLessThan( ItemSet * anItemSet ){	int MyCnt;	int OtherCnt;	MyCnt = NumOfItems();	OtherCnt = (*anItemSet).NumOfItems();	if( MyCnt < OtherCnt )		return true;	if( MyCnt > OtherCnt )		return false;	// MyCnt == OtherCnt	for( int i=0; i<MyCnt; i++ )	{		if( Items[i] < (*anItemSet).Items[i] )			return true;		if( Items[i] > (*anItemSet).Items[i] )			return false;	}	return true;}inline int ItemSet::Compare( ItemSet * anItemSet ){	int MyCnt;	int OtherCnt;	MyCnt = NumOfItems();	OtherCnt = (*anItemSet).NumOfItems();	if( MyCnt < OtherCnt )		return -1;	if( MyCnt > OtherCnt )		return +1;	// MyCnt == OtherCnt	for( int i=0; i<MyCnt; i++ )	{		if( Items[i] < (*anItemSet).Items[i] )			return -1;		if( Items[i] > (*anItemSet).Items[i] )			return +1;	}	return 0;}void ItemSet::Print1( FILE *aFile ){	int i;	fprintf( aFile, " (" );	for( i=0; i<Count; i++ )	{		fprintf( aFile, " %d ", Items[i] );	}	fprintf( aFile, ") " );}void ItemSet::Print( FILE *aFile ){	int i;	fprintf( aFile, " (" ); 	for( i=0; i<Count; i++ ) 	{		fprintf( aFile, " %d ", Items[i] );	}	fprintf( aFile, ") " );}void ItemSet::Add ( int Item ){	int i;	int * tmp;	tmp = new int[Count+1];	for( i=0; i<Count; i++ )	{		tmp[i] = Items[i];	}	tmp[Count] = Item;	delete[] Items;	Items = tmp;	Count++;}ItemSet::~ItemSet(){	delete[] Items;}//************************//************************//************************//************************Sequence::Sequence(){	Sup = 0;}Sequence::Sequence( Sequence * aSeq ){  ElementVector::iterator Itrtr;	Sup = (*aSeq).Sup;	for( Itrtr = (*aSeq).Elements.begin(); Itrtr != (*aSeq).Elements.end(); Itrtr++)		Add( new ItemSet( (*Itrtr) ) );}Sequence::Sequence( int * Ptr, int Support ){	ItemSet * anItemSet;	int Start;	Sup = Support;	Start = 0;  int * dataset = Ptr;	int * StartPtr = Ptr;	int i = 0;  for (; *dataset!=-2; dataset++)	{		if( *dataset == -1 )		{			anItemSet = new ItemSet( i-Start, StartPtr );			StartPtr = dataset + 1;			Start = i+1;			Add( anItemSet );		}		i++;	}	//Print();	//printf( "\n" );}Sequence::Sequence( int * Pat, int PatLen, int Support ){	ItemSet * anItemSet;	int Start;	Sup = Support;	Start = 0;	if( PatLen > 1 )	{		for( int i=0; i<PatLen; i++)		{			if( *(Pat + i) == -1 )			{				anItemSet = new ItemSet( i-Start, Pat+Start );				Start = i+1;				Add( anItemSet );			}		}		anItemSet = new ItemSet( i-Start, Pat+Start );		Add( anItemSet );	} else {		int tmp[1];		tmp[0] = *Pat;		anItemSet = new ItemSet( 1, tmp );		Add( anItemSet );	}}Sequence::Sequence( const struct PROJ_DB *proj_db, int Support ){	ItemSet * anItemSet;	int Start;	Sup = Support;	Start = 0;	if( proj_db[0].m_nPatLen > 1 )	{		for( int i=0; i<proj_db[0].m_nPatLen; i++)		{			if( proj_db[0].m_pnPat[i] == -1 )			{				anItemSet = new ItemSet( i-Start, &proj_db[0].m_pnPat[Start] );				Start = i+1;				Add( anItemSet );			}		}		anItemSet = new ItemSet( i-Start, &proj_db[0].m_pnPat[Start] );		Add( anItemSet );	} else {		int tmp[1];		tmp[0] = int( proj_db[0].m_pnPat );		anItemSet = new ItemSet( 1, tmp );		Add( anItemSet );	}//	Print();//	printf( "\n" );}Sequence::Sequence( const struct PROJ_DB *proj_db, int * aSeqPtr ) //: Sequence( proj_db, 0 ){#if defined( _PERFORM_COMMON_PREFIX_CHECKING )	int * aPtr;	int i;	SeqWrap * aSeq;	if( (*proj_db).m_nPatLen > 1 )	{		for( int j=0; j<(*proj_db).m_nPatLen; j++ )			buf_idx[j] = (*proj_db).m_pnPat[j];	} else		buf_idx[0] = int( (*proj_db).m_pnPat );	i = (*proj_db).m_nPatLen;	aPtr = aSeqPtr;	aSeq = new SeqWrap( aSeqPtr );	aPtr = (*aSeq).GetFirst();	while( *aPtr != -2 )	{		buf_idx[i++] = *aPtr;		aPtr = (*aSeq).GetNext();	}	delete aSeq;	int PatLen = i - 1;	int * Pat = buf_idx;/////////////////	ItemSet * anItemSet;	int Start;	Sup = 0;	Start = 0;	if( PatLen > 1 )	{		for( int i=0; i<PatLen; i++)		{			if( *(Pat + i) == -1 )			{				anItemSet = new ItemSet( i-Start, Pat+Start );				Start = i+1;				Add( anItemSet );			}		}		anItemSet = new ItemSet( i-Start, Pat+Start );		Add( anItemSet );	} else {		int tmp[1];		tmp[0] = *Pat;		anItemSet = new ItemSet( 1, tmp );		Add( anItemSet );	}/////////////////#endif // defined( _PERFORM_COMMON_PREFIX_CHECKING )}#if !defined( _USE_MAX_TREE )// Returns true if this sequence is the Max subset of aSeq.bool Sequence::IsMaxSubsetOf( Sequence * aSeq ){  ElementVector::iterator aSeqPtr;  ElementVector::iterator thisPtr;	int aSeqLen = (*aSeq).Elements.size();	int thisLen = Elements.size();	if( Elements.size() == 0 )		return true;	thisPtr = Elements.begin();	aSeqPtr = (*aSeq).Elements.begin();	if( aSeqLen >= thisLen && aSeqLen > 0 )	{		while( aSeqPtr != (*aSeq).Elements.end() )		{			if( (*(*thisPtr)).IsSubsetOf( (*aSeqPtr) ) )				thisPtr++;			if( thisPtr == Elements.end() )				return true;			aSeqPtr++;		}	}	return false;}#endif // !defined( _USE_MAX_TREE )void Sequence::Add( struct PROJ_SEQ * PrjSeq ){	ItemSet * anItemSet;	int * Start;	int * intPtr;	MoveLast();	anItemSet = Current();	if( (*PrjSeq).m_nProjCount > 1 )		intPtr = (*PrjSeq).m_ppSeq[0];	else		intPtr = (int *)(*PrjSeq).m_ppSeq;	// Should be improvemnet. 123	while( *intPtr != -1 && *intPtr != -2 )	{		(*anItemSet).Add( *intPtr );		intPtr ++;	}	while( *intPtr != -2 )	{		Start = intPtr;		while( *intPtr != -1 )		{ 			intPtr ++;		}		if( Start != intPtr )		{			anItemSet = new ItemSet( intPtr-Start, Start );			Add( anItemSet );		}		intPtr ++;	}}void Sequence::Print( FILE *aFile ){  ElementVector::iterator Itrtr;	fprintf( aFile, " <" );	for( Itrtr = Elements.begin(); Itrtr != Elements.end(); Itrtr++)		(*(*Itrtr)).Print( aFile );	fprintf( aFile, "> Support = %d\n", Sup );}Sequence::~Sequence(){  ElementVector::iterator Itrtr;	for( Itrtr = Elements.begin(); Itrtr != Elements.end(); Itrtr++)		delete *Itrtr;}//************************//************************//************************//************************//************************//************************#if defined( _USE_MAX_TREE )//************************//************************SeqTree::SeqTree( int ItemsCount ){	Root = new TreeNode();	NumOfItems = ItemsCount;	Header = new NodeVector[NumOfItems+1];	//Header = new NodeList[NumOfItems+1];	NumOfAdds = 0;	NumOfDels = 0;	NumOfAddIfClosed = 0;	NumIsMaxSubsetOf = 0;}bool TreeNodeLevelLess( TreeNode * a, TreeNode * b ){	return (*a).Level > (*b).Level;}int TreeNodeLevelCompare( TreeNode ** a, TreeNode ** b ){	if( (*(*a)).Level < (*(*b)).Level )		return 1;	else if( (*(*a)).Level > (*(*b)).Level )		return -1;	else   		return 0;	//return (*(*(*a)).Item).Compare( (*(*b)).Item );}void SeqTree::RemoveFromHeaderList( TreeNode * aNode ){	ItemSet * anItemSet;	int anItem;	TreeNode ** Res;  NodeVector::iterator Itrtr;	anItemSet = (*aNode).Item;	// Delete the links from the header table	for( int i=0; i<(*anItemSet).NumOfItems(); i++ )	{		anItem = (*anItemSet).Items[i];		Res = (TreeNode **) bsearch( &aNode, Header[anItem].begin(), Header[anItem].size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeLevelCompare );		if( !Res ) continue;		Itrtr = Res;				while( (*(*Itrtr)).Level == (*aNode).Level && Itrtr != Header[anItem].begin() ) 			Itrtr--;				while( (*(*Itrtr)).Level >= (*aNode).Level && Itrtr != Header[anItem].end() ) 		{			if( (*Itrtr) == aNode )				Itrtr = Header[anItem].erase( Itrtr );			else				 Itrtr++;		}	}	}void SeqTree::DeleteSequence( TreeNode * aNode ){	TreeNode * Parent;	if( (*aNode).NumOfChildren() == 0 && (*aNode).Parent )	{		RemoveFromHeaderList( aNode );		Parent = (*aNode).Parent;		//if( (*Parent).NumOfChildren() > 1 )			(*Parent).DelChild( aNode );		//DeleteSequence( (*aNode).Parent );		DeleteSequence( Parent );		delete aNode;	}}// If aSeq is a subset of the sequence in the tree with aNode as its last element.bool SeqTree::IsSubsetOfBranch( Sequence * aSeq, TreeNode * aNode ){	int NumOfRemElmnts;	ItemSet * anItemSet;	TreeNode * CurNode;	(*aSeq).MoveLast();	anItemSet = (*aSeq).Current();	CurNode = aNode;	NumOfRemElmnts = (*aSeq).NumOfElements();	NumIsMaxSubsetOf++;	if( (*CurNode).Level < NumOfRemElmnts )		return false;		while( true )	{		if( (*anItemSet).IsSubsetOf((*CurNode).Item) )		{			CurNode = (*CurNode).Parent;			(*aSeq).MovePrev();			anItemSet = (*aSeq).Current();			NumOfRemElmnts--;			if( NumOfRemElmnts == 0 )				return true;		} else {			CurNode = (*CurNode).Parent;			if( (*CurNode).Level < NumOfRemElmnts )				return false;		}	}}// Returns the item in the anItemSet, with shortest header list.int SeqTree::LeastFreqInHeader( ItemSet * anItemSet ){	int anItem;	int Res = -1;	int Min = 10000000;	int HeaderSize;	for( int i=0; i<(*anItemSet).NumOfItems(); i++ )	{		anItem = (*anItemSet).Items[i];		HeaderSize = Header[anItem].size();		if( HeaderSize < Min )		{			Min = HeaderSize;			Res = anItem;		}		if( Min==0 ) break;	}	return Res;}