ceph/src/boost/boost/sort/spreadsort/float_sort.hpp

   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
  27 namespace boost {
  28 namespace sort {
  29 namespace spreadsort {
  30
  31   /*!
  32   \brief Casts a float to the specified integer type.
  33
  34   \tparam Data_type Floating-point IEEE 754/IEC559 type.
  35   \tparam Cast_type Integer type (same size) to which to cast.
  36
  37   \par Example:
  38   \code
  39   struct rightshift {
  40     int operator()(const DATA_TYPE &x, const unsigned offset) const {
  41       return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
  42     }
  43   };
  44   \endcode
  45   */
  46   template<class Data_type, class Cast_type>
  47   inline Cast_type
  48   float_mem_cast(const Data_type & data)
  49   {
  50     // Only cast IEEE floating-point numbers, and only to a same-sized integer.
  51     BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type));
  52     BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559);
  53     BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer);
  54     Cast_type result;
  55     std::memcpy(&result, &data, sizeof(Cast_type));
  56     return result;
  57   }
  58
  59
  60   /*!
  61     \brief @c float_sort with casting to the appropriate size.
  62
  63     \param[in] first Iterator pointer to first element.
  64     \param[in] last Iterator pointing to one beyond the end of data.
  65
  66 Some performance plots of runtime vs. n and log(range) are provided:\n
  67    <a href="../../doc/graph/windows_float_sort.htm"> windows_float_sort</a>
  68    \n
  69    <a href="../../doc/graph/osx_float_sort.htm"> osx_float_sort</a>
  70
  71
  72
  73    \par A simple example of sorting some floating-point is:
  74    \code
  75      vector<float> vec;
  76      vec.push_back(1.0);
  77      vec.push_back(2.3);
  78      vec.push_back(1.3);
  79      spreadsort(vec.begin(), vec.end());
  80    \endcode
  81    \par The sorted vector contains ascending values "1.0 1.3 2.3".
  82
  83   */
  84   template <class RandomAccessIter>
  85   inline void float_sort(RandomAccessIter first, RandomAccessIter last)
  86   {
  87     if (last - first < detail::min_sort_size)
  88       std::sort(first, last);
  89     else
  90       detail::float_sort(first, last);
  91   }
  92
  93   /*!
  94     \brief Floating-point sort algorithm using random access iterators with just right-shift functor.
  95
  96     \param[in] first Iterator pointer to first element.
  97     \param[in] last Iterator pointing to one beyond the end of data.
  98     \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
  99
 100   */
 101   template <class RandomAccessIter, class Right_shift>
 102   inline void float_sort(RandomAccessIter first, RandomAccessIter last,
 103                          Right_shift rshift)
 104   {
 105     if (last - first < detail::min_sort_size)
 106       std::sort(first, last);
 107     else
 108       detail::float_sort(first, last, rshift(*first, 0), rshift);
 109   }
 110
 111
 112   /*!
 113    \brief Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
 114
 115    \param[in] first Iterator pointer to first element.
 116    \param[in] last Iterator pointing to one beyond the end of data.
 117    \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
 118    \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
 119   */
 120
 121   template <class RandomAccessIter, class Right_shift, class Compare>
 122   inline void float_sort(RandomAccessIter first, RandomAccessIter last,
 123                          Right_shift rshift, Compare comp)
 124   {
 125     if (last - first < detail::min_sort_size)
 126       std::sort(first, last, comp);
 127     else
 128       detail::float_sort(first, last, rshift(*first, 0), rshift, comp);
 129   }
 130 }
 131 }
 132 }
 133
 134 #endif