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