Compile-time алгоритмы. сборник - C++ - Ответ 4532299

#include <iostream>
 
#include <boost/mpl/vector.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/prior.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/less_equal.hpp>
#include <boost/mpl/distance.hpp>
 
namespace mpl = boost::mpl;
 
template<typename Begin, typename Current, typename End,
template<typename, typename> class Compare, bool CurrentResult>
struct is_sorted_helper
{
private:
    typedef Current current_impl_t;
    typedef typename mpl::prior<Current>::type prior_impl_t;
    typedef typename boost::is_same<Begin, current_impl_t>::type current_eq_begin;
    typedef typename mpl::if_<current_eq_begin,
        current_impl_t, prior_impl_t>::type current_prior_t;
    typedef typename mpl::deref<current_prior_t>::type current_p_d;
    typedef typename mpl::deref<current_impl_t>::type current_d;
    typedef Compare<current_p_d, current_d> compare_t;
    typedef typename mpl::next<current_impl_t>::type next_impl_t;
    typedef is_sorted_helper<Begin, next_impl_t, End, Compare,
        compare_t::type::value> impl_t;
public:
    typedef Begin begin_t;
    typedef typename impl_t::current_t current_t;
    typedef typename impl_t::next_t next_t;
    typedef typename impl_t::prior_t prior_t;
    static const bool value = CurrentResult &&
        impl_t::value;
};
 
template<typename Begin, typename Current, typename End,
template <typename, typename> class Compare>
struct is_sorted_helper<Begin, Current, End, Compare, false>
{
private:
    typedef typename mpl::prior<Current>::type prior_impl_t;
    typedef typename boost::is_same<Begin, Current>::type prior_less_eq_current_t;
public:
    typedef Begin begin_t;
    typedef typename mpl::prior<Current>::type current_t;
    typedef typename mpl::prior<current_t>::type prior_t;
    typedef mpl::next<current_t> next_t;
    static const bool value = false;
};
 
template<typename Begin, typename End, template<typename, typename> class Compare>
struct is_sorted_helper<Begin, End, End, Compare, true>
{
    typedef Begin begin_t;
    typedef End current_t;
    typedef mpl::prior<current_t> prior_t;
    typedef End next_t;
    static const bool value = true;
};
 
template<typename Begin, typename End, template<typename, typename> class Compare>
struct is_sorted_range
{
    typedef is_sorted_helper<Begin, Begin, End, Compare, true> result_t;
    typedef typename result_t::begin_t begin_t;
    typedef typename result_t::current_t current_t;
    typedef typename result_t::prior_t prior_t;
    static const bool value = result_t::value;
};
 
template<typename Sequence, template<typename, typename> class Compare>
struct is_sorted_sequence
{
    typedef is_sorted_range<typename mpl::begin<Sequence>::type, typename mpl::end<Sequence>::type, Compare> result_t;
    typedef typename result_t::begin_t begin_t;
    typedef typename result_t::current_t current_t;
    typedef typename result_t::prior_t prior_t;
    static const bool value = result_t::value;
};
 
 
template<typename Result, bool>
struct trace_helper
{
    static void apply()
    {
        std::cout << "Sorted sequence" << std::endl;
    }
};
 
template<typename Result>
struct trace_helper<Result, false>
{
    static void apply()
    {
        typedef typename mpl::deref<Result::prior_t>::type prior_t;
        typedef typename mpl::deref<Result::current_t>::type current_t;
        typedef typename mpl::distance<Result::begin_t, Result::prior_t>::type p_distance_t;
        typedef typename mpl::distance<Result::begin_t, Result::current_t>::type c_distance_t;
        std::cout << "Condition failure between " << p_distance_t::value + 1 << " and " << c_distance_t::value + 1
            << " elements: " << prior_t::value << " > " << current_t::value << std::endl;
    }
};
 
template<typename Result>
void trace()
{
    trace_helper<Result, Result::value>::apply();
}
 
int main()
{
    typedef mpl::vector<mpl::int_<1>, mpl::int_<2>, mpl::int_<3> >::type sorted_vector;
    trace<is_sorted_sequence<sorted_vector, mpl::less_equal> >();
    typedef mpl::vector<mpl::int_<4>, mpl::int_<2>, mpl::int_<3> >::type not_sorted_vector;
    trace<is_sorted_sequence<not_sorted_vector, mpl::less_equal> >();
    typedef mpl::vector<mpl::int_<1> >::type one_el_vector;
    trace<is_sorted_sequence<one_el_vector, mpl::less_equal> >();
    typedef mpl::vector<>::type empty_vector;
    trace<is_sorted_sequence<empty_vector, mpl::less_equal> >();
    typedef mpl::vector<mpl::int_<1>, mpl::int_<3>, mpl::int_<2> >::type not_sorted_vector2;
    trace<is_sorted_sequence<not_sorted_vector2, mpl::less_equal> >();
}