hashtable.h

关联分类算法采用贪心算法发现高质量分类规则

// HashTable.h: interface for the HashTable class.
//
//////////////////////////////////////////////////////////////////////


#include <vector>
using namespace std ;


//Must define "=" and "==" for Type!!!

#define LOAD_FACTOR 2.0

template<class Type>
class HashTable  
{
public:
	HashTable(int size=100);
	HashTable(int (*pHash)(const Type& x),int size=101);
	virtual ~HashTable();

	void SetHashFunc(int (*pHash)(const Type& x)){m_pHash=pHash;}

	int GetSize() const {return m_Size;}
	int GetNumData() const {return m_NumData;}
	
	int Insert(Type x);
	int Remove(const Type& x);
	int Find(const Type& x) const;
	int GetData(Type& x) const;

	void Empty();

	vector<Type> GetAt(int pos) const;

	void WriteTo(FILE* f);
	void ReadFrom(FILE* f);

	void operator =(const HashTable<Type>& table);

private:
	int m_Size;
	vector<Type> *m_Data;

	int m_NumData;

	//hash function
	int (*m_pHash)(const Type& x);

	void Resize(int newsize);
};

template<class Type> 
HashTable<Type>::HashTable(int size)
{
	m_Data=new vector<Type>[size];
	m_Size=size;
	m_NumData=0;
}

template<class Type> 
HashTable<Type>::HashTable(int (*pHash)(const Type& x),int size)
{
	m_Data=new vector<Type>[size];
	m_Size=size;
	m_NumData=0;
	m_pHash=pHash;
}

template<class Type> 
HashTable<Type>::~HashTable()
{
	delete[] m_Data;
}

//return 1 if insert a new element. return 0 if replace an old element with a new one.
template<class Type>
int HashTable<Type>::Insert(Type x)
{
	int finded=0;

	int pos=(*m_pHash)(x) % GetSize();

	for(typename vector<Type>::iterator it = m_Data[pos].begin(); it!=m_Data[pos].end(); it++)
	{
		if(*it==x)
		{
			finded=1;
			*it=x;
			break;
		}
	}

	if(!finded)
	{
		m_Data[pos].push_back(x);
		m_NumData++;
		if((double)m_NumData/m_Size>LOAD_FACTOR) 
			Resize(GetSize()*2+1);
		return 1;
	}
	else
		return 0;
}

template<class Type>
int HashTable<Type>::Remove(const Type& x)
{
	int pos=(*m_pHash)(x) % GetSize();
	for(typename vector<Type>::iterator it=m_Data[pos].begin();it!=m_Data[pos].end();it++)
	{
		if(*it==x)
		{
			erase(it);
			m_NumData--;
			return 1;
		}
	}
	return 0;
}

template<class Type>
int HashTable<Type>::Find(const Type& x) const
{
	int pos=(*m_pHash)(x) % GetSize();

	for(typename vector<Type>::iterator it=m_Data[pos].begin();it!=m_Data[pos].end();it++)
	{
		if(*it==x)
			return 1;
	}
	return 0;
}

template<class Type>
int HashTable<Type>::GetData(Type& x) const
{
	int pos=(*m_pHash)(x) % GetSize();
	for(typename vector<Type>::iterator it=m_Data[pos].begin();it!=m_Data[pos].end();it++)
	{
		if(*it==x)
		{
			x=*it;
			return 1;
		}
	}
	return 0;
}

template<class Type>
vector<Type> HashTable<Type>::GetAt(int pos) const
{
	return m_Data[pos];
}

template<class Type>
void HashTable<Type>::Resize(int newsize)
{
	vector<Type>* pNewData=new vector<Type>[newsize];
	for(int pos=0;pos<GetSize();pos++)
	{
		for(typename vector<Type>::iterator it=m_Data[pos].begin();it!=m_Data[pos].end();it++)
		{
			Type x=*it;
			int newpos=(*m_pHash)(x) % newsize;
			pNewData[newpos].push_back(x);
		}
	}

	delete[] m_Data;
	m_Data=pNewData;
	m_Size=newsize;
}

template<class Type>
void HashTable<Type>::Empty()
{
	for(int pos=0;pos<GetSize();pos++)
	{
		m_Data[pos].clear();
	}
	m_NumData=0;
}

template<class Type>
void HashTable<Type>::operator =(const HashTable<Type>& table)
{
	Empty();
	Resize(table.GetSize());
	for(int pos=0;pos<GetSize();pos++)
	{
		m_Data[pos].empty();
		vector<Type> vec=table.GetAt(pos);
		if(vec.size()==0)
			continue;
		for(typename vector<Type>::iterator it=vec.begin();it!=vec.end();it++)
		{
			Type x=*it;
			m_Data[pos].push_back(x);
		}
	}
	m_NumData=table.GetNumData();
}

template<class Type>
void HashTable<Type>::WriteTo(FILE* f)
{
	for(int pos=0;pos<GetSize();pos++)
	{
		for(typename vector<Type>::iterator it=m_Data[pos].begin();it!=m_Data[pos].end();it++)
		{
			(*it).WriteTo(f);
//			fprintf(f,"\n");
		}
	}
}

template<class Type>
void HashTable<Type>::ReadFrom(FILE* f)
{
	Empty();
	while(1)
	{
		Type x;
		if(x.ReadFrom(f))
		{
			fscanf(f,"\n");
			Insert(x);
		}
		else
		{
			break;
		}
	}
}