ds.SeparateChainingHashTable.test.h

#pragma once

#if YASI_TEST_THIS_MODULE != 1
#define YASI_TEST_THIS_MODULE  1
#endif
#include "ds.SeparateChainingHashTable.h"

namespace yasi{
	namespace ds{
		class SeparateChainingHashTableTest : public yasi::Test{
		protected:
			typedef SeparateChainingHashTable<int, int> IntHashTable;
			typedef KVPair<int, int> Pair;
			typedef IntHashTable::BucketType BucketType;
			typedef IntHashTable::ListType ListType;

			IntHashTable h;
		public:

			void hashCode(){
				// hashcode must be within range
				srand((unsigned int)time(NULL));
				for (int i = 0; i < 1000; i++){
					int n = rand();
					uint index = h.index(n);
					ASSERT_LT(index, h.size()) << "index(" << n << ") out of range";
					ASSERT_GE(index, 0u) << "index(" << n << ") out of range";
				}
			}

			void all(){
				srand((unsigned int)time(NULL));
				int logSize = h._logSize;
				int size = h._size;
				ASSERT_EQ(IntHashTable::INIT_LOGSIZE, logSize) << "initial logSize not " << IntHashTable::INIT_LOGSIZE;
				ASSERT_EQ(1 << logSize, h.size()) << "table size not 2^" << logSize;
				for (uint i = 0; i < h.size(); i++){
					ASSERT_EQ(0, (int)h.table[i]) << "table[i] not NULL for i=" << i;
				}

		{
			SCOPED_TRACE("add items in hashtable");
			// now add 10 items; should not trigger grow()
			ASSERT_LT(10 / h.size(), h.DENSITY_MAX) << "10/" << h.size() << " items triggered grow() while DENSITY_MAX=" << h.DENSITY_MAX;
			for (int i = 0; i < 10; i++){
				h.put(i, i);
			}
			// test contains()
			for (int i = 0; i < 10; i++){
				ASSERT_EQ(true, h.contains(i)) << "key " << i << " not found";
			}
			ASSERT_EQ(false, h.contains(100)) << "absent key 100 was found";
			// test get()
			for (int i = 0; i < 10; i++){
				int* pValue = h.get(i);
				ASSERT_NE(NULL, (int)pValue) << "pValue with key " << i << " NULL";
				ASSERT_EQ(i, *pValue) << "value with key " << i << " mismatch";
			}
			ASSERT_EQ(NULL, h.get(100)) << "absent key 100 was found";
			// test duplicate insert
			// should result in update
			h.put(5, -6);
			int* pValue = h.get(5);
			ASSERT_NE(NULL, (int)pValue) << "pValue with key " << 5 << " NULL";
			ASSERT_EQ(-6, *pValue) << "value with key " << 5 << " not -6";

			// now add some more but don't trigger grow()
			size = h.size();
			int maxCurrent = ((int)(h.size() * h.DENSITY_MAX)) - 1;
			int currentPop = h.population();
			for (int i = currentPop; i < maxCurrent; i++){
				// this insertion should not trigger grow()
				h.put(i, i);
			}
			ASSERT_EQ(maxCurrent, h.population()) << "population not maxCurrent";
			ASSERT_EQ(size, h.size()) << "size() not size";
			// this insertion should trigger grow()
			int key = rand();
			while (h.contains(key)){ key = rand(); }
			h.put(key, key); // should trigger grow()
			ASSERT_EQ(size * 2, h.size()) << "size() not 2*oldSize";
			ASSERT_EQ(maxCurrent + 1, h.population()) << "population() not maxCurrent+1";
			ASSERT_GE(0.375, h.density()) << "density() > 0.375";

			// print the table
			string str = h.toString();
			cout << "after grow(): " << endl << str << endl;

			// check that all old entries are still in the table
			for (int i = 0; i < 10; i++){ // first 10 entries
				int v = i;
				if (i == 5){
					// remember that we had updated an entry
					v = -6;
				}
				ASSERT_EQ(true, h.contains(i)) << "key " << i << " not found in new table";
				ASSERT_EQ(v, *h.get(i)) << "value with key " << i << " incorrect in new table";
			}
			for (int i = currentPop; i < maxCurrent; i++){ // further entries till max capacity before grow
				ASSERT_EQ(true, h.contains(i)) << "key " << i << " not found in new table";
				ASSERT_EQ(i, *h.get(i)) << "value with key " << i << " incorrect in new table";
			}
			// the entry that triggered grow()
			ASSERT_EQ(true, h.contains(key)) << "key " << key << " not found in new table";
			ASSERT_EQ(key, *h.get(key)) << " value with key " << key << " incorrect in new table";
		}

		{
			SCOPED_TRACE("remove");
			// now remove entries but do not trigger shrink()
			uint i = 0;
			BucketType pCriticalBucket = NULL;
			DoublyLinkedList<Pair> survivedKeys;
			int initPop = h.population();
			int numRemoved = 0;
			bool removedEnough = false;
			for (; i < h.size(); i++){
				BucketType pList = h.table[i];
				if (pList){
					// number of entries touched: either removed or copied
					int remainingItems = pList->size();

					while (remainingItems > 0){
						// check if we can remove this node without causing shrink()
						if (!removedEnough &&
							((float)(h._population - 1)) / h._size <= h.DENSITY_MIN){
							// this deletion will cause shrink()
							pCriticalBucket = pList;
							removedEnough = true;
						}
						else{
							Pair kvPair = (*pList->begin());
							int key = kvPair.key;
							if (removedEnough == false){
								// remove an entry
								int prevPop = h._population;
								int prevSize = h.size();
								h.remove(key);
								ASSERT_EQ(prevPop - 1, h._population) << "remove did not work";
								ASSERT_EQ(h._size, prevSize) << "size changed by remove";
								ASSERT_EQ(false, h.contains(key)) << "removed key " << key << " still remains";
								numRemoved++;
								remainingItems--;
							}
							else{
								// copy this should-be-surviving entry into a list for further verification
								survivedKeys.push(kvPair);
								remainingItems--;
							}
						}
					}
				}
			} // for loop through all slots

			ASSERT_EQ(initPop - numRemoved, survivedKeys.size()) << "initSize+numRemoved not survivedKeys.size";
			if (removedEnough) {
				// ok; removing next key should cause shrink()
				int prevPop = h._population;
				int prevSize = h.size();
				int removedKey = (*pCriticalBucket->begin()).key;
				h.remove(removedKey);
				cout << "shrinked: \n" << h.toString() << endl;
				ASSERT_EQ(h._population, prevPop - 1) << "remove did not work";
				ASSERT_EQ(h._size, prevSize >> 1) << "size did not shrink by half";
				ASSERT_EQ(false, h.contains(removedKey)) << "removed key " << removedKey << " still remains";

				// now check that all should-have-survived keys are still present in the new table
				for (DoublyLinkedList<Pair>::iterator it = survivedKeys.begin(); it != survivedKeys.end(); it++){
					int key = (*it).key;
					if (key == removedKey) continue; // this is the removed key that made the table shrink
					int value = (*it).value;
					ASSERT_EQ(true, h.contains(key)) << "key " << key << " absent in shrinked table";
					ASSERT_NE(NULL, (int)h.get(key)) << "get(" << key << ") is NULL in shrinked table";
					ASSERT_EQ(value, *(h.get(key))) << "get(" << key << ") not " << value << "in shrinked table";
				}

			}
		}


				//ASSERT_EQ(0, 1) << "incomplete test";
			}
		};

		ADD_TEST_F(SeparateChainingHashTableTest, hashCode);
		ADD_TEST_F(SeparateChainingHashTableTest, all);

	}
}