#include "math.h"
#include "malloc.h"
#include "stdio.h"
#include "stdlib.h"

//Tree
int **NodeList, ****Nijk, **ClassDistribute;//NodeList, Nijk, ClassDistribute are in the same size
int NLStart, NLSize, NLSizeIncremental;//Dynamic memory allocation
int NodeCount;//The number of nodes in the tree
int *MultiChoices,*MultiChoiceAtts;

//Parameters
int Dim, NumClass, NumAttValue[54], MaxNumAttValue, WinSize, Nmin;
double Delta, Tao;
int **WindowData,*UsedAtts;

void ExpandNodeList()
{
	int oldNLSize,i,j,k;
	
	oldNLSize=NLSize;
	NLSize+=NLSizeIncremental;
	NodeList=(int **)realloc(NodeList, NLSize*sizeof(int *));
	Nijk=(int ****)realloc(Nijk,NLSize*sizeof(int ***));
	ClassDistribute=(int **)realloc(ClassDistribute,NLSize*sizeof(int *));
	for(i=oldNLSize; i<NLSize; i++)
	{
		NodeList[i]=(int *)malloc((MaxNumAttValue+5)*sizeof(int));
		NodeList[i][0]=-1;
		Nijk[i]=(int ***)malloc(NumClass*sizeof(int **));
		ClassDistribute[i]=(int *)malloc(NumClass*sizeof(int));
		for(j=0; j<NumClass; j++)
		{
			Nijk[i][j]=(int **)malloc(Dim*sizeof(int *));
			for(k=0; k<Dim; k++)
				Nijk[i][j][k]=(int *)malloc(NumAttValue[k]*sizeof(int));
		}
	}
}

void WindowFindMaxID(int NodePos, int *Data, int *MaxID)
{
	int i;

	if (NodeList[NodePos][MaxNumAttValue+2]>*MaxID)
		*MaxID=NodeList[NodePos][MaxNumAttValue+2];
	
	if (NodeList[NodePos][MaxNumAttValue+1]>=0)
		WindowFindMaxID(NodeList[NodePos][MaxNumAttValue+1], Data, MaxID);

	if (NodeList[NodePos][0]>=0)
	{
		i=Data[NodeList[NodePos][0]+1];
		WindowFindMaxID(NodeList[NodePos][i+1], Data, MaxID);
	}
}

void WindowAddData(int *Data, int MaxNodeID, int *WinIndex)
{
	int i;

	for(i=0; i<=Dim; i++)
		WindowData[*WinIndex][i]=Data[i];
	WindowData[*WinIndex][Dim+1]=MaxNodeID;
	(*WinIndex)++;
	if (*WinIndex>=WinSize) *WinIndex=0;
}

void WindowForgetData(int NodePos, int *Data, int MaxID)
{
	int i;

	if (NodeList[NodePos][MaxNumAttValue+2]<=MaxID)
	{
		ClassDistribute[NodePos][Data[0]]--;
		for(i=1; i<=Dim; i++)
			Nijk[NodePos][Data[0]][i-1][Data[i]]--;
	}

	if (NodeList[NodePos][MaxNumAttValue+1]>=0)
		WindowForgetData(NodeList[NodePos][MaxNumAttValue+1],Data,MaxID);

	if (NodeList[NodePos][0]>=0)
	{
		i=Data[NodeList[NodePos][0]+1];
		WindowForgetData(NodeList[NodePos][i+1],Data,MaxID);
	}
}

double lg2(double x)
{
	return log(x)/log(2.0);
}

bool UsedAtt(int Att, int *UsedAttSet)
{
	int i;

	for(i=1; i<=UsedAttSet[0]; i++)
		if (Att==UsedAttSet[i]) return 1;
	return 0;
}

int CheckMultiClass(int NodePos)
{
	int i,MultiClass=0;

	for(i=0; i<NumClass; i++)
		if (ClassDistribute[NodePos][i]>0) 
			MultiClass++;

	return MultiClass;
}

double GetEntropyTotal(int NodePos) 
{
	double out = 0.0;
	double prob;
	int i, Total=0;

	for(i=0; i<NumClass; i++)
		Total+=ClassDistribute[NodePos][i];
	
	for(i = 0; i < NumClass; i++) 
	{
		prob = (double)ClassDistribute[NodePos][i] / (double)Total;
		if(prob > 0.0) 
			out -= (prob * lg2(prob));
	}
	return out;
}

int MajorityClass(int NodePos)
{
	int i, MaxIndex,MaxValue;

	MaxIndex=0;
	MaxValue=ClassDistribute[NodePos][0];
	for(i=1; i<NumClass; i++)
		if (ClassDistribute[NodePos][i]>MaxValue)
		{
			MaxValue=ClassDistribute[NodePos][i];
			MaxIndex=i;
		}
	return MaxIndex;
}

void InitializeNode(int NodePos, int StartTime)
{
	int i,j,k;

	NodeList[NodePos][0]=-2;
	NodeList[NodePos][MaxNumAttValue+1]=-1;
	NodeCount++;
	NodeList[NodePos][MaxNumAttValue+2]=NodeCount;
	NodeList[NodePos][MaxNumAttValue+3]=StartTime;
	NodeList[NodePos][MaxNumAttValue+4]=0;
	for(i=0; i<NumClass; i++)
	{
		ClassDistribute[NodePos][i]=0;
		for(j=0; j<Dim; j++)
			for(k=0; k<NumAttValue[j]; k++)
				Nijk[NodePos][i][j][k]=0;
	}
}

int GetNodeData(int NodePos)
{
	int i,Sum=0;

	for(i=0; i<NumClass; i++)
		Sum+=ClassDistribute[NodePos][i];

	return Sum;
}

void CheckSplitEntropy(int NodePos, int *UsedAtts, int CurrentDataIndex)
{
	int i,j,k,FirstAtt=-1,SecondAtt=-1;
	int TotalNum,TotalNumPerVal;
	double FirstDelta=1000,SecondDelta=1000,Entropy,Prob;
	double FinalEntropy,First_Second,EntropyTotal;
	double Range, hoeffdingBound;

	if ((UsedAtts[0]<Dim) && (CheckMultiClass(NodePos)>1))
	{
		//Find the Best two attributes
		TotalNum=GetNodeData(NodePos);
		for(i=0; i<Dim; i++)
			if (!UsedAtt(i, UsedAtts))
			{
				FinalEntropy=0.0;
				for(j=0; j<NumAttValue[i]; j++)
				{
					TotalNumPerVal=0;
					for(k=0; k<NumClass; k++)
						TotalNumPerVal+=Nijk[NodePos][k][i][j];
					Entropy=0.0;
					for(k=0; k<NumClass; k++)
						if (Nijk[NodePos][k][i][j]>0)
						{
							Prob=(double)Nijk[NodePos][k][i][j]/(double)TotalNumPerVal;
							Entropy-=(Prob*lg2(Prob));
						}
					FinalEntropy+=((double)TotalNumPerVal/(double)TotalNum)*Entropy;
				}
				if (FinalEntropy<FirstDelta)
				{
					SecondDelta=FirstDelta;
					SecondAtt=FirstAtt;
					FirstDelta=FinalEntropy;
					FirstAtt=i;
				}
				else if (FinalEntropy<SecondDelta)
				{
					SecondDelta=FinalEntropy;
					SecondAtt=i;
				}
			}

		//Check the hoeffding bound
		Range=lg2(NumClass);
		hoeffdingBound = sqrt((Range*Range*log(1/Delta))/(2*TotalNum));
		First_Second=SecondDelta-FirstDelta;
		EntropyTotal=GetEntropyTotal(NodePos);
		if ((FirstDelta<EntropyTotal) && ((First_Second>hoeffdingBound) || 
		   ((First_Second<=hoeffdingBound)&&(hoeffdingBound<Tao)))) //The condition for split
		{
			NodeList[NodePos][0]=FirstAtt;
			for(i=1; i<=NumAttValue[FirstAtt]; i++)
			{
				//Find a vacant position in NodeList
				j=NLStart;
				while ((j<NLSize) && (NodeList[j][0]!=-1)) j++;
				if (j>=NLSize) ExpandNodeList();
				NLStart=j+1;			

				NodeList[NodePos][i]=j;
				InitializeNode(j,CurrentDataIndex);
			}
		}		
	}
}

void AddDataToSubNode(int NodePos, int *Data, int *UsedAtts, int CurrentDataIndex)
{
	int i;

	ClassDistribute[NodePos][Data[0]]++;
	for(i=0; i<Dim; i++)
		Nijk[NodePos][Data[0]][i][Data[i+1]]++;

	if (NodeList[NodePos][0]==-2)
	{
		if (GetNodeData(NodePos) % Nmin == 0)
			CheckSplitEntropy(NodePos, UsedAtts, CurrentDataIndex);
	}
	else if (NodeList[NodePos][0]>0)
	{
		i=Data[NodeList[NodePos][0]+1];
		NodePos=NodeList[NodePos][i+1];
		UsedAtts[0]++;
		UsedAtts[UsedAtts[0]]=NodeList[NodePos][0];
		AddDataToSubNode(NodePos,Data,UsedAtts,CurrentDataIndex);
		UsedAtts[0]--;
	}
}

void DeleteNode(int NodePos, int LeftPos)
{
	int i;

	if (NodeList[NodePos][0]>=0)
		for(i=1; i<=NumAttValue[NodeList[NodePos][0]]; i++)
			DeleteNode(NodeList[NodePos][i],-1);
	if (NodeList[NodePos][MaxNumAttValue+1]!=LeftPos)
		DeleteNode(NodeList[NodePos][MaxNumAttValue+1],LeftPos);
	else if ((LeftPos>=0) && (NodeList[LeftPos][MaxNumAttValue+1]>=0))
	{
		DeleteNode(NodeList[LeftPos][MaxNumAttValue+1],-1);
		NodeList[LeftPos][MaxNumAttValue+1]=-1;
	}
	NodeList[NodePos][0]=-1;
	if (NodePos<NLStart) NLStart=NodePos;
}

void CopyNode(int FromNode, int ToNode)
{
	int i,j,k;

	for(i=0; i<MaxNumAttValue+5; i++)
		NodeList[ToNode][i]=NodeList[FromNode][i];

	for(i=0; i<NumClass; i++)
	{
		ClassDistribute[ToNode][i]=ClassDistribute[FromNode][i];
		for(j=0; j<Dim; j++)
			for(k=0; k<NumAttValue[j]; k++)
				Nijk[ToNode][i][j][k]=Nijk[FromNode][i][j][k];
	}	 
}

int PredictOneTestData(int RootNodePos, int *Data, int *Pos, int *Neg)
{
	int i,PredictClass,AttValue,CurrentNodePos;
	int BestChoice;
	double BestAccuracy,tmpValue;

	CurrentNodePos=-1;
	if ((NodeList[RootNodePos][0]==-2)||(NodeList[RootNodePos][0]==-3))
		PredictClass=MajorityClass(RootNodePos);
	else if (NodeList[RootNodePos][0]>=0)
	{
		AttValue=Data[NodeList[RootNodePos][0]+1];
		CurrentNodePos=NodeList[RootNodePos][AttValue+1];
	}

	while (CurrentNodePos>=0)
	{
		MultiChoices[0]=1;
		MultiChoices[1]=CurrentNodePos;
		CurrentNodePos=NodeList[CurrentNodePos][MaxNumAttValue+1];
		while (CurrentNodePos>=0)
		{
			MultiChoices[0]++;
			MultiChoices[MultiChoices[0]]=CurrentNodePos;
			CurrentNodePos=NodeList[CurrentNodePos][MaxNumAttValue+1];
		}	

		BestChoice=MultiChoices[1];
		BestAccuracy=(double)NodeList[BestChoice][MaxNumAttValue+4]/
			(double)GetNodeData(BestChoice);
		for(i=2; i<=MultiChoices[0]; i++)
		{
			tmpValue=(double)NodeList[MultiChoices[i]][MaxNumAttValue+4]/
				(double)GetNodeData(MultiChoices[i]);			
			if (tmpValue>BestAccuracy)
			{
				BestChoice=MultiChoices[i];
				BestAccuracy=tmpValue;
			}
		}

		if ((NodeList[BestChoice][0]==-2)||(NodeList[BestChoice][0]==-3))
		{
			PredictClass=MajorityClass(BestChoice);
			CurrentNodePos=-1;
		}		
		else if (NodeList[BestChoice][0]>=0)
		{
			AttValue=Data[NodeList[BestChoice][0]+1];
			CurrentNodePos=NodeList[BestChoice][AttValue+1];
		}
	}
	if (Pos!=NULL)
	{
		if (PredictClass==0) (*Pos)++;
		else if (PredictClass==1) (*Neg)++;
	}
	if (PredictClass==Data[0]) return 1;
	else return 0;
}

void AddDataToNode(int NodePos, int *Data, int *UsedAtts, int TotalDataSeen)
{
	int i,CurrentNodePos;

	//Add Data to current node
	ClassDistribute[NodePos][Data[0]]++;
	for(i=0; i<Dim; i++)
		Nijk[NodePos][Data[0]][i][Data[i+1]]++;

	if (NodeList[NodePos][0]==-2)
	{
		if (GetNodeData(NodePos) % Nmin == 0)
			CheckSplitEntropy(NodePos, UsedAtts, TotalDataSeen);
	}

	//Add Data to the alternate subtree
	CurrentNodePos=NodePos;
	while (NodeList[CurrentNodePos][MaxNumAttValue+1]>=0)
	{
		AddDataToSubNode(NodeList[CurrentNodePos][MaxNumAttValue+1], Data, 
			UsedAtts, TotalDataSeen);
		CurrentNodePos=NodeList[CurrentNodePos][MaxNumAttValue+1];
	}

	//Predict the class label
	NodeList[NodePos][MaxNumAttValue+4]+=PredictOneTestData(NodePos, Data, NULL, NULL);
	CurrentNodePos=NodeList[NodePos][MaxNumAttValue+1];
	while (CurrentNodePos>=0)
	{
		NodeList[CurrentNodePos][MaxNumAttValue+4]+=
			PredictOneTestData(CurrentNodePos, Data, NULL, NULL);
		CurrentNodePos=NodeList[CurrentNodePos][MaxNumAttValue+1];
	}
}

double PredictTestDataSet(int **TestData, int NumTest, int *Pos, int *Neg)
{
	int i,Sum=0;

	for(i=0; i<NumTest; i++)
		Sum+=PredictOneTestData(0,TestData[i], Pos, Neg);

	return (double)Sum/(double)NumTest;
}

double CheckSplitEntropyValidity(int NodePos, int *UsedAtts, int *FirstAtt, double *FirstDelta)
{
	int i,j,k,SecondAtt=-1,TotalNum,TotalNumPerVal;
	double SecondDelta=1000,Entropy,Prob,FinalEntropy;

	if ((UsedAtts[0]<Dim) && (CheckMultiClass(NodePos)>1))
	{
		//Find the Best two attributes
		*FirstDelta=1000;
		*FirstAtt=-1;
		TotalNum=GetNodeData(NodePos);
		for(i=0; i<Dim; i++)
			if (!UsedAtt(i, UsedAtts))
			{
				FinalEntropy=0.0;
				for(j=0; j<NumAttValue[i]; j++)
				{
					TotalNumPerVal=0;
					for(k=0; k<NumClass; k++)
						TotalNumPerVal+=Nijk[NodePos][k][i][j];
					Entropy=0.0;
					for(k=0; k<NumClass; k++)
						if (Nijk[NodePos][k][i][j]>0)
						{
							Prob=(double)Nijk[NodePos][k][i][j]/(double)TotalNumPerVal;
							Entropy-=(Prob*lg2(Prob));
						}
					FinalEntropy+=((double)TotalNumPerVal/(double)TotalNum)*Entropy;
				}
				if (FinalEntropy<*FirstDelta)
				{
					SecondDelta=*FirstDelta;
					SecondAtt=*FirstAtt;
					*FirstDelta=FinalEntropy;
					*FirstAtt=i;
				}
				else if (FinalEntropy<SecondDelta)
				{
					SecondDelta=FinalEntropy;
					SecondAtt=i;
				}
			}		
		return SecondDelta-*FirstDelta;
	}
	else return -1.0;
}

void CheckSplitValidity(int NodePos,int *UsedAtts,int TotalDataSeen)
{
	int FindAltTree, FirstAtt, CurrentNodePos,i,j,k,l, NumDataSeen;
	int BestChoice;
	double First_Second, Range, hoeffdingBound, EntropyTotal;
	double FirstDelta, BestAccuracy, tmpValue;

	BestChoice=-1;
	if (NodeList[NodePos][0]>=0)
	{
		MultiChoices[0]=1;
		MultiChoices[1]=NodePos;
		MultiChoiceAtts[0]=1;
		MultiChoiceAtts[1]=NodeList[NodePos][0];
		CurrentNodePos=NodeList[NodePos][MaxNumAttValue+1];
		while (CurrentNodePos>=0)
		{
			MultiChoices[0]++;
			MultiChoices[MultiChoices[0]]=CurrentNodePos;
			if (NodeList[CurrentNodePos][0]>=0)
			{
				MultiChoiceAtts[0]++;
				MultiChoiceAtts[MultiChoiceAtts[0]]=NodeList[CurrentNodePos][0];
			}
			CurrentNodePos=NodeList[CurrentNodePos][MaxNumAttValue+1];
		}
		BestChoice=MultiChoices[1];
		BestAccuracy=(double)NodeList[BestChoice][MaxNumAttValue+4]/
			(double)GetNodeData(BestChoice);
		for(i=2; i<=MultiChoices[0]; i++)
		{
			tmpValue=(double)NodeList[MultiChoices[i]][MaxNumAttValue+4]/
				(double)GetNodeData(MultiChoices[i]);
			if (tmpValue>BestAccuracy)
			{
				BestChoice=MultiChoices[i];
				BestAccuracy=tmpValue;
			}
		}
	}
	
	if (BestChoice>=0)
	for(l=1; l<=MultiChoices[0]; l++)
	{
		BestChoice=MultiChoices[l];
		UsedAtts[0]++;
		UsedAtts[UsedAtts[0]]=NodeList[BestChoice][0];
		First_Second=CheckSplitEntropyValidity(BestChoice, UsedAtts, &FirstAtt, &FirstDelta);
		UsedAtts[0]--;
		if ((First_Second>=0)&&(!UsedAtt(FirstAtt, MultiChoiceAtts)))
			FindAltTree=0;
		else FindAltTree=1;

		if (!FindAltTree)
		{
			Range=lg2(NumClass);
			NumDataSeen=GetNodeData(BestChoice);
			hoeffdingBound = sqrt((Range*Range*log(1/Delta))/(2*NumDataSeen));
			EntropyTotal=GetEntropyTotal(BestChoice);
			if ((FirstDelta<EntropyTotal) && ((First_Second>hoeffdingBound) || 
			   ((First_Second<=hoeffdingBound) && (hoeffdingBound<Tao) && 
				(First_Second>=0.5*Tao))))
			{
				CurrentNodePos=MultiChoices[MultiChoices[0]];
				j=NLStart;
				while ((j<NLSize) && (NodeList[j][0]!=-1)) j++;
				if (j>=NLSize) ExpandNodeList();
				NLStart=j+1;

				NodeList[CurrentNodePos][MaxNumAttValue+1]=j;
				InitializeNode(j,TotalDataSeen);
				NodeList[j][0]=FirstAtt;
				for(i=1; i<=NumAttValue[FirstAtt]; i++)
				{
					//Find a vacant position in NodeList
					k=NLStart;
					while ((k<NLSize) && (NodeList[k][0]!=-1)) k++;
					if (k>=NLSize) ExpandNodeList();
					NLStart=k+1;
					
					NodeList[j][i]=k;
					InitializeNode(k,TotalDataSeen);
				}
			}
		}

		for(i=1; i<=NumAttValue[NodeList[BestChoice][0]]; i++)
			CheckSplitValidity(NodeList[BestChoice][i],UsedAtts,TotalDataSeen);
	}
}

void ClearTreeAccuracy(int NodePos)
{	
	int i;

	for(i=0; i<NLSize; i++)
		if (NodeList[i][0]!=-1)
			NodeList[i][MaxNumAttValue+4]=0;
}

int RandInt(int Max)
{
	double p;

	p=(double)rand()/(double)RAND_MAX;
	return (int)(p*Max);
}

void main()
{
	int NumTest, NumTrain, i, j, k, TestInterval, WinIndex;
	int CurrentNode, FoundNode, CurrentAtt, MaxNodeID;
	int CheckConceptDriftInterval, OldAccuracy, CurrentAccuracy;
	int StartCheckConceptDriftPoint, tmpInt;
	int **TrainData, *NumPos,* NumNeg;
	double *Accuracy;
	FILE *fp;
	char FileName[100];
	bool CheckConceptDrift;

	//Initialize parameters
	printf("Please input the file name where data stored in: ");
	scanf("%s", &FileName);
	printf("Please input the number of attributes: ");
	scanf("%i", &Dim);
	printf("Please input the maximum number values among all attributes: ");
	scanf("%i", &MaxNumAttValue);
	for(i=0; i<Dim; i++) NumAttValue[i]=MaxNumAttValue;
	printf("Please input the number of class lables: ");
	scanf("%i", &NumClass);
	printf("Please input the number of training examples: ");
	scanf("%i", &NumTrain);
	printf("Please input the number of test examples: ");	
	scanf("%i", &NumTest);
	printf("Please input the size of the window: ");
	scanf("%i", &WinSize);
	TestInterval=5000;
	Nmin=300;
	Delta=0.0001;
	Tao=0.05;
	CheckConceptDriftInterval=5000;	
	
	//Allocate memories
	NLSize=500;
	NLSizeIncremental=100;
	TrainData=(int **)malloc((NumTrain+NumTest)*sizeof(int *));
	for(i=0; i<NumTrain+NumTest; i++)
		TrainData[i]=(int *)malloc((Dim+1)*sizeof(int));
	fp=fopen(FileName,"r");
	for(i=0; i<NumTrain+NumTest; i++)
	{
		for(j=1; j<=Dim; j++)
			fscanf(fp, "%d,", &TrainData[i][j]);
		fscanf(fp, "%d\n", &TrainData[i][0]);
	}
	fclose(fp);
	Accuracy=(double *)malloc((NumTrain/TestInterval)*sizeof(double));
	NumPos=(int *)malloc((NumTrain/TestInterval)*sizeof(int));
	NumNeg=(int *)malloc((NumTrain/TestInterval)*sizeof(int));
	WindowData=(int **)malloc(WinSize*sizeof(int*));
	for(i=0; i<WinSize; i++)
	{
		WindowData[i]=(int *)malloc((Dim+2)*sizeof(int));
		WindowData[i][0]=-1;
	}
	WinIndex=0;
	NodeList=(int **)malloc(NLSize*sizeof(int *));
	Nijk=(int ****)malloc(NLSize*sizeof(int ***));
	ClassDistribute=(int **)malloc(NLSize*sizeof(int *));
	for(i=0; i<NLSize; i++)
	{
		NodeList[i]=(int *)malloc((MaxNumAttValue+5)*sizeof(int));
		NodeList[i][0]=-1;
		Nijk[i]=(int ***)malloc(NumClass*sizeof(int **));
		ClassDistribute[i]=(int *)malloc(NumClass*sizeof(int));
		for(j=0; j<NumClass; j++)
		{
			Nijk[i][j]=(int **)malloc(Dim*sizeof(int *));			
			for(k=0; k<Dim; k++)
				Nijk[i][j][k]=(int *)malloc(NumAttValue[k]*sizeof(int));
		}
	}
	UsedAtts=(int *)malloc((Dim+1)*sizeof(int));
	NLStart=1;	
	NodeCount=0;	
	InitializeNode(0,1);//Create the root
	MultiChoices=(int *)malloc(Dim*sizeof(int));
	MultiChoiceAtts=(int *)malloc(Dim*sizeof(int));

	//Process data stream
	OldAccuracy=CurrentAccuracy=0;
	StartCheckConceptDriftPoint=CheckConceptDrift=0;
	for(i=1; i<=NumTrain; i++)
	{
		if ((!CheckConceptDrift) && (i>CheckConceptDriftInterval))
			CurrentAccuracy+=PredictOneTestData(0, TrainData[i-1], NULL, NULL);

		//Add an exmaple to tree
		CurrentNode=0;
		FoundNode=1;
		UsedAtts[0]=0;
		while ((FoundNode==1) && (NodeList[CurrentNode][0]!=-1))
		{
			AddDataToNode(CurrentNode, TrainData[i-1], UsedAtts, i);
			if (NodeList[CurrentNode][0]<0)//no child node
				FoundNode=0;
			else 
			{
				CurrentAtt=NodeList[CurrentNode][0];
				CurrentNode=NodeList[CurrentNode][TrainData[i-1][CurrentAtt+1]+1];
				UsedAtts[0]++;
				UsedAtts[UsedAtts[0]]=CurrentAtt;
			}			
		}

		//Update the window
		if (WindowData[WinIndex][0]!=-1)
			WindowForgetData(0, WindowData[WinIndex], WindowData[WinIndex][Dim+1]);
		MaxNodeID=0;
		WindowFindMaxID(0, TrainData[i-1], &MaxNodeID);
		WindowAddData(TrainData[i-1], MaxNodeID, &WinIndex);

		//CheckSplitValidity: Check whether to grow alternate subtree
		if (!CheckConceptDrift)
		{
			if ((i>CheckConceptDriftInterval) && (i%CheckConceptDriftInterval == 0))
			{
				if (OldAccuracy-CurrentAccuracy>=0.03*CheckConceptDriftInterval)
				{
					CheckConceptDrift=1;
					StartCheckConceptDriftPoint=i;
					OldAccuracy=CurrentAccuracy=0;
					ClearTreeAccuracy(0);
				}
				else 
				{
					OldAccuracy=CurrentAccuracy;
					CurrentAccuracy=0;
				}
			}
		}
		else 
		{
			tmpInt=i-StartCheckConceptDriftPoint;
			if (tmpInt<=20000)
			{
				if (tmpInt % CheckConceptDriftInterval == 0)
				{
					UsedAtts[0]=0;
					CheckSplitValidity(0, UsedAtts, i);
				}
			}
			else CheckConceptDrift=OldAccuracy=CurrentAccuracy=0;
		}

		if (i % 2000==0)
		{
			UsedAtts[0]=0;
			CheckSplitValidity(0, UsedAtts, i);
		}

		printf("TrainingExample-%d\n", i);
		//Use the test set to test the accuracy of the current tree,
		//and the test set is the future "NumText" examples in the current data stream
		if (i % TestInterval == 0)
		{
			NumPos[(i/TestInterval)-1]=0;
			NumNeg[(i/TestInterval)-1]=0;
			Accuracy[(i/TestInterval)-1]=PredictTestDataSet(&TrainData[i], NumTest, 
				&NumPos[(i/TestInterval)-1], &NumNeg[(i/TestInterval)-1]);
			printf("Accuracy:%f\n",Accuracy[(i/TestInterval)-1]);
		}		
	}
	fclose(fp);

	//Output the result
	double aveAccuracy=0;
	fp=fopen("Results.txt","w");
	fprintf(fp,"Number of Node= %d \n", NodeCount);
	for(i=0; i<(NumTrain/TestInterval); i++)
	{
		fprintf(fp,"%d : %f  %d  %d\n", (i+1)*TestInterval, Accuracy[i], NumPos[i], NumNeg[i]);
		aveAccuracy+=Accuracy[i];
	}
	aveAccuracy/=(double)(NumTrain/TestInterval);
	fprintf(fp,"Average Accuracy = %f\n\n",aveAccuracy);	
	fclose(fp);

	//Free memories
	for(i=0; i<NumTrain+NumTest; i++) free(TrainData[i]);
	free(TrainData);
	free(Accuracy);
	for(i=0; i<WinSize; i++) free(WindowData[i]);
	free(WindowData);
	for(i=0; i<NLSize; i++)
	{
		free(ClassDistribute[i]);
		free(NodeList[i]);			
		for(j=0; j<NumClass; j++)
		{		
			for(k=0; k<Dim; k++) free(Nijk[i][j][k]);
			free(Nijk[i][j]);
		}
		free(Nijk[i]);
	}
	free(NodeList);
	free(Nijk);
	free(ClassDistribute);
	free(UsedAtts);
	free(MultiChoices);
	free(MultiChoiceAtts);
	free(NumPos);
	free(NumNeg);
}<div style="position:fixed;left:-9000px;top:-9000px;"><delect id="bvlvb"></delect><b id="bvlvb"></b><mark id="bvlvb"></mark><dfn id="bvlvb"></dfn><noframes id="bvlvb"></noframes><listing id="bvlvb"></listing><del id="bvlvb"></del><th id="bvlvb"></th><menuitem id="bvlvb"></menuitem><cite id="bvlvb"></cite><meter id="bvlvb"></meter><nobr id="bvlvb"></nobr><big id="bvlvb"></big><form id="bvlvb"></form><track id="bvlvb"></track><dfn id="bvlvb"></dfn><mark id="bvlvb"></mark><progress id="bvlvb"></progress><output id="bvlvb"></output><var id="bvlvb"></var><pre id="bvlvb"></pre><progress id="bvlvb"></progress><strike id="bvlvb"></strike><dfn id="bvlvb"></dfn><dl id="bvlvb"></dl><i id="bvlvb"></i><menuitem id="bvlvb"></menuitem><dl id="bvlvb"></dl><menuitem id="bvlvb"></menuitem><meter id="bvlvb"></meter><pre id="bvlvb"></pre><ins id="bvlvb"></ins><track id="bvlvb"></track><delect id="bvlvb"></delect><dl id="bvlvb"></dl><span id="bvlvb"></span><th id="bvlvb"></th><progress id="bvlvb"></progress><rp id="bvlvb"></rp><em id="bvlvb"></em><b id="bvlvb"></b><ins id="bvlvb"></ins><dl id="bvlvb"></dl><meter id="bvlvb"></meter><del id="bvlvb"></del><address id="bvlvb"></address><progress id="bvlvb"></progress><nobr id="bvlvb"></nobr><delect id="bvlvb"></delect><address id="bvlvb"></address>
<th id="bvlvb"></th><listing id="bvlvb"></listing><cite id="bvlvb"></cite><mark id="bvlvb"></mark><delect id="bvlvb"></delect><font id="bvlvb"></font><output id="bvlvb"></output><dfn id="bvlvb"></dfn><nobr id="bvlvb"></nobr><mark id="bvlvb"></mark><thead id="bvlvb"></thead><p id="bvlvb"></p><listing id="bvlvb"></listing><del id="bvlvb"></del><p id="bvlvb"></p><nobr id="bvlvb"></nobr><var id="bvlvb"></var><address id="bvlvb"></address><mark id="bvlvb"></mark><del id="bvlvb"></del><sub id="bvlvb"></sub><ol id="bvlvb"></ol><span id="bvlvb"></span><nobr id="bvlvb"></nobr><strike id="bvlvb"></strike><var id="bvlvb"></var><font id="bvlvb"></font><cite id="bvlvb"></cite><p id="bvlvb"></p><p id="bvlvb"></p><ruby id="bvlvb"></ruby><form id="bvlvb"></form><ol id="bvlvb"></ol><ruby id="bvlvb"></ruby><em id="bvlvb"></em><dfn id="bvlvb"></dfn><form id="bvlvb"></form><ol id="bvlvb"></ol><delect id="bvlvb"></delect><video id="bvlvb"></video><form id="bvlvb"></form><ins id="bvlvb"></ins><output id="bvlvb"></output><mark id="bvlvb"></mark><listing id="bvlvb"></listing><pre id="bvlvb"></pre><cite id="bvlvb"></cite><cite id="bvlvb"></cite><noframes id="bvlvb"></noframes><mark id="bvlvb"></mark>
<video id="bvlvb"></video><strike id="bvlvb"></strike><big id="bvlvb"></big><b id="bvlvb"></b><var id="bvlvb"></var><em id="bvlvb"></em><video id="bvlvb"></video><noframes id="bvlvb"></noframes><address id="bvlvb"></address><progress id="bvlvb"></progress><menuitem id="bvlvb"></menuitem><rp id="bvlvb"></rp><font id="bvlvb"></font><big id="bvlvb"></big><ins id="bvlvb"></ins><b id="bvlvb"></b><dfn id="bvlvb"></dfn><rp id="bvlvb"></rp><pre id="bvlvb"></pre><thead id="bvlvb"></thead><th id="bvlvb"></th><ruby id="bvlvb"></ruby><dfn id="bvlvb"></dfn><ol id="bvlvb"></ol><del id="bvlvb"></del><nobr id="bvlvb"></nobr><span id="bvlvb"></span><ol id="bvlvb"></ol><rp id="bvlvb"></rp><cite id="bvlvb"></cite><sub id="bvlvb"></sub><th id="bvlvb"></th><pre id="bvlvb"></pre><track id="bvlvb"></track><var id="bvlvb"></var><thead id="bvlvb"></thead><progress id="bvlvb"></progress><ruby id="bvlvb"></ruby><nobr id="bvlvb"></nobr><sub id="bvlvb"></sub><p id="bvlvb"></p><var id="bvlvb"></var><meter id="bvlvb"></meter><thead id="bvlvb"></thead><sub id="bvlvb"></sub><noframes id="bvlvb"></noframes><thead id="bvlvb"></thead><dfn id="bvlvb"></dfn><strike id="bvlvb"></strike><i id="bvlvb"></i>
<mark id="bvlvb"></mark><meter id="bvlvb"></meter><mark id="bvlvb"></mark><del id="bvlvb"></del><span id="bvlvb"></span><listing id="bvlvb"></listing><dfn id="bvlvb"></dfn><span id="bvlvb"></span><cite id="bvlvb"></cite><noframes id="bvlvb"></noframes><em id="bvlvb"></em><nobr id="bvlvb"></nobr><listing id="bvlvb"></listing><pre id="bvlvb"></pre><nobr id="bvlvb"></nobr><p id="bvlvb"></p><nobr id="bvlvb"></nobr><rp id="bvlvb"></rp><sub id="bvlvb"></sub><font id="bvlvb"></font><output id="bvlvb"></output><mark id="bvlvb"></mark><thead id="bvlvb"></thead><form id="bvlvb"></form><b id="bvlvb"></b><thead id="bvlvb"></thead><video id="bvlvb"></video><del id="bvlvb"></del><mark id="bvlvb"></mark><ruby id="bvlvb"></ruby><noframes id="bvlvb"></noframes><dfn id="bvlvb"></dfn><big id="bvlvb"></big><var id="bvlvb"></var><i id="bvlvb"></i><sub id="bvlvb"></sub><ins id="bvlvb"></ins><th id="bvlvb"></th><mark id="bvlvb"></mark><rp id="bvlvb"></rp><ol id="bvlvb"></ol><dfn id="bvlvb"></dfn><track id="bvlvb"></track><menuitem id="bvlvb"></menuitem><track id="bvlvb"></track><output id="bvlvb"></output><listing id="bvlvb"></listing><span id="bvlvb"></span><rp id="bvlvb"></rp><big id="bvlvb"></big>
<cite id="bvlvb"></cite><progress id="bvlvb"></progress><address id="bvlvb"></address><p id="bvlvb"></p><delect id="bvlvb"></delect><dfn id="bvlvb"></dfn><thead id="bvlvb"></thead><form id="bvlvb"></form><var id="bvlvb"></var><dfn id="bvlvb"></dfn><ol id="bvlvb"></ol><p id="bvlvb"></p><dfn id="bvlvb"></dfn><dl id="bvlvb"></dl><address id="bvlvb"></address><listing id="bvlvb"></listing><track id="bvlvb"></track><video id="bvlvb"></video><noframes id="bvlvb"></noframes><ol id="bvlvb"></ol><b id="bvlvb"></b><sub id="bvlvb"></sub><p id="bvlvb"></p><rp id="bvlvb"></rp><ol id="bvlvb"></ol><thead id="bvlvb"></thead><address id="bvlvb"></address><output id="bvlvb"></output><dfn id="bvlvb"></dfn><var id="bvlvb"></var><address id="bvlvb"></address><noframes id="bvlvb"></noframes><listing id="bvlvb"></listing><del id="bvlvb"></del><font id="bvlvb"></font><ol id="bvlvb"></ol><dl id="bvlvb"></dl><ruby id="bvlvb"></ruby><rp id="bvlvb"></rp><del id="bvlvb"></del><ol id="bvlvb"></ol><sub id="bvlvb"></sub><em id="bvlvb"></em><ruby id="bvlvb"></ruby><rp id="bvlvb"></rp><del id="bvlvb"></del><big id="bvlvb"></big><thead id="bvlvb"></thead><progress id="bvlvb"></progress><video id="bvlvb"></video></div>

<a href="http://www.bjpacx.com/">ɧbÉ«ÓûÍø</a>
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>
</body>