/*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at https://mozilla.org/MPL/2.0/.
*/

#pragma once

#include <vector>
#include <map>
#include <utility>
#include <type_traits>

namespace OpenVulkano
{
	template<typename K, typename V, template<typename, typename> class Pair = std::pair,
	         template<typename...> class Vec = std::vector, typename = std::enable_if_t<std::is_integral<K>::value>>
	class BinSearchArrayMap
	{
	public:
		void Insert(K key, const V& value)
		{
			// Check if the key is bigger than the last element
			if (m_data.empty() || key > m_data.back().first)
			{
				m_data.emplace_back(key, value);
				return;
			}

			throw std::runtime_error("Key cannot be lesser than the last used key.");
		}

		template<typename... Args> void Emplace(K key, Args&&... args)
		{
			// Check if the key is bigger than the last element
			if (m_data.empty() || key > m_data.back().first)
			{
				m_data.emplace_back(key, std::forward<Args>(args)...);
				return;
			}

			throw std::runtime_error("Key cannot be lesser than the last used key.");
		}

		void Remove(const K key)
		{
			std::streamsize index = FindIndexInVector(key);
			m_data.erase(m_data.begin() + index);
		}

		size_t Size() const { return m_data.size(); }

		V& operator[](const K key) noexcept { return Get(key); }

		V& Get(const K key) { return FindPair(key).second; }

		Pair<K, V>& FindPair(const K key)
		{
			std::streamsize index = FindIndexInVector(key);
			if (index < 0)
			{
				throw std::runtime_error("Key not found");
			}
			return m_data[index];
		}

		std::streamsize FindIndexInVector(const K key)
		{
			size_t low = 0;
			size_t high = m_data.size();

			while (low <= high)
			{
				size_t mid = low + (high - low) / 2;

				if (m_data[mid].first == key)
				{
					return mid;
				}
				else if (m_data[mid].first < key)
				{
					low = mid + 1;
				}
				else
				{
					high = mid - 1;
				}
			}

			return -1;
		}

		bool Contains(const K key) noexcept { return FindIndexInVector(key) >= 0; }

		void Clear() { m_data.clear(); }

	private:
		Vec<Pair<K, V>> m_data;
	};
}
