namespace BP
{
	//------------------------------------------------------------------------------------------------------------------------
	// void Add(const kStr &in key, const kStr &in value)
	// kStr Get(const kStr &in key)
	// bool TryGetValue(const kStr &in key, kStr &out value)
	// bool ContainsValue(const kStr &in value)
	// bool ContainsKey(const kStr &in key)
	// bool Remove(kStr &in key)
	// void Clear()
	// int Count
	//------------------------------------------------------------------------------------------------------------------------
	class DictionaryString : Dictionary
	{
		array<kStr> _Keys;
		array<kStr> _Values;
		//------------------------------------------------------------------------------------------------------------------------
		DictionaryString()
		{
			super();
		}
		//------------------------------------------------------------------------------------------------------------------------
		void Initialize(int capacity) override
		{
			Dictionary::Initialize(capacity);
			
			int prime = Math::GetPrime(capacity);
			_Keys.resize(prime);
			BP::Array::Clear(_Keys, 0, prime);
			_Values.resize(prime);
			BP::Array::Clear(_Values, 0, prime);
		}
		//------------------------------------------------------------------------------------------------------------------------
		kStr Get(const kStr &in key)
		{
			int index = FindIndex(key);
			if (index >= 0)
			{
				return _Values[index];
			}
			return "";
		}
		//------------------------------------------------------------------------------------------------------------------------
		bool ContainsValue(const kStr &in value)
		{
			for (int i = 0; i < _Count; i++)
			{
				if (_HashCodes[i] >= 0 && BP::String::Equals(_Values[i], value))
				{
					return true;
				}
			}
			return false;
		}
		//------------------------------------------------------------------------------------------------------------------------
		bool ContainsKey(const kStr &in key)
		{
			return FindIndex(key) >= 0;
		}
		//------------------------------------------------------------------------------------------------------------------------
		void Clear()
		{
			if (_Count <= 0)
			{
				return;
			}

			for (uint i = 0; i < _Buckets.length(); i++)
			{
				_Buckets[i] = -1;
			}

			BP::Array::Clear(_Keys, 0, _Count);
			BP::Array::Clear(_Values, 0, _Count);
			BP::Array::Clear(_HashCodes, 0, _Count);
			BP::Array::Clear(_Next, 0, _Count);

			_FreeList = -1;
			_Count = 0;
			_FreeCount = 0;
		}
		//------------------------------------------------------------------------------------------------------------------------
		void Add(const kStr &in key, const kStr &in value)
		{
			Insert(key, value, true);
		}
		//------------------------------------------------------------------------------------------------------------------------
		void Resize(int newSize, bool forceNewHashCodes)
		{
			array<int> bucketsCopy(newSize);
			for (uint i = 0; i < bucketsCopy.length(); i++)
			{
				bucketsCopy[i] = -1;
			}

			array<kStr> keysCopy(newSize);
			array<kStr> valuesCopy(newSize);
			array<int> hashCodesCopy(newSize);
			array<int> nextCopy(newSize);

			BP::Array::Copy(_Values, valuesCopy, _Count);
			BP::Array::Copy(_Keys, keysCopy, _Count);
			BP::Array::Copy(_HashCodes, hashCodesCopy, _Count);
			BP::Array::Copy(_Next, nextCopy, _Count);

			if (forceNewHashCodes)
			{
				for (int i = 0; i < _Count; i++)
				{
					if (hashCodesCopy[i] != -1)
					{
						hashCodesCopy[i] = int(keysCopy[i].Hash()) & 2147483647;
					}
				}
			}

			for (int i = 0; i < _Count; i++)
			{
				int index = hashCodesCopy[i] % newSize;
				nextCopy[i] = bucketsCopy[index];
				bucketsCopy[index] = i;
			}

			_Buckets = bucketsCopy;
			_Keys = keysCopy;
			_Values = valuesCopy;
			_HashCodes = hashCodesCopy;
			_Next = nextCopy;
		}
		//------------------------------------------------------------------------------------------------------------------------
		void Resize()
		{
			Resize(Math::ExpandPrime(_Count), false);
		}
		//------------------------------------------------------------------------------------------------------------------------
		bool Remove(kStr &in key)
		{
			int hash = int(key.Hash()) & 2147483647;
			int index = hash % int(_Buckets.length());
			int num = -1;
			for (int i = _Buckets[index]; i >= 0; i = _Next[i])
			{
				if (_HashCodes[i] == hash && BP::String::Equals(_Keys[i], key))
				{
					if (num < 0)
					{
						_Buckets[index] = _Next[i];
					}
					else
					{
						_Next[num] = _Next[i];
					}

					_HashCodes[i] = -1;
					_Next[i] = _FreeList;
					_Keys[i] = "";
					_Values[i] = "";
					_FreeList = i;
					_FreeCount++;
					return true;
				}
				num = i;
			}
			return false;
		}
		//------------------------------------------------------------------------------------------------------------------------
		void Insert(kStr &in key, const kStr &in value, bool add)
		{
			int hash = int(key.Hash()) & 2147483647;
			int index = hash % int(_Buckets.length());
			int num1 = 0;
			for (int i = _Buckets[index]; i >= 0; i = _Next[i])
			{
				if (_HashCodes[i] == hash && BP::String::Equals(_Keys[i], key))
				{
					_Values[i] = value;
					return;
				}
				num1++;
			}
			int num2;
			if (_FreeCount > 0)
			{
				num2 = _FreeList;
				_FreeList = _Next[num2];
				_FreeCount--;
			}
			else
			{
				if (_Count == int(_Keys.length()))
				{
					Resize();
					index = hash % int(_Buckets.length());
				}
				num2 = _Count;
				_Count++;
			}
			_HashCodes[num2] = hash;
			_Next[num2] = _Buckets[index];
			_Keys[num2] = key;
			_Values[num2] = value;
			_Buckets[index] = num2;
		}
		//------------------------------------------------------------------------------------------------------------------------
		int FindIndex(kStr &in key)
		{
			int hash = int(key.Hash()) & 2147483647;
			for (int i = _Buckets[hash % int(_Buckets.length())]; i >= 0; i = _Next[i])
			{
				if (_HashCodes[i] == hash && BP::String::Equals(_Keys[i], key))
				{
					return i;
				}
			}
			return -1;
		}
		//------------------------------------------------------------------------------------------------------------------------
		bool TryGetValue(const kStr &in key, kStr &out value)
		{
			int index = FindIndex(key);
			if (index >= 0)
			{
				value = _Values[index];
				return true;
			}
			value = "";
			return false;
		}
		//------------------------------------------------------------------------------------------------------------------------
	};
}
