]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
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 | #include <boost/range/begin.hpp> | |
27 | #include <boost/range/end.hpp> | |
28 | ||
29 | namespace boost { | |
30 | namespace sort { | |
31 | namespace 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(&result, &data, 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 | ||
68 | Some 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) | |
92f5a8d4 | 90 | boost::sort::pdqsort(first, last); |
11fdf7f2 TL |
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) | |
92f5a8d4 | 120 | boost::sort::pdqsort(first, last); |
11fdf7f2 TL |
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) | |
92f5a8d4 | 153 | boost::sort::pdqsort(first, last, comp); |
11fdf7f2 TL |
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 |