ジャパニーズとても迷惑コード(TMPでエラトステネスの篩)

main.cpp

#include<iostream>
#include<chrono>
#include<vector>
#include<array>
#include<set>
#include<random>
#include<queue>

struct none_t {};
template<class Lhs, class Rhs>struct tree
{
	typedef Lhs lhs;
	typedef Rhs rhs;
};
template<std::size_t I>using index_node = std::integral_constant<std::size_t, I>;
namespace detail
{
	template<std::size_t First, std::size_t Last>struct make_index_tree
	{
		typedef tree<
			typename make_index_tree<First, (Last - First) / 2 + First>::type,
			typename make_index_tree<(Last - First) / 2 + First + 1, Last>::type> type;
	};
	template<std::size_t I>struct make_index_tree<I, I>
	{
		typedef index_node<I> type;
	};
}
template<std::size_t Size>struct make_index_tree
{
	typedef typename detail::make_index_tree<0, Size - 1>::type type;
};

namespace detail
{
	template<bool, class T>struct filter_check
	{
		typedef none_t type;
	};
	template<class T>struct filter_check<true, T>
	{
		typedef T type;
	};
	template<class Tree, template<std::size_t>class Cond>struct filter
	{
		typedef tree<
			typename filter<typename Tree::lhs, Cond>::type, 
			typename filter<typename Tree::rhs, Cond>::type> type;
	};
	template<template<std::size_t>class Cond>struct filter<none_t, Cond>
	{
		typedef none_t type;
	};
	template<std::size_t I,template<std::size_t>class Cond>struct filter<index_node<I>, Cond>
	{
		typedef typename filter_check<Cond<I>::value, index_node<I>>::type type;
	};

	template<class Tree>struct get_first;
	template<class Cond, class Rhs>struct get_first_i
	{
		typedef Cond type;
	};
	template<class Rhs>struct get_first_i<none_t, Rhs>
	{
		typedef typename get_first<Rhs>::type type;
	};
	template<class Lhs,class Rhs>struct get_first<tree<Lhs,Rhs>>
	{
		typedef typename get_first_i<typename get_first<Lhs>::type, Rhs>::type type;
	};
	template<>struct get_first<none_t>
	{
		typedef none_t type;
	};
	template<std::size_t I>struct get_first<index_node<I>>
	{
		typedef index_node<I> type;
	};

	template<class Tree>struct all_none
	{
		static constexpr bool value = false;
	};
	template<class Lhs, class Rhs>struct all_none<tree<Lhs, Rhs>>
	{
		static constexpr bool value = all_none<Lhs>::value&&all_none<Rhs>::value;
	};
	template<>struct all_none<none_t>
	{
		static constexpr bool value = true;
	};

	template<class Lhs,class Rhs>struct none_cat_i
	{
		typedef tree<Lhs, Rhs> type;
	};
	template<>struct none_cat_i<none_t, none_t>
	{
		typedef none_t type;
	};
	template<class Tree>struct none_cat
	{
		typedef Tree type;
	};
	template<class Lhs, class Rhs>struct none_cat<tree<Lhs, Rhs>>
	{
		typedef typename none_cat_i<typename none_cat<Lhs>::type, typename none_cat<Rhs>::type>::type type;
	};
}

template<class Tree, template<std::size_t>class Cond>struct filter
{
	typedef typename detail::filter<Tree, Cond>::type type;
};
template<class Tree>struct get_first
{
	typedef typename detail::get_first<Tree>::type type;
	static constexpr auto value = type::value;
};
template<class Tree>struct all_none :std::integral_constant<bool, detail::all_none<Tree>::value>
{

};
template<class Tree>struct none_cat
{
	typedef typename detail::none_cat<Tree>::type type;
};

namespace detail
{
	template<class Lhs, class Rhs>struct sequence_merge;
	template<std::size_t... L, std::size_t... R>struct sequence_merge<std::index_sequence<L...>, std::index_sequence<R...>>
	{
		typedef std::index_sequence<L..., R...> type;
	};
	template<class Tree>struct tree_to_sequence
	{
		typedef typename sequence_merge<
			typename tree_to_sequence<typename Tree::lhs>::type,
			typename tree_to_sequence<typename Tree::rhs>::type>::type type;
	};
	template<>struct tree_to_sequence<none_t>
	{
		typedef std::index_sequence<> type;
	};
	template<std::size_t I>struct tree_to_sequence<index_node<I>>
	{
		typedef std::index_sequence<I> type;
	};
}
template<class Tree>struct tree_to_sequence
{
	typedef typename detail::tree_to_sequence<Tree>::type type;
};

namespace sieve_detail
{
	template<std::size_t I, class Rest>struct sieve
	{
		typedef sieve<I - 1, Rest> first;
		typedef sieve<I - 1, typename none_cat<typename first::rest>::type> second;
		typedef tree<typename first::type, typename second::type> type;
		typedef typename none_cat<typename second::rest>::type rest;
	};
	template<class Rest>struct sieve<0, Rest>
	{
		static constexpr std::size_t value = get_first<Rest>::value;
		template<std::size_t N>struct diver_check :std::integral_constant<bool, (N%value != 0)>
		{

		};
		typedef index_node<value> type;
		typedef typename filter<Rest, diver_check>::type rest;
	};
	template<std::size_t I>struct sieve<I, none_t>
	{
		typedef none_t type;
		typedef none_t rest;
	};
	template<>struct sieve<0, none_t>
	{
		typedef none_t type;
		typedef none_t rest;
	};

	template<std::size_t I, class Primes, class Rest>struct sieve_i
	{
		typedef sieve<I, Rest> rhs;
		typedef typename sieve_i<I + 1, tree<Primes, typename rhs::type>, typename rhs::rest>::type type;
	};
	template<std::size_t I, class Primes>struct sieve_i<I, Primes, none_t>
	{
		typedef Primes type;
	};

	template<class Tree>struct ready;
	template<class Lhs, class Rhs>struct ready<tree<Lhs, Rhs>>
	{
		typedef tree<typename ready<Lhs>::type, typename ready<Rhs>::type> type;
	};
	template<std::size_t I>struct ready<index_node<I>>
	{
		typedef index_node<I + 2> type;
	};
	template<>struct ready<none_t>
	{
		typedef none_t type;
	};
}

template<std::size_t I>struct sieve
{
	typedef sieve_detail::sieve<0, typename sieve_detail::ready<typename make_index_tree<I - 1>::type>::type> init;
	typedef typename sieve_detail::sieve_i<0, typename init::type, typename init::rest>::type type;
};

template<std::size_t... Is>auto make_array(std::index_sequence<Is...>)
{
	return std::array<std::size_t, sizeof...(Is)>{ {Is...}};
}

template<std::size_t I>void print_tree(index_node<I>const&, int v = 0)
{
	for (int i{};i < 2 * v;++i)
	{
		std::cout << " ";
	}
	std::cout << I << std::endl;
}
void print_tree(none_t, int v = 0)
{
	for (int i{};i < 2 * v;++i)
	{
		std::cout << " ";
	}
	std::cout << "[]" << std::endl;
}
template<class Lhs, class Rhs>void print_tree(tree<Lhs, Rhs>const&, int v = 0)
{
	for (int i{};i < 2 * v;++i)
	{
		std::cout << " ";
	}
	std::cout << "[" << std::endl;
	print_tree(Lhs(), v + 1);
	print_tree(Rhs(), v + 1);
	for (int i{};i < 2 * v;++i)
	{
		std::cout << " ";
	}
	std::cout << "]" << std::endl;;
}

int main()
{
	typedef typename sieve<5000>::type tree;
	print_tree(tree());
}

main.md

#感想 久しぶりにコンパイラがヒープの領域食い尽くしたの見た。

omake.cpp

#include<iostream>
#include<memory>
#include<functional>
#include<list>
#include<boost/optional.hpp>

struct set
{
	struct node_t
	{
		virtual bool none_cat() = 0;
		virtual bool filter(std::function<bool(int)>const& cond) = 0;
		virtual boost::optional<int> get_first() = 0;
	};
	struct real_t :node_t
	{
		std::shared_ptr<node_t> lhs;
		std::shared_ptr<node_t> rhs;
		virtual bool none_cat()
		{
			auto x = lhs->none_cat();
			auto y = rhs->none_cat();
			if (x&&y)
				return true;
			if (x)
			{
				lhs = none;
			}
			if (y)
			{
				rhs = none;
			}
			return false;
		}
		virtual bool filter(std::function<bool(int)>const& cond)
		{
			auto x = lhs->filter(cond);
			auto y = rhs->filter(cond);
			if (x&&y)
				return true;
			if (x)
			{
				lhs = none;
			}
			if (y)
			{
				rhs = none;
			}
			return false;
		}
		virtual boost::optional<int> get_first()
		{
			if (auto p = lhs->get_first())
			{
				return p;
			}
			else
			{
				return rhs->get_first();
			}
		}

		real_t(int first, int last) :lhs(), rhs()
		{
			int middle = (first + last) / 2;
			if (first == middle)
			{
				lhs = std::make_shared<value_t>(first);
				rhs = std::make_shared<value_t>(last);
			}
			else
			{
				lhs = std::make_shared<real_t>(first, middle);
				if (middle + 1 == last)
				{
					rhs = std::make_shared<value_t>(last);
				}
				else
				{
					rhs = std::make_shared<real_t>(middle + 1, last);
				}
			}
		}
		real_t(std::shared_ptr<node_t>l, std::shared_ptr<node_t>r) :lhs(l), rhs(r)
		{

		}
	};
	struct value_t :node_t
	{
		int val;
		virtual bool none_cat()
		{
			return false;
		}
		virtual bool filter(std::function<bool(int)>const& cond)
		{
			return !cond(val);
		}
		virtual boost::optional<int> get_first()
		{
			return val;
		}

		value_t(int v) :val(v)
		{

		}
	};
	struct none_t :node_t
	{
		virtual bool none_cat()
		{
			return true;
		}
		virtual bool filter(std::function<bool(int)>const&)
		{
			return true;
		}
		virtual boost::optional<int> get_first()
		{
			return boost::none;
		}
	};
	static std::shared_ptr<none_t> none;
	std::shared_ptr<node_t> node;
	set(int first, int last) :node()
	{
		if (first == last)
		{
			node = std::make_shared<value_t>(first);
		}
		else
		{
			node = std::make_shared<real_t>(first, last);
		}
	}
	set() :node(none)
	{

	}
	void filter(std::function<bool(int)>const& cond)
	{
		if (node->filter(cond))
		{
			node = none;
		}
	}
	void none_cat()
	{
		if (node->none_cat())
		{
			node = none;
		}
	}
	boost::optional<int> get_first()
	{
		return node->get_first();
	}
};
std::shared_ptr<set::none_t> set::none = std::make_shared<set::none_t>();
set merge(set lhs, set rhs)
{
	set ret;
	ret.node = std::make_shared<set::real_t>(lhs.node, rhs.node);
	ret.none_cat();
	return ret;
}

std::list<int> sieve(set& s, int v)
{
	if (v == 0)
	{
		if (auto p = s.get_first())
		{
			s.filter([&](int x) {return x % (*p) != 0;});
			return std::list<int>{*p};
		}
		else
		{
			return std::list<int>{};
		}
	}
	else
	{
		auto ret = sieve(s, v - 1);
		if (auto p = s.get_first())
		{
			s.filter([&](int x) {return x % (*p) != 0;});
			ret.emplace_back(*p);
			ret.merge(sieve(s, v - 1));
		}
		return ret;
	}
}

std::list<int> sieve(set& s, int v, boost::none_t)
{
	auto ret = sieve(s, v);
	if (auto p = s.get_first())
	{
		s.filter([&](int x) {return x % (*p) != 0;});
		ret.emplace_back(*p);
		ret.merge(sieve(s, v + 1, boost::none));
	}
	return ret;
}
std::list<int> sieve(int size)
{
	set s(2, size + 1);
	return sieve(s, 0, boost::none);
}

int main()
{
	for (auto v : sieve(10000))
	{
		std::cout << v << std::endl;
	}
}