1 //Templated Spreadsort-based implementation of float_sort and float_mem_cast 2 3 // Copyright Steven J. Ross 2001 - 2014. 4 // Distributed under the Boost Software License, Version 1.0. 5 // (See accompanying file LICENSE_1_0.txt or copy at 6 // http://www.boost.org/LICENSE_1_0.txt) 7 8 // See http://www.boost.org/libs/sort/ for library home page. 9 10 /* 11 Some improvements suggested by: 12 Phil Endecott and Frank Gennari 13 float_mem_cast fix provided by: 14 Scott McMurray 15 */ 16 17 #ifndef BOOST_FLOAT_SORT_HPP 18 #define BOOST_FLOAT_SORT_HPP 19 #include <algorithm> 20 #include <vector> 21 #include <cstring> 22 #include <limits> 23 #include <boost/static_assert.hpp> 24 #include <boost/sort/spreadsort/detail/constants.hpp> 25 #include <boost/sort/spreadsort/detail/float_sort.hpp> 26 #include <boost/range/begin.hpp> 27 #include <boost/range/end.hpp> 28 29 namespace boost { 30 namespace sort { 31 namespace spreadsort { 32 33 /*! 34 \brief Casts a float to the specified integer type. 35 36 \tparam Data_type Floating-point IEEE 754/IEC559 type. 37 \tparam Cast_type Integer type (same size) to which to cast. 38 39 \par Example: 40 \code 41 struct rightshift { 42 int operator()(const DATA_TYPE &x, const unsigned offset) const { 43 return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset; 44 } 45 }; 46 \endcode 47 */ 48 template<class Data_type, class Cast_type> 49 inline Cast_type float_mem_cast(const Data_type & data)50 float_mem_cast(const Data_type & data) 51 { 52 // Only cast IEEE floating-point numbers, and only to a same-sized integer. 53 BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type)); 54 BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559); 55 BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer); 56 Cast_type result; 57 std::memcpy(&result, &data, sizeof(Cast_type)); 58 return result; 59 } 60 61 62 /*! 63 \brief @c float_sort with casting to the appropriate size. 64 65 \param[in] first Iterator pointer to first element. 66 \param[in] last Iterator pointing to one beyond the end of data. 67 68 Some performance plots of runtime vs. n and log(range) are provided:\n 69 <a href="../../doc/graph/windows_float_sort.htm"> windows_float_sort</a> 70 \n 71 <a href="../../doc/graph/osx_float_sort.htm"> osx_float_sort</a> 72 73 74 75 \par A simple example of sorting some floating-point is: 76 \code 77 vector<float> vec; 78 vec.push_back(1.0); 79 vec.push_back(2.3); 80 vec.push_back(1.3); 81 spreadsort(vec.begin(), vec.end()); 82 \endcode 83 \par The sorted vector contains ascending values "1.0 1.3 2.3". 84 85 */ 86 template <class RandomAccessIter> float_sort(RandomAccessIter first,RandomAccessIter last)87 inline void float_sort(RandomAccessIter first, RandomAccessIter last) 88 { 89 if (last - first < detail::min_sort_size) 90 boost::sort::pdqsort(first, last); 91 else 92 detail::float_sort(first, last); 93 } 94 95 /*! 96 \brief Floating-point sort algorithm using range. 97 98 \param[in] range Range [first, last) for sorting. 99 100 */ 101 template <class Range> float_sort(Range & range)102 inline void float_sort(Range& range) 103 { 104 float_sort(boost::begin(range), boost::end(range)); 105 } 106 107 /*! 108 \brief Floating-point sort algorithm using random access iterators with just right-shift functor. 109 110 \param[in] first Iterator pointer to first element. 111 \param[in] last Iterator pointing to one beyond the end of data. 112 \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits. 113 114 */ 115 template <class RandomAccessIter, class Right_shift> float_sort(RandomAccessIter first,RandomAccessIter last,Right_shift rshift)116 inline void float_sort(RandomAccessIter first, RandomAccessIter last, 117 Right_shift rshift) 118 { 119 if (last - first < detail::min_sort_size) 120 boost::sort::pdqsort(first, last); 121 else 122 detail::float_sort(first, last, rshift(*first, 0), rshift); 123 } 124 125 /*! 126 \brief Floating-point sort algorithm using range with just right-shift functor. 127 128 \param[in] range Range [first, last) for sorting. 129 \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits. 130 131 */ 132 template <class Range, class Right_shift> float_sort(Range & range,Right_shift rshift)133 inline void float_sort(Range& range, Right_shift rshift) 134 { 135 float_sort(boost::begin(range), boost::end(range), rshift); 136 } 137 138 139 /*! 140 \brief Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator. 141 142 \param[in] first Iterator pointer to first element. 143 \param[in] last Iterator pointing to one beyond the end of data. 144 \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits. 145 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. 146 */ 147 148 template <class RandomAccessIter, class Right_shift, class Compare> float_sort(RandomAccessIter first,RandomAccessIter last,Right_shift rshift,Compare comp)149 inline void float_sort(RandomAccessIter first, RandomAccessIter last, 150 Right_shift rshift, Compare comp) 151 { 152 if (last - first < detail::min_sort_size) 153 boost::sort::pdqsort(first, last, comp); 154 else 155 detail::float_sort(first, last, rshift(*first, 0), rshift, comp); 156 } 157 158 159 /*! 160 \brief Float sort algorithm using range with both right-shift and user-defined comparison operator. 161 162 \param[in] range Range [first, last) for sorting. 163 \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits. 164 \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. 165 */ 166 167 template <class Range, class Right_shift, class Compare> float_sort(Range & range,Right_shift rshift,Compare comp)168 inline void float_sort(Range& range, Right_shift rshift, Compare comp) 169 { 170 float_sort(boost::begin(range), boost::end(range), rshift, comp); 171 } 172 } 173 } 174 } 175 176 #endif 177