ds.LinearProbingHashTable.test.h

#pragma once

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

namespace yasi{
	namespace ds{
		///////////////////////// testing ////////////////////////

		typedef LinearProbingHashTable<int, int, Mod8Function<int>	> _LinProbHT8;
		typedef LinearProbingHashTable<int, int, Mod16Function<int>	> _LinProbHT16;
		typedef LinearProbingHashTable<int, int, Mod32Function<int>	> _LinProbHT32;

		template<
			class IntHashTable8 = _LinProbHT8,
			class IntHashTable16 = _LinProbHT16,
			class IntHashTable32 = _LinProbHT32
		>
		class LinearProbingHashTableTestBase : public yasi::Test{
		protected:
			//typedef LinearProbingHashTable<int, int, Mod8Function<int> > IntHashTable8;
			//typedef LinearProbingHashTable<int, int, Mod16Function<int> > IntHashTable16;
			//typedef LinearProbingHashTable<int, int, Mod32Function<int> > IntHashTable32;
			typedef IntHashTable16 IntHashTable; // default
			typedef typename IntHashTable::BucketType BucketType;
			typedef typename IntHashTable::BucketEntryPtr BucketEntryPtr;
			typedef typename IntHashTable::Pair Pair;


		public:

			virtual void insert(){

				IntHashTable h(4);
				ASSERT_EQ(16, h.size()) << "size not 16";
				ASSERT_EQ(0, h.population()) << "pop not 0";

				{
					SCOPED_TRACE("insert 4-5-6");
					h.insert(4, 4);
					h.insert(5, 5);
					h.insert(6, 6);
					//// - - - - 4 5 6 - - - -  -  -  -  -  -
					//// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
					cout << h;
					ASSERT_EQ(3, h.population()) << "pop not 3";
				}
		{
			string str = "insert 20, which should go to bucket 7";
			int key = 20;
			int bucket = 7;
			SCOPED_TRACE(str);
			BucketEntryPtr p = h.insertKey(key);
			p->value = key; // assign the value
			cout << str << endl << h;
			ASSERT_NE(true, h.isNull(bucket)) << "bucket " << bucket << " NULL";
			ASSERT_EQ(p, h.entryptr(bucket)) << key << " not in bucket  " << bucket;
			ASSERT_EQ(key, h.key(bucket)) << key << " not in bucket  " << bucket;
		}
		{
			string str = "insert 23, which should go to bucket 8";
			int key = 23;
			int bucket = 8;
			SCOPED_TRACE(str);
			BucketEntryPtr p = h.insertKey(key);
			p->value = key; // assign the value
			cout << str << endl << h;
			ASSERT_NE(true, h.isNull(bucket)) << "bucket " << bucket << " NULL";
			ASSERT_EQ(p, h.entryptr(bucket)) << key << " not in bucket  " << bucket;
			ASSERT_EQ(key, h.key(bucket)) << key << " not in bucket  " << bucket;
		}
		{
			string str = "insert 20, which is already in bucket 7";
			SCOPED_TRACE(str);
			int key = 20;
			int bucket = 7;
			SCOPED_TRACE(str);
			BucketEntryPtr p = h.insertKey(key);
			cout << str << endl << h;
			ASSERT_NE(true, h.isNull(bucket)) << "bucket " << bucket << " NULL";
			ASSERT_EQ(p, h.entryptr(bucket)) << key << " not in bucket  " << bucket;
			ASSERT_EQ(key, h.key(bucket)) << key << " not in bucket  " << bucket;
			ASSERT_EQ(key, h.value(bucket)) << key << " not in bucket  " << bucket;
		}
		{
			h.insert(13, 13);
			h.insert(14, 14);
			h.insert(15, 15);
			// 
			string str = "search round the table; now insert 16, should go to bucket 0";
			int key = 16;
			int bucket = 0;
			SCOPED_TRACE(str);
			BucketEntryPtr p = h.insertKey(key);
			p->value = key; // assign the value
			cout << str << endl << h;
			ASSERT_NE(true, h.isNull(bucket)) << "bucket " << bucket << " NULL";
			ASSERT_EQ(p, h.entryptr(bucket)) << key << " not in bucket  " << bucket;
			ASSERT_EQ(key, h.key(bucket)) << key << " not in bucket  " << bucket;

		}
		{
			string str = "search round the table; now insert 29, should go to bucket 1";
			int key = 29;
			int bucket = 1;
			SCOPED_TRACE(str);
			BucketEntryPtr p = h.insertKey(key);
			p->value = key; // assign the value
			cout << str << endl << h;
			ASSERT_NE(true, h.isNull(bucket)) << "bucket " << bucket << " NULL";
			ASSERT_EQ(p, h.entryptr(bucket)) << key << " not in bucket  " << bucket;
			ASSERT_EQ(key, h.key(bucket)) << key << " not in bucket  " << bucket;

		}
		{
			string str = "insert 0; should go to the zero element";
			int key = 0;
			SCOPED_TRACE(str);
			ASSERT_EQ(false, h._zeroUsed) << "_zeroUsed true";
			int prevPop = h.population();
			BucketEntryPtr p = h.insertKey(key);
			p->value = 100; // assign the value
			cout << str << endl << h;
			ASSERT_EQ(true, h._zeroUsed) << "_zeroUsed false";
			ASSERT_EQ(p, &h._zeroKeyEntry) << " zero key not in zeroPair";
			ASSERT_EQ(prevPop + 1, h.population()) << "population did not increase";
			ASSERT_EQ(key, h._zeroKeyEntry.key) << key << " not in zeroPair";
		}

			}

			virtual void copyTable(){

				IntHashTable16 h1(4);
				IntHashTable32 h2(5);

				ASSERT_EQ(16, h1.size()) << "h1 size not 16";
				ASSERT_EQ(0, h1.population()) << "h1 pop not 0";
				ASSERT_EQ(32, h2.size()) << "h2 size not 32";
				ASSERT_EQ(0, h2.population()) << "h2 pop not 0";

				int h1MaxItemsWithoutGrow = (int)(h1.size() * h1.DENSITY_MAX) - 1;
				// add some items to h1 without triggering grow()
				int* pKeys = new int[h1MaxItemsWithoutGrow];
				srand((unsigned int)time(NULL));
				for (int i = 0; i < h1MaxItemsWithoutGrow; i++){
					pKeys[i] = rand();
					h1.insert(pKeys[i], pKeys[i]);
				}
				ASSERT_EQ(16, h1.size()) << "h1 size not 16";
				ASSERT_EQ(h1MaxItemsWithoutGrow, h1.population()) << "h1 pop not " << h1MaxItemsWithoutGrow;

				// now copy items from h1 to h2
				h2.copyTable(h1.table, h1.size());

				// check that all items exist
				// items are rehashed mod 32
				for (uint i = 0; i < h1._size; i++){
					if (!h1.isNull(i)){
						int key = h1.key(i);
						int value = h1.value(i);
						BucketEntryPtr p = h2.lookupKey(key);
						ASSERT_NE(0, (int)p) << "key " << key << " not found in h2";
						ASSERT_EQ(key, p->key) << "key " << key << " mismatch in h2 key " << p->key;
						ASSERT_EQ(value, p->value) << "value " << value << " mismatch in h2 key " << p->key << "value: " << p->value;
					}
				}

				DELETE_ARR_SAFE(pKeys);
			}

			virtual void remove(){

				IntHashTable h(4);
				ASSERT_EQ(16, h.size()) << "size not 16";
				ASSERT_EQ(0, h.population()) << "pop not 0";

				{
					SCOPED_TRACE("insert 4-5-6-7");
					h.insert(4, 4);
					h.insert(5, 5);
					h.insert(6, 6);
					h.insert(7, 7);
					// add 12, and three more that map into 14
					h.insert(12, 12);
					h.insert(14, 14);
					h.insert(30, 30);
					h.insert(46, 46);
					//// 46 - - - 4 5 6 7 - - -  -  12  - 14 30
					//// 0  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
					cout << h;
					ASSERT_EQ(16, h.size()) << "size not 16";
					ASSERT_EQ(8, h.population()) << "population not 8";

				}
		{
			SCOPED_TRACE("remove 4");
			h.remove(4);
			//// 46 - - - - 5 6 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
			cout << h;
			ASSERT_EQ(16, h.size()) << "size not 16";
			ASSERT_EQ(NULL, (int)h.lookupKey(4)) << "key " << 4 << " not NULL";
			ASSERT_EQ(5, h.key(5)) << "[5] not " << 5;
			ASSERT_EQ(6, h.key(6)) << "[6] not " << 6;
			ASSERT_EQ(7, h.key(7)) << "[7] not " << 7;
			ASSERT_EQ(7, h.population()) << "population not 7";
		}
		{
			SCOPED_TRACE("remove 6");
			cout << "before removing 6\n" << h;
			h.remove(6);
			//// 46 - - - - 5 - 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
			ASSERT_EQ(16, h.size()) << "size not 16";
			ASSERT_EQ(6, h.population()) << "population not 6";
			cout << "after removing 6\n" << h;
			ASSERT_EQ(NULL, (int)h.lookupKey(6)) << "key " << 6 << " not NULL";
			ASSERT_EQ(5, h.key(5)) << "key " << 5 << " misplaced";
			ASSERT_EQ(7, h.key(7)) << "key " << 7 << " misplaced";
		}
		{
			SCOPED_TRACE("remove simple 2-item bucket");
			h.insert(85, 85);
			//// 46 - - - - 5 85 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5 6  7 8 9 10 11 12 13 14 15
			ASSERT_EQ(7, h.population()) << "population not 7";
			ASSERT_EQ(85, h.key(6)) << "[6] not 85";
			ASSERT_EQ(16, h.size()) << "size not 16";
			h.remove(5);
			//// 46 - - - - 85 - 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5  6 7 8 9 10 11 12 13 14 15
			ASSERT_EQ(NULL, (int)h.lookupKey(5)) << "key " << 5 << " not NULL";
			ASSERT_EQ(85, h.key(5)) << "key " << 85 << " misplaced";
			ASSERT_EQ(true, h.isNull(6)) << "[6] not NULL";
			ASSERT_EQ(7, h.key(7)) << "key " << 7 << " misplaced";

			// put 5 back
			h.insert(5, 5);
			//// 46 - - - - 85 5 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5  6 7 8 9 10 11 12 13 14 15
			ASSERT_EQ(5, h.key(6)) << "key " << 5 << " misplaced";

			// delete 5
			h.remove(5);
			//// 46 - - - - 85 - 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5  6 7 8 9 10 11 12 13 14 15
			ASSERT_EQ(16, h.size()) << "size not 16";
			ASSERT_EQ(NULL, (int)h.lookupKey(5)) << "key " << 5 << " not NULL";
			ASSERT_EQ(85, h.key(5)) << "key " << 85 << " misplaced";
			ASSERT_EQ(true, h.isNull(6)) << "[6) not NULL";
			ASSERT_EQ(7, h.key(7)) << "key " << 7 << " misplaced";

			// for consistency later on, replace 85 with 5
			h.remove(85);
			h.insert(5, 5);
			//// 46 - - - - 5 - 7 - - -  -  12 -  14 30
			//// 0  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
			ASSERT_EQ(16, h.size()) << "size not 16";
			ASSERT_EQ(5, h.key(5)) << "[5] not 5";
			ASSERT_EQ(true, h.isNull(6)) << "[6] not NULL";
			ASSERT_EQ(7, h.key(7)) << "key " << 7 << " misplaced";
		}

				// add several entries that map into bucket 5
				h.insert(21, 21);
				h.insert(37, 37);
				h.insert(53, 53);
				//// 46 - - - - 5 21 7 37 53 -  -  12  - 14 30
				//// 0  1 2 3 4 5 6  7 8  9  10 11 12 13 14 15

				// add several entries that map into bucket 7
				h.insert(23, 23);
				h.insert(39, 39);
				//// 46 - - - - 5 21 7 37 53 23 39 12 -  14 30
				//// 0  1 2 3 4 5 6  7 8  9  10 11 12 13 14 15

				{
					SCOPED_TRACE("remove key from multi-item bucket");

					{
						SCOPED_TRACE("remove 5");
						//// 46 - - - - 5 21 7 37 53 23 39 12 -  14 30
						//// 0  1 2 3 4 5 6  7 8  9  10 11 12 13 14 15
						// delete 5
						cout << "before removing 5:\n" << h << endl;
						h.remove(5);
						//// 46 - - - - 21 37 7 53 23 39 -  12 -  14 30
						//// 0  1 2 3 4 5  6  7 8  9  10 11 12 13 14 15
						cout << "after removing 5:\n" << h << endl;
						ASSERT_EQ(16, h.size()) << "size not 16";
						ASSERT_EQ(NULL, (int)h.lookupKey(5)) << "key " << 5 << " not NULL";
						ASSERT_EQ(21, h.key(5)) << "[5] not 21";
						ASSERT_EQ(37, h.key(6)) << "[6] not 37";
						ASSERT_EQ(7, h.key(7)) << "[7] not 7";
						ASSERT_EQ(53, h.key(8)) << "[8] not 53";
						ASSERT_EQ(23, h.key(9)) << "[9] not 23";
						ASSERT_EQ(39, h.key(10)) << "[10] not 39";
						ASSERT_EQ(true, h.isNull(11)) << "[11] not NULL";
						ASSERT_EQ(12, h.key(12)) << "[12] not 12";
						ASSERT_EQ(true, h.isNull(13)) << "[13] not NULL";
						ASSERT_EQ(14, h.key(14)) << "[14] not 14";
					}
			{
				SCOPED_TRACE("remove 21");
				//delete 21
				h.remove(21);
				//// 46 - - - - 37 53 7 23 39 -  -  12 -  14 30
				//// 0  1 2 3 4 5  6  7 8  9  10 11 12 13 14 15
				ASSERT_EQ(16, h.size()) << "size not 16";
				ASSERT_EQ(NULL, (int)h.lookupKey(21)) << "key " << 21 << " not NULL";
				ASSERT_EQ(37, h.key(5)) << "[5] not 37";
				ASSERT_EQ(53, h.key(6)) << "[6] not 53";
				ASSERT_EQ(7, h.key(7)) << "[7] not 7";
				ASSERT_EQ(23, h.key(8)) << "[8] not 23";
				ASSERT_EQ(39, h.key(9)) << "[9] not 39";
				ASSERT_EQ(true, h.isNull(10)) << "[10] not NULL";
				ASSERT_EQ(true, h.isNull(11)) << "[11] not NULL";
				ASSERT_EQ(12, h.key(12)) << "[12] not 12";
				ASSERT_EQ(true, h.isNull(13)) << "[13] not NULL";
				ASSERT_EQ(14, h.key(14)) << "[14] not 14";
			}

			{
				SCOPED_TRACE("remove 23");
				//delete 23
				h.remove(23);
				//// 46 - - - - 37 53 7 39 -  -  -  12 -  14 30
				//// 0  1 2 3 4 5  6  7 8  9  10 11 12 13 14 15
				ASSERT_EQ(16, h.size()) << "size not 16";
				ASSERT_EQ(NULL, (int)h.lookupKey(23)) << "key " << 23 << " not NULL";
				ASSERT_EQ(37, h.key(5)) << "[5] not 37";
				ASSERT_EQ(53, h.key(6)) << "[6] not 53";
				ASSERT_EQ(7, h.key(7)) << "[7] not 7";
				ASSERT_EQ(39, h.key(8)) << "[8] not 39";
				ASSERT_EQ(true, h.isNull(9)) << "[9] not NULL";
				ASSERT_EQ(true, h.isNull(10)) << "[10] not NULL";
				ASSERT_EQ(true, h.isNull(11)) << "[11] not NULL";
				ASSERT_EQ(12, h.key(12)) << "[12] not 12";
				ASSERT_EQ(true, h.isNull(13)) << "[13] not NULL";
				ASSERT_EQ(14, h.key(14)) << "[14] not 14";
			}
					h.insert(62, 62);
					h.insert(17, 17);
					//// 46 62 17 - - 37 53 39 - -  -  -  12 -  14 30
					//// 0  1  2  3 4 5  6  7  8 9  10 11 12 13 14 15
					ASSERT_EQ(62, h.key(1)) << "[1] not 62";

					{
						SCOPED_TRACE("remove 46");
						//delete 46
						cout << "before removing 46:\n" << h << endl;
						h.remove(46);
						//// 62 17 - - - 37 53 39 - -  -  -  12 -  14 30
						//// 0  1 2 3 4 5  6  7  8 9  10 11 12 13 14 15
						cout << "after removing 46:\n" << h << endl;
						ASSERT_EQ(16, h.size()) << "size not 16";
						ASSERT_EQ(NULL, (int)h.lookupKey(46)) << "key " << 46 << " not NULL";
						ASSERT_EQ(62, h.key(0)) << "[0] not 62";
						ASSERT_EQ(17, h.key(1)) << "[1] not 17";
						ASSERT_EQ(true, h.isNull(2)) << "[2] not NULL";
						ASSERT_EQ(14, h.key(14)) << "[14] not 14";
						ASSERT_EQ(30, h.key(15)) << "[15] not 30";
					}

			{
				SCOPED_TRACE("remove 30");
				//delete 30
				h.remove(30);
				//// - 17 - - - 37 53 39 - -  -  -  12 -  14 62
				//// 0 1  2 3 4 5  6  7  8 9  10 11 12 13 14 15
				ASSERT_EQ(16, h.size()) << "size not 16";
				ASSERT_EQ(NULL, (int)h.lookupKey(30)) << "key " << 30 << " not NULL";
				ASSERT_EQ(17, h.key(1)) << "[1] not 17";
				ASSERT_EQ(true, h.isNull(0)) << "[0] not NULL";
				ASSERT_EQ(14, h.key(14)) << "[14] not 14";
				ASSERT_EQ(62, h.key(15)) << "[15] not 62";
			}
			{
				SCOPED_TRACE("remove 14");
				//delete 14
				h.remove(14);
				//// - - - - - 37 53 39 - -  -  -  12 -  62 -
				//// 0 1 2 3 4 5  6  7  8 9  10 11 12 13 14 15
				ASSERT_EQ(16, h.size()) << "size not 16";
				ASSERT_EQ(NULL, (int)h.lookupKey(14)) << "key " << 14 << " not NULL";
				ASSERT_EQ(62, h.key(14)) << "[14] not 62";
				ASSERT_EQ(true, h.isNull(15)) << "[15] not NULL";
			}

				}
				{
					SCOPED_TRACE("Zero key");
					ASSERT_EQ(false, h._zeroUsed) << "_zeroUsed true";
					h.insert(0, 5);
					ASSERT_EQ(true, h._zeroUsed) << "_zeroUsed false";
					ASSERT_EQ(0, h._zeroKeyEntry.key) << "key of zero element non-zero";
					ASSERT_EQ(5, h._zeroKeyEntry.value) << "key of zero element non-zero";

					// now delete 0
					h.remove(0);
					ASSERT_EQ(false, h._zeroUsed) << "_zeroUsed true";
					ASSERT_EQ(0, h._zeroKeyEntry.key) << "key of zero element non-zero";
				}
			{
				SCOPED_TRACE("remove from an all-filled table");
				// create a pathological table
				BucketType* badTable = h.allocTable(8); // 8 entries in the table
				for (int i = 0; i < 8; i++){
					badTable[i] = Pair(5, i); // all keys are 5
				}
				IntHashTable8 h2(3); // 8 elements to begin
				h2.forceTable(badTable, 3, 8, h2.hash); // make the table full
				ASSERT_EQ(8, h2.size()) << "size not 8";
				ASSERT_EQ(8, h2.population()) << "population not 8";
				ASSERT_EQ(8, h2.hash.modulus) << "has mod not 8";

				{
					SCOPED_TRACE("delete from index 5");
					cout << "before removing 5:\n" << h2;
					h2.remove(5);
					cout << "after removing 5:\n" << h2;

					ASSERT_EQ(7, h2.population()) << "population not 7";
					for (int i = 0; i < 8; i++){
						if (i == 4){
							ASSERT_EQ(true, h2.isNull(i)) << "[" << i << "] not NULL";
						}
						else
							ASSERT_EQ(5, h2.key(i)) << "[" << i << "] not 5";
					}
				}

				// cleanup
			}

			}

			virtual void growCondition(){
				IntHashTable16 h1(4);

				int i = 0;
				{
					SCOPED_TRACE("grow");
					ASSERT_EQ(16, h1.size()) << "h1 size not 16";
					ASSERT_EQ(0, h1.population()) << "h1 pop not " << 0;
					int popLimit = h1.maxPopulationWithoutGrow();
					for (; i < popLimit; i++){
						h1.insert(i, i);
					}
					ASSERT_EQ(16, h1.size()) << "h1 size not 16";
					ASSERT_EQ(popLimit, h1.population()) << "h1 pop not " << popLimit;
					cout << h1;
					// this should trigger grow
					h1.insert(i, i);
					i++;
					ASSERT_EQ(32, h1.size()) << "h1 size not 32";
					ASSERT_EQ(popLimit + 1, h1.population()) << "h1 pop not " << popLimit + 1;
				}
			}
			virtual void shrinkCondition(){
				IntHashTable16 h1(4);

				int i = 0;
				{
					SCOPED_TRACE("shrink");
					// put as many items as we can without invoking grow()
					int popLimit = h1.maxPopulationWithoutGrow();
					for (; i < popLimit; i++){
						h1.insert(i, i);
					}
					ASSERT_EQ(16, h1.size()) << "h1 size not 16";
					ASSERT_EQ(popLimit, h1.population()) << "h1 pop not " << popLimit;

					popLimit = h1.minPopulationWithoutShrink();
					int removeCount = h1._population - popLimit;
					int j = 0;
					for (; j < removeCount; j++){
						h1.remove(j);
					}
					ASSERT_EQ(16, h1.size()) << "h1 size not 16";
					ASSERT_EQ(popLimit, h1.population()) << "h1 pop not " << popLimit;
					// next remove should trigger shrink
					ASSERT_EQ(true, h1.needShrink(h1.population() - 1));
					h1.remove(j); // shrink should not be automatic
					ASSERT_EQ(16, h1.size()) << "h1 size not " << 16;
					j--;
					// force shrink
					h1.shrink();
					ASSERT_EQ(8, h1.size()) << "h1 size not " << 8;
					ASSERT_EQ(popLimit - 1, h1.population()) << "h1 pop not " << popLimit - 1;
				}
			}

			virtual void isKeyZero(){
				//struct MyStruct{
				//	int a;
				//	float b;
				//	char c;
				//	bool operator==(const MyStruct& other) const { return a == other.a && b == other.b && c == other.c; }
				//	bool operator!=(const MyStruct& other) const { return !(*this == other); }
				//	bool operator<(const MyStruct& other) const { return a < other.a && b < other.b && c < other.c; }
				//	bool operator<=(const MyStruct& other) const { return a <= other.a && b <= other.b && c <= other.c; }
				//};
				//struct MyHashFunction{
				//public:
				//	virtual int operator()(const MyStruct& n)const{ return n.a + (int)n.b + (int)n.c; }
				//};
				//
				//// create a hashtable with MyStruct as Key
				//LinearProbingHashTable<MyStruct,MyStruct,KVPair<MyStruct>,MyHashFunction> h(1);

				IntHashTable h;
				IntHashTable* pH = new IntHashTable();
				delete pH;

				//h.insert(4, 4);
				//h.insert(5, 5);
				//h.insert(6, 6);

				//// now test
				//ASSERT_EQ(false, h.isNull(4)) << "4 zero";
				//ASSERT_EQ(false, h.isNull(5)) << "5 zero";
				//ASSERT_EQ(false, h.isNull(6)) << "6 zero";
				//ASSERT_EQ(true, h.isNull(3)) << "3 not zero";
				//ASSERT_EQ(true, h.isNull(0)) << "0 not zero";
				//
				//h.setKeyZero(h.keyptr(4));
				//ASSERT_EQ(true, h.isNull(4)) << "4 not null";
				//h.makeNull(5);
				//ASSERT_EQ(true, h.isNull(5)) << "5 not null";
				//*h.keyptr(6) = 0;
				//ASSERT_EQ(true, h.isNull(6)) << "6 not null";
				//h.entryptr(2)->key = 2;
				//ASSERT_EQ(2, h.key(2)) << "[2] not 2";
				//h.removeEntry(2);
				//ASSERT_EQ(true, h.isNull(2)) << "[2] not NULL";
				//h.makeEntry(4, 44);
				//ASSERT_EQ(44, h.key(4)) << "[4] not 44";


				{
					class A{
					public:
						virtual void x() = 0;
					};

					class BB :public A{
					public:
						int key;
						int value;
						void x() override {}
					};

					//typedef BB B;
					//typedef KVPairSimple<int> B;
					typedef KVPair<int> B;
					int n = 1;
					int s = sizeof(B);
					B* pArr = (B*)malloc(n * s);
					//B* pArr = new B[n];
					memset(pArr, 0, s * n);
					//std::fill((char*)pArr, (char*)(pArr+n), 0);
					//for (int i = 0; i < n; i++){
					//	pArr[i].key = 0xAAAAAAAA;
					//	pArr[i].value = 0xBBBBBBBB;
					//}
					//delete[] pArr;
					free(pArr);
				}

				//ASSERT_EQ(0, 1) << "uncomment other tests";
			}
		};

		class LinearProbingHashTableTest : public LinearProbingHashTableTestBase < _LinProbHT8, _LinProbHT16, _LinProbHT32> {
		public:
			// inherit all tests from base
		};

		ADD_TEST_F(LinearProbingHashTableTest, insert);
		ADD_TEST_F(LinearProbingHashTableTest, copyTable);
		ADD_TEST_F(LinearProbingHashTableTest, growCondition);
		ADD_TEST_F(LinearProbingHashTableTest, shrinkCondition);
		ADD_TEST_F(LinearProbingHashTableTest, isKeyZero);
		ADD_TEST_F(LinearProbingHashTableTest, remove);
	}
}