ds.SeparateChainingHashTable.h

#pragma once
#include "ds.hashtablebase.h"

// enable-disable testing classes in this file
#include "test.this.module.h"

using namespace std;

namespace yasi{
namespace ds{

	// Separate chaining collision resolution strategy
	// each bucket holds a list of values mapped into that bucket
	template<
		class Key,
		class Value = Key,
		class HashFunction = IntHashFunction<int>,
		class Pred = KVPairEqualityPredicate<Key>
	>
	class SeparateChainingHashTable : public HashTableBase<
		Key,
		Value,
		DoublyLinkedList< KVPair<Key, Value> >*,
		HashFunction>
	{
		///////////////// enable testing ///////////////////
		FRIEND_TEST_CLASS( SeparateChainingHashTableTest);

	protected:
		typedef KVPair<Key, Value> Pair;
		typedef DoublyLinkedList < Pair > List;
		typedef typename List::NodeType	Node;
	public:
		typedef List* BucketType;
		typedef List ListType;
	protected:
		// returns the pointer to the value if exists, otherwise returns NULL
		Node* bucketNode(BucketType pList, const Key& k) const{
			Pred keyEquals;
			for (List::iterator n = pList->begin(); n != pList->end(); n++){
				if (keyEquals((*n).key, k)){
					// found node; 
					return n.pNode;
				}
			}
			return NULL;
		}
		Pair* bucketEntry(BucketType pList, const Key& k) const{
			Pred keyEquals;
			for (List::iterator n = pList->begin(); n != pList->end(); n++){
				if (keyEquals((*n).key, k)){
					// found node; 
					return &(n.pNode->element);
				}
			}
			return NULL;
		}
		bool bucketContains(BucketType pList, const Key& k) const{
			Pred keyEquals;
			for (List::iterator n = pList->begin(); n != pList->end(); n++){
				if (keyEquals((*n).key, k)){
					// found node; 
					return true;
				}
			}
			return false;
		}
		virtual void copyTable(BucketType* oldTable, const unsigned int oldSize) override {
			//BucketType* oldTable = (BucketType*)prevTable;
			// copy old elements
			for (unsigned int i = 0; i < oldSize; i++){
				BucketType pList;
				if (pList = oldTable[i]){ // assigning oldTable[i] to pList
					// bucket exists; copy elements
					for (List::iterator n = pList->begin(); n != pList->end(); n++){
						Pair p = *n;
						put(p.key, p.value);
					}
					// now delete bucket
					pList->clear();
					DELETE_SAFE(oldTable[i]);
				}
			}

		}

		virtual bool isBucketEmpty(const int bucket) const override {
			return table[bucket] == NULL || table[bucket]->empty();
		}
	public:
		typedef Key		KeyType;
		typedef Value	ValueType;

		virtual ~SeparateChainingHashTable(){
			if (table){
				for (uint i = 0; i < _size; i++){
					// each entry is either NULL or a List*
					if (table[i]){
						table[i]->clear();
						DELETE_SAFE(table[i]);
					}
				}
			}
		}
		SeparateChainingHashTable(unsigned int logSize = INIT_LOGSIZE) : HashTableBase(logSize){

			//collisionHandler(this);
		}
		// returns true on success, false on failure
		virtual void put(const Key& k, const Value& v) override{
			int i = index(k);
			BucketType pList = table[i];
			if (pList == NULL){
				// empty slot; create a new list
				pList = table[i] = new List();
				// pushFront for better temporal locality
				pList->pushFront(Pair(k, v));
				_population++;
			}
			else{
				// existing bucket
				Pair* pEntry = bucketEntry(pList, k);
				if (pEntry){
					// key already exists; update value
					pEntry->value = v;
				}
				else{
					pList->pushFront(Pair(k, v));
					_population++;
				}
			}
			// do we need to grow?
			if (density() >= DENSITY_MAX) grow();
		}
		virtual void put(const Key& k) {
			put(k, k);
		}
		virtual Value* get(const Key& k) const override{
			int i = index(k);
			BucketType pList = table[i];
			if (pList != NULL){
				// existing bucket
				Pair* pEntry = bucketEntry(pList, k);
				if (pEntry)
					return &pEntry->value;
			}
			return NULL;
		}
		virtual void remove(const Key& k) override{
			int i = index(k);
			BucketType pList = table[i];
			if (pList == NULL){
				// the key is absent
				// nothing to do
			}
			else{
				// existing bucket
				Node* pNode = bucketNode(pList, k);
				if (pNode){
					pList->remove(pNode);
					_population--;
					// do we need to shrink?
					if (density() <= DENSITY_MIN) shrink();
				}
			}
		}
		virtual bool contains(const Key& k) const override{
			int i = index(k);
			BucketType pList = table[i];
			if (pList != NULL){
				// existing bucket
				return bucketContains(pList, k);
			}
			return false;
		}

	};


}
}