constexpr bitonic sort

constexpr_bitonic_sort.hpp

#include<utility>
#include<sprout/algorithm.hpp>
#include<sprout/array.hpp>

namespace impl
{
	template<class T, std::size_t N>
	struct bitonic_sort_impl
	{
		using array = sprout::array<T, (1u << N)>;
		template<std::size_t M, std::size_t i, std::size_t Idx>
		struct Eval
		{
			static const std::size_t a = (1u << (M + 1));
			static const std::size_t b = (1u << (M - i));
			static const std::size_t other = Idx + b * (((Idx / b) % 2) ? -1 : 1);

			constexpr static T apply(array const&v)
			{
				return (Idx / a % 2) ^ (Idx < other) ^ (v[Idx] < v[other]) ? v[other] : v[Idx];
			}
		};

		struct forward
		{
			template<class hoge>
			constexpr static array apply(array const&v, hoge)
			{
				return v;
			}
		};
		template<std::size_t Len, std::size_t state>
		struct Impl
		{
			static const bool r = (Len == state);
			using NextImpl = Impl<(r ? Len + 1 : Len), (r ? 0 : state + 1)>;
			using Next = typename std::conditional<(state != N - 1), NextImpl, forward>::type;
			template<std::size_t...Idx>
			constexpr static array apply(array const&v, std::index_sequence<Idx...> seq)
			{
				return Next::apply(array{{ Eval<Len, state, Idx>::apply(v)... }}, seq);
			}
		};

		constexpr static array apply(array const&v)
		{
			return Impl<0, 0>::apply(v, std::make_index_sequence<(1u << N)>{});
		}
	};
}//バイトニックソート
//
template<std::size_t N, class T>
constexpr sprout::array<T, (1u << N)> bitonic_sort(sprout::array<T, (1u << N)> const&v)
{
	return impl::bitonic_sort_impl<T, N>::apply(v);
}

template<std::size_t ...N>
constexpr sprout::array<int, sizeof...(N)> make_test(std::index_sequence<N...>)
{
	return{ { (sizeof...(N) -N)... } };
}




#include<sprout/range/algorithm.hpp>
static constexpr auto test = make_test(std::make_index_sequence<1024>{});
static constexpr auto res = bitonic_sort<10, int>(test);
int main()
{
	for (auto x : res)
		std::cout << x << '-';
}