#pragma once

#include "RE/G/GAllocator.h"
#include "RE/G/GFixedSizeHash.h"
#include "RE/G/GHashsetCachedEntry.h"
#include "RE/G/GMath.h"
#include "RE/G/GMemory.h"

namespace RE
{
	template <
		class C,
		class HashF = GFixedSizeHash<C>,
		class AltHashF = HashF,
		class Allocator = GAllocatorGH<C>,
		class Entry = GHashsetCachedEntry<C, HashF>>
	class GHashSetBase
	{
	public:
		using SelfType = GHashSetBase<C, HashF, AltHashF, Allocator, Entry>;

		struct const_iterator
		{
		public:
			const_iterator() :
				hash(nullptr),
				index(0)
			{}

			const C& operator*() const
			{
				assert(index >= 0 && index <= (SPInt)hash->table->sizeMask);
				return hash->E(index).value;
			}

			const C* operator->() const
			{
				assert(index >= 0 && index <= (SPInt)hash->table->sizeMask);
				return &hash->E(index).value;
			}

			void operator++()
			{
				if (index <= (SPInt)hash->table->sizeMask) {
					++index;
					while ((UPInt)index <= hash->table->sizeMask && hash->E(index).IsEmpty()) {
						++index;
					}
				}
			}

			bool operator==(const const_iterator& a_it) const
			{
				if (IsEnd() && a_it.IsEnd()) {
					return true;
				} else {
					return (hash == a_it.hash) && (index == a_it.index);
				}
			}

			bool operator!=(const const_iterator& a_it) const
			{
				return !(*this == a_it);
			}

			[[nodiscard]] bool IsEnd() const
			{
				return (!hash) || (!hash->table) || (index > (SPInt)hash->table->sizeMask);
			}

		protected:
			friend class GHashSetBase<C, HashF, AltHashF, Allocator, Entry>;

			const_iterator(const SelfType* a_hash, SPInt a_index) :
				hash(a_hash),
				index(a_index)
			{}

			const SelfType* hash;   // 00
			SPInt           index;  // 08
		};
		static_assert(sizeof(const_iterator) == 0x10);

		friend struct const_iterator;

		struct iterator : public const_iterator
		{
		public:
			iterator() :
				const_iterator(nullptr, 0)
			{}

			C& operator*() const
			{
				assert(const_iterator::index >= 0 && const_iterator::index <= (SPInt)const_iterator::hash->table->sizeMask);
				return const_cast<SelfType*>(const_iterator::hash)->E(const_iterator::index).value;
			}

			C* operator->() const
			{
				return &(operator*());
			}

			void Remove()
			{
				SelfType* theHash = const_cast<SelfType*>(const_iterator::hash);
				Entry*    ee = &theHash->E(const_iterator::index);
				const C&  key = ee->value;

				UPInt hashValue = AltHashF()(key);
				SPInt index = hashValue & hash->table->sizeMask;

				Entry* entry = &hash->E(index);

				if (entry->IsEmpty() || (entry->GetCachedHash(hash->table->sizeMask) != (UPInt)index)) {
					return;
				}

				SPInt naturalIndex = index;
				SPInt prevIndex = -1;

				while ((entry->GetCachedHash(hash->table->sizeMask) != (UPInt)naturalIndex) || !(entry->value == key)) {
					prevIndex = index;
					index = entry->nextInChain;
					if (index == -1) {
						return;
					}
					entry = &hash->E(index);
				}

				if (index == (SPInt)const_iterator::index) {
					if (naturalIndex == index) {
						if (!entry->IsEndOfChain()) {
							Entry* nextEntry = &hash->E(entry->nextInChain);
							entry->Clear();
							new (entry) Entry(*nextEntry);
							entry = nextEntry;
							--const_iterator::index;
						}
					} else {
						hash->E(prevIndex).nextInChain = entry->nextInChain;
					}

					entry->Clear();
					--(hash->table->entryCount);
				} else {
					assert(false);
				}
			}

		private:
			friend class GHashSetBase<C, HashF, AltHashF, Allocator, Entry>;

			using base = const_iterator;
			using base::hash;
			using base::index;

			iterator(SelfType* a_hash, SPInt a_idx) :
				const_iterator(a_hash, a_idx)
			{}
		};

		friend struct iterator;

		GHashSetBase() :
			table(nullptr)
		{}

		GHashSetBase(std::int32_t a_sizeHint) :
			table(0)
		{
			SetCapacity(this, a_sizeHint);
		}

		explicit GHashSetBase(void*) :
			table(0)
		{}

		GHashSetBase(void* a_memAddr, std::int32_t a_sizeHint) :
			table(0)
		{
			SetCapacity(a_memAddr, a_sizeHint);
		}

		GHashSetBase(const SelfType& a_src) :
			table(0)
		{
			Assign(this, a_src);
		}

		~GHashSetBase()
		{
			if (table) {
				// Delete the entries.
				for (UPInt i = 0, n = table->sizeMask; i <= n; i++) {
					Entry* entry = std::addressof(E(i));
					if (!entry->IsEmpty()) {
						entry->Free();
					}
				}

				Allocator::Free(table);
				table = nullptr;
			}
		}

		GFC_MEMORY_REDEFINE_NEW(GHashSetBase, Allocator::kStatID);

		void Assign(void* a_memAddr, const SelfType& a_src)
		{
			Clear();
			if (a_src.IsEmpty() == false) {
				SetCapacity(a_memAddr, a_src.GetSize());
				for (const_iterator it = a_src.begin(); it != a_src.end(); ++it) {
					Add(a_memAddr, *it);
				}
			}
		}

		void Clear()
		{
			if (table) {
				for (UPInt i = 0, n = table->sizeMask; i <= n; i++) {
					Entry* entry = std::addressof(E(i));
					if (!entry->IsEmpty()) {
						entry->Clear();
					}
				}

				Allocator::Free(table);
				table = nullptr;
			}
		}

		[[nodiscard]] bool IsEmpty() const
		{
			return !table || table->entryCount == 0;
		}

		template <class CRef>
		void Set(void* a_memAddr, const CRef& a_key)
		{
			UPInt hashValue = HashF()(a_key);
			SPInt index = static_cast<SPInt>(-1);

			if (table) {
				index = FindIndexCore(a_key, hashValue & table->sizeMask);
			}

			if (index >= 0) {
				E(index).value = a_key;
			} else {
				Add(a_memAddr, a_key, hashValue);
			}
		}

		template <class CRef>
		inline void Add(void* a_memAddr, const CRef& a_key)
		{
			const UPInt hashValue = HashF()(a_key);
			Add(a_memAddr, a_key, hashValue);
		}

		template <class K>
		void RemoveAlt(const K& a_key)
		{
			if (!table) {
				return;
			}

			const UPInt hashValue = AltHashF()(a_key);
			SPInt       index = hashValue & table->sizeMask;

			Entry* entry = std::addressof(E(index));

			if (entry->IsEmpty() || (entry->GetCachedHash(table->sizeMask) != (UPInt)index)) {
				return;
			}

			// Save index
			const SPInt naturalIndex = index;
			SPInt       prevIndex = -1;

			while ((entry->GetCachedHash(table->sizeMask) != (UPInt)naturalIndex) || !(entry->value == a_key)) {
				prevIndex = index;
				index = entry->nextInChain;
				if (index == -1) {
					return;
				}
				entry = std::addressof(E(index));
			}

			if (naturalIndex == index) {
				if (!entry->IsEndOfChain()) {
					Entry* nextEntry = std::addressof(E(entry->nextInChain));
					entry->Clear();
					new (entry) Entry(*nextEntry);
					entry = nextEntry;
				}
			} else {
				E(prevIndex).nextInChain = entry->nextInChain;
			}

			entry->Clear();
			--(table->entryCount);
		}

		template <class CRef>
		void Remove(const CRef& a_key)
		{
			RemoveAlt(a_key);
		}

		template <class K>
		C* Get(const K& a_key)
		{
			const SPInt index = FindIndex(a_key);
			if (index >= 0) {
				return std::addressof(E(index).value);
			} else {
				return 0;
			}
		}

		template <class K>
		const C* Get(const K& key) const
		{
			const SPInt index = FindIndex(key);
			if (index >= 0) {
				return std::addressof(E(index).value);
			} else {
				return 0;
			}
		}

		template <class K>
		C* GetAlt(const K& a_key)
		{
			const SPInt index = FindIndexAlt(a_key);
			if (index >= 0)
				return std::addressof(E(index).value);
			return nullptr;
		}

		template <class K>
		const C* GetAlt(const K& a_key) const
		{
			const SPInt index = FindIndexAlt(a_key);
			if (index >= 0) {
				return std::addressof(E(index).value);
			} else {
				return nullptr;
			}
		}

		template <class K>
		bool GetAlt(const K& a_key, C* a_val) const
		{
			const SPInt index = FindIndexAlt(a_key);
			if (index >= 0) {
				if (a_val) {
					*a_val = E(index).value;
				}
				return true;
			} else {
				return false;
			}
		}

		[[nodiscard]] UPInt GetSize() const
		{
			return table ? 0 : (UPInt)table->entryCount;
		}

		void CheckExpand(void* a_memAddr)
		{
			if (!table) {
				SetRawCapacity(a_memAddr, HashMinSize);
			} else if (table->entryCount * 5 > (table->sizeMask + 1) * 4) {
				SetRawCapacity(a_memAddr, (table->sizeMask + 1) * 2);
			}
		}

		void Resize(void* a_memAddr, UPInt a_count)
		{
			SetCapacity(a_memAddr, a_count);
		}

		void SetCapacity(void* a_memAddr, UPInt a_newSize)
		{
			UPInt newRawSize = (a_newSize * 5) / 4;
			if (newRawSize <= GetSize()) {
				return;
			}
			SetRawCapacity(a_memAddr, newRawSize);
		}

		iterator begin()
		{
			if (table == 0) {
				return iterator(0, 0);
			}

			UPInt idx = 0;
			while (idx <= table->sizeMask && E(idx).IsEmpty()) {
				++idx;
			}
			return iterator(this, idx);
		}

		iterator end()
		{
			return iterator(0, 0);
		}

		const_iterator begin() const
		{
			return const_cast<SelfType*>(this)->begin();
		}

		const_iterator end() const
		{
			return const_cast<SelfType*>(this)->end();
		}

		template <class K>
		iterator Find(const K& a_key)
		{
			SPInt index = FindIndex(a_key);
			if (index >= 0) {
				return iterator(this, index);
			}
			return iterator(0, 0);
		}

		template <class K>
		iterator FindAlt(const K& a_key)
		{
			SPInt index = FindIndexAlt(a_key);
			if (index >= 0) {
				return iterator(this, index);
			}
			return iterator(0, 0);
		}

		template <class K>
		const_iterator Find(const K& a_key) const
		{
			return const_cast<SelfType*>(this)->Find(a_key);
		}

		template <class K>
		const_iterator FindAlt(const K& a_key) const
		{
			return const_cast<SelfType*>(this)->FindAlt(a_key);
		}

	private:
		enum
		{
			HashMinSize = 8
		};

		struct TableType
		{
			UPInt entryCount;  // 00
			UPInt sizeMask;    // 08
							   //Entry	entries[0];	// 10
		};
		static_assert(sizeof(TableType) == 0x10);

		template <class K>
		SPInt FindIndex(const K& a_key) const
		{
			if (!table) {
				return -1;
			}
			UPInt hashValue = HashF()(a_key) & table->sizeMask;
			return FindIndexCore(a_key, hashValue);
		}

		template <class K>
		SPInt FindIndexAlt(const K& a_key) const
		{
			if (!table) {
				return -1;
			}
			const UPInt hashValue = AltHashF()(a_key) & table->sizeMask;
			return FindIndexCore(a_key, hashValue);
		}

		template <class K>
		SPInt FindIndexCore(const K& a_key, UPInt a_hashValue) const
		{
			assert(table);
			assert((a_hashValue & ~table->sizeMask) == 0);

			UPInt        index = a_hashValue;
			const Entry* entry = std::addressof(E(index));

			if (entry->IsEmpty() || (entry->GetCachedHash(table->sizeMask) != index)) {
				return -1;
			}

			for (;;) {
				assert(entry->GetCachedHash(table->sizeMask) == a_hashValue);
				if (entry->GetCachedHash(table->sizeMask) == a_hashValue && entry->value == a_key) {
					return index;
				}
				assert(!(entry->value == a_key));

				index = entry->nextInChain;
				if (index == (UPInt)-1) {
					break;
				}

				entry = std::addressof(E(index));
				assert(!entry->IsEmpty());
			}
			return -1;
		}

		template <class CRef>
		void Add(void* a_memAddr, const CRef& a_key, UPInt a_hashValue)
		{
			CheckExpand(a_memAddr);
			a_hashValue &= table->sizeMask;

			++(table->entryCount);

			const SPInt index = a_hashValue;
			Entry*      naturalEntry = &(E(index));

			if (naturalEntry->IsEmpty()) {
				new (naturalEntry) Entry(a_key, -1);
			} else {
				SPInt blankIndex = index;
				do {
					blankIndex = (blankIndex + 1) & table->sizeMask;
				} while (!E(blankIndex).IsEmpty());

				Entry* blankEntry = std::addressof(E(blankIndex));

				if (naturalEntry->GetCachedHash(table->sizeMask) == (UPInt)index) {
					new (blankEntry) Entry(*naturalEntry);
					naturalEntry->value = a_key;
					naturalEntry->nextInChain = blankIndex;
				} else {
					SPInt collidedIndex = naturalEntry->GetCachedHash(table->sizeMask);
					assert(collidedIndex >= 0 && collidedIndex <= (SPInt)table->sizeMask);
					for (;;) {
						Entry* entry = std::addressof(E(collidedIndex));
						if (entry->nextInChain == index) {
							new (blankEntry) Entry(*naturalEntry);
							entry->nextInChain = blankIndex;
							break;
						}
						collidedIndex = entry->nextInChain;
						assert(collidedIndex >= 0 && collidedIndex <= (SPInt)table->sizeMask);
					}

					naturalEntry->value = a_key;
					naturalEntry->nextInChain = -1;
				}
			}

			naturalEntry->SetCachedHash(a_hashValue);
		}

		Entry& E(UPInt a_index)
		{
			assert(a_index <= table->sizeMask);
			return *(((Entry*)(table + 1)) + a_index);
		}

		const Entry& E(UPInt a_index) const
		{
			assert(a_index <= table->sizeMask);
			return *(((Entry*)(table + 1)) + a_index);
		}

		void SetRawCapacity(void* a_heapAddr, UPInt a_newSize)
		{
			if (a_newSize == 0) {
				Clear();
				return;
			}

			if (a_newSize < HashMinSize) {
				a_newSize = HashMinSize;
			} else {
				const auto bits = gfchop(glog2f((float)(a_newSize - 1)) + 1);
				a_newSize = UPInt(1) << bits;
			}

			SelfType newHash;
			newHash.table = static_cast<TableType*>(Allocator::Alloc(a_heapAddr, sizeof(TableType) + sizeof(Entry) * a_newSize));
			assert(newHash.table);

			newHash.table->entryCount = 0;
			newHash.table->sizeMask = a_newSize - 1;
			UPInt i;
			UPInt n;

			for (i = 0; i < a_newSize; i++) {
				newHash.E(i).nextInChain = -2;
			}

			if (table) {
				for (i = 0, n = table->sizeMask; i <= n; ++i) {
					Entry* entry = std::addressof(E(i));
					if (entry->IsEmpty() == false) {
						newHash.Add(a_heapAddr, entry->value);
						entry->Clear();
					}
				}
				Allocator::Free(table);
			}

			// Steal newHash's data.
			table = newHash.table;
			newHash.table = nullptr;
		}

		// members
		TableType* table;  // 00
	};
	// size == 0x8
}
