nuclear@0: #ifndef HASHTABLE_H_
nuclear@0: #define HASHTABLE_H_
nuclear@0: 
nuclear@0: #include <list>
nuclear@0: #include <vector>
nuclear@0: 
nuclear@0: template <class KeyT, class ValT> 
nuclear@0: struct Pair {
nuclear@0: 	KeyT key; 
nuclear@0: 	ValT val;
nuclear@0: };
nuclear@0: 
nuclear@0: template <class KeyType, class ValType>
nuclear@0: class HashTable {
nuclear@0: private:
nuclear@0: 
nuclear@0: 	size_t size;
nuclear@0: 	std::vector<std::list<Pair<KeyType, ValType> > > table;
nuclear@0: 	//std::list<Pair<KeyType, ValType> > table[100];
nuclear@0: 
nuclear@0: 	unsigned int (*HashFunc)(const KeyType &key, unsigned long size);
nuclear@0: 	unsigned int Hash(const KeyType &key) {return (unsigned int)HashFunc(key, (unsigned long)size);}
nuclear@0: 
nuclear@0: public:
nuclear@0: 
nuclear@0: 	HashTable(unsigned long size = 101);
nuclear@0: 	~HashTable();
nuclear@0: 
nuclear@0: 	void SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long));
nuclear@0: 
nuclear@0: 	void Insert(KeyType key, ValType value);
nuclear@0: 	void Remove(KeyType key);
nuclear@0: 
nuclear@0: 	Pair<KeyType, ValType> *Find(KeyType key);
nuclear@0: };
nuclear@0: 
nuclear@0: //// std hash function
nuclear@0: //template <class KeyType>
nuclear@0: //unsigned int _HashFunction(const KeyType &key, unsigned long size) {
nuclear@0: //	return (size_t)key % size;
nuclear@0: //}
nuclear@0: 
nuclear@0: // hash table member functions
nuclear@0: template <class KeyType, class ValType>
nuclear@0: HashTable<KeyType, ValType>::HashTable(unsigned long size) {
nuclear@0: 	this->size = size;
nuclear@0: 	//HashFunc = _HashFunction;
nuclear@0: 	table.resize(size);
nuclear@0: }
nuclear@0: 
nuclear@0: template <class KeyType, class ValType>
nuclear@0: HashTable<KeyType, ValType>::~HashTable() {
nuclear@0: 	for(unsigned long i=0; i<size; i++) {
nuclear@0: 		table[i].erase(table[i].begin(), table[i].end());
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: template <class KeyType, class ValType>
nuclear@0: void HashTable<KeyType, ValType>::SetHashFunction(unsigned int (*HashFunc)(const KeyType&, unsigned long)) {
nuclear@0: 	this->HashFunc = HashFunc;
nuclear@0: }
nuclear@0: 
nuclear@0: template <class KeyType, class ValType>
nuclear@0: void HashTable<KeyType, ValType>::Insert(KeyType key, ValType value) {
nuclear@0: 	Pair<KeyType, ValType> newpair;
nuclear@0: 	newpair.key = key;
nuclear@0: 	newpair.val = value;
nuclear@0: 
nuclear@0: 	table[Hash(key)].push_back(newpair);
nuclear@0: }
nuclear@0: 
nuclear@0: template <class KeyType, class ValType>
nuclear@0: void HashTable<KeyType, ValType>::Remove(KeyType key) {
nuclear@0: 
nuclear@0: 	unsigned int pos = Hash(key);
nuclear@0: 
nuclear@0: 	std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
nuclear@0: 	while(iter != table[pos].end()) {
nuclear@0: 		if(iter->key == key) {
nuclear@0: 			table[pos].erase(iter);
nuclear@0: 			return;
nuclear@0: 		}
nuclear@0: 		iter++;
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: template <class KeyType, class ValType>
nuclear@0: Pair<KeyType, ValType> *HashTable<KeyType, ValType>::Find(KeyType key) {
nuclear@0: 
nuclear@0: 	unsigned int pos = Hash(key);
nuclear@0: 
nuclear@0: 	std::list<Pair<KeyType, ValType> >::iterator iter = table[pos].begin();
nuclear@0: 	while(iter != table[pos].end()) {
nuclear@0: 		if(iter->key == key) {
nuclear@0: 			return &(*iter);
nuclear@0: 		}
nuclear@0: 		iter++;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	return 0;
nuclear@0: }
nuclear@0: 
nuclear@0: #endif	// HASHTABLE_H_