#pragma once

#include <psemek/util/hash.hpp>
#include <psemek/util/span.hpp>

#include <vector>
#include <cstdint>
#include <climits>
#include <compare>

namespace psemek::util
{

	struct dynamic_bitset
	{
		using storage_type = std::uint64_t;
		static constexpr std::size_t storage_bits = sizeof(storage_type) * CHAR_BIT;
		static constexpr std::size_t storage_mask = storage_bits - 1;

		[[nodiscard]] static std::size_t bits_count_to_storage_size(std::size_t bits_count)
		{
			return (bits_count + storage_bits - 1) / storage_bits;
		}

		dynamic_bitset() = default;
		dynamic_bitset(std::size_t size)
			: storage_(bits_count_to_storage_size(size), 0)
		{}

		void resize(std::size_t size)
		{
			storage_.resize(bits_count_to_storage_size(size));
		}

		void assign(std::size_t size, bool value)
		{
			storage_type storage_value = value ? -1 : 0;
			storage_.assign(bits_count_to_storage_size(size), storage_value);
			if (value)
				storage_.back() &= ((static_cast<storage_type>(1) << (size % storage_bits)) - 1);
		}

		[[nodiscard]] std::size_t size() const
		{
			return storage_.size() * storage_bits;
		}

		[[nodiscard]] bool get(std::size_t index) const
		{
			std::size_t storage_index = index / storage_bits;
			std::size_t storage_shift = index & storage_mask;
			if (storage_index > storage_.size())
				return false;
			return (storage_[storage_index] & static_cast<storage_type>(1 << storage_shift)) != 0;
		}

		bool set(std::size_t index, bool value)
		{
			resize(index + 1);

			std::size_t storage_index = index / storage_bits;
			std::size_t storage_shift = index & storage_mask;

			auto & storage_value = storage_[storage_index];
			bool result = (storage_value & static_cast<storage_type>(1 << storage_shift)) != 0;

			if (value)
				storage_value |= static_cast<storage_type>(1 << storage_shift);
			else
				storage_value &= ~static_cast<storage_type>(1 << storage_shift);

			return result;
		}

		util::span<storage_type const> storage() const
		{
			return storage_;
		}

	private:
		std::vector<storage_type> storage_;
	};

	[[nodiscard]] bool operator == (dynamic_bitset const & b1, dynamic_bitset const & b2);

	[[nodiscard]] std::strong_ordering operator <=> (dynamic_bitset const & b1, dynamic_bitset const & b2);

	[[nodiscard]] bool is_subset(dynamic_bitset const & b1, dynamic_bitset const & b2);

	[[nodiscard]] std::size_t popcount(dynamic_bitset const & b);

}

namespace std
{

	template <>
	struct hash<::psemek::util::dynamic_bitset>
	{
		std::uint64_t operator()(::psemek::util::dynamic_bitset const & b) const
		{
			std::uint64_t result = static_cast<std::size_t>(0x23d2ef655094f9aeull);
			for (auto value : b.storage())
				::psemek::util::hash_combine(result, value);
			return result;
		}
	};

}
