sort/spreadsort/float_sort.hpp

0001 //Templated Spreadsort-based implementation of float_sort and float_mem_cast
0002
0003 //          Copyright Steven J. Ross 2001 - 2014.
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 */
0016
0017 #ifndef BOOST_FLOAT_SORT_HPP
0018 #define BOOST_FLOAT_SORT_HPP
0019 #include <algorithm>
0020 #include <vector>
0021 #include <cstring>
0022 #include <limits>
0023 #include <boost/static_assert.hpp>
0024 #include <boost/sort/spreadsort/detail/constants.hpp>
0025 #include <boost/sort/spreadsort/detail/float_sort.hpp>
0026 #include <boost/range/begin.hpp>
0027 #include <boost/range/end.hpp>
0028
0029 namespace boost {
0030 namespace sort {
0031 namespace spreadsort {
0032
0033   /*!
0034   \brief Casts a float to the specified integer type.
0035
0036   \tparam Data_type Floating-point IEEE 754/IEC559 type.
0037   \tparam Cast_type Integer type (same size) to which to cast.
0038
0039   \par Example:
0040   \code
0041   struct rightshift {
0042     int operator()(const DATA_TYPE &x, const unsigned offset) const {
0043       return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
0044     }
0045   };
0046   \endcode
0047   */
0048   template<class Data_type, class Cast_type>
0049   inline Cast_type
0050   float_mem_cast(const Data_type & data)
0051   {
0052     // Only cast IEEE floating-point numbers, and only to a same-sized integer.
0053     BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type));
0054     BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559);
0055     BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer);
0056     Cast_type result;
0057     std::memcpy(&result, &data, sizeof(Cast_type));
0058     return result;
0059   }
0060
0061
0062   /*!
0063     \brief @c float_sort with casting to the appropriate size.
0064
0065     \param[in] first Iterator pointer to first element.
0066     \param[in] last Iterator pointing to one beyond the end of data.
0067
0068 Some performance plots of runtime vs. n and log(range) are provided:\n
0069    <a href="../../doc/graph/windows_float_sort.htm"> windows_float_sort</a>
0070    \n
0071    <a href="../../doc/graph/osx_float_sort.htm"> osx_float_sort</a>
0072
0073
0074
0075    \par A simple example of sorting some floating-point is:
0076    \code
0077      vector<float> vec;
0078      vec.push_back(1.0);
0079      vec.push_back(2.3);
0080      vec.push_back(1.3);
0081      spreadsort(vec.begin(), vec.end());
0082    \endcode
0083    \par The sorted vector contains ascending values "1.0 1.3 2.3".
0084
0085   */
0086   template <class RandomAccessIter>
0087   inline void float_sort(RandomAccessIter first, RandomAccessIter last)
0088   {
0089     if (last - first < detail::min_sort_size)
0090       boost::sort::pdqsort(first, last);
0091     else
0092       detail::float_sort(first, last);
0093   }
0094
0095     /*!
0096     \brief Floating-point sort algorithm using range.
0097
0098     \param[in] range Range [first, last) for sorting.
0099
0100   */
0101   template <class Range>
0102   inline void float_sort(Range& range)
0103   {
0104     float_sort(boost::begin(range), boost::end(range));
0105   }
0106
0107   /*!
0108     \brief Floating-point sort algorithm using random access iterators with just right-shift functor.
0109
0110     \param[in] first Iterator pointer to first element.
0111     \param[in] last Iterator pointing to one beyond the end of data.
0112     \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
0113
0114   */
0115   template <class RandomAccessIter, class Right_shift>
0116   inline void float_sort(RandomAccessIter first, RandomAccessIter last,
0117                          Right_shift rshift)
0118   {
0119     if (last - first < detail::min_sort_size)
0120       boost::sort::pdqsort(first, last);
0121     else
0122       detail::float_sort(first, last, rshift(*first, 0), rshift);
0123   }
0124
0125     /*!
0126     \brief Floating-point sort algorithm using range with just right-shift functor.
0127
0128     \param[in] range Range [first, last) for sorting.
0129     \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
0130
0131   */
0132   template <class Range, class Right_shift>
0133   inline void float_sort(Range& range, Right_shift rshift)
0134   {
0135       float_sort(boost::begin(range), boost::end(range), rshift);
0136   }
0137
0138
0139   /*!
0140    \brief Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
0141
0142    \param[in] first Iterator pointer to first element.
0143    \param[in] last Iterator pointing to one beyond the end of data.
0144    \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
0145    \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
0146   */
0147
0148   template <class RandomAccessIter, class Right_shift, class Compare>
0149   inline void float_sort(RandomAccessIter first, RandomAccessIter last,
0150                          Right_shift rshift, Compare comp)
0151   {
0152     if (last - first < detail::min_sort_size)
0153       boost::sort::pdqsort(first, last, comp);
0154     else
0155       detail::float_sort(first, last, rshift(*first, 0), rshift, comp);
0156   }
0157
0158
0159     /*!
0160    \brief Float sort algorithm using range with both right-shift and user-defined comparison operator.
0161
0162    \param[in] range Range [first, last) for sorting.
0163    \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
0164    \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
0165   */
0166
0167   template <class Range, class Right_shift, class Compare>
0168   inline void float_sort(Range& range, Right_shift rshift, Compare comp)
0169   {
0170       float_sort(boost::begin(range), boost::end(range), rshift, comp);
0171   }
0172 }
0173 }
0174 }
0175
0176 #endif