#ifndef hashmap_hpp
#define hashmap_hpp

extern "C" {
#include "plat.h"
}

#include <tuple>
#include <stddef.h>

template <typename T>
struct Hash_Function {};

template <typename Key, typename Value, int size>
struct Hash_Map {
	enum {
		flags_tombstone = 1 << 0,
		flags_null      = 1 << 1
	};

	Key keys[size];
	Value values[size];
	uint8_t flags[size];

	void init() {
		int i;
		for (i = 0; i < size; i++) flags[i] = flags_null;
	}

	int find(const Key& to_find) const {
		int tombstone = -1, i;
		int bucket = (int)(Hash_Function<Key>{}(to_find) % (size_t)size);
		for (i = 0; i < size; i++) {
			const Key& k = keys[bucket];
			uint8_t flag = flags[bucket];
			if (flag & flags_null) {
				if (flag & flags_tombstone) {
					if (tombstone < 0) tombstone = bucket;
				} else return tombstone >= 0? tombstone: bucket;
			} else if (k == to_find) return bucket;
			bucket = (bucket + 1) % size;
		}
		if (tombstone >= 0) return tombstone;
		return -1;
	}

	Value& set(const Key& k, const Value& v) {
		int bucket = find(k);
		assert(bucket >= 0); /* full */
		flags[bucket] = 0;
		keys[bucket] = k;
		values[bucket] = v;
		return values[bucket];
	}

	Value* get(const Key& k) {
		int bucket = find(k);
		if (bucket < 0 || flags[bucket] & flags_null) return 0;
		return &values[bucket];
	}

	Value& operator[](const Key& k) {
		int bucket = find(k);
		assert(bucket >= 0);
		return values[bucket];
	}

	const Value& operator[](const Key& k) const {
		int bucket = find(k);
		assert(bucket >= 0);
		return values[bucket];
	}

	Key* kaddr(const Key& k) {
		int bucket = find(k);
		if (bucket < 0 || flags[bucket] & flags_null) return 0;
		return &keys[bucket];
	}

	void remove(const Key& k) {
		int bucket = find(k);
		assert(bucket >= 0);
		flags[bucket] = flags_null | flags_tombstone;
	}

	int has(const Key& k) {
		int bucket = find(k);
		return bucket >= 0 && ~flags[bucket] & flags_null;
	}

	template <typename Table>
	struct iterator {
		Table* table;
		int bucket;

		void init_begin(Table* t) {
			bucket = 0;
			table = t;
			while (
				bucket < size &&
				table->flags[bucket] & flags_null
			) bucket++;
		}
		void init_end(Table* t) {
			bucket = size;
			table = t;
		}
		bool equals(const iterator<Table>& other) {
			return bucket == other.bucket && table == other.table;
		}
		bool operator==(const iterator<Table>& other) {
			return equals(other);
		}
		bool operator!=(const iterator<Table>& other) {
			return !equals(other);
		}
		iterator<Table> operator++() {
			bucket++;
			while (
				bucket < size &&
				table->flags[bucket] & flags_null
			) bucket++;
			return *this;
		}
		std::pair<Key&, Value&> operator*() {
			return { table->keys[bucket], table->values[bucket] };
		}
		std::pair<const Key&, const Value&> operator*() const {
			return { table->keys[bucket], table->values[bucket] };
		}
	};

	iterator<Hash_Map<Key, Value, size>> begin() {
		iterator<Hash_Map<Key, Value, size>> r;
		r.init_begin(this);
		return r;
	}

	iterator<Hash_Map<Key, Value, size>> end() {
		iterator<Hash_Map<Key, Value, size>> r;
		r.init_end(this);
		return r;
	}

	iterator<const Hash_Map<Key, Value, size>> begin() const {
		iterator<const Hash_Map<Key, Value, size>> r;
		r.init_begin(this);
		return r;
	}

	iterator<const Hash_Map<Key, Value, size>> end() const {
		iterator<const Hash_Map<Key, Value, size>> r;
		r.init_end(this);
		return r;
	}
};

#endif