Boost.PPでクイックソート(改良版)
まず素直に再帰で実装したものがこちら。
http://ideone.com/3Sz2P
美しくありませんね。
マクロは再帰できないため、ループや再帰を実現するにはどこかでこのような連番マクロを使う必要があります。しかし、そういった汚れ仕事はBoost.PPのWHILEやSEQ_FOLD_LEFTに任せてしまいましょう。今回はWHILEを使ってループで実装してみます。
#include <boost/preprocessor/cat.hpp> #include <boost/preprocessor/control/iif.hpp> #include <boost/preprocessor/control/while.hpp> #include <boost/preprocessor/logical/bitand.hpp> #include <boost/preprocessor/logical/compl.hpp> #include <boost/preprocessor/logical/xor.hpp> #include <boost/preprocessor/seq/filter.hpp> #include <boost/preprocessor/seq/seq.hpp> #include <boost/preprocessor/tuple/eat.hpp> #include <boost/preprocessor/tuple/elem.hpp> #define PP_EMPTY #define PP_SEQ_EMPTY(seq)\ BOOST_PP_TUPLE_ELEM(\ 2, 0, (BOOST_PP_CAT(PP_SEQ_EMPTY_DEF_, PP_SEQ_EMPTY_1 seq))\ ) #define PP_SEQ_EMPTY_1(x) PP_SEQ_EMPTY_0 #define PP_SEQ_EMPTY_DEF_PP_SEQ_EMPTY_0 0, #define PP_SEQ_EMPTY_DEF_PP_SEQ_EMPTY_1 1, #define PP_SEQ_SORT(pred, seq)\ BOOST_PP_TUPLE_ELEM(\ 4, 3,\ BOOST_PP_WHILE(\ PP_SEQ_SORT_P, PP_SEQ_SORT_O,\ (pred, seq, PP_EMPTY, PP_EMPTY)\ )\ ) #define PP_SEQ_SORT_D(d, pred, seq)\ BOOST_PP_TUPLE_ELEM(\ 4, 3,\ BOOST_PP_WHILE_ ## d(\ PP_SEQ_SORT_P, PP_SEQ_SORT_O,\ (pred, seq, PP_EMPTY, PP_EMPTY)\ )\ ) #define PP_SEQ_SORT_P(d, state)\ BOOST_PP_COMPL(\ BOOST_PP_BITAND(\ PP_SEQ_EMPTY(BOOST_PP_TUPLE_ELEM(4, 1, state)),\ PP_SEQ_EMPTY(BOOST_PP_TUPLE_ELEM(4, 2, state))\ )\ ) #define PP_SEQ_SORT_O(d, state)\ BOOST_PP_IIF(\ PP_SEQ_EMPTY(BOOST_PP_TUPLE_ELEM(4, 1, state)),\ PP_SEQ_SORT_O_0, PP_SEQ_SORT_O_1\ )(\ d,\ BOOST_PP_TUPLE_ELEM(4, 0, state), BOOST_PP_TUPLE_ELEM(4, 1, state),\ BOOST_PP_TUPLE_ELEM(4, 2, state), BOOST_PP_TUPLE_ELEM(4, 3, state)\ ) #define PP_SEQ_SORT_O_0(d, pred, seq, stack, acc)\ (\ pred,\ BOOST_PP_TUPLE_ELEM(2, 1, BOOST_PP_SEQ_HEAD(stack)),\ BOOST_PP_SEQ_TAIL(stack),\ acc(BOOST_PP_TUPLE_ELEM(2, 0, BOOST_PP_SEQ_HEAD(stack)))\ ) #define PP_SEQ_SORT_O_1(d, pred, seq, stack, acc)\ (\ pred,\ PP_SEQ_SORT_F(\ d, 0, pred,\ BOOST_PP_SEQ_HEAD(seq), BOOST_PP_SEQ_TAIL(seq)\ ),\ (\ (\ BOOST_PP_SEQ_HEAD(seq),\ PP_SEQ_SORT_F(\ d, 1, pred,\ BOOST_PP_SEQ_HEAD(seq), BOOST_PP_SEQ_TAIL(seq)\ )\ )\ )stack,\ acc\ ) #define PP_SEQ_SORT_F(d, ge, pred, x, xs)\ BOOST_PP_IIF(PP_SEQ_EMPTY(xs), BOOST_PP_TUPLE_EAT(3), BOOST_PP_SEQ_FILTER)(\ PP_SEQ_SORT_F_P, (d, ge, pred, x), xs\ ) #define PP_SEQ_SORT_F_P(s, data, elem)\ BOOST_PP_XOR(\ BOOST_PP_TUPLE_ELEM(4, 1, data),\ BOOST_PP_TUPLE_ELEM(4, 2, data)(\ BOOST_PP_TUPLE_ELEM(4, 0, data),\ elem,\ BOOST_PP_TUPLE_ELEM(4, 3, data)\ )\ ) #include <boost/preprocessor/comparison/less.hpp> PP_SEQ_SORT(BOOST_PP_LESS_D, (3)(2)(0)(5)(8)(3)(4)(1)(3)(2))
g++ -E -P pp_seq_sort2.cpp
(0)(1)(2)(2)(3)(3)(3)(4)(5)(8)
非常に明解で分かりやすいですね。
ところで
プリプロセスタイムソートとか誰得