ds.HopScotchHashTable.test.h

#pragma once

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

namespace yasi{
	namespace ds{
		////////// test HopScotchHashTable
		// inherit tests from base class, just redefine the types

		class HopScotchHashTableTest : public yasi::Test
			//	: public LinearProbingHashTableTestBase<
			//	HopScotchHashTable<int, Mod8Function<int> >,
			//	HopScotchHashTable<int, Mod16Function<int> >,
			//	HopScotchHashTable<int, Mod32Function<int> >
			//>
		{
			//
		protected:
			typedef HopScotchHashTable<int, Mod8Function<int> > IntHashTable8;
			typedef HopScotchHashTable<int, Mod16Function<int> > IntHashTable16;
			typedef IntHashTable16 IntHashTable; // default
			typedef HopScotchHashTable<int, Mod32Function<int> > IntHashTable32;
			typedef IntHashTable::BucketType BucketType;
			typedef IntHashTable::BucketEntryPtr BucketEntryPtr;
			typedef IntHashTable::Pair Pair;

		public:
			// inherit all public tests

			//void pushToRight(){
			//	IntHashTable h(3, 4); // size 8, H=4
			//	ASSERT_EQ(8, h.size()) << "size not 8";
			//	ASSERT_EQ(4, h.H) << "H not 4";
			//	for (int i = 0; i < h.size(); i++){
			//		ASSERT_EQ(0, h.table[i].key) << "key[" << i << "] not zero";
			//	}

			//	h.table[2] = BucketType(2, 2, 0);
			//	/// - - 2 - - - - -
			//	/// 0 1 2 3 4 5 6 7 

			//	bool ok;
			//	int b, k;
			//	{
			//		SCOPED_TRACE("no bumps");
			//		/// - - 2 - - - - -
			//		/// 0 1 2 3 4 5 6 7 
			//		ok = h.pushToRight(2); h.makeNull(2);
			//		/// - - - 2 - - - -
			//		/// 0 1 2 3 4 5 6 7 
			//		ASSERT_EQ(true, ok) << "push[2] failed";
			//		// [2] will be 2 because
			//		b = 2; k = 0; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 3; k = 2; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		// put it back
			//		/// - - 2 - - - - -
			//		/// 0 1 2 3 4 5 6 7 
			//		h.swap(2, 3);
			//		b = 2; k = 2; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 3; k = 0; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;

			//		h.table[3] = BucketType(3, 3, 0);
			//		h.table[4] = BucketType(4, 4, 0);
			//		h.table[5] = BucketType(5, 5, 0);
			//		/// - - 2 3 4 5 - -
			//		/// 0 1 2 3 4 5 6 7 
			//		ok = h.pushToRight(3); h.makeNull(3);
			//		/// - - 2 - 4 5 3 -
			//		/// 0 1 2 3 4 5 6 7 
			//		ASSERT_EQ(true, ok) << "push[3] failed";
			//		b = 3; k = 0; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 6; k = 3; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//	}
			//	{
			//		SCOPED_TRACE("one bump");
			//		h.table[7] = BucketType(7, 7, 0);
			//		/// - - 2 - 4 5 3 7
			//		/// 0 1 2 3 4 5 6 7 
			//		// cout << "before push(4)" << h;
			//		ok = h.pushToRight(4); h.makeNull(4);
			//		//cout << "after push(4)" << h;

			//		/// 7 - 2 - - 5 3 4
			//		/// 0 1 2 3 4 5 6 7 
			//		ASSERT_EQ(true, ok) << "push[4] failed";
			//		b = 4; k = 0; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 7; k = 4; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 0; k = 7; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//	}
			//	{
			//		SCOPED_TRACE("two bumps");
			//		h.table[1] = BucketType(6, 7, 0);
			//		h.table[3] = BucketType(1, 7, 0);
			//		b = 1; k = 6; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 3; k = 1; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		/// 7 6 2 1 - 5 3 4
			//		/// 0 1 2 3 4 5 6 7 
			//		ok = h.pushToRight(5);  h.makeNull(5);
			//		/// 5 6 7 1 2 - 3 4
			//		/// 0 1 2 3 4 5 6 7 
			//		ASSERT_EQ(true, ok) << "push[5] failed";
			//		b = 5; k = 0; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 0; k = 5; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 1; k = 6; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 2; k = 7; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 3; k = 1; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//		b = 4; k = 2; ASSERT_EQ(k, h.table[b].key) << "[" << b << "] not " << k;
			//	}
			//	{
			//		SCOPED_TRACE("no more space");
			//		h.table[5] = BucketType(17); // just fill the place with something
			//		/// 5 6 7 1 2 17 3 4
			//		/// 0 1 2 3 4 5  6 7 
			//		ok = h.pushToRight(1);
			//		ASSERT_EQ(false, ok) << "push[1] succeeded";

			//	}
			//}

			// tests whether it is ok to move emptySlot to cur for a given firstBucket
			// hash(cur) should lie between firstBucket and emptySlot, and
			// hash(cur) should be withing H-1 of emptySlot
			void canSwapCurWithEmpty(){
				IntHashTable h(4, 4); // size 16, H=4
				int f, c, hc, e;
				{
					string str = "non-circular. boundary involving f,c,e";
					SCOPED_TRACE(str);
					f = 4, c = 5, hc = 5, e = 4;

					// f == e
					f = e;
					ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
						<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";
					f = 4;

					// f == c
					c = f;
					ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
						<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

					// c < f
					c = f - 1;
					ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
						<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

					// c = e
					c = e;
					ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
						<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

					// c > e
					c = e + 1;
					ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
						<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";
				}
		{
			string str = "circular. boundary involving f,c,e";
			SCOPED_TRACE(str);
			f = 14, c = 14, hc = 15, e = 1;

			// f == c
			c = f;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// c < f
			c = f - 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// c == e
			c = e;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// c > e
			c = e + 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";
		}

		{
			string str = "non-circular. hash(cur) not in range";
			SCOPED_TRACE(str);
			f = 4, c = 5, e = 8;

			// hc < f
			hc = f - 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc == f
			hc = f;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc == e
			hc = e;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc > e
			hc = e + 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc < e - H
			hc = e - h.H - 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc == e - H
			hc = e - h.H;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

		}
		{
			string str = "circular. hash(cur) not in range";
			SCOPED_TRACE(str);
			f = 12, c = 2, e = 3;

			// hc < f
			hc = f - 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc == f
			hc = 4;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc == e
			hc = e;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc > e
			hc = e + 1;
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc < e - H
			hc = h.modSize(e - h.H - 1);
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// hc == e - H
			hc = h.modSize(e - h.H);
			ASSERT_EQ(false, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

		}
		{
			string str = "hash(cur) in range";
			SCOPED_TRACE(str);

			// non-circular
			f = 4, c = 8, e = 10;

			// hc > e-H
			hc = e - h.H + 1;
			ASSERT_EQ(true, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";

			// circular
			f = 11, c = 15, e = 2;

			// hc > e-H
			hc = h.modSize(e - h.H + 1);
			ASSERT_EQ(true, h.canSwapCurWithEmpty(f, c, hc, e))
				<< "canSwapCurWithEmpty(" << f << ", " << c << ", " << hc << ", " << e << ")";
		}

			}

			void pullFromLeft(){
				IntHashTable h(4, 4); // size 16, H=4
				ASSERT_EQ(16, h.size());
				ASSERT_EQ(0, h.population());
				ASSERT_EQ(4, h.H);

				int k, b, f;
				BucketType* p;

				// test scenarios:
				//	- empty slot is within H-1 of firstBucket
				//	- the replacement item j is found, which is within H-1 of firstBucket
				//	- the replacement item j is found, which is not within H-1 of firstBucket
				//	- the replacement item j could not be found within H-1 of emptySlot
				//	- above, circular
				{
					SCOPED_TRACE("case #1");
					h.insert(4, 4);
					h.insert(5, 5);
					h.insert(6, 6);
					ASSERT_EQ(3, h.population());

					// 20 is hashed in 4, should be placed in 7
					k = 20; b = 7;
					ASSERT_EQ(true, h.isNull(b));
					p = h.pullFromLeft(4, b);
					ASSERT_NE(NULL, (int)p);
					ASSERT_EQ(&h.table[b], p);
					h.table[b] = BucketType(k, k, 0);

					// circular
					h.clear();
					ASSERT_EQ(16, h.size());
					ASSERT_EQ(0, h.population());
					ASSERT_EQ(4, h.H);

					h.insert(14, 14);
					h.insert(15, 15);
					h.insert(31, 31); // hash value 15
					// 17 is hashed in 4, should be placed in 7
					k = 17; b = 1;
					ASSERT_EQ(true, h.isNull(b));
					p = h.pullFromLeft(14, b);
					ASSERT_NE(NULL, (int)p); // already within H
					ASSERT_EQ(&h.table[b], p);

				}
		{
			SCOPED_TRACE("the replacement item j is found, which is within H-1 of firstBucket");
			h.clear();
			ASSERT_EQ(16, h.size());
			ASSERT_EQ(0, h.population());
			ASSERT_EQ(4, h.H);

			h.table[3] = BucketType(3);
			h.table[4] = BucketType(4);
			h.table[5] = BucketType(21); // hash value = 6
			h.table[6] = BucketType(22); // hash value = 5
			h.table[7] = BucketType(19); // hash value = 3

			cout << "before pulling 8\n" << h;
			p = h.pullFromLeft(3, 8); // empty slot should go to 5
			cout << "after pulling 8\n" << h;
			ASSERT_EQ(&h.table[5], p);
			ASSERT_EQ(3, h.table[3].key);
			ASSERT_EQ(4, h.table[4].key);
			ASSERT_EQ(0, h.table[5].key);
			ASSERT_EQ(22, h.table[6].key);
			ASSERT_EQ(19, h.table[7].key);
			ASSERT_EQ(21, h.table[8].key);

			// now try a case where key hashes prohibit their move
			h.clear();
			h.table[3] = BucketType(3);
			h.table[4] = BucketType(4);
			h.table[5] = BucketType(18); // hash value = 2
			h.table[6] = BucketType(17); // hash value = 1
			h.table[7] = BucketType(21); // hash value = 5

			cout << "before pulling 8\n" << h;
			p = h.pullFromLeft(3, 8); // empty slot should go to 4
			cout << "after pulling 8\n" << h;
			ASSERT_EQ(&h.table[4], p);
			ASSERT_EQ(3, h.table[3].key);
			ASSERT_EQ(0, h.table[4].key);
			ASSERT_EQ(18, h.table[5].key);
			ASSERT_EQ(17, h.table[6].key);
			ASSERT_EQ(4, h.table[7].key);
			ASSERT_EQ(21, h.table[8].key);

			/// circular
			h.clear();
			cout << "after clear\n" << h;
			ASSERT_EQ(16, h.size());
			ASSERT_EQ(0, h.population());
			ASSERT_EQ(4, h.H);

			k = 14;  h.table[k] = BucketType(k);
			k = 15;  h.table[k] = BucketType(k);
			k = 0;  h.table[k] = BucketType(159); // hash value 15
			k = 1;  h.table[k] = BucketType(30); // hash value 14
			k = 2;  h.table[k] = BucketType(k);
			k = 3;  h.table[k] = BucketType(k);
			// for firstBucket 15, empty slot [4] should move to [2] 
			// because [1]'s hash value is 14
			b = 2; f = 15;
			cout << "before moving from [4]\n" << h;
			ASSERT_EQ(true, h.isNull(4));
			p = h.pullFromLeft(f, 4);
			cout << "after moving from [4]\n" << h;
			ASSERT_EQ(&h.table[2], p);
			ASSERT_EQ(14, h.table[14].key);
			ASSERT_EQ(15, h.table[15].key);
			ASSERT_EQ(159, h.table[0].key);
			ASSERT_EQ(30, h.table[1].key);
			ASSERT_EQ(true, h.isNull(2));
			ASSERT_EQ(3, h.table[3].key);
			ASSERT_EQ(2, h.table[4].key);
		}
		{
			SCOPED_TRACE("the replacement item j is found, which is NOT within H-1 of firstBucket");
			h.clear();
			ASSERT_EQ(16, h.size());
			ASSERT_EQ(0, h.population());
			ASSERT_EQ(4, h.H);

			h.table[0] = BucketType(31); // hash to 15
			h.table[1] = BucketType(1);
			h.table[2] = BucketType(17); // hash 1
			h.table[3] = BucketType(33); // hash 1
			for (int i = 4; i < 16; i++){
				h.table[i] = BucketType(i);
			}
			h.table[13] = BucketType(0);
			///  keys:  31 1 17 33 4 5 6 7 8 9 10 11 12 0  14 15
			///  index: 0  1 2  3  4 5 6 7 8 9 10 11 12 13 14 15
			cout << "before moving from [13]\n" << h;
			p = h.pullFromLeft(1, 13); // empty slot should go to 4
			cout << "after moving from [13]\n" << h;
			///  keys:  31 1 17 33 0  5 6 4  8 9 7  11 12 10 14 15
			///  index: 0  1 2  3  4  5 6 7  8 9 10 11 12 13 14 15
			for (int i = 1; i < 16; i++){
				if (i == 4)
					ASSERT_EQ(true, h.isNull(i));
				else if (i == 13)
					ASSERT_EQ(10, h.table[i].key);
				else if (i == 10)
					ASSERT_EQ(7, h.table[i].key);
				else if (i == 7)
					ASSERT_EQ(4, h.table[i].key);
				else if (i == 2)
					ASSERT_EQ(17, h.table[i].key);
				else if (i == 3)
					ASSERT_EQ(33, h.table[i].key);
				else
					ASSERT_EQ(i, h.table[i].key);
			}

			/// circular
			h.clear();
			f = 4;

			for (int i = 0; i < 16; i++) h.table[i] = BucketType(i);
			h.table[3].key = 0; // make [3] null
			h.table[0].key = 0; // make [0] null
			h.table[15].key = 17; // make [15].key hash to 1, cannot move
			h.table[13].key = 0; // make [13] null
			h.table[10].key = 25; // make [10].key hash to 25
			h.table[11].key = 0; // make [11] null
			h.table[9].key = 19; // make [9].key hash to 3, cannot move
			h.table[5].key = 2; // make [5].key hash to 2, cannot move

			///  keys:  0  1 2  0  4 2 6 7 8 19 25 0  12 0  14 17
			///  index: 0  1 2  3  4 5 6 7 8 9  10 11 12 13 14 15
			cout << "before moving from [3]\n" << h;
			p = h.pullFromLeft(4, 3); // empty slot should settle at [7]
			cout << "after moving from [3]\n" << h;
			///  keys:  0  14 2  1  4 2 6 0 8 19 7  0  25 0  12 17
			///  index: 0  1  2  3  4 5 6 7 8 9  10 11 12 13 14 15

			ASSERT_EQ(&h.table[7], p);
			ASSERT_EQ(1, h.table[3].key); // first swap with 1
			ASSERT_EQ(14, h.table[1].key); // then swap with 14
			ASSERT_EQ(12, h.table[14].key); // then swap with 12
			ASSERT_EQ(25, h.table[12].key); // then swap with 10
			ASSERT_EQ(7, h.table[10].key); // then swap with 7
			ASSERT_EQ(0, h.table[7].key); // 7 is now empty slot
		}
		{
			SCOPED_TRACE("the replacement item j could not be found within H-1 of emptySlot");
			h.clear();
			ASSERT_EQ(16, h.size());
			ASSERT_EQ(0, h.population());
			ASSERT_EQ(4, h.H);

			for (int i = 0; i < 15; i++){
				h.table[i] = BucketType(i * 16 + 2); // all hash to 2
			}

			p = h.pullFromLeft(3, 9); // should fail
			ASSERT_EQ(NULL, (int)p);
			p = h.pullFromLeft(8, 2); // should fail
			ASSERT_EQ(NULL, (int)p);
		}
			}

			void circularDiff(){
				IntHashTable8 h(3, 4);
				ASSERT_EQ(8, h.size());
				ASSERT_EQ(0, h.circularDiff(4, 4));
				ASSERT_EQ(1, h.circularDiff(4, 5));
				ASSERT_EQ(3, h.circularDiff(4, 7));
				ASSERT_EQ(4, h.circularDiff(4, 0));
				ASSERT_EQ(6, h.circularDiff(4, 2));
				ASSERT_EQ(7, h.circularDiff(4, 3));
			}

			void insertRemoveLookup(){
				IntHashTable h(4, 4); // size 16, H=4
				ASSERT_EQ(16, h.size());
				ASSERT_EQ(0, h.population());
				ASSERT_EQ(4, h.H);

				// try to find an empty key
				ASSERT_EQ(NULL, (int)h.lookupKey(7));
				ASSERT_EQ(NULL, (int)h.lookupKey(0));

				// insert one key, find it, and remove it
				h.put(5, 50);
				ASSERT_EQ(true, h.contains(5));
				ASSERT_EQ(5, h.lookupKey(5)->key);
				ASSERT_EQ(50, *h.get(5));
				ASSERT_EQ(1, h.population());
				ASSERT_EQ(16, h.size());
				h.remove(5);
				ASSERT_EQ(false, h.contains(5));
				ASSERT_EQ(NULL, (int)h.lookupKey(5));
				ASSERT_EQ(NULL, (int)h.get(5));
				ASSERT_EQ(0, h.population());
				ASSERT_EQ(16, h.size());

				// insert many keys that should not cause resize
				h.clear();
				ASSERT_EQ(16, h.size());
				int numItemsWithoutResize = h.maxPopulationWithoutGrow();
				for (int i = 0; i < numItemsWithoutResize; i++){
					h.insert(16 + i, 16 + i);
				}
				ASSERT_EQ(16, h.size());
				ASSERT_EQ(numItemsWithoutResize, h.population());

				// test remove
				ASSERT_EQ(true, h.contains(21));
				h.remove(21);
				ASSERT_EQ(false, h.contains(21));
				ASSERT_EQ(16, h.size());
				ASSERT_EQ(numItemsWithoutResize - 1, h.population());
				// put it back
				h.insert(21, 21);

				// now add one more item, should cause grow()
				h.insert(15, 15);
				ASSERT_EQ(true, h.contains(15));
				ASSERT_EQ(32, h.size());
				ASSERT_EQ(numItemsWithoutResize + 1, h.population());

				///////// test resizing when a bucket gets more than H items
				IntHashTable32 h2(4, 4); // keep the hash func mod 32 so that we can grow and rehash
				for (uint i = 0; i < h2.H; i++){
					h2.insert(16 * i + 2, i); // all hashed to 2
				}
				ASSERT_EQ(16, h2.size());
				ASSERT_EQ(h2.H, h2.population());
				// this insert should cause grow
				cout << "before inserting " << 16 * h2.H + 2 << endl << h2;
				h2.insert(16 * h2.H + 2, h2.H);
				cout << "after inserting " << 16 * h2.H + 2 << endl << h2;
				ASSERT_EQ(32, h2.size());
				ASSERT_EQ(h2.H + 1, h2.population());
			}
			void nextPosInBucket(){
				IntHashTable h(4, 4);
				int cur, bitmap, next;

				bitmap = 0xC0000000; cur = -1; next = -1;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = h.H; next = -1;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = h.H - 1; next = -1;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = 1; next = -1;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = 0; next = 1;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC8800000; cur = 4; next = -1; // cur >= H
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC8000000; cur = 1; next = 4;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000001; cur = 1; next = 31;
				ASSERT_EQ(next, h.nextPosInBucket(bitmap, cur))
					<< "next(" << cur << ") not " << next << " in bitmap " << std::bitset<32>(bitmap);
			}

			void prevPosInBucket(){
				IntHashTable h(4, 4);
				int cur, bitmap, prev;

				bitmap = 0xC0000000; cur = -1; prev = -1;
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = 0; prev = -1;
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = h.H; prev = -1;
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC0000000; cur = 1; prev = 0;
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xA0000000; cur = 2; prev = 0;
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xC8000000; cur = 4; prev = -1; // cur >= H
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);

				bitmap = 0xD8000000; cur = 3; prev = 1;
				ASSERT_EQ(prev, h.prevPosInBucket(bitmap, cur))
					<< "prev(" << cur << ") not " << prev << " in bitmap " << std::bitset<32>(bitmap);
			}

		};
		ADD_TEST_F(HopScotchHashTableTest, circularDiff);
		ADD_TEST_F(HopScotchHashTableTest, nextPosInBucket);
		ADD_TEST_F(HopScotchHashTableTest, prevPosInBucket);
		ADD_TEST_F(HopScotchHashTableTest, canSwapCurWithEmpty);
		ADD_TEST_F(HopScotchHashTableTest, pullFromLeft);
		ADD_TEST_F(HopScotchHashTableTest, insertRemoveLookup);
	}
}