[ceph.git] / ceph / src / boost / libs / hana / include / boost / hana / sort.hpp

/*!
@file
Defines `boost::hana::sort`.

@copyright Louis Dionne 2013-2016
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 */

#ifndef BOOST_HANA_SORT_HPP
#define BOOST_HANA_SORT_HPP

#include <boost/hana/fwd/sort.hpp>

#include <boost/hana/at.hpp>
#include <boost/hana/concept/sequence.hpp>
#include <boost/hana/config.hpp>
#include <boost/hana/core/dispatch.hpp>
#include <boost/hana/core/make.hpp>
#include <boost/hana/detail/nested_by.hpp> // required by fwd decl
#include <boost/hana/length.hpp>
#include <boost/hana/less.hpp>

#include <utility> // std::declval, std::index_sequence


BOOST_HANA_NAMESPACE_BEGIN
    //! @cond
    template <typename Xs, typename Predicate>
    constexpr auto sort_t::operator()(Xs&& xs, Predicate&& pred) const {
        using S = typename hana::tag_of<Xs>::type;
        using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>,
            hana::Sequence<S>::value
        );

    #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
        static_assert(hana::Sequence<S>::value,
        "hana::sort(xs, predicate) requires 'xs' to be a Sequence");
    #endif

        return Sort::apply(static_cast<Xs&&>(xs),
                           static_cast<Predicate&&>(pred));
    }

    template <typename Xs>
    constexpr auto sort_t::operator()(Xs&& xs) const {
        using S = typename hana::tag_of<Xs>::type;
        using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>,
            hana::Sequence<S>::value
        );

    #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
        static_assert(hana::Sequence<S>::value,
        "hana::sort(xs) requires 'xs' to be a Sequence");
    #endif

        return Sort::apply(static_cast<Xs&&>(xs));
    }
    //! @endcond

    namespace detail {
        template <typename Xs, typename Pred>
        struct sort_predicate {
            template <std::size_t I, std::size_t J>
            using apply = decltype(std::declval<Pred>()(
                hana::at_c<I>(std::declval<Xs>()),
                hana::at_c<J>(std::declval<Xs>())
            ));
        };

        template <typename Pred, std::size_t Insert, bool IsInsertionPoint,
                  typename Left,
                  std::size_t ...Right>
        struct insert;

        // We did not find the insertion point; continue processing elements
        // recursively.
        template <
            typename Pred, std::size_t Insert,
            std::size_t ...Left,
            std::size_t Right1, std::size_t Right2, std::size_t ...Right
        >
        struct insert<Pred, Insert, false,
                      std::index_sequence<Left...>,
                      Right1, Right2, Right...
        > {
            using type = typename insert<
                Pred, Insert, (bool)Pred::template apply<Insert, Right2>::value,
                std::index_sequence<Left..., Right1>,
                Right2, Right...
            >::type;
        };

        // We did not find the insertion point, but there is only one element
        // left. We insert at the end of the list, and we're done.
        template <typename Pred, std::size_t Insert, std::size_t ...Left, std::size_t Last>
        struct insert<Pred, Insert, false, std::index_sequence<Left...>, Last> {
            using type = std::index_sequence<Left..., Last, Insert>;
        };

        // We found the insertion point, we're done.
        template <typename Pred, std::size_t Insert, std::size_t ...Left, std::size_t ...Right>
        struct insert<Pred, Insert, true, std::index_sequence<Left...>, Right...> {
            using type = std::index_sequence<Left..., Insert, Right...>;
        };


        template <typename Pred, typename Result, std::size_t ...T>
        struct insertion_sort_impl;

        template <typename Pred,
                  std::size_t Result1, std::size_t ...Result,
                  std::size_t T, std::size_t ...Ts>
        struct insertion_sort_impl<Pred, std::index_sequence<Result1, Result...>, T, Ts...> {
            using type = typename insertion_sort_impl<
                Pred,
                typename insert<
                    Pred, T, (bool)Pred::template apply<T, Result1>::value,
                    std::index_sequence<>,
                    Result1, Result...
                >::type,
                Ts...
            >::type;
        };

        template <typename Pred, std::size_t T, std::size_t ...Ts>
        struct insertion_sort_impl<Pred, std::index_sequence<>, T, Ts...> {
            using type = typename insertion_sort_impl<
                Pred, std::index_sequence<T>, Ts...
            >::type;
        };

        template <typename Pred, typename Result>
        struct insertion_sort_impl<Pred, Result> {
            using type = Result;
        };

        template <typename Pred, typename Indices>
        struct sort_helper;

        template <typename Pred, std::size_t ...i>
        struct sort_helper<Pred, std::index_sequence<i...>> {
            using type = typename insertion_sort_impl<
                Pred, std::index_sequence<>, i...
            >::type;
        };
    } // end namespace detail

    template <typename S, bool condition>
    struct sort_impl<S, when<condition>> : default_ {
        template <typename Xs, std::size_t ...i>
        static constexpr auto apply_impl(Xs&& xs, std::index_sequence<i...>) {
            return hana::make<S>(hana::at_c<i>(static_cast<Xs&&>(xs))...);
        }

        template <typename Xs, typename Pred>
        static constexpr auto apply(Xs&& xs, Pred const&) {
            constexpr std::size_t Len = decltype(hana::length(xs))::value;
            using Indices = typename detail::sort_helper<
                detail::sort_predicate<Xs&&, Pred>,
                std::make_index_sequence<Len>
            >::type;

            return apply_impl(static_cast<Xs&&>(xs), Indices{});
        }

        template <typename Xs>
        static constexpr auto apply(Xs&& xs)
        { return sort_impl::apply(static_cast<Xs&&>(xs), hana::less); }
    };
BOOST_HANA_NAMESPACE_END

#endif // !BOOST_HANA_SORT_HPP
Commit	Line	Data
7c673cae FG	1	/*!
	2	@file
	3	Defines `boost::hana::sort`.
	4
	5	@copyright Louis Dionne 2013-2016
	6	Distributed under the Boost Software License, Version 1.0.
	7	(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
	8	*/
	9
	10	#ifndef BOOST_HANA_SORT_HPP
	11	#define BOOST_HANA_SORT_HPP
	12
	13	#include <boost/hana/fwd/sort.hpp>
	14
	15	#include <boost/hana/at.hpp>
	16	#include <boost/hana/concept/sequence.hpp>
	17	#include <boost/hana/config.hpp>
	18	#include <boost/hana/core/dispatch.hpp>
	19	#include <boost/hana/core/make.hpp>
	20	#include <boost/hana/detail/nested_by.hpp> // required by fwd decl
	21	#include <boost/hana/length.hpp>
	22	#include <boost/hana/less.hpp>
	23
	24	#include <utility> // std::declval, std::index_sequence
	25
	26
	27	BOOST_HANA_NAMESPACE_BEGIN
	28	//! @cond
	29	template <typename Xs, typename Predicate>
	30	constexpr auto sort_t::operator()(Xs&& xs, Predicate&& pred) const {
	31	using S = typename hana::tag_of<Xs>::type;
	32	using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>,
	33	hana::Sequence<S>::value
	34	);
	35
	36	#ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
	37	static_assert(hana::Sequence<S>::value,
	38	"hana::sort(xs, predicate) requires 'xs' to be a Sequence");
	39	#endif
	40
	41	return Sort::apply(static_cast<Xs&&>(xs),
	42	static_cast<Predicate&&>(pred));
	43	}
	44
	45	template <typename Xs>
	46	constexpr auto sort_t::operator()(Xs&& xs) const {
	47	using S = typename hana::tag_of<Xs>::type;
	48	using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>,
	49	hana::Sequence<S>::value
	50	);
	51
	52	#ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
	53	static_assert(hana::Sequence<S>::value,
	54	"hana::sort(xs) requires 'xs' to be a Sequence");
	55	#endif
	56
	57	return Sort::apply(static_cast<Xs&&>(xs));
	58	}
	59	//! @endcond
	60
	61	namespace detail {
	62	template <typename Xs, typename Pred>
	63	struct sort_predicate {
	64	template <std::size_t I, std::size_t J>
65	using apply = decltype(std::declval<Pred>()(
66	hana::at_c<I>(std::declval<Xs>()),
67	hana::at_c<J>(std::declval<Xs>())
68	));
69	};
70
71	template <typename Pred, std::size_t Insert, bool IsInsertionPoint,
72	typename Left,
73	std::size_t ...Right>
74	struct insert;
75
76	// We did not find the insertion point; continue processing elements
77	// recursively.
78	template <
79	typename Pred, std::size_t Insert,
80	std::size_t ...Left,
81	std::size_t Right1, std::size_t Right2, std::size_t ...Right
82	>
83	struct insert<Pred, Insert, false,
84	std::index_sequence<Left...>,
85	Right1, Right2, Right...
86	> {
87	using type = typename insert<
88	Pred, Insert, (bool)Pred::template apply<Insert, Right2>::value,
89	std::index_sequence<Left..., Right1>,
90	Right2, Right...
91	>::type;
92	};
93
94	// We did not find the insertion point, but there is only one element
95	// left. We insert at the end of the list, and we're done.
96	template <typename Pred, std::size_t Insert, std::size_t ...Left, std::size_t Last>
97	struct insert<Pred, Insert, false, std::index_sequence<Left...>, Last> {
98	using type = std::index_sequence<Left..., Last, Insert>;
99	};
100
101	// We found the insertion point, we're done.
102	template <typename Pred, std::size_t Insert, std::size_t ...Left, std::size_t ...Right>
103	struct insert<Pred, Insert, true, std::index_sequence<Left...>, Right...> {
104	using type = std::index_sequence<Left..., Insert, Right...>;
105	};
106
107
108	template <typename Pred, typename Result, std::size_t ...T>
109	struct insertion_sort_impl;
110
111	template <typename Pred,
112	std::size_t Result1, std::size_t ...Result,
113	std::size_t T, std::size_t ...Ts>
114	struct insertion_sort_impl<Pred, std::index_sequence<Result1, Result...>, T, Ts...> {
115	using type = typename insertion_sort_impl<
116	Pred,
117	typename insert<
118	Pred, T, (bool)Pred::template apply<T, Result1>::value,
119	std::index_sequence<>,
120	Result1, Result...
121	>::type,
122	Ts...
123	>::type;
124	};
125
126	template <typename Pred, std::size_t T, std::size_t ...Ts>
127	struct insertion_sort_impl<Pred, std::index_sequence<>, T, Ts...> {
128	using type = typename insertion_sort_impl<
129	Pred, std::index_sequence<T>, Ts...
130	>::type;
131	};
132
133	template <typename Pred, typename Result>
134	struct insertion_sort_impl<Pred, Result> {
135	using type = Result;
136	};
137
138	template <typename Pred, typename Indices>
139	struct sort_helper;
140
141	template <typename Pred, std::size_t ...i>
142	struct sort_helper<Pred, std::index_sequence<i...>> {
143	using type = typename insertion_sort_impl<
144	Pred, std::index_sequence<>, i...
145	>::type;
146	};
147	} // end namespace detail
148
149	template <typename S, bool condition>
150	struct sort_impl<S, when<condition>> : default_ {
151	template <typename Xs, std::size_t ...i>
152	static constexpr auto apply_impl(Xs&& xs, std::index_sequence<i...>) {
153	return hana::make<S>(hana::at_c<i>(static_cast<Xs&&>(xs))...);
154	}
155
156	template <typename Xs, typename Pred>
157	static constexpr auto apply(Xs&& xs, Pred const&) {
158	constexpr std::size_t Len = decltype(hana::length(xs))::value;
159	using Indices = typename detail::sort_helper<
160	detail::sort_predicate<Xs&&, Pred>,
161	std::make_index_sequence<Len>
162	>::type;
163
164	return apply_impl(static_cast<Xs&&>(xs), Indices{});
165	}
166
167	template <typename Xs>
168	static constexpr auto apply(Xs&& xs)
169	{ return sort_impl::apply(static_cast<Xs&&>(xs), hana::less); }
170	};
171	BOOST_HANA_NAMESPACE_END
172
173	#endif // !BOOST_HANA_SORT_HPP