#include <cstring>
#include <stdexcept>
#include <type_traits>

namespace tmp
{
	template <typename T>
	struct identity
	{
		typedef T type;
	};

	template <typename T, T V>
	struct constant
	{
		static constexpr T value = V;
	};

	template <bool B>
	struct bool_ : constant<bool, B>
	{};

	template <typename First, typename Second>
	struct tpair
	{};

	template <typename Pair>
	struct first;

	template <typename First, typename Second>
	struct first<tpair<First, Second>> : identity<First>
	{};

	template <typename Pair>
	struct second;

	template <typename First, typename Second>
	struct second<tpair<First, Second>> : identity<Second>
	{};

	template <char... S>
	struct tstring
	{};

	template <typename S>
	struct c_str;

	template <char... S>
	struct c_str<tstring<S...>>
	{
		static char const value[];
	};

	template <char... S>
	char const c_str<tstring<S...>>::value[] = { S..., 0 };

	template <typename... List>
	struct tlist : identity<tlist<List...>>
	{};

	template <typename List>
	struct empty : bool_<false>
	{};

	template <>
	struct empty<tlist<>> : bool_<true>
	{};

	template <typename T, typename List>
	struct push_front;

	template <typename T, typename... List>
	struct push_front<T, tlist<List...>>
		: tlist<T, List...>
	{};

	template <typename List>
	struct pop_front;

	template <typename Head, typename... Tail>
	struct pop_front<tlist<Head, Tail...>>
		: tlist<Tail...>
	{};

	template <typename List>
	struct front;

	template <typename Head, typename... Tail>
	struct front<tlist<Head, Tail...>> : identity<Head>
	{};

	template
	<
		typename T,
		typename List,
		template <typename, typename> class Less
	>
	struct insert_sorted;

	template
	<
		typename T,
		template <typename, typename> class Less
	>
	struct insert_sorted<T, tlist<>, Less>
		: tlist<T>
	{};

	template
	<
		typename T,
		typename Head, typename... Tail,
		template <typename, typename> class Less
	>
	struct insert_sorted<T, tlist<Head, Tail...>, Less>
		: std::conditional
		<
			Less<T, Head>::value,
			tlist<T, Head, Tail...>,
			typename push_front<Head, typename insert_sorted<T, tlist<Tail...>, Less>::type>::type
		>::type
	{};

	template
	<
		template <typename, typename> class Less,
		typename List
	>
	struct sort;

	template
	<
		template <typename, typename> class Less
	>
	struct sort<Less, tlist<>>
		: tlist<>
	{};

	template
	<
		template <typename, typename> class Less,
		typename Head, typename... Tail
	>
	struct sort<Less, tlist<Head, Tail...>>
		: insert_sorted<Head, typename sort<Less, tlist<Tail...>>::type, Less>
	{};

	template <typename S1, typename S2>
	struct string_less;

	template <>
	struct string_less<tstring<>, tstring<>>
		: bool_<false>
	{};

	template <char... S>
	struct string_less<tstring<S...>, tstring<>>
		: bool_<false>
	{};

	template <char... S>
	struct string_less<tstring<>, tstring<S...>>
		: bool_<true>
	{};

	template <char Head1, char... Tail1, char Head2, char... Tail2>
	struct string_less<tstring<Head1, Tail1...>, tstring<Head2, Tail2...>>
		: bool_
		<
			Head1 == Head2
			? string_less<tstring<Tail1...>, tstring<Tail2...>>::value
			: (Head1 < Head2)
		>
	{};

	template <typename Pair1, typename Pair2>
	struct pair_less;

	template <typename Enum1, typename String1, typename Enum2, typename String2>
	struct pair_less<tpair<Enum1, String1>, tpair<Enum2, String2>>
		: string_less<String1, String2>
	{};

	template <unsigned N, typename List>
	struct take_n;

	template <>
	struct take_n<0, tlist<>>
	{
		typedef tlist<> left;
		typedef tlist<> right;
	};

	template <typename Head, typename... Tail>
	struct take_n<0, tlist<Head, Tail...>>
	{
		typedef tlist<> left;
		typedef tlist<Head, Tail...> right;
	};

	template <unsigned N, typename Head, typename... Tail>
	class take_n<N, tlist<Head, Tail...>>
	{
		typedef take_n<N - 1, tlist<Tail...>> recurse;

	public:
		typedef typename push_front<Head, typename recurse::left>::type left;
		typedef typename recurse::right right;
	};

	template <typename List>
	struct cut_half_with_median;

	template <typename... List>
	class cut_half_with_median<tlist<List...>>
	{
		typedef take_n<sizeof...(List) / 2, tlist<List...>> left_without_median;
		typedef take_n<1, typename left_without_median::right> median_with_right;

	public:
		typedef typename left_without_median::left left;
		typedef typename front<typename median_with_right::left>::type median;
		typedef typename median_with_right::right right;
	};

	template <typename Enum, typename Mappings>
	class decision_tree
	{
		typedef cut_half_with_median<Mappings> cut;
		typedef typename cut::median median;

		Enum not_found(std::string const& value) const
		{
			throw std::invalid_argument{ "string '" + value + "' has no enum value" };
		}

		Enum less(char const* value, bool_<true>) const
		{
			return not_found(value);
		}

		Enum less(char const* value, bool_<false>) const
		{
			return decision_tree<Enum, typename cut::left>()(value);
		}

		Enum greater(char const* value, bool_<true>) const
		{
			return not_found(value);
		}

		Enum greater(char const* value, bool_<false>) const
		{
			return decision_tree<Enum, typename cut::right>()(value);
		}

	public:
		Enum operator () (char const* value) const
		{
			auto cmp = std::strcmp(value, c_str<typename second<median>::type>::value);

			if(cmp < 0)
				return less(value, bool_<empty<typename cut::left>::value>());

			if(cmp > 0)
				return greater(value, bool_<empty<typename cut::right>::value>());

			return first<median>::type::value;
		}
	};

	template <typename Enum, typename... Mappings>
	struct enum_mapper;

	template <typename Enum, typename... Strings, Enum... Values>
	class enum_mapper<Enum, tpair<constant<Enum, Values>, Strings>...>
	{
		typedef tlist<tpair<constant<Enum, Values>, Strings>...> mappings;
		typedef typename sort<pair_less, mappings>::type sorted_mappings;

	public:
		Enum operator () (char const* value) const
		{
			return decision_tree<Enum, sorted_mappings>()(value);
		}
	};
}

#define EMAP(E, ...) tmp::tpair<tmp::constant<decltype(E), E>, tmp::tstring<__VA_ARGS__>>

////////////////////////////////////////////////////////////////

#include <iostream>

enum struct my_enum : unsigned
{
	foo,
	bar,
	baz,
	qux,
};

std::ostream& operator << (std::ostream& os, my_enum e)
{
	static char const* const table[] = { "foo", "bar", "baz", "qux" };
	return os << table[static_cast<unsigned>(e)];
}

int main()
{
	typedef tmp::enum_mapper
	<
		my_enum,
		EMAP(my_enum::baz, 'b','a','z'),
		EMAP(my_enum::bar, 'b','a','r'),
		EMAP(my_enum::foo, 'f','o','o'),
		EMAP(my_enum::qux, 'q','u','x')
	> my_enum_mapper;

	my_enum_mapper mapper;

	std::cout << mapper("foo") << '\n';
	std::cout << mapper("bar") << '\n';
	std::cout << mapper("baz") << '\n';
	std::cout << mapper("qux") << '\n';

	try
	{
		std::cout << mapper("garbage") << '\n';
	}

	catch(std::invalid_argument const& iv)
	{
		std::cout << iv.what() << '\n';
	}
}
