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/*
11Some improvements suggested by:
12Phil Endecott and Frank Gennari
13float_mem_cast fix provided by:
14Scott 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
29namespace boost {
30namespace sort {
31namespace 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
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(dest: &result, src: &data, n: 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
68Some 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>
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>
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>
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>
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>
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>
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

source code of boost/libs/sort/include/boost/sort/spreadsort/float_sort.hpp