#ifndef MINIMAL_PERFECT_HASH_HH
#define MINIMAL_PERFECT_HASH_HH

#include "cstd.hh"
#include "static_vector.hh"
#include "stl.hh"
#include "xrange.hh"

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>

// This calculates an "order preserving minimal perfect hash function" (mph).
//
// That is for N given input keys (typically these keys will be strings) we
// produce a function with the following properties:
// - The function takes a key as input and produces a number.
// - For the i-th input key (i in [0..N)) the functions returns the value 'i'.
//   * Distinct inputs produce a distinct output (it's a 'perfect' hash).
//   * There are no gaps in the output range (the function is 'minimal').
//   * The order between input and output is preserved.
// - For a new input that was not part of the original set, this function still
//   produces a value in the range [0..n), but it doesn't give any guarantee
//   about which specific value it returns. So typically this output will be
//   used as an index in an array to lookup the original key and then do an
//   equality comparison on that (single) key.
// - The function runs in constant time (O(1)). (Comparing all keys one by one
//   would be O(N), using a std::map would be O(log(N))). More in detail, the
//   input key is hashed (with given non-perfect hash function) only once,
//   followed by one or sometimes two table-lookups.
// - The function can be calculated at compile-time (constexpr).
// - The required storage is about 2 bytes per input key.
//
// This implementation is based on
//    Frozen - An header-only, constexpr alternative to gperf for C++14 users
//    https://github.com/serge-sans-paille/frozen
// Which is based on Steve Hanov's blog post:
//    http://stevehanov.ca/blog/index.php?id=119
// Which is based on this paper:
//    Hash, displace, and compress
//    Djamal Belazzougui, Fabiano C. Botelho and Martin Dietzfelbinger
//    http://cmph.sourceforge.net/papers/esa09.pdf
//
// Compared to the original implementation in 'Frozen' this version is more
// stripped down. There is a chance that the calculation of the mph fails. That
// chance is a bit bigger in our version(*1). On the other hand our produced
// functions runs a bit faster (only runs the non-perfect hash function once
// instead of once or twice). And the resulting tables are ~10x smaller in
// memory (for the specific use case in openMSX with only about ~100 input
// keys).
// (*1) If the calculation fails, it fails at compile time. And for the current
// use case in openMSX (mapper type names) it works fine. If in the future we
// add many (+20) more mapper types we may need to tweak this code a little.

namespace PerfectMinimalHash {

template<size_t M, typename Hash>
struct Result
{
	static_assert(std::has_single_bit(M));
	static constexpr auto M2 = M;

	std::array<uint8_t, M > tab1;
	std::array<uint8_t, M2> tab2; // Note: half this size is not enough, tried that before
	[[no_unique_address]] Hash hash;

	[[nodiscard]] constexpr uint8_t lookupIndex(const auto& key) const {
		const uint32_t h = hash(key);
		const uint8_t d = tab1[h % M];
		if ((d & 0x80) == 0) {
			return d;
		} else {
			return tab2[(h >> (d & 31)) % M2];
		}
	}
};

template<size_t N, typename Hash, typename GetKey>
[[nodiscard]] constexpr auto create(const Hash& hash, const GetKey& getKey)
{
	static_assert(N < 128);
	constexpr size_t M = std::bit_ceil(N);
	constexpr auto bucket_max = size_t(2 * cstd::sqrt(M));

	Result<M, Hash> r{};
	r.hash = hash;

	// Step 1: Place all of the keys into buckets
	std::array<static_vector<uint8_t, bucket_max>, r.tab1.size()> buckets;
	for (auto i : xrange(N)) {
		buckets[hash(getKey(i)) % r.tab1.size()].push_back(uint8_t(i));
	}

	// Step 2: Sort the buckets to process the ones with the most items first.
	std::ranges::sort(buckets, [](const auto& x, const auto& y) {
		// sort largest first
		if (x.size() != y.size()) {
			return x.size() > y.size();
		}
		// same size, sort lexicographical
		return std::ranges::lexicographical_compare(x, y);
	});

	// Step 3: Map the items in buckets into hash tables.
	constexpr auto UNUSED = uint8_t(-1);
	std::ranges::fill(r.tab2, UNUSED);
	for (const auto& bucket : buckets) {
		auto const bSize = bucket.size();
		if (bSize == 0) break; // done
		auto hash1 = hash(getKey(bucket[0])) % r.tab1.size();
		if (bSize == 1) {
			// Store index to the (single) item in tab1
			r.tab1[hash1] = bucket[0];
		} else {
			// Repeatedly try different shift-factors until we can
			// place all items in the bucket into free slots.
			uint8_t shift = 1;
			static_vector<uint8_t, bucket_max> bucket_slots;

			while (bucket_slots.size() < bSize) {
				auto hash2 = hash(getKey(bucket[bucket_slots.size()]));
				assert((hash2 % r.tab1.size()) == hash1);
				auto slot = (hash2 >> shift) % r.tab2.size();
				if (r.tab2[slot] != UNUSED || contains(bucket_slots, slot)) {
					++shift; // try next
					assert(shift < 32);
					bucket_slots.clear();
					continue;
				}
				bucket_slots.push_back(uint8_t(slot));
			}

			// Put successful shift-factor in tab1, and put indices to items in their slots
			r.tab1[hash1] = shift | 0x80;
			for (auto i : xrange(bSize)) {
				r.tab2[bucket_slots[i]] = bucket[i];
			}
		}
	}

	// Change unused entries to zero because it must be valid indices (< N).
	std::ranges::replace(r.tab2, UNUSED, uint8_t(0));
	return r;
}

} // namespace PerfectMinimalHash

#endif