ds.hashtablebase.h

#pragma once
#include "common.h"
#include "ds.kvpair.h"
//#include "ds.doublylinkedlist.h"
//#include "ds.iterator.h"
using namespace std;

namespace yasi{
namespace ds{


template<class Key, class Value = Key>
class IKeyValueStore{
protected:
	enum {
		RESIZE_GROW = 0,
		RESIZE_SHRINK
	};
	virtual void resize(const int growOrShrink, const unsigned int logFactor = 1) = 0;
	void grow() { resize(RESIZE_GROW, 1); } // doubles the capacity
	void shrink() { resize(RESIZE_SHRINK, 1); } // halves the capacity
public:
	virtual ~IKeyValueStore(){}
	virtual Value* get(const Key&) const = 0;
	virtual void put(const Key&, const Value&) = 0;
	virtual bool contains(const Key&) const = 0;
	virtual void remove(const Key&) = 0;
};

template<class Key>
class IHashFunction{
public:
	virtual int operator()(const Key& n) const = 0;
};

template<class Key>
class IntHashFunction : public IHashFunction<Key>{
public:
	virtual int operator()(const Key& n) const override{
		return n ^ (~n << 11) ^ (n << 3) ^ (~n << 27);
	}
};


class StringHashFunction{
	static const int A = 54059; /* a prime */
	static const int B = 76963; /* another prime */
	static const int C = 86969; /* yet another prime */
public:

	virtual int operator()(const char* s) const {
		unsigned int h = 31 /* also prime */;
		while (*s) {
			h = (h * A) ^ (s[0] * B);
			s++;
		}
		return h; // or return h % C;	
	}
	virtual int operator()(std::string str) const {
		unsigned int h = 31 /* also prime */;
		const char* s = str.c_str();
		while (*s) {
			h = (h * A) ^ (s[0] * B);
			s++;
		}
		return h; // or return h % C;	
	}
};


// various simplistic hash functions for testing
namespace testhash{
	template<class Key>
	class IdentityFunction : public IHashFunction < Key > {
	public:
		virtual int operator()(const Key& n) const override{
			return n;
		}
	};
	template<class Key>
	class Mod8Function : public IHashFunction < Key > {
	public:
		static const unsigned int modulus = 8;
		virtual int operator()(const Key& n) const override{
			return n % 8;
		}
	};
	template<class Key>
	class Mod16Function : public IHashFunction < Key > {
	public:
		static const unsigned int modulus = 16;
		virtual int operator()(const Key& n) const override{
			return n % 16;
		}
	};
	template<class Key>
	class Mod32Function : public IHashFunction < Key > {
	public:
		static const unsigned int modulus = 32;
		virtual int operator()(const Key& n) const override{
			return n % 32;
		}
	};
	// mod 16 by default
	template<class Key>
	class ModFunction : public IHashFunction < Key > {
	public:
		unsigned int modulus;
		ModFunction() : modulus(16){}
		virtual int operator()(const Key& n) const override{
			return n % modulus;
		}
	};

} // namespace testhash


//template<class Bucket, class Key>
//class ICollisionStrategy{
//
//public:
//	virtual ~ICollisionResolutionStrategy(){}
//	// either returns a ptr to the bucket-index, or NULL if no bucket found
//	virtual int* findBucket(const Key& k, (void*)pHashTable) = 0;
//};


template<	class Key, 
			class Value,
			class BucketType,
			class HashFunction
>
class HashTableBase : public IKeyValueStore < Key, Value >{
protected:

	// size of the table
	// must be a power of two
	unsigned int _size;
	unsigned int _logSize;
	static const unsigned int INIT_LOGSIZE = 5; // 32 elements
	// actual number of keys stored in the table
	unsigned int _population;
	// the buckets array
	BucketType* table;
	// the hash function
	HashFunction hash;
	// load factor for growth and shrinkage
	const float DENSITY_MAX;
	const float DENSITY_MIN;
	// compute hashCode modulo table size
	inline int modSize(const unsigned int k) const{
		return k & ((1 << _logSize) - 1);
	}
	inline int index(const Key& k) const{
		return modSize(hash(k)); // hash(k) % _size 
	}
	BucketType& bucket(const Key& k) const{
		return table[index(k)];
	}
	void initTable(BucketType* pTable, const int numElems){
		// initialize to zero
		memset(pTable, 0, numElems * sizeof(BucketType));
	}
	inline float density(){ return ((float) _population) / _size; }
	// true if the specified population would be too dense for current table
	inline bool needGrow(const int pop) const { return (((float)pop) / _size) >= DENSITY_MAX; }
	// true if the specified population would be too sparse for current table
	inline bool needShrink(const int pop) const { return (((float)pop) / _size) <= DENSITY_MIN; }

	// pure virtual function
	virtual inline bool isBucketEmpty(const int bucket) const = 0;

	inline unsigned int maxPopulationWithoutGrow() const{
		return (unsigned int)(_size * DENSITY_MAX) - 1;
	}
	inline unsigned int minPopulationWithoutShrink() const{
		return (unsigned int)(_size * DENSITY_MIN) + 1;
	}

	virtual void copyTable(BucketType* oldTable, const unsigned int oldSize) = 0;
	// grows/shrinks by specified logFactor
	// that is, newSize is either oldSize << logFactor (grow)
	// or oldSize >> logFactor (shrink)
	virtual void resize(const int growOrShrink, const unsigned int logFactor = 1) {
		unsigned int oldLogSize = _logSize;
		unsigned int oldSize = _size;
		unsigned int oldPopulation = _population;
		BucketType* oldTable = table;
		unsigned int newLogSize, newSize;

		if (growOrShrink == RESIZE_GROW){
			newLogSize = _logSize + logFactor;
			newSize = _size << logFactor;
		}
		else if (growOrShrink == RESIZE_SHRINK){
			newLogSize = _logSize - logFactor;
			newSize = _size >> logFactor;
		}
		else{
			// do nothing
			return;
		}

		// great; now we either grow or shrink
		_logSize = newLogSize;
		_size = newSize;
		_population = 0;

		table = allocTable(newSize); // twice the current size
		
		initTable(table, newSize); // initialize with zero
		// copy old elements
		// copy table elements
		
		copyTable(oldTable, oldSize);
		// now delete oldTable
		deallocTable(oldTable);
	} // method resize

	// allocates memory for hashtable
	BucketType* allocTable(const int numElems){
		// *pTable = new BucketType[newSize]; // twice the current size
		BucketType* pTable = (BucketType*)malloc(numElems * sizeof(BucketType));
		return pTable;
	}
	void deallocTable(BucketType* pTable){
		// DELETE_ARR_SAFE(pTable);
		FREE_SAFE(pTable);
	}
public:
	// the type of the entries in the hash table
	HashTableBase(unsigned int logSize = INIT_LOGSIZE) : _logSize(logSize), _size(1 << logSize), _population(0), DENSITY_MAX(0.75), DENSITY_MIN(0.25){
		assert(_logSize > 0);
		// table = new BucketType[_size];
		table = allocTable(_size);
		initTable(table, _size);
	}
	virtual ~HashTableBase(){ 
		deallocTable(table);
		_size = _population = _logSize = 0; 
	}

	inline unsigned int size() const { return _size; }
	inline unsigned int population() const { return _population; }


	string toString() const{
		stringstream buf;
		for (uint i = 0; i < _size; i++){
			buf << "[" << i << "] ";
			if (!isBucketEmpty(i)) buf << table[i];
			buf << endl;
		}
		return buf.str();
	}

};
// override for printing
template<	class Key,
			class Value,
			class BucketType,
			class HashFunction
>
std::ostream& operator<< (std::ostream& out, const HashTableBase<Key,Value,BucketType,HashFunction>& h) {
	out << h.toString();
	return out;
}


} // namespace ds
} // namespace yasi