common.cpp

关联规则中转换树算法在VC下的实现

// common.cpp: implementation of the common class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "AssocRule.h"
#include "common.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

common::common()
{

}

common::~common()
{

}

template <class T> void swap(T* k, T* j)
{
	T temp;
	temp = *j;
	*j = *k;
	*k = temp;
}

// Ascending
int common::findpivot(int *list, const int& l, const int& h)
{
	int pivot;
	int idx = (l+h)/2;
	
	if (list[l]>list[h])
		swap(list+l, list+h);
	
	if (list[idx]>list[l])
	{
		if(list[idx]<list[h])
		{
			pivot=list[idx];
			swap(list+idx, list+h);
		}
		else
			pivot=list[h];
	}
	else
	{
		pivot=list[l];
		swap(list+l, list+h);
	}
	
	return pivot;
}

// Ascending
int common::partition(int *list, int l, int h)
{
	int pivot=findpivot(list, l, h);
	
	while (l < h)
	{
		while (--h && list[h]>pivot);
		
		while (list[l]<pivot)
			++l;
		
		if (l<h)
			swap(list+l, list+h);
	}
	return l;
}

// Ascending
void common::sort(int *list, int low, int high)
{
	int i1, i2, ipos;
	
	for (i1=low; i1<high; i1++)
	{
		ipos = i1;
		int item1 = list[i1];
		for (i2=i1+1; i2<=high; i2++)
		{
			if (list[i2] < item1)
			{
				ipos=i2;
				item1 = list[ipos];
			}
		}
		
		if (ipos != i1)
		{
			list[ipos] = list[i1];
			list[i1] = item1;
		}
	}
}

// Ascending
void common::QuickSort(int *list, int low, int high)
{
	if (high-low < 8) sort(list, low, high);
	else
	{
		int k = partition(list, low, high);
		swap(list+k, list+high);
		
		if((k-low)>1) QuickSort(list, low, k-1);
		if((high-k)>1) QuickSort(list, k+1, high);
	}
}

// Descending
int common::findpivot(int *list, int *list2, const int& l, const int& h)
{
	int pivot;
	int idx = (l+h)/2;
	
	if (list[l]>list[h])
	{
		swap(list+l, list+h);
		swap(list2+l, list2+h);
	}
	
	if (list[idx]>list[l])
	{
		if(list[idx]<list[h])
		{
			pivot=list[idx];
			swap(list+idx, list+h);
			swap(list2+idx, list2+h);
		}
		else
			pivot=list[h];
	}
	else
	{
		pivot=list[l];
		swap(list+l, list+h);
		swap(list2+l, list2+h);
	}
	
	return pivot;
}

// Descending
int common::partition(int *list, int *list2, int l, int h)
{
	int pivot=findpivot(list, list2, l, h);
	
	while (l < h)
	{
		while (--h && list[h]<pivot);
		
		while (list[l]>pivot)
			++l;
		
		if (l<h)
		{
			swap(list+l, list+h);
			swap(list2+l, list2+h);
		}
	}
	return l;
}

// Descending
void common::sort(int *list, int *list2, int low, int high)
{
	int i1, i2, ipos;
	
	for (i1=low; i1<high; i1++)
	{
		ipos = i1;
		int item1 = list[i1];
		for (i2=i1+1; i2<=high; i2++)
		{
			if (list[i2] > item1)
			{
				ipos=i2;
				item1 = list[ipos];
			}
		}
		
		if (ipos != i1)
		{
			list[ipos] = list[i1];
			list[i1] = item1;
			swap(list2+ipos, list2+i1);
		}
	}
}

// Descending
void common::QuickSort(int *list, int *list2, int low, int high)
{
	if (high-low < 8) sort(list, list2, low, high);
	else
	{
		int k = partition(list, list2, low, high);
		swap(list+k, list+high);
		swap(list2+k, list2+high);
		
		if((k-low)>1) QuickSort(list, list2, low, k-1);
		if((high-k)>1) QuickSort(list, list2, k+1, high);
	}
}