1 //Templated Spreadsort-based implementation of float_sort and float_mem_cast
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)
8 // See http://www.boost.org/libs/sort/ for library home page.
11 Some improvements suggested by:
12 Phil Endecott and Frank Gennari
13 float_mem_cast fix provided by:
17 #ifndef BOOST_FLOAT_SORT_HPP
18 #define BOOST_FLOAT_SORT_HPP
23 #include <boost/static_assert.hpp>
24 #include <boost/sort/spreadsort/detail/constants.hpp>
25 #include <boost/sort/spreadsort/detail/float_sort.hpp>
29 namespace spreadsort
{
32 \brief Casts a float to the specified integer type.
34 \tparam Data_type Floating-point IEEE 754/IEC559 type.
35 \tparam Cast_type Integer type (same size) to which to cast.
40 int operator()(const DATA_TYPE &x, const unsigned offset) const {
41 return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
46 template<class Data_type
, class Cast_type
>
48 float_mem_cast(const Data_type
& data
)
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
);
55 std::memcpy(&result
, &data
, sizeof(Cast_type
));
61 \brief @c float_sort with casting to the appropriate size.
63 \param[in] first Iterator pointer to first element.
64 \param[in] last Iterator pointing to one beyond the end of data.
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>
69 <a href="../../doc/graph/osx_float_sort.htm"> osx_float_sort</a>
73 \par A simple example of sorting some floating-point is:
79 spreadsort(vec.begin(), vec.end());
81 \par The sorted vector contains ascending values "1.0 1.3 2.3".
84 template <class RandomAccessIter
>
85 inline void float_sort(RandomAccessIter first
, RandomAccessIter last
)
87 if (last
- first
< detail::min_sort_size
)
88 std::sort(first
, last
);
90 detail::float_sort(first
, last
);
94 \brief Floating-point sort algorithm using random access iterators with just right-shift functor.
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.
101 template <class RandomAccessIter
, class Right_shift
>
102 inline void float_sort(RandomAccessIter first
, RandomAccessIter last
,
105 if (last
- first
< detail::min_sort_size
)
106 std::sort(first
, last
);
108 detail::float_sort(first
, last
, rshift(*first
, 0), rshift
);
113 \brief Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
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.
121 template <class RandomAccessIter
, class Right_shift
, class Compare
>
122 inline void float_sort(RandomAccessIter first
, RandomAccessIter last
,
123 Right_shift rshift
, Compare comp
)
125 if (last
- first
< detail::min_sort_size
)
126 std::sort(first
, last
, comp
);
128 detail::float_sort(first
, last
, rshift(*first
, 0), rshift
, comp
);