sort/spreadsort/spreadsort.hpp

0001 // Templated generic hybrid sorting
0002
0003 //          Copyright Steven J. Ross 2001 - 2009.
0004 // Distributed under the Boost Software License, Version 1.0.
0005 //    (See accompanying file LICENSE_1_0.txt or copy at
0006 //          http://www.boost.org/LICENSE_1_0.txt)
0007
0008 // See http://www.boost.org/libs/sort/ for library home page.
0009
0010 /*
0011 Some improvements suggested by:
0012 Phil Endecott and Frank Gennari
0013 float_mem_cast fix provided by:
0014 Scott McMurray
0015  Range support provided by:
0016  Alexander Zaitsev
0017 */
0018
0019 #ifndef BOOST_SORT_SPREADSORT_HPP
0020 #define BOOST_SORT_SPREADSORT_HPP
0021 #include <algorithm>
0022 #include <vector>
0023 #include <cstring>
0024 #include <string>
0025 #include <limits>
0026 #include <boost/type_traits.hpp>
0027 #include <boost/sort/spreadsort/integer_sort.hpp>
0028 #include <boost/sort/spreadsort/float_sort.hpp>
0029 #include <boost/sort/spreadsort/string_sort.hpp>
0030 #include <boost/range/begin.hpp>
0031 #include <boost/range/end.hpp>
0032
0033 namespace boost {
0034 namespace sort {
0035
0036 /*! Namespace for spreadsort sort variants for different data types.
0037 \note Use hyperlinks (coloured) to get detailed information about functions.
0038 */
0039 namespace spreadsort {
0040
0041   /*!
0042     \brief Generic @c spreadsort variant detecting integer-type elements so call to @c integer_sort.
0043     \details If the data type provided is an integer, @c integer_sort is used.
0044     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
0045     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
0046     \param[in] first Iterator pointer to first element.
0047     \param[in] last Iterator pointing to one beyond the end of data.
0048
0049     \pre [@c first, @c last) is a valid range.
0050     \pre @c RandomAccessIter @c value_type is mutable.
0051     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
0052     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
0053     which returns an integer-type right-shifted a specified number of bits.
0054     \post The elements in the range [@c first, @c last) are sorted in ascending order.
0055   */
0056
0057   template <class RandomAccessIter>
0058   inline typename boost::enable_if_c< std::numeric_limits<
0059     typename std::iterator_traits<RandomAccessIter>::value_type >::is_integer,
0060     void >::type
0061   spreadsort(RandomAccessIter first, RandomAccessIter last)
0062   {
0063     integer_sort(first, last);
0064   }
0065
0066   /*!
0067     \brief Generic @c spreadsort variant detecting float element type so call to @c float_sort.
0068     \details If the data type provided is a float or castable-float, @c float_sort is used.
0069     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
0070     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
0071
0072     \param[in] first Iterator pointer to first element.
0073     \param[in] last Iterator pointing to one beyond the end of data.
0074
0075     \pre [@c first, @c last) is a valid range.
0076     \pre @c RandomAccessIter @c value_type is mutable.
0077     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
0078     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
0079     which returns an integer-type right-shifted a specified number of bits.
0080     \post The elements in the range [@c first, @c last) are sorted in ascending order.
0081   */
0082
0083   template <class RandomAccessIter>
0084   inline typename boost::enable_if_c< !std::numeric_limits<
0085     typename std::iterator_traits<RandomAccessIter>::value_type >::is_integer
0086     && std::numeric_limits<
0087     typename std::iterator_traits<RandomAccessIter>::value_type >::is_iec559,
0088     void >::type
0089   spreadsort(RandomAccessIter first, RandomAccessIter last)
0090   {
0091     float_sort(first, last);
0092   }
0093
0094   /*!
0095     \brief  Generic @c spreadsort variant detecting string element type so call to @c string_sort for @c std::strings.
0096     \details If the data type provided is a string, @c string_sort is used.
0097     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
0098     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
0099
0100     \param[in] first Iterator pointer to first element.
0101     \param[in] last Iterator pointing to one beyond the end of data.
0102
0103     \pre [@c first, @c last) is a valid range.
0104     \pre @c RandomAccessIter @c value_type is mutable.
0105     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
0106     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
0107     which returns an integer-type right-shifted a specified number of bits.
0108     \post The elements in the range [@c first, @c last) are sorted in ascending order.
0109   */
0110
0111   template <class RandomAccessIter>
0112   inline typename boost::enable_if_c<
0113     is_same<typename std::iterator_traits<RandomAccessIter>::value_type,
0114             typename std::string>::value, void >::type
0115   spreadsort(RandomAccessIter first, RandomAccessIter last)
0116   {
0117     string_sort(first, last);
0118   }
0119
0120   /*!
0121     \brief  Generic @c spreadsort variant detecting string element type so call to @c string_sort for @c std::wstrings.
0122     \details If the data type provided is a wstring, @c string_sort is used.
0123     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
0124     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.  Also, 2-byte wide-characters are the limit above which string_sort is inefficient, so on platforms with wider characters, this will not accept wstrings.
0125
0126     \param[in] first Iterator pointer to first element.
0127     \param[in] last Iterator pointing to one beyond the end of data.
0128
0129     \pre [@c first, @c last) is a valid range.
0130     \pre @c RandomAccessIter @c value_type is mutable.
0131     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
0132     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
0133     which returns an integer-type right-shifted a specified number of bits.
0134     \post The elements in the range [@c first, @c last) are sorted in ascending order.
0135   */
0136   template <class RandomAccessIter>
0137   inline typename boost::enable_if_c<
0138     is_same<typename std::iterator_traits<RandomAccessIter>::value_type,
0139             typename std::wstring>::value &&
0140     sizeof(wchar_t) == 2, void >::type
0141   spreadsort(RandomAccessIter first, RandomAccessIter last)
0142   {
0143     boost::uint16_t unused = 0;
0144     string_sort(first, last, unused);
0145   }
0146
0147 /*!
0148 \brief Generic @c spreadsort variant detects value_type and calls required sort function.
0149 \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
0150 as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
0151
0152 \param[in] range Range [first, last) for sorting.
0153
0154 \pre [@c first, @c last) is a valid range.
0155 \post The elements in the range [@c first, @c last) are sorted in ascending order.
0156 */
0157
0158 template <class Range>
0159 void spreadsort(Range& range)
0160 {
0161     spreadsort(boost::begin(range), boost::end(range));
0162 }
0163
0164
0165 } // namespace spreadsort
0166 } // namespace sort
0167 } // namespace boost
0168
0169 #endif