/* fptN20.c (release mode) *//* Mining N-most interesting large itemsets *//* array of linked lists for support[], largeItemset[][][] and numLarge[] *//* redo mining if there is not enough k-itemsets *//* modifications: 1, 6, 7, 8, 4, 9, 13, 14 *//* N21.c + N16.c */#include<stdio.h>#include<stdlib.h>#include<string.h>#include <sys/resource.h>#include <sys/times.h>#include <unistd.h>/***** Data Structure *****/typedef struct FPnode *FPTreeNode;typedef struct Childnode *childLink;typedef struct Childnode {	FPTreeNode node;	childLink next;} ChildNode;typedef struct FPnode {        /* int leaf; */        int item;        int count;	int numPath; 	FPTreeNode parent;        childLink children;        FPTreeNode hlink;} FPNode;typedef struct Itemsetnode *LargeItemPtr;typedef struct Itemsetnode {	int support;	int *itemset;	LargeItemPtr next;} ItemsetNode;		/***** Global Variables *****/int startHeader;int round=0;LargeItemPtr *largeItemset;int *numLarge;int *support1;int *largeItem1;int *limit;int *thresholdK;FPTreeNode root=NULL;FPTreeNode *headerTableLink;int headerTableSize;int N;int expectedK;int realK;int threshold;int oldThreshold;int numItem;int numTrans;float decreaseRate;char dataFile[50];char treeFile[50];char outFile[50];int *arrThresholdK;void destroyTree(FPTreeNode node, int level){ childLink temp1, temp2; if (node == NULL) return; temp1 = node->children; while(temp1 != NULL) {	temp2 = temp1->next;	destroyTree(temp1->node, level+1);	free(temp1);	temp1 = temp2; } free(node); return;}void destroy(){ LargeItemPtr aLargeItemset;  int i; for (i=0; i < realK; i++) {	aLargeItemset = largeItemset[i];	while (aLargeItemset != NULL) {		largeItemset[i] = largeItemset[i]->next;		free(aLargeItemset->itemset);		free(aLargeItemset);		aLargeItemset = largeItemset[i];	} } free(largeItemset); free(numLarge); free(support1); free(largeItem1); free(limit); destroyTree(root, 1); free(headerTableLink); free(thresholdK); return;}/* swap x th element and i th element */void swap2(int *support, int x, int i){  int temp;  temp = support[x]; support[x] = support[i]; support[i] = temp;  return;}/* Quick sort support[] and the corresponding itemset[] in descending order. * Parameters: *      support[]	-> array to be sorted *      itemset[]	-> array to be sorted *      low		-> lower bound index of the array to be sorted *      high		-> upper bound index of the array to be sorted *      size		-> size of the array *	length		-> length of an itemset */void q_sort2(int *support, int low,int high, int size){ int pass; int highptr=high++;     /* highptr records the last element */ /* the first element in list is always served as the pivot */ int pivot=low; if(low>=highptr) return; do {	/* find out 1st element value larger than the pivot's */	pass=1;	while(pass==1) {		if(++low<size) {			if(support[low] > support[pivot])				pass=1;			else pass=0;		} else pass=0;	} 	/* find out 1st element value smaller than the pivot's */ 	pass=1; 	while(pass==1) {		if(high-->0) { 			if(support[high] < support[pivot]) 				pass=1;			else pass=0; 		} else pass=0; 	}	/* swap elements pointed by low pointer & high pointer */	if(low<high)		swap2(support, low, high); } while(low<=high); swap2(support, pivot, high); /* divide list into two for further sorting */  q_sort2(support, pivot, high-1, size);  q_sort2(support, high+1, highptr, size);  return;}void visitTree(FPTreeNode T, int level){ childLink child; if (level == realK-1) { 	child = T->children;  	while (child != NULL) {		arrThresholdK[N] = child->node->count;				q_sort2(arrThresholdK, 0, N, N+1);		child = child->next;	}	return; } child = T->children; while (child != NULL) {	visitTree(child->node, level+1);	child = child->next; } return;}void initThresholdK(){ int i; int level=0; thresholdK = (int *) malloc (sizeof(int) * realK); if (thresholdK == NULL) {	printf("out of memory\n");	exit(1); } arrThresholdK = (int *) malloc (sizeof(int) * N); if (arrThresholdK == NULL) {	printf("out of memory\n");	exit(1); } threshold = 1; for (i=0; i <= N; i++) {	arrThresholdK[i] = threshold; } visitTree(root, level); for (i=1; i < realK; i++) {	thresholdK[i] = arrThresholdK[N-1]; } free(arrThresholdK);  threshold = thresholdK[realK-1]; return;}/* swap x th element and i th element */void swap(int *support, int *itemset, int x, int i){  int temp;  temp = support[x]; support[x] = support[i]; support[i] = temp; temp = itemset[x]; itemset[x] = itemset[i]; itemset[i] = temp;  return;}/* Quick sort support[] and the corresponding itemset[] in descending order. * Parameters: *      support[]	-> array to be sorted *      itemset[]	-> array to be sorted *      low		-> lower bound index of the array to be sorted *      high		-> upper bound index of the array to be sorted *      size		-> size of the array *	length		-> length of an itemset */void q_sortD(int *support, int *itemset, int low,int high, int size){ int pass; int highptr=high++;     /* highptr records the last element */ /* the first element in list is always served as the pivot */ int pivot=low; if(low>=highptr) return; do {	/* find out 1st element value larger than the pivot's */	pass=1;	while(pass==1) {		if(++low<size) {			if(support[low] > support[pivot])				pass=1;			else pass=0;		} else pass=0;	} 	/* find out 1st element value smaller than the pivot's */ 	pass=1; 	while(pass==1) {		if(high-->0) { 			if(support[high] < support[pivot]) 				pass=1;			else pass=0; 		} else pass=0; 	}	/* swap elements pointed by low pointer & high pointer */	if(low<high)		swap(support, itemset, low, high); } while(low<=high); swap(support, itemset, pivot, high); /* divide list into two for further sorting */  q_sortD(support, itemset, pivot, high-1, size);  q_sortD(support, itemset, high+1, highptr, size);  return;}/* Quick sort indexList[] and freqItemP[] in ascending order. * Parameters: *      indexList[]     -> array to be sorted *      freqItemP[]     -> array to be sorted *      low             -> lower bound index of the array to be sorted *      high            -> upper bound index of the array to be sorted *      size            -> size of the array *      length          -> length of an itemset */void q_sortA(int *indexList, int *freqItemP, int low, int high, int size){ int pass; int highptr=high++;     /* highptr records the last element */ /* the first element in list is always served as the pivot */ int pivot=low; if(low>=highptr) return; do {        /* find out 1st element value smaller than the pivot's */        pass=1;        while(pass==1) {                if(++low<size) {                        if(indexList[low] < indexList[pivot])                                pass=1;                        else pass=0;                } else pass=0;        }        /* find out 1st element value larger than the pivot's */        pass=1;        while(pass==1) {                if(high-->0) {                        if(indexList[high] > indexList[pivot])                                pass=1;                        else pass=0;                } else pass=0;        }        /* swap elements pointed by low pointer & high pointer */        if(low<high)                swap(indexList, freqItemP, low, high); } while(low<=high); swap(indexList, freqItemP, pivot, high); /* divide list into two for further sorting */ q_sortA(indexList, freqItemP, pivot, high-1, size); q_sortA(indexList, freqItemP, high+1, highptr, size); return;}void addToLargeList(int *pattern, int patternSupport, int index){ LargeItemPtr aLargeItemset; LargeItemPtr aNode, previous=NULL; int i; aLargeItemset = (LargeItemPtr) malloc (sizeof(ItemsetNode)); if (aLargeItemset == NULL) {	printf("out of memory\n");	exit(1); } aLargeItemset->itemset = (int *) malloc (sizeof(int) * (index+1)); if (aLargeItemset->itemset == NULL) {	printf("out of memory\n");	exit(1); } aLargeItemset->support = patternSupport; for (i=0; i <= index; i++) {	aLargeItemset->itemset[i] = pattern[i]; } aLargeItemset->next = NULL; aNode = largeItemset[index]; if (aNode == NULL) {	largeItemset[index] = aLargeItemset; } else { 	while ((aNode != NULL) && (aNode->support > patternSupport)) {		previous = aNode;		aNode = aNode->next; 	} 	if (previous != NULL) {		previous->next = aLargeItemset;		aLargeItemset->next = aNode;	} else {		aLargeItemset->next = largeItemset[index];		largeItemset[index] = aLargeItemset;	} } (numLarge[index])++; if (numLarge[index] >= limit[index]) {        aNode = largeItemset[index];        for (i=1; i < limit[index]; i++)                aNode = aNode->next;        if (thresholdK[index] < aNode->support) {                thresholdK[index] = aNode->support;		threshold = thresholdK[realK-1];		for (i = realK-2; i > 0; i--)			if (thresholdK[i] < threshold)				threshold = thresholdK[i];	} }  return;}void combine(int *itemList, int *support, int start, int itemListSize, int *base, int baseSize){ int *pattern; int i, j;  if (baseSize >= realK) return; if (start == itemListSize) return; pattern = (int *) malloc (sizeof(int) * (baseSize+1)); if (pattern == NULL) {	printf("out of memory\n");	exit(1); } for (j=0; j < baseSize; j++)	pattern[j+1] = base[j]; for (i=start; i < itemListSize; i++) {	pattern[0] = itemList[i];	if ((baseSize > 0) && (support[i] < oldThreshold)		&& (support[i] >= thresholdK[baseSize]))		addToLargeList(pattern , support[i], baseSize);	combine(itemList, support, i+1, itemListSize, pattern, baseSize+1);	 } free(pattern);  return;}void insert_tree(int *freqItemP, int *indexList, int count, int ptr, int length, 			FPTreeNode T, FPTreeNode *headerTableLink, int *path)  { childLink newNode; FPTreeNode hNode; FPTreeNode hPrevious; childLink previous; childLink aNode; if (ptr == length) return; if (T->children == NULL) {	/* T has no children */	newNode = (childLink) malloc (sizeof(ChildNode));	if (newNode == NULL) {		printf("out of memory\n");		exit(1);	}	newNode->node = (FPTreeNode) malloc (sizeof(FPNode));	if (newNode->node == NULL) {		printf("out of memory\n");		exit(1);	}	newNode->node->item = freqItemP[ptr];	newNode->node->count = count;	newNode->node->numPath = 1;	newNode->node->parent = T;	newNode->node->children = NULL;	newNode->node->hlink = NULL;	newNode->next = NULL;	T->children = newNode;	hNode = headerTableLink[indexList[ptr]];	if (hNode == NULL) {		headerTableLink[indexList[ptr]] = newNode->node;	} else {		while (hNode != NULL) {			hPrevious = hNode;			hNode = hNode->hlink;		}		hPrevious->hlink = newNode->node;	}	insert_tree(freqItemP, indexList, count, ptr+1, length, 				T->children->node, headerTableLink, path);	T->numPath += *path; } else {	aNode = T->children;	while ((aNode != NULL) && (aNode->node->item != freqItemP[ptr])) {		previous = aNode;		aNode = aNode->next;	}	if (aNode == NULL) {		/* create a new child for T */ 		newNode = (childLink) malloc (sizeof(ChildNode));		if (newNode == NULL) {			printf("out of memory\n");			exit(1);		}		newNode->node = (FPTreeNode) malloc (sizeof(FPNode));		if (newNode->node == NULL) {			printf("out of memory\n");			exit(1);		}		newNode->node->item = freqItemP[ptr];		newNode->node->count = count;		newNode->node->numPath = 1;		newNode->node->parent = T;		newNode->node->children = NULL;		newNode->node->hlink = NULL;		newNode->next = NULL;		previous->next = newNode;				hNode = headerTableLink[indexList[ptr]];		if (hNode == NULL)			headerTableLink[indexList[ptr]] = newNode->node;		else {			while (hNode != NULL) {				hPrevious = hNode;				hNode = hNode->hlink;			}			hPrevious->hlink = newNode->node;		}		insert_tree(freqItemP, indexList, count, ptr+1, length, 					newNode->node, headerTableLink, path);		(*path)++;				T->numPath += *path;	} else {		/* match an existing child of T */		aNode->node->count += count;		insert_tree(freqItemP, indexList, count, ptr+1, length, 				aNode->node, headerTableLink, path);		T->numPath += *path; 	} } return;}void buildConTree(FPTreeNode *conRoot, FPTreeNode **conHeader, int conHeaderSize, int *conLargeItem,		int *conLargeItemSupport, FPTreeNode T, FPTreeNode *headerTable, int baseIndex, int headerSize){ FPTreeNode aNode; FPTreeNode aNode2; int *freqItemP; int *indexList; int path; int count; int i; /* build header table */ *conHeader = (FPTreeNode *) malloc (sizeof(FPTreeNode) * conHeaderSize); if (*conHeader == NULL) {        printf("out of memory\n");        exit(1); } for (i=0; i < conHeaderSize; i++)        (*conHeader)[i] = NULL; /* create root of the FP-tree */ (*conRoot) = (FPTreeNode) malloc (sizeof(FPNode)); if (*conRoot == NULL) {        printf("out of memory\n");        exit(1); } (*conRoot)->numPath = 1; (*conRoot)->parent = NULL; (*conRoot)->children = NULL; (*conRoot)->hlink = NULL; freqItemP = (int *) malloc (sizeof(int) * conHeaderSize); if (freqItemP == NULL) {        printf("out of memory\n");        exit(1); } indexList = (int *) malloc (sizeof(int) * conHeaderSize); if (indexList == NULL) {        printf("out of memory\n");        exit(1); }