Chris@16: // Boost.Units - A C++ library for zero-overhead dimensional analysis and 
Chris@16: // unit/quantity manipulation and conversion
Chris@16: //
Chris@16: // Copyright (C) 2003-2008 Matthias Christian Schabel
Chris@16: // Copyright (C) 2008 Steven Watanabe
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_UNITS_DETAIL_SORT_HPP
Chris@16: #define BOOST_UNITS_DETAIL_SORT_HPP
Chris@16: 
Chris@16: #include <boost/mpl/size.hpp>
Chris@16: #include <boost/mpl/begin.hpp>
Chris@16: #include <boost/mpl/next.hpp>
Chris@16: #include <boost/mpl/deref.hpp>
Chris@16: #include <boost/mpl/push_front.hpp>
Chris@16: #include <boost/mpl/less.hpp>
Chris@16: 
Chris@16: #include <boost/units/dimensionless_type.hpp>
Chris@16: #include <boost/units/detail/dimension_list.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: namespace units {
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: template<int N>
Chris@16: struct insertion_sort_insert;
Chris@16: 
Chris@16: template<bool is_greater>
Chris@16: struct insertion_sort_comparison_impl;
Chris@16: 
Chris@16: // have to recursively add the element to the next sequence.
Chris@16: template<>
Chris@16: struct insertion_sort_comparison_impl<true> {
Chris@16:     template<class Begin, int N, class T>
Chris@16:     struct apply {
Chris@16:         typedef list<
Chris@16:             typename Begin::item,
Chris@16:             typename insertion_sort_insert<N - 1>::template apply<
Chris@16:                 typename Begin::next,
Chris@16:                 T
Chris@16:             >::type
Chris@16:         > type;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: // prepend the current element
Chris@16: template<>
Chris@16: struct insertion_sort_comparison_impl<false> {
Chris@16:     template<class Begin, int N, class T>
Chris@16:     struct apply {
Chris@16:         typedef list<T, Begin> type;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: template<int N>
Chris@16: struct insertion_sort_insert {
Chris@16:     template<class Begin, class T>
Chris@16:     struct apply {
Chris@16:         typedef typename insertion_sort_comparison_impl<mpl::less<typename Begin::item, T>::value>::template apply<
Chris@16:             Begin,
Chris@16:             N,
Chris@16:             T
Chris@16:         >::type type;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: template<>
Chris@16: struct insertion_sort_insert<0> {
Chris@16:     template<class Begin, class T>
Chris@16:     struct apply {
Chris@16:         typedef list<T, dimensionless_type> type;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: template<int N>
Chris@16: struct insertion_sort_impl {
Chris@16:     template<class Begin>
Chris@16:     struct apply {
Chris@16:         typedef typename insertion_sort_impl<N - 1>::template apply<typename Begin::next>::type next;
Chris@16:         typedef typename insertion_sort_insert<(next::size::value)>::template apply<next, typename Begin::item>::type type;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: template<>
Chris@16: struct insertion_sort_impl<0> {
Chris@16:     template<class Begin>
Chris@16:     struct apply {
Chris@16:         typedef dimensionless_type type;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: template<class T>
Chris@16: struct insertion_sort
Chris@16: {
Chris@16:     typedef typename insertion_sort_impl<T::size::value>::template apply<T>::type type;
Chris@16: };
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: } // namespace units
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif